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

Introduction

The stochastic block model (SBM) is a canonical model of networks with communities, and a natural model to study various central questions in machine learning, algorithms and statistics. The model serves in particular as a test bed for clustering and community detection algorithms, commonly used in social networks [NWS], protein-to-protein interactions networks [CY06], gene expressions [CSC+07], recommendation systems [LSY03], medical prognosis [SPT+01], DNA folding [CAT15], image segmentation [SM97], natural language processing [BKN11] and more.

The SBM emerged independently in multiple scientific communities. The block model terminology, which seems to have dominated in the recent years, comes from the machine learning and statistics literature [HLL83, WBB76, FMW85, WW87, BC09, KN11, SN97, RCY11, CWA12], while the model is typically called the planted partition model in theoretical computer science [BCLS87, DF89, Bop87, JS98, CK99, CI01, McS01], and the inhomogeneous random graphs model in the mathematical literature [BJR07]. Although the model was defined as far back as the 80s, it resurged in recent years due in part to the following fascinating conjecture established first in [DKMZ11], and backed in [MNS15], from deep but non-rigorous statistical physics arguments:

We prove this conjecture in this paper. The problem was settled already for the case of $k=2$: It was proved in [Mas14, MNS14b] that the KS threshold can be achieved efficiently for $k=2$, with an alternative proof later given in [BLM15], and [MNS15] shows that no information-computation gap takes places for $k=2$ with a tight converse. It was also shown in [BLM15] that for SBMs with multiple communities satisfying a certain asymmetry condition (i.e., the requirement that $\mu_{k}$ is a simple eigenvalue in Theorem 5 of [BLM15]), the KS threshold can be achieved. Yet, [BLM15] does not resolve Conjecture 1 for $k\geq 3$.

An interesting challenge raised by part (i) of the conjecture is that standard clustering methods, commonly used in applications, fail to achieve the KS threshold. This includes spectral methods based on the adjacency matrix or standard Laplacians, as well as SDPs. For standard spectral methods, a first issue is that the fluctuations in the node degrees produce high-degree nodes that disrupt the eigenvectors from concentrating on the clusters.This issue is further enhanced on real networks where degree variations are large. A classical trick is to trim such high-degree nodes [CO10, Vu14, GV16, CRV15], throwing away some information, but this does not suffice to achieve the KS threshold. SDPs are a natural alternative, but they also stumbleThe recent results of [MPW15] on robustness to monotone adversaries suggest that SDPs can in fact not achieve the KS threshold. before the KS threshold [GV16, MS16], focusing on the most likely rather than typical clusterings. As we shall show in this paper, and as already investigated in [KMM+13, BLM15] for two communities, a linearized BP algorithm, or equivalently a spectral algorithm on a nonbacktracking operator, provides instead a solution to the conjecture.

The nonbacktracking matrix $B$ of a graph was introduced by Hashimoto [Has89] to study the Ihara zeta function, with the identity $\det(I-zB)=\frac{1}{\zeta(z)}$, where $\zeta$ is the Ihara zeta function of the graph. In particular, the poles of the Ihara zeta function are the reciprocal of the eigenvalues of $B$. Studying the spectrum of a graph thus implies properties on the location of the Ihara zeta function. The matrix is further used to define the graph Riemann hypothesis [HST06], and studying its spectrum for random graphs such as the block model allows for generalizations of notions of Ramanujan graphs and Friedman’s Theorem to non-regular cases, as discussed in [BLM15]. The operator that we study is a natural extension of the classical nonbacktracking operator of Hashimoto, where we prohibit not only standard backtracks but also finite cycles.

In their original paper [DKMZ11], Decelle et al. conjecture that belief propagation (BP) achieves the KS threshold, and in fact, gives the the optimal accuracy in the reconstruction of the communities. However, the main issue when applying BP to the SBM is the classical one: the presence of cycles in the graph makes the behavior of the algorithm much more difficult to understand, and BP is susceptible to settling down in the wrong fixed points.Empirical studies of BP on loopy graph show that convergence still takes place in some cases [MWJ99]. This is a long standing challenge in the realm of message passing algorithms for graphical models. Moreover, achieving the KS threshold requires precisely running BP to an extent where the graph is not even tree-like, thus precluding simple tricks. Numerical simulations suggest that starting with a purely random initialization, i.e., letting each vertex in the graph guess its community membership at random, and running BP works. However, no method is currently known to control random initialization, as discussed in [MNS14b]. We develop here an alternate approach, using a linearized version of belief propagation.

Further, the paper proves part (ii) of the conjecture, crossing the KS threshold at $k=4$ using a non-efficient algorithm that samples a typical clustering (i.e., a clustering having the right proportions of edges inside and across clusters). Note that the information-computation gap concerns the gap between the KS and information-theoretic thresholds, which is the gap between the computational and information-theoretic thresholds only under non-formal evidences [DKMZ11]. However, the IT bound that results from our analysis gives a gap to the KS threshold which is large in some cases (quasi-linear in $k$), making the SBM a good study-case for such gap phenomena.

A linearized acyclic belief propagation (ABP) algorithm is developed and shown to detect communities down to the KS threshold with complexity $O(n\log n)$, proving part (i) of Conjecture 1. A more general result applying to arbitrary (possibly asymmetrical) SBMs with a generalized notion of detection and KS threshold is also developed. The complexity of ABP is either comparable or improved compared to prior algorithms for $k=2$ [Mas14, MNS14b, BLM15], while ABP achieves universally the KS threshold (see Theorem 1);

An algorithm that samples a clustering with typical volumes and cuts is shown to detect communities below the KS threshold at $k=4$, proving part (ii) of Conjecture 1;

A connection between ABP and a power iteration method on a non-backtracking operator is developed, extending the operator of [Has89] to higher order non backtracks, and formalizing the interplay described in [KMM+13] between linearized BP and nonbacktracking operators;

An information-theoretic (IT) bound is derived for the symmetric SBM. For $a=0$, it is shown that detection is information-theoretically solvable if $b>ck\ln k+o_{k}(1)$, $c\in$. Thus the information-computation gap — defined as the gap between the KS threshold and the IT bound — can be large since the KS threshold reads $b>k(k-1)$. Our bound interpolates the optimal threshold at $a=0$, and is conjectured to be tight in the scaling of $b$ for small $b$ and any $k$, and in the scaling of $k$ for large $k$.

An efficient algorithm is shown to learn the parameters $a,b,k$ in the symmetric SBM down to the KS threshold.

