How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra Email: This work is supported in part by NSF CAREER Award CCF-1453261, a grant from the MIT NEC Corporation and a Google Faculty Research Award. Massachusetts Institute of Technology, Department of Mathematics Massachusetts Institute of Technology, Computer Science and Artificial Intelligence Lab William Perry Email: Massachusetts Institute of Technology, Department of Mathematics Alexander S. Wein Email: This work is supported in part by an NDSEG graduate fellowship. Massachusetts Institute of Technology, Department of Mathematics
Abstract
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by deep but non-rigorous ideas from statistical physics, Decelle et al. [decelle] conjectured a sharp threshold for when community detection is possible in the sparse regime. Mossel, Neeman and Sly [mns] and Massoulié [massoulie] proved the conjecture and gave matching algorithms and lower bounds.
中文速览
随机块模型（stochastic block model）是研究社区发现的经典模型，此前已有严格证明：当参数满足 $(a-b)^2 > 2(a+b)$ 时社区可被部分恢复，否则信息论上不可能——这一阈值被认为是该问题的"极限"。本文从半随机模型（semirandom model）的角度重新审视这一问题：允许一个"善意对手"对随机图做只强化社区内部连接、削弱社区间连接的单调修改，理论上这类改动应让社区更容易被找到，结果却出人意料——即便在原始随机模型中可以恢复的参数范围内，这样的单调修改也能从信息论层面彻底摧毁部分恢复的可能性，证明了半随机阈值与平均情形阈值之间存在本质差距。与此同时，作者证明基于半定规划（semidefinite programming，SDP）的算法在任意单调对手的干扰下仍能保持有效，而达到信息论阈值的算法则无法做到这一点。这一发现揭示了SDP算法在鲁棒性上的独特优势，也为统计学中超越平均情形分析、寻找更稳健的半随机阈值指出了新的研究方向。
原文 arXiv:1511.01473;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1511.01473v2