Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs

2022/06/29 by Brennan, Matthew, Bresler, Guy, Huang, Brice · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2206.14896

Abstract

In the anisotropic random geometric graph model, vertices correspond to points drawn from a high-dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to hypothesis test between such a graph and an Erdős-Rényi graph with the same edge probability. If n is the number of vertices and α is the vector of eigenvalues, Eldan and Mikulincer show that detection is possible when n³ ≫ (‖α‖₂/‖α‖₃)⁶ and impossible when n³ ≪ (‖α‖₂/‖α‖₄)⁴. We show detection is impossible when n³ ≪ (‖α‖₂/‖α‖₃)⁶, closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer.

Cited by

• Recovery of latent inner products from an anisotropic Gaussian random geometric graph
• Spectra of high-dimensional sparse random geometric graphs

Related

• Information and dimensionality of anisotropic random geometric graphs
• Testing for high-dimensional geometry in random graphs
• Testing thresholds for high-dimensional sparse random geometric graphs
• Distinguishability threshold for random geometric graphs
• Phase transition in noisy high-dimensional random geometric graphs