Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap
Emmanuel Abbe Program in Applied and Computational Mathematics, and EE Department, Princeton University, USA, This research was partly supported by the NSF CAREER Award CCF-1552131, the ARO grant W911NF-16-1-0051, and the Google Faculty Research Award. Colin Sandon Department of Mathematics, Princeton University, USA,
Abstract
In a paper that initiated the modern study of the stochastic block model, Decelle et al., backed by Mossel et al., made the following conjecture: Denote by $k$ the number of balanced communities, $a/n$ the probability of connecting inside communities and $b/n$ across, and set $\mathrm{SNR}=(a-b)^{2}/(k(a+(k-1)b)$ ; for any $k\geq 2$ , it is possible to detect communities efficiently whenever $\mathrm{SNR}>1$ (the KS threshold), whereas for $k\geq 4$ , it is possible to detect communities information-theoretically for some $\mathrm{SNR}<1$ . Massoulié, Mossel et al. and Bordenave et al. succeeded in proving that the KS threshold is efficiently achievable for $k=2$ , while Mossel et al. proved that it cannot be crossed information-theoretically for $k=2$ . The above conjecture remained open for $k\geq 3$ .
中文速览
随机块模型（stochastic block model，SBM）的社区检测领域存在一个悬而未决十余年的核心猜想：对任意社区数 $k$，只要信噪比 SNR 超过 Kesten-Stigum（KS）阈值，就能用高效算法检测到社区；而当 $k\geq4$ 时，即便 SNR 低于 KS 阈值，也存在（非高效的）信息论算法能完成检测，意味着计算复杂度与信息论之间存在真实的鸿沟。本文通过两条路线彻底证明了这一猜想：在高效检测方面，提出了"线性化无环置信传播"（linearized acyclic belief propagation，ABP）算法，其关键创新是通过抑制短环带来的反馈来克服图中环路对消息传递的干扰，并在理论上证明该算法以 $O(n\log n)$ 的时间复杂度恰好在 KS 阈值处实现社区检测，同时将算法与一种高阶非回溯算子（nonbacktracking operator）上的幂迭代方法建立等价联系，统一了消息传递与谱方法两大框架；在信息论方面，构造了一种对"典型聚类"采样的非高效算法，证明其在 $k=4$ 时能突破 KS 阈值，并揭示当 $a=0$ 时信息论可行域远宽于 KS 阈值（后者要求 $b\gtrsim k^2$，而前者仅需 $b\gtrsim k\ln k$），从而使 SBM 成为研究信息-计算鸿沟现象的绝佳范例。
原文 arXiv:1512.09080;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1512.09080v4