- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies Random Node Sampling (RNS) for transductive GNN training. It reports that training on randomly partitioned induced subgraphs can match or improve full graph accuracy while reducing computational cost. To explain this behavior, the author exploits backward error analysis (previously developed) to sampled subgraph training and obtains a modified objective comprising the sampled loss and a mini-batch gradient-variance regularizer. They also derive RNS-specific bias and variance bounds and demonstrate competitive accuracy with reduced computational costs across several benchmarks.
Critical strengths
-
Practical effectiveness: RNS achieves competitive or better accuracy than more sophisticated sampling methods, often with substantial computational savings. Specifically, the results on ogbn-products and the additional GraphLand experiments provide meaningful evidence that RNS could be useful.
-
Useful analytical perspective: The paper try to distinguish sampling-induced objective bias from implicit regularization due to sequential mini-batch updates. The graph specific bounds further characterize RNS.
Critical weaknesses
The practical observation is useful. However, the reviewer is not fully convinced that the analysis and experiments establish the proposed explanation for RNS's performance. Since both RNS (Luo et al. 2024) and the modified objective characterization (Eq. (8)) build on existing work, the paper's contribution seems to depend critically on explaining RNS's empirical advantage.
-
Eq. (8) largely instantiates existing backward error analysis (Smith et al., 2021) for sampled graph losses. The RNS-specific bounds characterize its bias and variance, but do not establish an advantage over competing samplers. The paper should clarify what new understanding of RNS is obtained beyond applying the existing modified objective characterization.
-
Small batch gradient variance does not imply proximity to the full graph gradient. Moreover, the contribution of to the modified dynamics depends on , not merely the magnitude of measured at initialization. The statistics in Figure 2 therefore do not establish that RNS's smaller variance term yields a more favorable learning objective or explains its generalization advantage.
-
Refer to Table 1. RNS performs sequential updates per epoch, while RNS (no batch) performs one accumulated update. Appendix F.2 does not specify how accumulated gradients are normalized or establish that differences in update scale and optimization progress are adequately controlled. The comparison therefore does not seem to isolate the effect of the proposed regularizer. The Adam results (83.01% vs. 83.15%, with overlapping confidence intervals) also provides limited support for the claim that sequential updates are necessary for the observed gains.
-
Although Appendix F reports sampled neighborhood inference for neighborhood sampling and full graph inference for the other methods, for example, LADIES uses a different architecture (5-layer GCN), and neighborhood sampling uses a different inference procedure. These differences, together with different sampling implementations, make it difficult to attribute the observed accuracy and runtime differences soley to the sampling strategies. A more controlled comparison would strengthen the author's claim.
-
As far as the reviewer concerns, some of relevant works are missing. The related work discussion could be expanded to include (1) Sketch-GNN: Scalab le Graph Neural Networks with Sublinear Training Complexity (Ding et al., 2022), Graph Neural Networks for Link Prediction with Subgraph Sketching (chamberlain et al., 2023), and Efficient Learning of Linear Graph Neural Networks via Node Subsampling (Shin et al., 2023). These works offer relevant perspectives on sketching and sampling for scalable graph learning in a principled manner. Although these works address different settings, discussing their connections to the present work, while distinguishing their settings and theoretical guarantees, would help clarify the scope and novelty of the proposed approach.
Questions for authors
-
How are accumulated gradients normalized in Table 1, and does the claimed advantage of sequential updates persist even with controlling hyperparameter sensitivity (e.g., optimizer step counts, optimization budgets, and learning rate)?
-
What evidence distinguishes the proposed variance regularization mechanism from improvements due to graph perturbation or different optimization progress? Can a controlled intervention validate the role of the derived correction while keeping the sampled objective fixed?
-
Do the conclusions persist under consistent inference procedures and model architectures? Does the variance gap in Figure 2 hold when controlling for the number of supervised batch sizes?
3 comments
Q2. Variance regularization, graph perturbation or optimization progress? Table 1 varies one factor at a time with the step count fixed, which separates the three:
- Variance regularization. With the objective fixed to , adding explicitly (83.27%) or implicitly through chained updates (RNS, 83.00%) leaves accuracy within the confidence intervals of 83.12%.
- Optimization progress. All rows take the same number of steps, so progress per step does not explain the differences.
- Graph perturbation. Replacing by , with absent in both cases, gives +3.1 points. Each step on uses a freshly resampled partition and drops about of the edges. Dropping the same fraction of edges independently on the full graph (DropEdge) recovers part of this gain (82.32%), and the induced-subgraph removal of RNS does better still (83.00%). The answer is therefore mainly graph perturbation. RNS obtains it at about of the compute of gradient descent on . Section 4.2 and Appendix B.6 now present this account.
Q3b. Does the variance gap in Figure 2 hold at matched supervised batch size? Largely not, and we thank the reviewer for asking. With exactly supervised nodes per batch for every sampler, the ratio of to that of RNS is (Appendix G.3.2):
| Dataset, | Neighbor | GraphSAINT | ClusterGCN |
|---|---|---|---|
| arxiv, native | 278× | 12× | 377× |
| arxiv, 1,024 | 0.99× | 1.05× | 6.1× |
| products, native | 41× | 6.5× | 512× |
| products, 1,024 | 0.90× | 1.24× | 45× |
Against Neighborhood Sampling and GraphSAINT, the native gap is mostly batch size. RNS batches are large, cheap to build and drawn without replacement, so vanishes as (Theorem 28). ClusterGCN stays at least 6 times higher at matched , a structural effect of mutually dissimilar METIS partitions. Figure 2 now shows the statistics through training, and the text no longer claims an orders-of-magnitude advantage.
W4 / Q3a. Consistent inference and architectures. We re-evaluated the trained Neighborhood Sampling models with full-graph inference, the protocol used by the other methods (test accuracy, %, Appendix H.3.2):
| Dataset | NS, sampled inference | NS, full-graph inference | RNS |
|---|---|---|---|
| arxiv | 71.08 ± 0.47 | 70.80 ± 0.63 | 72.51 ± 0.19 |
| products | 80.56 ± 0.28 | 80.14 ± 1.15 | 83.11 ± 0.17 |
| pokec | 80.70 ± 0.13 | 73.77 ± 1.71 | 83.98 ± 0.08 |
Full-graph inference does not help Neighborhood Sampling, so Table 2 reports it at its best, and RNS leads under either protocol. LADIES uses a GCN because it is only defined for GCN: its layer-wise importance sampling rescales the sampled adjacency by a correction factor that applies only to the GCN propagation rule (Appendix F.1). Table 4 also trains a GCN with full-graph training and with RNS, using the configuration of Luo et al. (2024), which differs slightly from the LADIES GCN (Appendix F.4). With this backbone, RNS outperforms LADIES on all three datasets.
W5. Related work. Section 2 now discusses Sketch-GNN (Ding et al., 2022), which trains on compressed sketches of the graph and activations at sublinear cost. Chamberlain et al. (2023) approximate subgraph GNNs for link prediction by passing subgraph sketches as messages, and Shin et al. (2023) learn two-layer linear GCNs from a subsample of the adjacency matrix with guarantees on the learned weights. These methods change the model or its inputs, or restrict it to linear GNNs, while we study the implicit objective of standard mini-batch training of nonlinear message-passing GNNs.
We hope these additions address the reviewer's concerns, and we would be glad to clarify anything further.
Response to the Authors' Rebuttal
Thank you. The rebuttal addresses most of my empirical concerns. In particular, the controlled experiments clarify that the performance gains mainly come from the sampled objective rather than the proposed variance regularization. While this strengthens the empirical findings, it also leaves the theoretical contribution beyond existing backward error analysis unclear. I therefore maintain my original assessment.
We thank the reviewer for a precise review. Several points were correct (the Table 1 normalization, the batch-size effect in Figure 2, the gap between R and ∇R), and the experiments they led to changed our interpretation. We answer each point below.
W1. Eq. (8) instantiates Smith et al. (2021). We agree that the derivation is standard, as Remark 16 already states. What is specific to graphs is that the epoch-averaged loss Lˉ differs from Lfull (Remark 17), so Eq. 8 contains two distinct sources of implicit regularization: the sampled objective and the variance term R. The new contribution is to test which one matters with controlled interventions (Section 4.2). The sampled objective accounts for most of the gain, while the effect of R stays within confidence intervals. We also agree that the RNS bounds (Appendices B to D) do not show an advantage over other samplers. Their role is to explain the two terms of Eq. 8 for RNS. Appendix B shows that sampling nodes alone is unbiased, so the bias of Lˉ comes only from the edges removed between batches, which is what Table 1 tests against DropEdge. Theorem 28 bounds R by a term linear in m−1 that vanishes at m=1, so R is small for RNS. The contributions now say exactly that.
W2. Low variance does not imply proximity to the full gradient, and ∇R matters rather than R. Both points are right.
W3 / Q1. Normalization of the accumulated gradient, step counts and learning rate. The reviewer is right that this was not controlled. The no-batch variant averaged the m per-batch losses, each normalized by its own number of training nodes. This matches Lˉ in Eq. 8 exactly, but gives one step per epoch against m for RNS. We now run it for m times as many epochs, so that all rows take 10,000 steps, and tune the learning rate per row over {0.01, 0.03, 0.1, 0.3, 1} (Appendix F.2). On ogbn-products with SGD and m=10:
With steps matched, the gap between RNS and its no-batch variant disappears, so the claim that chained updates are necessary does not hold, and we removed it. SGD with momentum gives the same picture (83.12% vs. 83.30%), and on ogbn-arxiv (m=2) all rows at equal steps lie within 0.35 points (Appendix G.1). Under Adam with matched steps, the no-batch variant reaches 83.05% against 83.15% for RNS, consistent with the overlap the reviewer noted (Section 6.1, Table 5).
(Continued in Part 2.)