To achieve the KS threshold, we rely on a linearized version of BP that can handle cycles. The simplest linearizedDifferent forms of approximate message passing algorithms have been studied, such as in [DMM09] for compressed sensing. version of BP is to simply repeatedly update beliefs about a vertex’s community based on its neighbor’s suspected communities while ignoring the part of that belief that results from the beliefs about that vertex’s community to prevent a feedback loop. However, this only works ideally if the graph is a tree. The correct response to a cycle would be to discount information reaching the vertex along either branch of the cycle to compensate for the redundancy of the two branches. However, due to computational issues we simply prevent information from cycling around small cycles in order to limit feedback. We also add steps where a multiple of the beliefs in the previous step are subtracted from the beliefs in the current step to prevent the beliefs from settling into an equilibrium where vertices’ communities are sytematically misrepresented in ways that add credibility to each other. We refer to Section 2.1.1 for a complete description of the algorithm and Section 3 for further intuition on how it performs.

The fact that ABP is equivalent to a power iteration method on a non-backtracking operator results from its linearized form, as pointed out first in [KMM+13]. This provides an intriguing synergy between message passing and spectral algorithms. It further allows us to interpret the obstructions of spectral methods through the lens of BP. The risk of obtaining eigenvectors that concentrate on singular structures (e.g., high degree nodes for Laplacian’s), is related to the risk that BP settles down in wrong fixed points (e.g., due to cycling around high-degree nodes). Rather than removing such obstructions, ABP mitigates the feedback coming from the loops, giving rise to a non-backtracking operator, which extends the operator of [Has89] by considering higher order nonbacktracks. In addition to simplifying the proofs, considering higher order nonbacktracking operators can help mitigating short loops in more general models, which is of independent interest. Further details are provided in Section 3.

Note that solving the detection problem has direct implications on obtaining algorithms having optimal agreement (i.e., least fraction of mislabelled vertices) for the SBM. Once one has reasonable initial guesses of which communities the vertices are in, one can simply use full belief propagation to improve this to a better agreement. In order to do that from that output of ABP, one needs to first convert the division of vertices into two sets that are correlated with their communities to an assignment of each vertex to a nontrivial probability distribution for how likely it is to be in each community. Then, for each adjacent $v$ and $v^{\prime}$, one can determine the probability distribution of what community $v$ is in based of the signs of $y^{\prime}_{(v^{\prime\prime},v)}$ for all $v^{\prime\prime}\neq v^{\prime}$. Finally, use these as the starting probabilities for a belief propagation algorithm of depth $\ln(n)/3\ln(\lambda_{1})$. See Section 5 for further details on how this can be done. The main algorithmic challenge for obtaining optimal agreement in the SBM seems then captured by the detection problem.

To cross the KS threshold information theoretically, we rely on a non-efficient algorithm that samples a typical clustering. Upon observing a graph drawn from the SBM, the algorithm builds the set of all partitions of the $n$ nodes that have a typical fraction of edges inside and across clusters, and then samples a partition uniformly at random from that set. The analysis of the algorithm reveals three different regimes, that reflect three layers of refinement in the bounds on the typical set’s size. In a first regime, no bad clustering (i.e., partition of the nodes that classifies close to $1/k$ of the vertices correctly) is typical with high probability based on a union-bound, and the algorithm samples only good clusterings with high probability. This allows us to cross the KS threshold for $k=5$ when $a=0$ but does not give the right bound at $b=0$. In a second regime, the large number of tree-like components in the graph is exploited, finding some bad clusterings to be typical but unlikely to be sampled. This gives a regime where the algorithm succeeds with the right bound at $b=0$, but not the right approximation at small $b$. To address the latter, a finer estimate on the typical set’s size is obtained by also exploiting parts of the giant that are tree-like. Finally, we tighten our estimates on the typical set’s size by taking into account vertices that are not saturated, i.e., whose neighbors do not cover all communities. The final bound crosses the KS threshold at $k=4$, interpolates the optimal threshold at $a=0$, and is conjectured to be tight in the scaling of $b$ for small $b$ and in the scaling of $k$ for large $k$ and small $a$. Further details are in Section 4.

The learning of the parameters $a,b,k$ is done similarly as for the case $k=2$ [MNS15]. Note that learning the parameters when $k$ is unknown was previously settled only for diverging degrees [AS15b], with related results in [BCS15].

2 Related literature

Several methods were proved to succeed down to the KS threshold for two communities. The first is basedRelated ideas relying on shortest paths were also considered in [BB14]. on a spectral method from the matrix of self-avoiding walks (entry $(i,j)$ counts the number of self-avoiding walks of moderate size between vertices $i$ and $j$) [Mas14], the second on counting weighted non-backtracking walks between vertices [MNS14b], and the third on a spectral method with the matrix of non-backtracking walks between directed edges (each edge is replaced with two directed edges and entry $(e,f)$ is one if and only if edge $e$ follows edge $f$) [BLM15]. The first method has a complexity of $O(n^{1+\varepsilon})$, $\varepsilon>0$, while the second method affords a lesser complexity of $O(n\log^{2}n)$ but with a large constant (see discussion in [MNS14b]). These two methods were the first to achieve the KS threshold for two communities. The third method is based on a thorough analysis of the spectrum of the non-backtracking operator and allows going beyond the SBM with 2 communities, requiring however a certain asymmetry in the SBM parameters to obtain a result for detection (the precise condition is the requirement on $\mu_{k}$ being a simple eigenvalue of $M$ in Theorem 5 of [BLM15]), thus falling short of proving Conjecture 1.(i) for $k\geq 3$ (since the second eigenvalue in this case has multiplicity at least 2). Note that a certain amount of symmetry is needed to make the detection problem interesting. For example, if the communities have different average degrees, detection becomes trivial. Thus the symmetric model SBM$(n,k,a,b)$ is in a sense the most challenging model for detection.

The non-backtracking operator was proposed first for the SBM in [KMM+13], also described as a linearization of BP. A precise spectral analysis of this operator is developed in [BLM15] and applied to the SBM. This approach gives a fascinating approach to community detection, giving the first rigorous understanding on why nonbacktracking operators achieve the KS threshold. Besides the previously mentioned shortcomings for Conjecture 1 in the symmetric case, the operator suffers from an increase in dimension, as the derived matrix scales with the number of edges rather than vertices (specifically $2|E|\times 2|E|$, where $|E|$ is the number of edges).The non-backtracking matrix is also not normal and has thus a complex spectrum; an interesting heuristic based on the Bethe Hessian operator was proposed in [SKZ14] to address the dimensionality and normality issues. Nonbactracking spectral methods were also developed recently for the problem of detecting a single planted community .

Our results are closest to [MNS14b, BLM15], while diverging in several key parts. A few technical expansions in the paper are similar to those carried in [MNS14b], such as the weighted sums over nonbacktracking walks and the SAW decomposition from [MNS14b], which are similar to our compensated nonbacktracking walk counts and standard decomposition. Our modifications are however developed to cope with general SBMs rather than the 2-symmetric case, in particular to compensate for the dominant eigenvalues in the latter setting, which is delicate due to the numerous potentially close eigenvalues. Our algorithm complexity is also slightly reduced by a logarithmic factor.

