Community Detection and Stochastic Block Models

1.1 Community detection, clustering and block models

• The SBM is a canonical random-graph model whose planted communities provide ground truth for formally studying community-detection limits.Its discrete labels are sampled independently from p, while edges connect independently according to the symmetric matrix W.Source: §1.1 · pp. 6–7, §2.1 · p. 14

1.2 Fundamental limits: information and computation

• Fundamental limits characterize necessary and sufficient conditions for recovery, separating information-theoretic feasibility from polynomial-time computability and revealing phase transitions.These limits have motivated sphere-comparisons, linearized belief propagation, and nonbacktracking spectral methods, while information-computation gaps can remain.Source: §1.2 · p. 8

1.3 An example on real data

• Under an SBM fit, the political-blog graph achieves about 95% agreement with known left- and right-leaning labels, roughly matching the state of the art.The example contains 1,222 blogs connected by hyperlinks, with two assortative communities inferred from the graph.Source: §1.3 · p. 9, Figure 1.2 · p. 10

introduction).

• For the political-blog data, the estimated constant-degree SNR is approximately 18 and logarithmic-degree CH-divergence approximately 2, placing the graph above weak and exact recovery thresholds.This indicates a strongly clusterable regime under the SBM, although algorithmic failures may instead reflect degree variation and motivate degree-corrected models.Source: introduction) · pp. 10–11

1.4 Historical overview of the recent developments

• Recent work established the Kesten–Stigum weak-recovery transition and the general-SBM exact-recovery transition, with efficient algorithms reaching these limits in broad settings.The historical development includes nonbacktracking spectral methods, higher-order message passing, and information-theoretic crossing of the Kesten–Stigum threshold for four or more symmetric communities.Source: §1.4 · pp. 11–12

1.5 Outline

• The monograph next defines exact, weak, and partial recovery, develops their limits and algorithms for two and general communities, then discusses other block models and open problems.It provides complete revised proofs for exact recovery and partial proofs for weak and partial recovery.Source: §1.5 · p. 13

2.1 The general SBM

• In SBM(n, p, W), vertex labels are i.i.d. from p, and each vertex pair connects independently with probability W_Xi,Xj, forming community sets Ω_i.The monograph generally keeps p fixed with n, so the number of communities is fixed and communities have linear size, while W may vary with n.Source: §2.1 · pp. 14–15
• Equivalent SBM formulations can impose fixed community proportions on uniformly random vertex labels, and the models may be interchanged to simplify proofs.For consistent n and p, one may require n|{v ∈ [n] : Xv = i}| = p_i; for two symmetric communities, n/2 must be an integer.Source: §2.1 · p. 15
• The fixed-proportion formulation applies only for consistent choices of n and p, such as integer n/2 in the two-community symmetric case.Source: §2.1 · p. 15
• If every entry of W is identical, the SBM collapses to an Erdős–Rényi random graph and meaningful community reconstruction is impossible.Source: §2.1 · p. 15

2.2 The symmetric SBM

• The symmetric SBM uses uniform community prior 1/k, within-community probability qin, between-community probability qout, and equal community sizes when n is divisible by k.Symmetry means p is uniform and W has one diagonal value and one off-diagonal value; the strictly balanced model imposes n/k vertices per community.Source: §2.2 · p. 15

2.3 Recovery requirements

• Recovery evaluates inferred labels up to permutation because SSBM labels are non-identifiable, although the underlying partition remains recoverable.Once the partition is found, assigning labels is simpler when labels are identifiable, but impossible under symmetric label exchangeability.Source: §2.3 · p. 16
• Exact, almost exact, partial, and weak recovery require progressively weaker accuracy, with partial recovery demanding α > 1/k and weak recovery demanding 1/k + ε in SSBM.All recovery requirements are asymptotic with high probability; partial and weak recovery use normalized agreement, while symmetric SBMs can use ordinary agreement.Source: §2.3 · p. 17
• Normalized agreement is necessary for general SBMs because max-detection can reward trivial majority assignments and fail to capture informative separation between communities.For example, in a two-community model with sizes (0.8, 0.2), assigning every vertex to the larger community achieves 0.8 agreement, while normalized criteria avoid this issue.Source: §2.3 · p. 18
• Weak recovery requires nontrivial community separation; in symmetric SBMs, Definition 7 implies max-detection after adding k − 2 empty output sets, with extension to some weakly symmetric models.Vanishing conditional mutual information between arbitrary vertex labels also precludes reconstructing all vertices for weak recovery.Source: §2.3 · pp. 17, 19

2.4 SBM regimes and topology

