Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation
The stochastic block model (SBM) has long been studied in machine learning and network science as a canonical model for clustering and community detection. In the recent years, new developments have demonstrated the presence of threshold phenomena for this model, which have set new challenges for algorithms. For the detection problem in symmetric SBMs, Decelle et al. conjectured that the so-called Kesten-Stigum (KS) threshold can be achieved efficiently. This was proved for two communities, but remained open for three and more communities. We prove this conjecture here, obtaining a general result that applies to arbitrary SBMs with linear size communities. The developed algorithm is a linearized acyclic belief propagation (ABP) algorithm, which mitigates the effects of cycles while provably achieving the KS threshold in O(n ln n) time. This extends prior methods by achieving universally the KS threshold while reducing or preserving the computational complexity. ABP is also connected to a power iteration method on a generalized nonbacktracking operator, formalizing the spectral-message passing interplay described in Krzakala et al., and extending results from Bordenave et al.
This work is about the community detection threshold in stochastic block models (SBM). It deals with arbitrary SBM with $k$ communities (i.e. the communities need not to have equal proportion, the interactions between groups is not restricted to within-groups and inter-groups values and $k$ may be larger than 2).    The paper establishes that a linearized acyclic belief propagation algorithm achieves the Kesten-Stigum (KS) threshold for group detection. Here, detection is defined in a weaker sense than the previous definition from Decelle et al. In the specific case of $k=2$ and equal group proportions it boils down to Decelle et al.'s definition but is weaker in general. 
Major comments:  - As mentioned by the authors in the introduction, the SBM is widely used throughout many areas, and not only for detecting communities. The authors introduce no condition on the parameter matrix Q so that their setup includes (in principle) cases as diverse as communities, anti-communities (graphs of a bipartite type) and any other type of connectivity structure. However, I believe that their algorithm (based on belief propagation and thus on the community structure) will reveal only communities. If I am right, they should specify where this underlying assumption comes into play. Is it only that definition 3 becomes useless when the structure is not the one of communities?  - Most of the arguments given here are not understandable to someone not familiar to the field. For e.g. on line 186-187: ‘For any small t, we would expect that \bar w. W^t \bar w is almost equal to \lambda_i^t \|\bar w \|_2^2’. Why is this the case? Maybe you could refer to some textbooks to ease the understanding.    Minor comments:  - The bibliography needs to be corrected. I believe Ref [12] appeared in Probab. Theory Relat. Fields (2015, vol 162:431–461) with a slightly different title. Authors ordering is wrong for ref [5]. Ref [15] also appeared in PTRF in 2015. Ref [16] appeared in STOC'16. Ref [19] has appeared in FOCS 2015, etc.  - please avoid usage of undefined acronyms (e.g. SDP, SAW,…) - End of section 2.1 uses notation introduced at the beginning of section 2.2 (matrix P and eigenvalue \lambda_1). It would be more convenient to move this paragraph.  - Theorem 1: notation ABP(G,m(n),r,c,\lambda_1,\dots,\lambda_h)) only appears in the next section.   - Remark 1: ‘one should use variable that are accurate to within a factor of…’: to which variable are you referring here? Also the term ln(\lambda_1^2/\lambda_2^2) could be simplified into 2ln(\lambda_1/\lambda_2)  - Algorithm description: as the graph G is not directed, the algorithm description should be cautious when referring to edge (v,v’) \in E(G) as here these are directed edges. This remark is valid for the vanilla version as well as the full version (and also the supplementary material).  - line 296: ‘whenever there is no repeated vertex within r of a nonzero c_i’. What do you mean?    Typos: - line 81-82: ’SBM model’ is redundant.  - line 286: do you mean a ‘r-nonbacktracking walk’?  - line 288: the sum is over v_0, \dots v_t but v_t has no meaning here. Should be v_m?  - line 304: second factor on the right-hand side: is this \lambda_s or \lambda_j? Same applies on line 306.   In Supplementary material:  - Before Theorem 1: ’SBP algorithm’ should be ABP.  - Corollary 1: Notation ‘SBM(n,k,a,b)’ -while easily understandable- has never been defined.