acceptodds
Under review as a conference paper at ICLR 2027

Tightness and Error Exponents of SDP with Logarithmically Many Communities

Abstract

We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with vertices, we consider the regime , with edge probabilities within communities and across them, for fixed . 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.

Primary area:
learning theory
Keywords:
stochastic block model, semidefinite programming, community detection, exact recovery, error exponents, random matrix theory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.83 over 6 reviews, above 85% of the others.
Reviewer_6zprOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper theoretically studies SDP for community recovery in a balanced SBM with k≈γlog⁡mk \approx \gamma \log m communities. It establishes sharp conditions for SDP tightness (a>2σa > 2\sigma and I(τ)>1I(\tau) > 1), characterizes the recovery error and phase transition, and shows that SDP with rounding and refinement can achieve exact recovery even when the SDP solution is not tight. The paper contains no experiments.

Critical strengths

Previous work provided only sufficient conditions with unspecified constants (Agarwal et al., 2015) or established failure for large γ\gamma (Hajek et al., 2016a). Theorem 2.1 establishes a sharp SDP tightness threshold for every fixed γ>0\gamma > 0 when k≍log⁡mk \asymp \log m. The result substantially improves upon previous bounds and provides a clear explanation through the local margin correction τL\tau L.

The upper and lower bounds identify the same correction term τ\tau, leading to a matching exponent I(τ)I(\tau). This supports the sharpness of the theoretical results. The proofs are technically rigorous, and the main arguments appear sound.

The paper also shows that failure of SDP tightness does not necessarily imply failure of exact recovery. When a>2σa > 2\sigma and (α−β)2>1(\sqrt{\alpha} - \sqrt{\beta})^2 > 1, exact recovery remains achievable through SDP, rounding, and refinement, even when Z∗Z^* is not optimal. The guarantees also hold for near-optimal solutions without requiring sample splitting.

Critical weaknesses

The results are limited to a balanced SBM with known community sizes and k=Θ(log⁡m)k = \Theta(\log m). The asymptotic convergence is slow, and the paper lacks numerical experiments to demonstrate whether the theoretical thresholds are observable at practical graph sizes.

Corollary 4.1 mainly builds on existing rounding and refinement techniques, offering limited technical novelty. Moreover, the paper does not establish recovery guarantees when a<2σa < 2\sigma, even though exact recovery may be information-theoretically possible. This gap deserves further discussion.

Some technical discussions, particularly around Proposition 3.1, are rather brief and difficult to follow. A clearer explanation of the main proof ideas would improve the paper's readability.

Questions for authors
  1. Notation is overloaded:

    • SS is both the slack matrix and the small-diagonal vertex set within the same proofs (B.25–B.32, Lemma B.4).
    • DD is the dual diagonal, the degree margins, a constant in Appendix C, and the ℓ1\ell_1 distance in Lemma F.1.
    • QQ is both the projection Z∗/mZ^*/m and the quadratic form Q(y)Q(y).
    • MM, TT, rr, η\eta, θ\theta, and ℓ\ell are reused in several roles.
  2. Proposition 3.1 uses SuS_u, while Appendix B.1 uses StS_t.

  3. Section 3.1: “adopt these estimates” should be “adapt”.

  4. Figure 1(a) uses δ=α−β\delta = \sqrt{\alpha} - \sqrt{\beta} while the text works in (a,σ)(a,\sigma); the caption should state the conversion.

4 comments

Thank you for your careful review and for identifying places where the explanation and notation can be clearer. The sharp tightness boundary and matching error exponent are the central contributions. We have now added a 180-graph boundary experiment (Sec. 5; Secs. K.1–K.2), a direct explanation of label recovery (Sec. 4), and clarifications of the proof and notation (Secs. 3.1 and B.1).

W1. Model scope and finite-size behavior.

The results are limited to a balanced SBM with known community sizes and k=Θ(log⁡m)k=\Theta(\log m).

The balanced SBM is a widely studied benchmark for SDP community recovery (Agarwal et al., 2015; Hajek et al., 2016; Fei and Chen, 2019; Appendix I). This setting lets us analyze, at comparable scales, unusually small degree margins at individual vertices and spectral noise across the graph. Their interaction determines the sharp SDP boundary and matching error exponent. We have added calculations for unequal sizes and degree heterogeneity in Sec. J.5, with sensitivity experiments in Sec. K.3, Table 2. We plan to explore sharp SDP guarantees for these more general models (Sec. 6).

The asymptotic convergence is slow, and the paper lacks numerical experiments to demonstrate whether the theoretical thresholds are observable at practical graph sizes.

We have now solved the SDP on 180 graphs with 900 vertices: (m,k,β)=(75,12,1)(m,k,\beta)=(75,12,1), nine signal levels and twenty seeds each (Sec. 5, Fig. 3). Already at 900 vertices, the observed matrix-recovery transition is close to the sharp asymptotic boundary, with label recovery occurring earlier as predicted.

Counts below are out of twenty graphs. Matrix recovery uses the numerical unique-optimality checks in Sec. K.2; refinement uses the smallest-label tie rule.

α\alphaMatrix recoveryLabels after roundingLabels after refinement
3.50,3.753.50,3.750/200/200/20
4.004.000/200/201/20
4.254.250/202/201/20
4.334  Sufficient condition
4.504.500/209/203/20
4.754.750/2017/2010/20
5.005.0012/2020/2016/20
5.149Sharp boundary  
5.255.2518/2020/2019/20
5.505.5020/2020/2020/20

Matrix recovery rises from 12/20 at α=5.0\alpha=5.0 to 18/20 at 5.25 and 20/20 at 5.5, near the sharp asymptotic boundary 5.149. Above the label reference 4.334, refinement succeeds on 3/20, 10/20, and 16/20 graphs at α=4.5,4.75,5.0\alpha=4.5,4.75,5.0. The bold rows mark asymptotic references; 4.334 is Corollary 4.1's sufficient condition under its feasibility and accuracy assumptions.

At α=4.75\alpha=4.75, feasible objective improvements show that the planted matrix is suboptimal on all twenty graphs, yet rounding recovers every label on seventeen and refinement on ten. Table 1 reports matrix errors, objective-gain intervals, label errors, and numerical gaps on the same graphs (Sec. K.1). We plan to quantify convergence rates as graph size grows (Sec. 6).

References

  • Agarwal, N., Bandeira, A. S., Koiliaris, K., and Kolla, A. (2015). Multisection in the Stochastic Block Model Using Semidefinite Programming. arXiv:1507.02323v1.
  • Hajek, B., Wu, Y., and Xu, J. (2016). Semidefinite Programs for Exact Recovery of a Hidden Community. COLT, PMLR 49:1051–1095.
  • Fei, Y., and Chen, Y. (2019). Exponential Error Rates of SDP for Block Models: Beyond Grothendieck's Inequality. IEEE Transactions on Information Theory, 65(1):551–571. Author version: arXiv:1705.08391v1.

W2. Postprocessing contribution and bulk recovery.

Corollary 4.1 mainly builds on existing rounding and refinement techniques, offering limited technical novelty.

Our contribution is to prove that the SDP itself supplies sufficiently accurate starting labels beyond matrix tightness, and that refinement can recover every label using the same graph. When a>2σa>2\sigma and I(0)>1I(0)>1, Corollary 4.1 gives this guarantee with high probability, simultaneously for every feasible input with objective at least Vm−1V_m-1. The proof controls all sufficiently small error sets at once, accounting for the dependence between SDP initialization and subsequent updates. We have made the matrix-to-label bound explicit in Sec. 4; Appendix I compares the guarantee with established clustering and refinement methods.

Moreover, the paper does not establish recovery guarantees when a<2σa<2\sigma, even though exact recovery may be information-theoretically possible.

