acceptodds
Under review as a conference paper at ICLR 2027

Implicit Regularization of Mini-Batch Training in Graph Neural Networks

Abstract

Mini-batch training of Graph Neural Networks (GNNs) is fundamentally different from training on i.i.d. data: sampling a subgraph alters the topology and introduces boundary effects, leading prior work to develop structure-aware samplers that preserve local connectivity and reduce embedding variance. Surprisingly, we demonstrate that the simplest possible scheme, Random Node Sampling (RNS) — training on the induced subgraph of uniformly sampled nodes — matches or outperforms full-graph training on most datasets at a fraction of the wall-clock time and memory. To explain this, we apply backward error analysis to graph mini-batch Stochastic Gradient Descent (SGD) and show that it implicitly minimizes the sampled loss plus a regularizer proportional to the mini-batch gradient variance, a quantity directly shaped by the sampler. Although RNS discards local structure, it produces mini-batches whose expected loss is closer to the full-graph loss, and whose per-batch gradients have lower variance, yielding a better implicit objective. Our analysis reframes the choice of graph sampler as a form of implicit regularization, and identifies RNS as a strong, theoretically grounded method for scalable GNN training.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural networks, sampling, batch training, regularization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DR2SOpenReview ↗
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
  1. 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.

  2. 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.

  1. 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.

  2. Small batch gradient variance does not imply proximity to the full graph gradient. Moreover, the contribution of R(w)R(w) to the modified dynamics depends on ∇R(w)\nabla R(w), not merely the magnitude of R(w)R(w) 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.

  3. Refer to Table 1. RNS performs mm 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.

  4. 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.

  5. 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
  1. 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)?

  2. 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?

  3. 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

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 RR and ∇R\nabla 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ˉ\bar L differs from LfullL_{\text{full}} (Remark 17), so Eq. 8 contains two distinct sources of implicit regularization: the sampled objective and the variance term RR. 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 RR 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ˉ\bar L comes only from the edges removed between batches, which is what Table 1 tests against DropEdge. Theorem 28 bounds RR by a term linear in m−1m-1 that vanishes at m=1m=1, so RR is small for RNS. The contributions now say exactly that.

W2. Low variance does not imply proximity to the full gradient, and ∇R\nabla R matters rather than RR. Both points are right.

  • Proximity to the full gradient. We now report the total gradient error, which splits exactly as 1m∑k∥∇L^k−∇Lfull∥2=∥∇Lˉ−∇Lfull∥2+R\frac{1}{m}\sum_k \|\nabla \hat L_k - \nabla L_{\text{full}}\|^2 = \|\nabla \bar L - \nabla L_{\text{full}}\|^2 + R. Through training, RNS has the lowest total error on ogbn-arxiv and ties GraphSAINT on ogbn-products, several times below ClusterGCN and Neighborhood Sampling (Figure 2, Appendix G.4).
  • ∇R\nabla R rather than RR. Instead of inferring the effect of the regularizer from the size of RR, we test it directly. Adding ϵ4R\frac{\epsilon}{4}R explicitly to the objective puts its gradient into every update, and accuracy stays within the confidence intervals (83.27% vs. 83.12% without it, Table 1). A smaller RR therefore does not by itself yield a measurably better objective. What separates RNS from full-graph training is the sampled objective Lˉ\bar L.

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 mm per-batch losses, each normalized by its own number of training nodes. This matches Lˉ\bar L in Eq. 8 exactly, but gives one step per epoch against mm for RNS. We now run it for mm 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=10m = 10:

Training regimeTest acc. (%)
Full graph79.98 ± 0.52
Full graph, DropEdge (p=0.9p = 0.9)82.32 ± 0.19
No batch83.12 ± 0.13
No batch, explicit RR83.27 ± 0.27
RNS83.00 ± 0.18

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=2m = 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.)

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 Lˉ\bar L, adding RR 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 LfullL_{\text{full}} by Lˉ\bar L, with RR absent in both cases, gives +3.1 points. Each step on Lˉ\bar L uses a freshly resampled partition and drops about 1−1/m1 - 1/m 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 1/m1/m of the compute of gradient descent on Lˉ\bar L. 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 kk supervised nodes per batch for every sampler, the ratio of RR to that of RNS is (Appendix G.3.2):

