PaperlayerView exact revision on arXiv

Source-linked AI summary

Tightness and Error Exponents of SDP with Logarithmically Many Communities

Shengtao Guo, Ethan X. Fang, Junwei Lu

arXiv:2610.09303v1math.STcs.ITmath.ITstat.TH

TL;DR

The paper asks how tightness failure affects the information retained by a balanced-community SDP as the number of communities grows logarithmically. It characterizes the tightness boundary and local error, and shows exact label recovery remains possible from SDP output in the spectrally stable region.

  • Problem

    For logarithmically many balanced communities, the sharp behavior of the SDP relaxation is unresolved despite prior guarantees for fixed or sublogarithmic community counts.

    Source: §1 · p. 1

  • Method

    The paper analyzes the balanced cluster-matrix SDP through degree-margin fluctuations, a spectral-noise correction, and matching bounds on error and objective gain.

    Source: §1 · pp. 1–2

  • Results

    When a > 2σ, tightness is governed by I(τ), and in the local failure region normalized matrix error and objective gain share exponent I(τ).

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    For a > 2σ and I(0) > 1, one SDP solve followed by row clustering and refinement recovers all labels with high probability, even when the planted matrix is not optimal.

    Source: §1 · p. 2

    The analysis concerns the balanced SDP at fixed α, β, and γ; critical cases and finite-sample behavior remain open.

    Source: §6 · p. 9

Abstract

from arXiv · show

We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with $n=km$ vertices, we consider the regime $k/\log m\to\gamma>0$, with edge probabilities $\alpha\log m/m$ within communities and $\beta\log m/m$ across them, for fixed $\alpha>\beta>0$. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.

1 INTRODUCTION

The paper studies whether the balanced-community SDP remains tight when the number of communities grows logarithmically, and what information remains when tightness fails. It identifies sharp tightness and error behavior, and shows that SDP output can still support exact label recovery in the spectrally stable region.

1 INTRODUCTION

  • In the spectrally stable region, tightness holds when I(τ) > 1, while the planted matrix is not optimal when I(τ) < 1.The local correction τ accounts for surrounding spectral noise in a vertex’s degree margin.Source: §1 · p. 1
  • When tightness fails locally, normalized matrix error and objective gain both scale as m^-I(τ)+oP(1), uniformly for feasible solutions within one of optimal.The exponent is governed by the frequency of vertices with degree margins below the correction τL.Source: §1 · pp. 1–2
  • A single SDP solve followed by row clustering and refinement recovers all labels with high probability when a > 2σ and I(0) > 1, even if the planted matrix is not optimal.The condition I(0) > 1 is the information-theoretic exact-recovery condition.Source: §1 · p. 2
  • In the bulk regime a < 2σ, near-optimal matrices have asymptotically zero normalized overlap with the planted matrix, a result that alone does not rule out label recovery.The paper leaves whether SDP output permits label recovery in this regime unresolved.Source: §1 · p. 2
  • The upper and lower error bounds share an exponent because both depend on the number of vertices with degree margins near τL.The proof uses a Schur complement and dual-certificate adjustments for upper bounds, and forests rooted at low-margin vertices for the matching lower bound.Source: §1 · p. 2
  • Earlier work established sufficient conditions or constant-factor recovery regimes, while this analysis identifies sharp constants for the balanced SDP and logarithmically many communities.The paper builds on prior sharp-error and planted-dual-certificate approaches to obtain matching bounds in this regime.Source: §1 · pp. 2–3

2 MODEL AND MAIN RESULTS

The paper specifies the balanced SBM and its cluster-matrix SDP, then characterizes tightness, local error, optimal value, and planted overlap. The results distinguish local failure from bulk spectral failure and leave stated critical cases unresolved.

2.1 MODEL, SDP, AND ERROR MEASURES

  • The model has n = km vertices in fixed communities of size m, with within- and between-community probabilities αL/m and βL/m for fixed α > β > 0.The SDP maximizes ⟨A, Z⟩ subject to positive semidefiniteness, entrywise nonnegativity, unit diagonal, and row sums m.Source: §2.1 · p. 3
  • The paper measures SDP behavior using normalized matrix error, objective gain, and planted overlap; tightness means the planted matrix is the unique optimizer.The degree-margin lower-tail rate I(x) and correction τ describe the local fluctuations relevant to the boundary and error exponent.Source: §2.1 · pp. 3–4

