- 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 communities. It establishes sharp conditions for SDP tightness ( and ), 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 (Hajek et al., 2016a). Theorem 2.1 establishes a sharp SDP tightness threshold for every fixed when . The result substantially improves upon previous bounds and provides a clear explanation through the local margin correction .
The upper and lower bounds identify the same correction term , leading to a matching exponent . 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 and , exact recovery remains achievable through SDP, rounding, and refinement, even when 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 . 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 , 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
-
Notation is overloaded:
- is both the slack matrix and the small-diagonal vertex set within the same proofs (B.25–B.32, Lemma B.4).
- is the dual diagonal, the degree margins, a constant in Appendix C, and the distance in Lemma F.1.
- is both the projection and the quadratic form .
- , , , , , and are reused in several roles.
-
Proposition 3.1 uses , while Appendix B.1 uses .
-
Section 3.1: “adopt these estimates” should be “adapt”.
-
Figure 1(a) uses while the text works in ; the caption should state the conversion.
4 comments
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 and , Corollary 4.1 gives this guarantee with high probability, simultaneously for every feasible input with objective at least . 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 , even though exact recovery may be information-theoretically possible.
The condition is sufficient for our label-recovery guarantee when . Our new experiments also find accurate labels beyond this range: at , we have and , 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.
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 throughout Sec. 3.2 and Appendix B. The vertex sets retain , , and .
is the dual diagonal, the degree margins, a constant in Appendix C, and the distance in Lemma F.1.
We retain for the dual diagonal and use for degree margins, for the block-degree bound in Appendix C, and for matrix distance in Lemma F.1. The normalization matrix in Sec. E.3 is now .
is both the projection and the quadratic form .
We retain for the projection and use for the Gram energy in Sec. 3.3 and Appendix C.
, , , , , and are reused in several roles.
We have separated the conflicting uses at their definitions and throughout the corresponding arguments:
| Objects | Revised notation and location |
|---|---|
| Root count / auxiliary matrices | in Sec. 3.4 and Appendix D; in B.2 |
| Off-block mass / Gram perturbation / refinement rounds | in B.3; in Appendix C; in F.3 |
| Marked-set sparsity / Gram mixing / small-set sparsity | , , in B.1, C, and F.2 |
| Exponential tilting / planted overlap | in A.1, G.3, and H.1; in Sec. 2.1 |
| Positive lower bound / moment order / forest level | in Sec. 3.3 and Appendix C; in B.1; in Sec. 3.4 and Appendix D |
The error exponent remains ; neighborhood radii use . Ordinary community indices are defined locally.
Q2. Marked-set parameters.
Proposition 3.1 uses , while Appendix B.1 uses .
We now use the same threshold and marked set 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 while the text works in ; 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 , 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.
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 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).
We have now solved the SDP on 180 graphs with 900 vertices: (m,k,β)=(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.
Matrix recovery rises from 12/20 at α=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. The bold rows mark asymptotic references; 4.334 is Corollary 4.1's sufficient condition under its feasibility and accuracy assumptions.
At α=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