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

Abstract

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 S^d-1, while all remaining edges follow the Erdős--Rényi model G(n, p). The random geometric graph is generated by thresholding inner products of latent vectors on S^d-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 = Θ(k^2 k^6/n^3) 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.

Reproductions