2.2 TIGHTNESS AND THE LOCAL ERROR EXPONENT

  • Away from critical cases, the planted matrix is the unique optimizer with high probability when a > 2σ and I(τ) > 1; it is not optimal when a ≥ 2σ and I(τ) < 1.The theorem makes no assertion at a = 2σ with I(σ) ≥ 1 or at a > 2σ with I(τ) = 1.Source: §2.2 · p. 4
  • When a > 2σ and r = I(τ) is in (0, 1), normalized matrix error and objective gain have matching exponent r, with high probability.The error bound holds uniformly over feasible solutions whose objective is within one of the optimum; the exponent reflects rare vertices with margins below τL.Source: §2.2 · p. 4

2.3 OPTIMAL VALUE AND PLANTED OVERLAP

  • When a < 2σ, near-optimal solutions have normalized planted overlap tending to zero, while the normalized objective gain tends to 2σ − a and normalized matrix error tends to one.When a > 2σ, near-optimal solutions instead have overlap tending to one; at a = 2σ, the proposition gives no overlap guarantee.Source: §2.3 · p. 5

3 ESTABLISHING THE SHARP ERROR EXPONENT

The section proves matching upper and lower bounds for matrix error and objective gain, with both governed by low-margin vertices near the corrected margin τL. Its proof links that correction to the upper-bound diagonal repair and the lower-bound Gram construction.

3 ESTABLISHING THE SHARP ERROR EXPONENT

  • Both normalized matrix error and objective gain have matching exponent I(τ), governed by vertices with margins near τL.The upper and lower bounds share this exponent.Source: §3 · p. 5, Figure 2 · p. 5, §3.4 · p. 8

3.1 THE CORRECTION TO THE DEGREE MARGIN

  • Eliminating the surrounding coordinates reduces a vertex’s effective margin by τL to leading order.For a positive-definite background block, the reduction is the quadratic form b^T C^-1 b; when the background diagonal is zL, it is τ_z L to leading order.Source: §3.1 · pp. 5–6

3.2 UPPER BOUNDS FROM THE DUAL CERTIFICATE

  • Increasing small dual-certificate diagonals restores positive semidefiniteness and bounds the error and objective gain through the total adjustment.Degree-margin tail estimates bound the total diagonal adjustment, yielding the matrix-error upper bound uniformly over near-optimal feasible solutions.Source: §3.2 · pp. 6–7

3.3 A GRAM CONSTRUCTION FOR THE LOWER BOUND

  • The finite-step Gram construction turns a positive quadratic gain into a feasible SDP improvement while enforcing row sums and entrywise nonnegativity.The resulting feasible matrix can have rank O(k).Source: §3.3 · p. 7

3.4 MATCHING LOWER BOUNDS FROM LOW-MARGIN VERTICES

  • For the matching lower bound, many low-margin vertices serve as roots for balanced, fixed-depth trees that reproduce the correction τ and yield positive objective gain.Pairing active communities and growing trees from roots with margins at most xL, for x < τ, produces the construction.Source: Figure 2 · p. 5, §3.4 · pp. 7–8

4 LABEL RECOVERY BEYOND TIGHTNESS

A single near-optimal SDP solution can seed row clustering and iterative neighbor-based refinement. In the spectrally stable region, this procedure recovers all labels under the information-theoretic condition, even when the planted matrix is not optimal.

