TY - JOUR

T1 - Proof of the Achievability Conjectures for the General Stochastic Block Model

AU - Abbe, Emmanuel

AU - Sandon, Colin

N1 - Funding Information:
In order to obtain an efficient estimator, one can count nonbacktracking walks instead of cycles. For m D o.logd1=4.n//, the neighborhood at depth m of a vertex in SBM.n; k; a; b/ contains at most one cycle with high probability. Thus the numberP of cycles of length m in SBM.n; k; a; b/ is with high probability equal to v2ŒńCv where Cv is the number of nonbacktracking walks of length m starting and ending at v. This is efficiently computable as shown in [61]. □ Acknowledgment. This research was partly supported by National Science Foundation CAREER Award CCF-1552131, ARO Grant W911NF-16-1-0051, and the Google Faculty Research Award.

PY - 2018/7

Y1 - 2018/7

N2 - In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborová, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten-Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulié, Mossel et al., and Bordenave, Lelarge, and Massoulié proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi-linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message-passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information-computation gaps.

AB - In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborová, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten-Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulié, Mossel et al., and Bordenave, Lelarge, and Massoulié proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi-linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message-passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information-computation gaps.

UR - http://www.scopus.com/inward/record.url?scp=85031743551&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031743551&partnerID=8YFLogxK

U2 - 10.1002/cpa.21719

DO - 10.1002/cpa.21719

M3 - Article

AN - SCOPUS:85031743551

VL - 71

SP - 1334

EP - 1406

JO - Communications on Pure and Applied Mathematics

JF - Communications on Pure and Applied Mathematics

SN - 0010-3640

IS - 7

ER -