• For Erdős–Rényi graphs, connectivity and giant-component thresholds occur at c = 1, while neighborhoods up to depth δ log_c n locally converge to Poisson(c) Galton–Watson trees for δ < 1/2.The symmetric SBM inherits analogous statements after replacing c with its average degree.Source: §2.4 · p. 20
• In SSBM(n, k, a log n/n, b log n/n), connectivity requires a+(k−1)b/k > 1, whereas in SSBM(n, k, a/n, b/n), a giant component requires d := a+(k−1)b > 1.Sparse SSBM neighborhoods locally converge to Poisson(d) Galton–Watson trees at depth δ log_d n for δ < 1/2.Source: §2.4 · p. 20
• Disconnected graphs rule out exact recovery and graphs without a giant component rule out weak recovery, but connectivity and giant-component thresholds are not themselves sufficient.Thus exact recovery requires the logarithmic-degree regime, while weak recovery in sparse SSBM needs more than a+(k−1)b > 1.Source: §2.4 · pp. 20–21

2.5.1 Diverging degree regime

• In the diverging-degree regime, agnostic sphere comparison enables community detection with accuracy at least 1 − e^−Ω(α) in O(n^(1+ε(α))) time, yielding quasi-linear consistent parameter estimation.The guarantee applies for sufficiently large α, with ε(α) = O(1/log(c)); the number of communities, prior, and connectivity matrix can all be estimated.Source: §2.5.1 · p. 21

2.5.2 Constant degree regime

• In the constant-degree two-community SBM, cycle counts and average degree provide polynomial-time consistent estimators for a and b above the weak-recovery threshold.The condition is (a − b)^2 > 2(a + b), using cycles of length m_n = floor(log^(1/4)(n)).Source: §2.5.2 · p. 22
• For general constant-degree SBMs, parameter learning requires stabilized cycle statistics to extract eigenvalues of diag(p)Q, followed by weak-recovery methods to estimate p and Q.Which parameters are learnable in the general SBM remains non-trivial; in the symmetric case, estimation is impossible at or below (a − b)^2 = 2(a + b).Source: §2.5.2 · p. 23

model

• The SBM admits both a low-rank perturbation interpretation and a noisy-channel interpretation, with community labels encoded through sparse graph interactions.In the channel view, edge presence or absence is generated by a memoryless channel determined by W.Source: model · pp. 24–25

3.1 The block MAP estimator

• Block MAP minimizes exact partition error and, for balanced two-community SBMs, is equivalent to finding a minimum bisection.However, weak recovery can remain solvable when MAP fails, including parameters a = 2.5 and b = 0.1 where MAP fails despite weak recovery being possible.Source: §3.1 · pp. 26–27

3.2 Computing block MAP: spectral and SDP relaxations

• Exact MAP optimization may require exponential search and is computationally difficult because worst-case min-bisection is NP-hard with a polylogarithmic integrality gap.This motivates relaxations designed to approximate the MAP objective.Source: §3.2 · p. 27
• Spectral relaxations replace integral labels with real vectors and use the second adjacency eigenvector, or equivalently the second Laplacian eigenvector, to round communities.In the symmetric SBM, the expected adjacency matrix has eigenvalues (q_in + q_out)/2 and (q_in − q_out)/2, so success depends on noise preserving alignment with the leading eigenspaces.Source: §3.2 · pp. 27–28
• SDP relaxations lift the quadratic MAP objective into a linear optimization by dropping the rank-one constraint; they work well for exact recovery but are suboptimal for weak recovery.Compared with spectral methods, SDPs are less sensitive to degree variation but have significantly higher complexity; other spectral methods can achieve optimality in quasi-linear time.Source: §3.2 · p. 29

3.3 The bit MAP estimator

• Bit MAP maximizes expected agreement by choosing, for each vertex, the label with the largest posterior marginal P(X_v = x_v|G = g).In the symmetric SBM, the marginal is 1/2, so symmetry must first be broken; the weakly symmetric model provides one way to do this.Source: §3.3 · p. 30

3.4 Computing bit MAP: belief propagation

• Belief propagation computes bit-MAP marginals by repeatedly passing neighboring-community beliefs through the graph.The recursion is based on conditional independence of edges given labels and asymptotic independence of neighbors after removing the target vertex.Source: §3.4 · pp. 30–31
• The BP approximation relies on sparse SBM graphs being locally tree-like, so distant neighbors are connected only through paths of length Ω(log n) with high probability.This makes the independence approximation reasonable except when small cycles couple the relevant vertices.Source: §3.4 · p. 31
• BP is efficient and outputs a distribution for each vertex, but proving convergence to the true distribution, even from random initialization, remains open.Linearizing BP yields an analyzable method related to the nonbacktracking operator, avoiding adjacency-matrix sensitivity to degree variations in weak recovery.Source: §3.4 · p. 32