Dataset, kkNeighborGraphSAINTClusterGCN
arxiv, native278×12×377×
arxiv, 1,0240.99×1.05×6.1×
products, native41×6.5×512×
products, 1,0240.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 RR vanishes as m→1m \to 1 (Theorem 28). ClusterGCN stays at least 6 times higher at matched kk, 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):

DatasetNS, sampled inferenceNS, full-graph inferenceRNS
arxiv71.08 ± 0.4770.80 ± 0.6372.51 ± 0.19
products80.56 ± 0.2880.14 ± 1.1583.11 ± 0.17
pokec80.70 ± 0.1373.77 ± 1.7183.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.

Reviewer_DR2SOpenReview ↗

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.

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

This paper studies how subgraph sampling affects the optimization and predictive performance of GNNs for transductive node classification. It revisits Random Node Sampling (RNS), an existing approach that randomly partitions nodes each epoch and performs mini-batch updates on the corresponding induced subgraphs.

Experiments compare RNS against full-graph training, neighbor sampling, layer-wise sampling (LADIES), and subgraph-based methods (Cluster-GCN and GraphSAINT). Evaluations cover three large-scale graphs, seven GraphLand datasets, and four architectures: GCN, GraphSAGE, GAT, and SGFormer. The authors report that RNS generally matches or improves full-graph accuracy while achieving 2–12× wall-clock speedups and up to 3× lower peak GPU memory. These findings support RNS as a practical training baseline, while the extent to which the proposed implicit-regularization mechanism explains its empirical gains remains to be established.

Critical strengths
  1. Strong empirical performance and practical value. RNS achieves a favorable accuracy–efficiency trade-off, often matching or outperforming full-graph training while reducing runtime and memory consumption. Evaluations across multiple datasets and architectures support its value as a simple, competitive training baseline.

  2. An insightful perspective on graph sampling. The paper highlights that samplers should not be evaluated solely by how closely they approximate full-graph training. The paper provides a useful distinction between sampled-objective bias and optimization-induced effects, encouraging evaluation of graph samplers beyond approximation fidelity alone.

Critical weaknesses
  1. Limited novelty. RNS is an existing training strategy, and the theoretical framework builds on established backward error analysis of SGD. The contribution lies primarily in adapting this analysis to graph mini-batching and systematically evaluating RNS. While useful, the methodological and theoretical advances appear incremental. A clearer comparison with related subgraph-based learning and graph regularization work would help establish the distinct contribution.

  2. The proposed mechanism is not sufficiently validated. The sequential-update versus gradient-accumulation ablation changes both update frequency and potentially the effective optimization scale, making it difficult to attribute the gains specifically to the derived implicit regularizer. Moreover, gradient-variance statistics measured at initialization do not establish that this mechanism explains the final generalization gains. This concern is particularly relevant to Adam, for which the accumulated-gradient variant already performs similarly to standard RNS.

Questions for authors

My main concerns are described in the weaknesses above.

1 comment

We thank the reviewer for the review and for recognizing both the practical value of RNS and the distinction between sampled-objective bias and optimization effects. The reviewer's second weakness was correct, and the experiments it prompted are summarized in the general response. We answer both points here.

W1. Limited novelty. We agree that RNS itself is not new (we cite Luo et al., 2024, and the graph-transformer works) and that Eq. 8 follows the backward error analysis of Smith et al. (2021). What had not been done is to isolate what RNS does to accuracy: Luo et al. use it to scale classic GNNs, but do not measure its effect against full-graph training. The revised introduction states our contribution more plainly, in three parts:

  1. In graph mini-batching, the epoch-averaged loss Lˉ\bar L differs from LfullL_{\text{full}} (Remark 17), so Eq. 8 separates two sources of implicit regularization that coincide in the i.i.d. case.
  2. Controlled ablations tell them apart. With optimizer steps matched, optimizing Lˉ\bar L instead of LfullL_{\text{full}} gives +3.1 points on ogbn-products, while adding the variance term RR leaves accuracy within the confidence intervals (Section 4.2, Table 1). RNS obtains this gain at about 1/m1/m of the compute of gradient descent on Lˉ\bar L.
  3. We benchmark five mini-batch samplers under a fixed architecture and per-method tuning, on three large graphs, seven GraphLand datasets and four backbones, with time and memory alongside accuracy. We also derive RNS-specific bounds on bias and gradient variance and a degree-tail result (Appendices B to D), which explain where the bias of Lˉ\bar L comes from and why RR is small for RNS.
  4. Relation to graph regularization. The gain of Lˉ\bar L is a graph perturbation: each step drops about 1−1/m1 - 1/m of the edges. To test whether this reduces RNS to DropEdge, Table 1 now includes DropEdge on the full graph with the same expected fraction of dropped edges (p=0.9p = 0.9). It recovers part of the gain (82.32% against 79.98% for full-graph training), but RNS stays above it (83.00%, with non-overlapping intervals). Removing all edges between random batches, so that each batch is an induced subgraph, thus regularizes better than removing edges independently. RNS also gets this effect while processing only a fraction 1/m1/m of the nodes per step, whereas DropEdge still runs message passing over the whole graph. Section 2 now discusses DropEdge and sketching or subsampling methods (Ding et al., 2022, Chamberlain et al., 2023, Shin et al., 2023), and Appendix B.6 relates the edge removal of RNS to DropEdge.