4 LABEL RECOVERY BEYOND TIGHTNESS

  • When a > 2σ and I(0) > 1, row clustering followed by refinement recovers all labels up to permutation with high probability from any feasible SDP matrix within 1 of optimal.The procedure uses A and the known community size m, then performs ⌈log2 n⌉ + 2 simultaneous neighbor-label updates.Source: §4 · p. 8
  • Row clustering first yields o(m) mislabeled vertices in total, after which refinement contracts the error set until no errors remain.A wrongly labeled vertex after an update must have at least dL/2 neighbors in the preceding error set, while sufficiently small sets span too few edges to sustain many such vertices.Source: §4 · pp. 8–9
  • The contraction argument holds simultaneously over sufficiently small vertex sets, so it does not require independence between initialization and refinement on the same graph.The paper also gives an upper bound on label error with exponent I(0).Source: §4 · p. 9

5 NUMERICAL ILLUSTRATIONS OF THE ASYMPTOTIC FORMULAS

The numerical illustrations evaluate the asymptotic regime formulas along one parameter cut and show distinct tightness, recovery, and bulk boundaries. They do not report finite-sample SDP experiments.

5 NUMERICAL ILLUSTRATIONS OF THE ASYMPTOTIC FORMULAS

  • Along (α, β) = (4.25, 1), I(0) ≈ 1.1269 > 1, the tightness boundary is γ ≈ 0.55515, and the bulk boundary is γ = 2.640625.Figure 1 gives representative values in the three regimes.Source: §5 · p. 9
  • At γ = 1, matrix error and normalized objective gain have exponent approximately 0.8923, while postprocessing recovers all labels; at γ = 3, normalized objective gain converges to approximately 0.2141 and planted overlap tends to zero.The local error exponent does not apply at γ = 3 because τ is not real.Source: §5 · p. 9
  • The formulas are asymptotic illustrations, not finite-sample SDP experiments; such experiments would require optimization and feasibility errors below the scales being measured.Matrix error, objective gain, and label error would need to be measured on the same graphs.Source: §5 · p. 9

6 DISCUSSION

The discussion separates matrix tightness from the information needed for label recovery. It also states that the analysis is specific to the balanced SDP and leaves several questions unresolved.

6 DISCUSSION

  • At the local tightness boundary, small-margin vertices begin to change the SDP optimum, yet postprocessing still recovers labels when a > 2σ and I(0) > 1.In the bulk regime a < 2σ, the unnormalized objective gain is of order nL and normalized planted overlap tends to zero.Source: §6 · p. 9
  • The analysis covers the balanced SDP at fixed α, β, γ; critical cases, multiplicative error prefactors, and finite-sample behavior remain open.Whether the SDP output permits label recovery in the bulk regime is also unresolved.Source: §6 · p. 9
  • The bulk boundary concerns this relaxation and does not establish a computational lower bound for community recovery.Source: §6 · p. 9

A PROBABILITY AND RANDOM-MATRIX INPUTS

The appendix develops probability and random-matrix bounds, then uses a marked-resolvent dual analysis to establish unique SDP optimality above the tightness boundary. Its estimates control low-margin vertices and their dependence on the same graph.

A PROBABILITY AND RANDOM-MATRIX INPUTS

  • Degree-margin tail and count estimates, centered-norm and degree bounds, and their conditional versions supply the probability and random-matrix inputs.The bounds remain valid after conditioning on any fixed number of specified edge values.Source: A PROBABILITY AND RANDOM-MATRIX INPUTS · pp. 12–13

B DUAL ANALYSIS AND UPPER BOUNDS

  • If the dual form is positive on every nonzero vector in H, the planted community matrix is the unique SDP optimizer.The certificate's equality case forces any optimal feasible matrix to equal the planted matrix.Source: B DUAL ANALYSIS AND UPPER BOUNDS · pp. 13–14

B.1 THE MARKED-RESOLVENT ESTIMATE

  • The resolvent restricted to marked low-margin vertices is controlled in operator norm, accounting for the fact that the marked set depends on the graph.For fixed radius, marked neighborhoods are trees with high probability and contain only a bounded number of marks.Source: §B.1 · p. 15

B.2 UNIQUE OPTIMALITY ABOVE THE TIGHTNESS BOUNDARY

  • When a > 2σ and I(τ) > 1, the dual analysis proves unique SDP recovery with high probability.The proof separates small-diagonal vertices and uses a Schur complement together with the marked-resolvent estimate.Source: §B.2 · pp. 16–17

