Testing thresholds for high-dimensional sparse random geometric graphs

DOI10.1145/3519935.3519989MaRDI QIDQ6083521zbMATH OpenFDO

Authors Si-Qi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

belief propagationcavity methodoptimal transportrandom geometric graphsrandom graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In the random geometric graph model $mathsf{Geo}_d(n,p)$, we identify each of our $n$ vertices with an independently and uniformly sampled vector from the $d$-dimensional unit sphere, and we connect pairs of vertices whose vectors are ``sufficiently close, such that the marginal probability of an edge is $p$. We investigate the problem of testing for this latent geometry, or in other words, distinguishing an ErdH{o}s-R'enyi graph $mathsfG(n,p)$ from a random geometric graph $mathsf{Geo}_d(n,p)$. It is not too difficult to show that if $doinfty$ while $n$ is held fixed, the two distributions become indistinguishable; we wish to understand how fast $d$ must grow as a function of $n$ for indistinguishability to occur. When $p=fracalphan$ for constant $alpha$, we prove that if $dgemathrmpolylogn$, the total variation distance between the two distributions is close to $0$; this improves upon the best previous bound of Brennan, Bresler, and Nagaraj (2020), which required $dgg{n}^{3/2}$, and further our result is nearly tight, resolving a conjecture of Bubeck, Ding, Eldan, & R'{a}cz (2016) up to logarithmic factors. We also obtain improved upper bounds on the statistical indistinguishability thresholds in $d$ for the full range of $p$ satisfying $frac1nleplefrac12$, improving upon the previous bounds by polynomial factors. Our analysis uses the Belief Propagation algorithm to characterize the distributions of (subsets of) the random vectors {em conditioned on producing a particular graph}. In this sense, our analysis is connected to the ``cavity method from statistical physics. To analyze this process, we rely on novel sharp estimates for the area of the intersection of a random sphere cap with an arbitrary subset of the sphere, which we prove using optimal transport maps and entropy-transport inequalities on the unit sphere.

Cited in

(7)

• Testing multivariate uniformity based on random geometric graphs
• The bin-covering technique for thresholding random geometric graph properties
• Phase transition in noisy high-dimensional random geometric graphs
• Threshold for detecting high dimensional geometry in anisotropic random geometric graphs
• Random algebraic graphs and their convergence to Erdős-Rényi
• Phase synchronization in random geometric graphs on the two-dimensional sphere
• Distribution-free connectivity testing for sparse graphs

This page was built for publication: Testing thresholds for high-dimensional sparse random geometric graphs

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