Our algorithm is also closely related to [BLM15], which focuses on extracting the eigenvectors of the standard nonbacktracking operator. However, our proof technique is different than the one in [BLM15], so that we can cope with the setting of Conjecture 1. Also, we do not proceed with the eigenvectors extraction, but implement the algorithm in a belief propagation fashion. This avoids building the nonbacktracking matrix whose dimension grows with the number of edges. Note that from a spectral point of view, the power iteration method that we use is not relying on a traditional deflation method that subtracts the dominant eigenvector. Such an approach is likely to work in the symmetric SBM, but in the general SBM, we rely on a different approach that subtracts large eigenvalues times the identity matrix. Another difference from [BLM15] is that we rely on nonbacktracking operators of higher orders $r$. While $r=2$ is arguably the simplest implementation and may suffice for the sole purpose of achieving the KS threshold, a larger $r$ may be beneficial in practice. For example, an adversary may add triangles for which ABP with $r=2$ would fail while larger $r$ would succeed. Finally, the approach of ABP can be extended beyond the linearized setting to improve the algorithm’s accuracy.

For the information-theoretic part, a few papers have studied information-theoretic bounds and information-computation tradeoffs for SBMs with a growing number of communities [YC14], two unbalanced communities [NN14], and a single community [Mon15]. No results seemed known for the symmetric SBM and Conjecture 1(b). Shortly after this paper posting, [BM16] obtained bounds on the information theoretic threshold in an independent effort using moment methods. The bound in [BM16] crosses at $k=5$ rather than $k=4$ and does not interpolate to the giant component bound for $b=0$.

3 Related models

Exact recovery is a stronger recovery requirement than detection, which has long been studied for the SBM [BCLS87, DF89, Bop87, SN97, JS98, CK99, CI01, McS01, BC09, RCY11, CWA12, CSX12, Vu14, YC14, AL14, ABBS14a], and more recently in the lens of sharp thresholds [ABH16, MNS14a, YP14, BH14, Ban15, GMZZ15, JL15, YP15]. The notion of exact recovery requires a reconstruction of the complete communities with high probability. It was proved in [ABH16, MNS14a] that exact recovery has a sharp threshold for SBM$(n,2,a\log(n),b\log(n))$ at $|\sqrt{a}-\sqrt{b}|=1$, which can be achieved efficiently. As opposed to detection which can exploit variations in degrees, exact recovery becomes harder when considering general SBMs, where communities have different relative sizes and different connectivity parameters. In [AS15a], it was proved that for the general SBM with linear size communities, exact recovery has a sharp threshold at the CH-divergence, and the threshold is proved to be efficiently achievable (without knowing the parameters in [AS15c]). This further improves on the result of [Vu14] that apply to the logarithmic degree regime in full generality. Thus, for exact recovery with linear size communities, there is no information-computation gap. When considering sub-linear communities and coarser regime of the parameters, [YC14] gives evidences that exact recovery can again have information-computation gaps. We also conjecture that similar phenomenon can take place in the setting of [AS15a] for exact recovery when $k$ is larger than $\log(n)$.

Finally, many variants of the SBM can be studied, such as the labelled block model [GZFA10, HLM12, XLM14], the censored block model [AM15, ABBS14a, CG14, ABBS14b, GRSY14, CRV15, SKLZ15], the degree-corrected block model [KN11], overlapping block models [For10] and more. While most of the fundamental challenges seem to be captured by the SBM already, these represent important extensions for applications.

Results

Our goal is to find an algorithm that can distinguish between vertices from one community and vertices from another community in a non trivial way, as defined below.

In other words, an algorithm solves detection if it divides the graph’s vertices into two sets such that vertices from different communities have different probabilities of being assigned to one of the sets. An alternate definition by Decelle et al. [DKMZ11] says that an algorithm succeeds at detection if it divides the vertices into $k$ sets and there exists $\epsilon>0$ such that with high probability there exists an identification of the sets with the communities such that the algorithm classifies at least $\max p_{i}+\epsilon$ of the vertices correctly:

In the $k$ community symmetric case, these definitions (detection and max-detection) are equivalent, but under asymmetry, this may not hold. Consider a two community asymmetric case where $p=(.2,.8)$. An algorithm that could find a set containing $2/3$ of the vertices from the large community and $1/3$ of the vertices from the small community would satisfy our definition; however, it would not satisfy Decelle’s definition because each vertex is more likely to be in the large community than the small one no matter what the algorithm outputs. In general, our definition is satisfied by any algorithm that produces nontrivial amounts of evidence on what communities the vertices are in, while Decelle’s definition requires the algorithm to sometimes produce enough evidence to overcome the prior probability. This may not always be possible (take for example the extreme case of an SBM with two community where each vertex is in community 1 with probability 0.99 and each pair of vertices in community 1 have an edge between them with probability $2/n$, while vertices in community 2 never have edges). If all communities have the same size then this distinction is meaningless, and we have:

of the vertices correctly with high probability. ∎

We present first a result that applies to the general SBM. We next specify the result for symmetric SBMs, and provide the ABP algorithm in the next section. Given parameters $p$ and $Q$ for the SBM, let $P$ be the diagonal matrix such that $P_{i,i}=p_{i}$ for each $i\in[k]$. Also, let $\lambda_{1},...,\lambda_{h}$ be the distinct eigenvalues of $PQ$ in order of nonincreasing magnitude. Our results are in terms of the following notion of SNR:

Let $p\in(0,1)^{k}$ with $\sum p=1$, $Q$ be a symmetric matrix with nonnegative entries, $P$ be the diagonal matrix such that $P_{i,i}=p_{i}$, and $\lambda_{1},...,\lambda_{h}$ be the distinct eigenvalues of $PQ$ in order of nonincreasing magnitude. If $\lambda_{2}^{2}>\lambda_{1}$ then there exist constants $r,c$ and $m=\Theta(\log(n))$ such that the acyclic belief propagation algorithm with these parameters solves detection in $SBM(n,p,Q/n)$. The algorithm can be run in $O(n\log n)$ time.

Our definition of detection also extends to deciding whether or not an algorithm distinguishes between two specific communities, in the sense that there exists $\epsilon>0$ such that the fraction of the vertices from one of these communities assigned to $S$ differs from the fraction of the vertices from the other community assigned to $S$ by at least $\epsilon$ with high probability. The right version of our ABP algorithm can then distinguish between communities $i$ and $j$ if there exists an eigenvector $w$ of $PQ$ with an eigenvalue of magnitude greater than $\sqrt{\lambda_{1}}$ such that $w_{i}\neq w_{j}$.

