Proof of the Achievability Conjectures for the General Stochastic Block Model

Emmanuel Abbe, Colin Sandon

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1334-1406
Number of pages73
JournalCommunications on Pure and Applied Mathematics
Volume71
Issue number7
DOIs
StatePublished - Jul 2018

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Proof of the Achievability Conjectures for the General Stochastic Block Model'. Together they form a unique fingerprint.

Cite this