Testing for a Hidden Geometry in Random Graphs

In this work, we investigate the fundamental problem of detecting a faint geometric signal hidden within an otherwise random graph. We formulate this task as a hypothesis testing problem: under the null hypothesis, the observed graph is an Erdős–Rényi random graph $\mathcal{G}(n,q)$ with edge density $q\in(0,1)$; under the alternative, a high-dimensional geometric structure is clandestinely embedded. Specifically, a random geometric graph $\mathcal{G}(k,q,d)$ on $k\le n$ vertices is planted inside $\mathcal{G}(n,q)$, where each of the $k$ vertices corresponds to an independent random point drawn uniformly from the unit sphere $\mathbb{S}^{d-1}$, and edges are formed according to latent proximity, resulting in the same edge probability $q$. Our objective is to characterize the limits of detectability of this hidden geometry, from both statistical and computational perspectives. We derive sharp information-theoretic lower bounds that characterize the regimes in which detection is fundamentally impossible, expressed explicitly in terms of the problem parameters. Complementing these impossibility results, we propose and analyze several algorithms that provably attain these limits whenever detection is feasible. We also explore the algorithmic landscape of the problem and investigate which regimes admit efficient, polynomial-time testing procedures. As in many other structured high-dimensional inference problems, our model exhibits a pronounced \emph{easy–hard–impossible} phase transition: there exist regimes in which detection is statistically possible yet computationally prohibitive, as well as regimes in which detection is impossible even with unbounded computational resources. As concrete evidence of this computational barrier, we show that the entire class of low-degree polynomial algorithms fails in the conjecturally hard regime, highlighting a sharp separation between statistical possibility and algorithmic feasibility.