Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Authors: Rui Xue
Tong Zhao
Neil Shah
Xiaorui Liu
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Networks
Large Scale Machine Learning
Historical Embeddings
Primary area: deep_learning->graph_neural_networks

Abstract: Graph neural networks (GNNs) have demonstrated remarkable success in graph representation learning and various sampling approaches have been proposed to scale GNNs to applications with large-scale graphs. A class of promising GNN training algorithms take advantage of historical embeddings to reduce the computation and memory cost while maintaining the model expressiveness of GNNs. However, they incur significant computation bias due to the stale feature history. In this paper, we provide a comprehensive analysis of their staleness and inferior performance on large-scale problems. Motivated by our discoveries, we propose a simple yet highly effective training algorithm (REST) to effectively reduce feature staleness, which leads to significantly improved performance and convergence across varying batch sizes, especially when staleness is predominant. The proposed algorithm seamlessly integrates with existing solutions, boasting easy implementation, while comprehensive experiments underscore its superior performance and efficiency on large-scale benchmarks. Specifically, our improvements to state-of-the-art historical embedding methods result in a 2.7\% and 3.6\% performance enhancement on the ogbn-papers100M and ogbn-products dataset respectively, accompanied by notably accelerated convergence. The code can be found at https://github.com/RXPHD/REST.

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Rui Xue Tong Zhao? 2
Neil Shah?
Xiaorui Liu
Abstract
data (Hamilton, 2020). They exhibit significant advantages across various general graph learning tasks, including node classification, link prediction, and graph classification (Kipf & Welling, 2016; Gasteiger et al., 2019; Veličković et al., 2017; Wu et al., 2019; Xue et al., 2023b). GNNs have also proven to be highly effective in various applications, such as recommendation systems, biological molecules, and trans- portation (Tang et al., 2020; Sankar al.. 2021; Fout et al., 2017; Wu al., 2022; Zhang al., 2024). However, scala- bility becomes a dominant bottleneck when applying GNNs to large-scale graphs. This is because the recursive feature propagations in GNNs lead to the notorious neighborhood explosion problem since the number of neighbors involved in the mini-batch computation grows exponentially with the number of GNN layers (Hamilton et al., 2017: Chen et al., 2018; 8; Han et al., 2023). This is particularly undesirable for deeper GNNs that try to capture long-range dependency on large graphs using more feature propagation layers. This neighborhood explosion problem poses a significant chal- lenge as it cannot be accommodated within the limited GPU memory and computation resources during training and in- ference, which hampers the expressive power of GNNs and limits their applications large-scale graphs.
Graph neural networks (GNNs) have demon- strated remarkable success in graph representa- tion learning and various sampling approaches have been proposed to scale GNNs to applica- tions with large-scale graphs. A class of promis- ing GNN training algorithms take advantage of historical embeddings to reduce the computation and memory cost while maintaining the model expressiveness of GNNs. However, they incur significant computation bias due to the stale fea- ture history. In this paper, we provide com- prehensive analysis of their staleness and infe- rior performance on large-scale problems. Mo- tivated by our discoveries, we propose simple yet highly effective training algorithm (REST) to effectively reduce feature staleness, which leads to significantly improved performance and con- vergence across varying batch sizes, especially when staleness is predominant. The proposed al- gorithm seamlessly integrates with existing solu- tions, boasting easy implementation, while com- prehensive experiments underscore its superior performance and efficiency on large-scale bench- marks. Specifically, our improvements to state- of-the-art historical embedding methods result in 2.7% and 3.6% performance enhancement on dataset
Existing works have made significant contributions to ad- dress this issue from various perspectives, such as sam- pling, distributed computing, and pre-computing or post- computing approaches. In this paper, we focus on the most commonly used sampling approaches. In particular, various sampling approaches have been proposed to mit- igate the neighborhood explosion problem in large-scale GNNs (Hamilton et al., 2017; Chen et al., 2018; Chiang et al., 2019; Zeng et al., 2020). These sampling approaches attempt to reduce the graph size by sampling nodes and edges to lower the memory and computation costs in each mini-batch iteration. However, they also introduce estima- tion variance of embedding approximation in the sampling process, and they inevitably lose accurate graph information.
the ogbn- papers100M and respectively, accompanied by notably acceler- ated convergence. The code can be found at https:// triithun www.hh...ooo...ccec
1. Introduction and Related Works
Graph neural networks (GNNs) have emerged as power- ful tools for representation learning on graph-structured
DDepartment of Electrical and Computer Engineering, North Carolina State University, Raleigh, US 'Snap Inc., Bellevue, US DDepartment of Computer Science, North Carolina State University, Raleigh, US. Correspondence to: Xiaorui Liu Exliu96@ncsu.cdu.
Historical embedding methods have emerged as promising solutions to address this issue, such as VR-GCN (Chen et al., 2017), MVS-GCN (Cong et al., 2020), GAS (Fey et al., 2021), and GraphFM (Yu et al., 2022). They propose to reduce the estimation variance of sampling methods using historical embeddings. Specifically, during each training iteration, they preserve intermediate node embeddings
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
each GNN layer as historical embeddings, which are then used reduce estimation variance in future iterations. The historical embeddings can be stored offline on CPU memory or disk and will be used to fill in the interddepen from nodes out of the current mini-batch. Therefore, it does not ignore any nodes or edges, which reduces variance and keeps the expressivity properties of the backbone GNNs with strong scalability and efficiency. Please refer Appendix M for detailed summary of related works.
methods yield a 2.7% and 3.6% performance boost on the ogbn-papers 10mm and ogbn-products dataset respectively. Notably, these improvements are achieved with significantly faster convergence times without sacrificing efficiency.
2. Preliminary Study
In this section, we illustrate that the staleness of historical embeddings serves the bottleneck for existing historical embedding approaches when handling large-scale graphs. We aim to support this claim with empirical studies on prediction performance, training convergence, memory per- sistence, and approximation errors.
Despite their promising scalability and efficiency, in this pa- per, we discover that all historical embedding methods can not consistently outperform vanilla sampling methods such as GraphSAGE which do not utilize historical embeddings, especially on larger graph datasets. Moreover, their predic- tion performance and convergence suffer from significant degradation when the batch size decreases. Although some existing works have attempted basic analyses (Huang et al., 2023; Wang et al., 2024), these efforts are quite limited, and the underlying reasons remain unclear. In this paper, we provide the first and most comprehensive analysis, incorpo- rating both theoretical and empirical studies, to reveal the emergence of significant embedding staleness with these methods and its severe negative impact on GNN training. Our preliminary study reveals that the primary obstacle lies in the fact that these stored historical embeddings are not computed by the most recent model parameters, leading to a phenomenon known as staleness. Staleness represents the approximation error between the true embeddings computed using the most recent model parameters and the stale embed- dings cached in the memory. This issue is pervasive across all historical embedding methods and significantly impacts training convergence and model performance, particularly when models undergo frequent updates-suun -uch as training GNNs on large-scale graphs with smaller batch sizes. Due to the substantial bias introduced by stale embeddings, these approaches cannot fully realize their potential in perfor- mance, despite their excellent efficiency and scalability.
2.1. Message Passing with Historical Embeddings
Formulations. Let h2 represent the feature embedding of the in-batch node v in I-th layer and I denote the message passing update in a 1-th layer with parameter 0. The standard sampling method for mini-batch B C V can be expressed as follows:
h(+1) = -1(+1(1 ((llee()))))
(1)
where N((v) n B is the in-batch 1-hop neighborhood of in-batch node v. As discussed in the introduction, the sampling methods (e.g., GraphSAGE, FastGCN) drop all out-of-batch neighbors (V()) B and cannot aggregate their embeddings (w)) which results in high estima- tion variance. To address this issue, historical embedding methods use historical embeddings [N to approx- imate [Nal N(w) GAS (Fey et al., 2021) can be denoted as:
N())) B. For example, the message passing in
k0+11) = 18(+1) (My, (NleeN(o))
(2)
= 1o (1(+1) (bb, (bb, (h Unluevion U
Uileetioee )
in butch neighbors
out batch neighbors
Motivated by our findings and analysis, we propose sim- ple yet highly effective solution to reduce feature staleness by decoupling the forward and backward phases and dy- namically adjusts their execution frequencies, allowing the memory table to be updated more frequently than the model parameters. Our aim is to alleviate the current bottleneck on performance and convergence while preserving excep- tional efficiency. Our proposed framework is highly flex- ible, orthogonal and compatible with any sampling meth- ods, meemory-based models, and various GNN backbones. Comprehensive experiments demonstrate its effectiveness in addressing the significant staleness issue present in large- scale datasets, leading to superior prediction performance and accelerated convergence while maintaining or even im- proving running time and memory efficiency. Specifically, our enhancements to state-of-the-se historical embedding
se (1+1) (bby, [nllevionn (Flleet)))))))) in-batch neighbors
historical embeddings
followed by feature memory update h4+1 = 111 It is evi- dent that historical embedding methods effectively reduce the estimation variance of h (1+1) without further expansion on the neighbor size. An illustrative example is presented in Figure to elaborate on these concepts. However, these historical embedding methods also incur larger estimation bias due to the approximation using historical embeddings.
2.2. Empirical Study
Inferior performance. While historical embedding meth- ods exhibit both strong performance and scalability on small-
2

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
GAS; however, in all other cases (when staleness is large), GraphSAGE converges more rapidly and achieves better performance. Despite GraphFM's utilization of current one hop neighbors to mitigate staleness, its impact is limited. This observation supports our earlier conclusion that histori- cal embedding methods perform well when staleness is not dominant but face limitations in realizing their full potential under conditions of high staleness.
In batch nodes
Direct I-hop Out batch nodes
Other Out of batch nodes
Figure 1: We sample a batch with a batch size of 2 (e.g., nodes 1 and 2), their direct one-hop neighbors are nodes 3 and 4. Nodes 1 and 2 are considered "in-batch" nodes, as
Test Accuracu a
Accuured
0.6
SAGL(Smmlli GAStSmall
Smaln
they always use real-time updated embeddings and partici- pate in model updates with gradient computation; Nodes 3
GASISmall!
SAGE (large)
SAGE (Larça)
GAS [Large!
0.2
GAS (Larpe)
and 4 are considered "direct one hop out-of-batch" nodes (simply referred to as "out-offbatchh nodes (Yu et al., 2022)) because they are approximated using historical embeddings and their embeddings are not real-time updated; Node 5 is called "other out-of-batch" node that is not used in the current iteration.
20
40
00
100
0
10
20
30
40 50
Epachs
Epochs
(a) GAS-oghn--rxiv
(h) GAS- -oo-ooubn-sssuucts
Test Accuracy
as 0.
0.
Test Accuragy
0.7
SAGe PMISmall
SAGErSmal)
scale and medium-scal graph datasets, they not con-
E.
[M/Smal]
sistently outperform simpler variants such as GraphSAGE, Cluster-GCN, and GraphSAINT on larger datasets such as Reddit and egbn-products as shown in multiple works (Fey et al., 2021; Yu et al., 2022; Xue et al., 2023a). The bitter truth is that their prediction performance can be signifi- cantly inferior in many cases even though they cost much more offline memory to store hidden features in all inter- mediate layers. For example, as one of the taate-of-the-art historical embedding methods, GAS (GCNII) achieves only 77.20% accuracy on ogbn-products while GraphSAGE and GraphSAINT achieve 78%70% and 79.08%. The potential of historical embedding methods significantly limited. How- ever, their fundamental limitations of inferior performance are yet unclear. Next, will provide comprehensive analysis from the feature staleness perspective.
2
SAGEE (Lange)
FN [Large!
SAGE (Larg:)
IM (Large)
40
00
100
10
20
40
50
Epochs
Epochs
(c) FM-ogbn-arxiv
(d) FM-oobn-prooducts
Figure 2: GAS and FM exhibit inferior performance and slower convergence, especially larger datasets (i.c., (gbn-productt) small batch size (i.c., "Smalll".
Memory persistence. To clearly illustrate staleness, we introduce new notation of "memory persistence" for each node embedding, which quantifies the duration that histor- ical embedding remains in memory before being updated, measured in the number of optimizer steps. A large memory persistency means it has not been updated frequently, which may lead to stronger feature staleness. We present the aver- age memory persistence over all nodes GAS (Fey et al., 2021) on ogbn-arxiv and ogbn- -oooduutstttss datasets with vary- ing batch sizes in Figure 3. It can be observed that smaller batch size incurs larger memory persistence. In particular, when employing batch size of 1024 on oghn-products, the model experiences around 2400 updates before updating the historical embedding, which results in a considerable persistence of stale features.
Convergence analysis. We present a deeper empirical con- vergence analysis to reveal the performance bottleneck of historical embedding methods. To underscore this point, we present convergence curves comparing GraphSAGE. two representative historical embedding methods, GAS and GraphFM with GCN as backbone. We explore the impact of staleness accuracy and convergence by using datasets of different scales (ogbn-arxiv arxiv and ogbn-proe baobn-productsann ex- perimenting with both small and large batch sizes. Compar- isons are conducted under identical hyperparameter settings. "Small" and "Large" denote the small and large batch sizes settings, respectively. In particular, when using small batch sizes or larger graphs, model updates occur more frequently within single epoch. Consequently, staleness becomes significant and exerts a dominant influence on performance.
Embedding approximation errors. We present Figure to show the approximation error of the embeddings between GAS and full batch [[ - 1 on ogbn-arxiv and ogbn- products. Please refer Appendix for GraphFM.
As shown in Figure 4, the embeddings in the final layer gradually diverge from the true embeddings computed using full-batch data as the model parameters are updated through stochastic gradient descent. Consequently, the approxima- tion errors accumulate and grow over epochs due to the accumulated staleness of the historical embeddings. These empirical analyses demonstrate that historical embedding
From Figure 2, when using the small agbn-arxiv dataset with a larger batch size (staleness is minor), GrE exhibits slower convergence and poorer performance than
3

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Memory pers persistence
1200.0 0
1000.0
sybn-ansiy
Memorry parcitance
2500.0
2000.0
oghn
Approkimation Enrer
0.91
mm
8 1.350
3,721
1,200
1.175
e00.0
1500.0
1.323
e00.0
400.0
1000000
0.86
007
1.300
1,775
200.0
0.0
128
512
1024
0.0
1024
8192
32768
0
10
15
20
25
10
15
20 25 Epochs
30 35 40
Batch Sizes
Batch Sizes
Epochs
Figure 3: Embedding Memory persistence (GAS).
Figure Approx. Error on Arxiv(I.) and Products(R).
methods such as GAS are significantly influenced by the quality of the historical embeddings utilized for message passing.
approximation error, we can efficiently minimize this error accumulation across layers and tighten the upper bound.
3.2. REST: REducing STaleness
3. Methodology
As discussed in Appendix M, existing works such as GAS (Fey et al., 2021), GraphFM-OB (Yu et al., 2022), and ReFresh (Huang et al., 2023) endeavor to tackle stale- ness from various angles, such as minimizing nodes inter- connectivity, applying regularization techmiques, employing feature momentum by in-batch nodes, and expanding in- batch neighbor size, to alleviate staleness. However, these approaches can not control the staleness effectively and ef- ficiently. Consequently, they typically yield only marginal performance improvements. We attribute this to their inabil- ity to resolve the staleness issue stemming from the disparity in updating frequency of model parameters and the memory tables for historical embeddings. Therefore, we propose a simple yet novel approach to adjust the frequency of for- ward and backward propagation, addressing this problem at its root. Note that our model is orthogonal to all of the existing techniques and can be seamlessly integrated.
In this section, we first elucidate the primary factor influ- encing the final performance through theoretical analysis. Subsequently, we introduce simple yet novel and effec- tive approach designed to mitigate staleness at its source, thereby significantly enhancing performance. Furthermore, we present an advanced version that takes into account the importance of nodes, demonstrating improved robustness and performance, particularly in scenarios where staleness is pronounced.
3.1. Approximation Error Analysis
While a historical embedding approaches efficiently pre- serve the expressive power of the original GNNs and reduce variance, they introduce approximation errors between the exact embeddings and historical embeddings. This limita- tion becomes more pronounced, particularly in scenarios with large graphs or when employing deep GNN models. To illustrate this challenge and provide motivation for our work, we first introduce a theory to demonstrates that the approximation error of the gradient can be upper-bounded by the accumulation of staleness in each layer. We adhere to the assumptions used in existing works (Fey et al., 2021). Theorem 3.1 (Gradient Approximation Error). Consider a L-layers GNN f( (h) with Lipschitz constant (t),, UPDATE function with Lipschitz constant 8, 3,11 1=1, L. Lo has Lipschitz constant e. If Ve E V, [|7(0) - h001 denotes the staleness between historical embeddings and true embeddings from full batch aggregations, then the ap- proximation error of gradients is bounded by:
In standard training procedures, forward and backward prop- agation are typically interconnected. During forward prop- agation, intermediate values are computed at each layer, which are then used during backward propagation to com- pute gradients and update the model parameters. This cou- pling ensures that the gradients computed during backward propagation accurately reflect the effect of the model param- eters on the loss function, allowing for effective parameter updates during optimization. Under these limitations, it is natural to mitigate feature staleness by using larger batch sizes, but it will cost higher memory and computation costs.
Effortless and Effective Staleness Reduction. In histor- ical embedding methods, in addition to the computation of intermediate values, forward propagation also plays a role in updating the memory table by in-batch nodes. Con- sequently, only the historical embeddings of the bn-batch nodes are updated during a single training iteration. Taking GAS as an example, the entire table completes an update after to = training iterations, where is the number of nodes and B is the batch size. However, during this period, model parameters undergo updates & times. The inability to refresh historical embeddings using the most recent parame- ters results in the approximation errors and it accumulates
(h( (Io
(5)
<e
Σ
II a ( BIN(()) * ||...11 * (1](t-11 1k h1-1111) k=1+1
The proof of the above theorem and the explanation of the assumption can be found in Appendix A. We can conclude that the gradient is influenced by the number of layers L, the number of neighbors (v)), and the per-layer approxima- tion error (x-1)) 11(k-)]]] we effectively reduce the

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
at each training iteration. When retrieving the embedding from memory, this error introduces significant bias to the final representation, illustrated in Figure 4. The root issue lies in the fact that the frequency of updating the memory table is too slow compared with the frequency of model up- dates. The disparity between the frequency originates from the forward and backward propagation are tightly coupled.
dings methods such as GAS, LMC, and REST, which is
2(L(0)) - LG + Go)
<Go
Go
+ N N(1
N
vP)
(6)
where Go is the upper bound of gradient approximation error, Nis the number of iterations, Ris chosen uniformly from [N], P E 1). Based on Theorem 3.1, the upper bound Gøof REST is tighter than that of existing historical embedding methods. Consequently, the convergence speed of REST surpasses that of existing works.
Building upon this analysis, we propose to simply decou- ple the forward and backward propagations and adjust their execution frequency. The process is illustrated in Figure 5 and outlined in Algorithm 1. Specifically, F times the for- ward propagations on batch B| BF are initially executed without requiring gradient (line 7). This process updates the memory table at each layer using in-batch nodes exclusively. Subsequently, another forward propagation with different batch Bj is executed with requiring gradients for the fol- lowing model update by backward (line 10). The updated embeddings from every forward propagation (line 11 and line 8) are then cached in memory to facilitate the updat- ing of embeddings and mitigate staleness issues. Hence, our REST approach effectively reduces the gap in update frequencies from A to $. The hyperparameter F directly governs the staleness and allows for flexible adjustments without increasing memory cost. Our experiments in Ap- pendix D empirically demonstrate that employing F = 1 not only yields significantly improved performance com- pared to baselines but also accelerates convergence than baselines. This training process is very simple and flexi- ble since forward passes are relatively cheap and trivially parallelizable. For example, it can be further accelerated by parallclizing the forward propagations (line 7 and line 10) on multiple GPUs. However, in this paper, we only use single GPU for fair comparison with the baselines.
The detailed proof can be found in Appendix B. In addi- tion to its simplicity, REST exhibits remarkable generality, Notably, REST can also address staleness in backward by maintaining a historical gradient cache and updating it at different frequency F without updating model parameters (see Bidirectional REST in Section 4.5). Furthermore, for the application of REST to asynchronous updates, please refer to Appendix for the discussion.
3.3. REST: Sampling Strategy
It's crucial to emphasize that our algorithm is versatile and applicable to any historical embedding methods. Further- more, this flexibility also extends the sampling strategy employed in forward propagation, encompassing various techniques such as uniform sampling, importance sampling, and any custom sampling method tailored to the specific re- quirements of the task at hand. Here, we propose a fcasible option to further address the staleness issue by consider- ing the varying significance of individual nodes within the graph, termed REST-IS (Importance Sampling). Notably, nodes with high degrees are more likely to serve as neighbor nodes for the sampled nodes, making more substantial contribution to the final representation and carrying higher importance. The staleness in these highly important node embeddings makes a more detrimental impact on perfor- mance compared to nodes with lower importance.
Algorithm 1 REST Technique
1: Input: Input graph G EV, GNN 00)
2: Output: Fine-tuned GNN O(X
3: Begin
4: for each mini- batch .B:
5: each mini-batch B, do
6: for i in updating frequency F do
Motivated by this potential issue, rather than employing conventional importance sampling techniques, we propose novel and efficient method for importance sampling. Our method utilizes the neighbor nodes from batch (B, in Al- gorithm 1) in the forward propagation for model updates (line 10) and lets them serve as the in-batch nodes in batch B = B U B2 ... U BF for updating the memory table (line 7). We are motivated by the fact that if one node is frequently served as neighbor nodes by different batches, it's likely to holds higher importance than other nodes in the graph. We summarize this approach by presenting formulas:
7:
H, = [B, @+): offline forward propagation 8: Cache into memory M t banihhhttch]
9:
end for
10:
H2 f(B,, )+:: forward propagation with back-
ward
11: Cache into memory M < [g[[inbatch]
12: Compute loss and gradient update
13:
end for
Finally, we can prove that REST achieves a faster conver- genee rate theoretically (Chen et al., 2017; Shi et al., 2023):
Theorem 3.2. Given the upper bound of the expectation of gradients' norm in the state-of-the-ar historical embed-
h(+1)_ = -o (1(+))(b), (b..:
5

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Model update
Mini-batch feature update
Forward
F+1
Forward
Forward
Forward
Forward
Mini-batch for model update
Backward
Backward
Forward
Forward
No gradient
With gradlint
No gradient
With gradivent
Feature update
11
11
Feature retrieve
Festure
Feocure
Feacure
Festure
Figure 5: Training process for the proposed REST technique. (1) F mini-batches ..... ...B (blue ellipse) are executed without computing gradients to update memory table (2) Another one mini-batch B (yellow ellipse) is processed with gradient computation to update the model parameters.
-1(+1) (he (h Moluesoon U ((llaeNo))))
(8)
et al., 2023) in Appendix O, which have not yet been of- ficially published or do not have publicly available code, ensuring that our results are as comprehensive as possible. The hyperparameter tuning of baselines closely follows their default settings (See Appendix R). Besides, have chosen to stick to the baseline settings (such as sampling methods) in this work to maintain consistency across our baselines although numerous sophisticated tricks could potentially enhance performance. We emphasize that our proposed method is orthogonal to them. For our model, we choose a frequency of F 1, as it has been proven to be effective in ablation study. The performance is shown in Table 1. In instances where performance metries hyperparameters are not reported, we denote them with "-" to align with the baseline papers. OOM stands for out-of-memory. Note that, REST uses default uniform sampling while REST-IS uses proposed importance sampling.
fot+1) h1. DillweN(t))
uls (Ker MolweN(wn U (oLIENN (o)(B)
Historical
(9)
Similar to the initial approach, we employ historical em- beddings (Wwle for these out-of-batch nodes. Sub- sequently, we store both the in-batch nodes (1 (ww) and the in-batch nodes [ into memory for up- dating historical embeddings, as they are all freshly com- puted. As only neighbor nodes are chosen as in-batch nodes during memory table update, this approach simply and ef- ficiently accounts for the importance of each node. This approach can be especially helpful when dealing with a high staleness situation, as shown in our experiments.
4. Experiments
4.1. Performance
In this section, we conduct experiments to showcase the superior ability of our proposed algorithms in improving the performance while accelerating the convergence, especially when staleness is predominant.
Table showcases the accuracy comparison of REST and REST-IS with state-of-the-arr bascline methods across mul- tiple backbones. We can observe the following:
All historical embedding methods exhibit inferior per- formance compared to simple models like GraphSAGE on the large dataset, ogbn- products, aligning with our earlier observations. Note that GraphFM uses in-batch nodes to compensate for staleness to a certain extent. However, only achieves marginal improvement. This stems from their inability to eliminate staleness at its source, as discussed in the Section 3.2, whereas our approach can.
Experimental setting. We first provide a best perfor- mance comparison with multiple major baselines includ- ing GCN (Kipf& & Welling, 2016), GraphSage (Hamilton et al., 2017), FastGCN (Chen et al., 2018), LADIES (Zou et al., 2019), Cluster- GCN (Chiang al., 2019), Graph- SAINT (Zeng et al., 2020), SGC (Wu et al., 2019), GN- NAutoScale(GAAS) (Fey et al., 2021), VR-GCN (Chen et al., 2017). MVS-GCN (Cong et al., 2020) and GrpahFM (Yu et al., 2022) on three widely used large-scale graph datasets including REDDIT, ogbn-arxiv, and ogbn-products (Hu et al., 2020). Based on our current computation resources, we also include two larger datasets, agbn-papers 100m and MAG240M, in Appendix E. For our model, we opt use GAS based approach for simplicity since it's proven the best (Fey et al., 2021). We provide comparison with recent related baselines Refresh (Huang et al., 2023) and LMC (Shi et al., 2023) in Appendix G. We also include compar- isons with several minor baselines (Wang al., 2024; Bai
Compare with all other baselines on large scale datasets, our proposed algorithms outperform all baselines on ogbn- arxiv and ogon-products and reach comparable performance on Reddit. Specifically, REST can achieve 73.2% on ogbn- arixv and 80.5% on ogbn-products. Note that, it boosts the performance of GAS by 3.6% when using APPNP as GNN backbone. The only exceptions are that GraphSAINT slightly outperforms our method. However, they require complicated and time-consuming preprocessing.
6

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
When combined with results from larger datasets such as oghn-products, oghn-papers1000 and MAG240M, which exhibit significant staleness, our model demonstrates sub- stantial performance boost compared to smaller datasets (e.g., ogbn-arxiv) (see Appendix E). This clearly indicates that our approach effectively addresses the staleness issue. Given the increasing size of datasets in practical, these re- sults highlight the potential and necessity of our work.
Table 2: Accuracy (%) improvement for GAS. Cyan denotes the best performance under a specific GNN model.
DATASET
GNN
PARTS
BS
GAS
+REST
+REST-IS
5
75.6
0.4
77.6 0.2
77.9 + 0.2
GCN
70
10
76.5
+.2
7944-02
78.6 + 0.1
7..0
0..7
0.
Products
APPNP
40
76.8 =
80.1
80.4
GCNII
150
74,8
74.8+00. 0.6
75.9
76,2 + 0.3
20
76.9 0.3
79.8 0.3
79.6 + 0.2
Table I:
Accuracy comparison (%) with major baselines.
GCN
200
20
94.8
+ 0.2
95.3 0.1
95.4 + 0.1
100
95.4
95.6 0.1
95.7 0.1
Cyan denotes the best performance under a specific dataset.
20
92.620.2 0.2
0..
96.1 0.1
Reddit
APPNP
200
# podes # Bedges
230K
169K
2 2.4M
100
96.0 + 0.1
96.4 0.1
96.5 +: 0.1
Framework
GNNs
REDDIT
11.6M
ARXIV
1.2M
PRODUCTS
61.9M
GCNI
200
100
93.9
96.7 0.1
95.7 0.1
96.8
96.8 0.1
95.7 0.1
Major
GraphSAGE
95.4+ 0.2 71.5+ 0.2
78.7+ 0.1
67.6
71.1
71.9 0.1
FasiGCN
93.7:1 0.1
69.5 0.5
71.3+
72.1 0.1
LADIES
92.8:1 0.2
GCN
80
20
70.6
1..6:00
71.5
72.2 + 0.2
ChutterGCN
96.6+t 0.1
79.0 0.2
40
71.5 + 0.2
72.2++0.1
72.3 + 0.2
GraphSAINT
97.0:1
79.1
5
6.
12.3 7..2
SGC
96.41
Arxiv
APPNP
10
7.30
72.4 722
VR-GCN
94.1=
71.6 0.1
76.41 0.1
20
0.
0.14
72.3
MVS-GNN
94.92 71.6 0.1
76.9 0.1
70.0
0.6
72.7
72.7+022
Full Batch
GCN
95.41 0.2
0.1
0OM
GCNII
71.9
02
72.7 0.1
APPNP
96.1 7.8
0OM
20
72.5
0.3
0.11
72.8 + 0.2
GCNII
9611= 0.2
00M
GAS
GCN
95.4 0.1 0.2
76 76.9 0.1
APPNP
96.01
71.91 0.2
Table 3: Improvement (%) for VR-GCN and MVS-GCN.
GCNII
96.7= 0.1
0.1
77.2 0.3
GruphI.M
GCN
9541 0.2
0.2
0.2
Cyan and Magenta indicate the best performance for them.
GCNII
96.8 72.91
77.41
REST (Ours)
GCN
9..6
72.2::.22
79.6
Dataset
Batch Size
VR-GCN
+REST
+REST-IS
APPNP
9.14= 72.4 0.1
80.0 0.1
10000
76.3 1.3
77.4
78.0 0.2
Products
GCNII
96.8 0.1 73.2+ 0.1
79.8+ 0.2
50000
76.4 4: 0.1
77.5 0.
78.1 #.2
REST-IS (Our)
GCN
95.7 0.1
0.1
256
91.7 0.2
93.8::02.
94.1 0.1
APPNP
96.5= 0.1 72.4#
0.2
Reddit
512
93.0 1: 0.2
94.1
94.2 0.2
GCNII
96.8 72.8+ 0.2
79.6 0.3
2048
94.1 0.1
9..5
94.3
4.2. Improvement for Historical Embeddings
128
70.4 1 0.3
0.
71.9
0.1
512
71.5 0.3
724 7..3+-0.
Arxiv
Experimental setting, According to our analysis in method- ology, our proposed approach can efficiently reduce the staleness in all of the memory-based algorithms, especially when the batch size is small. Hence, we conduct further experiments under different batch sizes to show the effec- tiveness of our algorithm. We first present a comparison with three representative historical embedding methods, GN- NAutoScale (GAS) (Fey et al., 2021), VR- GCN (Chen et al., 2017) and shown in Table 2 and Table 3. In these experiments, we closely adhere to their settings, including the datasets they utilized in their paper and official repositories.
2048
71.5
0.21
72.1
0.2
8192
71.6
0.1
72.1 033
Batch Size
MVS-GCN
+REST
+REST-IS
10000
77.9 76.7 0.2
0,3
Products
50000
76.9 1
7.21
78.3 0.3
256
0.2
9.25
9..7
Reddit
512
0.1
9.1
9,
2048
94.9
9..2
95.2 95.2.10.2 0.2
128
70.9
0.29
0,3
512
71.4
1.1
72.5
1.5::00 0,3
(Cong et al.. 2020). The results are
Arxiv
2048
71.5 4 0.1
02.0
72.1 0.1
8192
71.6
72.1
0.11
72.0
Our algorithms outperform all the baselines by substan- tial margin, particularly in scenarios with significant staleness, such as large datasets or small batch sizes. We also show similar results of GraphFM in Appendix J. For example, on the ogbn-arxiv dataset, we observe a perfor- mance boost of 2.4% with REST and 3.0% with REST-IS using batch size of 5 and APPNP as backbone. Similarly, ogbn-products, our algorithms outperform GAS by 4.7% with REST and 5.4% with REST-IS under the same hatch size setting. The similar phenomenon is noticeable when our approach is implemented on VR-GCN and MVS-GCN.
In detail, both VR-GCN and MVS-GCN leverage neigh- bor sampling, akin to the approach introduced by Graph- SAGE (Hamilton et al., 2017), whereas GAS adopts dif- ferent strategy. GAS begins the process by employing the METIS algorithm to partition the graph into distinct clusters. Following this partitioning, one or more of these clusters are thoughtfully selected to constitute a batch for computation purposes. The total number of clusters is detailed in Table 2 under the name "parts". The number under "BS" (batch size) indicates the number of clusters included in one batch. Performance Analysis. From results, we can observe:
Our proposed algorithms exhibit exceptional adaptabil-
7

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
small batch size
large batch size
small batch size
large batch size
0.7
0.7
0.8
0.8
0.6
MM My 1
0.6
0.7
0.7
0.5
Accuracy
0.5
0.6
Accura
0.4
Accuracy
0.5
0.3
REST
0.3
REST REST-IS GAS
REST
0.4
REST REST-IS GAS
0.2
REST-IS
0.2
0.3
REST-IS
0.3
0.1
GAS
GAS
0.2
0.0
20
40
60 to
100
120
140
0.0
20
40
60
60
100
0. 1000 2000 2000 4000 Time(s)
5000 6003
0.1
6 1000
2000
3000 Time(s)
4000
5000
Time(s)
Time(s)
Figure 6: Convergence on ogbn-arxiv.
Figure 7: Convergence ogbn- rgbn-products.
ity by seamlessly integrating with all historical embedding methods and surpassing the performance of three promi- nent historical embedding methods. This showcases the flexibility and universality our algorithms.
cal embedding model, addressing the staleness issue without modifying the model architecture. As a result, it preserves the memory efficiency of the original baselines while achiev- ing better performance and expediting the training process. This attributed to REST's faster convergence (see Theo- rem 3.2), which requires substantially fewer epochs to con- verge, despite longer per-epoch runtime due to multiple forward passes (see Figure 8, 9, 10 and 11 in Appendices).
It is important note that our proposed methods designed to alleviate the staleness issues present in baselines. Staleness
those historical embedding-baseee only becomes significant when dealing with large-scale datasets, which explains why our model demonstrates sub- stantially larger improvements on datasets such as ogbn- products, oown-gapeeeeee 100M, and MAG240M compared to other datasets (see Appendix E). These results clearly indi- cate that our algorithm effectively mitigates staleness, and substantial enhancements can be easily achieved with differ- ent GNN backbones.
4.4. Convergence Analysis
We present comparison of convergence analysis by show- ing test accuracy with respect to the running time for both GAS and our algorithms on the ogbn-arxiv and ogbn- products datasets with different batch sizes. Specifically, we represent small and large batch sizes using 5 and 10 clus- ters for both datasets. The convergence curves are shown in Figures 6 and 7, respectively. The results illustrate that our model not only achieves superior performance but also converges faster. This advantage is more evident when there is significant staleness, such as when smaller batch sizes are used or with larger datasets as shown in the first subfigures in Figures and 7. Importantly, the convergence of GAS is significantly influenced by staleness. However, our model's s convergence speed only experiences a slight decrease as staleness becomes larger, which supports the convergence advantage discussed in introduction. Compared to REST, REST-IS appears to be more stable after convergence. We conclude that this is attributed to that we continually refresh the embeddings of important nodes. All observations indi- cate that our algorithm possesses advantages in convergence beyond mere performance metrics. We also conducted sim- ilar experiments demonstrating convergence over epochs using GAS and VR-GCN in Appendix C. We can draw the same conclusion that convergence is accurately achieved by our algorithm, regardless of the historical embedding methods used. Please also refer to Appendix K for SAGE.
4.3. Efficiency Analysis
To verify the efficiency of our proposed approach, we pro- vide empirical efficiency analysis compared with one scal- able GNNs, GraphSAGE and two historical embedding methods, VR-GCN and GAS in Table 4 and Table 5. Specif- ically, we measure the memory usage, total running time and the approximate number of epochs until convergence for training process on the ogbn-arxiv and ogbn-products under different batch sizes. Note that, the number under "Batch Size" indicates the number of sampled clusters in one batch in Table 4. We used a server, and all experiments were run on a single NVIDIA A6000 GPU. To ensure a fair comparison, we employ the same official implementations for all baseline methods (Fey et al., 2021; Shi et al., 2023) as well as our proposed method. For GAS, we use the APPNP with 5 aggregation layers as the GNN backbone and keep all other hyperparameters the same to make a fair comparison. We also include the performance on the same table for the convenience.
It's important to note that GraphSAGE may still encounter the neighbor explosion problem, leading oft-ory (OOM) errors for ogbn-products and significantly higher memory costs for ogbn-arxiv in our experiments. REST demonstrates comparable running time to GraphSAGE while achieving superior performance and significantly lower memory costs. Compared to GAS and VR-GCN, our approach is designed to be compatible with any histori-
4.5. Ablation Study
In this subsection, we present detailed ablation studies on the impact of important hyperparameters and the generality of our approach.
Forward batch size B for memory table update. In ad- dition to the flexible adjustment of the updating frequency
8

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Table 4: Memory usage (MB), Total running time (seconds) and Epochs on ogbn-arxiv and ogbn-products.
(EM)RY(MB)
TOTAL TIME(S) / EPOCHS
ACCURACY
Dutaset
Parts
Batch Size
SAGE
GAS REST REST-IS
SAGE
GAS
REST
REST-IS SAGE
GAS REST REST-IS
5
00M
8913
9295
10059
N/A
2600 75
1170 1312/15 18
N/A
75.2
79.7
80.5
oghn-products
40
10
0OM
13406
13495
14753
N/A
1890 65 940/ 18 1200 / 18
N/A
76.9
80.0
80.4
3011
790
837
703
39
67.5 60
/9/16
42/15
70.9
69.4
71.7
72.1
ogbn-arxiv
10
3156
997
1115
948
37.2/33
54.0/ 58
315/18
33/18
712
70.1
72.3
72.4
20
3323
1486
1505
1262
25.8/32 32 39.6/ 50 24.0/
1
71.
71.5
72.4
72.4
Table Memory usage (MB), Total running time (seconds) and Epochs on ogbn-produce
MEMORY (MB)
TOTAL VVRGGN REST REST-IS VR-GCN REST REST-IS
TIMB(S)/ # EPOCHS
ACCURACY((6)
Batch Size
VR-GCN REST REST-IS
10000
8730
8733
9119
2892 25 2616 / 12 2275/11 11
76.3
77.4
78.0
50000
15402
17585
16322
1104/21
936 11
920/10 10
76.4
77.5
78.1
f. our algorithm offers another advantage: the batch size during the memory table updating process can also be rea- sonably increased since it does not require significant mem- ory for backward propagation. Please refer Appendix F for all results. The presented results indicate that larger batch size used in updating the memory table has the potential to further enhance performance by reducing staleness.
ments follow the settings provided in the authors' official repository. From the results, we observe that bidirectional REST improves accuracy and accelcrates training while keeping memory cost comparable. In contrast, LMC per- forms poorly because it cannot fundamentally resolve the gradient staleness issue. Overall, these findings underscore the versatility and benefits of our approach.
Table 6: Performance (%), Memory usage(MB) and Total running time(seconds) of Bidirectional REST
Forward computation frequency F. We also evaluate the performance under different frequencies on the ogbn- products dataset in Appendix D. We observe that the per- formance gradually increases with the updating frequency and higher frequencies tend to enhance convergence, vali- dating the conclusion that staleness is key factor affecting performance and our algorithm demonstrates effectiveness in addressing this issue.
Models
OGBN-ARXIV
OGBN- PROD-PRODUCTS
Acc MEMORY RUNNING TIME Acc MEMORY RUNNING TIME
LMC LMC+REST
71.4
558
66
77.5
10982
1520
72.6
584
41
80.1
11139
925
Other Studies. We present the ablation study follows in Appendices: (1) Comparison with more baselines in Ap- pendices G and O: (2) Performance and efficiency on more large scale datasets in Appendix E ; (2) Memory persistence and Embedding approximation errors of REST in Appendix H: (3) Various aggregation layers in Appendix I; (4) Further analyses with various baselines in Appendices J and K. (5) Difference between REST and other techniques in Appen- dices L,, N and Q. (6) Broad impact and generalizability analysis of REST in in Appendix P.
Bidirectional REST. While existing historical embedding methods like GAS and GraphFM consider all available neighborhood information, they fail to aggregate gradient information from these neighbors because they reside in memory and are excluded from computation graphs. One straightforward solution is to maintain an additional memory per layer to store historical gradients, similar to the forward pass in GAS. However, backward propagation encounters the same bottleneck of staleness. We can leverage the idea of REST to increase the frequency of gradient memory up- dates, thereby reducing gradient staleness bidirectionally.
5. Conclusion
In this paper, we first conduct a highly comprehensive study of existing historical embedding methods and conclude that the primary reason for their inferior performance and slow convergence originates from staleness. Instead of merely at- tempting to control staleness, we aim to address this issue at its source. Through both theoretical and empirical analyses, we identify the root cause as the disparity in the frequency of updating the memory table and model parameters. Then, we propose simple yet highly effective algorithm by de- coupling forward and backward propagations and executing them at different frequencies. Comprehensive experiments demonstrate its superior ability to resolve the staleness issue, leading to significantly improved prediction performance, faster convergence, and greater flexibility on large-scale graph datasets.
Specifically, we select a frequeney F where F S F, in- dicating that we can easily choose F out of F batches for gradient computation during the execution of line 7 in Al- gorithm 1, updating the historical gradient memory without altering model parameters. Analogous to the forward pass, we conduct backward propagation F times to refresh the gra- dient memory bank without updating any model parameters. Subsequently, we execute standard backward propagation to update the model parameters (line 10 in Algorithm I).
Because LMC is the only baseline that incorporates his- torical gradients via momentum, we include LMC as our only baseline and report its results in Table We set /=1 and use GCN as backbone for simplicity. All LMC experi-

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Impact Statement
Gasteiger, J., Bojchevski, A., and Günnemann, S. Com- bining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations, 2019. URL https:// openreview, www.ewwwww... net forum? i d= gT. 2m.mm.
Graph Neural Networks (GNNs) have become essential for leaming on graph-structured data, yet scalability remains significant challenge due memory limitations and com- putational overhead. Historical embedding methods have been widely adopted to improve scalability but suffer from substantial bias caused by stale feature history. This paper first provides the most comprehensive analysis, combining theoretical and empirical studies to uncover the root causes of staleness. To address this issue, we introduce REST, a simple yet highly effective approach that reduces feature staleness in historical embedding methods. By decoupling forward and backward propagations and dynamically adjust- ing their execution frequencies, REST effectively mitigates the impact of stale embeddings, resulting in significantly enhanced prediction accuracy and faster convergence across large-scale graph datasets.
Hamilton, W., Ying. Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Hamilton, W. L. Graph representation learning. Synthesis
Lectures on Artifical Intelligence and Machine Learning, 14(3):1-15,, 2020.
Han, X., Zhao, T., Liu, Y., Hu, X., and Shah, N. Mlpinit: Embarrassingly simple gnn training acceleration with mlp initialization. ICLR, 2023.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22118 18-22133, 2020.
References
Bai, G., Yu, Z., Chai, Z., Cheng, Y., and Zhao, L. Staleness- alleviated distributed gmn training via online dynamic- embedding prediction. arXiv preprint arXiv:2308. 13466, 2023.
Hu, W., Fey, M., Ren, H., Nakata, M., Dong. Y., and Leskovec, J. Ogb-Ise: A large-scale challenge for machine learning graphs. arXiv preprint arXiv:2103.09433 2021.
Chen, J., Zhu, J., and Song, L.. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arxiv: 10568, 2017.
Huang, K., Jiang, H., Wang, M., Xiao, G., Wipf, D., Song, X., Gan, Q., Huang, Z., Zhai, J., and Zhang, Z. Refresh: Reducing memory access from exploiting stable historical embeddings for graph neural network training. arXiv preprint arXiv:2301.07488 2023.
Chen, J., Ma, T., and Xiao, C. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 10247, 2018.
Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsich, C.-J. Cluster-gen An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference knowledge discovery & data mining, pp. 257-266, 2019.
Huang, W., Zhang, T., Rong, Y., and Huang, J. Adap- tive sampling towards fast graph representation learning, Advances in neural information processing systems, 31, 2018.
Cong, W., Forsati, R., Kandemir, M.. and Mahdavi, M. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1393-1403, 2020.
Jiang, H., Liu, R., Yan, X., Cai, Z. Wang, M.. and Wipf, D. Musegnn: Interpretable and convergent graph neural network layers scale. arXiv preprint a:X1v:2310.12457, 2023.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: 1609: 02907, 2016.
Fey, M., Lenssen, J. E., Weichert, F., and Leskovec, J. Gn- nautoscale: Scalable and expressive graph neural net- works via historical embeddings. In International Con- ference on Machine Learning, pp. 3294-3304. PMLR, 2021.
Sankar, A., Liu, Y., Yu, J., and Shah, N. Graph neural net- works for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021, pp. 2535- 2546, 2021.
Fout, A., Byrd, J., Shariat, B., and Ben-Hur, A. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
Shi, 2., Liang, X., and Wang, J. Lme: Fast training of gnns via subgraph sampling with provable convergence. arXiv preprint arXiv:2302.0090 2023.
10

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Tang, X., Liu, Y., Shah, N., Shi, X., Mitra, P., and Wang. S. Knowing your fate: Friendship, action and temporal planations for user engagement prediction social apps. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 2269-2279, 2020.
Zou, D., Hu, Z., Wang, Y., Jiang, S., Sun, Y., and Gu, Q Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in neural information processing systems, 32, 2019.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint 1710v
2017.
Wang, L., Zhang, S., Zeng, H., Wu, H., Hua, Z., Has- sani. K., Malevich, A., Long, B., and Ji, S. Staleness- based subgraph sampling for large-scale GNNs training, 2024. URL htttt:/:///openeeee htpppppeeeeee..coc maee/fooum. id=H7zigHsa20.
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861- 6871. PMLR, 2019.
Wu, S., Sun, F., Zhang, W., Xie, X., and Cui, B. Graph neural networks recommender systems: a survey, ACM Computing Surveys, 55(5):1-37. 2022.
Xue, R., Han, H., Torkamani, M., Pei, J., and Liu, X. Lazygnn: large-scale graph neural networks via lazy propagation. Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org. 2023a.
Xue, R., Shen, X., Yu, R., and Liu, X. Efficient large language models fine-tunin tinettunig on graphs. arXiv preprint arXiv:2312.0477 04.3377. 2023b.
Ying, R., Hc, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J. Graph convolutional neural net- works for web-scale recommender systems. In Proceed- ings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974-983, 2018.
Yu, H., Wang, L.,, Wang, B., Liu, M., Yang, T., and Ji, S. Graphfm: Improving large-scale gnn training via feature momentum. In International Conference on Machine Learning, pp. 25684-25701. PMLR, 2022.
Zeng. H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. Graphsaint: Graph sampling based in- ductive learning method. In International Conference on Learning Representationss, 2020. URL https:// http://wweettoorummooo-----e---e
Zhang, J., Xue, R., Fan, W., Xu, X., Li, Q., Pei. J., and Liu, X. Linear-time time graph neural networks for scalable recom- mendations. Proceedings of the ACM Web Conference 2024, pp. 3533-3544 2024.

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
A. Proof of Theorem 1
Theorem A.1 (Approximation Error). Consider a L-layers GNN _ (h) with Lipschitz constant o UPDATE function
with Lipschitz constant B. I ==,,... .... L. Lo has Lipschitz constant If Ve V,, [( hh'll denotes the staleness between the historical embeddings and the true embeddings from full batch aggregations, N(r) is the neighborhood set of then the approximation error of gradients is bounded by:
I - (L S
πI k=1+1
a ( 3W(() * +12,,,1 (| - (1(--)11)
A.1. Detailed Proof:
Proof. Suppose ((0) is historical embedding basse GNN with L-layers, then the whole GNN model can be defined as T,(0) = fo (()) fg z( .... f()) similarly, the full batch GNN can be defined as: h(()) f0 p(L)
fo ((L-1)
fo (1)
then:
11((2) 1( = -11(() of 30
z(L
10
fo
fo
1
(10)
(LL 1)
[11
(
F(L-1)
f0
(1)
(11)
+ M
6
a 1)
8
(2)
(
L(
f(L-1) 1)
(2)
(1)
(12)
+ j
f0
(13)
8
$ ())
7 ((--))
(
(
||+
(14)
(L-1) 1)
fo
f
(1-1)
(15)
a
11
200) o s0 (k-1
1 fo
(k)
fa
clk (k-1)
o 1 ((1)
(16)
1+++1
According to the rule of message passing, assuming update function, aggregation function and message passing function at (R) (k)
k-th layer is denoted by Pupdater Gägg and ginsp, respectively, then:
(())
(11) - f((t) o f
p(b-1) o ..... f/1011
(17)
-lsuudate
(h)
(n(R-1), gass
Jamp (Fo (1))-11)))
Jupdate
(k)
(1(
(u8e Lit (1(4-11)))
II
(18)
3 * Σ Ly (N--1) Σ L Su (1-11)
(19)
((v)
N(v)
<+)) -| (M-1) - (x-11())11))
(20)
<+)) -I| *117, 12 111
(21)
From [/ (ho S <= - -nol'11 we can get final conclusion by combining all previous steps together:
- S Σ
II a a
(10,]) | - 1010111)
(22)
1=1 k=l+1
A.2. Lipschitz Continuity Assumption:
Consider GNN with T. layers, where the embedding at layer is given by
h p (n (1-)),
(23)
12

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
with (0)) the input features. A typical layer can be expressed
((++1) UPDATE (, (G u e
(24)
Then, the following assumptions usually hold in the literature (e.g., in GAS (Fey et al., 2021)):
The aggregation function evaluated on the embeddings, AGG, a-Lipschitz:
||AGG(X) AGG(Y) - a ||X - Y|l.
(25)
where functions such as mean, sum, and max are all Lipschitz continuous.
The update function evaluated on embeddings. UPDATE, is 3-Lipschitz
[UPDATE(X) - -UPDATE(Y) || - -Y)
(26)
Furthermore, commom activation functions and loss functions with respect to the predictions are also Lipschitz continuous. When these components are composed to form the full GNN, the overall Lipschitz continuity is preserved, with the constant being a function of the individual layer constants.
B. Proof of Theorem 2
Theorem B.1. Given the upper bound of the expectation of gradients' norm in the state-of-the-art historical embeddings methods such as GAS, LMC, and REST, which is
E O ((((())) - L3 Go)
cGe
Go
(27)
N
N
N(1
vp)
where Go is the upper bound of gradient approximation error, N is the number of iterations, is chosen uniformly from [N], p (0, 1). Based on Theorem 3.1, the upper bound Ge of REST is tighter than that of existing historical embedding methods. Consequently, the convergence speed of REST surpasses that of existing works.
Proof. Suppose that function L : R R is continuously differentiable. Consider optimization algorithm with any bounded initialization and update rule in the form of
Tk+1 F* dd(x),
(28)
where 17 > 0 is the learning rate and d(rx) is the estimated gradient that can be viewed as stochastic vector depending on Ik- Let the estimation error of the gradient be
As d(xx) - VL(xx).
(29)
Suppose that (Chen al., 2017; Shi et al., 2023):
1. The optimal value L inf, L(z) is bounded;
2. The gradient of L e-Lipschitz, i.e..
Vx, E RR; [V)(v) - VL(x)12 I <llv x 212,,
(30)
3. There exists Go 0 (independent of 11) such that [1]
E E I Go. VKEN"
(31)
4. There exist N e N and p (0,1) (both independent of such that
E (x(x), Ax) S Go 122 + Paa + Mts)) VkeN"
(32)
where Go is the same constant as that in Condition 3. [1]
13

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Then by letting
7 min : 2 }
(33)
we have
2 (L(a)) - Le + Go)
cGo
Go
[+R))) <
(34)
N1/3
N2/3
N vp)
where R is chosen uniformly at random from (I....,Ny Nj.
As the gradient of L is c-Lipscciiz, we have
L(y) L(x) / VLV(22) dz L(x) + S (VL(x +ty ((y-x))) y - x) ))t.
(35)
Hence,
((y) = 1(x) + (VL()),y-)) 1) + 1 (V((x+lly=))
Mly x)) VL(x), y - x )dl
(36)
$ [(a) + (VL(x), - x) + S. VL + t(y - 2)) - VL(x)) || 11 - fy==122 dt
(37)
s [(x) + (VI(x), - x) + [/" e11ly x112 di
(38)
s L(x) + (VL(z), x) + y - 2112.
(39)
Now let Th+1 Ih 11 ((())) and A d(xx)= V((xR). Then
L(*++1) S L(xx) (VL(E))), d(zx)) + en² d((
(40)
Taking the total expectation on both sides and rearranging terms yields
[[[()e+)]] s E[[(x))] - 1/ (E(VL(A))) (((Fs) + A.) + En² B[ld(<=)11]]
(41)
2
=[(((x)] 7E((VLL(>>11 T (VL(TN) An)
+
en²
V[) + A
(42)
2
Using [[z) + Axl13 < (2))1 + 21 12 and the assumption E [[| [3]
I Gg. we obtain
[[[(+++1]] < B[L(xx)] o7 [ n (VL( sc)] n k [ + en [
(43)
$ [[[(zz)] - -1 (1- B (L)))) E n (((L((E))) An)l + en² Go.
(44)
Summing over k = 1,...,
J....,,. N, dividing by N, and rearranging imply
E E (VL(I)). Aw)
1
E [[]VL(=)) < L(x1) - E[L(EN+1) 1
en Ge
(45)
N
En)N
6
Since L = inf, L(x) is bounded and xy is bounded. L(x1)= B[L( < L(x1) - L Also note that [VVI(xx), An) & Go (7 + (1/-1)/2 + --133 by assumption. Hence,
14

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
L(21)= - L'
+ En
-[IVL(
E ((()) A&)
(46)
Nn -E7)
1-
N (1 cn)
M(x)) - -t
+ en
GB
N
11 1/2 + p / + N-118)
+
(47)
N N1 cn)
1-01 E1)
(1 (1-en) N
k=1
Since Ex=1 P p=
S
1
we then get
v-v0
1 N
Σ
B[IV
B
[(x1) - L (n(1-en)
Cg
+
Go
(Nn) + I-Vo + N2/S)..
(48)
1 1-en
N N en)
Note that
1 N R|=
[[V[())) = [x[[V[(ER)11111
N Σ
B
((]] [[
(49)
Finally choose 77 = m
1 N273 J. it follows that
N
(L(r)) - 1++ + +Go)
6 Go
Go
E
B
+
+
(50)
N
N1/3
N2/3
N (1
vp)
which completes the proof.
C. Convergence
We replicated the convergence analysis outlined in our main paper (Figure 6 and Figure 7), using VR-GCN and GAS, but with epochs as the x-axis. The results are shown in Figure 8 and 9 for GAS and Figure 10 and 11 for VR-GCN, GAS settings remained consistent with those specified in the main paper. For VR-GCN, we experimented with batch sizes of 128 and 2048 for the ogbn-arxiv dataset, and 10000 and 50000 for ogbn-products. For GAS, our findings align with those of the main paper: our algorithm not only achieves superior performance but also converges more rapidly with much less epochs. For VR-GCN, when dealing with small datasets with large batch sizes, VR-GCN exhibits comparable convergence to our approach, as staleness isn't 't a significant factor. However, as the dataset size increases or the batch size decreases, VR-GCN's 's convergence deteriorates significantly, whereas our algorithm maintains robust convergence. Furthermore, after convergence, REST-IS demonstrates greater resilience than REST in scenarios where staleness plays a significant role.
Small Batch Size
Large Batch
Small Batch Size
Large Size
0.7
0.7
0.8
0.8
(ccuracy()))
0.5
0.6
0.5
0.6
0.7
0.6
0.4
0.4
0.5
0.5
0.3
REST
0.4
REST
0.4
0.2
REST-IS
0.2
REST-IS
0.3
REST-IS
0.3
REST-IS
0.1
GAS
0.1
GAS
0.2
GAS
0.2
GAS
0.0
0.0
20
40 60
80
100
0
20
40
60
80
100
0
20
40
60
80
100
20
40
60
80
100
Epochs
Epochs
Epochs
Epochs
Figure 8: ogbn-arxiv
Figure 9: ogbn-products
D. Forward computation frequency F
We evaluate the performance under different frequencies on the ogbn grondctoducts dataset. We select the case with 5 clusters (40 clusters in total) for APPNP and report the performance in Figure 12. We observe that the performance gradually increases
15

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Small Batch Size
Large Batch Size
Small Batch
Large Batch Size
72
70
Accuracy
65
Accuracy (%)
68
Accuracy
70
Accuracy
60
66
REST
64
REST
65
REST
REST REST-I
62
REST-IS
REST-15
60
REST-IS
45
VR-GCN
58
VR-GCN
VR-GON
VR-GCN
0
2
4
10
2
4
6
8
10
0
2
10
Epochs
Epochs
Epochs
Epochs
Figure 10: oghn-arxiv
Figure 11: ogbn-products
with the updating frequency, validating the conclusion that staleness a key factor affecting performance and our algorithm demonstrates effectiveness in addressing this issue.
Furthermore, also present the efficiency analysis with different frequency F in Table 7, accompanied by convergence curves corresponding to different frequencies in Figure 13 and 14. As observed from the results, higher frequencies tend to enhance convergence, shown in Figure 13 (epoch as unit). However, they also entail extra computation overhead. Hence, the actual convergence time remains relatively consistent across different frequencies, as illustrated in Figure 14 (time as unit). Nevertheless, all cases exhibit significant improvements compared to GAS.
Table Memory usage (MB) and running time (seconds) with different frequency.
Dataset
Freduency
MEMORY(MB) TIME(S)
2
9295
1053
3
9295
1188
ogbn-producee
9295
1200
5
9295
1204
Updating Frequency
80.8
80.6
Accuracy(%)
80.4
80.2
80.0
79.8
2
3
4
5
6
7
8
Frequency
Figure 12: Different Frequency
E. Performance and Efficiency on Larger Datasets
In this section, we demonstrate the effectiveness larger datasets, which typically exhibit Given our limited computational resources, chose to add experiments on ogbn-papers 100M and MAG240M, which are significantly larger in scale compared to other commonly used datasets and are highly representative. Note that for MAG240M, we follow the common practice of homogenizing it (Hu et al., 2021; Jiang et al., 2023). We report the performance and efficiency Table 8.
staleness problems.
The larger size of the oghn-papers100M and MAG240M dataset exacerbates the staleness issue for GAS, leading to
16

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Different Frequency
Different Frequency
0.7
0.7
0.6
Accuracy
F=2
Accuracy(%) (%)
0.6
F=2
0.5
F=3
0.5
F=3
0.4
F=4
0.4
F=4
0.3
F=5
0.3
F=5
0.2
GAS
0.2
GAS
0
5
10
15 Epochs
20
25
30
1000
2000 Time(s)
3000
4000
5000
Figure 13: Convergence w.r.t epochs
Figure 14: Convergence w.r. time
decreased accuracy and slower convergence, anticipated. In contrast, REST demonstrates significantly improved accuracy and efficiency, along with accelerated convergence. This conclusion aligns with our main claim in the main paper that REST has strong ability to address the staleness issue.
Table 8: Memory usage (MB) and running time (seconds) on larger datasets.
Datasets
Models
Accuracy
MEMORY(MB) TIME(S)
GAS
64.9
15705
8840
ogbn-papers1000
GAS REST
67.6
16808
4100
GAS
61.2
31256
42603
MAG240M
GAS + REST
67.6
32062
25355
F. Forward batch size B for memory table update.
In addition the flexible adjustment of the updating frequency F, our algorithm offers another advantage: the batch size during the memory table updating process (line in Algorithm 1) can also be reasonably increased since it does require significant memory for backward propagation. We explore the effect of varying batch size the final performance using GCN, APPNP, and GCNII as the backbone. We also include GAS for comparison. Specifically, we illustrate three scenarios for the batch size: (1) Same: identical to the batch size used for updating the model (consistent with the setting in Table 2); (2) Half: half batch (encompassing half of all clusters); and (3) Full: full batch (encompassing all clusters (whole graph)). use frequency =1 for all cases. We show the results three cases in Figure 15.
The presented results indicate that a larger batch size used in updating the memory table has the potential further enhance performance by reducing staleness. This is because large batch size accelerates the memory table updates, which is equivalent to using higher frequency F. However, the improvement is marginal and comes with additional memory costs. Consequently, we opt to maintain the same batch size to keep the memory efficiency of our proposed algorithm.
G. More Recent Baselines
Several historical embedding methods have been proposed recently, including LMC (Shi et al., 2023), which incorporates memory table for neighbors' gradients, and Refresh (Huang et al., 2023), which utilizes staleness scores and gradient changes as metrics to selectively update the memory table. However, as discussed in related works in Appendix M. these methods still struggle to address the staleness issue at its source, and their techniques are orthogonal to ours. Therefore, to provide comprehensive analysis, we have included performance comparison between REST, Refresh, and LMC in Table 9. We employ GCN as the GNN backbone model and include the GAS case in the table for convenience. From the results, we observe that REST can be easily combined with existing works and significantly outperforms them. For example, achieves a 2.6% increase over LMC on the agbn-products dataset.
17

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
GCN
APPNP
GCNII
72
72.5
73.0
Accuracy
71
Accuraoy
72.0
72.5
70
Same
Half
71.5
71.0
Same
Half
A
72.0
71.5
Same
Half
69
Full
70.5
Full
71.0
Full
68
GAS
70.0
69.5
GAS
70.5
70.0
GAS
5
10
15
25 30 35 40 Batch Size
20
6
10
16
20
8
12
18
Batch
Batch Size
Figure 15: The impact of batch size (a) GCN, (b) APPNP, and GCNII
Table 9: Performance Comparison ogbn-arxiv and egbn-productt
Models
OGBN-ARXIV OGBN-PRODUCE
Refresh
70.5
78.3
GAS
71.7
76.7
GAS+REST
72.2
79.6
LMC
71.4
77.5
LMC+REST
72.6
80.1
H. Memory persistence and embedding approximation errors of REST
We present two additional results memory persistence and approximation error comparison, similar to those in our preliminary study, between GAS and REST+GAS on the ogbn-arxiv dataset, as follows:
(1) Memory Persistence (Figure 16): It is evident that persistence continuously decreases with the increase in updating frequency, regardless of the batch size used. This directly demonstrates that staleness is reduced by REST.
(2) Approximation Error (Figure 17): The decrease in error value is also noticeable when compared the case where REST utilized. This provides another straightforward evidence showing the effectiveness of REST.
Approximation Error
0.8
Memory persistence
ogbn-arxiv
Memory persistence
ogbn-andiv, batch size 128
1.700
1200.0
1200.0 0
1.175
0.7
Approximation raation
1000.0 D
1000.0 0
0.6
800.0
800 0
1.225
0.5
600.0
600.0
400.0
400.0
1.050
1.075
0.4
200.0
0.025
0.3
0.0
128
512
1024
b(GAS)
Batch Sizes
Frequency
Epochs
Epochs
Figure 16: Left: GAS, Right: REST + GAS.
Figure 17: Left: GAS, Right: REST + GAS
I. Various aggregation layers
We introduce an additional experiment conducted on the ogbn-arxin dataset to evaluate the influence of the number of aggregation layers on performance. For simplicity, we opt employ the APPNP model as the GNN backbone and utilize GAS as the baseline, given its proven superiority among all baselines. We keep all other hyperparameters consistent for fair comparison and only vary the number of propagation layers. To demonstrate the enhanced capability of our approach in handling staleness, we specifically choose to use 5 clusters (out of a total of 40 clusters) for this ablation study, which corresponds to high staleness situation. From Table 10, we can readily observe that the performance of both GAS and our algorithm drops after stacking more layers. This result verifies the conclusion in Theorem 3.1: the approximation error between the historical embeddings and the full batch embeddings each layer accumulates. However, the performance of
18

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
GAS deteriorates significantly when adding more layers. In contrast, model not impacted the same extent since significantly reduce the approximation error each layer. This demonstrates another advantage of our algorithm when deeper GNNs are utilized.
Table 10: Prediction accuracy (%) with varying number of propagation layers ogbn-arxiv.
Layers
GAS
GAS+REST
GAS+REST-IS
L=l
68.2
71.9
72.0
L=3
69.4
71.8
72.3
L=5
70.1
72.5
72.5
L=8
69.4
72.4
72.4
L=10
69.4
72.4
72.3
J. More analysis on GraphFM
Approximation errors In this section, we provide more comprehensive analysis on another important baseline, GraphFM. Regarding approximation errors in Figure 18 and 19, GraphFM also experiences staleness accumulation between each layer. While it can alleviate the approximation error introduced by staleness, incurs additional approximation error by using biased one-hop neighbors for the momentum combination. This occurs because these nodes lose aggregations from their out-of-batch neighbors, exacerbating the overall approximation error.
Approximation Error
1.2
Approximation Error
0.9
1.0
0.7
0.8
0.6
0.6
0.5
0.4
0.4
12 Epochs
7
17
12 Epochs
7
10
17
Figure 18: ogbn-arxiv
Figure 19: agbn-products
Performance and frequency We provide in Table 11 for the performance of GraphFM+REST. Compared with GAS, GraphFM shows slight performance improvement by reducing staleness, but it still falls short of achieving superior performance as it doesn't fully address the staleness issue at its source, unlike REST. Conversely, be seamlessly applied to GraphFM, yielding even better performance, underscoring the generality of REST. Furthermore, the frequency analysis in Table 12 indicates that higher frequencies tend to enhance performance, consistent with our claim in the main paper.
proposed method can
K. Additional results comparing with SAGE
Convergence To better illustrate that REST outperforms not only other historical embedding methods but also classical sampling methods such as GraphSAGE, besides performance reported in Table 1, we further include Figures 20 and 21, showcasing convergence curves on ogbn-arxiv with both small and large batch sizes, utilizing time as the unit of measurement. The results indicate that our model's convergence is nearly equivalent to that of GraphSAGE. However, it's important to note that REST outperforms GraphSAGE in terms of performance and only requires a much smaller memory cost. Hence, REST demonstrates its advantage over GraphSAGE.
19

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Table II: Accuracy (%) improvement for GraphFM.
DATASET
BACKBONE
PaRTS
BATCH SIZE
FM
+REST +REST-IS
5
76.3
77.9
78.0
GCN
70
10
76.9
79.9
78.8
5
76.2
80.2
80.6
oghn-products
APPNP
10
77.1
80.3
80.6
76.6
GCNII
150
20
77.4
80.0
72.0
10
70.5
72.0
72.4
GCN
80
20
70,9
72.2
72.5
40
71.8
72.5
72.7
72.0
72.4
ogbn-arxiv
APPNP
40
10
70.5
72.2
72.4
20
71.5
72.3
72.3
5
70.6
72.7
72.8
GCNII
40
72.0
72.7
72.8
20
73.1
73.2
73.1
Table 12: Frequency analysis of REST+GraphFM ogbn gebbn-product..
Dataset
Freduency
Acc
2
80.0
3
80.1
ogbn- bobnuproducts
4
80.4
5
80.6
small batch size
large batch size
0.7
0.7
"W mmm
0.6
0.6
Accuragy (%)
Accuracy(%
0.5
0.5
0.4
REST
0.4
REST
0.3
REST-IS
0.3
REST-IS
0.2
GAS
0.2
GAS
0.1
SAGE
0.1
SAGE
0.0
0.0
40
100 120 140
100
Time(s)
Time(s)
Figure 20: Small batch size
Figure 21: Large batch size
L. Difference between REST and variation of learning rate
While there are some engineering techniques proposed to reduce feature staleness, such as adding regularization (Fey et al., 2021) or reducing the learning rate, they often suffer from many potential issues during the training process. Taking reduced learning rate as an example:
(1) Reduced convergence speed and increased training time: Lowering the learning rate slow down convergence and prolong training time significantly.
(2) Risk of getting stuck in local minima: Lower learning rates may cause the model to get trapped in local minima for extended periods, hindering overall optimization.
(3) Sensitivity to other hyperparameters: The effectiveness of reduced learning rates can depend heavily on other hyperpa-
20

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
rameter choices, such the optimizer used.
In contrast, REST does not encounter the optimization issues associated with engineering techniques like reducing the learning rate. It involves only additional forward passes without changing the optimization process. Furthermore, REST is highly versatile: it can utilize higher frequencies or larger batch sizes to refresh the memory bank more frequently, thereby reducing staleness. Additionally, it can incorporate importance sampling to prioritize the refreshment of embeddings for important nodes, such as REST-IS. It's important to note that REST can achieve these outcomes that traditional engineering techniques cannot accomplish.
To further support our stance, we provide a comparison between REST with different frequencies (F) and simply reducing the learning rate by F. The original learning rate used in our experiment is 0.001. We provide performance, efficiency and convergence curve in Table 13 and Figures 22, 23 to comprehensively support our claim. Upon examining the results, it's clear that when comparing F=2 with LR=0.0005 and F=5 with LR=0,0002, REST demonstrates superior performance and faster convergence rates compared to solely reducing the learning rate.
Table 13: Memory usage (MB) and running time (seconds) ogbn-products.
ogbn-products hy hyperparameters ACCURACY
TIME(S)
learning rate
0.0002
79.7 + 0.15
2275
Frequency
5
80.5 + 0.09
1204
learning rate
0.0005
79.7 + 0.18
1950
Frequency
2
80.2 + 0.11
1053
Different Frequency
0.8
Different Frequency
0.8
0.7
0.7
Accuracy (%6
0.6
Accuracy(% (%)
0.6
0..5
F=4
0.5
0.4
5=5
0.4
F=2
0.1
0.2
0.3
LR=0.0005
LR=0.0002
0.2
0.1
0.3
F=5
LR=0,0005
LR=0.0002
10
20
30 40 Epochs
50 60 70
1000
2000
3000 Time(s)
4000
5000
Figure 22: Convergence w.r.t epochs.
Figure 23: Convergence w.r. time.
M. Related Work
In this section, we summarize related works on the scalability of large-scals GNNs with a focus on sampling methods.
Vanilla sampling methods. Sampling methods involve dropping nodes and edges through the adoption of mini-batch training strategies, effectively reducing computation and memory requirements. In node-wise sampling, fixed number of neighbors are sampled instead of considering all of them, such as GraphSAGE (Hamilton et al., 2017), PinSAGE (Ying et al., 2018) and GraphFM-IB (Yu et al., 2022). However, these methods cannot climinate but still grapple with the neighbor explosion problem and introduce bias and variance.
Layer-wise sampling fixes the sampled neighbors per layer to avoid the neighbor explosion problem. For instance, FastGCN (Chen al., 2018) independently samples nodes in each GNN layer using importance sampling. LADIES (Zou al., 2019) onsiders the correlation between layers. ASGCN (Huang et al., 2018) further defines the sampling probability of lower layers based the upper ones. However, the layer-wise induced adjacency matrix is usually sparser than the others, contributing to its sub-optimal performance.
Different from the previous methods, subgraph sampling involves sampling subgraphs from the entire graph as mini- and then constructing a full GNN on those subgraphs. This approach can address the neighbor explosion problem, as only the nodes within the subgraph participate the computation. For example, ClusterGCN (Chiang et al., 2019) first
21

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
partitions the graph into clusters and then selects a subset of clusters construct mini-batches. GraphSaint (Zeng et al., 2020) proposes importance sampling construct mini-batches through different samplers. However, this method may introduce significant variance because the edges between subgraphs are ignored.
Historical embedding methods. Some advanced algorithms attempt to use historical embeddings as approximate embed- dings instead of true embeddings from the full batch computation. This approach can reduce memory costs by decreasing the number sampled neighbors, either per hop (Chen et al., 2017) or in terms of the number of hops (Fey et al., 2021), VR-GCN (Chen et al., 2017) first proposed this idea of restricting the number of sampled neighborhoods per hop and using historical embeddings for out-of-batch nodes to reduce variance. MVS-GCN (Cong et al., 2020) simplified this scheme into one-shot sampling scenario, where nodes no longer need to recursively explore neighborhoods in each layer. GNNAutoScale (Fey et al., 2021) further restricts the neighbors to their direct one-hop but without discarding any data, enabling it to maintain constant GPU memory consumption. GraphFM-OB (Yu et al., 2022) employs feature momentum to further improve performance.
Although these historical embedding approaches are promising because of their scalability and efficiency, they suffer from approximation errors originating from feature staleness. This issue has become bottleneck, especially for large-scale datasets, as demonstrated in our preliminary study in the main paper. Several works have proposed techniques reduce staleness. For instance, GAS (Fey et al., 2021) concludes the staleness is from the cnter-connettivity between batches and uses graph clustering to relieve it and also uses regularization prevent model parameters change too much. GraphFM-OB (Yu et al., 2022) uses feature momentum of in-batch and out-of-batch nodes for compensation. Refresh (Huang et al., 2023) alleviates the staleness issue by establishing staleness criteria. However, these approaches fail to address the fundamental issue, which is the discrepancy in updating frequency between memory tables and model parameters. Besides, their methods are complementary to ours and can be seamlessly incorporated into our algorithm.
N. Differences between REST and Gradient Accumulation
REST aims to refresh the memory bank to reduce staleness, whereas gradient accumulation simulates the effect of increasing the batch size. Hence, gradient accumulation introduces additional computation overhead. In terms of runtime, it prolongs the time since every forward pass requires gradient computation. Regarding memory usage, gradients must be stored for each forward pass until backward propagation is executed with accumulation. This accumulation of gradients across multiple forward passes can result increased memory consumption, particularly with large models or datasets. To demonstrate the efficiency contrast between REST and gradient accumulation, and superior efficiency of our design. Note that REST can also be combined with gradient accumulation since they are orthogonal techniques. We leave this as a future work.
present the following Table 14, showcasing the difference
Table 14: Memory usage (MB) and running time (seconds) on egbn-products.
MEMORY(MB) TIME/EPOCH(S)
REST Gradient Accumulation
9295
33
14537
39
O. Minor Baselines
In addition to major baselines such as GAS, GraphFM, LMC, and Refresh, there are also several minor baselines that address the issue of optimizing staleness, For example, S3 (Wang et al., 2024) uses staleness scores to guide the sampling process, and SAT (Bai et al., 2023) alleviates staleness through distributed training. We use GCN as GNN backbone. The results are shown in Table 15:
From the results, we can see that REST easily outperforms these baselines without requiring complicated design. It is important to note that their approaches are entirely orthogonal and can be combined with ours, given that our method is quite general. However, since their code is not yet available, we only report the numbers from their respective papers for comparison purposes.
22

---

Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Table 15: Performance Comparison with Minor Baselines.
Models OGBN-ARXIV OGBN-PRODUCTS
S3
72.1
77.2
SAT
72.0
78.9
REST
73.2
80.5
P. Broad Impact and Generalizability
Besides alleviating the staleness issue, REST also addresses the broader issue of staleness caused by asynchronous updates-a common challenge in many settings. To highlight our contributions, we present several additional scenarios in which REST can be applied:
Distributed Training: Asynchronous updates often arise in distributed training due to communication overhead. Nodes may operate on potentially stale global parameters from central servers, leading to parameter staleness. Applying REST in this scenario means performing extra forward passes without gradient calculation asynchronously, which refreshes local embeddings (or activation caches) more frequently. Consequently, when the node eventually computes gradients or synchronizes with the central server, the resulting update is less affected by staleness, improving overall convergence.
Federated Learning: Federated learning suffers from parameter staleness due to infrequent client-server communica- tions. REST's decoupling strategy can be applied by letting the clients (or server) perform additional forward-only steps between global synchronizations. These extra forward passes keep local representations up to date with the client's current model version, so that when the client finally computes gradients and communicates them back, the cached embeddings are no longer heavily stale. These additional asynchronous forward updates serve opportunities for refreshing beyond global synchronization. This mitigates the mismatch arising from stale parameters and promotes faster convergence in federated learning.
This broader applicability indicates REST is not merely method specific to historical embeddings, but generally beneficial framework for addressing asynchronous update issues widely prevalent in machine learning training.
Q. Difference from Related Works
As emphasized in the main text, GAS and related methods are specialized, scalable historical-embeedinn techniques: they apply a fixed training optimization improve the scalability of GNN backbones (e.g., GCN) and reduce bias from traditional sampling methods. In contrast, REST is novel, general training framework that effectively alleviates the most notable staleness issue at its root in all such approaches, offering fundamentally new training optimization strategy to eliminate the staleness introduced by GAS and similar approaches-thereby significantly boosting performance and accelerating convergence. In GAS, the memory table updates only the embeddings of nodes that appear in the current batch. As result, most node embeddings remain stale because GAS and similar approaches inevitably suffer from a frequency mismatch between cache updates and model parameter updates, leading to persistent staleness. Our work addresses this root cause by proposing general training framework that ensures more frequent-and more flexible-refreshing of historical embeddings to eliminate staleness without changing the model architecture, aggregator, or sampling algorithm, rather than merely designing model that differs from GAS. Meanwhile, it can be scamlessly integrated with any historical embedding method.
R. Hyperparameters Searching Space
Our model's hyperparameters are tuned from the following search space: (I) learning rate: (0.01, 0,000,0.100055 0.005): (2) weight decay: {0, 5e 4, 5e 5): (3) dropout: {0.1, 0.3, 0.5, 0.7, 0.8); (4) propagation layers L E 3, 4); (5) MLP layers: (3. 4): (6) MI.P hidden units: (128, 256,512).
23


Reviews:
[{"review_id": "IASimPSrSK", "reviewer": "Reviewer_uPqW", "summary": "In this paper, the author proposes an algorithm to mitigate the issue of feature staleness.\n\n\n## update after rebuttal\nI would thank the author for the rebuttal, and my score remains the same.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**A1** Memory Efficiency:\n\nFirst, we highlight that REST consistently demonstrate significant advantages over GraphSAGE in terms of memory efficiency across all datasets as shown in Table 4 and 5.\n\nWhen comparing REST with GAS and VR-GCN, REST maintains a similar memory cost. This is because our work aims to introduce a novel, general training framework that can be applied to any historical embedding model to address the serious staleness issue by adjusting the execution frequency of forward propagation, rather than altering the model architecture, thereby naturally preserving the memory efficiency of the chosen baselines. This design choice makes our approach compatible with any historical embedding methods.\n\nWe want to emphasis that baseline methods come with more notable drawbacks— deteriorate performance and slow convergence—than memory efficiency. Therefore, our work focuses on resolving these critical issues to benefit all existing methods and provide a promising solution for future research, rather than further reducing memory cost.\n\n**A2** Computational Complexity:\n\nWe would like to emphasize that REST still demonstrates significant computational advantages over the baselines. In terms of time complexity, our model consistently achieves much faster convergence and requires considerably less running time compared with SOTA historical embedding baselines such as GAS (Table 4, 12; Figure 5, 6, 10, 11), VR-GCN (Table 5; Figure 12, 13), LMC (Table 7). It maintains a comparable running time to GraphSAGE while achieving superior performance. Regarding memory complexity, please refer to the previous answer. Overall, since related works are more severely impacted by staleness  than by memory cost, our work focuses on addressing critical staleness problems in these methods. REST aims to enhance performance and accelerate convergence while preserving the high scalability that these methods have achieved.\n\n**A3** Applicability of REST:\n\nWe would like to clarify that the memory table being updated at a different frequency from the model is a key advantage of our method rather than a limitation. Based on our finding that frequency mismatch is the root cause of staleness, our model is designed to decouple the forward and backward operations, enabling the memory table to be refreshed at a flexible frequency that existing works cannot achieve. In other words, REST actively assigns different update frequencies, thereby alleviating the staleness. If we set the frequency $f$ to 0, it degenerates into the conventional training mode. Thus, our approach is actually an general form of the existing methods rather than an imposed restriction.\n\nIn summary, REST is not limited to any specific case; rather, it represents a novel strategy that enables flexible adjustment of the forward and backward operations to address the root cause of staleness. Moreover, it is adaptable to existing training frameworks and broader techniques, making it both highly valuable and widely applicable.\n\n**A4** Broad Impact and asynchronous scenario:\n\nREST addresses the general issue of staleness arising from asynchronous updates—a common challenge in various scenarios, not just limit to the historical embeddings, even though our focus is on large-scale GNN training in this work. We provide several other common scenarios in which REST can be applied:\n\n(1) Distributed Training:\nAsynchronous updates often arise in distributed training due to communication overhead. Nodes may operate on potentially stale global parameters from central servers, leading to parameter staleness. Applying REST in this scenario means performing extra forward passes without gradient calculation asynchronously, which refreshes local embeddings (or activation caches) more frequently. Consequently, when the node eventually computes gradients or synchronizes with the central server, the resulting update is less affected by staleness, improving overall convergence.\n\n(2) Federated Learning:\nFederated learning suffers from parameter staleness due to infrequent client–server communications. REST’s decoupling strategy can be applied by letting the clients (or server) perform additional forward-only steps between global synchronizations. These extra forward passes keep local representations up to date with the client’s current model version, so that when the client finally computes gradients and communicates them back, the cached embeddings are no longer heavily stale. These additional asynchronous forward updates serve as opportunities for refreshing beyond global synchronization. This mitigates the mismatch arising from stale parameters and promotes faster convergence in federated learning.\n\nThis broader applicability indicates REST is not merely a method specific to historical embeddings, but a generally beneficial framework for addressing asynchronous update issues widely prevalent in machine learning training. We believe that this idea can offer new insights for various scenarios.", "claims_and_evidence": "The claims appear to be valid.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The given theory looks solid.", "experimental_designs_or_analyses": "The overall experimental design seems reasonable. The author compares various baselines across datasets of different scales. The results suggest that for large-scale datasets, the proposed method achieves better performance while maintaining a better convergence speed. \n\nHowever, in terms of memory efficiency, Table 4 and Table 5 suggest that REST and REST-IS do not show a significant advantage. It would be helpful if the author provided a more in-depth analysis of this aspect, discussing potential trade-offs and explaining why the proposed method does not yield substantial improvements in memory efficiency.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well-organized and easy to follow. \n\nThe proposed method is simple and can be applied to existing GNNs.\n\nThe main concern is that the experimental results do not demonstrate significant improvements in terms of computational complexity. Additionally, the applicability of the proposed method seems restricted to scenarios where the memory table updates at a different frequency than the model.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. In the experiment session, Table 4 and Table 5 suggest that REST and REST-IS do not show a significant advantage. It would be helpful if the author provided a more in-depth analysis of this aspect, discussing potential trade-offs and explaining why the proposed method does not yield substantial improvements in memory efficiency.\n\n2. Do you think the difference in update frequencies is a general issue, or is it specific to historical embeddings? Could your method be extended to other scenarios involving asynchronous updates?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YX9IaClEz0", "reviewer": "Reviewer_mAEj", "summary": "The paper studies the problem of scaling the use of graph neural \nnetworks to large graphs. Existing techniques make use of the \nhistorical features, which may become outdated. On the contrary,\nthe paper introduces REST algorithm, which contains the \ninfluence of the outdated features. Also, the new model \ncan merge with current pipelines and advance their \nperformance and the machine learning algorithm's convergence.\n\n## Update after rebuttal: I thank the authors for their response about the F1 metric. After the extensive answers to the other reviews of the paper, I am acknowledging the deeper expertise of the other reviewers and basing my opinion on their comments.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your insightful comments and thoughtful questions.\n\n**A1** Other Metrics of performance:\n\nWe choose to use accuracy as the metric in our submission since all other baselines use it, ensuring a fair comparison. Since the major task is a multi-class classification problem, we follow your suggestion and further include micro and macro F1 scores as additional metrics to better highlight the advantages of REST/REST-IS. Due to the limited time available for the rebuttal, we currently report the performance of state-of-the-art baselines, GAS and GraphFM on ogbn-arxiv and ogbn-products. We use GCN as our GNN backbone for all methods including REST. We will include similar results for other baselines on other large-scale datasets in our revision of the main text.\n\nFrom the results in the following table, we observe that REST outperforms state-of-the-art baselines across various evaluation metrics on all datasets, demonstrating superior performance in large-scale training. This is consistent with the conclusions in our main submission. Moreover, while historical embedding methods still suffer from the staleness problem—resulting in significant performance drops on large-scale datasets such as ogbn-products—REST addresses the problem at its source, delivering significant performance enhancements that further validate our main text's findings.\n\n| Models   | ogbn-arxiv Micro-F1 | ogbn-arxiv Macro-F1 | ogbn-products Micro-F1 | ogbn-products Macro-F1 |\n|----------|---------------------|---------------------|------------------------|------------------------|\n| Sage     | 71.5 ± 0.2          | 52.1 ± 0.1          | 78.7 ± 0.1             | 37.0 ± 0.1             |\n| GAS      | 71.7 ± 0.2          | 52.5 ± 0.1          | 76.7 ± 0.2             | 35.3 ± 0.1             |\n| GraphFM  | 71.8 ± 0.2          | 52.6 ± 0.2          | 76.8 ± 0.2             | 35.5 ± 0.1             |\n| REST     | 72.2 ± 0.2          | 53.3 ± 0.1          | **79.6 ± 0.1**             | **39.1 ± 0.1**             |\n| REST-IS     | **72.3 ± 0.1**          | **53.4 ± 0.1**         | 78.6 ± 0.1             | 38.6 ± 0.1             |\n\nWe appreciate your feedback and have worked diligently to address all your concerns. If you have any further questions, please let us know, and we kindly request that you consider adjusting the scores in light of our revisions.", "claims_and_evidence": "The paper is clear to read and carefully written for ideas and their materialization to `REST Technique'.", "methods_and_evaluation_criteria": "In the comparisons' two tables, the authors report the accuracy of the Graph Classification task. How about the other metrics, e.g. AUC ROC, Mean squared error, Pr/Recall, Pr/Recall AUC, F1 with 0.5 as threshold (or with varying thresholds)?", "theoretical_claims": "The paper suggests the solution of containing the \noutdated features \nby decoupling the forward and backward propagation\nof the neural network weight updates and \ndynamically adjusts their execution frequencies, \npermitting the\nmemory table to be renewed faster than than the model\nparameters.", "experimental_designs_or_analyses": "The authors employ extensive experiments of their \nsolution (`REST') with 5 datasets\nand list the performing accuracy metric in them; it is \nhigher than that of the existing techniques (VR-GCN,\nMVS-GCN, GCN, APPNP, GCNII).", "relation_to_broader_scientific_literature": "The suggested approach seems novel from a first overview of the GNN literature.", "essential_references_not_discussed": "After a first study, there are not any references missing.", "other_strengths_and_weaknesses": "No more comments.", "other_comments_or_suggestions": "NA.", "questions_for_authors": "No more questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jeKMDE6ZGs", "reviewer": "Reviewer_1EQa", "summary": "This paper presents a simple yet effective training approach called REST for scaling GNNs. The authors analyze the issue of embedding staleness in historical embedding methods, demonstrating that stale features negatively impact model convergence and performance. REST addresses this issue by decoupling forward and backward propagations and adjusting their execution frequencies, significantly reducing feature staleness. Experimental results indicate that REST achieves superior performance and faster convergence on several large-scale benchmark datasets.\n\n##Update after rebuttal\n\nIn the 2nd-round rebuttal, the authors provided more clearer differences between their work and existing works, and hence I changed my mind from \"weak reject\" to \"neutral\". I will respect AC or other reviewers to further discuss the outcome.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Anonymous link**: https://anonymous.4open.science/r/REST_ICML2025-0972/REST_ICML_2025_Reviewer_1EQa.pdf\n\n**A1** Proof of Theorem 3.2\n\nPlease check the detailed proof in the anonymous link . We would like to clarify that the main result in Theorem 3.2 shares foundational assumptions with previous works, which we explicitly cited in line 253. To avoid misinterpretation, we initially chose to cite the references rather than showing our proofs in submission.\n\n**A2** Difference between GAS and REST\n\nWe believe that the essential technical aspects of GAS are adequately covered in **Section 2.1**. Given the space constraints of the rebuttal, please refer to our main text, and we are happy to address any further questions you may have.\n\nDifference: **Overall, GAS and other related works are specific historical embedding methods, whereas REST is a novel, general training framework that effectively solves the most notable staleness issue in these methods, boosting performance and accelerating convergence.** In GAS, most node embeddings remain stale because these methods inherently suffer from a frequency mismatch between cache updates and model parameter updates. Our work tackles this issue by introducing a general training framework that can be integrated with any related approach, enabling more frequent refreshing of historical embeddings and thereby eliminating staleness without altering the model architecture—rather than merely designing a model that differs from GAS.\n\n**Thus, the target of our work is not the introduction of a new model, but the development of a widely applicable training framework that addresses a key limitation—staleness—in all related works. Moreover, it provides promising solutions for other tasks involving asynchronous update scenarios in machine learning.**\n\n**A3** Specific Phrases\n\nIn this work, we follow the definitions used in existing related works. Due to space constraints, we did not reiterate these definitions in our submission. However, please refer to the figure in the anonymous link for a more visual explanation. \n\n**A4** Contribution Highlight\n\nWe would like to respectfully disagree with the statement. We hope to clarify any misunderstandings regarding our objectives and highlight the significant novelty and contributions:\n\nFirst, the main focus of our work is **not** to introduce a new historical embedding model architecture, but rather to **propose a general, effective, efficient, and simple training framework that fundamentally resolves the staleness issue present in all existing  methods.** In other word, our model aims to address the critical shortcomings in GAS and other related works, rather than designing a model that differs from GAS. **The requirement of minor implementation modification precisely demonstrates our model's strength rather than its weakness.** REST exhibits strong generalizability and can significantly improve performance and accelerate convergence by eliminating staleness in historical embeddings, without requiring any changes to the underlying model.\n\nSecond, our work is the first to provide a comprehensive analysis of staleness and to reveal that a mismatch in update frequencies is its root cause—a research aspect that has not been explored before. We not only employ Theorem 1 to directly link the frequency mismatch to staleness, but also present extensive empirical results demonstrating that existing methods inevitably suffer from severe staleness issues.\n\nThird, REST introduces a previously unexplored method: decoupling forward and backward prop so that the memory table can refresh at a frequency different than the parameter updates. **To the best of our knowledge, this core innovation does not appear in GAS or any other existing method. Rather than merely being a modification, our approach can be viewed as a more general form of GAS.** Our experiments demonstrate substantial performance improvements as well as significantly faster convergence. These empirical results not only validate our theoretical claims but also highlight practical advantages that GAS does not achieve. Moreover, this idea can be applied to any staleness issue arising from asynchronous updates—a common challenge in various machine learning tasks—providing promising solutions for future work that hold significant value for the entire community. Furthermore, we introduce a novel variant, REST-IS, which employs a unique importance sampling strategy to further mitigate staleness, showcasing additional methodological innovation.\n\nFourth, Theorem1 in our paper diverges from GAS. We also introduce Theorem 3.2, which substantiates the empirical observation that REST achieves faster convergence. This rigorous theoretical contribution clearly differentiates our work from GAS. Please refer to the anonymous link for proof.\n\nWe believe our work offers a more substantial advancement and provides promising solutions for future research, rather than merely proposing a specific model design.", "claims_and_evidence": "The proof of Theorem 3.2 is missing. Hence the claim “REST achieves a faster convergence rate theoretically” is not convincing.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proof of Theorem 3.2 is missing. Although there are some references proving the upper bound of the expectation of gradients’ norm, its complex form seems not trivial to prove. A more detailed or self-contained proof should be provided.", "experimental_designs_or_analyses": "Yes. The experiments are designed scientifically and the results can support the claim.", "relation_to_broader_scientific_literature": "Starting from the scalable issues in GNN, this paper builds its contribution on the drawbacks of other GNN methods which utilize the historical embeddings. It also highlights its novelty in directly addressing the embedding staleness issue at its root by decoupling forward and backward propagations.", "essential_references_not_discussed": "The related works are discussed in the appendix. However, the most related works such as GAS are not discussed in detail in the main context. Consequently, the differences between the proposed work and previous works are not well explained and compared.", "other_strengths_and_weaknesses": "Strengths:\n1.\tThe experiments are well set, and the results seem promising with respect to accuracy.\n2.\tThe issues in the scalable GNN are well-targeted. In other words, the motivation of this paper is built properly.\nWeakness:\n1.\tThis paper should add more explanation to some specific phrases. For example, this paper can provide the definition for the words such as “in-batch” and “out-batch”. The lack of explanation will make this paper hard to follow.\n2.\tThe novelty of this paper is not properly highlighted. It seems that this paper incorporates many insights from the paper of GAS (Fey et al., 2021), including the reference of Theorem 3.1. From my point of view, this paper only modifies a minor implementation detail of GAS and has not proposed enough theoretical contribution. In order to highlight the main contribution, this paper should provide a detailed introduction of strongly related works and compare them theoretically.\n3.\tThe detailed proof of theorem 3.2 is missing.", "other_comments_or_suggestions": "None", "questions_for_authors": "Please see the weakness part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0WAt2PSXYq", "reviewer": "Reviewer_y9S9", "summary": "This paper proposes a simple yet highly effective training algorithm (REST) to effectively reduce feature staleness. The proposed REST significantly improves performance and convergence across varying batch sizes, especially when staleness is predominant. Experiments demonstrate that REST achieves a 2.7% and 3.6% performance enhancement on the ogbn-papers100M and ogbn-products dataset.\n\n\n## update after rebuttal\n\n\nI thank the authors for the authors' rebuttal. I would like to keep my original evaluations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Anonymous link: https://anonymous.4open.science/r/REST_ICML2025-0972/REST_ICML_2025_Reviewer_y9S9.pdf**\n\n**A1** Counterexample of Theorem 3.1\n\nWe sincerely appreciate the reviewer's careful and thoughtful comments, and we are happy to clarify this counterexample.\n\nBased on our understanding of the review, a special graph was constructed with only two nodes ($v_1, v_2$), where each induced subgraph contains exactly one node. Under this extreme scenario, each subgraph includes only the node itself. The reviewer further assumes that the historical embeddings exactly match the true embeddings, which leads to the gradient becoming zero under these special conditions:\n\n$\\nabla_{\\hat{h}_2^{(1)}}\\hat{h}_1^{(2)}= 0$\n\nIn the full batch training scenario, due to the existence of actual message passing, we have:\n\n$\\nabla_{h_2^{(1)}} h_1^{(2)} \\neq 0$\n\nThus, the statement argues that the assumption of Lipschitz continuity may not hold. \n\nHowever, we would like to clearly point out that this scenario does **not** align with the historical embedding or neighbor aggregation logic used in our method (and in the broader family of historical embedding methods):\n\nFirstly, we want to clarify the definition of \"out-of-batch\" nodes commonly used in all historical embedding methods. Existing methods typically first sample a mini-batch (or subgraph) of nodes termed \"in-batch\" nodes, whose embeddings are updated every iteration. Then, they select all direct one-hop neighbors of these \"in-batch\" nodes as \"direct one-hop out-of-batch\" nodes (simply referred to as \"out-of-batch\" nodes in existing literature) and use their historical embeddings to approximate the true embeddings during aggregations to reduce computation bias. All other nodes that are not directly connected to the batch are simply discarded and referred to as \"other out-of-batch nodes.\" Therefore, since the message passing is given by\n$h_1^{(2)} = W_2 h_2^{(1)} = W_2 \\sigma(W_1 h_1^{(0)})$, this indicates that there is an edge between $v_1$ and $v_2$.\nif we consider $v_1$ as an in-batch node, then $v_2$ should exactly be treated as a \"direct one-hop out-of-batch node\" whose historical embedding is used in aggregation—even though they are not in the same subgraph—rather than simply discarding it as an \"other out-of-batch node.\" We also provide a figure in the anonymous link that better explains the definition.\n\n\nSpecifically, in most historical embedding methods, the absence of node $v_2$ explicitly from the subgraph does **not** imply the complete loss of its influence on node $v_1$. Instead, historical embedding methods utilize historical embeddings $\\hat{h}_2^{(1)}$ to preserve neighbor information, and gradients in the backward pass will still propagate through these stored embeddings. For \"out-of-batch\" nodes, their previously stored activation values are retrieved from memory to ensure their influence can still be incorporated. A typical form can be represented as:\n\n$h_i^{(l)} = \\text{Agg}\\left(\\\\\\{h_j^{(l-1)}\\mid j \\in \\text{in-batch}\\\\\\} \\cup \\\\\\{\\hat{h}_k^{(l-1)}\\mid k \\in \\text{out-of-batch}\\\\\\}\\right)$\n\nThus, the update of $v_1$'s embeddings still references $\\hat{h}_2^{(1)}$, even if $v_2$ is not explicitly included in the sampled mini-batch/subgraph. Consequently, node $v_1$ will indeed incorporate $\\hat{h}_2^{(1)}$, preserving \n\n$\\nabla_{\\hat{h}_2^{(1)}}(\\hat{h}_1^{(2)})\\neq 0$, \n\nand $\\nabla_{W_1}L$ does **not** simply vanish but instead includes the gradient contributions from $\\hat{h}_2^{(1)}$. Thus, the proposed counterexample does not hold under historical embedding methods.\n\nMoreover, **the Lipschitz continuity assumption regarding the gradients is a general and widely accepted assumption in the literature, such as in LMC[1].** It has consistently proven valid empirically across a wide range of realistic datasets and practical training scenarios.\n\n**A2** The standard deviation in Table 1.\n\nWe conducted multiple runs and included the standard deviation in Table 1. Please see the updated table in the anonymous link.\n\nWe appreciate your feedback and have worked diligently to address all your concerns. If you have any further questions, please let us know, and we kindly request that you consider adjusting the scores in light of our revisions.\n\n[1] LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence", "claims_and_evidence": "Theorem 3.1 gives the approximation errors by Equation (5). However, Equation (5) may not hold, as the assumption of Lipschitz continuity about  $\\nabla_{\\theta} L$ is not reasonable. Consider a two-layer GCN message passing on a graph $(\\\\{v\\_1,v\\_2\\\\}, \\\\{ (v_1,v_2) \\\\})$. The message passing is $h\\_1^{(2)}=W\\_2h\\_2^{(1)}=W\\_2\\sigma(W\\_1h\\_1^{(0)})$. We construct two subgraphs $S\\_1,S\\_2$ induced by $\\{v\\_1\\}$ and $\\{v\\_2\\}$ respectively. Suppose that the historical embeddings are equal to true embeddings, i.e., ${\\hat{h}}\\_i^{(j)}=h\\_i^{(j)}$. The gradients with the historical embeddings are $\\nabla_{W\\_1}L({\\hat{h}}\\_1^{(2)})=\\nabla_{W\\_1}{\\hat{h}}\\_2^{(1)} \\nabla_{{\\hat{h}}\\_2^{(1)}}{\\hat{h}}\\_1^{(2)} \\nabla_{\\hat{h}\\_1^{(2)}}L({\\hat{h}}\\_1^{(2)})=\\nabla_{W\\_1}{\\hat{h}}\\_2^{(1)} \\cdot 0 \\cdot \\nabla_{\\hat{h}\\_1^{(2)}}L({\\hat{h}}\\_1^{(2)})=0$, while the gradients of the  true embeddings $\\nabla_{{h}\\_2^{(1)}}{h}\\_1^{(2)} \\neq 0 $.", "methods_and_evaluation_criteria": "The authors propose REST to reduce feature staleness, which is useful to accelerate convergence.", "theoretical_claims": "1. Equation (5) may not hold, as the assumption of Lipschitz continuity about  $\\nabla_{\\theta} L$ is not reasonable. Consider a two-layer GCN message passing on a graph $(\\\\{v\\_1,v\\_2\\\\}, \\\\{ (v_1,v_2) \\\\})$. The message passing is $h\\_1^{(2)}=W\\_2h\\_2^{(1)}=W\\_2\\sigma(W\\_1h\\_1^{(0)})$. We construct two subgraphs $S\\_1,S\\_2$ induced by $\\{v\\_1\\}$ and $\\{v\\_2\\}$ respectively. Suppose that the historical embeddings are equal to true embeddings, i.e., ${\\hat{h}}\\_i^{(j)}=h\\_i^{(j)}$. The gradients with the historical embeddings are $\\nabla_{W\\_1}L({\\hat{h}}\\_1^{(2)})=\\nabla_{W\\_1}{\\hat{h}}\\_2^{(1)} \\nabla_{{\\hat{h}}\\_2^{(1)}}{\\hat{h}}\\_1^{(2)} \\nabla_{\\hat{h}\\_1^{(2)}}L({\\hat{h}}\\_1^{(2)})=\\nabla_{W\\_1}{\\hat{h}}\\_2^{(1)} \\cdot 0 \\cdot \\nabla_{\\hat{h}\\_1^{(2)}}L({\\hat{h}}\\_1^{(2)})=0$, while the gradients of the  true embeddings $\\nabla_{{h}\\_2^{(1)}}{h}\\_1^{(2)} \\neq 0 $.", "experimental_designs_or_analyses": "The authors may want to report the standard deviation in Table 1.", "relation_to_broader_scientific_literature": "The related work mainly focuses on graphs with less than three million nodes (e.g., ogbn-products) [Ref1][Ref2], while the proposed REST can scale to ogbn-papers100M and MAG240M, which contain at least one hundred million nodes.\n\n\n\n[Ref1] Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. ICML 2021.\n\n\n[Ref2] Lmc: Fast training of gnns via subgraph sampling with provable convergence. ICLR 2023.", "essential_references_not_discussed": "The cited references are sufficient.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The proposed REST is simple yet highly effective.\n2. Experiments demonstrate strong scalability of REST to large-scale datasets, such as ogbn-papers100M, ogbn-products, and MAG240M.\n\n\n\nWeaknesses:\n\n1. Equation (5) may not hold, as the assumption of Lipschitz continuity about  $\\nabla_{\\theta} L$ is not reasonable. Consider a two-layer GCN message passing on a graph $(\\\\{v\\_1,v\\_2\\\\}, \\\\{ (v_1,v_2) \\\\})$. The message passing is $h\\_1^{(2)}=W\\_2h\\_2^{(1)}=W\\_2\\sigma(W\\_1h\\_1^{(0)})$. We construct two subgraphs $S\\_1,S\\_2$ induced by $\\{v\\_1\\}$ and $\\{v\\_2\\}$ respectively. Suppose that the historical embeddings are equal to true embeddings, i.e., ${\\hat{h}}\\_i^{(j)}=h\\_i^{(j)}$. The gradients with the historical embeddings are $\\nabla_{W\\_1}L({\\hat{h}}\\_1^{(2)})=\\nabla_{W\\_1}{\\hat{h}}\\_2^{(1)} \\nabla_{{\\hat{h}}\\_2^{(1)}}{\\hat{h}}\\_1^{(2)} \\nabla_{\\hat{h}\\_1^{(2)}}L({\\hat{h}}\\_1^{(2)})=\\nabla_{W\\_1}{\\hat{h}}\\_2^{(1)} \\cdot 0 \\cdot \\nabla_{\\hat{h}\\_1^{(2)}}L({\\hat{h}}\\_1^{(2)})=0$, while the gradients of the  true embeddings $\\nabla_{{h}\\_2^{(1)}}{h}\\_1^{(2)} \\neq 0 $.\n2. The authors may want to report the standard deviation in Table 1.", "other_comments_or_suggestions": "See Weaknesses.", "questions_for_authors": "See Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work aims to reduce feature staleness in GNNs. Staleness occurs when, to scale GNNs, "historical" features are used for some neighboring nodes during the aggregation. After some empirical explorations, the paper proposes different frequencies for forward and backward propagation, and evaluates them empirically.
During the rebuttal and discussion, the relation to prior work was an issue that was discussed. While the relation to GAS was resolved, overall, the reviewers judged the novelty of the work as not too high, which made this a borderline paper. However, what swayed the opinion towards positive was the empirical evaluation with large-scale experiments, which also show the effectiveness of the proposed method in achieving higher accuracy and better convergence.

One main issue that remains is the assumption of the theorems that the gradients are Lipschitz. Why does this hold? Why is the gradient for the true feature and that for the approximation even the same object/function? This must be explained or the theorems toned down as a contribution accordingly, with the assumption discussed.

There are still some modifications that the authors need to make:

(1) The proofs of all theorems must be in the paper to make it self-contained, it is not enough to cite prior work unless that work has proven the exact same result. This also includes specifying and discussing all assumptions (there was no consensus yet on the Lipschitz continuity, and when it may or may not hold; this should be discussed in light of the algorithm).

(2) Some reviewers could not follow all terminology or apparently misunderstood something. The writing should be accessible by the general ICML audience.
I feel Section 2 could also gain in clarity, e.g. the discussion about convergence analysis. It would also be clearer, in addition to the provided plots, to directly check the correlation of memory consistence with accuracy/convergence, instead of going indirectly via batch size.
Decision: Accept (poster)