The condition a>2σa>2\sigma is sufficient for our label-recovery guarantee when I(0)>1I(0)>1. Our new experiments also find accurate labels beyond this range: at (α,β,m,k)=(4.25,1,75,12)(\alpha,\beta,m,k)=(4.25,1,75,12), we have a=3.25<2σ≈3.334a=3.25<2\sigma\approx3.334 and I(0)>1I(0)>1, while row rounding achieves 99.67% mean label accuracy, with exact labels on 2/20 graphs (Sec. K.1, Table 1). We plan to study how this finite-size performance scales with graph size and develop recovery guarantees for actual SDP outputs in the asymptotic bulk regime (Secs. 6, J.4).

W3. Explanation of Proposition 3.1.

Some technical discussions, particularly around Proposition 3.1, are rather brief and difficult to follow. A clearer explanation of the main proof ideas would improve the paper's readability.

We have rewritten the proof roadmap after Proposition 3.1 in Sec. 3.1. It connects local walk counts to uniform row-sum control, explains the passage to centered noise, and states how the spectral bound controls the remaining resolvent terms. Detailed configuration counts and mean-removal estimates remain in Sec. B.1.

Q1. Overloaded notation.

Notation is overloaded:

Thank you for identifying these conflicts. We have revised the notation where it is used in the text and proofs.

SS is both the slack matrix and the small-diagonal vertex set within the same proofs (B.25–B.32, Lemma B.4).

The dual slack matrix is now Λ\Lambda throughout Sec. 3.2 and Appendix B. The vertex sets retain Su\mathcal S_u, S\mathcal S, and T\mathcal T.

DD is the dual diagonal, the degree margins, a constant in Appendix C, and the ℓ1\ell_1 distance in Lemma F.1.

We retain D∗D^* for the dual diagonal and use Δi,s\Delta_{i,s} for degree margins, CdegC_{\mathrm{deg}} for the block-degree bound in Appendix C, and RZR_Z for matrix distance in Lemma F.1. The normalization matrix in Sec. E.3 is now N\mathsf N.

QQ is both the projection Z∗/mZ^*/m and the quadratic form Q(y)Q(y).

We retain Q=Z∗/mQ=Z^*/m for the projection and use Φ(y)\Phi(y) for the Gram energy in Sec. 3.3 and Appendix C.

MM, TT, rr, η\eta, θ\theta, and ℓ\ell are reused in several roles.

We have separated the conflicting uses at their definitions and throughout the corresponding arguments:

ObjectsRevised notation and location
Root count / auxiliary matricesNrootN_{\mathrm{root}} in Sec. 3.4 and Appendix D; MD,MzM_D,M_z in B.2
Off-block mass / Gram perturbation / refinement roundsBoutB_{\mathrm{out}} in B.3; HmixH_{\mathrm{mix}} in Appendix C; NiterN_{\mathrm{iter}} in F.3
Marked-set sparsity / Gram mixing / small-set sparsityηmark\eta_{\mathrm{mark}}, ηmix\eta_{\mathrm{mix}}, ηsmall\eta_{\mathrm{small}} in B.1, C, and F.2
Exponential tilting / planted overlapλ\lambda in A.1, G.3, and H.1; θm(Z)\theta_m(Z) in Sec. 2.1
Positive lower bound / moment order / forest levelℓmin⁡\ell_{\min} in Sec. 3.3 and Appendix C; ν\nu in B.1; ℓ\ell in Sec. 3.4 and Appendix D

The error exponent remains r=I(τ)r=I(\tau); neighborhood radii use RR. Ordinary community indices are defined locally.

Q2. Marked-set parameters.

Proposition 3.1 uses SuS_u, while Appendix B.1 uses StS_t.

We now use the same threshold uu and marked set Su\mathcal S_u throughout Proposition 3.1 and its proof in B.1.

Q3. Word correction.

Section 3.1: “adopt these estimates” should be “adapt”.

We have removed that wording in the rewritten explanation in Sec. 3.1. Thank you for catching this.

Q4. Figure 1 parameter conversion.

Figure 1(a) uses δ=α−β\delta=\sqrt\alpha-\sqrt\beta while the text works in (a,σ)(a,\sigma); the caption should state the conversion.

We have added the parameter conversion to Figure 1's caption. Its signal coordinate is the square-root gap δ=α−β\delta=\sqrt\alpha-\sqrt\beta, which gives

$ \alpha=(\delta+\sqrt\beta)^2,\qquad a=\alpha-\beta=\delta^2+2\delta\sqrt\beta,\qquad \sigma=\sqrt{\beta\gamma}. $

Thank you again for your time and thoughtful suggestions!

Thank you for your response. I will keep my score.

Reviewer_6HcuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies when an SDP exactly outputs the planted communities matrix in a regime of stochastic block models with k=Θ(log⁡n)k = \Theta(\log n) communities, and when it cannot exactly output the planted communities matrix, does it input contain enough information to recover the communities? The main technique is to use SDP dual certificates to establish exact recovery. The main result shows that even when the optimal solution of the SDP does not match the planted matrix, the error converges to 00 when n→∞n\rightarrow \infty. By that, the exact recovery can be done via rounding and other refinement. This regime suggest that when only a mall fraction of the vertices have low degrees and hence, being misplaced the plated Z∗Z^* is not optimal, the community structure of ZZ remains intact.

Critical strengths
  • The paper establishes a sharp condition for the SDP tightness for the planted matrix to be the optimal solution for the regime of k=Θ(n)k = \Theta(n)
  • Produce exact recovery even when the planted matrix is not the optimal soultion of the SDP, by rounding and refinement via row clustering.
Critical weaknesses
  • The technique is built on top of established techniques (SDP dual certificates (Hajek et al 2015), rounding, local refinement), leaving the main technical contribution to the sharp analysis, not a new exact recovery algorithm.
  • The asymptotic analysis does not establish hidden constants, making it unclear on how large nn needed for the exact recovery to be materialized.
  • The bulk-dominated regime only states the distance between the optimal solution of the SDP to the planted matrix, not the recoverability (such as the lower bound by Abbel et al, Hajek et al).
  • The error bound is via the distance of ZZ and Z∗Z^* (matrix error), but the main objective of exact recovery is the fraction of recovered community labels (label error).
Questions for authors

Please address the 2nd and the 4th bullet point of the weaknesses.

2 comments

Thank you for your careful review and questions about the sharp analysis and label recovery. We have added explicit constants and finite-graph refinement conditions (Secs. J.1–J.2), actual SDP experiments (Sec. 5; Appendix K), and an explicit matrix-to-label bound (Sec. 4).

W1. Technical contribution.

The technique is built on top of established techniques (SDP dual certificates (Hajek et al 2015), rounding, local refinement), leaving the main technical contribution to the sharp analysis, not a new exact recovery algorithm.

Our contribution is the sharp analysis of this established SDP: we determine when it recovers the true matrix, the matching matrix-error exponent when it fails, and when its output still permits exact labels. The same local correction τ\tau links the tightness boundary and error exponent.

The technical difficulty is that the low-margin vertices are selected from the same graph whose noise affects their interaction. We control this dependence and construct a competing matrix satisfying every SDP constraint to prove the matching lower bound (Sec. 3). We have clarified the order of limits in Sec. 3.1, made the matrix-to-label conversion explicit in Sec. 4, and explained the relationship to established methods in Appendix I.

W2. Constants and finite-size onset.

The asymptotic analysis does not establish hidden constants, making it unclear on how large nn needed for the exact recovery to be materialized.

We have now added explicit initialization constants and finite-graph refinement conditions (Secs. J.1–J.2), together with a 900-vertex experiment (Sec. 5). Already at 900 vertices, the observed matrix-recovery transition is close to the sharp asymptotic boundary, with label recovery occurring earlier as predicted.

For a>2σa>2\sigma, set κ=(a−2σ)/4\kappa=(a-2\sigma)/4 and u=(3a+2σ)/4u=(3a+2\sigma)/4. For sufficiently large mm, on the spectral and diagonal-repair events in Sec. J.1, every feasible input within objective gap sms_m satisfies

