# Optimizing k in kNN Graphs with Graph Learning Perspective

arXiv: https://arxiv.org/abs/2401.08245 · HTML: https://mlsanity.com/paper/2401.08245/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 16 Jan 2024.

## Builds on (most cited first, 8 of 8)

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Few-Shot Learning with Graph Neural Networks](https://mlsanity.com/paper/1711.04043/) (2017)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Graph Learning from Filtered Signals: Graph System and Diffusion Kernel Identification](https://mlsanity.com/paper/1803.02553/) (2018)
- [Sparse Graph Learning with Spectrum Prior for Deep Graph Convolutional Networks](https://mlsanity.com/paper/2202.13526/) (2022)

## Built on by (most cited first, 2 of 2)

- [Multiscale Graph Construction Using Non-local Cluster Features](https://mlsanity.com/paper/2411.08371/) (2024)
- [Investigating the Effect of k-NN Preprocessing on Developing Graph Neural Networks: A Fairness-Based Perspective](https://mlsanity.com/paper/2609.33416/) (2026)

## Abstract (arXiv)

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).