Testing for a Hidden Geometry in Random Graphs
For researchers in hypothesis testing and random graph theory, this work establishes fundamental limits and a computational gap for a natural geometric signal detection problem.
The paper characterizes the statistical and computational limits of detecting a hidden random geometric graph planted in an Erdős–Rényi random graph, identifying an easy–hard–impossible phase transition. It provides sharp information-theoretic lower bounds and algorithms that achieve these limits, and proves that low-degree polynomial algorithms fail in the hard regime.
We study the problem of detecting a faint geometric signal hidden in an otherwise random graph. Formally, we consider a hypothesis testing problem in which, under the null, the observed graph is an Erdős--Rényi random graph $\mathcal{G}(n,q)$, while under the alternative a random geometric graph $\mathcal{G}(k,q,d)$ is planted on $k\le n$ vertices. The planted subgraph is generated from independent random points on the unit sphere $\mathbb{S}^{d-1}$, with edges determined by latent geometric proximity and calibrated to have edge density $q$. Our goal is to characterize the statistical and computational limits of detecting this hidden geometry. We derive sharp information-theoretic lower bounds that identify regimes where detection is impossible and provide algorithms that achieve these limits whenever detection is feasible. We further investigate the computational complexity of the problem and determine when efficient polynomial-time tests exist. The model exhibits an \emph{easy--hard--impossible} phase transition: some regimes allow efficient detection, others permit detection only with computationally intractable procedures, and still others render detection impossible even with unlimited computational power. As evidence for the computational barrier, we prove that all low-degree polynomial algorithms fail throughout the conjecturally hard regime, demonstrating a sharp gap between statistical and computational feasibility.