Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap

In a paper that initiated the modern study of the stochastic block model,\nDecelle et al., backed by Mossel et al., made the following conjecture: Denote\nby $k$ the number of balanced communities, $a/n$ the probability of connecting\ninside communities and $b/n$ across, and set\n$\\mathrm{SNR}=(a-b)^2/(k(a+(k-1)b)$; for any $k \\geq 2$, it is possible to\ndetect communities efficiently whenever $\\mathrm{SNR}>1$ (the KS threshold),\nwhereas for $k\\geq 4$, it is possible to detect communities\ninformation-theoretically for some $\\mathrm{SNR}<1$. Massouli\\'e, Mossel et\nal.\\ and Bordenave et al.\\ succeeded in proving that the KS threshold is\nefficiently achievable for $k=2$, while Mossel et al.\\ proved that it cannot be\ncrossed information-theoretically for $k=2$. The above conjecture remained open\nfor $k \\geq 3$.\n This paper proves this conjecture, further extending the efficient detection\nto non-symmetrical SBMs with a generalized notion of detection and KS\nthreshold. For the efficient part, a linearized acyclic belief propagation\n(ABP) algorithm is developed and proved to detect communities for any $k$ down\nto the KS threshold in time $O(n \\log n)$. Achieving this requires showing\noptimality of ABP in the presence of cycles, a challenge for message passing\nalgorithms. The paper further connects ABP to a power iteration method with a\nnonbacktracking operator of generalized order, formalizing the interplay\nbetween message passing and spectral methods. For the information-theoretic\n(IT) part, a non-efficient algorithm sampling a typical clustering is shown to\nbreak down the KS threshold at $k=4$. The emerging gap is shown to be large in\nsome cases; if $a=0$, the KS threshold reads $b \\gtrsim k^2$ whereas the IT\nbound reads $b \\gtrsim k \\ln(k)$, making the SBM a good study-case for\ninformation-computation gaps.\n