Consistency Thresholds for the Planted Bisection Model

Allan Sly; Elchanan Mossel; Joe Neeman

RECORD

Consistency Thresholds for the Planted Bisection Model

Elchanan Mossel, Joe Neeman, Allan Sly

Probability · Submitted 7 Jul 2014

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,612 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.13 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.43 · states quantitative result 0.21 · compares with prior results 0.95 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v5. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	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.	background 1.00	0.05	0.02	asserted 0.99
s1	We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model.	contribution 0.60	0.96	0.75	asserted 1.00
s2	When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it.	contribution 0.83	0.96	0.15	asserted 1.00
s3	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.	result 1.00	0.92	0.56	asserted 1.00
s4	Our algorithm for finding the planted bisection runs in time almost linear in the number of edges.	method 0.39	0.96	0.06	asserted 1.00
s5	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.	method 1.00	0.93	0.04	asserted 1.00
s6	An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the case of logarithmic average degree.	background 0.82	0.05	0.02	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.97 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v5

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

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.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Information Limits of Joint Community Detection and Finite Group Synchronization
cs.IT 2024-12 conditional novelty 8.0 of 10

For the joint stochastic block model plus finite-group synchronization, perfect community recovery is possible exactly when (a+b)/2 - sqrt(ab/M) > 1, and perfect group recovery additionally requires a > 2.
Fundamental Limits of Query-Based Subgraph Detection
math.ST 2026-07 conditional novelty 7.0 of 10

For non-adaptive edge-query detection of arbitrary planted subgraphs, the minimum query count is governed by whether the planted graph has dense local witnesses, high-degree hubs, or just many edges.

How the literature uses it

59 arXiv papers cite this in 136 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 78 sentences without a confident label

Builds on it 2 papers

We derive sharp thresholds for strong and weak consistency for community detection [ref] in MLSBM and the aggregate SBM under two scenarios: sparse graph with average degree per layer $o(logn)$ and ultra-sparse graph with average degree per layer $o(1)$.

Community detection in multi-relational data with restricted multi-layer stochastic blockmodel · Sharp consistency thresholds · 0.90
For the symmetric block model where $p$ is equiprobable on $[k]$ and $Q$ takes only two different values, $α$ on the diagonal and $β$ outside the diagonal (with $α,β>0$), the requirement in Theorem [ref] for recovery of any (or all) communities is equivalent to [equation] which generalizes the result obtained in [ref] for $k=2$.

Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms · Formal results · 0.94

Uses its method or tool 1 paper

The proposed algorithm begins by obtaining an initial clustering using an approach presented in [ref] , which consists of spectral clustering followed by a replica method.

Active Learning for Community Detection in Stochastic Block Models · Introduction · 1.00

Uses its data or values 1 paper

To do this, we use the fact that the probability that a node is a minority is $Ω(n^-D/ln(n))$ [ref] .

Active Learning for Community Detection in Stochastic Block Models · Necessary Condition · 0.83

Compares with it 13 papers

Note that Theorem [ref] is congruous with previous results [ref] .

Active Learning for Community Detection in Stochastic Block Models · Background and Main Result · 0.88
As a consequence, we obtain phase transitions for non-consistency and strong consistency, under various settings, which recover the tight thresholds for phase transition in [ref] .

Minimax Rates of Community Detection in Stochastic Block Models · Introduction · 0.85
When $k=O(1)$, weak consistency is possible if and only if $inf_zsup_Θ_k(p,q,β)𝔼ℓ(z,z)=o(1)$, which is equivalently the condition $nI→∞$ [ref] .

Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing · Results for SBMs · 0.86

Cites it as support 1 paper

Such a rate is the slowest for exact recovery in the SBM, as established by [ref] , [ref] , [ref] , and [ref] .

Detecting Latent Communities in Network Formation Models · Full- and Split-Sample Low-Rank Estimations · 0.97

Cites it as background 26 papers

In particular, substantial advances have been made in the past decade on understanding the statistical limits for detection and recovery of communities in graphs that are generated by SBMs, and on developing computationally tractable methods that can detect and recover the underlying communities at their corresponding statistical limits; see, for example, [ref] .

Non-Convex Exact Community Recovery in Stochastic Block Model · Introduction · 0.97
Over the past years, great progress has been made on establishing the fundamental limits for detecting communities in various SBMs [ref] and on developing computationally tractable algorithms that can recover the hidden communities at the information-theoretic limits [ref] .

Exact Community Recovery over Signed Graphs · Related Works · 0.94
In SBM, both the fundamental limits and computationally efficient algorithms are investigated initially for the case of two communities [ref] , and recently for the case of an arbitrary number of communities [ref] .

Community Recovery in Hypergraphs · The $d=2$ case · 0.94

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.