Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917568417103872 |
|---|---|
| author | Tamaru, Asuka Hara, Junya Higashi, Hiroshi Tanaka, Yuichi Ortega, Antonio |
| author_facet | Tamaru, Asuka Hara, Junya Higashi, Hiroshi Tanaka, Yuichi Ortega, Antonio |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_08245 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective Tamaru, Asuka Hara, Junya Higashi, Hiroshi Tanaka, Yuichi Ortega, Antonio Machine Learning Signal Processing 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). |
| title | Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective |
| topic | Machine Learning Signal Processing |
| url | https://arxiv.org/abs/2401.08245 |