# Distribution-Informed Adaptation for kNN Graph Construction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 4 Aug 2023.

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

- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [Fast k-means based on KNN Graph](https://mlsanity.com/paper/1705.01813/) (2017)
- [PL-kNN: A Parameterless Nearest Neighbors Classifier](https://mlsanity.com/paper/2209.12647/) (2022)

## Abstract (arXiv)

Graph-based kNN algorithms have garnered widespread popularity for machine learning tasks due to their simplicity and effectiveness. However, as factual data often inherit complex distributions, the conventional kNN graph's reliance on a unified k-value can hinder its performance. A crucial factor behind this challenge is the presence of ambiguous samples along decision boundaries that are inevitably more prone to incorrect classifications. To address the situation, we propose the Distribution-Informed adaptive kNN Graph (DaNNG), which combines adaptive kNN with distribution-aware graph construction. By incorporating an approximation of the distribution with customized k-adaption criteria, DaNNG can significantly improve performance on ambiguous samples, and hence enhance overall accuracy and generalization capability. Through rigorous evaluations on diverse benchmark datasets, DaNNG outperforms state-of-the-art algorithms, showcasing its adaptability and efficacy across various real-world scenarios.