揭示稀疏社区模型相关性检测的计算边界，明确低阶多项式方法的有效阈值。
A computational transition for detecting correlated stochastic block models by low-degree polynomials
- 用低阶多项式测试判断两图是否相关，分析其可解性边界。
- 当采样概率 $s< \ ext{min} \{ \sqrtα, \frac{1}{λε^2} \}$ 时，检测与恢复均困难。
- 结果适用于社区结构稳定、稀疏图场景，适合理论学习者参考。
本文研究一对从共同父模型中子采样的相关稀疏随机块模型 $\mathcal{S}(n,\tfracλ{n};k,ε;s)$ 的相关性检测问题。该模型由平均度 $λ=O(1)$、对称社区数 $k=O(1)$、分歧参数 $ε$ 和子采样概率 $s$ 定义。目标是区分此模型与具有相同边密度 $\mathcal{G}(n,\tfrac{λs}{n})$ 的独立 Erdős-Rényi 图对。我们分析基于邻接矩阵元素的低阶多项式测试，证明此类测试仅在 $s> \min \{ \sqrtα, \frac{1}{λε^2} \}$ 时有效，其中 $α≈0.338$ 为 Otter 常数，$\frac{1}{λε^2}$ 为 Kesten-Stigum 阈值。结合 \\cite{Li25+} 的归约论证，该结果还表明：当 $s< \min \{ \sqrtα, \frac{1}{λε^2} \}$ 时，部分恢复与检测均存在低阶硬度。证明依赖于条件化的低阶似然计算。
原文摘要 · Abstract (English)
Detection of correlation in a pair of random graphs is a fundamental statistical and computational problem that has been extensively studied in recent years. In this work, we consider a pair of correlated (sparse) stochastic block models $\mathcal{S}(n,\tfracλ{n};k,ε;s)$ that are subsampled from a common parent stochastic block model $\mathcal S(n,\tfracλ{n};k,ε)$ with $k=O(1)$ symmetric communities, average degree $λ=O(1)$, divergence parameter $ε$, and subsampling probability $s$. For the detection problem of distinguishing this model from a pair of independent Erdős-Rényi graphs with the same edge density $\mathcal{G}(n,\tfrac{λs}{n})$, we focus on tests based on \emph{low-degree polynomials} of the entries of the adjacency matrices, and we determine the threshold that separates the easy and hard regimes. More precisely, we show that this class of tests can distinguish these two models if and only if $s> \min \{ \sqrtα, \frac{1}{λε^2} \}$, where $α\approx 0.338$ is the Otter's constant and $\frac{1}{λε^2}$ is the Kesten-Stigum threshold. Combining a reduction argument in \cite{Li25+}, our hardness result also implies low-degree hardness for partial recovery and detection (to independent block models) when $s< \min \{ \sqrtα, \frac{1}{λε^2} \}$. Finally, our proof of low-degree hardness is based on a conditional variant of the low-degree likelihood calculation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。