W2. The mechanism is not sufficiently validated. We agree on all three sub-points and changed the paper accordingly.

  • Update frequency and scale. The original no-batch row took one averaged step per epoch, against mm for RNS. We now match the number of optimizer steps and tune the learning rate per row (ogbn-products, SGD, m=10m = 10, 10,000 steps, Table 1): | Training regime | RR | Test acc. (%) | | --- | --- | --- | | Full graph | – | 79.98 ± 0.52 | | Full graph, DropEdge (p=0.9p = 0.9) | – | 82.32 ± 0.19 | | No batch | – | 83.12 ± 0.13 | | No batch, explicit RR | explicit | 83.27 ± 0.27 | | RNS | implicit | 83.00 ± 0.18 |

Once steps are matched, chained updates and the explicit penalty both leave accuracy within the confidence intervals, so we no longer attribute the gain to the derived regularizer. The gain over full-graph training survives the control and comes from Lˉ\bar L.

  • Statistics at initialization. Figure 2 now tracks the statistics through training, and Appendix G.4 reports all of them on ogbn-arxiv and ogbn-products. RNS keeps the lowest or tied-lowest RR and total gradient error, but the gaps are smaller than at initialization (on ogbn-products RNS ties GraphSAINT), and the text says so.
  • Adam. The reviewer's observation that the accumulated Adam variant already matches RNS is what the revised account predicts: both optimize Lˉ\bar L, which is defined by the sampler and not by the optimizer. Section 6.1 and Table 5 now show the same pattern for SGD, SGD with momentum and Adam.

We believe the revised paper makes a narrower but better-supported claim, and we would be glad to answer further questions.

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

This paper studies RNS for mini-batch GNN training. Using backward error analysis, the authors distinguish changes to the training objective caused by subgraph computation from the implicit regularization induced by sequential mini-batch updates. They derive bounds on objective bias and gradient variance and compare different sampling methods empirically.

Critical strengths
  1. The implicit-regularization perspective is useful. The analysis separates changes in the average training objective from the gradient-norm and gradient-variance terms associated with sequential updates. This provides a concrete way to study how graph mini-batching affects optimization.

  2. The analysis of sampling bias and gradient variance is informative. The theoretical bounds and empirical measurements help characterize the discrepancy between subgraph and full-graph computation. The observation that RNS has comparable loss bias but substantially lower gradient variance offers a plausible explanation for its effectiveness despite substantial edge removal.

Critical weaknesses
  1. The connection between these quantities and the reported training gains remains incomplete. The measurements in Appendix G.7 are taken at random initialization, so it is unclear whether the observed patterns persist during training. Furthermore, the derivation concerns small-step SGD, whereas the main performance experiments use Adam, limiting how directly the theory explains the empirical results.

  2. The scaling evidence could be stronger. The paper already includes large graphs, but larger graphs or tighter memory budgets may require more partitions and consequently remove more edges. Further experiments would help clarify how this affects accuracy and computational cost.

Questions for authors
  1. Do the bias and gradient-variance patterns persist at early, middle, and late training checkpoints? Do their changes correspond to differences in generalization?

  2. Can a controlled SGD experiment more directly test the proposed implicit-regularization explanation?

  3. On larger graphs or under stricter memory budgets, how does the number of partitions affect accuracy, training time, and memory usage?

2 comments

We thank the reviewer for a clear review and three concrete questions. We ran all three experiments, and their results changed our interpretation, as summarized in the general response.

