Community Detection and Stochastic Block Models

Emmanuel Abbe

Source-linked AI summary

Community Detection and Stochastic Block Models

Emmanuel Abbe

arXiv:1703.10146v3Mar 29, 2017math.PRcs.CCcs.ITcs.SIstat.ML

TL;DR

The monograph studies the fundamental limits of community detection in stochastic block models across exact, partial, and weak recovery. It synthesizes information-theoretic and computational thresholds with algorithms designed to approach them, reporting sharp recovery transitions alongside unresolved gaps and scope boundaries.

Problem
Community detection requires determining when planted communities can be recovered under different accuracy requirements and whether information-theoretic limits are efficiently achievable.
Method
The monograph surveys and derives threshold results and algorithms including graph splitting, semidefinite programming, belief propagation, spectral methods, and graph powering.
Results
Exact recovery reaches the Chernoff–Hellinger threshold, weak recovery reaches the Kesten–Stigum threshold efficiently, and partial recovery has an optimal SNR–mutual-information tradeoff, while computational gaps can remain.
Takeaways & Limitations
Fundamental limits provide benchmarks for developing algorithms that succeed in challenging community-detection regimes and for separating model limitations from algorithmic limitations.
Takeaways & Limitations
The Kesten–Stigum conjecture is not generally correct under the max-detection criterion for general SBMs, and open questions remain for adversarial and geometric block models.

Abstract

from arXiv · show

The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatorial statistics and more generally data science. This monograph surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational tradeoffs, and for various recovery requirements such as exact, partial and weak recovery. The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal SNR-mutual information tradeoff for partial recovery, and the gap between information-theoretic and computational thresholds. The monograph gives a principled derivation of the main algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, (linearized) belief propagation, classical/nonbacktracking spectral methods and graph powering. Extensions to other block models, such as geometric block models, and a few open problems are also discussed.

Introduction

The monograph presents the SBM as a canonical framework for studying community detection and its fundamental information-theoretic and computational limits. It surveys how these limits guide algorithms, while illustrating both successful recovery and model- or algorithm-dependent failures on real data.

Community detection, clustering and block models: Community detection seeks to identify groups of vertices that connect densely or behave similarly, making it relevant across many networked data applications.The monograph lists applications including social networks, biological interactions, recommendation systems, and image segmentation.
Community detection, clustering and block models: The monograph addresses whether communities are meaningful, whether they can be recovered fully or partially, and how algorithmic performance should be benchmarked.These questions motivate the focus on block models and fundamental limits.
Community detection, clustering and block models: The SBM models vertices assigned to communities whose pairwise connection probabilities depend on their labels.It provides a generative ground truth for studying community detection formally.
Fundamental limits: information and computation: Fundamental limits specify necessary and sufficient conditions for recovery, either without computational constraints or for polynomial-time algorithms.The distinction separates information-theoretic limits from computational limits.
Fundamental limits: information and computation: The surveyed results connect recovery thresholds to algorithm design, while information-theoretic limits may remain unattainable by efficient algorithms.The monograph discusses sphere comparisons, linearized belief propagation, and nonbacktracking spectral methods, alongside information-computation gaps.
An example on real data: For the political-blog data, fitted SBM parameters place the network above both weak-recovery and exact-recovery thresholds, although degree variation can cause a specific SBM-based algorithm to fail.The reported values are λ2^2/λ1 ≈18 for weak recovery and J(p,Q) ≈2 for exact recovery.
Historical overview of the recent developments: The Kesten–Stigum conjecture is not accurate for general SBMs when detection is defined by improving over the largest-community baseline.The monograph notes that this max-detection formulation is too strong in some general SBMs.

2.2 The symmetric SBM

The symmetric SBM specializes community assignments and connection probabilities to balanced, exchangeable communities. The section distinguishes recovery goals and explains why normalized agreement is needed for meaningful weak-recovery definitions, especially beyond the symmetric case.

