Source-linked AI summary
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
Bruce Hajek, Yihong Wu, Jiaming Xu
TL;DR
The paper studies exact recovery of planted communities in random graphs and whether semidefinite programming can attain optimal recovery thresholds. It resolves the conjecture affirmatively for the stochastic block model and proves the same threshold result for a planted dense subgraph model with a cluster proportional to n.
Problem
Community detection seeks to recover underlying communities using only network topology, while prior work conjectured whether SDP could attain the optimal recovery threshold.
Method
The paper analyzes the semidefinite programming relaxation of the maximum likelihood estimator for the binary symmetric stochastic block model and planted dense subgraph model.
Results
SDP achieves the optimal recovery threshold for the stochastic block model and for the planted dense subgraph model when the cluster size scales linearly with n.
Takeaways & Limitations
The conjecture that SDP attains the optimal recovery threshold is resolved positively, including for planted dense subgraphs with cluster size proportional to n.
Takeaways & Limitations
The planted dense subgraph threshold guarantee need not extend when the cluster size grows sublinearly in n.
Abstract
from arXiv · showhide
The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability $p$ within clusters and $q$ across clusters. In the asymptotic regime of $p=a \log n/n$ and $q=b \log n/n$ for fixed $a,b$ and $n \to \infty$, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. \cite{Abbe14}. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to $n$.
1 Introduction
The paper studies exact community recovery in planted random graph models, focusing on the binary symmetric stochastic block model and planted dense subgraphs. It shows that semidefinite programming reaches the optimal recovery threshold in the considered regimes.
- Models: The planted cluster model partitions rK of n vertices into r clusters of size K, with in-cluster edge probability p and cross-cluster probability q.Vertices outside clusters are outliers connected to every other vertex with probability q.
- Binary symmetric stochastic block model: For the binary symmetric stochastic block model, exact recovery is possible when (√a − √b)^2 > 2 and impossible when (√a − √b)^2 < 2.These conditions describe the sharp information-theoretic threshold in the regime p=a log n/n and q=b log n/n.
- Computational context: The maximum likelihood estimator achieves the optimal threshold but requires solving minimum graph bisection, which is NP-hard in the worst case.A known polynomial-time two-step procedure first obtains partial recovery and then corrects vertices using the majority of their neighbors.
- Main contributions: The paper resolves a conjecture by proving that the SDP relaxation achieves the optimal recovery threshold for the binary symmetric stochastic block model.The result establishes polynomial-time attainment of the information-theoretic threshold.
- Main contributions: The paper also proves optimal-threshold recovery by SDP for the planted dense subgraph model when the cluster size scales linearly with n.This contrasts with a planted-clique-based computational barrier described for sublinear cluster sizes.
2 Stochastic block model
The paper formulates community recovery as an optimization over cluster-sign matrices and relaxes the resulting rank-one constraint to obtain an SDP. Under the sharp threshold, this SDP recovers the true partition with high probability and is robust to monotone graph alterations.
- Maximum likelihood formulation: The binary partition is represented by σ ∈ {±1}^n, with balanced clusters enforced by σ^T1=0.The true partition corresponds to σ*, and the maximum likelihood estimator maximizes in-cluster edges minus out-cluster edges.
- SDP formulation: Replacing Y=σσ^T's rank-one restriction with positive semidefiniteness yields a convex semidefinite-programming relaxation.The formulation also imposes unit diagonal and a balance constraint through ⟨J,Y⟩=0.
- SDP formulation: The SDP formulation requires only knowledge that a>b; when a<b, the optimization direction changes from maximization to minimization.This formulation differs from an earlier SDP by explicitly imposing ⟨J,Y⟩=0.
- Recovery guarantee: When (√a − √b)^2 > 2, the SDP recovers the true cluster matrix with probability 1−n^−Ω(1) as n→∞.The result is stated uniformly over balanced sign vectors through min_{Y*∈Y_n} P{Y_SDP=Y*}.
- Robustness: The SDP remains correct after a monotone adversary adds in-cluster edges and deletes cross-cluster edges, provided the original optimizer is unique.The robustness follows from feasibility-implied bounds |Y_ij|≤1 and the direction of the adversarial changes.
3 Planted dense subgraph model
For a planted dense subgraph with one cluster of size proportional to n, the paper characterizes the sharp exact-recovery threshold and shows that SDP attains it. The section also contrasts this linear-size regime with sublinear cluster sizes, where computational difficulty can separate statistical and polynomial-time recovery.
- Recovery threshold: For ρf(a, b) > 1, SDP achieves exact cluster recovery in polynomial time with probability tending to one; for ρf(a, b) < 1, every estimator fails asymptotically.The threshold ρf(a, b) = 1 is therefore sharp and is plotted for several values of ρ.
- Estimator: The maximum-likelihood estimator maximizes the number of in-cluster edges, while removing the rank-one constraint from its matrix formulation yields the SDP relaxation.For a > b, the estimator uses arg max; for a < b, arg min is used, and the estimator otherwise needs only the cluster size K as a model parameter.
- Optimality: The SDP recovery threshold is optimal: above the stated condition it succeeds with probability 1 − n^-Ω(1), while below the converse condition every estimator's success probability tends to zero.
- Scope and computational boundary: When K grows sublinearly in n, SDP need not attain the statistical optimum, and under planted-clique hardness there can be a gap between information and computational limits.In contrast, for K proportional to n and p, q = Θ(log n/n), SDP attains the statistically optimal threshold in polynomial time.
4 Proofs
The proofs combine random-matrix spectral bounds, binomial tail estimates, concentration, and stochastic comparison to establish the SDP recovery results. They also characterize conditions supporting exact recovery and show uniqueness of the SDP solutions.
- Proof ingredients: The proof uses random-matrix symmetrization, Seginer’s spectral-norm result, binomial tail bounds, and concentration inequalities.A second-order stochastic comparison transfers the analysis from general bounded entries to an Erdős-Rényi comparison matrix.
- Spectrum of Erdős-Rényi random graphs: Theorem 5 bounds the centered spectral norm by c′√(np) with probability at least 1−n^−c under logarithmic sparsity and bounded edge means.The result applies to symmetric, zero-diagonal random matrices with independent [0,1]-valued upper-triangular entries.
- Spectrum of Erdős-Rényi random graphs: The condition p=Ω(log n/n) is necessary to ensure the centered spectral norm is Ω_P(√(np)); the upper bound p≤1−c1 is unnecessary for G(n,p).This identifies the sparsity regime in which the spectral estimate has the stated scale.
- SDP recovery proofs: The SDP solution is shown to be unique in both the binary symmetric stochastic block model and the planted dense subgraph formulation.The proofs conclude uniqueness for the respective SDP optimizers under their stated conditions.
- Planted dense subgraph model: For the planted dense subgraph lower-bound argument, isolated vertices create multiple likelihood maximizers, preventing exact recovery by any estimator.The proof also uses events controlling within-cluster and cross-cluster edge counts to establish ML failure.
A The sharpness of the condition for Theorem 5
The condition in Theorem 5 is sharp in the sparse regime: below the stated logarithmic scale, the centered adjacency matrix has diverging normalized spectral norm. The proof uses a basis-vector lower bound and independent contributions from the upper-right block.
- The sparse condition p=o(log n …) makes ∥A−E[A]∥/√(np) diverge in probability.
- The spectral norm is lower-bounded by the largest norm of (A−E[A])e_i over standard basis vectors.
- The argument focuses on the upper-right part of A after assuming n is even.
- Independence of the variables {X_i} is used to establish the relevant probability bound.
- The final inequality follows from the preceding bound in (36).