We present here two versions of our main algorithm. A simplified version ABP∗ that applies to the symmetric SBM and that can easily be implemented, and the general version ABP that is used to prove Theorem 1. The general version has additional steps that are used to prove the theorem, but these can be removed for practical applications. The intuitions behind the algorithms are discussed in Section 3.5, and in Section 3.6, we show that how the algorithms can be viewed as applying a power iteration method on a nonbacktracking operator $W^{(r)}$ of generalized order (where $r$ denotes the order of the nonbacktracks). The algorithms below have a message passing implementation and correspond to linearized version of belief propagation in which we originally guess what communities each vertex is likely to be in and then determine what communties each vertex’s neighbors provide evidence for it to be in. Then we use that information to update our beliefs about what evidence each vertex provides about its neighbors’ communities and repeat while mitigating cycles.

For each adjacent $v$ and $v^{\prime}$ in $G$, randomly draw $y^{(1)}_{v,v^{\prime}}$ from a Gaussian distribution with mean and variance $1$. Also, consider $y^{(t)}_{v,v^{\prime}}$ as having a value of whenever $t<1$.

for all adjacent $v$ and $v^{\prime}$. For each adjacent $v,v^{\prime}$ in $G$ that are not part of a cycle of length $r$ or less, set

and for the other adjacent $v,v^{\prime}$ in $G$, let the other vertex in the cycle that is adjacent to $v$ be $v^{\prime\prime\prime}$, the length of the cycle be $r^{\prime}$, and set

unless $t=r^{\prime}$, in which case, set $y_{v,v^{\prime}}^{(t)}=\sum_{v^{\prime\prime}:(v^{\prime},v^{\prime\prime})\in E(G),v^{\prime\prime}\neq v}z_{v^{\prime},v^{\prime\prime}}^{(t-1)}-z^{(1)}_{v^{\prime\prime\prime},v}$.

Set $y^{\prime}_{v}=\sum_{v^{\prime}:(v^{\prime},v)\in E(G)}y^{(m)}_{v,v^{\prime}}$ for every $v\in G$. Return $(\{v:y^{\prime}_{v}>0\},\{v:y^{\prime}_{v}\leq 0\})$.

(2) What the algorithm does if $(v,v^{\prime})$ is in multiple cycles of length $r$ or less is unspecified above, as there is no such edge with probability $1-o(1)$ in the sparse SBM. This can be modified for more general settings. The simplest such modification would be to apply this adjustment independently for each such cycle, and thus to set

where $C^{(r^{\prime})}_{v^{\prime\prime\prime},v,v^{\prime}}$ denotes the number of length $r^{\prime}$ cycles that contain $v^{\prime\prime\prime},v,v^{\prime}$ as consecutive vertices, substituting $z_{v^{\prime\prime\prime},v}^{(1)}$ for $\sum_{v^{\prime\prime}:(v,v^{\prime\prime})\in E(G),v^{\prime\prime}\neq v^{\prime},v^{\prime\prime}\neq v^{\prime\prime\prime}}z_{v,v^{\prime\prime}}^{(t-r^{\prime})}$ when $r^{\prime}=t$. This will not quite count r-nonbacktracking walks, but we believe that it would give a good enough approximation.

The full version of the algorithm applying to the general SBM is as follows.

$ABP(G,m,r,c,(\lambda_{1},...,\lambda_{h})):$

Set $s=2$ unless $h>2$ and $|\lambda_{2}|=|\lambda_{3}|$, in which case set $s=3$.

Set $\gamma=(1-\lambda_{1}/\lambda^{2}_{2})/2$.

Set $l=\max((s-1)/\ln((1-\gamma)|\lambda_{s}|)+s-1,2(2r+1)(s-1))$.

Assign each edge of $G$ independently with probability $\gamma$ to a set $\Gamma$. Then, remove these edges from $G$.

For every vertex $v\in G$, randomly draw $x_{v}$ from a Gaussian distribution with mean and variance $1$.

For each adjacent $v$ and $v^{\prime}$, set $y_{v,v^{\prime}}^{(1)}=x_{v^{\prime}}$, and $y_{v,v^{\prime}}^{(t)}=0$ for all $t<1$.

For each $1\leq t\leq m$, and each adjacent $(v,v^{\prime})\in E(G)$, set

unless $(v,v^{\prime})$ is part of a cycle of length $r$ or less. If it is, then let the other vertex in the cycle that is adjacent to $v$ be $v^{\prime\prime\prime}$, and the length of the cycle be $r^{\prime}$What the algorithm does if $(v,v^{\prime})$ is in multiple cycles of length $r$ or less is unspecified as there is no such edge with probability $1-o(1)$ in the SBM. One can adapt this for more general models.. Set

Set $Y$ to be the $n\times m$ matrix such that for all $t$ and $v$,

and set $y^{\prime\prime}_{v}$ to the sum of $y^{\prime}_{v^{\prime}}$ over all $v^{\prime}$ that have shortest paths to $v$ of length $\lfloor\sqrt{\log\log n}\rfloor$.

Set $c^{\prime}=c\cdot\sqrt{\sum_{v\in G}(y^{\prime\prime}_{v})^{2}/n}$. Create sets of vertices $S_{1}$ and $S_{2}$ as follows. For each vertex $v$, if $y^{\prime\prime}_{v}<-c^{\prime}$, assign $v$ to $S_{1}$. If $y^{\prime\prime}_{v}>c^{\prime}$, then assign $v$ to $S_{2}$. Otherwise, assign $v$ to $S_{2}$ with probability $1/2+y^{\prime\prime}_{v}/2c^{\prime}$ and $S_{1}$ otherwise.

2 Crossing the KS threshold information-theoretically

The following gives a region of the parameters in the symmetric SBM where detection can be solved information-theoretically.

This bound strictly improves on the KS threshold for $k\geq 4$:

As we shall see in Lemma 15, the above corresponds to the regime where there is no bad clustering that is typical with high probability. However, the above bound is not tight in the extreme regime of $b=0$, since it reads $a>2k$ as opposed to $a>k$, and only crosses the KS threshold at $k=5$.

Defining $a_{k}(b)$ as the unique solution of

and simplifying the bound in Theorem 2 gives the following.

Note that (9) approaches the optimal bound given by the presence of the giant at $b=0$, and we further conjecture that $a_{k}(b)$ gives the correct first order approximation of the information-theoretic bound for small $b$.

Note that the $k\ln k$ scaling in (8) improves significantly on the KS threshold given by $b>k(k-1)$ at $a=0$. Relatedly, note that the $k$-colorability threshold for Erdős-Rényi graphs grows as $2k\ln k$ [DA05]. This coule be used to obtain an information-theoretic bound, but the constant would be looser than the one obtained here.