The symmetric SBM: In the symmetric SBM, communities have a uniform prior and identical within-community and across-community connection probabilities.The strictly balanced formulation fixes each community size at n/k when n is a multiple of k.
Recovery requirements: Community detection aims to recover vertex labels from the observed graph, with recovery requirements defined asymptotically with high probability.The standard setup assumes known SBM parameters when designing algorithms, except in Section 2.5.
Recovery requirements: Partial recovery permits a constant fraction of errors while requiring normalized agreement α greater than 1/k.Exact, almost exact, partial, and weak recovery differ by the allowed fraction of misclassified vertices.
Weak recovery: Weak recovery in the symmetric SBM requires accuracy at least 1/k + ε with high probability for some ε > 0.This improves over the accuracy of an independent random labeling, which is 1/k.
Weak recovery: For unequal community sizes, max-detection can be misleading because a trivial assignment to the largest community may achieve high accuracy.Normalized agreement addresses this issue by requiring separation reflected in community-weighted performance.
Weak recovery: A two-set partition definition of weak recovery requires vertices from different communities to have different probabilities of being assigned to either set.In symmetric SBMs, this definition implies max-detection after padding the output with k − 2 empty sets.
Weak recovery: The equivalence between this weak-recovery definition and max-detection extends to some weakly symmetric SBMs but not all.The section also notes that vanishing conditional mutual information between arbitrary vertex labels rules out weak recovery.

2.5 Learning the model

Model learning is easier in some regimes than community recovery, but the general sparse SBM remains technically delicate. Diverging-degree methods enable efficient recovery-based estimation, while constant-degree estimation uses cycle and nonbacktracking statistics.

Diverging degree regime: In the diverging-degree regime, agnostic sphere comparison detects communities with accuracy at least 1−e^−Ω(α) in O(n^{1+ϵ(α)}) time.Here ϵ(α)=O(1/log(c)) for sufficiently large α.
Diverging degree regime: The number of communities, community prior, and connectivity matrix can be consistently estimated in quasi-linear time when degrees diverge.The guarantee applies to SBM(n,p,ω(1)Q/n).
Constant degree regime: In the constant-degree regime, tight parameter estimation uses cycle counts approximated by nonbacktracking walks, although full cluster recovery is impossible.An alternative Bethe-free-energy expectation-maximization method is proposed without rigorous analysis.
Constant degree regime: For the two-community symmetric SBM above the weak-recovery threshold, average degree and slowly growing cycle counts consistently estimate a and b in polynomial time.The estimator uses m_n=⌊log^{1/4}(n)⌋ cycles.
General SBM: General SBM estimation requires stabilizing cycle statistics to extract eigenvalues of PQ and then using weak-recovery methods to refine p and Q.The monograph describes this problem as non-trivial.
Recovery and algorithms: Weak recovery can be solvable even when block MAP fails, while spectral and SDP methods have different tradeoffs across recovery regimes.SDPs work well for exact recovery but are suboptimal for weak recovery; spectral methods can achieve optimality with quasi-linear complexity.

3.3 The bit MAP estimator

The block MAP estimator motivates spectral relaxations and belief propagation, but its performance depends on the recovery task. Belief propagation estimates vertex marginals through locally tree-like neighborhoods, whereas vanilla spectral methods can fail in weak recovery despite working well for exact recovery.

Weak recovery: Weak recovery requires maximizing expected agreement through the posterior marginal P(X_v=·|G), rather than relying only on a global MAP partition.In the symmetric SBM, the marginal is uniform, motivating a symmetry-breaking device.
Belief propagation: Belief propagation recursively estimates vertex-label marginals by combining neighboring messages under an approximate local-independence assumption.The assumption is motivated by the sparse SBM’s locally tree-like structure.
Belief propagation: Linearizing belief propagation yields an analyzable version that leads to a spectral method based on a new operator.The ordinary algorithm is efficient, but convergence to the true distribution remains open.
Exact recovery: Exact recovery in the symmetric two-community model occurs when the square-root separation condition exceeds its threshold, with connectivity required but insufficient.The additional over-sampling factor distinguishes exact recovery from mere connectivity.

