Source-linked AI summary
Exact Recovery in the Stochastic Block Model
Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall
TL;DR
The paper asks for the information-theoretic threshold for exact community recovery in the two-community stochastic block model and for an efficient algorithm attaining it. It proves a sharp threshold, develops an SDP relaxation that succeeds near it, and gives an efficient partial-recovery-plus-local-improvement method matching the threshold.
Problem
The paper addresses the missing sharp threshold and tight impossibility results for exact recovery, alongside guarantees of algorithmic optimality.
Method
The paper establishes the information-theoretic limit through maximum likelihood and develops an SDP relaxation plus a partial-recovery algorithm followed by local improvements.
Results
Exact recovery is possible with high probability when (α + β)/2 − √αβ > 1 and impossible when it is below 1; the efficient local-improvement method matches this threshold.
Takeaways & Limitations
The results identify the information-theoretic recovery boundary and show that an efficient algorithm can achieve it, while the SDP is proved successful under a slightly looser condition.
Takeaways & Limitations
The SDP analysis has an additional factor-2 gap from the optimal threshold, and whether the SDP or a spectral algorithm reaches the optimum remains open.
Abstract
from arXiv · showhide
The stochastic block model (SBM) with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behaviour. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability $p$ within clusters and $q$ across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower-bounds on the scaling of $|p-q|$ to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if $α=pn/\log(n)$ and $β=qn/\log(n)$ are constant (with $α>β$), recovering the communities with high probability is possible if $\frac{α+β}{2} - \sqrt{αβ}>1$ and impossible if $\frac{α+β}{2} - \sqrt{αβ}<1$. In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst-case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest it may achieve the threshold. An efficient algorithm which succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure.
1 Introduction
The paper frames community detection through the two-community stochastic block model and identifies exact recovery as an unresolved threshold problem. It establishes a sharp phase transition and develops efficient approaches aimed at reaching it.
- 1 Introduction: The stochastic block model assigns community labels and connects node pairs according to a probability matrix, enabling community assignments to be reconstructed from an unlabeled graph.The two-community symmetric case has equal-sized clusters with within-community probability p and across-community probability q.
- 1 Introduction: The planted bisection model G(n, p, q) contains two equal-sized clusters, with connection probabilities p within clusters and q across clusters.Recovery is defined up to a global label flip, so the partition—not the labels themselves—is recovered.
- 1 Introduction: Prior work largely sought lower bounds on |p-q| sufficient for efficient recovery, with the best reported bound remaining unimproved for more than a decade.The cited state of the art ensures recovery under a condition involving (p−q)/√p and log(n)/n.
- 1 Introduction: The sparse constant-degree regime permits partial recovery but not exact recovery because the graph is with high probability disconnected.This regime instead studies detection, meaning recovery of a proportion 1/2 + ε of vertices correctly for some ε > 0.
- 1 Introduction: The paper addresses whether exact recovery has a sharp phase transition, noting that tight impossibility results and optimality guarantees were missing.It states that the paper establishes a sharp phase transition, obtains a tight bound, and gives an efficient algorithm achieving it.
2 Related works
Related work has produced recovery bounds for the two-community stochastic block model across computer science, statistics, and machine learning. These works vary in the connectivity conditions and algorithms they analyze.
- 2 Related works: A substantial literature studies recovery in the two-community stochastic block model G(n, p, q).The cited work spans computer science, statistics, and machine learning.
- 2 Related works: Existing studies obtain bounds on connectivity parameters that ensure recovery for various algorithms.The passage presents the list as partial rather than exhaustive.
- 2 Related works: The literature covers multiple fields, including computer science, statistics, and machine learning.
3 Information theoretic perspective and main results
The paper frames exact recovery in the SBM as decoding over a structured memoryless channel, establishes an information-theoretic threshold, and develops efficient algorithms approaching or matching it.
- Information-theoretic perspective: The SBM can be viewed as a structured code over a memoryless channel, with community assignments as inputs and graph edges as outputs.The channel is memoryless but not time-homogeneous because p and q scale with n; its graph-derived code has rate 2/(n−1).
- Information-theoretic perspective: Maximum likelihood is information-theoretically optimal because uniform community assignments make MAP equivalent to ML.ML nevertheless reduces to minimum bisection, which is NP-hard in the worst case, so it establishes a benchmark rather than an efficient procedure.
- Main results: The exact-recovery threshold is (α+β)/2 − √αβ = 1 for p = α log(n)/n and q = β log(n)/n.ML fails below this threshold and succeeds above it with high probability.
- Main results: The threshold improves prior sufficient conditions such as (α−β)^2 > 64(α+β) and (α−β)^2 > 72(α+β).Those earlier results reached the correct n-scaling but not the correct dependence on α and β.
- Efficient algorithms: The proposed SDP relaxation succeeds with high probability under (α−β)^2 > 8(α+β)+8/3(α−β), while simulations suggest performance at the optimal threshold.A separate efficient partial-recovery plus local-improvement procedure has guarantees matching the information-theoretic threshold.
4 Additional related literature
The paper relates its recovery problem to the censored block model and notes parallel work obtaining a similar, somewhat more general threshold result.
- Censored block model: The censored block model recovers unknown binary labels from noisy edge observations and has matching bounds near ε = 1/2.Its efficient SDP algorithm is related to the SDP developed in this paper.
- Parallel work: A parallel study obtained a similar recovery result while allowing parameters a and b to depend on n, provided both remain Θ(1).The paper describes that result as slightly more general.
5 Information theoretic lower bound
The lower-bound analysis proves that below the threshold, maximum likelihood fails with probability bounded away from zero, so exact recovery is impossible for any algorithm.
- Proof strategy: The tail analysis uses estimates for sums of discrete random variables whose number of summands grows with n.Standard CLT, Chernoff, and Sanov estimates are described as insufficient in this slow-concentration regime.
- Model and regime: The model uses balanced binary labels and edge probabilities p = α log(n)/n within communities and q = β log(n)/n across communities.Edges are conditionally independent given the labels, with n even.
- Lower bound: If (α+β)/2 − √αβ < 1, ML fails with probability bounded away from zero.Equivalently, failure occurs when α+β < 2, or when (α−β)^2 < 4(α+β)−4 with α+β ≥ 2.
- Boundary case: When β = 0, recovery is possible if and only if the graph has no isolated nodes, with a sharp threshold at α = 2.The main analysis therefore focuses on α > β > 0.
6 Information theoretic upper bound
The upper-bound analysis shows that maximum likelihood exactly recovers the planted communities above the same threshold, completing the sharp information-theoretic characterization.
- Upper bound: If (α+β)/2 − √αβ > 1, ML exactly recovers the communities up to a global flip with high probability.Equivalently, α+β > 2 and (α−β)^2 > 4(α+β)−4.
- Boundary case: The β = 0 case follows from the Erdős-Rényi connectivity threshold, so the proof restricts the main argument to α > β > 0.This boundary case is treated separately from the positive-β regime.
- Proof strategy: The proof reduces ML failure to the existence of a balanced alternative partition with a cut no larger than the planted partition.A witness consists of equally sized subsets Aw ⊂ A and Bw ⊂ B satisfying the corresponding edge-count inequality.
7 Efficient algorithms
The paper develops two efficient exact-recovery approaches for the symmetric two-community SBM: an SDP relaxation of maximum likelihood and a partial-recovery algorithm followed by local improvements. The SDP is provably successful above a sufficient threshold, while the second approach reaches the optimal information-theoretic threshold.
- 7.1 A semidefinite programming based relaxation: The proposed SDP encodes community assignments with ±1 vectors and relaxes the objective of maximizing within-community edges minus across-community edges to a semidefinite program.The relaxation follows the Goemans–Williamson framework, and SDPs can be solved in polynomial time.
- 7.1 A semidefinite programming based relaxation: The SDP proof constructs a feasible dual certificate and uses KKT conditions, matrix inequalities, and eigenvalue control to establish optimality and uniqueness of gg^T.The second-smallest-eigenvalue condition ensures that any optimal solution must be a multiple of gg^T, and the diagonal constraints then identify it uniquely.
- 7.2 Efficient full recovery from efficient partial recovery: The full-recovery algorithm splits the observed graph into G1 and G2, applies partial recovery to G1, and uses edges in G2 for local membership corrections.The split makes the two stages almost independent; partial recovery misclassifies at most δ(C)n nodes with high probability, where δ(C) tends to zero as C grows.
- 7.2 Efficient full recovery from efficient partial recovery: If (α+β)/2 − √(αβ) > 1, sufficiently large C makes the partial-recovery-plus-local-improvement algorithm recover both communities with high probability.The proof shows that the probability that any node remains mislabeled after local improvements tends to zero.
8 Conclusion and open problems
The conclusion identifies an efficiency gap in the SDP analysis and several open directions for algorithms and broader models.
- 8 Conclusion and open problems: At high SNR, the SDP algorithm succeeds near the ML threshold but only up to an additional factor of 2.Numerical simulations suggest the SDP method may reach the optimal threshold, indicating the factor may arise from the analysis.
- 8 Conclusion and open problems: It remains open whether the SDP or a spectral algorithm achieves the optimal bound α+β over 2 −√αβ > 1.
- 8 Conclusion and open problems: Partial recovery followed by local improvement eliminates the gap between efficient recovery and maximum likelihood, although direct algorithms would still be desirable.
- 8 Conclusion and open problems: The authors expect extensions to models with multiple clusters, overlapping communities, and labelled edges.
A.1 Tail of the difference between two independent binomials of different parameters
This appendix develops tight bounds for tails involving differences between independent binomial variables, using careful asymptotic control of dominant terms and binomial coefficients.
- A.1 Tail bounds: The analysis models the relevant sums with independent Bernoulli variables having parameters p and q.The variables W_i and Z_i are mutually independent sequences with the respective Bernoulli parameters.
- A.1 Tail bounds: The resulting bound requires tight estimates because CLT and Chernoff approximations incur exponent errors of order O(log(n)).The appendix states that this error is relevant in the considered regime.
- A.1 Tail bounds: The analysis targets T(m, p, q, ε) through its dominant term T*(m, p, q, ε), maximized over τ > 0.The proof repeatedly bounds the original quantity by this dominant contribution.
- A.1 Tail bounds: The derivation uses upper and lower bounds for binomial coefficients, followed by optimization over τ.The proof substitutes the parameter expressions, applies coefficient bounds, and minimizes h(α, β, τ, ε).
- A.1 Tail bounds: The proof treats separate regimes of m, including m ≥ n log log n and m < n log log n.The second regime requires restricting the sum because the preceding argument fails when m is O(n).
A.2 Information Theoretic Lower Bound Proofs
The information-theoretic lower-bound proofs establish probability control for degree-related events using binomial variables and Chernoff bounds.
- A.2 Information Theoretic Lower Bound Proofs: P(∆) ≥ 9/10 for sufficiently large n.
- A.2 Information Theoretic Lower Bound Proofs: The event ∆ concerns an Erdős–Rényi graph in which every node has degree strictly less than log n over log log n.
- A.2 Information Theoretic Lower Bound Proofs: The proof bounds individual degree probabilities with multiplicative Chernoff estimates and combines them using a union bound.
A.3 SDP Algorithm Proofs
The SDP proof analyzes random graph matrices through projections onto the all-ones direction and its orthogonal complement, using matrix concentration and degree bounds.
- A.3 SDP Algorithm Proofs: The proof decomposes the relevant matrix into components on the 1 direction and its orthogonal complement.The quantity R is defined as the maximum of the contributions R1 and R2 from these two subspaces.
- A.3 SDP Algorithm Proofs: The deterministic matrix C has the ground-truth vector g as an eigenvector associated with eigenvalue 0.The proof then checks the required condition on the subspace orthogonal to g.
- A.3 SDP Algorithm Proofs: Matrix Bernstein’s inequality supplies the concentration bound for the independent random self-adjoint matrix sequence.
- A.3 SDP Algorithm Proofs: With high probability, every node in H1 has degree at most 2 C log(n) over n.The argument uses Chernoff bounds and a union bound over nodes.