# Testing for high-dimensional geometry in random graphs

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2014.

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

- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Non-asymptotic approximations of neural networks by Gaussian processes](https://mlsanity.com/paper/2102.08668/) (2021)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Harnessing Multiple Correlated Networks for Exact Community Recovery](https://mlsanity.com/paper/2412.02796/) (2024)
- [Is Dimensionality a Barrier for Retrieval Models?](https://mlsanity.com/paper/2605.23556/) (2026)
- [Community Recovery in the Geometric Block Model](https://mlsanity.com/paper/2206.11303/) (2022)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Reconstruction of Random Geometric Graphs: Breaking the Omega(r) distortion barrier](https://mlsanity.com/paper/2107.14323/) (2021)
- [Impossibility of latent inner product recovery via rate distortion](https://mlsanity.com/paper/2407.11932/) (2024)
- [Counting Cycles with AI: Counting Cycles with AI: Computationally Efficient Equivalent Forms with Applications](https://mlsanity.com/paper/2505.17964/) (2025)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [A note on estimating the dimension from a random geometric graph](https://mlsanity.com/paper/2311.13059/) (2023)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)
- [Grokability in five inequalities](https://mlsanity.com/paper/2605.05193/) (2026)
- [Recovery of latent inner products from an anisotropic Gaussian random geometric graph](https://mlsanity.com/paper/2607.23723/) (2026)
- [Spectral graph clustering with inhomogeneous latent geometry](https://mlsanity.com/paper/2608.11321/) (2026)

## Abstract (arXiv)

We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an ErdHos-R'enyi random graph G(n,p). Under the alternative, the graph is generated from the G(n,p,d) model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere mathbbSd-1, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in G(n,p,d).