4.1 Warm up: genie-aided hypothesis test

The genie-aided test reduces exact recovery to classifying one unknown vertex when all other labels are revealed. Its error probability identifies the threshold, and bad vertices or swaps provide the corresponding impossibility mechanism.

Genie-aided test: With all other labels revealed, classifying one vertex reduces to testing whether its cross-community edge count follows Bin(n/2,q_in) or Bin(n/2,q_out).The MAP test compares the two hypotheses under equal prior probabilities.
Genie-aided test: The single-vertex error probability is determined entirely by the numbers of edges from that vertex to the two communities.These counts are denoted N_1 and N_2.
Threshold implication: If the genie-aided error probability is sublinear, all vertices can be classified correctly with high probability; if it is superlinear, exact recovery fails with high probability.This establishes the single-vertex test as the key exact-recovery threshold proxy.
Converse: Disconnected graphs already prevent exact recovery because disconnected components cannot be correctly labelled with probability tending to one.This supplies a necessary connectivity condition.
Converse: A bad pair of vertices makes exact recovery impossible because swapping their labels yields an alternative partition at least as likely as the planted one.The resulting probability of error is at least 1/2.
Converse: Bad vertices are identified when their within-community degree is no larger than their across-community degree minus one, and sufficiently likely bad vertices imply a bad pair.The argument uses approximate independence and a second-moment bound.
Sharpness: The sharp threshold is tight because one-vertex swaps dominate larger swaps, with the remainder bounded by the two-vertex error contribution.The monograph states that R=O(n^2P_e(1)).

4.3 Achieving the threshold

The section shows that vanilla spectral methods achieve exact recovery at the threshold by analyzing eigenvector behavior more sharply than global norm or entrywise closeness alone. Centering, perturbation bounds, and sign alignment connect the spectral estimator to the planted communities.

Spectral algorithm: Centering removes the top expected eigenvector, making the relevant community signal appear in the top eigenvector of the centered adjacency matrix.The centered matrix has rank-one expectation, while the uncentered formulation uses the second eigenvector.
Achieving exact recovery: The centered formulation requires knowledge of p + q, although estimating this quantity or using the uncentered second eigenvector avoids that requirement.The uncentered approach is analyzed separately as an alternative.
Spectral algorithm: The spectral algorithm outputs the signs of the second eigenvector and solves exact recovery at the stated threshold.The method relaxes min-bisection to an Euclidean constraint and rounds the second eigenvector.
Achieving exact recovery: Strong eigenvector alignment follows from perturbation analysis, but exact recovery requires controlling coordinatewise signs rather than only global alignment.Graph splitting can convert strong alignment into exact recovery, while sharper analysis proves direct sign recovery.
Achieving exact recovery: The eigenvector is approximated entrywise by A¯ϕ/¯λ, whose coordinates inherit the hypothesis-testing variables governing community-label errors.This approximation remains useful even when direct closeness to the population eigenvector is insufficient at the threshold.
Achieving exact recovery: An O(1/√n log log n) perturbation cannot cross the Ω(1/√n) signal margin, so the eigenvector signs remain correct with high probability.The argument allows large coordinate errors provided they stay on the correct side of zero.

Weak recovery for two communities

For two-community SBMs, weak recovery has an efficiently achievable Kesten–Stigum threshold, while larger symmetric models can exhibit an information-theoretic gap below it. Standard clustering methods may fail at this threshold, motivating robust spectral and belief-propagation methods.