Exact recovery for two communities

• For exact recovery, [Vu14] obtained a spectral-algorithm result when expected degrees are logarithmic rather than poly-logarithmic, with tight scaling, but without revealing the phase transition.Source: Exact recovery for two communities · p. 33
• At the exact-recovery threshold, the solvability condition differs according to whether both connectivity parameters are positive or one is zero, as shown in [MNS14].The zero-parameter case corresponds to connectivity, while the positive-parameter case has a distinct square-root separation condition.Source: Exact recovery for two communities · p. 34
• The exact-recovery theorem covers parameter sequences whose within- and across-community probabilities are not asymptotically equivalent; when their ratio tends to one, second-order terms determine solvability.For a_n, b_n = Θ(1), [MNS14] gives the criterion ((√a_n −√b_n)^2 −1) log n + log log n/2 = ω(1).Source: Exact recovery for two communities · p. 34
• Exact recovery requires connectivity but connectivity alone is insufficient: an additional over-sampling factor separates the exact-recovery threshold from the connectivity threshold.The connectivity threshold is recovered in the special case b = 0.Source: Exact recovery for two communities · p. 34

4.1 Warm up: genie-aided hypothesis test

• The genie-aided problem labels one unknown vertex given n/2 revealed vertices in each community, reducing recovery to distinguishing two equiprobable hypotheses.Under the two-community model, the unknown vertex’s incident-edge counts determine the test: N1 is Bin(n/2, qin) under one label and Bin(n/2, qout) under the other.Source: §4.1 · pp. 34–35
• The MAP error probability in the genie-aided test provides the key local estimate underlying the exact-recovery threshold.The same asymptotic estimate applies to closely related binomial comparisons, as noted through Lemma 1 in [AFWZ17], initially proved in.Source: §4.1 · p. 35

4.2.1 Converse

• Below the connectivity bound, exact recovery is impossible because the graph is disconnected with high probability.Disconnected components cannot be assigned their planted labels with probability tending to one, although connectivity alone is not the tight condition.Source: §4.2.1 · p. 36
• More generally, a nonempty set of bad vertex pairs makes exact recovery impossible because swapping such a pair yields an alternative partition with at least as high likelihood.A bad vertex has no more within-community than cross-community edges, and approximate independence allows such obstructions to occur with nonvanishing probability below the threshold.Source: §4.2.1 · pp. 37–39

4.2 The information-theoretic threshold

• Exact recovery is solvable above the information-theoretic threshold and impossible below it in the two-community symmetric SBM with uniformly balanced communities.The MAP estimator is the minimum-bisection estimator, and the converse and achievability theorems show that the threshold is tight.Source: §4.2.1 · p. 36, §4.2 · p. 36, §4.2.2 · p. 40

4.2.2 Achievability

• Above the converse bound, the planted bisection is recovered because no balanced k-swap reduces the cut, for any k from 1 through n/4.The one-swap obstruction dominates: the remainder from larger swaps satisfies R = O(n^2Pe(1)), and n^2Pe(1) vanishes above the threshold; this approach is used in.Source: §4.2.2 · pp. 40–41
• Graph-splitting gives an alternative achievability route by producing an almost-exact clustering on a low-degree subgraph and refining it with a genie-aided test on the remaining edges.With γ = log log(n)/log(n), the first graph has degrees scaling as log log(n), while the refinement graph yields the same threshold despite the genie being only almost exact.Source: §4.2.2 · p. 41

4.3.1 Spectral algorithm

• The vanilla spectral algorithm achieves exact recovery at the exact recovery threshold by rounding the signs of the leading eigenvector of the centered adjacency matrix.The method relaxes min-bisection through an Euclidean-norm constraint and uses random-matrix perturbation analysis; the centered formulation assumes p + q is known or estimated, while the second eigenvector of A′ can be used directly [AFWZ17].Source: §4.3.1 · pp. 42–43
• The spectral and MAP estimators are equivalent whenever MAP succeeds in recovering the true community assignment, up to the global label flip.Source: §4.3.1 · p. 43
• Entrywise spectral analysis shows that the eigenvector remains correctly signed even when uniform coordinate-wise closeness fails at the exact recovery threshold.The proof approximates ϕ by A¯ϕ/¯λ, whose coordinates stay on the correct side of zero, while the residual is O(1/√n log log n) and the signal is Ω(1/√n).Source: §4.3.1 · pp. 44–46

4.3.2 SDP algorithm

