Source-linked AI summary
Stochastic Block Models and Reconstruction
Elchanan Mossel, Joe Neeman, Allan Sly
TL;DR
The paper studies whether clustering and parameter estimation are possible in the sparse planted partition model at the conjectured statistical-physics threshold. It proves impossibility below the threshold, gives efficient parameter estimation above it, and rigorously connects clustering with tree reconstruction.
Problem
The central question is whether clustering and model-parameter estimation are possible in sparse planted partition graphs, where prior rigorous clustering guarantees required a larger separation threshold.
Method
The paper establishes the conjectured impossibility results and develops a coupling between graph neighborhoods and a broadcast process on trees.
Results
Below (a − b)^2 < 2(a + b), clustering and consistent parameter estimation are impossible; above it, an efficient polynomial-time algorithm estimates a and b.
Takeaways & Limitations
The results rigorously establish the conjectured non-reconstruction threshold for clustering and parameter estimation in the sparse model.
Takeaways & Limitations
For the Potts model with k > 2, existing non-reconstruction results are less precise and harder to prove than for k = 2.
Abstract
from arXiv · showhide
The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on $n$ nodes with two equal-sized clusters, with an between-class edge probability of $q$ and a within-class edge probability of $p$. Although most of the literature on this model has focused on the case of increasing degrees (ie.\ $pn, qn \to \infty$ as $n \to \infty$), the sparse case $p, q = O(1/n)$ is interesting both from a mathematical and an applied point of view. 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$, then Decelle et al.\ conjectured that it is possible to cluster in a way correlated with the true partition if $(a - b)^2 > 2(a + b)$, and impossible if $(a - b)^2 < 2(a + b)$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $(a - b)^2 > C (a + b)$ for some sufficiently large $C$. We prove half of their prediction, showing that it is indeed impossible to cluster if $(a - b)^2 < 2(a + b)$. Furthermore we show that it is impossible even to estimate the model parameters from the graph when $(a - b)^2 < 2(a + b)$; on the other hand, we provide a simple and efficient algorithm for estimating $a$ and $b$ when $(a - b)^2 > 2(a + b)$. Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.
1 Introduction
The planted bisection model studies clustering in random graphs with labels determining within- and between-class edge probabilities, especially in sparse networks. Statistical-physics conjectures connect its clustering threshold to tree reconstruction, while prior rigorous results were weaker.
- The planted partition problem: The planted bisection model assigns independent random ± labels and includes edges with probability p within labels and q across labels.
- The planted partition problem: When p = q the model reduces to Erdős-Rényi, whereas p ≫ q typically produces two well-defined clusters.
- Sparse graphs and insights from statistical physics: Sparse graphs with constant average degree are motivated by large real-world networks, many of which have millions of nodes but average degree no more than 20.
- Sparse graphs and insights from statistical physics: Decelle et al. conjectured that clustering is solvable above (a − b)^2 > 2(a + b) and impossible below (a − b)^2 < 2(a + b).
- Sparse graphs and insights from statistical physics: Prior rigorous results established clustering for (a − b)^2 > C(a + b) with sufficiently large C, leaving the conjectured threshold unresolved.
- Sparse graphs and insights from statistical physics: Tree reconstruction reaches its threshold at (a − b)^2 = 2(a + b), motivating the connection between graph neighborhoods and multi-type branching processes.
2 Our results
The paper establishes the conjectured threshold for non-reconstruction and parameter estimation below the threshold, while giving efficient estimation above it. Its proofs connect local tree-like structure and short-cycle counts with global planted-versus-Erdős–Rényi comparisons, while addressing non-Markov dependencies.
- The paper establishes Conjectures 1.3 and 1.4 for the sparse planted partition model.
- If a+b > 2 and (a−b)^2 ≤ 2(a+b), no algorithm can determine whether two random vertices share a label, including equality at the threshold.The assumption a+b > 2 ensures a giant component.
- Below the threshold, the planted model and a same-average-degree Erdős–Rényi model are mutually contiguous, and no consistent estimator for a and b exists.
- 2.1.1 Short Cycles: The estimators use cycle-derived quantities, with ˆd_n+ˆf_n estimating a and ˆd_n−ˆf_n estimating b, and can be computed in polynomial time.Short-cycle counts are replaced with efficiently computable non-backtracking walks with high probability.
- 2.1.1 Short Cycles: Above the threshold, short-cycle counts distinguish the planted and Erdős–Rényi models and consistently estimate a+b and a−b, hence a and b.The comparison uses first and second moments while cycle lengths increase slowly with n.
- 2.1.2 Non-Reconstruction: The non-reconstruction proof must overcome global equal-size conditioning and anti-ferromagnetic interactions between nonadjacent vertices, so the model is not a conditioned Markov random field.The proof uses enriched distributions, an explicit second-moment formula, and small-graph conditioning to control the likelihood ratio.
3 Counting cycles
This section shows that short-cycle counts have an asymptotically Poisson distribution and uses them to distinguish models and estimate parameters. The resulting estimator for a and b is consistent above the threshold and computable efficiently.
- For k = O(log^1/4 n), the number X_k,n of k-cycles is asymptotically Poisson with mean k2k+1((a + b)^k + (a − b)^k).
- Model distinction: Comparing cycle-count distributions yields an event that occurs with probability tending to one under P′ and tending to zero under P.
- Parameter estimation: Counting edges consistently estimates d = (a + b)/2, while suitably growing cycle counts consistently estimate f = (a − b)/2 when f > 1.
- Parameter estimation: The parameters are recovered as â = d̂ + f̂ and b̂ = d̂ − f̂.
- Efficient implementation: An algorithm computes â and b̂ in time O(nlog^O(1) n) when k(n) = o(log^1/4 n).It counts non-backtracking closed walks using recursively defined matrix products on local graph balls.
- Poisson cycle counts: The factorial-moment proof separates ordered tuples of cycles into vertex-disjoint and overlapping tuples, whose expected number tends to zero.
4 Non-reconstruction
This section connects sparse planted-partition neighborhoods to broadcast processes on Galton-Watson trees. The coupling and non-reconstruction theorem imply impossibility of reconstruction below the threshold.
- Broadcast process: The broadcast process assigns each child the parent’s label with probability 1 − epsilon and the opposite label otherwise.
- Non-reconstruction: On a Galton-Watson tree with offspring mean d > 1, reconstruction is impossible in the regime d(1 − 2epsilon)^2 <= 1.
- Non-reconstruction: Substituting the planted-partition parameters shows that root-label reconstruction is impossible whenever (a − b)^2 <= 2(a + b).
- Tree coupling: The neighborhood of the planted graph can be coupled with a Galton-Watson tree carrying a Markov label process up to radius R.The coupling holds asymptotically almost surely for R = floor((1/(10log(2(a+b)))) log n).
- Long-range correlations: The graph’s root and a separated vertex become asymptotically conditionally independent given the boundary labels and graph.This uses the fact that weak long-range interactions are sufficiently small when one separated set occupies most of the graph.
- Transfer to the graph: The coupling transfers tree non-reconstruction to the graph, implying that the root label cannot be reconstructed from another vertex below the threshold.
5 The Second Moment Argument
The section applies small subgraph conditioning to the partition function, using short-cycle counts and moment calculations to establish contiguity and the first statement of Theorem 2.4.
- Method: The proof reduces Theorem 2.4 to studying the partition function Z_n(G) and applies the small subgraph conditioning method.This method handles variables that concentrate after conditioning on the numbers of short cycles.
- Short cycles: The auxiliary variables X_k are the numbers of k-cycles in G_n, whose limiting means satisfy λ_k = 1/(2k) (a+b)^k.
- Moment calculations: The first moment is normalized so that E[Y_n] = 1, while the second moment is computed through weights associated with pairs of labelings.The calculation introduces the overlap parameter ρ(σ,τ) and evaluates E[W_uvV_uv].
- Cycle contributions: For cycle unions, the argument computes E[Y_n 1_H] exactly for vertex-disjoint cycles and bounds contributions from non-disjoint unions.Cycle weights depend only on whether adjacent vertices have equal or different labels.
- Parameter estimation: No consistent estimator for a and b exists when (a−b)^2 < 2(a+b), because models with the same a+b become indistinguishable in this regime.The argument compares the planted model with another parameter choice having the same sum and applies Theorem 2.4.
6 Conjectures Regarding Regular Models
The section proposes regular planted models and conjectures a spectral threshold governed by (d−1)θ^2, with a correlated approximate eigenvector above threshold.
- Model: The proposed regular model is a simple d-regular graph with approximately independent local choices and Binom(d,1−ε) same-label neighbors per vertex.
- Model: Two constructions are suggested: conditioned same-label degree sequences with random within- and between-class graphs, and a configuration-model variant using independent matchings.
- Conjecture: The conjectured regular-model threshold replaces (a−b)^2/2(a+b) with (d−1)θ^2, where θ = 1−2ε.
- Spectral conjecture: If (d−1)θ^2 > 1, the second eigenvalue is conjectured to exceed 2√(d−1)+δ, while all other eigenvalues remain below 2√(d−1).
- Spectral conjecture: The eigenvector associated with λ_2(G) is conjectured to correlate with the true partition, enabling spectral distinction and clustering.
- Proof sketch: The proof sketch constructs f from radius-r boundary labels and shows an approximate eigenvalue-eigenvector pair, but does not establish the required bound on all other eigenvalues.The approximation becomes tighter as r increases.
7 Open problems
The section identifies open problems involving efficient algorithms, more than two clusters, and sharper reconstruction thresholds for the Potts model.
- Open problems: Conjecture 1.2 remains open, including whether one of several popular efficient algorithms realizes the predicted clustering threshold.
- Algorithms: The conjectured algorithmic variants include spectral methods, belief propagation, and simulating an almost-balanced Ising model.
- More clusters: For k clusters, Conjecture 7.2 proposes thresholds separating impossible clustering, non-polynomial-time solvability, and polynomial-time solvability.
- More clusters: When k ≤ 4, c(k) = k, whereas for k ≥ 5, c(k) < k, so the intermediate computational regime is absent only for smaller k.
- More clusters: The k > 2 case is harder because the best known non-reconstruction results for the Potts model are less precise than for k = 2.
- Related extensions: When a < b, the conjectured intermediate regime becomes much larger and connects the problem to random Boolean satisfiability and spin glasses.