Thresholds: SNR > 1 is the conjectured efficient threshold for weak recovery in symmetric SBMs with any number of communities.The conjecture also allows information-theoretic recovery below SNR 1 for some k ≥ 4.
Thresholds: Information-theoretic weak recovery can occur below SNR 1 for some models with k ≥ 4, creating a gap from the efficient threshold.The stated sub-KS possibility is not necessarily achieved in polynomial time.
Two communities: For two communities with constant expected degree, weak recovery is solvable efficiently if and only if (a − b)^2 > 2(a + b).This is the Kesten–Stigum threshold in the constant-degree two-community model.
Two communities: When the expected degrees diverge, weak recovery is solvable if and only if λ > 1 for λ = (a_n − b_n)^2/(2(a_n + b_n)).The result applies when a_n, b_n = ω(1) and the displayed ratio converges to λ.
Two communities: For two communities, detection is impossible at SNR ≤ 1 because the SBM is contiguous to an Erdős–Rényi model.This establishes indistinguishability rather than merely a failure of a particular algorithm.
Algorithms: Adjacency-based spectral methods, standard Laplacians, and SDPs can fail to reach the KS threshold, whereas approximate belief propagation and robust graph operators can achieve it.Degree fluctuations disrupt standard spectral eigenvectors, and trimming or shifting alone does not suffice.

5.1 Warm up: broadcasting on trees

The tree-reconstruction warm-up analyzes how information about a root bit propagates through noisy descendants. Its central conclusion is the KS transition: below the threshold information vanishes, while above it weak recovery is possible.

Broadcasting model: The tree problem broadcasts a root bit through independently noisy branches and asks whether the root can be inferred from distant leaves.Weak recovery is defined through persistent posterior advantage or mutual information at large depth.
Regular trees: When c(1 − 2ε)^2 ≤ 1, the root information is lost at large depth, including in the stronger sense captured by mutual information.The subcritical regime prevents reconstruction irrespective of the statistics used.
Regular trees: For a regular tree, weak recovery is solvable if and only if c(1 − 2ε)^2 > 1.This is the Kesten–Stigum threshold for constant degree c and flip probability ε.
Moment analysis: Above the threshold, the difference between correctly and incorrectly transmitted bits has total variation distance Ω(1), enabling root inference with error 1/2 − Ω(1).The moment calculation uses SNR = √c(1 − 2ε) and assumes SNR > 1.
Information inequalities: The subadditivity argument relies on binary labels and symmetric channels; it does not hold in general for non-binary labels or binary nonsymmetric noise.A degradation to a detached stringy tree supplies the needed inequality in the supported setting.
Galton–Watson trees: For Poisson offspring, the Galton–Watson broadcasting model has an analogous necessary-and-sufficient threshold for weak recovery.The SBM neighborhood is approximated by a Galton–Watson tree, making this model relevant to community detection.

5.2 The information-theoretic threshold

For the two-community sparse SBM, weak recovery is information-theoretically impossible at or below the Kesten–Stigum threshold, while above it efficient recovery is possible. The converse reduces local SBM neighborhoods to tree broadcasting, whereas achievability must leave the tree-like regime and use deeper, nonbacktracking or graph-splitting constructions.

(a −b)2 ≤2(a + b) is the information-theoretic impossibility threshold for weak recovery in the symmetric two-community SBM.
Converse: The converse reveals boundary labels in a small neighborhood, reducing single-vertex recovery to broadcasting on a Galton–Watson tree.The reduction uses approximate conditional independence and the coupling between SBM neighborhoods and tree broadcasting.
The threshold reduction extends to asymmetric and multiple-community models, but tightness of the Kesten–Stigum bound can fail and gap phenomena may arise.
Converse: Below the Kesten–Stigum threshold, tree broadcasting cannot weakly recover the root, so weak recovery in the SBM is also impossible.
Achievability: In the tree-like regime, neighborhood majority improves accuracy above the threshold but requires more than n vertices to amplify a 1/√n bias to constant accuracy.Thus, tree-like neighborhoods alone cannot achieve weak recovery in the SBM.
Achievability: Achievability therefore goes beyond tree-like neighborhoods, where loops require counting nonbacktracking walks and create additional complications.The monograph discusses this approach as an efficient algorithmic route.
Achievability: A conjectured graph-splitting strategy seeks a good initial guess and tests its amplification on a residue graph before bad guesses are accepted.

5.3 Achieving the threshold

The monograph develops algorithms that reach weak-recovery limits by replacing ordinary walks with nonbacktracking or higher-order walk constructions, linearized belief propagation, spectral methods, SDPs, and graph powering. These methods address failures caused by backtracking, cycles, high-degree localization, and model dependence.