B.3 MATRIX-ERROR BOUNDS FROM THE DUAL CERTIFICATE

The dual certificate is repaired by increasing small diagonal entries, and the size of this adjustment controls both objective gain and error. This gives high-probability upper bounds for near-optimal solutions in the spectrally stable regime.

B.3 MATRIX-ERROR BOUNDS FROM THE DUAL CERTIFICATE

  • Increasing small dual-diagonal entries restores positive semidefiniteness, and the total adjustment bounds matrix error and objective gain.The marked-resolvent estimate permits adjustment only below a threshold arbitrarily close to τL.Source: §B.3 · pp. 17–18
  • The uniform upper bounds control both optimal objective gain and the error of every sufficiently near-optimal feasible matrix through the total diagonal adjustment.The argument chooses thresholds near τ and bounds the adjustment using the low-margin count.Source: §B.3 · pp. 18–19
  • For (α, β, γ) = (5, 1, 3), I(0) ≈ 1.528, I(τ) ≈ 0.834, and I(2σ) ≈ 0.024; the coarse argument has a much smaller limiting rate than the local error law.The local error law uses I(τ), while the coarse initialization bound can approach I(2σ).Source: §B.3 · p. 19, Figure 3 · p. 19

C FINITE-STEP GRAM CONSTRUCTION

The lower-bound construction builds a feasible Gram-matrix perturbation from balanced forests rooted at low-margin vertices. Finite-depth weights reproduce the local correction and yield an objective gain, with the step size constrained by the energy margin.

C FINITE-STEP GRAM CONSTRUCTION

  • The finite-step Gram construction yields a feasible matrix with objective gain at least δtLE/2 for a fixed positive step t.Mixing two Gram matrices preserves the constraints while correcting negative entries; the step size may shrink as δ approaches zero.Source: C FINITE-STEP GRAM CONSTRUCTION · pp. 19, 21

D MULTI-ROOT FORESTS AND MATCHING LOWER BOUNDS

  • With high probability, at least M/2 groups of roots have disjoint depth-R forests balanced across active communities.The construction reserves roots and discards failed groups; fewer than half fail with high probability, without requiring independence between groups.Source: D MULTI-ROOT FORESTS AND MATCHING… · pp. 21–22

D.1 THE CENTERED FOREST VECTOR AND ITS QUADRATIC FORM

  • The centered forest vector has matching coordinate multisets across active communities, meeting the structural conditions for the Gram construction.The uniform degree bound and forest estimates verify the assumptions needed for the objective-gain argument.Source: §D.1 · pp. 22–23

D.2 CHOOSING THE WEIGHTS

  • Optimizing finite-depth weights produces correction τR − x, which is positive for sufficiently large fixed R whenever x < τ.The resulting forest construction reproduces the correction τ to any fixed accuracy.Source: Figure 4 · p. 23

D.3 NONOPTIMALITY IN THEOREM 2.1

The appendices construct feasible SDP matrices to show nonoptimality and match upper bounds on objective gain and matrix error. They also develop a polynomial Gram-matrix construction satisfying the SDP constraints.

D.3 NONOPTIMALITY IN THEOREM 2.1

  • When a ≥ 2σ and I(τ) < 1, a low-margin vertex yields a feasible matrix with strictly larger objective than the planted matrix.The construction uses a vertex with margin at most xL for a fixed x < τ with I(x) < 1.Source: §D.3 · p. 23

D.4 LOWER BOUNDS ON THE OBJECTIVE GAIN AND MATRIX ERROR

  • Both the normalized objective gain and matrix error have lower bounds of order m^−I(τ)−ε for every near-optimal feasible matrix, with high probability.The bounds hold simultaneously for all feasible matrices whose objective is within one of the optimum.Source: §D.4 · p. 24

E MACROSCOPIC OPTIMAL VALUE AND OVERLAP

  • The macroscopic-value argument pairs an upper bound uniform over feasible matrices with a feasible polynomial Gram-matrix construction.The construction must satisfy row sums and entrywise nonnegativity in addition to the other SDP constraints.Source: E MACROSCOPIC OPTIMAL VALUE AND OVERLAP · p. 24

