Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Science
By George C. Linderman, Gal Mishne, Yuval Kluger, Stefan Steinerberger. 2017
17 citations recorded by the source corpus.
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 $ c_{d,1} \log{\log{n}}$ points chosen randomly among its $ c_{d,2} \log{n}-$nearest neighbors to ensure a giant component of size $n - o(n)$ with high probability. This construction yields a much sparser random graph with $\sim n \log\log{n}$ instead of $\sim n \log{n}$ 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.
Subfields: Computational Theory and Mathematics, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Statistics and Probability
Citations in the corpus
- Measuring Association on Topological Spaces Using Kernels and Geometric Graphs (2020, unknown): “[59] Jaffe, A.”
- Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding (2017, methodology): “This would allow for t-SNE based iterative methods to be developed, similar to Mishne et al. (2017), where the the embedding of the cells is used to improve the embedding of the genes, which is then used to improve the embedding of the cells, and so forth.”