Nonbacktracking constructions: Ordinary walk counts are confounded by repeated vertices and edges, making their endpoint differences difficult to predict from a vertex’s community.Nonbacktracking walks provide an efficient compromise because most logarithmic-length nonbacktracking walks are paths.
Linearized belief propagation: Linearized belief propagation approximates Bayesian updates around the prior to obtain a simpler message-passing algorithm.The linearization focuses on the first-order behavior of beliefs that remain close to prior probabilities.
Nonbacktracking spectral methods: The nonbacktracking spectral method does not require the graph parameters and uses the second eigenvector to perform weak recovery.Its threshold condition for two symmetric communities is (a−b)^2 > 2(a+b).
Higher-order nonbacktracking: Higher-order nonbacktracking achieves the weak-recovery threshold when m = 2 log(n)/log(SNR) + ω(1).The extension prohibits short loops rather than only direct backtracks.
Semidefinite programming: SDPs approach the weak-recovery threshold at large degrees and offer robustness to certain monotone adversaries that can disrupt nonbacktracking spectral methods.Such adversaries may add within-cluster edges or remove across-cluster edges, while a planted clique can create a localized nonbacktracking eigenvector.
Graph powering and robustness: Graph powering reduces localization from high-degree vertices because its non-linearity flattens large-magnitude entries, while normalized spectral methods can fail in low-degree regions.The powered graph uses powers larger than Ω(log log(n)) but below half the diameter, and its spectrum separates bulk, localized, community, and Perron-Frobenius eigenvalues.

Partial recovery for two communities

This section introduces partial recovery, the regime in which a constant fraction of vertices may be misclassified.

Partial recovery refers to a constant fraction of misclassified vertices.

6.1 Almost Exact Recovery

Almost exact recovery permits a vanishing error fraction and can be achieved efficiently through graph splitting, sphere comparisons, and related pairwise statistics. These methods use neighborhood overlap or bridge edges to infer whether vertex pairs share a community.

Recovery threshold: Almost exact recovery is solvable efficiently exactly under the condition stated by Theorem 21.The supplied passage introduces the theorem’s if-and-only-if characterization but does not include its displayed threshold.
Boosting weak recovery with graph-splitting: Graph splitting repeatedly creates subgraphs whose weak-recovery outputs can be combined by voting over vertex pairs.Using k = floor(log(n)/log(SNR)) subgraphs makes each split graph largely above the KS threshold.
Sphere comparison: Sphere comparison classifies vertex pairs using edges between neighborhoods grown in a work-graph and a bridge-graph.Graph splitting supplies approximate independence between the spheres and the crossing-edge statistic.
Scope and limitations: The approach is simpler with diverging degrees because spheres can be compared at depths below the graph diameter, whereas linear error fractions remain more challenging.
Sphere comparison: Neighborhood spheres contain about d^r vertices, with approximately ((a−b)/2)^r more vertices from a vertex’s own community than from each other community before the graph becomes saturated.Direct sphere intersections are dependent, motivating the bridge-edge construction.
Parameter-agnostic statistics: The sign-invariant statistic tends to be positive for same-community pairs and negative for different-community pairs when r + r′ is odd, without requiring the values of a and b.A general-SBM variant solves almost exact recovery efficiently under Theorem 21’s conditions.

6.2 Partial recovery at finite SNR

Finite-SNR partial recovery asks how the signal-to-noise ratio controls the achievable error fraction, MMSE, or mutual information. The section distinguishes constant-degree and proportionally scaling diverging-degree regimes and reviews known bounds and optimality results.

Definition and regimes: Partial recovery concerns a constant fraction of misclassified vertices, unlike almost exact recovery, where the error fraction vanishes.
Definition and regimes: Finite-SNR partial recovery occurs when the SNR remains finite in either the constant-degree regime or a diverging-degree regime with proportionally scaling numerator and denominator.
Optimal tradeoffs: The main objective is the optimal tradeoff between SNR and reconstruction error, MMSE, or mutual information.The mutual-information formulation is connected to graph compression.
Known bounds: Large-SNR upper bounds on the incorrectly recovered fraction have the form C exp(−cSNR), with a two-community spectral result achieving C exp(−SNR/2) asymptotically.
Known bounds: The optimal recovered fraction is known for two symmetric communities at constant degree and sufficiently large SNR, but remains open at arbitrary finite SNR.The result connects the problem to broadcasting on trees.