E.1 AN OBJECTIVE BOUND UNIFORM OVER THE FEASIBLE SET

  • Degree-deviation control and the SDP row-sum and nonnegativity constraints yield a uniform objective upper bound over feasible matrices.The resulting bound is used to establish the required upper bound for the optimal value.Source: §E.1 · pp. 24–25

E.2 FIXED-DEGREE POLYNOMIAL MOMENTS

  • For each fixed polynomial degree, normalized adjacency-matrix moments converge to the corresponding semicircle moments.The argument controls the contribution of exceptional vertices and keeps radii and polynomial degrees fixed as m grows.Source: §E.2 · p. 25

E.3 EXACT CONSTRAINTS FOR THE POLYNOMIAL GRAM MATRIX

  • A shifted-adjacency polynomial gives greater weight to upper-edge eigenvalues, and its Gram matrix is adjusted to satisfy the SDP constraints.Projection removes the all-ones direction; diagonal correction then preserves positive semidefiniteness while enforcing unit diagonal and row sums.Source: §E.3 · p. 25

E.4 THE OBJECTIVE VALUE AND OVERLAP

Near-optimal matrices have limiting planted overlap one above the bulk threshold and zero below it. The section also describes row clustering and same-graph refinement, with a deterministic rounding guarantee and a uniform sparsity event for small vertex sets.

E.4 THE OBJECTIVE VALUE AND OVERLAP

  • As the polynomial degree R increases, the weighted spectral density shifts toward the upper edge, and its mean gives the limiting noise value.For fixed R ≥ 1, this mean is the limiting noise value of the centered Gram matrix H.Source: §E.4 · p. 26, Figure 5 · p. 27
  • For a > 2σ, every feasible matrix within o(nL) of the optimum has normalized planted overlap tending uniformly to one; for a < 2σ, that overlap tends uniformly to zero.The objective deficit bounds force the respective overlap limits.Source: §E.4 · p. 26

F ROW CLUSTERING AND SAME-GRAPH REFINEMENT

  • Row clustering followed by refinement uses only the graph and known community size, and its small-error event holds simultaneously for graph-dependent initial and refined labels.This permits initialization and each refinement step to use the same graph.Source: F ROW CLUSTERING AND SAME-GRAPH… · p. 27

F.1 A DETERMINISTIC ROW-CLUSTERING GUARANTEE

  • When 8D/m < m/2, deterministic row rounding completes all k stages and makes at most 8D/m label errors, up to permutation.Here D is the entrywise ℓ1 distance from the planted matrix.Source: §F.1 · p. 27

F.2 UNIFORM SPARSITY OF SMALL VERTEX SETS

  • Lemma F.2 establishes a high-probability uniform sparsity event for small vertex sets.Its proof controls the probability over possible set sizes and vertex sets.Source: §F.2 · p. 28

F.3 SYNCHRONOUS REFINEMENT

Synchronous refinement repeatedly reduces errors under a uniform small-set condition, while the threshold analysis identifies the community-ratio boundary for SDP tightness. The boundary depends on the smallest degree margins and the bulk spectral condition.

F.3 SYNCHRONOUS REFINEMENT

  • Under the small-set event, refinement keeps every iterate small and gives a final error count bounded by 2Bd after the prescribed rounds.The recurrence is hT ≤ h0/2^T + 2Bd; when Bd = 0, the illustrated bound reaches zero.Source: §F.3 · p. 29, Figure 6 · p. 29
  • The label-error result provides a high-probability upper bound with exponent I(0), but no matching lower bound or expected-risk guarantee.For the SDP matrix error, Theorem 2.2 instead gives matching bounds with exponent I(τ).Source: §F.3 · p. 29

G INFORMATION BENCHMARK AND THRESHOLD CONSEQUENCES

  • The critical community ratio is derived from the tightness theorem and compared with the information-theoretic threshold.The analysis also describes the boundary as the background parameter grows.Source: G INFORMATION BENCHMARK AND THRESHOLD… · p. 30