• SDP exact recovery follows from a dual certificate when the SBM Laplacian condition 2L_SBM + 11^t + I_n ⪰ 0 holds with positive second eigenvalue.The certificate uses Y = 2(D_in − D_out) + I_n; established the condition, while [Ban15] closed the remaining factor-of-2 gap and showed threshold achievement in the symmetric case.Source: §4.3.2 · p. 52
• For unbalanced communities, SDPs have not yet been shown to achieve the general Chernoff-Hellinger threshold, despite additional results for weak recovery and block-structured Ising models.Results for unbalanced communities were obtained in, while approaches the weak-recovery threshold in the two-community SSBM as expected degrees diverge.Source: §4.3.2 · p. 52

Weak recovery for two communities

• For any k ≥ 2, the conjectured efficient weak-recovery threshold is SNR > 1, the Kesten–Stigum threshold.The threshold is motivated by reconstruction on trees, and the two-community converse follows from the corresponding tree reduction.Source: Weak recovery for two communities · pp. 53–54
• For k ≥ 4, weak recovery is information-theoretically possible at some SNR strictly below 1, creating a gap from the efficient KS threshold [DKMZ11, MNS15].The conjecture distinguishes a second information-theoretic transition below KS for k ≥ 4 from a single threshold at k = 3 [DKMZ11].Source: Weak recovery for two communities · p. 53
• For k = 2, weak recovery is possible efficiently if and only if (a − b)^2 > 2(a + b), equivalently SNR > 1 [MNS15, Mas14].When SNR ≤ 1, the two-community SBM is contiguous to an Erdős–Rényi model and is not distinguishable.Source: Weak recovery for two communities · p. 54
• For balanced multi-community SBMs satisfying a suitable eigenvalue asymmetry condition, efficient algorithms achieve the KS threshold, while resolve achievability for k ≥ 3.The asymmetry condition requires the relevant eigenvalue μ_k to be simple.Source: Weak recovery for two communities · p. 54
• Standard adjacency and Laplacian spectral methods and SDPs fail to reach KS, whereas approximate belief propagation and robust graph operators do achieve it.Degree fluctuations disrupt standard spectral eigenvectors; trimming or shifting removes information without reaching KS, while SDPs favor most-likely rather than typical clusterings.Source: Weak recovery for two communities · p. 54

Regular-tree broadcasting

• The broadcasting problem sends a uniformly random root bit through independently noisy branches and asks whether the leaf bits permit better-than-chance root inference at large depth.This replaces exact recovery with a probability bounded above 1/2 and formalizes weak recovery through conditional expectation or mutual information.Source: §5.1 · p. 55
• Weak recovery is solvable on a regular tree if and only if c(1−2ε)^2 > 1, the Kesten–Stigum threshold.Equivalently, the leaf observations retain nonzero asymptotic mutual information about the root, while below threshold that information vanishes.Source: §5.1 · pp. 55–57

Threshold scope and limitations

• The KS threshold is sharp for census reconstruction in symmetric binary broadcasting, but need not be sharp for reconstruction with nonbinary labels such as the multicolor Potts model.The subadditivity argument also extends through χ² mutual information, which recovers the same threshold for binary inputs.Source: §5.1 · pp. 56, 58

Regular-tree broadcasting

• Above threshold, the generation imbalance has separated conditional distributions, enabling root testing with error 1/2−Ω(1); below threshold, subadditivity forces information loss.The proof uses first- and second-moment calculations for the signed generation imbalance, while the converse uses mutual-information subadditivity among leaves.Source: §5.1 · pp. 56–58

Galton–Watson trees

• SBM neighborhoods are coupled to Galton–Watson trees, and for broad offspring distributions establishes a necessary-and-sufficient criterion involving c(1−2ε)^2; Poisson offspring is the relevant case.The Galton–Watson formulation conditions recovery on the realized tree and identifies the Poisson(c) model as particularly important for SBM applications.Source: §5.1 · pp. 58–59

Extensions

• Robust reconstruction remains possible under sufficiently noisy leaf observations at the KS threshold.Here the leaves are not observed exactly but are independently corrupted by additional noise.Source: §5.1 · p. 59

5.2 The information-theoretic threshold

• Weak recovery is solvable, efficiently, if and only if (a −b)^2 > 2(a + b).Source: §5.2 · p. 59

5.2.1 Converse

• The converse uses [MNS15] to couple SBM neighborhoods with broadcasting on Poisson((a + b)/2) Galton–Watson trees and control the weak effect of non-edges.Tree coupling is valid to logarithmic depth before neighborhood collisions become likely, and non-edges induce only a slight same-community repulsion.Source: §5.2.1 · pp. 59–60
• Below the threshold, proves impossibility of weak recovery by reducing single-vertex inference to tree broadcasting, whose Kesten–Stigum condition is c(1 −2ε)^2 ≤ 0.The reduction extends beyond two symmetric communities, but tightness of the KS bound can fail for asymmetric or more numerous communities.Source: §5.2.1 · pp. 60–61

