Phase transition in noisy high-dimensional random geometric graphs

DOI10.1214/23-EJS2162MaRDI QIDQ6184923zbMATH OpenOpenAlexFDO

Authors Suqi Liu, Miklós Z. Rácz

Publication date 5 January 2024

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.15249, https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-17/issue-2/Phase-transition-in-noisy-high-dimensional-random-geometric-graphs/10.1214/23-EJS2162.full

zbMATH Keywords

high-dimensional geometric structurehypothesis testingrandom geometric graphrandom graphsigned triangle

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study the problem of detecting latent geometric structure in random graphs. To this end, we consider the soft high-dimensional random geometric graph $mathcalG(n,p,d,q)$, where each of the $n$ vertices corresponds to an independent random point distributed uniformly on the sphere $mathbb{S}^{d-1}$, and the probability that two vertices are connected by an edge is a decreasing function of the Euclidean distance between the points. The probability of connection is parametrized by $qin[0,1]$, with smaller $q$ corresponding to weaker dependence on the geometry; this can also be interpreted as the level of noise in the geometric graph. In particular, the model smoothly interpolates between the spherical hard random geometric graph $mathcalG(n,p,d)$ (corresponding to $q=1$) and the ErdH{o}s-R'enyi model $mathcalG(n,p)$ (corresponding to $q=0$). We focus on the dense regime (i.e., $p$ is a constant). We show that if $nqo0$ or $dgg{n}^3{q}^2$, then geometry is lost: $mathcalG(n,p,d,q)$ is asymptotically indistinguishable from $mathcalG(n,p)$. On the other hand, if $dll{n}^3{q}^6$, then the signed triangle statistic provides an asymptotically powerful test for detecting geometry. These results generalize those of Bubeck, Ding, Eldan, and R'acz (2016) for $mathcalG(n,p,d)$, and give quantitative bounds on how the noise level affects the dimension threshold for losing geometry. We also prove analogous results under a related but different distributional assumption, and we further explore generalizations of signed triangles in order to understand the intermediate regime left open by our results.

Recommendations

• A probabilistic view of latent space graphs and phase transitions
• Testing for high-dimensional geometry in random graphs
• Phase transitions for detecting latent geometry in random graphs
• Information and dimensionality of anisotropic random geometric graphs
• Threshold for detecting high dimensional geometry in anisotropic random geometric graphs

Cites work

• A CLT in Stein's distance for generalized Wishart matrices and higher-order tensors
• A note on a method for generating points uniformly on n -dimensional spheres
• A probabilistic view of latent space graphs and phase transitions
• A Quest to Unravel the Metric Structure Behind Perturbed Networks
• A smooth transition from Wishart to GOE
• Approximation of rectangular beta-Laguerre ensembles and large deviations
• Basic models and questions in statistical network analysis
• Choosing a Point from the Surface of a Sphere
• Cliques in random graphs
• Community detection and percolation of information in a geometric setting
• Connectivity of soft random geometric graphs
• Entropic CLT and phase transition in high-dimensional Wishart matrices
• High-dimensional random geometric graphs and their clique number
• High-dimensional statistics. A non-asymptotic viewpoint
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• Information and dimensionality of anisotropic random geometric graphs
• Latent Space Approaches to Social Network Analysis
• Law of log determinant of sample covariance matrix and optimal estimation of differential entropy for high-dimensional Gaussian distributions
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Modeling graphs using dot product representations
• On some inequalities for the gamma and psi functions
• Pattern recognition and machine learning.
• Phase transitions for detecting latent geometry in random graphs
• Random Geometric Graphs
• Some Continuous Monte Carlo Methods for the Dirichlet Problem
• Statistical inference on random dot product graphs: a survey
• Testing for high-dimensional geometry in random graphs
• Testing thresholds for high-dimensional sparse random geometric graphs
• The capacity of wireless networks
• The Distribution of Distance in a Hypersphere
• The distribution of the number of isolated nodes in the 1-dimensional soft random geometric graph
• The geometry of continuous latent space models for network data
• The middle-scale asymptotics of Wishart matrices

Cited in

(3)

• Threshold for detecting high dimensional geometry in anisotropic random geometric graphs
• Random algebraic graphs and their convergence to Erdős-Rényi
• Goodness-of-fit via count statistics in dense random simplicial complexes

This page was built for publication: Phase transition in noisy high-dimensional random geometric graphs

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