G.1 EXTREME MARGINS AND THE CRITICAL COMMUNITY RATIO

  • When Iα,β(0) > 1, the smallest margin divided by log m converges to x*, defined by Iα,β(x*) = 1; the critical ratio separates high-probability tightness from nonoptimality.For fixed γ below γ_SDP, the planted matrix is the unique optimizer with high probability; above γ_SDP, it is not optimal with high probability.Source: §G.1 · p. 30

G.2 THE INFORMATION THRESHOLD AND THE SDP GAP

The section establishes an information-theoretic recovery benchmark and shows a gap between that benchmark and SDP tightness, then characterizes the sequential large-background boundary and fixed-parameter geometry.

G.2 THE INFORMATION THRESHOLD AND THE SDP GAP

  • For every fixed β, γ > 0, a nonempty interval above the information threshold permits exact recovery while the planted matrix is not SDP-optimal.The gap persists in an open neighborhood under the strict conditions.Source: §G.2 · p. 31

G.3 THE LARGE-BACKGROUND LIMIT

  • After taking the graph limit first, δ > f(γ) gives a unique SDP optimizer and δ < f(γ) gives nonoptimality for all sufficiently large fixed β.The proposition does not cover β = β_m → ∞, and the finite-β junction can differ from the sequential-limit junction.Source: §G.3 · p. 32

H FIXED-PARAMETER GEOMETRY AND FIGURE EVALUATION

H.1 MONOTONICITY AND THE LOCAL–BULK JUNCTION

  • For fixed β and γ, the tightness boundary is unique: it is the bulk boundary when its rate is at least one, otherwise the larger local-rate root.The local and bulk branches meet at a unique junction.Source: §H.1 · p. 33

H.2 THE SMALL-RATIO EXPANSION

  • As γ ↓ 0, the local boundary has a positive initial slope whose limit as β grows is 1/4.Figure 8 compares boundaries for β = 1, 4, and 16 and plots the slope coefficient cβ.Source: §H.2 · p. 34, Figure 8 · p. 34

H.3 EVALUATION OF THE THEORETICAL CURVES

The numerical figures evaluate analytic formulas rather than sampled graphs or SDP solutions. The comparison section clarifies how prior models, feasible sets, and recovery objectives differ from the setting studied here.

H.3 EVALUATION OF THE THEORETICAL CURVES

  • The numerical checks validate theoretical formulas and recurrences; they use no sampled graphs or numerical SDP solutions.Checks include boundary roots, rate functions, spectral densities, and refinement bounds.Source: §H.3 · p. 34

I COMPARISON OF MODELS AND FEASIBLE SETS

  • Comparisons require matching parameter scalings and feasible sets; a theorem for fixed a_old cannot be applied directly when that parameter grows with m.For p = a_old log n/n, the corresponding parameter in this scaling is a_old = αk log m / log n.Source: I COMPARISON OF MODELS AND FEASIBLE SETS · p. 34
  • Agarwal et al. (2015) and Hajek et al. (2016a) study the same SDP, but prior sufficient conditions do not determine its sharp boundary at every fixed positive ratio.The present analysis identifies the boundary at each fixed positive ratio.Source: I COMPARISON OF MODELS AND FEASIBLE SETS · pp. 34–35
  • Chen & Xu (2016) use a larger feasible set: their unique recovery implies recovery by this SDP, but their nonoptimality result need not transfer back.Their sufficient condition has leading form a² ≥ c(α + βγ), with an unspecified universal constant c.Source: I COMPARISON OF MODELS AND FEASIBLE SETS · p. 35
  • Fei & Chen (2019a) give exponential error bounds for the same relaxation, while Theorem 2.2 here determines the matching exponent I(τ) in this scaling.Source: I COMPARISON OF MODELS AND FEASIBLE SETS · p. 35
  • The cited growing-community KS results use independent labels and different recovery criteria; their signal-to-noise comparison does not establish a computational threshold for this balanced model.Transferring them would require control under exact-balance conditioning and a change from weak to exact recovery.Source: I COMPARISON OF MODELS AND FEASIBLE SETS · p. 36

Related papers

Loading 2610.09303v1…