5.2.2 Achievability

• Naive amplification of a Θ(1/√n) random-guess bias cannot succeed at tree-like depths, because the required neighborhood size would exceed n.Going deeper leaves the tree-like regime and requires handling repeated vertices and loops, motivating nonbacktracking methods.Source: §5.2.2 · pp. 64–65
• The proposed information-theoretic achievability scheme graph-splits G, amplifies many random guesses on an above-KS subgraph, and tests them on the residue graph.The authors conjecture that a sufficiently large number of guesses yields a good amplified partition that is accepted before bad guesses.Source: §5.2.2 · p. 65

5.3 Achieving the threshold

• Nonbacktracking walks provide an efficient compromise between path counting and ordinary walk counting, avoiding repeated-edge effects that obscure community information.Most logarithmic-length nonbacktracking walks are paths, so replacing paths with nonbacktracking walks is expected to preserve accuracy while improving efficiency.Source: §5.3 · p. 66

5.3.1 Linearized BP and the nonbacktracking matrix

• Linearized belief propagation addresses full BP’s nonlinear, model-dependent analysis by approximating belief updates near the community prior.Non-edge evidence must also be incorporated at large depth, because otherwise small biases can grow until nearly all vertices receive the same label.Source: §5.3.1 · pp. 68–69
• If (a −b)2 > 2(a + b), a nonbacktracking-eigenvector algorithm solves weak recovery in the two-community SSBM.The construction extracts the second-largest eigenvector of the nonbacktracking matrix and thresholds aggregated edge entries at vertices.Source: §5.3.1 · p. 72
• Approximate belief propagation with higher-order backtrack avoidance achieves the weak-recovery threshold when m = 2 log(n)/ log(SNR) + ω(1).The spectral interpretation views linearized belief propagation as power iteration on an adjusted nonbacktracking operator.Source: §5.3.1 · pp. 71–72

5.3.2 Algorithms robustness and graph powering

• Nonbacktracking spectra mitigate degree-driven localization: above the KS threshold, the community-informative eigenvalue λ2 appears before √λ1, enabling weak recovery.Unlike adjacency powers, nonbacktracking powers prevent direct reversals that amplify high-degree vertices.Source: §5.3.2 · pp. 73–74
• In loopy graphs, direct nonbacktracking may remain insufficient, motivating r-nonbacktracking, graph powering, and other robustness alternatives.The geometric block model illustrates this limitation: nonbacktracking can concentrate output on a dense tangle, whereas graph powering produces the desired community partition.Source: §5.3.2 · pp. 74–76
• SDPs solve weak recovery when (a−b)2/(2(a+b)) > 1+δ(a, b), with δ(a, b) →0 as (a+b) →∞.Thus, in the two-community SSBM, SDPs approach the weak-recovery threshold arbitrarily closely as expected degrees diverge.Source: §5.3.2 · pp. 76–77
• SDPs are robust to monotone adversaries that add within-community edges and remove across-community edges, unlike nonbacktracking spectral methods vulnerable to localized clique eigenvectors.However, SDPs perform poorly in some very sparse regimes and are impractical on large graphs.Source: §5.3.2 · p. 77
• Normalized Laplacian methods improve robustness to high-degree vertices but can overcorrect degrees, causing peripheral low-degree regions to dominate and preventing weak recovery in general.In the illustrated sparse SBM above the KS threshold, the methods isolate a small tail rather than recover the communities; the authors conjecture neither reaches the weak-recovery threshold generally.Source: §5.3.2 · pp. 77–78, Figure 5.7 · p. 78
• Graph powering adds edges between vertices within distance r, and deep cuts make cut-based inference more Bayes-like by incorporating feedback from vertices at greater depths.This contrasts with standard cuts that approximate MAP-style min-cuts; in the example, a 2-deep cut assigns the vertex to community 2 rather than community 1.Source: §5.3.2 · pp. 78–80
• Powering homogenizes high- and low-density regions, and choosing r below the graph diameter but larger than log log(n), such as r = ⌊log(n)⌋, enables vanilla spectral algorithms to achieve the weak-recovery threshold.Powers that are too small may not help, whereas powers at least the diameter produce a complete graph and destroy useful information.Source: §5.3.2 · p. 80
• The powering nonlinearity is more robust to cliques and dense tangles than path-counting operators, but powering densifies graphs and may require normalization, sparsification, or leaf and path peeling.The nonlinearity 1(· ≥1) flattens large entries, while sparsification reduces the resulting density without canceling powering’s edge-completion effect.Source: §5.3.2 · pp. 80–81