W1 / Q1. Do the bias and variance patterns persist during training, and do they track generalization? We recomputed loss bias, loss variance, RR, gradient bias and total gradient error at initialization and at 10, 50 and 100% of training for RNS, ClusterGCN, GraphSAINT and Neighborhood Sampling on ogbn-arxiv and ogbn-products. Figure 2 now shows these statistics through training, and Appendix G.4 reports all of them. Initialization overstated the gaps, and the text now says so.

  • RR and total gradient error. On ogbn-products, RNS ties GraphSAINT, while ClusterGCN and Neighborhood Sampling stay several times higher. On ogbn-arxiv, RNS has the lowest RR and total gradient error at every checkpoint.
  • Loss variance. RNS has the lowest on both datasets.
  • Loss bias. There is no consistent ordering (RNS has the largest on ogbn-arxiv, GraphSAINT on ogbn-products), so we no longer claim that RNS has comparable or lower bias. On ogbn-products, the ordering by RR and total gradient error (RNS ≈ GraphSAINT < ClusterGCN < Neighborhood Sampling) matches the ordering by test accuracy in Table 2. With four samplers this is a correlation, not a test. Q2 below is the causal test.

W1 / Q2. The theory is for SGD and the experiments use Adam: can a controlled SGD experiment test the explanation? Yes. On ogbn-products with plain SGD (m=10m = 10), we fixed the number of optimizer steps at 10,000 and varied one factor at a time (Section 4.2, Table 1):

Training regimeRRTest acc. (%)
Full graph–79.98 ± 0.52
Full graph, DropEdge (p=0.9p = 0.9)–82.32 ± 0.19
No batch–83.12 ± 0.13
No batch, explicit RRexplicit83.27 ± 0.27
RNSimplicit83.00 ± 0.18

The experiment supports one half of Eq. 8 and cannot resolve the other. Optimizing the sampled objective Lˉ\bar L rather than LfullL_{\text{full}} gives +3.1 points, and DropEdge with the same fraction of dropped edges recovers part of this gain, so it comes from graph perturbation. Adding the variance term RR, implicitly or explicitly, leaves accuracy within the confidence intervals, so its contribution, if any, is small. RNS reaches the accuracy of gradient descent on Lˉ\bar L at about 1/m1/m of its compute.

The same holds beyond plain SGD (Section 6.1, Table 5). With SGD with momentum and with Adam, RNS outperforms full-graph training (83.30% vs. 79.27% with momentum, 83.15% vs. 80.12% with Adam), and the no-batch update on Lˉ\bar L matches RNS (83.12% vs. 83.30% with momentum, 83.05% vs. 83.15% with Adam). This is expected: Lˉ\bar L is defined by the sampler, not by the optimizer. A formal analysis of stochastic Adam remains open, as Section 6.1 discusses.

W2 / Q3. More partitions and tighter memory budgets. We extended the sweep to m=20m = 20 and measured training-only peak GPU memory (Appendix H.2.4). Accuracies for m≤10m \le 10 use 5 seeds, and m>10m > 10 uses 3 seeds with hyperparameters fixed at their m=10m = 10 values.

mmproducts acc. (%)products memory (GiB)pokec acc. (%)pokec memory (GiB)
Full graph (H100)80.42 ± 0.5062.0683.40 ± 0.2355.43
281.48 ± 0.1327.0983.98 ± 0.0826.24
482.11 ± 0.2014.7281.97 ± 0.3813.64
1083.11 ± 0.177.5480.15 ± 0.096.10
2083.08 ± 0.255.3277.83 ± 0.153.66

Full-graph training does not fit on the 48 GB L40S used for the other rows, and its values above come from Table 2 (whole run on an H100, including evaluation). On ogbn-products, accuracy plateaus from m=10m = 10 while training memory falls by a further 30%, and epoch time stays around 0.9 s although each epoch performs mm steps. On pokec, accuracy drops by about 6 points from m=2m = 2 to m=20m = 20, and RNS exceeds full-graph training only at m=2m = 2. Section 6.2 now states this limitation. Under the tightest budgets, full-graph evaluation (14.92 GiB on ogbn-products, 8.39 GiB on pokec) becomes the memory bottleneck, from m=4m = 4 on ogbn-products and m=8m = 8 on pokec.

We thank the reviewer again: these questions led directly to the main change in the revision.

