Threshold for detecting high dimensional geometry in anisotropic random geometric graphs

DOI10.1002/RSA.21178MaRDI QIDQ6185052zbMATH OpenFDO

Authors Matthew D. Brennan, Guy Bresler, Brice Huang

Publication date 5 January 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Erdős-Rényi graphhigh-dimensional geometryhypothesis testingrandom geometric graphWishart matrix

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05) Central limit and other weak theorems (60F05) Hypothesis testing in multivariate analysis (62H15)

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 ErdH{o}s-R'enyi graph with the same edge probability. If $n$ is the number of vertices and $alpha$ is the vector of eigenvalues, Eldan and Mikulincer show that detection is possible when $n^{3}gg(|alpha{|}_2/|alpha{|}_3{)}^6$ and impossible when $n^{3}ll(|alpha{|}_2/|alpha{|}_4{)}^4$. We show detection is impossible when $n^{3}ll(|alpha{|}_2/|alpha{|}_3{)}^6$, closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer.

Recommendations

• Information and dimensionality of anisotropic random geometric graphs
• Testing for high-dimensional geometry in random graphs
• Phase transition in noisy high-dimensional random geometric graphs
• High-dimensional random geometric graphs and their clique number
• Phase transitions for detecting latent geometry in random graphs

Cites work

• A CLT in Stein's distance for generalized Wishart matrices and higher-order tensors
• A smooth transition from Wishart to GOE
• Analysis of Boolean Functions
• Approximation of rectangular beta-Laguerre ensembles and large deviations
• Asymptotic behavior of large Gaussian correlated Wishart matrices
• Entropic CLT and phase transition in high-dimensional Wishart matrices
• High-dimensional random geometric graphs and their clique number
• scientific article; zbMATH DE number 5204610 (Why is no real title available?)
• Information and dimensionality of anisotropic random geometric graphs
• Multivariate normal approximation using exchangeable pairs
• Phase transitions for detecting latent geometry in random graphs
• Random Geometric Graphs
• Testing for high-dimensional geometry in random graphs
• Testing thresholds for high-dimensional sparse random geometric graphs
• The middle-scale asymptotics of Wishart matrices

Cited in

(2)

• Phase transition in noisy high-dimensional random geometric graphs
• Random algebraic graphs and their convergence to Erdős-Rényi

This page was built for publication: Threshold for detecting high dimensional geometry in anisotropic random geometric graphs

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