We also believe that the above gives the correct scaling in $k$ for $a=0$, i.e., that for $b<(1-\varepsilon)k\ln(k)+o_{k}(1)$, $\varepsilon>0$, detection is information-theoretically impossible. To see this, consider $v\in G$, $b=(1-\epsilon)k\ln(k)$, and assume that we know the communities of all vertices more than $r=\ln(\ln(n))$ edges away from $v$. For each vertex $r$ edges away from $v$, there will be approximately $k^{\epsilon}$ communities that it has no neighbors in. Then vertices $r-1$ edges away from $v$ have approximately $k^{\epsilon}\ln(k)$ neighbors that are potentially in each community, with approximately $\ln(k)$ fewer neighbors suspected of being in its community than in the average other community. At that point, the noise has mostly drowned out the signal and our confidence that we know anything about the vertices’ communities continues to degrade with each successive step towards $v$.

In [BM16], a different approach than the one described in previous remark is developed based on a contiguity argument and estimates from [DA05], and formally proves that the scaling in $k$ is in fact tight.

where the above assumes that $a>b$; flip the above two inequalities in the case $a<b$.

3 Learning the model

To learn the parameters, we count cycles of slowly growing length as already done in [MNS15] for $k=2$, using non-backtracking walks to approximate the count.

Achieving the KS threshold: proof technique

Recall the parameters: $k$ and $n$ are positive integers, $p\in(0,1)^{k}$ with $\sum p_{i}=1$, and $Q$ is a $k\times k$ symmetric matrix with nonnegative entries. Then $SBM(n,p,Q/n)$ generates $n$-vertex graphs by the following procedure. First, each vertex $v$ is randomly and independently assigned a community $\sigma_{v}$ such that the probability that $\sigma_{v}=i$ is $p_{i}$ for each $i$. Then, each pair of vertices $v$ and $v^{\prime}$ have an edge put between them with probability $Q_{\sigma_{v},\sigma_{v^{\prime}}}/n$. Also, let $\Omega_{1},...,\Omega_{k}$ be the communities and $P$ be the $k\times k$ diagonal matrix such that $P_{i,i}=p_{i}$ for each $i$. Now, consider the $2$-community symmetric stochastic block model. In this case, $k=2$, $p=[1/2,1/2]$, $Q_{i,j}$ is $a$ if $i=j$ and $b$ otherwise for some $a,b$. Now, let $\lambda_{1}=\frac{a+b}{2}$ be the average degree of a vertex in a graph drawn from this model, and $\lambda_{2}=\frac{a-b}{2}$ be the other eigenvalue of $PQ$. Throught this section we say $f$ is approximately $g$ or $f\approx g$ when $|f-g|=o(|f+g|)$ with probability $1-o(1)$.

Our goal is to determine which of $v$’s vertices are in each community with an accuracy that is nontrivially better than that attained by random guessing. Obviously, the symmetry between communities ensures that we can never tell whether a given vertex is in community $1$ or community $2$, so the best we can hope for is to divide the vertices into two sets such that there is a nontrivial difference between the fraction of vertices from community $1$ that are assigned to the first set and the fraction of vertices from community $2$ that are assigned to the first set.

Let $x$ and $n-x$ be the numbers of vertices in community $1$ and community $2$ respectively. If the vertices are assigned sets at random, then the expected numbers of vertices from each community in the first set are $\frac{x}{2}$ and $\frac{n-x}{2}$. However, by the central limit theorem, the probability distribution of the actual number of vertices from a given community in the first set is approximately a gaussian distribution with the mean stated previously and a variance of $\frac{x}{4}$ or $\frac{n-x}{4}$ as appropriate. That means that the probability distribution of the difference between the fraction of the vertices from community $1$ assigned to the first set and the fraction of the vertices from the community $2$ assigned to the first set is also approximately a bell curve. This one has a mean of $\frac{1}{2}-\frac{1}{2}=0$ and a variance of

That means that it has a standard deviation of $\approx 1/\sqrt{n}$, and the difference between the fraction of the vertices from community $1$ assigned to the first set and the fraction of the vertices from community $2$ assigned to the first set will typically have a magnitude on the order of $1/\sqrt{n}$. Label the sets $S_{1}$ and $S_{2}$ such that the fraction of the vertices from $\Omega_{1}$ that were assigned to $S_{1}$ is at least as large as the fraction of the vertices from $\Omega_{2}$ that were assigned to $S_{1}$. For the rest of this section, we will consider the difference between these fractions to be fixed.

Consider determining the community of $v$ using belief propagation, assuming some preliminary guesses about the vertices $t$ edges away from it, and assuming that the subgraph of $G$ induced by the vertices within $t$ edges of $v$ is a tree. For any vertex $v^{\prime}$ such that $d(v,v^{\prime})<t$, let $C_{v^{\prime}}$ be the set of the children of $v^{\prime}$. If we believe based on either our prior knowledge or propagation of beliefs up to these vertices that $v^{\prime\prime}$ is in community $1$ with probability $\frac{1}{2}+\frac{1}{2}\epsilon_{v^{\prime\prime}}$ for each $v^{\prime\prime}\in C_{v^{\prime}}$, then the algorithm will conclude that $v^{\prime}$ is in community $1$ with a probability of

If all of the $\epsilon_{v^{\prime\prime}}$ are close to , then this is approximately equal to

Equivalently, given a vertex $v$ and a small $t$, the expected number of vertices that are $t$ edges away from $v$ is approximately $(\frac{a+b}{2})^{t}$, and the expected number of these vertices in the same community as $v$ is approximately $(\frac{a-b}{2})^{t}$ greater than the expected number of these vertices in the other community. So, if we had some way to independently determine which community a vertex is in with an accuracy of $\frac{1}{2}+\epsilon$ for small $\epsilon$, we could guess that each vertex is in the community that we think that the majority of the vertices $t$ steps away from it are in to determine its community with an accuracy of roughly $\frac{1}{2}+\left(\frac{(a-b)^{2}}{2(a+b)}\right)^{t/2}\epsilon$.

To obtain initial estimates, we simply guess the vertices’ communities at random as described in the previous section, with the expectation that the fractions of the vertices from the two communities assigned to a community will differ by $\theta(1/\sqrt{n})$ by the Central Limit Theorem. Once we have even such weak information on which vertex is in which community, we can try to improve our classification of a given vertex by factoring in our knowledge of what communities the nearby vertices are in. For a vertex $v$ and integer $t$, let $N_{t}(v)$ be the number of vertices $t$ edges away from $v$, $\Delta_{t}(v)$ be the difference between the number of vertices $t$ edges away from $v$ that are in community $1$ and the number of vertices $t$ edges away from $v$ that are in community $2$, and $\widetilde{\Delta}_{t}(v)$ be the difference between the number of vertices $t$ edges away from $v$ that are in $S_{1}$ and the number of vertices $t$ edges away from $v$ that are in $S_{2}$. For small $t$,

