PaperlayerView exact revision on arXiv

Source-linked AI summary

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

Bruce Hajek, Yihong Wu, Jiaming Xu

arXiv:1502.07738v3stat.MLcs.SImath.PR

TL;DR

Prior SDP results established sharp exact-recovery thresholds for two equal-sized clusters and for a single cluster with outliers, leaving broader cluster configurations to examine. This paper extends SDP threshold guarantees to several such settings and gives a sufficient recovery condition for general fixed-number clusters with outliers.

  • Problem

    Earlier sharp SDP recovery results covered two equal-sized clusters and a single cluster with outliers, motivating threshold analysis for additional cluster structures.

    Source: §1 · p. 2

  • Method

    The paper extends SDP recovery analysis to asymmetric two-cluster, fixed-number equal-cluster, and censored-block settings, and studies adaptive procedures for unknown cluster sizes.

    Source: §1 · p. 2

  • Results

    SDP attains the optimal recovery threshold in the three extended settings, while the general unequal-cluster-plus-outlier case has a sufficient condition within a factor of eight of the necessary bound.

    Source: §1 · p. 2, §6 · p. 11

  • Takeaways & Limitations

    The results demonstrate SDP relaxation as a versatile, computationally feasible approach to community detection across the stated settings.

    Source: §6 · p. 11

    For fixed-number unequal clusters with outliers, the sufficient condition is within a factor of eight of the necessary bound, and whether SDP attains the optimal threshold remains open.

    Source: §6 · p. 11

Abstract

from arXiv · show

Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: (1) Binary stochastic block model with two clusters of sizes proportional to network size but not necessarily equal; (2) Stochastic block model with a fixed number of equal-sized clusters; (3) Binary censored block model with the background graph being Erd\H{o}s-R\'enyi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection.

1 Introduction

The paper extends sharp exact-recovery guarantees for SDP beyond two equal-sized clusters and a single cluster with outliers. It treats asymmetric two-cluster, fixed-number equal-cluster, and censored-block settings, and gives additional recovery guarantees when cluster sizes are unknown.

1 Introduction

  • Earlier work established the optimal recovery threshold for two equal-sized clusters and for a single cluster with outliers; the equal-sized result was conjectured in and independently resolved in.These results assume p = a log n/n and q = b log n/n, with fixed a, b and cluster sizes growing linearly in n.Source: §1 · pp. 1–2
  • The paper extends SDP optimality to two asymmetric clusters, a fixed number of equal-sized clusters, and the binary censored block model with an Erdős-Rényi background graph.For two asymmetric clusters, the size may be known or unknown; the extensions assume p = a log n/n and q = b log n/n with a > b > 0.Source: §1 · p. 2
  • Across these three settings, the ML estimator's necessary recovery condition matches a sufficient condition for SDP correctness, establishing the optimal threshold and SDP optimality.The paper also resolves an open problem about the censored block model's optimal threshold and shows that SDP achieves it in polynomial time.Source: §1 · p. 2
  • For two clusters, a cluster-size-independent Lagrangian achieves recovery at the equal-sized threshold for all sizes; for unequal clusters with outliers, SDP has a sufficient condition using the smallest cluster size and a, b.The general unequal-size case requires only the smallest cluster size and parameters a, b as input to the procedure.Source: §1 · p. 2

2 Binary asymmetric SBM

For two asymmetric clusters with known size, the SDP reaches the exact-recovery threshold, which is impossible to improve on. With unknown size, a penalized SDP achieves the balanced-case threshold without a size constraint, with a slower error-probability decay for the data-driven penalty choice.

2.1 Known cluster size

  • When η(ρ, a, b) > 1, the known-size SDP recovers exactly with high probability; when η(ρ, a, b) < 1, every estimator fails under a uniform prior.The matching achievability and converse establish the optimal recovery threshold for the known-size setting.Source: §2.1 · pp. 4–5

2.2 Unknown cluster size

  • Without a cluster-size constraint, a penalized SDP achieves the balanced-case threshold (√a − √b)^2 > 2 for all cluster sizes.The penalty parameter depends on a and b, although a data-driven choice is also available for linearly scaling cluster sizes.Source: §2.2 · p. 5
  • For the data-driven penalty choice, the error probability vanishes polylogarithmically rather than polynomially as n → ∞.This is the stated cost of adaptivity.Source: §2.2 · p. 5

