Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection

1.1 Background

• SDP addresses the failure of spectral methods on bounded-degree random graphs, whose leading eigenvectors can localize around high-degree vertices instead of revealing global structure.This motivates replacing adjacency-matrix spectral analysis with a positive-semidefinite relaxation.Source: §1.1 · p. 2

1.2 Main results (I): Erdős-Rényi and regular random graphs

• The SDP is designed to overcome high-degree irregularities in sparse Erdős-Rényi graphs, while retaining the known connection between SDP values and extremal cuts.The diagonal constraint helps rule out highly localized eigenvectors.Source: §1.2 · pp. 3–4
• For Erdős-Rényi graphs with large bounded degree, SDP has a sharply characterized value with exponentially high probability, and its error term is quantitatively bounded by Cd^2/5 log(d).The theorem gives probability at least 1 − C e−n/C, while the stated asymptotic includes an o_d term controlled by the displayed bound.Source: §1.2 · pp. 3–4
• Random regular graphs achieve the corresponding centered-adjacency SDP value at the spectral scale, supporting the conclusion that Erdős-Rényi and regular graphs behave similarly for SDP.The paper explicitly interprets the Erdős-Rényi result as dependence primarily on average degree.Source: §1.2 · p. 4

1.3 Main results (II): Hidden partition problem

• For the hidden-partition problem, the SDP-based test succeeds with high probability when d=(a+b)/2 is sufficiently large, with error at most Ce−n/C.The result concerns testing an Erdős-Rényi null against a two-community planted-partition alternative.Source: §1.3 · pp. 4–5
• The SDP is nearly optimal in the large-bounded-degree regime, whereas naive spectral testing is sub-optimal by an unbounded factor when d=O(1).For fixed a and b, the paper states that the SDP threshold does not coincide with the optimal one; approximate partition estimation is nevertheless also addressed.Source: §1.3 · p. 5

1.4 Notations

• The paper uses standard asymptotic notation, ordered eigenvalue notation, and high-probability statements throughout its four introductory subsections.These conventions distinguish n-asymptotics from d-asymptotics such as o_d(1).Source: §1.4 · pp. 5–6

• Earlier results on classical SDPs for sparse random graphs were not tight, while SDP hierarchy analyses typically established only one-sided bounds.Source: §2 · p. 6
• Prior community-detection SDP results focused mainly on exact recovery at diverging degrees, with optimal-threshold guarantees obtained through dual-witness arguments.Source: §2 · p. 6
• [GV14] required (a−b)^2 ≥104(a+b), far above the information-theoretic threshold (a−b)^2 > 2(a+b), leaving SDP's true sparse-graph performance unresolved.Source: §2 · p. 6
• The paper develops a higher-rank Grothendieck inequality, smoothing, interpolation, and sharp Gaussian-matrix SDP analysis to address this gap.Source: §2 · pp. 6–7

3 Proof strategy

• The proof replaces SDP(M) by a differentiable log-partition function Φ(β, k; M), then controls smoothing and rank-truncation errors uniformly in dimension.The construction uses rank-constrained vectors on a sphere and satisfies limβ→∞ Φ(β, k; M)=OPTk(M), with OPTn(M)=SDP(M).Source: §3 · pp. 7–8

3.2 Interpolation

• A Lindeberg-style interpolation compares centered sparse-graph matrices with Gaussian matrices, using differentiability of Φ to control the comparison.For community detection, the Gaussian deformation uses mean shift λ/n with λ=(a−b)/(2d), where d=(a+b)/2.Source: §3 · p. 7, §3.2 · p. 9

3.1 Higher-rank Grothendieck inequalities and zero-temperature limit

• The higher-rank Grothendieck inequality bounds |OPTk(M)−SDP(M)| for centered adjacency and Gaussian matrices, yielding relative error O(1/k) under comparable SDP scales.Source: §3.1 · pp. 8–9
• The inequality is needed because the centered adjacency matrix is strongly indefinite, making existing positive-semidefinite results too weak for the application.Source: §3.1 · pp. 8–9

3.3 SDPs for Gaussian random matrices