For any fixed values of $N_{t}(v)$ and $\Delta_{t}(v)$, the probability distribution of $\widetilde{\Delta}_{t}(v)$ is essentially a Gaussian distribution with a mean of $\Theta(\Delta_{t}(v)/\sqrt{n})$ and a variance of $\approx N_{t}(v)$ because it is the sum of $N_{t}(v)$ nearly independent variables that are approximately equally likely to be $1$ or $-1$. So, $\widetilde{\Delta}_{t}(v)$ is positive with a probability of $\frac{1}{2}+\Theta(\Delta_{t}(v)/\sqrt{|N_{t}(v)|n})$. In other words, if $v$ is in community $1$ then $\widetilde{\Delta}_{t}(v)$ is positive with a probability of

and if $v$ is in community $2$ then $\widetilde{\Delta}_{t}(v)$ is positive with a probability of

If $(a-b)^{2}\leq 2(a+b)$, then this is not improving the accuracy of the classification, so this technique is useless. On the other hand, if $(a-b)^{2}>2(a+b)$, the classification becomes more accurate as $t$ increases. However, this formula says that to classify vertices with an accuracy of $1/2+\Omega(1)$, we would need to have $t$ such that

However, unlessIf $a=0$ and $k=2$ or $b=0$, then classifying vertices based on the sign of $\widetilde{\Delta}_{t}(v)$ for suitable $t$ is likely to work, but this is pointlessly complicated because every component of the graph consists of all vertices of one community or vertices of alternating communities. $a$ or $b$ is , that would imply that

which means that $(\frac{a+b}{2})^{t}=\omega(n)$. It is obviously impossible for $N_{t}(v)$ to be greater than $n$, so this $t$ is too large for the approximation to hold. The problem is, the approximation assumes that each vertex at a distance of $t-1$ from $v$ has one edge leading back towards $v$, and that the rest of its edges lead towards new vertices. Once a significant fraction of the vertices are less than $t$ edges away from $v$, a significant fraction of the edges incident to vertices $t-1$ edges away from $v$ are part of loops and thus do not lead to new vertices.

2 Nonbacktracking walks

An obvious way to solve the problem caused by running out of vertices would be to simply count the walks of length $t$ from $v$ to vertices in $S_{1}$ or $S_{2}$. Recall that a walk is a series of vertices such that each vertex in the walk is adjacent to the next, and a path is a walk with no repeated vertices. The last vertex of such a walk will be adjacent to an average of approximately $a/2$ vertices in its community outside the walk and $b/2$ vertices in the other community outside the walk. However, it will also be adjacent to the second to last vertex of the walk, and maybe some of the other vertices in the walk as well. As a result, the number of walks of length $t$ from $v$ to vertices in $S_{1}$ or $S_{2}$ cannot be easily predicted in terms of $v$’s community. So, the numbers of such walks are not useful for classifying vertices.

We could deal with this issue by counting pathsThis type of approach is considered in [BB14]. of length $t$ from $v$ to vertices in $S_{1}$ and $S_{2}$. Given a path of length $t-1$, the expected number of vertices outside the path in the same community as its last vertex that are adjacent to it is approximately $a/2$ and the expected number of vertices outside the path in the opposite community as its last vertex that are adjacent to it is approximately $b/2$. So, the expected number of paths of length $t$ from $v$ is approximately $(\frac{a+b}{2})^{t}$ and the expected difference between the number that end in vertices in the same community as $v$ and the number that end in the other community is approximately $(\frac{a-b}{2})^{t}$. The problem with this is that counting all of these paths is inefficient.

The compromise we use is to count nonbacktracking walks ending at $v$, i.e. walks that never repeat the same edge twice in a row. We can efficiently determine how many nonbacktracking walks of length $t$ there are from vertices in $S_{i}$ to $v$ by using the fact that the number of nonbacktracking walks of length $t$ starting at a vertex in $S_{i}$ and having $v^{\prime}$ and $v$ as their last two vertices is equal to the sum over all $v^{\prime\prime}\neq v$ such that $v^{\prime\prime}$ is adjacent to $v^{\prime}$ of the number of nonbacktracking walks of length $t-1$ starting at a vertex in $S_{i}$ and having $v^{\prime\prime}$ and $v^{\prime}$ as their last two vertices. Furthermore, most nonbacktracking walks of a given length that is logarithmic in $n$ are paths, so it seems reasonable to expect that counting nonbacktracking walks instead of paths in our algorithm will have a negligible effect on the accuracy.

More precisely, that suggests the following approach. Define $y_{v,v^{\prime}}^{(t)}$ to be the number of nonbacktracking walks of length $t$ that start at vertices in $S_{2}$ and end in the directed edge $(v^{\prime},v)$ minus the number of nonbacktracking walks of length $t$ that start at vertices in $S_{1}$ and end in $(v^{\prime},v)$. Also, define $y_{v}^{(t)}$ to be the overall difference between the number of nonbacktracking walks of length $t$ from vertices in $S_{2}$ to $v$ and the number of nonbacktracking walks of length $t$ from vertices in $S_{1}$ to $v$. Their values can be efficiently computed by means of the following procedure:

If $v^{\prime}\in S_{2}$, set $y_{v,v^{\prime}}^{(1)}=1$

Otherwise, set $y_{v,v^{\prime}}^{(1)}=-1$

For every $1<t\leq m$ and $(v,v^{\prime})\in E(G):$

Set $y_{v,v^{\prime}}^{(t)}=\sum_{v^{\prime\prime}:(v^{\prime\prime},v^{\prime})\in E(G),v^{\prime\prime}\neq v}y_{v^{\prime},v^{\prime\prime}}^{(t-1)}$

For every $(v,v^{\prime})\in E(G)$ and $v\in G$

Set $y_{v}^{(m)}=\sum_{v^{\prime}:(v,v^{\prime})\in E(G)}y_{v,v^{\prime}}^{(m)}$

One way of viewing this algorithm is that $y_{v,v^{\prime}}^{(t)}$ represents our current belief about what community $v^{\prime}$ is in, disregarding any information derived from the fact that it is next to $v$. We start with fairly unconfident beliefs about the vertices’ communities, and then derive more and more confident beliefs about the vertices’ communities by taking our beliefs about their neighbors’ communities into account.

3 Compensation for the average value

$y_{v,v^{\prime}}^{(1)}$ has an average value of $\Theta(1/\sqrt{n})$ for $v^{\prime}$ in community $2$ and $-\Theta(1/\sqrt{n})$ for $v^{\prime}$ in community $1$. Also, $y_{v,v^{\prime}}^{(1)}$ has a variance of order $1$. For a random $(v,v^{\prime})\in E(G)$, $v^{\prime}$ will have an average of approximately $a/2$ neighbors other than $v$ in its community and $b/2$ neighbors other than $v$ in the other community. So, by induction on $t$, we would expect that $y_{v,v^{\prime}}^{(t)}$ would have an average value of $\Theta((\frac{a-b}{2})^{t}/\sqrt{n})$ for v’ in community $2$ and $-\Theta((\frac{a-b}{2})^{t}/\sqrt{n})$ for v’ in community $1$. Since $y_{v^{\prime},v^{\prime\prime}}^{(t-1)}$ should be approximately independent for different $v^{\prime\prime}$ adjacent to $v^{\prime}$, we would also expect that $y_{v,v^{\prime}}^{(t)}$ would have an empirical variance of approximately $(\frac{a+b}{2})^{t}$, and thus a standard deviation of approximately $\sqrt{(\frac{a+b}{2})^{t}}$. So, for $t$ such that $(\frac{a-b}{2})^{t}/\sqrt{n}>\sqrt{(\frac{a+b}{2})^{t}}$, we would expect that we could determine the community of $v^{\prime}$ from $y_{v,v^{\prime}}^{(t)}$ with accuracy $1/2+\Omega(1)$.