Thank you for the controlled SGD ablations. The new experiments address my main concern, and I will raise my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General answer and summary of changes

We thank the three reviewers for careful and constructive reviews. All three recognize RNS as a strong practical baseline, and all three ask whether the analysis and experiments establish why it works. We ran the controlled experiments the reviewers asked for. They support the decomposition of Eq. 8 but correct which of its two terms does the work, and we revised the paper accordingly. Changes are in blue.

What changed and what did not. Eq. 8, its derivation, the RNS bounds and the benchmark are unchanged. So is the main empirical finding: RNS improves over full-graph training, and the gain holds when we match the number of steps, tune the learning rate per row and change the optimizer. What changed is which term of Eq. 8 explains the gain. The controls attribute most of it to the sampled objective Lˉ\bar L, while the effect of the variance term RR stays within confidence intervals. The revised claim is narrower, and it rests on the experiments the reviewers asked for.

Beyond the mechanism, the paper makes two empirical contributions. First, random node sampling is used to scale classic GNNs (Luo et al., 2024), but its effect on accuracy had not been isolated. We show that it does not merely save memory: at matched steps it improves over full-graph training, and we identify why. Second, we compare five mini-batch samplers under a fixed architecture and per-method tuning, on three large graphs, seven GraphLand datasets and four backbones, and report time and memory alongside accuracy.

1. Controlled ablation (Section 4.2, Table 1). As DR2S and 21SS pointed out, the original "RNS (no batch)" row took one step per epoch, mm times fewer than RNS. We now match the number of optimizer steps (ogbn-products, GraphSAGE, SGD, m=10m = 10, 10,000 steps, learning rate tuned per row):

Training regimeRRTest acc. (%)
Full graph–79.98 ± 0.52
Full graph, DropEdge (p=0.9p = 0.9)–82.32 ± 0.19
No batch–83.12 ± 0.13
No batch, explicit RRexplicit83.27 ± 0.27
RNSimplicit83.00 ± 0.18

With steps fixed and no variance term, optimizing the sampled objective Lˉ\bar L instead of LfullL_{\text{full}} gives +3.1 points, and adding RR implicitly or explicitly leaves accuracy within the confidence intervals. Each step on Lˉ\bar L drops about 1−1/m1 - 1/m of the edges. Dropping the same fraction independently (DropEdge) recovers part of the gain, and the induced-subgraph removal of RNS does better still. We removed the claim that chained updates are necessary: what they buy is compute, since RNS reaches the accuracy of gradient descent on Lˉ\bar L at about 1/m1/m of its cost.

2. Statistics through training (Section 4.3, Figure 2, Appendix G.4). Figure 2 now tracks the terms of Eq. 8 during training instead of at initialization only. On ogbn-products, RNS ties GraphSAINT on RR and has the lowest loss variance, while ClusterGCN and Neighborhood Sampling stay at least 4 times higher. On ogbn-arxiv, RNS has the lowest RR and total gradient error at every checkpoint. Initialization overstated the gaps, and the loss bias has no consistent ordering. The text now says both.

3. Batch size (Appendix G.3.2). At a matched 1,024 supervised nodes per batch, RNS, Neighborhood Sampling and GraphSAINT have nearly the same RR (within 25% of RNS), while ClusterGCN stays at least 6 times higher, a structural effect of METIS partitions. The native advantage of RNS comes from its large batches drawn without replacement.

4. Optimizers (Section 6.1, Table 5). The pattern holds with SGD with momentum and Adam: RNS beats full-graph training with all three, and the no-batch update on Lˉ\bar L matches RNS. This is expected, since Lˉ\bar L is defined by the sampler and not by the optimizer.

5. Scaling in mm (Appendix H.2.4). Up to m=20m = 20, accuracy plateaus on ogbn-products while training memory falls from 27.1 to 5.3 GiB. On pokec, accuracy drops from 83.98% to 77.83%, a limitation we state.

6. Other changes.

  • Neighborhood Sampling with full-graph inference (Appendix H.3.2).
  • Why LADIES uses a GCN (Appendix F.1).
  • New related work: Ding et al. 2022, Chamberlain et al. 2023, Shin et al. 2023.
  • Contributions and abstract updated: "theoretically grounded" is now "theoretically motivated", and the claim of an orders-of-magnitude advantage in RR is removed.
  • The appendices are reorganized for readability: G for the implicit regularization, H for the benchmark.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.