$ \mathcal E_m(Z)\leq\frac{2}{\kappa}m^{-I(u)/2}+\frac{s_m}{\kappa n\log m}. $

This makes the dependence on signal strength and solver accuracy explicit. Prop. J.1 permits sm=o(mlog⁡m)s_m=o(m\log m) for exact label recovery when a>2σa>2\sigma and I(0)>1I(0)>1.

Sec. J.2 also gives conditions that ensure refinement succeeds on a finite graph:

ConditionRequired bound
Initial errorsAt most HH vertices
True degree marginsAt least dlog⁡m>0d\log m>0 at every vertex
Edges within each nonempty set UU of at most 2H2H verticesFewer than c∣U∣log⁡mc\lvert U\rvert\log m, with c<d/12c<d/12

Under these conditions, every round at least halves the errors until none remain. Sec. J.2 supplies finite-model probability bounds for the margin and small-set conditions. We plan to quantify the spectral and initialization events to obtain graph-size requirements at a chosen success probability.

Our new experiment solves the SDP on 180 graphs with (m,k,β)=(75,12,1)(m,k,\beta)=(75,12,1), twenty seeds at each signal level. Counts below are out of twenty; matrix recovery uses the numerical unique-optimality checks in Sec. K.2, and refinement uses the smallest-label tie rule (Fig. 3):

α\alphaMatrix recoveryLabels after roundingLabels after refinement
3.50,3.753.50,3.750/200/200/20
4.004.000/200/201/20
4.254.250/202/201/20
4.334  Sufficient condition
4.504.500/209/203/20
4.754.750/2017/2010/20
5.005.0012/2020/2016/20
5.149Sharp boundary  
5.255.2518/2020/2019/20
5.505.5020/2020/2020/20

Matrix recovery rises near the sharp asymptotic boundary 5.149; above the label reference 4.334, refinement success rises from 3/20 to 10/20 and 16/20 at α=4.5,4.75,5.0\alpha=4.5,4.75,5.0. The bold rows are asymptotic references; 4.334 is Corollary 4.1's sufficient condition under its feasibility and accuracy assumptions. At α=4.75\alpha=4.75, feasible objective improvements verify that the planted matrix is suboptimal on all twenty graphs, yet rounding recovers every label on seventeen and refinement on ten. Table 1 reports matrix errors, gain intervals, label errors, and numerical gaps on the same graphs.

W3. Recoverability in the bulk regime.

The bulk-dominated regime only states the distance between the optimal solution of the SDP to the planted matrix, not the recoverability (such as the lower bound by Abbel et al, Hajek et al).

We have clarified in Secs. 6 and J.4 that Proposition 2.3 characterizes the SDP objective and normalized overlap, while label recovery from its output is a further question. Overlap summarizes total within-community mass; finer differences between entries can still encode labels even as normalized overlap tends to zero (Sec. J.4). With growing community count, even the uninformative feasible reference has overlap approximately 1/k1/k, tending to zero.

Our new bulk-side experiment shows that row rounding achieves 99.67% mean label accuracy, with exact labels on 2/20 graphs, at (α,β,m,k)=(4.25,1,75,12)(\alpha,\beta,m,k)=(4.25,1,75,12) (Sec. K.1, Table 1). Here a<2σa<2\sigma and I(0)>1I(0)>1. Mean SDP overlap is 0.881 versus 0.09455 for the uninformative reference. We plan to study how this advantage scales and develop recovery guarantees for actual SDP outputs in the asymptotic bulk regime (Secs. 6, J.4).

W4. From matrix error to label error.

The error bound is via the distance of ZZ and Z∗Z^* (matrix error), but the main objective of exact recovery is the fraction of recovered community labels (label error).

The matrix bound directly controls the fraction of incorrect labels after rounding; refinement then gives exact labels under Corollary 4.1's conditions. We have added this link in Sec. 4 and explained both stages in Sec. J.2.

Write RZ=∥Z−Z∗∥1,entryR_Z=\|Z-Z^*\|_{1,\mathrm{entry}} and let h0h_0 count incorrect labels after aligning community names. Whenever RZ<m2/16R_Z<m^2/16, Lemma F.1 gives

$ h_0\leq8R_Z/m=16n\mathcal E_m(Z),\qquad h_0/n\leq16\mathcal E_m(Z). $

Thus the label-error fraction is at most sixteen times the matrix error. Under Corollary 4.1's assumptions, h0=o(m)h_0=o(m), and refinement at least halves the error count each round until it reaches zero, with high probability. The bound covers all sufficiently small error sets simultaneously, allowing initialization and every update to use the same graph (Sec. F.3).

For a>2σa>2\sigma and any fixed ε>0\varepsilon>0, Prop. F.3 also bounds the refined label-error fraction by m−I(0)+εm^{-I(0)+\varepsilon} with high probability, simultaneously for every feasible input with objective at least Vm−1V_m-1. Sec. J.2 distinguishes this label-error upper bound, with exponent I(0)I(0), from the matching upper-and-lower matrix-error exponent I(τ)I(\tau).

Q1. Requested clarifications.

Please address the 2nd and the 4th bullet point of the weaknesses.

W2 gives the added constants, finite-graph conditions, and experimental recovery counts. W4 gives the explicit label-error fraction and explains how refinement reaches exact recovery.

Thank you again for your time and thoughtful suggestions!

Reviewer_4ucbOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies semidefinite programming (SDP) relaxations for community recovery in the balanced stochastic block model (SBM), focusing on the regime where the number of communities grows logarithmically with community size.

The paper's main contributions are Theorem 2.1 on SDP tightness boundaries, Theorem 2.2 on error analysis when the SDP is not tight, and Corollary 4.1 on recovery beyond SDP tightness. In Theorem 2.1, the authors characterize the conditions under which the planted community matrix is the unique optimal SDP solution. They also explain when and why tightness fails, distinguishing between failures caused by unusual connection patterns involving individual vertices and those caused by noise affecting the entire graph. In Theorem 2.2, the authors show that even when the SDP fails to recover the planted community matrix, near-optimal solutions can still remain very close to it. They provide matching theoretical bounds that characterize the magnitude of this error, as well as the improvement in the optimal SDP objective over the planted community matrix. Finally, Corollary 4.1 shows that, under certain conditions, all community labels can still be recovered exactly even when the SDP is not tight. This is achieved by clustering similar rows of the SDP solution and subsequently refining the resulting assignments.

To establish these results, the authors combine mathematical techniques for analyzing the effects of graph noise with constructions that demonstrate when and how SDP tightness can fail.

I recommend weak acceptance. The paper provides strong theoretical results on SDP tightness, offering a precise characterization of when the relaxation fails and how large the resulting error becomes.

I find it particularly interesting that the authors do not stop at characterizing when the SDP loses tightness, but also demonstrate that the resulting solutions can still be useful for exact community recovery. The theoretical analysis is technically substantial, and the proofs address several nontrivial challenges.

My main concerns are the complete absence of finite-sample experiments and the limited discussion of the computational cost of the recovery procedure. In particular, the required numerical accuracy and the scalability of solving the SDP deserve more attention.

Additionally, the restricted model assumptions and the unresolved recovery behavior outside the spectrally stable regime limit the generality of the results.

Nevertheless, I believe these limitations primarily affect the practical applicability of the proposed approach rather than the main theoretical contributions of the paper.

Critical strengths
  1. Strong theoretical contribution on SDP tightness.

Theorem 2.1 provides a sharp characterization of SDP tightness when the number of communities grows logarithmically. The authors extend existing results by identifying more precise conditions under which the SDP is tight or fails to be tight.

Furthermore, distinguishing between failures caused by individual vertices and those caused by the overall graph noise provides a better understanding of the mechanisms behind the loss of tightness.

  1. Good analysis of SDP behavior even after tightness fails.

Theorem 2.2 goes beyond simply showing that the SDP fails to recover the planted community matrix. It also quantifies how much the resulting near-optimal solutions differ from the correct matrix.