6.3 Mutual Information-SNR tradeoff

In the finite-SNR, diverging-degree regime, the SBM is equivalent to a spiked Wigner model, enabling an exact characterization of mutual information and MMSE through an effective Gaussian channel. Weak recovery becomes possible precisely above λ = 1, while optimal agreement is characterized in several regimes.

Model equivalence: The SBM with finite SNR and diverging degrees is essentially equivalent to a spiked Wigner model with block-structured signal.This equivalence supplies the Gaussian framework used to analyze mutual information and MMSE.
Mutual information characterization: Theorem 22 characterizes normalized MMSE and mutual information through the largest non-negative solution γ∗(λ) of a fixed-point equation.The effective scalar channel has a binary input X0 and Gaussian noise Z0.
Weak-recovery transition: λ > 1 is the threshold for non-trivial normalized MMSE and mutual information, whereas λ ≤ 1 makes weak recovery unsolvable.Equivalently, normalized MMSE remains 1 for λ ≤ 1 and becomes strictly smaller than 1 for λ > 1.
Mutual-information bounds: The mutual-information curve is bounded by limn→∞ I(X; G)/n ≤ λ/4 and I(X; G)/n ≤ log 2.These bounds apply to the asymptotic mutual information per vertex in the symmetric two-community SBM.
Open problem: Determining optimal agreement at finite arbitrary SNR with constant degrees remains an open problem.The problem is settled only for sufficiently high SNR in the cited result.
Partial recovery: For sufficiently large SNR, optimal agreement equals the broadcasting-on-trees inference probability and is efficiently achievable.Theorem 24 states this equality for SNR > C, with a belief-propagation variant providing the efficient algorithm.

The general SBM

For general SBMs with arbitrary community sizes and connectivity rates, exact recovery is governed by a Chernoff-Hellinger divergence threshold. Two-round graph-splitting methods connect almost exact recovery to efficient exact recovery at this threshold.

The general SBM: The general SBM allows arbitrary community proportions and arbitrary connectivity rates between communities.The exact-recovery result considers the logarithmic-degree regime W = log(n)Q/n.
Exact-recovery threshold: Exact recovery is solvable efficiently when I+(p, Q) > 1 and impossible when I+(p, Q) < 1.Here I+(p, Q) is the minimum CH-divergence between distinct community profiles.
Threshold behavior: At I+(p, Q) = 1, exact recovery is solvable precisely under a support-separation condition on every pair of community profiles.The condition requires a component that is non-zero and different in both columns.
Converse and achievability: The CH-divergence threshold arises from the error exponent of a genie-aided single-vertex hypothesis test.The component error must be below order 1/n for all vertices to be recovered.
Computational implication: The second round has linear complexity because it performs independent local computations for each vertex.Thus efficient almost exact recovery suffices for an efficient overall exact-recovery algorithm.
Two-round algorithms: If almost exact recovery is solvable in SBM(n, p, ω(1)Q/n), then exact recovery is solvable in SBM(n, p, log(n)Q/n) when I+(p, Q) > 1.The two-round procedure first obtains a sufficiently accurate clustering and then locally reclassifies vertices.

7.2 Weak recovery and generalized KS threshold

The generalized Kesten–Stigum threshold characterizes efficient weak recovery through SNR > 1 for arbitrary SBMs, while information-theoretic recovery may extend below it in symmetric models with at least four communities.

