Source-linked AI summary
Consistency Thresholds for the Planted Bisection Model
Elchanan Mossel, Joe Neeman, Allan Sly
TL;DR
The paper studies when the hidden bisection in a random graph can be reconstructed from the graph, addressing necessary as well as sufficient recoverability conditions. It characterizes recoverability through a local majority condition and provides an efficient algorithm combining spectral, replica, and local-move stages. The results connect asymptotic recovery with the planted bisection being the minimum bisection with high probability.
Problem
The central question is whether the hidden labeling can be reconstructed from the graph, with prior work providing sufficient but rarely necessary conditions on p_n and q_n.
Method
The paper characterizes recoverability through the probability P(n,p_n,q_n) and supplies an efficient algorithm for recovering the planted bisection.
Results
Strong consistency exists if and only if P(n,p_n,q_n)=o(n^-1), while weak consistency exists if and only if P(n,p_n,q_n)→0.
Takeaways & Limitations
The planted bisection equals the minimum bisection with high probability exactly when every node has more neighbors with its own label than with the other label.
Takeaways & Limitations
The paper leaves open whether almost-exact recovery can be guaranteed when an adversary is restricted to adding o(n) edges.
Abstract
from arXiv · showhide
The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the case of logarithmic average degree.
1 Introduction
The planted bisection model connects random-graph community detection with the Min-Bisection problem. This paper gives a necessary and sufficient recoverability condition and an efficient recovery algorithm.
- Model: The model divides 2n vertices into two equal classes, adding within-class edges with probability p_n and between-class edges with probability q_n.The planted bisection is the hidden partition underlying the random graph.
- Motivation: Min-Bisection seeks a bisection cutting the fewest edges, although the problem is NP-complete in the worst case.For fixed p_n=p>q=q_n, the planted bisection is typically the minimum bisection and can be found in expected O(n^3) time.
- Motivation: In community detection, the two bisection parts represent latent communities to be identified from the observed graph structure.When p_n>q_n, maximum a posteriori community estimation coincides with minimum bisection.
- Contribution: The paper establishes a necessary and sufficient condition on p_n and q_n for recoverability and provides an efficient recovery algorithm.This directly addresses the asymptotic label-reconstruction problem in the planted model.
2 Definitions and results
The paper characterizes when planted bisections can be recovered, showing that strong and weak consistency are governed by the probability that a vertex lacks a majority. It also gives an efficient almost-edge-linear recovery algorithm and explicit threshold consequences in several regimes.
- Consistency characterization: Strong consistency exists if and only if P(n,pn,qn) = o(n^-1), while weak consistency exists if and only if P(n,pn,qn) →0.These are the necessary and sufficient conditions for strongly and weakly consistent estimators, respectively.
- Local majority conditions: P(n,pn,qn) = o(n^-1) exactly when every vertex has a majority asymptotically almost surely, whereas P(n,pn,qn) →0 exactly when at most o(n) vertices lack one.A majority means having at least one more neighbor with the same label than with the opposite label, with the inequality reversed when qn > pn.
- Local-to-global interpretation: The planted bisection equals the minimum bisection with high probability exactly when every vertex has more neighbors of its own label than of the other label with high probability.This places the recovery threshold in a local-to-global framework analogous to connectivity and Hamiltonicity thresholds in random graphs.
- Contribution and novelty: The algorithm’s novelty lies in combining existing spectral, replica, and local-improvement ideas in a way that is crucial to correctness.The paper closes a gap between prior sufficient and necessary conditions; in the example pn = 1/2 and qn = 1/2 − rn, the critical constant is C = c = 1.
- Explicit regimes: Strong consistency requires at least one of pn or qn to be asymptotically at least n^-1 log n, and explicit characterizations are available in the Θ(n^-1 log n) regime.Proposition 2.8 treats pn = an n^-1 log n and qn = bn n^-1 log n under boundedness assumptions, while Proposition 2.9 gives equivalent conditions when pn,qn = ω(n^-1 log^3 n).
3 Binomial probabilities and graph structure
This section develops binomial perturbation estimates and uses them to relate the probability of a node having a minority to the global number of minority nodes. First- and second-moment arguments establish when almost all or all nodes have majorities.
- Binomial perturbation estimates: Proposition 3.1 gives binomial perturbation estimates under mp ≥64log m and p ≤2/3, with a universal constant controlling the bound.The estimates support later applications involving majority margins and single-trial perturbations.
- Binomial perturbation estimates: The condition mp ≥64log m is substantive: when p = m−1 log m and q = 0, the comparison between Pr(Y ≥X) and Pr(Y ≥X −1) changes by a logarithmic factor.The sparse regime requires a separate analogue of the perturbation estimate.
- Dependence between minority events: The preceding estimates show that the events that two nodes have minorities are essentially independent and therefore essentially uncorrelated.The proof conditions on whether the two nodes are adjacent and bounds the resulting variance contribution.
- Graph structure: If P(n,p_n,q_n) = o(n−1), then the expected number of nodes with minorities is o(1), so a.a.s. every node has a majority.The argument uses the first moment and Markov’s inequality.
- Graph structure: If P(n,p_n,q_n) is not o(n−1), then the expected minority count remains bounded away from zero along an infinite subsequence, and a second-moment argument gives a nonvanishing chance of a minority.Thus, the event that every node has a majority is not asymptotically almost sure.
4 Sufficient condition for strong consistency
The proposed strong-consistency strategy starts with a weakly accurate labeling and improves it using local majority decisions. Spectral structure motivates the initial guess, while removing held-out vertices supplies the independence needed for cleanup.
- Algorithmic idea: The algorithm first obtains a weakly consistent labeling and then improves it by flipping nodes that have a minority relative to that labeling.A sufficiently large true neighborhood majority is unlikely to be reversed by the small labeling noise.
- Algorithmic idea: The naive local-improvement argument requires independent labeling errors and only directly handles nodes with sizeable majorities.These limitations motivate removing a node before computing the almost-accurate labeling used to update it.
- Spectral initialization: The conditional expectation of the adjacency matrix has the all-ones vector and the planted label vector as its principal directions, with the label vector corresponding to the second eigenvalue.Rounding the second eigenvector of the observed adjacency matrix is therefore the spectral starting point when the matrices are sufficiently close.
- Algorithmic implementation: The resulting algorithm takes graph G and an accuracy parameter ϵ as input and outputs a partition W+,W−, using random vertex subsets and majority comparisons.The comparison direction depends on whether p > q or p < q.
20 end
This section proves that spectral initialization can produce an almost-correct labeling and analyzes the replica and local-cleanup stages. The stages progressively confine errors to a small, weakly connected set before correcting them all.
- Spectral initialization: When n(p_n + q_n) →∞, the random adjacency fluctuation is order-wise smaller than the signal eigenvalue, enabling recovery of all but o(n) vertices by Davis–Kahan.The spectral argument begins from the condition p_n + q_n = Ω(n−1 log n).
- Initial accuracy boost: Algorithm 1 correctly labels every node outside V_ϵ a.a.s., where V_ϵ contains nodes with weak majorities or more than 100np neighbors.V_ϵ is defined using a majority threshold ϵ√nplog n and a degree threshold 100np.
- Structure of the bad set: If P(n,p_n,q_n) = o(n−1), then V_ϵ is small a.a.s.; for every δ > 0, an appropriate ϵ gives |V_ϵ| ≤ n^δ.The proof treats both the denser and sparse regimes using the corresponding binomial estimates.
- Hill-climbing cleanup: In the sparse regime np ≤ n1/4, no two nodes in V_ϵ are adjacent and no node has two or more neighbors in V_ϵ a.a.s., while Algorithm 2 then returns the true partition.The bad set is consequently too small and poorly connected to overturn the remaining majority decisions.
5 Necessary condition for strong consistency
The necessity proof shows that if minority nodes occur with nonvanishing probability, exact recovery cannot be guaranteed. A likelihood comparison rules out a unique maximum-posterior labeling when opposite-label minority nodes coexist.
- Likelihood argument: Under a unique maximum-posterior labeling, there cannot be both a + node and a − node with minorities relative to that labeling.Swapping the labels of such a pair preserves balance while contradicting uniqueness of the likelihood maximizer.
- Likelihood argument: The likelihood of a graph under a labeling is determined by the within-label and between-label edge sets, allowing the swap argument to compare candidate labelings directly.The proof uses the fact that the swap preserves the sizes of these edge sets.
- Necessity setup: Strong consistency requires ruling out a nonvanishing chance that nodes of both planted labels simultaneously have minorities.This is the key obstruction to proving necessity when P(n,p_n,q_n) is not o(n−1).
- Necessity conclusion: When P(n,p_n,q_n) is not o(n−1), symmetry and Harris’s inequality yield infinitely many n for which opposite-label minority events occur together with nonvanishing probability.This contradicts the unique-maximizer condition required for strong consistency.
6 Binomial approximations
This section develops binomial approximations and tail estimates used to characterize when P(n,p_n,q_n)=o(n^-1). It treats sparse and dense regimes using Poisson, local central limit, Stirling, Taylor, and concentration arguments.
- Overview: The section proves explicit sparse- and dense-case characterizations of P(n,p_n,q_n)=o(n^-1), together with perturbative binomial estimates.The main tools are Bernstein’s inequality, Stirling’s approximation, Taylor expansion, Poisson approximation, and a local central limit theorem.
- Sparse regime: Poisson approximation is introduced for sums of binomial variables in the sparse regime, with uniform asymptotics for k≤10c log n.The approximation’s implicit error sequence is independent of n and k.
- Sparse regime: If a−b≤ε(C) under p_n=a log n/n and q_n=b log n/n, strong consistency does not hold.The argument uses a constant-probability fluctuation of X below its mean and a lower bound on the probability that Y exceeds a log n.
- Dense regime: The dense-case analysis uses a local central limit theorem, with Stirling’s approximation providing the underlying binomial probability estimate.The theorem applies when k lies within C√(n log n)σ_q of nq, and the proof controls deviations using Bernstein’s inequality.
- Approximation strategy: The estimates reduce relevant sums to central windows around the binomial means, while Bernstein bounds the omitted tails.In one argument, the retained range is centered at mp and has width proportional to √(mp log m), with an additive 2m^-2 cost.
7 Erratum
The erratum corrects Lemma 5.1 by introducing strict minorities and replacing the invalid argument with Lemma 7.2. The corrected result supports the necessity proof for strong consistency in sparse and dense regimes.
- Correction: The published version contained a mistake, and the original Lemma 5.1 was incorrect because its proof used an invalid inequality.The paper explicitly acknowledges the error and identifies the problematic lemma and inequality.
- Correction: A strict minority is defined by a strict imbalance toward the opposite-label neighbors when p>q, or toward same-label neighbors when p<q.The definition is stated separately for the two parameter orderings.
- Corrected lemma: Lemma 7.2 states that a unique maximal labelling cannot contain opposite-labelled nodes that both have strict minorities.It also covers the case of opposite-labelled non-adjacent nodes with minorities.
- Necessity proof: In the sparse case, when P(n,p_n,q_n)≥εn^-1 and np_n≤64 log n infinitely often, opposite-labelled non-adjacent minorities occur with asymptotically positive probability.This supplies the sparse obstruction used in the corrected necessity argument.
- Necessity proof: In the dense case, when P(n,p_n,q_n)≥εn^-1 and np_n≥64 log n infinitely often, opposite-labelled strict minorities occur with asymptotically positive probability.The proof combines bounds on strict-minority counts, approximate independence, and Harris’s inequality.
- Conclusion: Combining Lemma 7.2 with the sparse or dense obstruction proves that P(n,p_n,q_n)=o(n^-1) is necessary for strong consistency.The sparse case uses Lemma 7.3, while the dense case uses Lemma 7.4.