In particular, the authors provide matching upper and lower bounds on this error, demonstrating that SDP solutions can still remain close to the planted matrix even when tightness is lost.

  1. Exact community recovery even when the SDP is not tight.

Corollary 4.1 shows that failing to recover the planted community matrix directly does not necessarily imply that the community labels cannot be recovered exactly. The authors demonstrate that SDP solutions can still retain enough information to recover all labels correctly through clustering and refinement, under the required conditions.

Furthermore, the proof allows the same graph to be reused during initialization and refinement, without requiring independent data. This is a useful property that makes the proposed recovery procedure particularly interesting.

Critical weaknesses
  1. No finite-sample experiments to validate the theoretical results.

Section 5 presents numerical evaluations of the theoretical formulas, but does not include experiments performed on sampled graphs or actual SDP solutions.

My main concern is how accurately the theoretical tightness boundaries and error estimates describe the behavior of SDP on graphs of realistic sizes. Since the results are asymptotic, it remains unclear how large a graph needs to be before the predicted behavior becomes observable.

Even a small experimental evaluation using actual SDP solutions, measuring both the matrix error and the recovery performance, would help clarify the practical relevance of the theoretical results.

  1. Computational cost and required SDP accuracy are not sufficiently discussed.

Corollary 4.1 requires a feasible SDP solution whose objective value is within an additive one of the optimal value. However, the authors do not sufficiently discuss how computationally expensive it would be to achieve this level of accuracy using an actual SDP solver, especially as the graph size increases.

A more explicit discussion of the computational cost and the required optimization accuracy would improve the practical interpretation of the proposed recovery procedure.

  1. Results are restricted to a specific model and do not fully characterize recovery in all regimes.

The paper assumes communities of exactly equal size, known community sizes, and fixed parameters governing the within- and between-community connection probabilities. While these assumptions are reasonable for the theoretical analysis, they limit how easily the results can be extended to more general community detection problems.

Moreover, the exact-recovery guarantee is established only in the spectrally stable regime.

Questions for authors
  • Finite-sample behavior: Have the authors investigated how quickly the theoretical tightness boundaries and error estimates become accurate on sampled graphs? Would it be possible to include even a limited numerical evaluation using actual SDP solutions?
  • Computational efficiency: What would be the computational cost of the complete recovery procedure, including the SDP solve?
  • Recovery outside spectral stability: In the bulk regime, SDP solutions have vanishing normalized overlap with the planted matrix. Does this suggest that these solutions cannot be used for recovery, or could alternative clustering and refinement techniques still recover useful information?
2 comments

Thank you for your careful review and for highlighting recovery beyond tightness. We have added finite-graph SDP experiments, a more flexible accuracy guarantee, and a complete cost analysis. We address each question alongside the corresponding weakness below.

W1 / Q1. Finite-sample behavior.

Would it be possible to include even a limited numerical evaluation using actual SDP solutions?

We have now solved the SDP on 180 graphs with 900 vertices: (m,k,β)=(75,12,1)(m,k,\beta)=(75,12,1), nine signal levels and twenty seeds each. Our new Fig. 3 (Sec. 5) compares matrix recovery and exact labels before and after refinement on the same graphs. Table 1 reports their matrix errors, objective-gain intervals, label errors, and numerical gaps (Sec. K.1).

Have the authors investigated how quickly the theoretical tightness boundaries and error estimates become accurate on sampled graphs?

Already at 900 vertices, the observed matrix-recovery transition is close to the sharp asymptotic boundary, with label recovery occurring earlier as predicted. Counts below are out of twenty graphs. Matrix recovery uses the numerical unique-optimality checks in Sec. K.2; refinement uses the smallest-label tie rule.

α\alphaMatrix recoveryLabels after roundingLabels after refinement
3.50,3.753.50,3.750/200/200/20
4.004.000/200/201/20
4.254.250/202/201/20
4.334  Sufficient condition
4.504.500/209/203/20
4.754.750/2017/2010/20
5.005.0012/2020/2016/20
5.149Sharp boundary  
5.255.2518/2020/2019/20
5.505.5020/2020/2020/20

Matrix recovery rises from 12/20 at α=5.0\alpha=5.0 to 18/20 at 5.25 and 20/20 at 5.5, near the sharp asymptotic boundary 5.149. Above the label reference 4.334, refinement succeeds on 3/20, 10/20, and 16/20 graphs at α=4.5,4.75,5.0\alpha=4.5,4.75,5.0. The bold rows mark asymptotic references; 4.334 is Corollary 4.1's sufficient condition under its feasibility and accuracy assumptions.

At α=4.75\alpha=4.75, feasible objective improvements show that the planted matrix is suboptimal on all twenty graphs, yet rounding recovers every label on seventeen and refinement on ten. Sec. K.1 gives sampling intervals and matrix errors on the same graphs: mean normalized matrix error is 0.03087 at α=4.5\alpha=4.5 and 0.00609 at α=4.75\alpha=4.75 (Table 1). These measurements describe performance at the fixed size n=900n=900. We plan to quantify how the boundary and error estimates converge as graph size grows (Sec. 6).

W2 / Q2. Required accuracy and complete computational cost.

Corollary 4.1 requires a feasible SDP solution whose objective value is within an additive one of the optimal value.

Our new Prop. J.1 allows the objective gap to grow as sm=o(mlog⁡m)s_m=o(m\log m) while preserving exact label recovery when a>2σa>2\sigma and I(0)>1I(0)>1. For every feasible input ZZ within this gap of the optimum,

$ \mathcal E_m(Z)\leq C m^{-c}+\frac{s_m}{\kappa n\log m}. $

The second term quantifies the effect of solver accuracy. Rounding then makes at most h0≤16nEm(Z)=o(m)h_0\leq16n\mathcal E_m(Z)=o(m) errors, which refinement corrects with high probability. Sec. J.3 also bounds the effect of feasibility corrections. In our experiments, we check the constraints and numerical objective gap on the restored matrix used for rounding (Sec. K.2).

What would be the computational cost of the complete recovery procedure, including the SDP solve?

We have added the full cost in Sec. J.6:

$ T_{\rm SDP}(n,\varepsilon)+O(n^3)+O((|E|+nk)\log n). $

The terms are the SDP solve at the requested accuracy, row rounding, and all refinement rounds using adjacency lists. A dense first-order solver can spend O(n3)O(n^3) per iteration on PSD projections, with O(n2)O(n^2) matrix storage. Sec. K.4 and Table 3 report implementation timings for a separate 100-graph comparison with 80–480 vertices, including numerical checks and restoration; solver tolerances and the execution setup are specified there.

W3 / Q3. Model assumptions and bulk recovery.

The paper assumes communities of exactly equal size, known community sizes, and fixed parameters governing the within- and between-community connection probabilities.

This setting lets us distinguish failures caused by individual degree margins from those caused by spectral noise and determine the sharp SDP boundary. We have added the effects of model changes in Sec. J.5: using row sum m^\widehat m with true balanced size mm forces entrywise error at least n∣m^−m∣n|\widehat m-m|, while degree heterogeneity changes the margin rate and noise variance profile. Our new tests vary degrees within equal-sized communities and perturb community sizes (Sec. K.3, Table 2). We plan to extend the sharp SDP guarantees to these models (Sec. 6).

Does this suggest that these solutions cannot be used for recovery, or could alternative clustering and refinement techniques still recover useful information?

Normalized overlap summarizes the total within-community mass. Label recovery can use finer differences between entries, which may remain informative even as the normalized overlap tends to zero (Sec. J.4).

Our new bulk-side experiment shows that row rounding can use the remaining information at a finite size: at (α,β,m,k)=(4.25,1,75,12)(\alpha,\beta,m,k)=(4.25,1,75,12), it achieves 99.67% mean label accuracy, with exact labels on 2/20 graphs (Sec. K.1, Table 1). Here a=3.25<2σ≈3.334a=3.25<2\sigma\approx3.334 and I(0)>1I(0)>1.