Efficient weak recovery: For symmetric SBMs, the KS threshold is conjectured to be necessary and sufficient for efficient weak recovery.The conjecture concerns the normalized weak-recovery criterion rather than max-detection.
Information-computation gap: For k ≥ 4, information-theoretic weak recovery can be possible at some SNR strictly below 1.Thus the KS threshold need not equal the information-theoretic threshold.
Efficient weak recovery: SNR > 1 is sufficient for efficient weak recovery in general SBMs.This extends earlier results under eigenvalue and balance conditions to arbitrary community priors and connectivity matrices.
Algorithms: Nonbacktracking spectral methods and approximate acyclic belief propagation achieve efficient recovery above the KS threshold.The former extracts a leading nonbacktracking eigenvector, while the latter uses power iteration on a related operator.
Recovery criteria: The normalized weak-recovery definition is essential because max-detection can fail even when SNR > 1 in general SBMs.An asymmetric counterexample shows that max-detection may be too stringent.
Algorithms: Sphere-comparison detects communities with accuracy 1 − e^−Ω(c) and complexity O(n^(1+ε(c))) for sufficiently large signal scaling c.Here ε(c) = O(1/log(c)), and the method applies when the connectivity matrix has no two equal rows.

The information-computation

Information-theoretic methods can cross the KS threshold by sampling clusterings that are typical under the SBM, with topology-aware bounds tightening the resulting recovery regimes. The gap is especially pronounced as the number of communities grows, although the efficient converse remains unresolved.

Information-theoretic gap: For k ≥ 4, information-theoretic weak recovery is possible below the KS threshold.This establishes an information-computation gap in symmetric SBMs.
Typicality sampling: Typicality sampling uniformly selects a balanced clustering whose within- and across-cluster edge counts match the SBM expectations.The method uses the abundance or absence of such bad typical clusterings to derive information-theoretic bounds.
Topological refinement: When b = 0, weak recovery is information-theoretically solvable once a > k, matching the giant-component threshold.The recovery strategy separates the giant components and assigns the remaining small components randomly.
Extremal regimes: For a = 0, the information-theoretic threshold scales as k log k, far below the KS requirement b > k(k−1).The k log k scaling is reported as tight in the large-k regime.
Algorithmic perspective: The gap also reflects different belief-propagation behavior for k = 3 and k = 4, linked to the loss of a diminishing-return property.The monograph identifies understanding this phenomenon as an active research area.
Topological refinement: The topology-aware bound improves the crude union-bound regime, which requires a > 2k when b = 0 despite recovery being possible for a > k.The refinement accounts for the graph’s giant-component structure.

Other block models

The monograph surveys extensions of the SBM that add edge labels, degree variation, overlapping memberships, geometric structure, censored observations, graphon limits, and higher-order interactions. These variants broaden modeling scope while raising new questions about recovery thresholds and algorithms.

Model extensions: Degree-corrected, overlapping, and labelled SBMs extend the basic model by adding vertex degree parameters, mixed memberships, or edge information.These variants target heterogeneous degrees, overlapping communities, and weighted similarity relationships.
Geometric block models: Geometric block models assign vertices metric-space labels and make connectivity depend on distances as well as abstract community labels.The sphere-GBM uses points on a sphere and thresholded distances, with probabilities a or b according to community agreement.
Geometric versus abstract structure: Geometric models can produce many short loops, whereas the SBM captures abstract edges and small-world low-diameter connections more directly.Hybrid models superpose geometric and SBM structure to combine these properties.
Censored block models: Censored block models replace some non-edge information with observed edge labels and can be mathematically more convenient while behaving similarly to SBMs.The binary symmetric CBM specifies label accuracy conditional on an observed edge.
Graphons and broader models: Graphons generalize vertex labels to continuous spaces and provide limit objects preserving local and global properties of graph sequences.They are represented by measurable kernels on [0,1]^2.
Supported conclusions: The survey concludes that exact recovery reaches the CH threshold efficiently, while weak recovery reaches KS efficiently but may have a lower information-theoretic threshold.It also reports partial-recovery tradeoffs between distortion and SNR.
Open problems: Open problems include fundamental limits for richer models, adversarial perturbations, robust algorithms, and exact or weak recovery in geometric block models.These questions extend the threshold program beyond the basic SBM.