The problem with this reasoning is that the average value over all $(v,v^{\prime})\in E(G)$ of $y_{v,v^{\prime}}^{(1)}$ will not be exactly . It will also tend to have an absolute value on the order of $1/\sqrt{n}$. That means that the average value over all $(v,v^{\prime})\in E(G)$ of $y_{v,v^{\prime}}^{(t)}$ will have an absolute value of $\Theta((\frac{a+b}{2})^{t}/\sqrt{n})$. If we hold the average value of $y_{v,v^{\prime}}^{(t-1)}$ fixed then that means that $E[y_{v,v^{\prime}}^{(t)}|N_{1}(v^{\prime})]$ will have an empirical variance of $\Theta((\frac{a+b}{2})^{2t}/n)$, and thus that $y_{v,v^{\prime}}^{(t)}$ will also have an empirical variance of at least $\Theta((\frac{a+b}{2})^{2t}/n)$. This implies that the standard deviation of $y_{v,v^{\prime}}^{(t)}$ will always be much greater than the difference between the average value of $y_{v,v^{\prime}}^{(t)}$ for $v^{\prime}$ in community $1$ and the average value of $y_{v,v^{\prime}}^{(t)}$ for $v^{\prime}$ in community $2$, which would render attempts to classify $v^{\prime}$ based on $y_{v,v^{\prime}}^{(t)}$ ineffective.

The simple way to fix this would be to add a step where we subtract the average value of $y^{(t)}$ from every element of $y^{(t)}$ so its sum is for every $t$ like we did in the version of $ABP$ in Section 2.1.1. However, this does not extend easily to the general Stochastic Block Model, and we want a solution that does.

In order to prevent this, we need to stop the average value of $y_{v,v^{\prime}}^{(t)}$ from getting too large. It will tend to multiply by roughly $\frac{a+b}{2}$ each time $t$ increases by $1$, so the average value of $y_{v,v^{\prime}}^{(t)}-\frac{a+b}{2}y_{v,v^{\prime}}^{(t-1)}$ will probably be much smaller than the average value of $y_{v,v^{\prime}}^{(t)}$. So, if we pick some $1<i\leq m$ and redefine $y_{v,v^{\prime}}^{(i)}$ so that

for all $(v,v^{\prime})\in E(G)$, the average value of $y_{v,v^{\prime}}^{(i)}$ will be much smaller than it would have been. Since the difference between the average values of $y_{v,v^{\prime}}^{(t)}$ over $v^{\prime}$ in different communities grows as $\Theta((\frac{a-b}{2})^{t}/\sqrt{n})$, this redefinition will merely change the difference between the average values over $v^{\prime}$ in different communities of $y_{v,v^{\prime}}^{(i)}$ from $\Theta((\frac{a-b}{2})^{i}/\sqrt{n})$ to

However, the average value of $y_{v,v^{\prime}}^{(i)}$ will still be nonzero, and if we continue to set $y_{v,v^{\prime}}^{(t)}=\sum_{v^{\prime\prime}:(v^{\prime\prime},v^{\prime})\in E(G),v^{\prime\prime}\neq v}y_{v^{\prime},v^{\prime\prime}}^{(t-1)}$ for all $t>i$, the average value of $y_{v,v^{\prime}}^{(t)}$ would resume increasing in magnitude faster than the average difference between $y_{v,v^{\prime}}^{(t)}$ for different communities of $v^{\prime}$. This creates the risk that it would still eventually get too large. So, in order to actually fix the problem, it may be necessary to repeat the step where its magnitude is reduced. More precisely, we may have to choose several indices $t_{0},t_{1},...t_{m^{\prime}}$ and redefine $y_{v,v^{\prime}}^{(t_{i})}$ for each $i$ so that

Once we have made these modifications, it will be the case that for sufficiently large $m$, the average value for $v^{\prime}$ in community $1$ of $y_{v,v^{\prime}}^{(m)}$ will differ from the average value for $v^{\prime}$ in community $2$ of $y_{v,v^{\prime}}^{(m)}$ by a constant multiple of the standard deviation of $y_{v,v^{\prime}}^{(m)}$. Then, we define $y_{v}^{(m)}=\sum_{v^{\prime}:(v,v^{\prime})\in E(G)}y_{v,v^{\prime}}^{(m)}$ in order to simplify it to a function of one vertex which is still correlated with the vertex’s community. Unfortunately, this does not guarantee that simply dividing the vertices into those with a positive value of $y_{v}^{(m)}$ and those with a negative value of $y_{v}^{(m)}$ will give a useful partition. It could be the case that the fraction of $v$ for which $y_{v}^{(m)}$ is positive is the same for both communities, but $y_{v}^{(m)}$ is typically more strongly positive or less strongly negative for $v$ in one community than $v$ in the other. So, we randomly assign each vertex to a set with a probability that scales linearly with $y_{v}^{(m)}$ in order to ensure that having a higher average value of $y_{v}^{(m)}$ actually leads to having greater representation in one of the proposed communities.

4 Vanilla ABP

We present first a simplified version of our algorithm. Our proof relies on a modified version described below, but this version captures the essence of our algorithm while avoiding technicalities required for the proof.

For each adjacent $v$ and $v^{\prime}$ in $G$, randomly draw $y^{(1)}_{v,v^{\prime}}$ from a Gaussian distribution with mean and variance $1$. Also, consider $y^{(t)}_{v,v^{\prime}}$ as having a value of whenever $t<1$.

For each $1<t\leq m$, and each adjacent $v$ and $v^{\prime}$ in $G$, set

unless $(v,v^{\prime})$ is part of a cycle of length $r$ or less.See Remark (2) in Section 2.1.1 for how to modify the algorithm in the case of multiple cycles. If it is, then let the other vertex in the cycle that is adjacent to $v$ be $v^{\prime\prime\prime}$, and the length of the cycle be $r^{\prime}$, and set

unless $t=r^{\prime}$, in which case, set

Set $Y$ to be the $n\times m$ matrix such that for all $t$ and $v$,

Return $(\{v:y^{\prime}_{v}>0\},\{v:y^{\prime}_{v}\leq 0\})$.

