Randomized near-neighbor graphs, giant components and applications in data science

DOI10.1017/JPR.2020.21zbMATH Open1446.60013arXiv1711.04712OpenAlexW3042432370WikidataQ99350568 ScholiaQ99350568MaRDI QIDQ3299443FDOQ3299443

Authors: Ariel Jaffe, Yuval Kluger, George C. Linderman, Gal Mishne, Stefan Steinerberger 

Publication date: 22 July 2020

Published in: Journal of Applied Probability (Search for Journal in Brave)

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 $simnloglogn$ instead of $simnlogn$ 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^{\prime }llk$ 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.

Full work available at URL: https://arxiv.org/abs/1711.04712

Recommendations

• scientific article; zbMATH DE number 1222330
• On nearest-neighbor graphs
• On the Connectivity of Random k-th Nearest Neighbour Graphs
• On nearest-neighbor graphs
• Connectivity of random k-nearest-neighbour graphs

zbMATH Keywords

random graphconnectivitysparsification\(k\)-nn graph

Mathematics Subject Classification ID

Statistical aspects of big data and data science (62R07) Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Connectivity (05C40)

Cites Work

• Visualizing data using t-SNE
• Diffusion maps
• Random Geometric Graphs
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Weak laws of large numbers in geometric probability
• Probability theory of classical Euclidean optimization problems
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• From graph to manifold Laplacian: the convergence rate
• How the result of graph clustering methods depends on the construction of the graph
• Learning Theory
• The Scottish Book. Mathematics from the Scottish Café. With selected problems from the New Scottish Book
• Algorithms for the Assignment and Transportation Problems
• Connectivity threshold of Bluetooth graphs
• Title not available (Why is that?)
• A randomized algorithm for principal component analysis
• Large deviations for discrete and continuous percolation
• \(k\)-nearest-neighbor clustering and percolation theory
• Connectivity of random k-nearest-neighbour graphs
• The shortest path and the shortest road through n points
• Sharpness in the \(k\)-nearest-neighbours random geometric graph model
• A critical constant for the k nearest-neighbour model
• Small components in \(k\)-nearest neighbour graphs
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Highly connected random geometric graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Shortest Paths Through Pseudo-Random Points in the d-Cube
• New Bounds for the Traveling Salesman Constant
• A new lower bound for the geometric traveling salesman problem in terms of discrepancy
• Title not available (Why is that?)
• Algorithm 971
• Comments on the ``Core vector machines: fast SVM training on very large data sets
• Clustering with t-SNE, provably

Uses Software

• RCV1
• t-SNE
• Algorithm 971
• SpectralNet

This page was built for publication: Randomized near-neighbor graphs, giant components and applications in data science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3299443)