Mean SDP overlap is 0.881, compared with 0.09455 for the uninformative feasible reference. Sec. J.4 explains that the reference overlap itself vanishes as kk grows. We plan to study how this finite-size advantage scales and develop label-recovery guarantees for actual SDP outputs in the asymptotic bulk regime (Secs. 6, J.4).

Thank you again for your time and thoughtful suggestions!

Reviewer_6eBSOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper discusses the SemiDefinite Programming (SDP) method in Community Detection when the number of communities KK increases logarithmically. When the communities are balanced, the paper first identifies the signal strength requirements so that the SDP optimizer is exactly the groundtruth, for which they call it as "tight". The requirement is based on the within-community signal strength, the between-community strength, and the ratio K/log⁡mK/\log m.

Next, the authors consider the case that the groundtruth is not the empirical optimizer. It is possible that some local fluctations induce such non-tightness. They have derived the error exponent in this case. Hence, using a further refinement step, they can adjust the labels for such nodes and achieve an exact recovery with high probability, even it is not tight.

Overall, I think the theoretical results and proof outlines are important in this field.

Critical strengths

Theoretical understanding of this problem. The authors do not only derive a consistency result, they have a sharp error exponent that describes the cause of the error.

Based on the reason analysis, the authors discuss the refinement step as a natural generalization.

Critical weaknesses

NA.

Questions for authors

In Section 4, the authors discuss the general community detection exact recovery problem. The authors should consider a more broadly comparison with current upper bounds, such as spectral methods. In this way, we can have a better understanding of the problem.

2 comments

Thank you for recognizing the value of the sharp error analysis and for suggesting a broader comparison! We have expanded Appendix I to compare spectral recovery guarantees at their stated assumptions and added an empirical spectral baseline in Sec. K.4.

Q1. Comparison with spectral recovery bounds.

The authors should consider a more broadly comparison with current upper bounds, such as spectral methods.

We have expanded Appendix I to compare the settings and recovery guarantees directly:

WorkSettingRecovery guarantee
Abbe et al. (2020), Thm. 3.2 in the cited author versionBinary symmetric SBMA direct eigenvector estimator attains the exact-recovery threshold.
Gao et al. (2017), Thm. 6 and Remark 8Allows growing community counts under the stated signal conditionsA spectral initializer supplies labels for refinement.
Ariu et al. (2025)Labeled SBM with fixed community count and positive fixed proportionsA spectral procedure and refinement achieve instance-optimal recovery.
Our Cor. 4.1Balanced SBM with k/log⁡m→γ>0k/\log m\to\gamma>0SDP initialization and same-graph refinement recover every label when a>2σa>2\sigma and I(0)>1I(0)>1, including beyond SDP tightness.

The growing-community comparison is particularly relevant. Gao et al.'s sufficient spectral-initialization condition requires the ratio (a′−b′)2/(a′k3)(a'-b')^2/(a'k^3) to be sufficiently large, where a′=npa'=np and b′=nqb'=nq. In our scaling,

$ \frac{(a'-b')^2}{a'k^3}=\frac{(\alpha-\beta)^2\log m}{\alpha k^2}\longrightarrow0. $

Our SDP bound supplies o(m)o(m) initialization errors in this logarithmic-community regime when a>2σa>2\sigma; same-graph refinement then recovers every label when I(0)>1I(0)>1 (Sec. 4). Theorems 2.1–2.2 additionally determine the SDP's sharp tightness boundary and matching matrix-error and objective-gain exponent.

We have also added a matched adjacency spectral comparison on 100 graphs (Sec. K.4, Table 3), using top-kk eigenvectors, kk-means, and the same refinement rule. SDP row rounding has lower mean initial label error in all five tested settings. After refinement, relative accuracy varies, while the spectral procedure is much faster in our implementation; Table 3 reports both stages and running times.

Thank you again for your time and thoughtful suggestions!

References

  • Abbe, E., Fan, J., Wang, K., and Zhong, Y. (2020). Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank. Annals of Statistics, 48(3):1452–1474. Author version: arXiv:1709.09565v2.
  • Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2017). Achieving Optimal Misclassification Proportion in Stochastic Block Models. JMLR, 18(60):1–45.
  • Ariu, K., Proutiere, A., and Yun, S.-Y. (2025). Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model. ICML, PMLR 267:1650–1689.

Thank you for the responses. I will maintain my positive score. Even though there is little data analysis in this paper, theoretical understanding is still, if not more, important.

Reviewer_zc5gOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies an SDP relaxation for community recovery in balanced stochastic block models with logarithmically many communities. It identifies the sharp tightness boundary away from critical cases and proves matching exponents for matrix error and objective gain in the spectrally stable, non-tight regime. It also characterizes the optimal objective value and planted overlap across the spectral transition. Finally, it shows that rounding and refinement can recover all labels above the information-theoretic threshold within the spectrally stable region, even when the planted matrix is not SDP-optimal.

Critical strengths
  • The paper is well written and easy to follow, with clear explanations of the main results and proof ideas.

  • The technical contributions are substantial, particularly the sharp SDP tightness boundary and matching error exponents in the logarithmic-community regime.

  • The paper deepens our understanding of SDP beyond tightness by quantifying its errors and showing that postprocessing can still achieve exact label recovery when the planted matrix is not SDP-optimal.

Critical weaknesses
  1. Please clarify the relationship between SDP tightness and exact label recovery, including when post-processing succeeds despite non-tightness. How does Theorem 2.1 differ from prior sharp recovery results allowing growing kk?

  2. The numerical section only evaluates theoretical formulas. Finite-sample SDP experiments would help show whether the predicted transitions and the separation between tightness and label recovery are observable in practice.

  3. The analysis assumes exactly balanced communities and a known community size. Please discuss how mild imbalance or misspecification of the community size might affect the conclusions.

Questions for authors
  1. Do you expect a>2σa>2\sigma to be necessary for label recovery from the SDP output, or could improved postprocessing succeed beyond this region?

  2. How does the SDP approach compare with low-rank SDP factorization [1] and projected power iteration [2] in recovery guarantees, initialization requirements, and computational cost, particularly when k≍log⁡nk\asymp\log n? Could the analysis extend to these nonconvex methods?

[1] McRae, Abdalla, Bandeira, and Boumal. “Nonconvex landscapes for Z₂ synchronization and graph clustering are benign near exact recovery thresholds.” Information and Inference, 14(2), 2025.

[2] Wang, Liu, Zhou, and So. “Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method.” ICML, 2021.

4 comments

Thank you for your careful review and for recognizing the sharp guarantees beyond SDP tightness. We have expanded the comparisons in Appendix I, added finite-graph experiments in Sec. 5 and Appendix K, and analyzed size misspecification in Sec. J.5.

W1. Tightness, labels, and prior results.

Please clarify the relationship between SDP tightness and exact label recovery, including when post-processing succeeds despite non-tightness.

Tightness asks whether solving the SDP directly gives the true community matrix as its unique solution. Exact label recovery asks whether processing the SDP output can still put every vertex in the correct community. When a>2σa>2\sigma and I(τ)<1<I(0)I(\tau)<1<I(0), the SDP does not directly recover the true matrix, but rounding and refinement recover all labels with high probability. We have added the explicit link between matrix error and the number of incorrect labels in Sec. 4.

How does Theorem 2.1 differ from prior sharp recovery results allowing growing (k)?

Agarwal et al. already give a sharp threshold when the number of communities grows more slowly than log⁡n\log n, that is, k=o(log⁡n)k=o(\log n). We address k/log⁡m→γ>0k/\log m\to\gamma>0, where their guarantee contains an unspecified constant.

For (α,β)=(4.25,1)(\alpha,\beta)=(4.25,1), we can compare the published conditions on the same scale, k/log⁡m→γk/\log m\to\gamma:

