Source-linked AI summary
A Proof Of The Block Model Threshold Conjecture
Elchanan Mossel, Joe Neeman, Allan Sly
TL;DR
The paper addresses whether sparse stochastic block-model clustering has an efficient threshold at s^2 > d. It proves the conjectured threshold using an algorithm based on non-backtracking walks and matrix powering, while noting limitations in the preceding algorithm’s distributional analysis and running time. The main theorem establishes asymptotic clustering above the threshold.
Problem
Sparse stochastic block-model clustering had a conjectured threshold s^2 > d, while rigorous algorithms previously required a stronger condition.
Method
The paper analyzes non-backtracking walks and implements the resulting algorithm using matrix powering.
Results
If s^2 > d, the clustering problem is solvable as n →∞, and one can a.a.s. find a bisection correlated with the planted bisection.
Takeaways & Limitations
The paper proves the conjectured sparse-regime threshold for efficient clustering above s^2 = d.
Takeaways & Limitations
The preceding algorithm has dependent remaining edges after removing a node and running time about O(n^2 log n).
Abstract
from arXiv · showhide
We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph with two equal-sized clusters, with a between-class edge probability of $q$ and a within-class edge probability of $p$. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if $p = a/n$ and $q = b/n$, $s=(a-b)/2$ and $p=(a+b)/2$ then Decelle et al.\ conjectured that it is possible to efficiently cluster in a way correlated with the true partition if $s^2 > p$ and impossible if $s^2 < p$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $s^2 > C p \ln p$ for some sufficiently large $C$. In a previous work, we proved that indeed it is information theoretically impossible to to cluster if $s^2 < p$ and furthermore it is information theoretically impossible to even estimate the model parameters from the graph when $s^2 < p$. Here we complete the proof of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when $s^2 > p$. A different independent proof of the same result was recently obtained by Laurent Massoulie.
1 Introduction
The paper studies sparse stochastic block models, where clustering is difficult but practically motivated, and examines the conjectured threshold s^2 = d for recovery and parameter identifiability.
- Model: The stochastic block model assigns each vertex a random ±1 label, with edge probabilities determined by whether endpoint labels agree.Edges appear with probability q for equal labels and q′ for unequal labels.
- Sparse setting: Sparse graphs with constant average degree are motivated by real networks, whereas earlier theory largely focused on connected dense graphs.The dense regime has average degree at least log n.
- Sparse setting: For q = a/n and q′ = b/n, the model is parameterized by d = (a+b)/2 and s = (a−b)/2.Under these parameters, s^2 > d implies s,d > 1.
- Threshold conjecture: Decelle et al. conjectured that clustering is solvable when s^2 > d, allowing a bisection correlated with the planted partition.Their prediction was based on non-rigorous statistical-physics arguments and simulations.
- Threshold conjecture: The threshold s^2 = d was conjectured and proved to mark both clustering solvability and identifiability of parameters a and b.The threshold also has interpretations through Ising-model reconstruction and non-backtracking matrix spectra.
2 Our results
The paper proves efficient clustering above the conjectured threshold s^2/d > 1, with correlation bounded away from zero and improving toward exact recovery as the ratio grows.
- s^2 > d suffices for clustering correlated with the planted bisection, proving the conjectured solvability threshold.
- As s^2/d → ∞, the algorithm finds a bisection differing from the planted one on o(n) vertices.
- 2.1 Proof strategy: The proof analyzes weighted non-backtracking and self-avoiding paths, whose counts correlate with whether endpoint vertices share a label.A rank-one correction assigns edges weight 1−d/n and non-edges weight −d/n, giving each edge weight expectation zero.
- 2.1 Proof strategy: Second-moment control handles nice paths, while conditioning on tangle-free events controls paths affected by cliques and other problematic structures.Sparse graphs are ℓ-tangle-free with probability 1−n^-1+o(1) under the stated parameter assumptions.
- O(n d log^2 n) time yields an almost-linear algorithm for detecting communities above any fixed threshold ratio s^2/d ≥ λ > 1.A slightly modified algorithm could achieve O(n d log n).
- 2.3 Connections with random matrix theory: Naive spectral methods fail in sparse graphs because high-degree vertices distort the adjacency spectrum, whereas this algorithm uses non-backtracking walks and matrix powering.
3 The algorithm and its running time
The algorithm estimates vertex labels using non-backtracking path statistics, then computes those statistics efficiently through sparse matrix recursions. Above the threshold s^2>d, its output correlates with the true partition with high probability in time O(ndlog^2 n).
- Algorithm: The algorithm estimates graph labels from non-backtracking path quantities around a high-degree reference node.The simplified version removes the reference node and a neighborhood around each target vertex, then combines boundary statistics to estimate its label.
- Correctness: Above s^2>d, the estimator is correlated with the true partition with high probability.The proof uses branching-process coupling and shows P[σ_v=τ_v]→1 for a random vertex under the stated conditions.
- Algorithm: Uniformly removing δn vertices makes the remaining graph approximately preserve the stochastic block model distribution.The construction avoids the dependence created by removing specific neighborhoods while retaining usable local structures.
- Efficient implementation: The implementation computes path statistics through matrix recursions using sparse-plus-rank-one matrix-vector multiplications.The recursion is encoded by MQ^k=Q^{k+1} and a block-matrix relation recovering N^(k); each multiplication costs O(n+m).
4 Combinatorial path bounds
This section bounds the number of paths by classifying edges and controlling self-intersections. Non-backtracking paths with few tangles receive sufficiently sharp counting bounds, while paths with many returning edges are negligible.
- Crude bounds: Paths with large k_r are sufficiently rare that their total weight is negligible.Lemma 4.4 provides the counting bound used to discard paths with many returning edges.
- Path classification: Edges are classified as new, old, or returning, with path vertices equal to k_n(γ)+1 and edges equal to k_n(γ)+k_r(γ).New edges add vertices, returning edges add edges without vertices, and old edges add neither.
- Refined bounds: Non-backtracking and low-tangle structure are required to obtain bounds of order n^{k_n−1+o(1)}.The crude estimates are inadequate when k_r is small, motivating the introduction of tangles and non-backtracking restrictions.
- Tangles: An ℓ-tangle-free path is one whose induced multigraph becomes tangle-free without deleting edges, while t ℓ-tangles count the minimum deleted edge multiplicity needed.The decomposition separates short, tangled, and long neighbors to control old-edge choices.
- Refined bounds: The refined counting argument bounds old-edge choices using short neighbors and the constraints imposed by long or tangled departures.Each vertex has at most two short neighbors, and tangle structure bounds relevant arrivals and departures by k/(2ℓ)+t.
5 Weighted sums over self-avoiding paths
The analysis evaluates weighted sums over self-avoiding paths and decomposes general paths into self-avoiding pieces. These tools identify the dominant path configurations and control their moments.
- Self-avoiding paths: Self-avoiding paths and simple cycles provide the basic building blocks for expected-weight calculations.Lemma 5.1 evaluates their weights uniformly under the stated sparsity condition.
- SAW decomposition: A canonical SAW-decomposition covers a general path with self-avoiding pieces whose interiors do not overlap.Each component connects endpoints in the decomposition, and every edge is covered.
- SAW decomposition: The canonical decomposition uses at most 2k_r(γ)+B(γ)+1 components, or at most 2k_r(γ)+B(γ)+1+|U| in the U-canonical version.Returning edges, backtracks, and selected endpoint vertices account for the additional components.
- Weighted sums: Applying the self-avoiding-path estimate componentwise controls the expected weight of a SAW-decomposition.The components are conditionally independent given their endpoints, enabling Lemma 5.1 to be applied separately.
- Second moment: The Γ1 path class supplies the main term in the second-moment bound.Γ1 consists of a simple cycle with up to two twice-traversed tails, while other contributions are lower order.
6 Weighted sums over complicated paths
The section controls weighted sums over non-self-avoiding paths by conditioning on tangle-free events and decomposing paths into self-avoiding components. It shows that these complicated paths contribute negligibly under the required sparsity conditions.
- Tangle control: The event that the graph is ℓ-tangle-free is covered by events forbidding suitable edge sets.For every path γ, Ξ⊂Ω_F(γ), where the forbidden set removes enough short edges to eliminate tangles.
- Tangle control: If ℓ log d=o(log n), the graph is ℓ-tangle-free with probability at least 1−n^{−1+o(1)}.A union bound over bounded-size bicyclic subgraphs gives the stated probability.
- Path pairs: For pairs of non-self-avoiding paths, concatenation and SAW-decomposition control the contribution of repeated and tangled segments.The analysis separates short components affected by forbidden-edge events from long components bounded by the SAW estimates.
- Final bound: The fourth part of Theorem 2.8 follows from the non-self-avoiding-path bound, Chebyshev’s inequality, and the high-probability tangle-free event.The section concludes the proof of Theorem 2.8 by combining these ingredients.