3 SBM with multiple equal-sized clusters

For a fixed number of equal-sized clusters, the paper establishes optimal exact recovery by SDP. It also extends SDP threshold optimality to a specified regime with a logarithmically growing number of clusters.

3 SBM with multiple equal-sized clusters

  • The SDP relaxes discrete cluster assignments to unit vectors whose pairwise inner products are constrained to be at least −1/(r − 1).The discrete assignments use the vertices of an equilateral simplex to represent the r clusters.Source: §3 · p. 6
  • For equal-sized clusters, the SDP has a sufficient condition for exact recovery, and a converse establishes the procedure's optimality.The converse states that under its condition, any sequence of estimators fails to recover the partition with probability tending to one.Source: §3 · p. 7
  • For any fixed γ, a, b > 0 and s ∈ [0, 1), SDP achieves the optimal recovery threshold.Source: §3 · p. 7

4 Binary censored block model

The section formulates maximum-likelihood recovery and its SDP relaxation for the binary censored block model, then establishes that the SDP reaches the optimal exact-recovery threshold. The threshold is insensitive to the cluster proportion, and a converse shows recovery is impossible below it.

4 Binary censored block model

  • The maximum-likelihood objective uses signed edges to favor within-cluster positive edges and cross-cluster negative edges, but is computationally intractable in the worst case.The passage notes that max-cut reduces to this objective.Source: §4 · p. 8
  • The SDP is formed by replacing the rank-one constraint on the cluster matrix with positive semidefiniteness.The cluster labels are represented by a sign vector, and their outer product gives the rank-one matrix.Source: §4 · p. 8
  • Above the stated threshold, the SDP recovers the true cluster matrix with probability tending to one; below it, every estimator fails with probability tending to one.The SDP guarantee is uniform over true cluster matrices, while the converse is stated for a uniformly chosen true partition.Source: §4 · p. 8
  • The SDP relaxation achieves the optimal exact-recovery threshold for the binary censored block model, with the threshold insensitive to the cluster proportion.The authors state that the result holds for fixed ε and compare this insensitivity with the binary stochastic block model.Source: §4 · pp. 8–9
  • The section notes that the optimal threshold for fixed ε and its polynomial-time attainability were previously unknown for this model.Earlier work established the ML threshold as ε approaches 1/2, while its SDP guarantee required a stronger condition.Source: §4 · p. 9

5 An SDP for general cluster structure

This section gives sufficient recovery conditions for SDPs handling multiple clusters of varying sizes, with or without outliers. It also describes the information needed by two SDP formulations and compares a simpler explicit condition with necessary bounds.

5 An SDP for general cluster structure

  • The unpenalized SDP avoids needing a, b, the cluster count, or individual cluster sizes, but requires the exact sum and sum of squares of cluster sizes.The penalized alternative drops those two constraints but requires specifying η* and λ*.Source: §5 · pp. 9–10
  • Either of the two SDPs recovers the cluster matrix with probability at least 1−n^−Ω(1) when the sufficient inequalities of Theorem 8 hold.The theorem requires positive ψ1 and ψ2 with b+ψ1+ψ2<a; some inequalities can be dropped in the stated special cases.Source: §5 · p. 10
  • Given a lower bound ρmin on the cluster proportions and enough information to implement an SDP, recovery is guaranteed when I(b,b+ψ)>1/ρmin.ψ solves I(a,b+2ψ)=I(b,b+ψ).Source: §5 · p. 10
  • A simpler explicit sufficient condition is within a factor of four of the necessary condition with outliers and within a factor of eight without them.The comparison concerns the sufficient condition derived using the explicit choice of ψ.Source: §5 · pp. 10–11

6 Conclusions

The conclusions report asymptotically optimal SDP recovery in several community-detection settings and a sufficient guarantee for a more general setting. The general case of clusters with varying sizes plus outliers remains less settled.

6 Conclusions

  • SDP relaxations achieve asymptotically optimal recovery for two unequal clusters, a fixed number of equal-sized clusters, and the binary censored block model with an Erdős–Rényi background.The paper presents these results as extensions beyond two equal-sized clusters or one cluster with outliers.Source: §6 · p. 11
  • The authors characterize SDP relaxation as a simple, general-purpose, computationally feasible methodology for community detection.This conclusion follows their reported results across the listed settings.Source: §6 · p. 11
  • For varying-size clusters plus outliers, an SDP achieves exact recovery without knowing cluster sizes under a sufficient condition within a factor of eight of the necessary bound.Whether the SDP attains the optimal threshold in this general case is posed as an open problem in the paper.Source: §6 · p. 11