• The SDP therefore has a phase transition at λ=1, matching the leading-eigenvalue transition below the threshold, while the eigenvalue upper bound is expected to be non-tight above it.Source: §3.3 · p. 10
• For deformed GOE matrices, SDP(B(λ))/n lies within ε of 2 when λ≤1, while for λ>1 it exceeds 2 by a positive Δ(λ).Source: §3.3 · p. 10
• Unlike the leading-eigenvalue transition, the SDP transition for B′=λvvT+W is expected to depend on the spike vector v, particularly its spikiness.Source: §3.3 · p. 10

4.1 Estimation

• The estimation setting encodes the hidden partition by ±1 labels and permits zero-valued vertex estimates.Below the information threshold, prior work shows every estimator has vanishing correlation with the ground truth.Source: §4.1 · p. 11
• For large bounded average degree, the randomized SDP estimator achieves a nearly optimal estimation threshold.The estimator is built from eigenvectors of one graph split and selected using another independently randomized edge subset.Source: §4.1 · p. 11

4.2 Robustness

• The SDP-based test remains successful after an adversary modifies o(n) edges, provided the perturbed distributions can be coupled to the originals with o(n) edge disagreement.The resulting error probability vanishes as n tends to infinity.Source: §4.2 · p. 11

4.3 Multiple communities

• For r hidden communities, the model uses within-community probability a/n and across-community probability b/n, with average degree d = [a + (r −1)b]/r.The same SDP relaxation and test do not require knowing r, and succeed with exponentially small error for sufficiently large d under the theorem’s condition.Source: §4.3 · p. 12

A Proofs of Theorem 1 and Theorem 3 (main theorems)

• The proofs combine a general approximation theorem with technical lemmas controlling centered adjacency matrices, deformed Gaussian matrices, and SDP-related quantities.The appendix derives the main theorems from these approximation and concentration ingredients.Source: A Proofs of Theorem 1 and Theorem 3… · p. 18, §A.1 · pp. 18–19

A.1 Three technical lemmas

• A higher-rank SDP analysis uses Gibbs measures, moment-generating bounds, Gaussian isoperimetry, and bounded-differences concentration.These lemmas provide the probabilistic controls needed in the appendix proofs.Source: §A.1 · p. 18

A.2 A general approximation result

• Theorem 8 establishes a high-probability approximation between the SDP on the centered sparse graph matrix and the corresponding deformed GOE matrix.The bound holds uniformly for sufficiently large n, with failure probability at most C e^(-n/C).Source: §A.2 · p. 20

A.3 Proofs of Theorem 1

• For the Erdős–Rényi null model, the approximation is specialized through λ = 0 and the GOE comparison to recover the SDP value used in Theorem 1.The resulting claim holds with high probability and the stated concentration bound.Source: §A.3 · p. 21

A.4 Proofs of Theorem 3

• For the planted two-community model, the proof controls false positives under the null and false negatives under the alternative using monotonicity and the approximation theorem.The error probability vanishes once d exceeds a threshold depending on ε.Source: §A.4 · pp. 21–22
• The concentration argument strengthens the detection guarantee to an error probability bounded by C e^(-n/C).The constant depends on the model parameters a and b.Source: §A.4 · p. 22

B Proof of Theorem 2 (SDP for random regular graphs)

