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

Area of Science:

• Computational Geometry
• Graph Theory
• Data Science

Background:

• Random geometric graphs are typically constructed by connecting points to their k-nearest neighbors.
• Ensuring graph connectivity with a minimal number of edges is crucial for efficient algorithms.
• Existing methods often result in dense graphs with O(n log n) edges.

Purpose of the Study:

• To investigate a sparser random graph construction with comparable connectivity properties.
• To reduce the number of edges in random geometric graphs while maintaining a large connected component.
• To explore implications for data science applications, particularly in affinity matrix construction and spectral clustering.

Main Methods:

• Analyzing random geometric graphs in d-dimensional Euclidean space ([0, 1]^d).
• Proving connectivity by connecting each point to a subset of its c log n-nearest neighbors.
• Specifically, connecting to c log log n randomly chosen neighbors from the c log n-nearest neighbors.

Main Results:

• A sparser random graph construction is proposed, requiring only O(n log log n) edges.
• This construction ensures a giant connected component of size n - o(n) with high probability.
• The number of edges is significantly reduced compared to traditional k-nearest neighbor graphs.

Conclusions:

• Connecting points to a small random subset of their nearest neighbors is sufficient for robust connectivity.
• This method offers substantial computational advantages in data science by simplifying and accelerating computations.
• Experimental results demonstrate the effectiveness of this approach in spectral clustering of large datasets.