Partial recovery for two communities

• The section discusses various results for partial recovery.Source: Partial recovery for two communities · p. 82

Threshold

• Almost exact recovery is solvable efficiently in the two-community SBM if and only if the condition stated in Theorem 21 holds.The result first appeared in and was also shown in [MNS14].Source: §6.1 · p. 82

Boosting weak recovery

• Graph-splitting boosts weak recovery by applying it to k=⌊log(n)⌋ subgraphs, whose increased signal places them largely above the Kesten–Stigum threshold.A vote across the resulting clusterings classifies vertex pairs with probability 1−o(1), because sparse graph splitting provides approximate independence.Source: §6.1 · pp. 82–83

Sphere comparison

• Sphere comparison directly tests whether vertices share a community by counting cross-edges between their graph spheres, with graph splitting separating work and bridge graphs.Diverging degrees permit sphere depths below the diameter, and Figure 6.1 states that a careful unbalanced choice needs 4 log n/log d depth.Source: §6.1 · pp. 83–84, Figure 6.1 · p. 85

Agnostic statistics

• For r+r′ odd, the sign-invariant statistic is positive for same-community pairs and negative otherwise, regardless of the specific values of a and b.This yields an agnostic partial-recovery algorithm, and a variant for general SBMs achieves almost exact recovery under Theorem 21’s conditions.Source: §6.1 · p. 84

Recovery requirements

• Almost exact recovery can be refined to allow a prescribed number s(n) of errors; logarithmically small error budgets are treated in [YP15], while linear error budgets require later methods.The linear case corresponds to allowing a constant fraction of errors.Source: §6.1 · pp. 84–85

• Partial recovery allows a constant fraction of misclassified vertices, unlike the vanishing-error setting studied previously.Source: §6.2 · p. 85
• Finite-SNR partial recovery occurs either at constant degrees or when diverging degrees make the SNR numerator and denominator scale proportionally.Source: §6.2 · p. 85
• The central goal is the optimal tradeoff between SNR and misclassification fraction, MMSE, or mutual information, including graph-compression applications.Source: §6.2 · p. 86
• At large SNR, established bounds give error rates of C exp(−cSNR), including C exp{−SNR/2} for suitable symmetric spectral and minimax settings.Source: §6.2 · p. 86
• The optimal recoverable fraction is known for two symmetric communities with constant degrees and sufficiently large SNR, while arbitrary finite-SNR optimality remains open.Source: §6.2 · p. 86

6.3 Mutual Information-SNR tradeoff

• In the finite-SNR, diverging-degree regime, the two-community SBM is essentially equivalent to a block-structured spiked Wigner model, extending sparse-PCA comparisons.Mutual information is used to compare the models.Source: §6.3 · pp. 86–87
• Theorem 22 [DAM15] gives a single-letter characterization of normalized SBM MMSE and mutual information using an effective Gaussian scalar channel.The channel uses a uniform binary signal and standard Gaussian noise, with corresponding mmse(γ) and I(γ).Source: §6.3 · p. 87
• Weak recovery is unsolvable when λ ≤ 1 and solvable when λ > 1, so normalized MMSE becomes nontrivial exactly above the SNR threshold one [DAM15].This extends weak-recovery results to finite SNR with diverging degrees.Source: §6.3 · p. 88
• The asymptotic mutual information per vertex is bounded by both λ/4 and log 2, as shown for the symmetric two-community SBM.The figure plots the asymptotic mutual information against λ and displays both bounds as dashed lines.Source: Figure 6.2 · p. 89

6.4 Proof technique and connections to spiked Wigner models

• Theorem 23 [DAM15] formalizes SBM equivalence to the spiked Wigner observation λ/n XX^t + Z under converging SNR and diverging expected degree.The proof obtains Theorem 22 through boundary conditions, I-MMSE, AMP estimates, and density evolution; a noisy genie breaks AMP’s symmetry and is later removed.Source: §6.4 · pp. 89–90

6.5 Partial recovery for constant degrees

• For constant degrees, the optimal agreement at finite and arbitrary SNR remains open, although high-SNR recovery is characterized via broadcasting on trees [MNS13].The tree reduction gives an upper bound on graph agreement and motivates the high-SNR characterization.Source: §6.5 · p. 91
• When SNR > C, graph and tree optimal agreements coincide and the normalized agreement is efficiently achievable by a belief-propagation variant [MNS13].The construction uses a two-round strategy: first obtain nontrivial reconstruction above the KS threshold, then refine it with shorter-depth BP.Source: §6.5 · p. 91