ResultWhat it guarantees for direct matrix recovery as graphs grow
Agarwal et al. (2015), Thm. 1.1Success when γ<0.005421/c2\gamma<0.005421/c^2, with an unspecified universal constant cc.
Hajek et al. (2016), Thm. 17 and eq. (23)Failure when γ>718.25\gamma>718.25.
Our Thm. 2.1Success below the boundary γ≈0.55515\gamma\approx0.55515 and failure above it.

The first two rows come from substituting these parameters into their theorems. Agarwal et al.'s constant remains unspecified, so their bound stays in terms of cc. Hajek et al.'s value is a one-sided failure bound. Our result locates the boundary between success and failure. Appendix I now compares the same SDP and assumptions in detail. Theorem 2.2 further determines how quickly matrix error decreases when direct recovery fails but the output stays close to the true matrix.

W2. Experiments on simulated graphs.

Finite-sample SDP experiments would help show whether the predicted transitions and the separation between tightness and label recovery are observable in practice.

We have now solved the SDP on 180 graphs with 900 vertices: (m,k,β)=(75,12,1)(m,k,\beta)=(75,12,1), nine signal levels and twenty seeds each. Our new Fig. 3 (Sec. 5) compares matrix recovery with exact labels before and after refinement on the same graphs. Counts are out of twenty graphs. We assess whether the planted matrix is the unique SDP optimum using the numerical checks in Sec. K.2; refinement uses the smallest-label tie rule.

Already at 900 vertices, the observed matrix-recovery transition is close to the sharp asymptotic boundary, with label recovery occurring earlier as predicted.

α\alphaMatrix recoveryLabels after roundingLabels after refinement
3.50,3.753.50,3.750/200/200/20
4.004.000/200/201/20
4.254.250/202/201/20
4.334  Sufficient condition
4.504.500/209/203/20
4.754.750/2017/2010/20
5.005.0012/2020/2016/20
5.149Sharp boundary  
5.255.2518/2020/2019/20
5.505.5020/2020/2020/20

Matrix recovery rises from 12/20 at α=5.0\alpha=5.0 to 18/20 at 5.25 and 20/20 at 5.5, near the sharp asymptotic boundary 5.149. Above the label reference 4.334, exact recovery after refinement increases from 3/20 at α=4.5\alpha=4.5 to 10/20 at 4.75 and 16/20 at 5.0. The bold rows mark asymptotic references: 4.334 is the sufficient condition for rounding followed by refinement under Corollary 4.1's feasibility and accuracy assumptions.

At α=4.75\alpha=4.75, feasible objective improvements show that the planted matrix is suboptimal on all twenty graphs, yet rounding recovers every label on seventeen and refinement on ten. These measurements directly exhibit matrix and label recovery separating on the same instances.

Appendix K provides the numerical verification and sampling intervals; Table 1 reports matrix errors, objective-gain intervals, label errors, and numerical gaps for these same graphs.

References

  • Agarwal, N., Bandeira, A. S., Koiliaris, K., and Kolla, A. (2015). Multisection in the Stochastic Block Model Using Semidefinite Programming. arXiv:1507.02323v1.
  • Hajek, B., Wu, Y., and Xu, J. (2016). Semidefinite Programs for Exact Recovery of a Hidden Community. COLT, PMLR 49:1051–1095.

W3. Unequal or incorrectly specified community sizes.

Please discuss how mild imbalance or misspecification of the community size might affect the conclusions.

If the assumed community size is wrong, the planted matrix violates the row-sum constraint, so the SDP cannot recover it exactly. Labels can nevertheless remain accurate, as our new imbalance experiments show (Sec. K.3, Table 2).

We have added the corresponding calculation in Sec. J.5. If the assumed size is m^\widehat m and the true size is mm, every feasible ZZ satisfies

$ |Z-Z^*|_{1,\mathrm{entry}}\geq n|\widehat m-m|. $

For unequal true sizes mrm_r, the bound is ∑rmr∣m^−mr∣\sum_r m_r|\widehat m-m_r|.

Our tests keep the assumed size at 40 and use ten graphs per setting. Mean label errors (%) are:

True community sizesRefinementRefinement with label retention on ties
400.1670.167
36/440.3330.229
32/483.7290.396

In these finite-size tests, mean label accuracy remains high under the tested imbalances, even though the row-sum constraint rules out exact matrix recovery. We plan to extend the sharp SDP guarantees to unequal community sizes (Secs. 6, J.5).

Q1. Recovery when a<2σa<2\sigma.

Do you expect a>2σa>2\sigma to be necessary for label recovery from the SDP output, or could improved postprocessing succeed beyond this region?

The condition a>2σa>2\sigma is sufficient for our label-recovery guarantee when I(0)>1I(0)>1: the SDP supplies starting labels with o(m)o(m) mistakes, which refinement corrects with high probability (Sec. F.3). Our new experiments also find accurate labels on the bulk side of this boundary.

At (α,β,m,k)=(4.25,1,75,12)(\alpha,\beta,m,k)=(4.25,1,75,12), we have a=3.25<2σ≈3.334a=3.25<2\sigma\approx3.334 and I(0)>1I(0)>1. Row rounding achieves 99.67% mean label accuracy, with exact labels on 2/20 graphs (Sec. K.1, Table 1). This motivates exploring postprocessing beyond the spectrally stable region. We plan to study how this recovery scales with graph size and determine the conditions for exact label recovery from SDP outputs in the asymptotic bulk regime (Secs. 6, J.4).

Q2. Comparison with low-rank and projected-power methods.

How does the SDP approach compare with low-rank SDP factorization [1] and projected power iteration [2] in recovery guarantees, initialization requirements, and computational cost, particularly when k≍log⁡nk\asymp\log n?

We have added a comparison in Appendix I and the full computational cost in Sec. J.6. The main differences are:

MethodRecovery guarantee and initializationComputational features
Low-rank factorization [1]Recovery in the studied two-community model without accurate starting labels.An n×rn\times r factor uses O(nr)O(nr) variable storage; total running time depends on the solver.
Projected power [2]Exact recovery from sufficiently accurate starting labels under its stated conditions.Updates labels directly; each balanced-assignment projection costs O(k2nlog⁡n)O(k^2n\log n).
Our approachSharp matrix-recovery and error guarantees for logarithmically many communities; the SDP supplies starting labels for refinement.A full SDP matrix uses O(n2)O(n^2) storage; total cost is given below.

Our regime k/log⁡m→γ>0k/\log m\to\gamma>0 also has k≍log⁡nk\asymp\log n, since n=kmn=km and log⁡n/log⁡m→1\log n/\log m\to1. Wang et al. [2] state their guarantee with fixed coefficients in p=α′log⁡n/np=\alpha'\log n/n and q=β′log⁡n/nq=\beta'\log n/n. Writing our model in that form makes both coefficients grow with kk. Extending their guarantee to our regime therefore requires checking how the permitted starting errors and convergence bounds change with those growing coefficients (Appendix I). For a factorization of our SDP, the nonnegativity and row-sum constraints must also be enforced. Our new Lemma I.1 shows that every feasible matrix has rank at least kk, with equality only for balanced partition matrices.

Our stated procedure costs (Sec. J.6)

$ T_{\rm SDP}(n,\varepsilon)+O(n^3)+O((|E|+nk)\log n). $

The terms are the SDP solve at the requested accuracy, row rounding, and refinement using adjacency lists. These costs accompany our guarantee of recovering labels even when the planted matrix is not SDP-optimal.

Could the analysis extend to these nonconvex methods?

A factorized solver can use our statistical guarantees whenever it returns a matrix satisfying the SDP constraints with a sufficiently small objective gap to the full SDP optimum. We plan to analyze when nonconvex optimization reaches such outputs in the logarithmic-community regime (Appendix I; Sec. J.1).

Thank you again for your time and thoughtful suggestions!

