# Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Science

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2017.

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

- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [Structural-Entropy-Based Sample Selection for Efficient and Effective Learning](https://mlsanity.com/paper/2410.02268/) (2024)
- [One-shot Conditional Sampling: MMD meets Nearest Neighbors](https://mlsanity.com/paper/2509.25507/) (2025)

## Abstract (arXiv)

If we pick n random points uniformly in [0,1]d and connect each point to its k-nearest neighbors, then it is well known that there exists a giant connected component with high probability. We prove that in [0,1]d it suffices to connect every point to  cd,1 loglogn points chosen randomly among its  cd,2 logn-nearest neighbors to ensure a giant component of size n - o(n) with high probability. This construction yields a much sparser random graph with ~ n loglogn instead of ~ n logn edges that has comparable connectivity properties. This result has nontrivial implications for problems in data science where an affinity matrix is constructed: instead of picking the k-nearest neighbors, one can often pick k' ll k random points out of the k-nearest neighbors without sacrificing efficiency. This can massively simplify and accelerate computation, we illustrate this with several numerical examples.