• The constructed lower bound matches the spectral upper bound, completing the asymptotic characterization of the SDP value.The upper bound uses the almost-Ramanujan property of random regular graphs.Source: B Proof of Theorem 2 (SDP for random… · p. 22
• The proof constructs a feasible SDP point from Gaussian wave functions on the infinite d-regular tree and transfers the construction to finite random regular graphs.The process can be approximated by a linear factor of independent Gaussian variables, making it localizable.Source: B Proof of Theorem 2 (SDP for random… · p. 22
• The localized construction produces a positive semidefinite matrix with unit diagonal and the desired objective value.Local weak convergence of random regular graphs to the regular tree supports the finite-graph calculation.Source: B Proof of Theorem 2 (SDP for random… · p. 23

C Proof of Theorem 4 (Grothendieck-type inequality)

• An SDP solution is written as inner products of unit vectors, converting the matrix optimization into a vector representation.This is the starting point for the higher-rank rounding argument.Source: C Proof of Theorem 4… · p. 24
• A Gaussian matrix projects each vector into a lower-dimensional representation before applying the rounding construction.The projection matrix has independent Gaussian entries with variance 1/k.Source: C Proof of Theorem 4… · p. 24
• The technical lemma computes the expected rounded inner products, which supplies the correlation guarantee needed by the SDP lower bound.The proof expands the Gaussian products and substitutes the resulting identity into the objective comparison.Source: C Proof of Theorem 4… · pp. 24–25
• Applying the argument to both M and −M yields the two-sided inequality claimed by the theorem.The resulting expression coincides with the target bound.Source: C Proof of Theorem 4… · p. 25

• The partition function links the free energy to Φ(β, k; M) through Φ(β, k; M) = (1/β) log Z(β, k; M).Source: D Proof of Lemma 3.2 (zero-temperature… · p. 25
• A spherical-cap probability estimate bounds the contribution from configurations near an optimizer σ∗.The cap volume is expressed using a Beta-distributed random variable.Source: D Proof of Lemma 3.2 (zero-temperature… · p. 26
• Substituting the cap estimate and using OPT_k(M) = H_M(σ∗) yields the desired bound after taking logarithms.Source: D Proof of Lemma 3.2 (zero-temperature… · p. 26

E Proof of Lemma 3.3 (interpolation)

• The planted groups are fixed as two equal subsets, and a sign vector encodes their membership for the interpolation argument.Source: E Proof of Lemma 3.3 (interpolation) · p. 26
• An intermediate Gaussian matrix is introduced with variances determined separately for within-group and across-group pairs.Source: E Proof of Lemma 3.3 (interpolation) · p. 26

E.1 Proof of Lemma E.1

• Lindeberg interpolation compares the centered adjacency variables with Gaussian variables having matching first two moments, while controlling third moments.Source: §E.1 · pp. 27–28
• The comparison uses derivatives of the free energy under an associated Gibbs measure and applies bounds on the resulting moment sums.Source: §E.1 · pp. 27–28

E.2 Proof of Lemma E.2

• A coupling of Gaussian matrices with different variance profiles, together with operator-norm and GOE eigenvalue estimates, establishes the second comparison bound.Source: §E.2 · p. 29

F.1 Two technical lemmas

• For the deformed GOE matrix B(λ), the SDP value is monotone in λ, and random Haar subspace projections provide concentration estimates used in the proof.Source: F Proof of Theorem 5.(a) (deformed GOE… · p. 30, §F.1 · p. 30

F.2 Proof of Theorem 5.(a)

• The proof reduces the lower bound for SDP(B(λ)) to the λ = 0 case using monotonicity, then constructs a feasible witness for W ∼ GOE(n).Source: §F.2 · pp. 30–31
• The witness is built from the top nδ eigenvectors of W and a diagonal normalization matrix.Source: §F.2 · p. 31
• The random eigenvector basis is Haar-distributed, allowing concentration bounds to control the witness normalization uniformly over coordinates.Source: §F.2 · p. 31
• The normalization error vanishes asymptotically, while GOE spectral limits and nuclear-norm bounds yield the lower bound on the SDP objective.Source: §F.2 · pp. 31–32

G Proof of Theorem 5.(b) (deformed GOE matrices, λ > 1)

• The deformed GOE matrix is analyzed through its ordered eigenpairs, with λ restricted to a bounded interval above 1 and operator-norm control holding with high probability.The proof invokes standard GOE eigenvalue bounds and uses the spectral separation λ + λ^-1 > 2.Source: G Proof of Theorem 5.(b) (deformed GOE… · pp. 32, 33, 35
• Theorem 5.(b) is proved using a capped, eigenvector-based witness X that is positive semidefinite with unit diagonal, then lower-bounding its objective value with high probability.The construction uses the leading eigenvector and a block of subsequent eigenvectors, with small parameters ε and δ.Source: G Proof of Theorem 5.(b) (deformed GOE… · pp. 32, 34

G.2 Proof of Lemma G.4

• Lemma G.4 states that there exists a finite constant C > 0 such that, for all δ, ε > 0, ⟨u_i, F B F u_i⟩ ≥ L(ε, δ) for every i ∈ {2, …, nδ + 1}.Source: G Proof of Theorem 5.(b) (deformed GOE… · p. 34

G.1 A law of large numbers for the eigenvectors of deformed Wigner matrices

• The eigenvector law of large numbers shows that projections of non-leading eigenvectors behave like a uniformly random orthonormal pair in the subspace orthogonal to the planted direction, with high-probability moment bounds.Rotational invariance and Gaussian Gram–Schmidt representations reduce the argument to concentration and union bounds over polynomial observables.Source: §G.1 · pp. 35, 37

G.2 Proof of Lemma G.4

• For each i ∈ {2, …, n^δ + 1}, the proof combines eigenvalue bounds and projection estimates to obtain ⟨u_i, F B F u_i⟩ ≥ 2 − 2ε² − Cδ^(2/3) − Cε⁴.The bound follows from Lemmas G.7 and G.8, and a union bound over i completes the lemma.Source: §G.2 · p. 42

H.1 A rounding lemma

• If X_0 is symmetric binary, E(X_0Y) ≥ ε > 0, and E(Y^2) = 1, some threshold t* makes the ternary rounding s_t(X_0Y) retain correlation at least ε^2/4.The proof defines Z = X_0Y, averages E[s_t(Z)] over a bounded threshold interval, and selects a threshold attaining the stated bound.Source: §H.1 · pp. 42–43

I Proof of Corollary 4.1 (robustness)

• The proof treats two coupled graph instances as independent because their shared-edge discrepancy is only O(1) with high probability, producing negligible error.The resulting SDP perturbation is o(n) with high probability.Source: §H.2 · p. 43, I Proof of Corollary 4.1 (robustness) · p. 45

H.2 Proof of Theorem 6

• The planted adjacency matrix is represented as a rank-one signal plus a centered symmetric noise matrix with independent off-diagonal entries.The within-community edge probabilities are a/n and the across-community probability is b/n.Source: §H.2 · p. 43
• The proof compares the SDP value for the centered noise matrix with that of a suitably scaled Gaussian random matrix.The comparison is stated as a high-probability estimate for a GOE matrix.Source: §H.2 · p. 43
• At least one constructed estimator has good correlation with the planted partition, and the algorithm selects such a pair with high probability using a concentration lemma.The selected estimator satisfies |⟨x̂(I,J), x0⟩| ≥ n∆2(ε)/8 on the relevant high-probability events.Source: §H.2 · pp. 44–45

J Proof of Theorem 7 (testing r > 2 communities)

• For d ≥ d∗(ε), the SDP-based test T(·;δ∗) succeeds with high probability.The false-positive analysis uses Theorem 1, while false negatives are controlled by the SDP-to-deformed-GOE approximation and analysis.Source: J Proof of Theorem 7 (testing r > 2… · pp. 45–46

J.1 Proof outline for Theorem 10

• The deformed signal matrix has rank r−1 with all nonzero eigenvalues equal to one, and the witness is built from leading and subsequent eigenvectors.The construction produces X ∈ PSD1(n) and achieves ⟨B,X⟩/n ≥ 2 + ∆(λ,r) with high probability.Source: J Proof of Theorem 7 (testing r > 2… · p. 46, §J.1 · p. 47

J Proof of Theorem 7 (testing r > 2 communities)

• The approximation uses a rank-constrained SDP, a finite-temperature smoothing argument, and Lindeberg replacement of the centered adjacency matrix by the Gaussian model.This extends the proof strategy through a higher-rank Grothendieck-type bound and interpolation steps.Source: J Proof of Theorem 7 (testing r > 2… · p. 46
• If λ > 1, the deformed GOE model has SDP value at least n(2 + ∆(λ,r)) with probability tending to one.The positive gap ∆(λ,r) is the key signal-dependent separation used in the multi-community analysis.Source: J Proof of Theorem 7 (testing r > 2… · p. 46
• For λ ≥ 1 + ε, the graph SDP is lower-bounded by transferring the result from the deformed GOE model with high probability.The proof selects δ∗(ε)=∆(1+ε)/2 to obtain a positive separation.Source: J Proof of Theorem 7 (testing r > 2… · p. 47