References

  1. McRae, A. D., Abdalla, P., Bandeira, A. S., and Boumal, N. (2025). Nonconvex Landscapes for Z2Z_2 Synchronization and Graph Clustering Are Benign Near Exact Recovery Thresholds. Information and Inference, 14(2):iaaf012. Author version: arXiv:2407.13407v1.
  2. Wang, P., Liu, H., Zhou, Z., and So, A. M.-C. (2021). Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method. ICML, PMLR 139:10828–10838.

Thanks for the response. I am positive about this paper.

Reviewer_Quw5OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a semidefinite program, or SDP, for community detection under a balanced stochastic block model. The number of communities grows logarithmically with the size of each community. The main question is when the true community matrix is the unique solution to the SDP and what can still be recovered once that property fails.

The authors find two ways the SDP can fail. In the first, a small number of vertices have unusually weak connections to their own community relative to a competing one. These vertices can make the true community matrix suboptimal even though the SDP solution remains close to it. The paper shows that the matrix error and the improvement in the SDP objective over the true community matrix decay at the same polynomial rate. In the second regime, spectral noise dominates, and the normalized overlap between near-optimal SDP solutions and the true community matrix tends to zero. The authors also show that, in the spectrally stable regime above the information-theoretic threshold, rounding and refining the SDP solution can recover every label even after the SDP loses tightness.

Critical strengths

The paper separates two questions that are easy to conflate. The SDP can fail to return the true community matrix and still provide a good enough starting point to recover every label. I found this distinction to be the most interesting part of the paper. The authors identify a regime where it occurs and quantify how far the SDP solution moves away from the true matrix.

Critical weaknesses
  1. The model is too restrictive to support much practical relevance. The entire analysis is built on the basic, balanced stochastic block model in Equation (2.2). Every community has the same known size, and all vertices in a community have the same expected degree. I was surprised that the paper does not discuss the degree-corrected block model introduced by Karrer and Newman in 2011, a standard model for community detection when vertices in the same community have very different connectivity levels.

This omission matters for the main result. Under the paper’s model, a vertex with a small degree margin is an unusual draw from a common distribution. With degree heterogeneity, a vertex may have a small margin simply because it has a low expected degree. If a substantial fraction of vertices have low expected degrees, the frequency of small margins can change, which puts the paper’s explanation for the error exponent in question outside the model studied. The authors should discuss which parts of the proof depend on homogeneous expected degrees and whether the same SDP and refinement rule remain appropriate under degree correction. A simulation that varies within-community degree heterogeneity while keeping community sizes equal would help isolate the issue. As it stands, I see the paper primarily as a theoretical result for a narrow benchmark, with limited guidance for analyzing real networks.

  1. The numerical section does not show how the results play out on finite graphs. The figures evaluate the asymptotic formulas, but the authors never solve the SDP on simulated graphs. I would have liked to see the matrix error, objective gain, and label accuracy before and after refinement measured on the same instances. The fixed-signal example in Section 5 already gives a natural setup. Since the objective gain can be small, reporting solver gaps and feasibility residuals would help readers judge which differences are numerically meaningful.

  2. The guarantees are hard to translate into solver tolerances. The sharp error bound and exact recovery result assume an exactly feasible matrix whose objective value is within one unit of the optimum. The paper gives a coarser overlap result for larger objective gaps, but it remains unclear how much accuracy the refinement step actually needs. I would like to know how the guarantees change with the objective gap and which constraint violations are most consequential for rounding.

Questions for authors

The question is whether the SDP retains signal above that baseline and whether a rounding procedure can use it. This is especially relevant in the part of the bulk regime where exact recovery is still possible in principle.

4 comments

Thank you for your careful review and thoughtful questions. To address your questions, we have added finite-graph experiments (Sec. 5; Appendix K), degree-correction analysis (Sec. J.5), and solver-accuracy guarantees (Secs. J.1–J.3).

W1. Degree heterogeneity.

The model is too restrictive to support much practical relevance.

The balanced homogeneous SBM is a widely studied SDP benchmark (Agarwal et al., 2015; Hajek et al., 2016; Fei and Chen, 2019; Appendix I). This model separates failures caused by unusually small degree margins at individual vertices from those caused by spectral noise across the graph, and pinpoints when SDP exactly recovers the true matrix. We plan to extend these recovery and error guarantees to varying expected degrees and unequal community sizes (Secs. 6, J.5).

With degree heterogeneity, a vertex may have a small margin simply because it has a low expected degree.

We have added a calculation of precisely this effect in Sec. J.5. For a Bernoulli version of the degree-corrected SBM (Karrer and Newman, 2011), let ϑi\vartheta_i be a vertex-specific degree multiplier. Assume fixed bounds 0<ϑmin⁡≤ϑi≤ϑmax⁡<∞0<\vartheta_{\min}\leq\vartheta_i\leq\vartheta_{\max}<\infty and mean multiplier one per community. For margins below their mean, JiJ_i describes how quickly the probability of a small margin decreases as the graph grows:

$ J_i(x)=\vartheta_i I_{\alpha,\beta}(x/\vartheta_i),\qquad J_i(0)=\vartheta_i I_{\alpha,\beta}(0). $

Thus a vertex with lower expected degree is more likely to have at least as many edges to another community as to its own.

The authors should discuss which parts of the proof depend on homogeneous expected degrees and whether the same SDP and refinement rule remain appropriate under degree correction.

For equal sizes, the existing rounding bound still controls how many vertices are assigned incorrectly. Our new Prop. J.2 shows that refinement recovers all labels with high probability if it starts with o(m)o(m) errors and ϑmin⁡I(0)>1\vartheta_{\min}I(0)>1. Extending the SDP guarantees requires analyzing how the changed mean and noise affect its solution; Sec. J.5 identifies the affected resolvent and dual-certificate arguments.

A simulation that varies within-community degree heterogeneity while keeping community sizes equal would help isolate the issue.

We added equal-size heterogeneity tests at (α,β,m,k)=(4.75,1,40,12)(\alpha,\beta,m,k)=(4.75,1,40,12) (Sec. K.3, Table 2). With degree multipliers 1±h1\pm h for h=0.1,0.2,0.4h=0.1,0.2,0.4, SDP followed by refinement has mean label errors of 0.125%, 0.417%, and 1.563% over ten graphs per level, compared with 0.167% in the matched homogeneous control. Mean error increases across these three perturbation levels; mean label accuracy remains above 98% at each tested level.

References

  • Agarwal, N., Bandeira, A. S., Koiliaris, K., and Kolla, A. (2015). Multisection in the Stochastic Block Model Using Semidefinite Programming. arXiv:1507.02323v1.
  • Hajek, B., Wu, Y., and Xu, J. (2016). Semidefinite Programs for Exact Recovery of a Hidden Community. COLT, PMLR 49:1051–1095.
  • Fei, Y., and Chen, Y. (2019). Exponential Error Rates of SDP for Block Models: Beyond Grothendieck's Inequality. IEEE Transactions on Information Theory, 65(1):551–571. Author version: arXiv:1705.08391v1.
  • Karrer, B., and Newman, M. E. J. (2011). Stochastic Blockmodels and Community Structure in Networks. Physical Review E, 83:016107.

W2. Experiments.

I would have liked to see the matrix error, objective gain, and label accuracy before and after refinement measured on the same instances.

We have now solved the SDP on 180 graphs with n=900n=900: nine signal levels and twenty seeds each. Table 1 reports matrix error, objective-gain intervals, and label errors before and after both refinement rules on the same graphs (Sec. K.1).

Our new Fig. 3 (Sec. 5) compares matrix recovery with exact labels before and after refinement, for (m,k,β)=(75,12,1)(m,k,\beta)=(75,12,1). Counts are out of twenty graphs. We assess whether the planted matrix is the unique SDP optimum using the numerical checks in Sec. K.2; refinement uses the smallest-label tie rule.

Already at 900 vertices, the observed matrix-recovery transition is close to the sharp asymptotic boundary, with label recovery occurring earlier as predicted.

