- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies semi-supervised node classification on a symmetric stochastic block model. For a one-step linearized GCN, the authors derive a sharp exact-recovery threshold and the leading-order error exponent.
Critical strengths
-
The problem setting is meaningful.
-
The theoretical analysis is deep.
-
Experiments show the effectiveness of the proposed method.
Critical weaknesses
-
Possible mismatch between theorem and method. Theorem 4.1 requires , but the experiments use . These experiments do not satisfy the theorem's assumptions.
-
Possible inconsistency in experiments. Section 5 reports for Figures 1 and 2. However, the actual figure uses .
-
The proposed estimator is just a random-feature approximation of two-hop graph-based label propagation.
-
The paper does not contain Limitation.
-
The paper does not contain an AI use statement.
Questions for authors
Please see the above weaknesses
5 comments
A Gentle Reminder
Dear Reviewer,
With less than a day left in the discussion period, we wanted to follow up on our rebuttal and revised manuscript. We would appreciate hearing whether our responses have addressed your concerns, or if there are any points that still need clarification. We are happy to respond to any remaining questions before the discussion closes. Thank you for your time.
Final Reminder Before the Discussion Closes
Dear Reviewer,
With only a few hours left in the discussion period, we wanted to follow up on our earlier responses. For Question 1, the original experiments show that exact recovery is possible with fewer labels (). This is consistent with Theorem 4.1, which gives a sufficient condition for recovery. To address your concern, we also ran experiments with , which satisfies the theorem’s labeling condition, and again observed exact recovery. The code is available in the supplementary material. For Question 2, we clarified that we used different values of to illustrate different theoretical results on exact recovery and misclassification rates. The values shown in each panel match the corresponding settings in Section 5, so there is no inconsistency between the figures and the text. We also addressed the remaining questions in our earlier replies and revised the manuscript accordingly.
We believe these updates address your main concerns, and we hope to hear from you before the discussion closes. If anything remains unclear, we’ll respond as soon as we can.
Response to Reviewer nbi3: Clarifications on Experiments and Theoretical Contributions
Response to Weakness 1
We thank the reviewer for pointing this out. The original experiments use η=2/logn, which does not satisfy the condition ηlogn→∞ in Theorem 4.1.
However, the original experiments use a smaller labeled proportion, so the estimator has less supervision and faces a harder recovery task. These results show that the method also performs well at finite sample sizes under a more limited label budget. The theorem gives a sufficient condition, so these experimental results do not contradict it.
To address the reviewer's concern, we have run additional experiments with η=1/logn. This choice satisfies the theorem's condition on the labeled proportion. We again observed exact recovery, consistent with Theorem 4.1.
The experimental code was included in the supplementary material of the original submission at
experiments/single_layer/exact_recovery.py. The script supports setting the labeled proportion through the--etaargument. The reviewer can use the above setting to run the additional experiments and check the results independently.Response to Weakness 2
We thank the reviewer for asking us to clarify the settings of the different panels. These dimensions are used in different experiments. The exact-recovery experiment in Figure 1(b) uses d=n, while the misclassification-rate experiments in Figures 1(d) and 2(b) use d=nlogn and $ d = \sqrt n$, respectively.
Section 5 states these settings separately, and they agree with the labels in the corresponding figures. The first experiment studies how reducing the feature dimension affects exact recovery. The other experiments compare misclassification rates at different feature dimensions. The panels therefore use different parameter settings; there is no mismatch between the text and figures for the same experiment.
Response to Weakness 3
We thank the reviewer for pointing out this connection. Our question is whether GCNs can attain the information-theoretic limits of semi-supervised node classification on the SBM. To answer it, we study a linearized version of a standard GCN. It aggregates node features through graph convolutions and trains the readout using a regularized least-squares loss on the revealed labels. We focus on the recovery performance of this GCN and do not aim to propose a more complex estimator.
We agree that, in high dimensions, the single-layer estimator can be viewed as a random-feature approximation of two-hop graph-based label propagation scores. But this approximation alone does not give optimal recovery guarantees. Proving a sharp recovery threshold and an optimal misclassification rate requires keeping the leading constant in the error exponent. Showing only that a high-dimensional approximation holds, or that accuracy tends to one, is not enough. Length-two paths share edges, so their contributions cannot be treated as independent. The error probability caused by random features must also be small enough to leave this exponent unchanged. In the critical exact-recovery regime, we must further handle score gaps close to zero to control errors across all nodes. Through these steps, the upper bounds in Theorems 4.1 and 4.3 match the lower bounds in Theorems 4.2 and 4.4, respectively, under their common conditions. Our theoretical contribution is to prove that one gradient step on the readout, using the supervised loss, enables this simple GCN to attain information-theoretic optimality. This conclusion does not follow from its two-hop form alone.
We also study multi-layer GCNs at fixed depth. Their graph scores involve longer walks, and the analysis must handle dependencies caused by shared and repeated edges. This goes beyond the single-layer two-hop structure. Theorem 4.5 gives an upper bound on the expected misclassification rate and uses it to study the tradeoff between reduced feature noise and weaker community separation as depth increases. This bound helps explain the role of multi-layer propagation.
Response to Weaknesses 4 and 5
We thank the reviewer for raising this issue. We omitted the AI use statement from the initial submission. As soon as we noticed this omission, we emailed the Program Chairs to explain it. We have now added the full AI use statement and Limitation to the revised manuscript.