Home / Curated / Mathematical Methods / Stochastic Block Model Exact Recovery Phase Transition and Semidefinite Programming

Stochastic Block Model Exact Recovery Phase Transition and Semidefinite Programming

Mathematical Methods AIMech:StochasticBlockModelExactRecoveryPhaseTransitionAndSemidefiniteProgramming DRAFT

Aliases: SBM Exact Recovery Phase Transition, Abbe-Bandeira-Hall SBM Phase Transition, Chernoff-Hellinger Symmetric SBM Threshold, SBM Semidefinite Programming Exact Community Recovery

Stochastic Block Model Exact Recovery Phase Transition and Semidefinite Programming is the information-theoretic and convex-optimization framework established by Abbe, Bandeira, and Hall (2016) for exact community recovery (strong consistency) in the two-community symmetric Stochastic Block Model SBM(n, p, q) in the logarithmic degree regime p = alpha log(n)/n and q = beta log(n)/n (alpha > beta >= 0). It proves a sharp phase transition at the Chernoff-Hellinger threshold (sqrt(alpha) - sqrt(beta))^2 / 2 = 1 (equivalently alpha + beta - 2*sqrt(alpha*beta) = 2): when (sqrt(alpha) - sqrt(beta))^2 < 2, maximum a posteriori (MAP) estimation fails with probability -> 1 due to the emergence of flipped vertices having more cross-community than within-community neighbors (Theorem 1), whereas when (sqrt(alpha) - sqrt(beta))^2 > 2, both MAP and the polynomial-time Goemans-Williamson-type semidefinite programming relaxation max_{Y >= 0, Y_{ii}=1} Tr(B Y) with B = 2A - (1 1^T - I_n) recover the exact partition X^* = g g^T up to global sign with probability 1 - o(1) (Theorem 2 and Theorem 4).

Identity Notes & Concept Scope Distinct from generic graph clustering (AIO:Clustering, AIO:UnsupervisedClustering), normalized spectral clustering (AIMech:NormalizedSpectralClusteringNgJordanWeiss), and spectral regularization of sparse random graphs. Specifically captures the Abbe-Bandeira-Hall (2016) logarithmic-degree exact recovery threshold (sqrt(alpha) - sqrt(beta))^2 = 2 (Theorems 1-2), the binomial large-deviation bound P(Z_1 - Z_2 >= 0) = n^{-(sqrt(alpha)+sqrt(beta))^2/2 + o(1)} (Lemma 2), and the SDP dual-certificate Laplacian analysis S = 2 L_SBM + 1 1^T >= 0 with lambda_2(S) > 0 (Lemma 6, Lemma 11, and Theorem 4).

Claims & Grounded Evidence

3 Claims

Mechanism #claim-01

Exact recovery in the symmetric two-community SBM reduces to maximum likelihood / minimum bisection min_{x in {+-1}^n, x^T 1 = 0} sum_{i<j} A_{ij} 1{x_i != x_j} (Lemma 1), which fails whenever both communities contain at least one vertex whose external degree Z_2 ~ Bin(n/2, beta log(n)/n) exceeds its internal degree Z_1 ~ Bin(n/2 - 1, alpha log(n)/n); by Lemma 2, P(Z_1 <= Z_2) = n^{-(sqrt(alpha)-sqrt(beta))^2/2 + o(1)}, so expected misclassified vertices diverge when (sqrt(alpha)-sqrt(beta))^2 < 2 and vanish when (sqrt(alpha)-sqrt(beta))^2 > 2 (Theorems 1-2).

supports Source: Exact Recovery in the Stochastic Block Model · Locator: Section II, Theorems 1-2, pp. 3-4; Section IV, Lemmas 1-5 and Proof of Theorem 1, pp. 9-12
supports Source: Exact Recovery in the Stochastic Block Model (Crossref metadata) · Locator: Bibliographic metadata for IEEE Transactions on Information Theory 62(1):471-487

Scope #claim-02

For the convex semidefinite relaxation max_{Y >= 0, Y_{ii}=1} Tr(B Y) with B = 2A - (1 1^T - I_n), Lemma 6 proves that the rank-one community matrix Y^* = g g^T is the unique optimal solution whenever the dual slack matrix S = 2 L_SBM + 1 1^T = 2(D^+ - D^- - A) + 1 1^T (which satisfies S g = 0 identically) is positive semidefinite with lambda_2(S) > 0; Lemma 11 shows that E[S] has eigenvalues n - 2*beta*log(n) (on 1), 0 (on g), and (alpha - beta)*log(n) (with multiplicity n - 2 on {1, g}^perp), enabling Theorem 4 to establish exact SDP recovery down to the optimal threshold.

supports Source: Exact Recovery in the Stochastic Block Model · Locator: Section III.B, Equations 20-24, Theorem 4, and Lemma 6, pp. 7-9; Section V.B, Lemmas 9-11 and Proof of Theorem 4, pp. 12-13

Limitation #claim-03

Exact recovery (strong consistency of 100% of vertices) is information-theoretically impossible below the connectivity and Chernoff-Hellinger threshold (sqrt(alpha) - sqrt(beta))^2 < 2 or in the constant average degree regime O(1/n), where isolated and degree-flipped vertices occur with constant probability and only partial (weak) recovery is achievable.

supports Source: Exact Recovery in the Stochastic Block Model · Locator: Section I-II, Table I and Remark 1 (Strong vs. Weak Consistency), pp. 2-4; Section IV, Proof of Impossibility Theorem 1, pp. 9-12

⚠️ Curated Limitations & Negative Results

Exact recovery of all n community labels requires edge probabilities in the logarithmic degree regime p = alpha log(n)/n, q = beta log(n)/n satisfying (sqrt(alpha) - sqrt(beta))^2 > 2; in sparser graphs or below this threshold, no algorithm can avoid misclassifying a non-empty set of vertices.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:Clustering` Clustering	narrow_match	Exact recovery in the Stochastic Block Model is a probabilistic graph clustering and community detection method.
`AIO:UnsupervisedClustering` Unsupervised Clustering	narrow_match	The SBM semidefinite program partitions unlabeled network vertices into latent communities.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r318-primary-pdf`	Exact Recovery in the Stochastic Block Model Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall	primary paper full_text	ID: https://doi.org/10.1109/TIT.2015.2490670 sha256:4c6ceb3af2f7…
`r318-arxiv-abs`	Exact Recovery in the Stochastic Block Model (arXiv abstract) Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall	primary paper abstract_only	ID: https://arxiv.org/abs/1405.3267v4 sha256:083554e5bbee…
`r318-metadata-cr`	Exact Recovery in the Stochastic Block Model (Crossref metadata) Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall	primary paper abstract_only	ID: https://doi.org/10.1109/TIT.2015.2490670 sha256:ba3188267e4e…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T06:28:00Z

Updated: 2026-10-19T06:28:00Z

Source File: data/curated/StochasticBlockModelExactRecoveryPhaseTransitionAndSemidefiniteProgramming.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories