# Phase Transitions for Detecting Latent Geometry in Random Graphs

arXiv: https://arxiv.org/abs/1910.14167 · HTML: https://mlsanity.com/paper/1910.14167/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2019.

## Built on by (most cited first, 9 of 9)

- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Near Optimal Heteroscedastic Regression with Symbiotic Learning](https://mlsanity.com/paper/2306.14288/) (2023)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Impossibility of latent inner product recovery via rate distortion](https://mlsanity.com/paper/2407.11932/) (2024)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [Recovery of latent inner products from an anisotropic Gaussian random geometric graph](https://mlsanity.com/paper/2607.23723/) (2026)

## Abstract (arXiv)

Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These graphs are also of purely theoretical interest within computer science, probability and statistics. A fundamental initial question regarding these models is: when are these random graphs affected by their latent geometry and when are they indistinguishable from simpler models without latent structure, such as the ErdHos-R'enyi graph G(n, p)? We address this question for two of the most well-studied models of random graphs with latent geometry -- the random intersection and random geometric graph. Our results are as follows: (1) we prove that the random intersection graph converges in total variation to G(n, p) when d = tildeω(n3), and does not if d = o(n3), resolving an open problem in Fill et al. (2000), Rybarczyk (2011) and Kim et al. (2018); (2) we provide conditions under which the matrix of intersection sizes of random family of sets converges in total variation to a symmetric matrix with independent Poisson entries, yielding the first total variation convergence result for τ-random intersection graphs to G(n, p); and (3) we show that the random geometric graph on mathbbSd - 1 with edge density p converges in total variation to G(n, p) when d = tildeωleft(min pn3, p2 n7/2  right), yielding the first progress towards a conjecture of Bubeck et al. (2016). The first of these three results was obtained simultaneously and independently by Bubeck, Racz and Richey.