The general SBM

• The threshold applies to general SBMs with arbitrary relative community sizes and arbitrary intercommunity connectivity rates, under W scaling as log(n)Q/n with positive Q entries.The model permits unequal communities and unrestricted connectivity patterns, while the theorem considers the logarithmic-degree regime.Source: The general SBM · p. 93, §7.1 · p. 93

7.1 Exact recovery and CH-divergence

• Exact recovery in SBM(n,p,log(n)Q/n) is efficiently solvable when I+(p,Q)≥1 and impossible when I+(p,Q)<1, where I+ is the minimum CH-divergence.At I+(p,Q)=1, solvability requires a stated componentwise condition on columns of diag(p)Q; with nonzero Q entries, the threshold is inclusive.Source: §7.1 · p. 93, §7.1.1 · p. 96
• In the symmetric SBM, the CH-divergence maximizes at t=1/2 and reduces to the Hellinger divergence, recovering the corresponding two-community threshold expression.The supplied passage identifies this as matching the expression from Theorem 3 for two symmetric communities.Source: §7.1 · pp. 93–94
• The CH-divergence D+ is an f-divergence that interpolates Hellinger divergence at t=1/2 and governs whether community profiles are sufficiently distinguishable for exact recovery.Its operational role parallels KL-divergence in channel coding: sufficiently different profiles permit separation of communities.Source: §7.1 · p. 94

7.1.1 Converse

• The converse reveals all other labels and analyzes component-MAP errors; weak dependence among vertex errors makes a local error probability ω(1/n) force global recovery failure.The CH threshold emerges from moderate-deviation behavior of the single-vertex error probability.Source: §7.1.1 · pp. 95–96

7.1.2 Achievability

• Achievability splits the graph, obtains an almost exact clustering from one sub-logarithmic-degree part, and applies independent-like local cleanup on the remaining logarithmic-degree graph.Graph-splitting controls dependencies between the preliminary clustering and cleanup graph, while the cleanup phase performs separate computations for each vertex.Source: §7.1.2 · pp. 97–98
• Almost exact recovery is efficiently solvable in SBM(n,p,ω(1)Q/n), and therefore yields efficient exact recovery at I+(p,Q)>1 through the two-round reduction.The cleanup threshold is determined by whether the component-MAP error is o(1/n), while ω(1/n) makes exact recovery impossible.Source: §7.1.2 · pp. 98, 100

7.2 Weak recovery and generalized KS threshold

• For symmetric SBMs, weak recovery is conjectured to be efficiently possible if and only if SNR > 1, whereas information-theoretic recovery can occur below 1 when k ≥4 [DKMZ11, MNS15].The conjecture distinguishes the computational KS threshold from a lower information-theoretic threshold for sufficiently many communities.Source: §7.2 · p. 101
• For arbitrary general SBM parameters, weak recovery is efficiently solvable whenever SNR > 1, establishing the achievability side of the generalized KS threshold.Under an additional balanced-community and simple-eigenvalue condition, the same threshold was previously achieved efficiently [BLM15].Source: §7.2 · p. 101
• The efficient procedures achieving the KS threshold use nonbacktracking spectral methods or approximate acyclic belief propagation, equivalent to power iteration on a regularized nonbacktracking matrix [AS17].The nonbacktracking approach extracts the second eigenvector, while ABP implements the corresponding power iteration.Source: §7.2 · p. 102
• The KS characterization requires normalized weak-recovery agreement; without normalization, the analogous max-detection criterion can fail even when SNR > 1.The normalization accounts for unequal community sizes in the recovery agreement.Source: §7.2 · p. 102

7.3 Partial recovery

• Sphere-comparison achieves partial-recovery accuracy 1 − e^−Ω(c) for SBM(n, p, cQ/n) at sufficiently large c when Q has no two equal rows [AS15b].The theorem applies to any k ∈ Z and p ∈ (0, 1)^k, with an error term ϵ(c) = O(1/log(c)).Source: §7.3 · p. 102
• Tight finite-SNR expressions for partial recovery in the general SBM remain open, apart from results requiring the assortative regime [CKPZ16].Related results are cited in [GMZZ15] [YP14a].Source: §7.3 · p. 102

gap

• The information-computation gap occurs when k is larger than 4, and an information-theoretic bound shows that this gap can grow rapidly with the number of communities.The bound samples a uniformly random typical clustering and can be sharpened using posterior mutual information, total variation, KL divergence, or contiguity arguments.Source: gap · p. 103

8.1 Crossing KS: typicality