This version of ABP is mostly the same as the one in Section 2.1.1. However, the previous version compensates for biases in $y^{(1)}$ by subtracting the average value of $y^{(t)}$ from each entry in $y^{(t)}$ for every $t$ in order to prevent it from ever becoming significantly biased. This version compensates for biases by a variant of the method explained in the previous subsection instead. More specifically, it uses the method explained in the previous subsection except that it calculates all of the $y^{(t)}$ without using any form of compensation and then adjusts the results in order to essentially apply the compensation retroactively.

Implementation details. Note that $ABP^{*}$ has several differences from the algorithm outlined in previous sections. First of all, we initialize the $y_{v,v^{\prime}}^{(0)}$ using a random value that is drawn from a normal distribution because a probability distribution that is a multidimensional normal distribution is easier to analyse than a probability distribution that is evenly distributed over the vertices of an $n$-dimensional hypercube. Secondly, we require that our walks never repeat the same vertex within $r$ steps for some $r$, rather than merely requiring that they not backtrack. This allows us to use the expected number of walks between vertices in our analysis without worrying about the tiny probability that there is a dense tangle in the graph with a huge number of nonbacktracking walks between its vertices. Making this modification to the algorithm requires adding an extra part to the recursion step where walks that just repeated a vertex are cancelled out, specifically the second half of step $3$ of the algorithm above. The resulting algorithm is called the acyclic belief propagation algorithm because it counts walks that do not contain any small cycles. Thirdly, we move all of the recursion steps that compensate for the average value to the end of the algorithm. This is possible because the operation that takes $y^{(t-1)}$ as input and outputs a list that has a value of

for each $(v,v^{\prime})\in E$ commutes with the one that simply outputs a list that has a value of $\sum_{v^{\prime\prime}:(v^{\prime\prime},v^{\prime})\in E(G),v^{\prime\prime}\neq v}y_{v^{\prime},v^{\prime\prime}}^{(t-1)}$ for each $(v,v^{\prime})\in E$. The algorithm generates $y^{(m)}$ by applying these two operations in some sequence to $y^{(1)}$, so we can calculate it by applying the later operation $m-m^{\prime}$ times and then applying the former operation $m^{\prime}$ times. Actually, the algorithm takes this one step farther by applying the later operation $m$ times and then calculating how the result would have changed if it had applied the former the appropriate number of times, but it still has the same result.

The full Acyclic Belief Propagation algorithm also has a few differences from $ABP^{*}$ that make it easier to prove that it works. In particular, we randomly select a small fraction of the graph’s edges at the beginning of the algorithm. Then, we require one specific step of each nonbacktracking walk to use one of the selected edges, and all of their other steps to use edges that have not been selected. Since the selected edges are nearly independent of the rest of the graph, this allows us to more easily prove that the values of $y_{v^{\prime},v^{\prime\prime}}^{(t-1)}$ for $v^{\prime}$ adjacent to $v$ will not become dependent in a way that disrupts the algorithm.

5 ABP for the symmetric SBM

Let $a$ and $b$ be positive real numbers such that $(a-b)^{2}>2(a+b)$, and $S$ be the $2$-community symmetric stochastic block model with these parameters. There exist constants $\epsilon,l,r,c>0$ and $m=\Theta(\log(n))$ such that when the basic $2$-community symmetric acyclic belief propagation algorithm is run on these parameters and a random $G\in S$, the expected difference between the fraction of vertices from community $1$ that are in $S_{1}$ and the fraction of vertices from community $2$ that are in $S_{1}$ is at least $\epsilon$.

The basic $2$-community symmetric acyclic belief propagation algorithm is as follows.

$2CS-ABP^{\star}(G,m,r,l,c,\lambda_{1}):$

Find all cycles of length $r$ or less in $G$.

For every vertex $v\in G$, randomly assign $x_{v}$ according to a Normal distribution with mean and variance $1$. For each adjacent $v$ and $v^{\prime}$, let $y_{v,v^{\prime}}^{(1)}=x_{v^{\prime}}$, and $y_{v,v^{\prime}}^{(t)}=0$ for all $t\leq 0$.

For each $1\leq t\leq m$, and each adjacent $(v,v^{\prime})\in E(G)$, set

unless $v,v^{\prime}$ is part of a cycle of length $r$ or less. If it is, then let the other vertex in the cycle that is adjacent to $v$ be $v^{\prime\prime\prime}$, and the length of the cycle be $r^{\prime}$. Set

Set $Y$ to be the $n\times m$ matrix such that for all $t$ and $v$,

Set $c^{\prime}=c\cdot\sqrt{\sum_{v\in G}(y^{(m)}_{v})^{2}/n}$. Create sets of vertices $S_{1}$ and $S_{2}$ as follows. For each vertex $v$, if $y^{(m)}_{v}<-c^{\prime}$, assign $v$ to $S_{1}$. If $y^{(m)}_{v}>c^{\prime}$, then assign $v$ to $S_{2}$. Otherwise, assign $v$ to $S_{2}$ with probability $1/2+y^{(m)}_{v}/2c^{\prime}$ and $S_{1}$ otherwise. Return $(S_{1},S_{2})$.

We believe that the difference between the fraction of vertices from community $1$ that this algorithm puts in $S_{1}$ and the fraction of vertices from community $2$ that this algorithm puts in $S_{1}$ will be at least $\epsilon$ with probability $1-o(1)$. However, in order to prove that we can detect communities reliably we use the following slightly modified form of the algorithm.

Let $a$ and $b$ be positive real numbers such that $(a-b)^{2}>2(a+b)$, and $S$ be the $2$-community symmetric stochastic block model with these parameters. There exist constants $\epsilon,l,r,c,\gamma>0$ and $m=\Theta(\log(n))$ such that when the $2$-community symmetric acyclic belief propagation algorithm is run on these parameters and a random $G\in S$, the difference between the fraction of vertices from community $1$ that are in $S_{1}$ and the fraction of vertices from community $2$ that are in $S_{1}$ is at least $\epsilon$ with probability $1-o(1)$.

The $2$-community symmetric acyclic belief propagation algorithm is as follows.

Randomly and independently select each edge in $G$ with probability $\gamma$. Put all of the selected edges in a set $\Gamma$, and remove them from the graph.

For every vertex $v\in G$, randomly assign $x_{v}$ according to a Normal distribution with mean and variance $1$. For each adjacent $v$ and $v^{\prime}$, let $y_{v,v^{\prime}}^{(1)}=x_{v^{\prime}}$, and $y_{v,v^{\prime}}^{(t)}=0$ for all $t\leq 0$.

For each $1\leq t\leq m$, and each adjacent $(v,v^{\prime})\in E(G)$, set

unless $v,v^{\prime}$ is part of a cycle of length $r$ or less. If it is, then let the other vertex in the cycle that is adjacent to $v$ be $v^{\prime\prime\prime}$, and the length of the cycle be $r^{\prime}$. Set