α\alphaMatrix recoveryLabels after roundingLabels after refinement
3.50,3.753.50,3.750/200/200/20
4.004.000/200/201/20
4.254.250/202/201/20
4.334  Sufficient condition
4.504.500/209/203/20
4.754.750/2017/2010/20
5.005.0012/2020/2016/20
5.149Sharp boundary  
5.255.2518/2020/2019/20
5.505.5020/2020/2020/20

Matrix recovery rises near the sharp asymptotic boundary α≈5.149\alpha\approx5.149. Above the label reference α≈4.334\alpha\approx4.334, exact recovery after refinement increases from 3/20 at α=4.5\alpha=4.5 to 10/20 at 4.75 and 16/20 at 5.0. At α=4.75\alpha=4.75, feasible objective improvements show that the planted matrix is suboptimal on all twenty graphs, yet rounding recovers every label on seventeen and refinement on ten. The bold rows mark asymptotic references; 4.334 is Corollary 4.1's sufficient condition for rounding followed by refinement, under its feasibility and accuracy assumptions.

We noticed that zero or negative true degree margins can trigger incorrect refinement updates. Keeping the current label on ties increases exact recovery from 10/20 to 15/20 at α=4.75\alpha=4.75 (Sec. K.1).

Since the objective gain can be small, reporting solver gaps and feasibility residuals would help readers judge which differences are numerically meaningful.

Table 1 reports the numerical objective gaps and gain intervals, and Sec. K.2 gives the constraint checks. For a concrete example, the supplementary per-instance record for α=4.5\alpha=4.5, seed 14000, reports:

Numerical checkMeasured value
Feasible objective gain over the true matrix≈17.995\approx17.995
Numerical primal–dual gap<0.462<0.462
Largest diagonal or row-sum residual<5×10−14<5\times10^{-14}
Minimum entry and minimum eigenvalueBoth positive

The optimal objective gain lies in the numerical interval [17.99, 18.46], clearly above zero; the constraint checks confirm feasibility to numerical precision. Sec. K.2 details the verification for all graphs, including exact rational checks for small positive gains.

W3. Solver accuracy.

The sharp error bound and exact recovery result assume an exactly feasible matrix whose objective value is within one unit of the optimum.

We have added a guarantee that allows a larger objective gap while preserving exact label recovery (Prop. J.1). When a>2σa>2\sigma and I(0)>1I(0)>1, the allowed gap is sm=o(mlog⁡m)s_m=o(m\log m), extending the original additive-one guarantee. For every feasible matrix ZZ within sms_m of the optimal objective,

$ \mathcal E_m(Z)\leq C m^{-c}+\frac{s_m}{\kappa n\log m}. $

Thus rounding makes at most h0≤16nEm(Z)=o(m)h_0\leq16n\mathcal E_m(Z)=o(m) errors, which refinement corrects with high probability. Since the optimum has scale nlog⁡mn\log m (Prop. 2.3), the allowed relative objective gap is o(1/k)o(1/k).

Sec. J.1 summarizes sufficient objective accuracies for the different conclusions, under their respective model conditions:

ConclusionSufficient absolute objective gap sms_m
Exact labels after rounding and refinemento(mlog⁡m)o(m\log m)
Preserve the sharp matrix-error exponent r=I(τ)∈(0,1)r=I(\tau)\in(0,1)sm≤nlog⁡m m−r−ξs_m\leq n\log m\,m^{-r-\xi}, for any fixed ξ>0\xi>0
Preserve the limiting overlapo(nlog⁡m)o(n\log m)

I would like to know how the guarantees change with the objective gap and which constraint violations are most consequential for rounding.

The constraints have complementary roles in controlling matrix and label errors (Lemma B.3):

ConstraintRole in the guarantee
PSDLets the dual matrix inequality control the objective and matrix error.
Nonnegative entriesEnsures that the entrywise dual penalty is nonnegative.
Unit diagonalTogether with PSD and nonnegativity, bounds all entries between 0 and 1.
Row sums equal to mmFixes total mass at nmnm; with the other constraints, gives Em(Z)=1−θm(Z)\mathcal E_m(Z)=1-\theta_m(Z).

Our new Sec. J.3 corrects these constraints jointly and quantifies the effect on rounding. Let XX be the raw output, ZZ the corrected feasible matrix, and R=∥X−Z∥1,entryR=\|X-Z\|_{1,\mathrm{entry}} the total entrywise correction. Rounding XX directly gives

$ h_0(X)\leq16n\mathcal E_m(Z)+8R/m, $

provided 2nmEm(Z)+R<m2/162nm\mathcal E_m(Z)+R<m^2/16. Thus constraint violations enter through the correction distance RR. If R=o(m2)R=o(m^2) and the corrected matrix has objective gap sm=o(mlog⁡m)s_m=o(m\log m), the initial error count remains o(m)o(m) under the conditions above.

In our experiments, we round the restored matrix after checking its feasibility and numerical objective gap (Sec. K.2).

Q1. Signal above the baseline.

The question is whether the SDP retains signal above that baseline and whether a rounding procedure can use it.

Our new experiments show that row rounding correctly labels 99.67% of vertices on average at (α,β,m,k)=(4.25,1,75,12)(\alpha,\beta,m,k)=(4.25,1,75,12). We chose this setting because α=4.25\alpha=4.25 lies below the asymptotic spectral-stability reference 4.334, on the bulk side of the boundary, while I(0)>1I(0)>1. Across twenty graphs, the SDP also retains substantially higher overlap than the uninformative reference (Sec. K.1, Table 1):

MatrixNormalized planted overlap
Uninformative feasible reference BmB_m0.09455
SDP output, mean0.881
Planted matrix1

The reference assigns the same value to every distinct vertex pair (Sec. J.4). The SDP has 9.3 times its overlap, and rounding makes only 2.95 errors per 900-vertex graph on average, with exact labels on 2/20 graphs. We plan to study how this advantage scales with graph size and develop label-recovery guarantees for actual SDP outputs in the asymptotic bulk regime (Secs. 6, J.4).

Thank you again for your time and thoughtful suggestions!

I appreciate your efforts on the revisions, and would like to raise my rating to 2.

Comments on the paper

1 comment
AuthorsOpenReview ↗

To the AC and All Reviewers

We sincerely thank the Area Chair and all reviewers for their time and consideration. The reviews have helped us substantially improve our work.

In response, we have addressed all concerns raised by the reviewers and provide point-by-point responses. One major change we made was to conduct additional simulations on 330 graphs and add two propositions addressing solver accuracy and refinement under degree heterogeneity.

Our other major revisions include:

  1. Actual SDP experiments on finite graphs (Sec. 5, Fig. 3; Appendix K). We solved the SDP on 180 sampled graphs with 900 vertices. Already at this size, the observed matrix-recovery transition is close to the sharp asymptotic boundary, with label recovery occurring earlier as predicted. The experiments measure matrix error, objective gain, and labels before and after refinement on the same instances, with numerical accuracy checks.

  2. Solver accuracy and label-recovery guarantees (Sec. 4; Secs. J.1–J.3, J.6). Our new Proposition J.1 relaxes the objective-gap requirement from 1 to o(mlog⁡m)o(m\log m), while preserving exact label recovery for feasible SDP outputs under the same model assumptions. We made the matrix-to-label conversion explicit and added initialization constants, finite-graph refinement conditions, and a complete cost analysis.

  3. Model scope and comparisons (Appendix I; Secs. J.5, K.3–K.4). We added a conditional refinement guarantee under degree heterogeneity (Prop. J.2), sensitivity tests for degree variation and unequal sizes on 50 graphs, and a matched spectral comparison on 100 graphs. Appendix I now compares the assumptions and guarantees of existing SDP, spectral, and nonconvex methods.

  4. Clearer proofs and notation (Secs. 3.1, B.1; Fig. 1). We rewrote the explanation following Proposition 3.1, unified conflicting notation directly in the text and proofs, and clarified the parameter conversion in Figure 1.

Our individual responses address each reviewer's questions in detail. Thank you again for your time and consideration!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.