2024/01/16 by Asuka Tamaru, Tamaru, Asuka, Junya Hara +7
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Data Visualization and Analytics #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2401.08245
openalex publication_date 2024/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose a method, based on graph signal processing, to optimize the choice of k in k-nearest neighbor graphs (kNNGs). kNN is one of the most popular approaches and is widely used in machine learning and signal processing. The parameter k represents the number of neighbors that are connected to the target node; however, its appropriate selection is still a challenging problem. Therefore, most kNNGs use ad hoc selection methods for k. In the proposed method, we assume that a different k can be chosen for each node. We formulate a discrete optimization problem to seek the best k with a constraint on the sum of distances of the connected nodes. The optimal k values are efficiently obtained without solving a complex optimization. Furthermore, we reveal that the proposed method is closely related to existing graph learning methods. In experiments on real datasets, we demonstrate that the kNNGs obtained with our method are sparse and can determine an appropriate variable number of edges per node. We validate the effectiveness of the proposed method for point cloud denoising, comparing our denoising performance with achievable graph construction methods that can be scaled to typical point cloud sizes (e.g., thousands of nodes).