# Detection of local geometry in random graphs: information-theoretic and computational limits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 113 references that are in the map.
- First posted on arXiv 25 Mar 2026.

## Builds on (most cited first, 5 of 5)

- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Exact Label Recovery in Euclidean Random Graphs](https://mlsanity.com/paper/2407.11163/) (2024)
- [Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture](https://mlsanity.com/paper/2602.14998/) (2026)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)

## Abstract (arXiv)

We study the problem of detecting local geometry in random graphs. We introduce a model G(n, p, d, k), where a hidden community of average size k has edges drawn as a random geometric graph on mathbbSd-1, while all remaining edges follow the ErdHos--R'enyi model G(n, p). The random geometric graph is generated by thresholding inner products of latent vectors on mathbbSd-1, with each edge having marginal probability equal to p. This implies that G(n, p, d, k) and G(n, p) are indistinguishable at the level of the marginals, and the signal lies entirely in the edge dependencies induced by the local geometry. We investigate both the information-theoretic and computational limits of detection. On the information-theoretic side, our upper bounds follow from three tests based on signed triangle counts: a global test, a scan test, and a constrained scan test; our lower bounds follow from two complementary methods: truncated second moment via Wishart--GOE comparison, and tensorization of KL divergence. These results together settle the detection threshold at d = widetildeTheta(k2 vee k6/n3) for fixed p, and extend the state-of-the-art bounds from the full model (i.e., k = n) for vanishing p. On the computational side, we identify a computational--statistical gap and provide evidence via the low-degree polynomial framework, as well as the suboptimality of signed cycle counts of length ℓ ≥ 4.