Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport. (arXiv:2208.00604v1 [stat.ML])

Nearest neighbour graphs are widely used to capture the geometry or topology
of a dataset. One of the most common strategies to construct such a graph is
based on selecting a fixed number k of nearest neighbours (kNN) for each point.
However, the kNN heuristic may become inappropriate when sampling density or
noise level varies across datasets. Strategies that try to get around this
typically introduce additional parameters that need to be tuned. We propose a
simple approach to construct …

arxiv graphs knn ml transport