7 Proofs

This section proves exact-recovery results for asymmetric and multiple-cluster SBMs and censored block models, using tail and spectral-norm bounds, SDP dual certificates, and deterministic uniqueness conditions. It also analyzes when maximum-likelihood recovery fails.

7.1 Proofs for Section 2: Binary asymmetric SBM

  • A tail-bound lemma for the difference of binomial counts supplies the vertexwise estimates used to bound the SDP certificate’s diagonal entries.The proof applies these estimates to vertices in each cluster before using a union bound.Source: §7.1 · pp. 11, 12, 17
  • Under η(ρ,a,b)>1, a dual-certificate argument establishes that the SDP uniquely recovers the planted partition with high probability.The proof verifies positive semidefiniteness and a positive second eigenvalue for the certificate.Source: §7.1 · pp. 14, 17
  • When η(ρ,a,b)<1, swapping vertices between the two clusters yields a strictly higher likelihood with probability tending to one, so maximum likelihood fails.The proof bounds the relevant events for each cluster and shows both occur with probability tending to one.Source: §7.1 · pp. 17–18
  • In Theorem 3’s proof, the true clusters have cardinalities K_n and n−K_n, and the proof considers every 0≤K_n≤n; when K_n=0 or n, Y*=J and the graph is G(n,p).Source: §7.1 · p. 18
  • For the asymmetric SBM proof, Talagrand’s inequality controls the relevant Lipschitz quantities, and the remaining argument follows the proof of Theorem 1.The Lipschitz constants are bounded by O(log^(1/4) n).Source: §7.1 · p. 20

7.2 Proofs for Section 3: Multiple equal-sized clusters

  • A certificate satisfying the stated matrix conditions makes the planted clustering the unique solution of the multiple-cluster SDP.The proof shows every feasible solution has objective no larger than the planted solution, with equality forcing the planted matrix.Source: §7.2 · p. 22
  • The multiple-cluster converse reduces recovery of two clusters to the two-cluster problem by revealing all other cluster memberships to a genie.The resulting argument establishes an impossibility result for exact recovery under the stated parameter condition.Source: §7.2 · p. 24

7.3 Proofs for Section 4: Binary censored block model

  • For the censored block model, the proof establishes a high-probability spectral-norm bound of order sqrt(np) for A − E[A].The bound is developed under np ≥ c0 log n, with constants depending on the stated parameters.Source: §7.3 · pp. 24–25
  • The censored-model analysis also derives upper and lower tail bounds for sums of signed Bernoulli variables when m = n + o(n) and p = a log n/n.The lemmas consider thresholds k_n of order log n.Source: §7.3 · pp. 25–26
  • Under its stated deterministic sufficient condition for a > b, SDP (13) uniquely recovers Y*.Source: §7.3 · p. 27
  • For ε = 0 and a < 1, isolated vertices make exact-recovery probability vanish; for ε > 0, event F yields ML failure with high probability under the stated condition.Source: §7.3 · pp. 28–29

7.4 Proofs for Section 5: General cluster structure

  • A dual certificate satisfying the lemma’s conditions makes Z* the unique optimizer of both SDPs (15) and (16).The certificate conditions include positive semidefiniteness and a positive (r + 1)th smallest eigenvalue.Source: §7.4 · pp. 29–30
  • Theorem 8’s certificate is built by controlling minimum within-cluster degrees and maximum cross-cluster edges, ensuring its conditions hold with high probability.Source: §7.4 · pp. 31–32
  • For μ > 0 and x > 0, I(μ, μ + 2x) ≤ 4I(μ, μ + x).Source: §7.4 · p. 32

A Behavior of threshold function in (4)

For the asymmetric binary SBM, the threshold function η(ρ, a, b) is symmetric about ρ = 1/2 and convex in ρ, so it is minimized at equal cluster sizes.

A Behavior of threshold function in (4)

B A data-driven choice of the penalization parameter in (5)

This section selects the penalization parameter from the observed graph by estimating quantities that determine its appropriate value. The estimates support the stated penalty choices in balanced and unbalanced cases.

B A data-driven choice of the penalization parameter in (5)

Related papers

Loading 1502.07738v3…