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

2017/11/13 by Linderman, George C., Mishne, Gal, Kluger, Yuval +1 · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Probability (math.PR)

paper · doi:10.48550/arxiv.1711.04712

Abstract

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 loglogn points chosen randomly among its c_d,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' ≪ 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.

Cited by

• One-shot Conditional Sampling: MMD meets Nearest Neighbors

Related

• From algorithms to connectivity and back: finding a giant component in random k-SAT
• Small components in k-nearest neighbour graphs
• Large Components and Trees of Random Mappings
• A new approach to the giant component problem
• The giant in random graphs is almost local