Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective
Asuka Tamaru Junya Hara Hiroshi Higashi Yuichi Tanaka Antonio Ortega
In this paper, we propose a method, based on graph signal processing, to
optimize the choice of $k$ in $k$-nearest neighbor graphs ($k$NNGs). $k$NN 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 $k$NNGs 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 $k$NNGs 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).