• The information-theoretic threshold is much less restrictive than the KS threshold: for a = 0, weak recovery is solvable when b > c k log k + o_k(1), c ∈ [1, 2], versus b > k(k−1).Source: §8.1 · p. 104
• The resulting threshold interpolates the giant-component limit at b = 0: weak recovery is solvable when a > a_k(b), with a_k(0) = k, and a_k(b) is conjectured correct to first order for small b.The bound also gives b > 2k log k / ((k−1) log k) in SBM(n, k, 0, b), as displayed in Corollary 7.Source: §8.1 · p. 105
• [BM16, BMNN16] obtain matching information-theoretic upper and lower bounds in the large-k regime when (a − b)/d = O(1), using contiguity and second-moment estimates.The lower bound compares the SBM with an Erdős–Rényi graph of matching expected degree; contiguity rules out weak recovery because clustering would distinguish the two models.Source: §8.1 · p. 106

8.2 Nature of the gap

• In the KS–information-theoretic gap, nontrivial BP fixed points exist but have exponentially small basins of attraction, so typical initializations converge to noisy trivial solutions.Above KS the uniform fixed point is unstable, whereas below the information-theoretic threshold nontrivial fixed points disappear; reaching them in the gap is believed to require exponentially many initializations.Source: §8.2 · p. 107
• The gap also appears locally in ABP because nonlinear terms behave differently for k = 3 and k = 4, making its structure an open research problem.The difference is attributed to the loss of a diminishing-return property in the approximation underlying ABP.Source: §8.2 · p. 107

8.3 Proof technique for crossing KS

• The crossing-KS proof bounds the probability that exponentially many bad, nearly uninformative clusterings are typical, using careful Binomial tail estimates and a union bound.A bad balanced clustering splits each true community across the k inferred communities, so its edge statistics must undergo a rare deviation; derives the needed bounds.Source: §8.3 · pp. 108–109
• The basic union bound crosses KS for k ≥5 in symmetric communities and k ≥2 in asymmetric ones, but is loose at b = 0, requiring a > 2k instead of the achievable a > k.The refinement is needed because separating the two giant components already solves weak recovery for a > k in SBM(n, k, a, 0).Source: §8.3 · p. 109
• Topology-aware typical-set counting fixes this looseness by constructing typical labelings on isolated trees, planted trees, and unsaturated vertices, yielding the giant-component bound at b = 0 and crossing at k = 4.Tree labels follow a k-ary symmetric channel, with planted-tree roots frozen to their true labels; unsaturated vertices can be swapped without changing typicality.Source: §8.3 · pp. 109–110

Other block models

• SBM extensions include labelled edges, degree corrections, overlapping memberships, metric or geometric labels, censored observations, inhomogeneous random graphs, and graphons, covering edge labels, degree heterogeneity, mixed memberships, geometric connectivity, and continuous latent labels.Source: Other block models · pp. 111–113
• Geometric block models combine abstract communities with metric labels, while hybrid SBM–GBM models address both transitive short loops and small-world abstract edges.Graph powering is presented as more robust than basic spectral methods and belief propagation when geometric models contain many short loops.Source: Other block models · pp. 111–112

Concluding remarks and open problems

• Graphical channels generalize these models by assigning vertex inputs and edge outputs through a kernel, with information governed by observation-graph richness and kernel noise.The framework includes hypergraphs and conditional random fields.Source: Concluding remarks and open problems · p. 115
• The survey shows efficient CH-threshold exact recovery and KS-threshold weak recovery for fixed community counts, while the KS threshold need not be information-theoretically optimal.It also gives partial results on optimal SNR–distortion tradeoffs [CLM16].Source: Concluding remarks and open problems · pp. 115–116
• Open problems include exact recovery with many sublinear communities, partial-recovery tradeoffs at constant degree, sparse-SBM parameter learning, and finite-size scaling laws.The assortative constant-degree mutual-information limit remains open, as do larger community counts and optimal error exponents [CKPZ16].Source: Concluding remarks and open problems · p. 116, • The information-computation gap · p. 117

• The information-computation gap:

• The information-computation gap remains unresolved for weak recovery with k ≥3 at arbitrary constant degrees and for proving KS computational optimality under the stated sparse-SBM condition.The conjecture asserts no polynomial-time weak-recovery algorithm when λ2^2 < λ1 for SBM(n, p, Q/n).Source: • The information-computation gap · pp. 116–117
• Further directions ask whether thresholds extend to labelled, corrected, overlapping, graphon, geometric, and other graphical-channel models, and how robust they are to perturbations or adversaries.The survey also proposes semi-supervised and dynamical extensions, including networks with revealed labels or observations across time [HS17] [BCLS17].Source: • The information-computation gap · p. 117