Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2603.24545v1</id>\n    <title>Detection of local geometry in random graphs: information-theoretic and computational limits</title>\n    <updated>2026-03-25T17:20:01Z</updated>\n    <link href='https://arxiv.org/abs/2603.24545v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2603.24545v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>We study the problem of detecting local geometry in random graphs. We introduce a model $\\mathcal{G}(n, p, d, k)$, where a hidden community of average size $k$ has edges drawn as a random geometric graph on $\\mathbb{S}^{d-1}$, while all remaining edges follow the Erdős--Rényi model $\\mathcal{G}(n, p)$. The random geometric graph is generated by thresholding inner products of latent vectors on $\\mathbb{S}^{d-1}$, with each edge having marginal probability equal to $p$. This implies that $\\mathcal{G}(n, p, d, k)$ and $\\mathcal{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.\n  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 = \\widetildeΘ(k^2 \\vee 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 $\\ell \\geq 4$.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='math.ST'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.CC'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.DS'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='math.PR'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='stat.ML'/>\n    <published>2026-03-25T17:20:01Z</published>\n    <arxiv:comment>68 pages</arxiv:comment>\n    <arxiv:primary_category term='math.ST'/>\n    <author>\n      <name>Jinho Bok</name>\n    </author>\n    <author>\n      <name>Shuangping Li</name>\n    </author>\n    <author>\n      <name>Sophie H. Yu</name>\n    </author>\n  </entry>"
}