SpSC: A Fast and Provable Algorithm for Sampling-Based GNN Training
Authors: Shihui Song
Peng Jiang
Venue: ICLR 2022 Submitted (2022)

Abstract: Neighbor sampling is a commonly used technique for training Graph Neural Networks (GNNs) on large graphs. Previous work has shown that sampling-based GNN training can be considered as Stochastic Compositional Optimization (SCO) problems and can be better solved by SCO algorithms. However, we find that SCO algorithms are impractical for training GNNs on large graphs because they need to store the moving averages of the aggregated features of all nodes in the graph. The moving averages can easily exceed the GPU memory limit and even the CPU memory limit. In this work, we propose a variant of SCO algorithms with sparse moving averages for GNN training. By storing the moving averages in the most recent iterations, our algorithm only requires a fixed size buffer, regardless of the graph size. We show that our algorithm can achieve $O(\sqrt{1/K})$ convergence rate when the buffer size satisfies certain conditions. Our experiments validate our theoretical results and show that our algorithm outperforms the traditional Adam SGD for GNN training with a small memory overhead.

Under review as a conference paper at ICLR 2022
SPSC: A FAST AND PROVABLE ALGORITHM FOR SAMPLING-BANI GNN TRAINING
Anonymous authors
Paper under double-blind review
ABSTRACT
Neighbor sampling is commonly used technique for training Graph Neural Networks (GNNs) on large graphs. Previous work has shown that sampling- based GNN training can be considered as Stochastic Compositional Optimization (SCO) problems and can be better solved by SCO algorithms. However, we find that SCO algorithms are impractical for training GNNs on large graphs because they need to store the moving averages of the aggregated features of all nodes in the graph. The moving averages can easily exceed the GPU memory limit and even the CPU memory limit. In this work, we propose variant of SCO algorithms with sparse moving averages for GNN training. By storing the moving averages in the most recent iterations, our algorithm only requires fixed size buffer, regardless of the graph size. We show that our algorithm preserves the convergence rate of the original SCO algorithm when the buffer size satisfies certain conditions. Our experiments validate our theoretical results and show that our algorithm outperforms the traditional Adam SGD for GNN training with a small memory overhead.
INTRODUCTION
Graph Neural Networks (GNNs) have become the state-of-the-art models for machine learning tasks on graph-structured data. By recursively aggregating the features of neighboring nodes, GNNs learn an embedding of the nodes and use the embedding for downstream tasks such as node classification (Kipf & Welling 2017 Duran & Niepert 2017 or link prediction (Zhag & Chen 2017 2018).
Due to the recursive neighbor aggregation, training GNNs on large graphs is computationally challenging. To alleviate the computation burden, various neighbor sampling methods have been proposed (Hamilton et al. 2017, Ying al.] 2018 Chen et al., 2018 Zou et al., 2019 Li et al. 2018 Chiang et al.) 2019] Zeng et al. 2020). The idea is to compute an unbiased estimation of the aggregation result in each layer based on sampled subset of neighbors. These sampling techniques enable GNN training on large graphs. However, due to the composition of the aggregation functions in multiple layers, the stochastic gradient obtained with sampled neighbor aggregation is not an unbiased estimation of the true gradient, which undermines the convergence property of SGD-based training algorithms.
Previous work has shown that sampling-based GNN training is actually a Stochastic Compositional Optimization (SCO) problem (Cong et al. 2020 202T). Cong al. (202T) show that SCO algorithms can achieve faster convergence than the commonly used Adam SGD for GNN training on small graphs. Despite their good convergence property, SCO algorithms are not widely adopted for GNN training due to two reasons. First, although SCO algorithms achieve smaller training losses, the obtained GNN models usually have poor generalization the validation and test accuracy are lower than the models trained by Adam SGD. Second, SCO algorithms need to maintain the moving averages of aggregation results of all nodes in the graph. For large graphs, the moving averages may exceed the memory capacity of the GPU. While it is possible to store the moving averages in CPU memory, copying the data from CPU to GPU in each iteration is expensive, which may negate the benefits of the faster convergence of SCO algorithms.
To address the above issues, we propose a Sparse Stochastic Compositional (SpSC) gradient method in this work. Our main idea is store the moving averages for nodes sampled in the most recent

---

Under review as a conference paper at ICLR 2022
Sampled Nodes
Sampled nodes found in buller Sampled nodes
Involideted nodes
Unsampled
Unsampled
chuni-o
chunk-1
(1 (1--8 BxXx
2
chunk (k mad t)
20
chunk it 1)
1112
(a) SCGD
(b) SpSC
Figure 1: Updating the moving average of Z SCGD needs to store the moving averages for all nodes in the graph. In SpSC. we only stores the data for nodes sampled in the past iterations.
iterations instead of all nodes. As only small number of nodes are stored, our algorithm has small memory consumption even for large graphs. We provide a convergence analysis on SpSC and show that, when the number stored iterations satisfies certain constraints, SpSC can preserve the asymptotic convergence rate of the original SCO algorithm. In practice, the sparse moving averaging slightly slows down the convergence SCO algorithm, but it surprisingly overcomes its poor generalization problem and achieves higher accuracy for sampling-based GNN training. Compared with Adam SGD, our algorithm incurs a small overhead for updating the moving averages in each iteration, but the overhead can be easily justified by the faster convergence of our algorithm.
Our experiments with two GNN models on different input graphs validate our theoretical results and show that our algorithm achieves higher accuracy than Adam SGD with the same less amount of training time.
BACKGROUND AND MOTIVATION 2
To facilitate our discussion, we first give background on sampling-based GNN training and its relation stochastic compositional optimization.
2.1
GNN COMPUTATION
The computation at each layer of a GNN is conducted in two steps: aggregate and update. For each node the graph, the aggregate function gathers data from its neighboring nodes and returns the aggregation result as
Agg, (hee(vv) Re, Fne(e))
(1)
Here, hefoo] is the intermediate features u's neighbors from the previous layer, vy the input feature of v, and Fne(f] is the input features of v's neighbors. The update function uses the aggregated value to produce the intermediate features as
h = (Zo5
By stacking the intermediate features and the input features of all nodes, the computation at layer / can be written as
の - X), H U) X, (.))
(3)
Here, (1-1)) - (1(1111) (1-1) ................................ ...., (1 denotes the intermediate features of all nodes at layer 1-1, 7 N xd: is the aggregated features of all nodes at layer 1, X ..i,...,NN is the input features of all nodes, and (()) is the learnable weights. As example, Graph Convolutional Network (GCN) Kipf & Welling 2017) has Agg (1-1) X) (H where P is the normalized Laplacian matrix of the graph, and (od(Z(()x (() or (((W) where is non-linear activation function. Many other GNNs can expressed in this form with different definitions of Agg and Upd (Zhou
al. 2018)
2

---

Under review as a conference paper at ICLR 2022
2.2 SAMPLING-BASEI GNN TRAINING AS STOCHASTIC COMPOSITIONAL OPTIMIZATION
When the graph is large, the neigbhbor aggregation operation Agg incurs a large overhead, making the training of GNNs computationally challenging. Therefore, prior work has proposed to replace the Agg function with a sampled neighbor aggregation operation Agg. By sampling the neighboring nodes, an unbiased estimate of z is computed each layer, i.e.
t Agg(H
with B[Z ~ If define the computation layer of the original GNN as function f() (z(-11, w(( ..... W(TT) (Z w W(T)
(5)
= =Agg (Upd( (Upd(Z (11-)) )( w W
the computation with sampled neighbor aggregation can be written as stochastic function
f: 2 (1- 1), (1-11) ..... W(T) 12 w ((()
(
(6)
Ag (pdd( 21-1), X, ((- w Way
where & represents the sampled neighbors at layer 1. Since ~ is an unbiased estimate of z we have E = f(), and the computation of T-layer GNN can be written
F(0)= Eer+1 [STT]])
(BEr (((T)
where e = [X, [X, W( f(T+1) is the loss function, and fET corresponds to the estimated loss with mini-batch sampling. Note that we put all the learnable weights in 0 to formulate the computation as a stochastic compositional function. Our goal is to minimize F(O), which is exactly a multi-level SCO problem.
2.3 LARGE MEMORY CONSUMPTION ISSUE WITH A NAIVE IMPLEMENTATION
SCO has been well studied in the past few years, and many algorithms with guaranteed convergence
have been proposed (Zhang & Xiao 2019 Yang et al. 2019
Chen al. 2020 Yang et al. 2019
Balasubramanian et al., 22200] Chen et al., 2020 Lian et al.
2017 Wang et al. 2017b] Ghadimi
al.) 2020). It seems straightforward GNNs, However, these algorithms have large memory consumption when applied to GNN training
adopt these SCO algorithms achieve faster training of
and cannot run on GPUs for large graphs.
To see the problem, let us consider the implementation of the SCGD algorithm Yang et al. GNN training. Formally, the algorithm is written as
2019 for
(1) Mk+1
(1 - -Bx) + B..JE
(2) (0x);
(8)
yk+1 (1 3x)yk (1) + B.seel (WHH)))
(1)
251ST,
gx+1 0₂ - as V (1) (8.) 5 E2. (y
(2)
(T+1) Er+LA (sk ())
(10)
The key idea is to store auxiliary variable ( to maintain the moving average of each composite
function. Since f( returns the exact values of W ..., (TT), we only need to maintain a moving
average of (1) for each layer. The computation is shown in Figure la The moving average of the
aggregated features is stored in ())) with each row for one node. In each iteration, some nodes (rows)
sampled, and the estimated aggregation results ( are merged into (()) based Formula (8) and (9). For the nodes that are not sampled, we simply multiply the corresponding rows of 7 by
(1 3e). Since the number of rows in (I) is the number of nodes in the graph, ( takes lot of memory when the graph is large. For example, for training a 3-layer GCN on a graph with two million nodes, suppose the hidden state dimension d; 512 and floating point has 4 bytes, Y takes
3 x 2M x 512 x 4 12GB of memory. All of the existing SCO algorithms need to maintain this moving average, which impedes their application to large-scale GNN training.
3

---

Under review as a conference paper at ICLR 2022
3 SPARSE STOCHASTIC COMPOSITIONAL GRADIENT DESCENT
To reduce the memory consumption of SCO algorithms for GNN training, we propose a Sparse Stochastic Compositional (SpSC) gradient method. Instead of storing the moving averages of all nodes in the graph, we only store the moving averages of nodes that are sampled in the most recent iterations.
As shown in Figure lb we maintain a fixed size buffer of the moving averages. The buffer is divided into & chunks with each chunk for the z of one iteration. The size of each chunk is my dj where my is the maximum number of the nodes that can be sampled at layer / and di the hidden state dimension. Initially, the buffer is empty. In every iteration, we first check if the sampled nodes are in the buffer. For the nodes that are found in the buffer, we collect the corresponding rows of the buffer and add them to = based on Formula (8) and (9). For the nodes that are not found in the buffer, we
multiply the corresponding rows of ( by Bx. The updated _ is then written to chunk- (k mod t). All the other chunks are multiplied by (1 .3x)- Since the sampled nodes found in the buffer are updated to chunk-(k (I mod t), the original values in chunk-0 and chunk-1 1 are invalidated, as shown by the shadowed rows in Figure [b] As the buffer size is constant (T' t ma di) regardless of the graph size, our algorithm can be employed to train GNN on very large graphs.
Our algorithm overwrites chunk-(k mod in iteration k. The information of the overwritten nodes is lost. The update of the moving averages can be written as
k-1
2k-1
(1) (1- BBu)u
(1)
BLSELN (
II
(1 (1- B,
(11)
j=k-
where
u = P(ELA-I/(EL. U... (... (L.))
(12)
P(E,,-I/((E,. U.... is matrix with binary values representing the overwritten nodes in the current iteration & i.e. the nodes that are sampled in iteration k - t and are not sampled in the following iterations. Since we only store the moving averages of nodes that sampled in the most recent & iterations, the information of the overwritten nodes is lost. These nodes are multiplied by (1 3,) every iteration after iteration k The values the overwritten rows are I1 (1 B, 2,)) Our algorithm simply replaces Formula 8 and 9 in the SCGD algorithm with Formula .TI.
To study the convergence property of SpSC, we make the following assumptions that are commonly used in the analysis of SCO algorithms (Yang et al., 2019 Balasubramanian et al. 2020
Assumption 1. The composite functions f(h) are Li-smooth. That is, for any y and y', we have |V vIg (y')ll Tully-y/i
Assumption 2. The stochastic gradients of the composite functions f0) are bounded in expectation,
ie., E[[IV f [(v)l S CP.
Assumption 3. The estimated aggregation results obtained by sampled neighbor aggregation unbiased, i.e., 1 (v)) (y), and the stochastic gradient of f0) is unbiased, i.e.,
E (1) (v)) (V)
Following the single-timescale analysis the algorithm (Balasubramanian et al., 2020). we use large batches for estimating the composite functions and assume that the estimation variance is small.
Assumption 4. The estimated aggregation results have small bounded variance, i.e., (v)l V
This is reasonable assumption for GNN training GPUs always sample a batch of nodes for neighbor aggregation to achieve better utilization of the GPU parallelism.
In additional to the conventional assumptions, we make an assumption on the moving averages.
Assumption 5. The moving average of the aggregated features are bounded, i.e. E0(ly ( [1]] D
4

---

Under review as a conference paper at ICLR 2022
The convergence rate of our algorithm is summarized in the following theorem.
Theorem 1. Under Assumptions 1-5, if set
2(-121((T-))) and
3
the model parameters {0k} of our training algorithm with 11 for updating sparse moving averages satisfy
min
2CTTV V
201 (0--))a-1-1
2
Cmax
K K
(1+ maz))( (1- (1-3)2((-1) 3)2(1-1)
+ (1 9))
V =0(33)))) + 4Cmaz T2
0,32
Ta,3
R=
(13)
where Cmaax max
CR. CG.3......333........ ................ Cr. for 2. is the number of buffer chunks used our algorithm.
The last term on the RHS of 13) reveals how the convergence of the SCGD algorithm affected by the sparse moving averages. The larger we use (i.e., the more chunks we have in the buffer), the smaller (1 ())((111 and (1 3 Twe have, and the faster convergence we achieve. In theory, if we can make (1 - () = ((3)), the algorithm will achieve O O(vI/K) convergence rate. As + O, we need larger t to maintain the convergence rate, and eventually, we will need to store the moving average of all nodes in the graph.
Applying Sparse Moving Averages to SCSC. Our sparse moving average can also be applied to other SCO algorithms. For example, the Stochastically Corrected Stochastic Compositional gradient method (SCSC) (Chen et al., 2020) has a correction term in the update of the moving averages. Because of the correction term, SCSC needs relaxed assumption on the estimation error of the composite functions. More specifically, if we change (11 to
k-1
(1) M (1 BR)uE
(l) Sca (o
3x) B.) ( (0t )
II j=k-t+1
(1 (1- 3,)u
(14)
and replace and with (4). we can relax Assumption as Assumption 6. The estimated aggregation results have bounded variance, i.e., BlllfeRx()) (V)il) < V2
The convergence rate of SCSC with sparse moving averages is summarized as follows.
Theorem 2. Under Assumptions 1-3 and 5-6, if we choose ag JK model parameters {0k) of SCSC with for updating sparse moving averages satisfy
ça and Bk = B 0g the
/K
BIIVFF(0+)11) (B) 2(1 + () 2(t-1) 1)
Dj
a
1=1
6 2)
T C₂
+
D?
(15)
a
1=1
where C. max (4C7 + 2)) for 11..T.
The result suggests that, if we can set such that (1 (1- ) the algorithm will achieve ((/1/K) convergence rate.
=((3),
4 IMPLEMENTATION DETAILS
Algorithm [ describes implementation of Formula (11 in our algorithm. For each layer, allocate a buffer (buf) of size tm x di for the moving averages. The buffered nodes are maintained in list nose_list E tm where nodeJistfi] is the index of the node stored bif If bu [ii] is empty, node list[i] is set to -1. In every iteration k. we first get the location of chunk-(k (k mod t). Then, look up each of the sampled nodes in the buffer (line 3). The Look Up function computes
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Updating sparse moving average of aggregated features at layer / in iteration k
Input:
Sampled nodes S, Buffered nodes node. list E B buf R xd1 2 Rl5)x4
// Get the location of chunk- (k mod t)
start = (k mod 1) mm; my:
end= = chunksstrrttt
// 1ook up the sampled nodes in the buffer
idr in buf,ida idr in 2 LookUp(S, node list);
// Update the moving average for the sampled nodes
z 5xx * 7 - [idr.in=z]] (1 Bc) * fidr.in + Z
" jidr. (dd..in.]]
// Update the moving average for all buffered nodes
-1 3x) bu buf [start: end] _
11 Invalidate the old buffer for the sampled nodes nodeJisst idr (iddiinnbuf = =1;
// Add the sampled nodes to modellist
lost_list|sse end] S;
the intersection of S and Jose and returns the indices of the overlapping nodes in the two arrays. If a sampled node is not found in the buffer, we multiply the corresponding row of Z by 3x. If a sampled node in the buffer, we read in its current moving average and update the corresponding row of (1()) (line 4). For buffered nodes that are not sampled, we simply multiply their moving averages by (1- -xx) (line 5). For buffered nodes that are sampled, we invalidate their original buffer by setting mode fiiisiidrr.nnbufff bu to -1 (line 6). Last, we add the sampled nodes to the node list.
Most of the operations Algorithm Mare simple vector operations, and they incur little overhead. The performance bottleneck is the LookUp function. With naive implementation, it has O(tm; log [S)) sorted. In our implementation, we use an auxiliary array node loc E R.N to store the locations of all nodes in the buffer and accelerate the LookUp function. Specifically, if node-í is in the buffer, we store its location in buffer in node nodi_loc[i]: otherwise, noe(] is set to With the auxiliary array, the idr_in_= can be obtained by comparing nodeJoc[S] with zero, and the ida in bu_ is simply remove the overwritten nodes from node_loc by setting node lowloooo_e_iisssseoooee liststasssstart end]] to -T. Finally, we store the locations of the newly sampled nodes to node loc by setting node loc|S] to (start, start + 1, ,,.-.,,dd,, end]. It is easy to see that all these operations have O([5)) time complexity.
time complexity, assuming
|]
Before updating the node_list at line 7 Algorithm
start:
5 EVALUATION
5.1
EXPERIMENTAL SETUP
We conduct experiments on a workstation with an Nvidia RTX 3090 GPU, an Intel Xeon Gold 6226R CPU, and 512GB RAM. Our code is implemented with PyTorch 1.8.0 and PyTorch Geometric 1.7.0.
We evaluate our algorithm on five graphs as listed in Table [ The reddit and yelp graph are adopted from GraphSAINT (Zeg et al. (2020). and the arxiv, arxiv,proteins, proteins, products are from the Open Graph Benchmark (Hu et al. 2020).
We apply our algorithm two GNN models: GCN (Kipf & Welling 2017) and GraphSAGE (Hamil- ton et al. 2017). Both models have three convolutional layers. We use Formula [T] for updating the moving average instead of Formula (14). This is because Formula (14) requires two forward passes which incurs extra overheads. The algorithm is run for 50 epochs. We set 33 to 0.2 initially,
and decrease it to 0.1 at epoch 20, and further decrease it to 0.05 epoch 40. The number of buffered chunks (t) is set to 8. We adopt the layer-wise sampling method in Zou et al.] (2019) for neighbor sampling. The batch size set to 4096, and the number of sampled neighbors each layer set to 8192.
5.2 TRAINING RESULTS
Validation Accuracy. Figure 2a shows the validation accuracy of different algorithms for training GCN vrxiv. We can see that full neighbor aggregation (Adam Full) achieves the highest

---

Under review as a conference paper at ICLR 2022
Table 1: Graph datasets ('m' stands for multi-label classification).
reddi:
yelp
arxiv
proteins
products
#nodes
233K
717K
169K
132K
2.4M
#odges
11.6M
7.0M
1.2M
79M
123M
#classes
41
100
(m)
40
112 (m)
47
Saldaton Accuras
0.7.
Validation Accura.cy
2.00
0.9
0.76
0.74
0.4
0.7
0.72
0.3
0.70
0.-
0.6-
0.5
8.66
20
30
40
0.64
30
Epoch
Epech
Epach
(a) a arxiv GCN
(b) reddit GraphSAGE
(c) proteins GraphSAGE
Validation Accuracy
0.50
Validation Accuracy
0.6
Sparse_SCO SCO
0.8n
2.5
SCO
0.86
Adam Full
0.84
03-
Adam Sample
Epoch
Epoch
(d) products GCN
(c) yelp GraphSAGE
Figure 2: Validation accuracy over epochs.
accuracy. This is reasonable because full neighbor aggregation returns unbiased estimates of gra- dients. If neighbor sampling is used, the accuracy clearly drops with the same training algorithm (AmpllSa Our algorithm (Sparse_SCO SCO) is able improve the convergence of sampling- GNN training and achieves almost the same accuracy as full neighbor aggregation. The results on reddit and yelp are similar. On products graph, Adam_Full runs out of memory, so we only show the results of sampling-base based training in Figure 2d Interestingly, we find that our algorithm with neighbor sampling achieves even higher accuracy than Adam Full on prote i ns graph, as shown in Figure 2c The original SCO algorithm (which stores the moving averages for all nodes in the graph) also has lower accuracy than Sparse_SCO. This is probably due to the overfitting of models by Adam Full and SCO.
Training Loss. Figure 3 shows the training loss of different algorithms on different graphs. GPU. As expected,
able to full neighbor aggregation Adam Full achieves the smallest training loss. Adam Sample, however, has the slowest convergence. SCO achieves training loss close to Adam Full. We run our algorithm with different f's. The larger t we use, the smaller training loss we obtain. The results are consistent with our theoretical analysis and also suggesting that the poor accuracy of the original SCO algorithm probably due overfitting. For products graph, we are not able to run full neighbor aggregation. The results show a clearly faster convergence of our algorithm than Adam SGD for campling-based training.
For reddit and yelp.
Test Accuracy. Table lists the test accuracy of the models trained by different algorithms. For reddit and yelp, we follow the GraphS paper (Zng al. 2020) and report the Fi-micro score. For proteins, we follow the OGB (Hu et al. 2020) and report the ROC-AUC. We can see that our training algorithm achieves the highest test accuracy for both GCN and GraphSAGE on almost all the graphs. We do not include the results for GCN yelp graph because its accuracy apparently lower than GraphSAGE with all training algorithms, probably due to the limited expressiveness of the GCN model. While it is hard draw direct comparison with GraphS SAIT because the sampling methods and the model architectures are different, our test accuracy on reddit and yelp matches the best accuracy reported by GraphSAINT (Zeng et al. 2020 It is worth noting that our algorithm achieves higher accuracy than Adam SGD with both full neighbor aggregation and neighbor sampling on proteing ns and products graph. The numbers are higher than the accuracy
7

---

Under review as a conference paper at ICLR 2022
500
Training Loss
2.0
Adrne Spare 500 (1-10)
adan_Samuke
Traiinng Loss
Ador_Some
4.5
1.0
1.0
9:0 16
0.8
Spors,
9.4
10
10
20
30
Epoch
Epoch
Epach
(a) reddit GraphSAGE
(b) yelp GraphS AGE
(c) products GCN
Figure Training loss over epochs.
Table Test accuracy of models trained by different algorithms on different graphs ('-' means not available due to out of memory).
(a) GCN
reddit
arxiv
protei ns
productss
Adam_Fut
0.961
0.712
0.749
Adam_ Maamp_
0.957
0.663
0.726
0.790
SCO
0.945
0.698
0.744
0,773
Sparse.SCC .SCO
0.961
0.711
0.770
0,802
(b) GraphSAGE
reddit
yelp
arxiv
proteins
products
Adam Full
0.963
0.632
0.714
0.758
Adam Sample
0.956
0.631
0.685
0.718
0.787
SCO
0.913
0.628
0.644
0.717
Sparse SCO
0.966
0.651
0.713
0.779
0.801
of the same models reported in OGB Leaderboards (ogb) 202T). The results suggest that there an improvement space for the accuracy of GNN models by using better training algorithms.
Execution Time. Table 3 lists the time per epoch of different training algorithms on different graphs Although full neighbor aggregation achieves good convergence in many cases, it incurs much large computation overhead than sampled neighbor aggregation. The execution time of Adam Full is to 55x longer than that of Adam_Sample Compared with adam_Sample the SCO algorithm incurs small overhead for updating the moving average of aggregation results. Our algorithm runs slightly slower than SCO because the Look Up operation in Algorithm |ineurs extra overhead. However, the execution time is still much smaller than full neighbor aggregation.
Memory Consumption. Figure 4 shows the memory consumption of different algorithms. We collect the numbers by calling the max maa.x/emorry.alll alocatte function in PyTorch at the end the first epoch. For rxiiv v. reddi prote ns, and yelp. full neighbor aggregation takes much larger memory space than sampled aggregation, SCO and Sparse SCO require additional memory for storing the moving averages. Because only store the moving average of nodes sampled in recent iterations, Sparse_SCO SCO uses less memory than SCO. On products graph, SCO requires extremely large memory due the massive number of nodes, while our Sparse_SCC SCO can run with only 2GB of GPU memory.
RELATED WORK
To overcome the scalability limitation of GNN training, various neighbor sampling methods have been proposed, including mode-wise sampling (Hamilton et al. 2011]] Ying et al. 2018), layer-wise sampling (Chen al., 2018; Huang et al.) 2018 Zou al. (201)). and subgraph sampling (Zeng ct al. 2020; Chiang et al. 2019). These sampling-bart based training methods achieve good accuracy in practice (particularly small graphs), but they lack theoretical justification.
8

---

Under review as a conference paper at ICLR 2022
Table Time per epoch different training algorithms in seconds ('' means not available due to out of memory).
(a) GCN
reddit
arxiv
proteins
products
Adam Full
28.4
1.97
20.65
Adam_ Sample
0.53
0.28
0.55
1.01
SCO
0.72
0.37
0.67
2.31
Sparse_Ste SCO
0.82
0.51
1.24
(b) GraphSAGE
reddit
yelp
arxiv
proteins
products
Adam Full
45.29
23.07
4.10
46.16
Adam._Sampp
0.82
2.38
0.50
0.93
1.47
SCO
1.09
3.61
0.61
1.03
Sparse_SCO
1.26
2.93
0.85
1.26
1.87
25
12
2.5
10
MPUMeneryyCo Cost
1.5
15
Adam (Full)
Adon (Sample)
SC0
Adamm (Poll)
Adam (Sample)
Sparse SCD
SC0
Adlmm (Ful))
Adamn (Smple))
Sparss SCO
500
Adam (Sample)
Sparse SCO
5CD
Adam Full)
Adon (Sample)
500
Sparse SCO
Sparse
(a) arxiv GCN
(b) reddit GraphSAGE
(c) proteins
(d) products GCN
(e) yelp
GraphSAGE
GraphSAGE
Figure GPU memory consumption of different algorithms.
2021) point out that sampling- based GNN training is actually multi-level Stochastic Compositional Optimization (SCO). However, they either use this connection justify their sampling techniques and fall back to Adam SGD for training (Cong al.) 2020),
Some recent works (Cong al., 2020
they directly adopt an SCO algorithm without considering the large memory consumption issue (Cong al. 2021).
The research on SCO traces back to (Ermoliev
1976 where a two-timescale stochastic approximation scheme was proposed for two-level problems. Various SCO algorithms and convergence analyses have been proposed ever since (Wang et al.] [201 by Lian et al. 2017 Yang et al., 2019 Zhang &
Xiao 2019 Chen et al., 2020 (Balasubramanian et al. 2020 Ghadimi et al. 2020 et al. 2019] Lin et al. 2018). Despite substantial volume of work on SCO in recent years, none of the existing work has considered the large memory consumption issue and the data movement overhead of the algorithms. Our work is the first to establish convergence analysis for SCO algorithms with sparse moving averages.
7 CONCLUSION
In this work, we propose new variant of SCO algorithm for training graph neural networks on large graphs. Our main idea is to maintain sparse moving average of the aggregation results in each convolutional layer. We study the convergence property of our algorithm and show that the algorithm achieve O(v1/K) convergence rate when sufficient amount of moving averages are maintained. Our experiments with two GNN models on different graphs validate our theoretical results and show clear advantage of algorithm against Adam SGD for GNN training.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ogb leaderboards for node classification, 2021. URL https://opp.ssaanoorddddd//////d leader nodeprop/
Krishnakumar Balasubramanian, Saeed Ghadimi, and Anthony Nguyen. Stochastic multi-level composition optimization algorithms with level-independent convergence rates. arXiv preprint arXiv:2008. 10526, 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. FasIGCN; Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization nearly as easy as solving stochastic optimization. arXiv preprini arXiv:2008. 10847, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An
efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1393-1403, 2020.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the importance of sampling in learning graph convolutional networks. arXiv preprint arXiv:2103.0266 2021.
Alberto Garcia Duran and Mathias Niepert. Learning graph representations with embedding propaga- tion. In Advances in neural information processing systems, pp. 5119-5130, 2017.
Yu. Ermoliev. Methods of stochastic programming. Monographs in Optimization and OR, 1976. In Russian.
Saced Ghadimi, Andrzej Ruszezynski, and Mengdi Wang. A single timescale stochastic approxima- tion method for nested stochastic optimization. SIAM Journal on Optimization, 30(1 (0(1):960-99)) 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint 1=Xiv:2005.00687 2020.
Wenqing Hu, Chris Junchi Li, Xiangru Lian, Ji Liu, and Huizhuo Yuan. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. In Advances in Neural Information Processing Systems, pp. 6929-699999999 6937, 2019.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558 4567, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In AAAI Conference on Artificial Intelligence, 2018.
Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pp. 1159-1167, 2017.
Tianyi Lin, Chenyou Fan, and Mengdi Wang. Improved oracle complexity variance reduced methods for nonsmooth convex stochastic composition optimization. arXiv, pp. arXiv-1802, 2018.
10

---

Under review as a conference paper at ICLR 2022
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2): 419-449 2017a.
Mengdi Wang, Ji Liu, and Ethan Fang. Accelerating stochastic composition optimization. The Journal of Machine Learning Research, 18(1):3721-3743, 2017b.
Shuoguang Yang. Mengdi Wang, and Ethan X Fang. Multilevel stochastic gradient methods for nested composition optimization. SIAM Journal on Optimization, 29(11:616660) 659, 2019.
Rex Ying, Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 974 983, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Junyu Zhang and Lin Xiao. Multi-level composite stochastic optimization via nested variance reduction. arXiv preprint vrXiv:1908.11468 2019.
Muhan Zhang and Yixin Chen. Weisfeiler-lehman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 575-583, 2017.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang. Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08443 2018
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 11249-11259 2019.

---

Under review as a conference paper at ICLR 2022
8 APPENDIX
Link to our source code:
https://anonymuus 40wp:yyuuuuuuuuun..oooooo /tppseacceeeeeee//////0000000000
Artifact--Fel
8.1 PROOF TO THEOREM
Based on the discussion in Section 3 our proposed algorithm can be written as
Mk+1 (1 - -B22vu ()) + Baseen (1) (0x)
II (1 - B,)uk (2)
(16)
j=k-t+1
h-1
(1) M8+1 = (1 - 1Ba)ub + BxfELL (1) (6/41
II
(1 (1- B,) 251ST,
(17)
j --++1
0x+1= = 02 - Oo V
(18)
with
(1)
U
(1)
(19)
and
VIL ELL (0x)
V &T
(1++1 Er+i.
(T-1)) (I+1) (3)
(20)
8.1.1 SUPPORTING LEMMA
Lemma 3. The change of yk in every iteration is bounded, i.e.,
(1)
Mk+1
(1) - y/ 111199
$ 1 - 3k
82 E
(()(()))) (0x) -
(
(2) 2
B j=k-t+1 t+1
1 (1-
3,)² E
Uk
(1) 27
+
s2v2
(1=1)
(21)
and
E
Mhtt
2/22 11]
<
33 E
|1 (b(+1))
(9)
11]
k-1
(1- b,)² E
(1)
3 v2
3x
Bi j=k-t41
2)
(22)
Proof. According to 17 we have
k-1
(v - (1) =Ba (Jel)
( - 4/ (1))
II
j=k-t+1
R-1
=Bk (fe)) (((-11)) (0) 3xx
(1E)) (V
- ((0
II
(3)
2+1
(23)
Taking the square of both sides and using Assumption 4, we have
27
k-1
Mkt1
(
2/22
1]= E
Bx (f()) (DK+11)
v
II
(1 B,) u
+.822
-=--++1
32 F. |||
k-1
(
- wk++
(1)
+
(1 (1-8,)
8,) R.
11
(1)
1 - Br
j=k-t41
(24)
12

---

Under review as a conference paper at ICLR 2022
Lemma 4. The difference between the stochastic gradient and the true gradient is bounded, i.e.,
V VF
Σ
iIE'
||
f(m)
(vk+1 (vb4I1)) 1))
) [Fa]
1=2
m=1
(25)
T
ArE
y(h)
(ubt1) )
FF
where A == Em A1.-
This lemma is commonly used in the analysis of SCO algorithms Chen et al. (2020); Yang et al. (0019). Proof can be found in Chen et al. (2020), page 20-23.
Lemma 5. The difference between the composite function and its moving average satisfies
T ΣΣ
f(()
yk+1
k= 1=0 1=1
40 C K-1
E [F(
82
k=0
(1
3)21-1
Cmaz - 3)2(e-11
(1 (1- 8)2++1
+ 20 m
D2
B3
,3
T g3
8 (11-1)(1 3) +T) V2
+ 20'mx 2
BC |30mas
(26)
T
where Cmax mar(C203...
CR.C303..C....... for 1 = ..
Proof. According to
we have
(111) (1) f()
2241
1-1
-(1- 3x) Uk f()) (0(t11) + Bk (f (W(TT)) - -(() (v(
II
(1 (1-3,) 3,)
k=k-
(1 36) (1 f()) (2h 1)
) + (1- - Bxx (f(1) (1 f(3) (11-11))
h-1
+ 3h (10) ( - f(() (1
II
(1 BB) u
j=k-t+1
(1 3x)) Uk
y(() (u - + (()) (16 -1)-)) (())
Mk++1
(2-1)
==y(()
+ 3x (fele (11-1))) - f(() (2t ))))
II (1- B,) u 1 j=k-t+1
(27)
13

---

Under review as a conference paper at ICLR 2022
Taking the square of both sides of (27 and taking the expectation conditioned Fu,
Fis Wk+11"'
(2)
11 +1 J. we have:
(1-1)
Uk+1 f(0) (uRtz")) !1
(1)
E
k-1
=E E
(1 Bb) (ulk - f(h) (1 + x
II
(1
B3) xx
j=k-t+1
+ LE
[1(VEL. (wRtt)) p() (v ))
(28)
(Aesumptiond)
1 - -(()) 1/2 (
1
Y
(1 - 3x) E
+ 3x 1 3x
E
k
(1- (1-B,)² E |1 [=
+ B8V2
3 j=k-t+1
Let us define
kk1 = E [1000 p(1)
( ||
(29)
Formula 28
be rewritten as
(() S(1 -
|| |2]
[2]
+ 8k 1 1 3x
(30)
-1- - (1-8,)² E ||
(1) |1]
+ 12
B
j=k-
Because
U1 k
| (v) 1 1
E
=
E
(31)
(Assumption2)
| 2 ( 11]
CFB
when = 1.
(1)
< C?E 10 - 0h1l2]
s C?E |111 V + ax VF(O))) - ax
(32)
+ 2T T
< C2 of (2E |VF
A7s k+1 )
plugging 32
into 30).
we have
(1 8,) 11 / 11]
5 (1)
1-1 <(1 -
(
+ +8822
K
(+1
1
1
+ 3x
1 -
Br
(33)
k-1
5(1 - (() k
+
(1- P
[1
(1)
+ +2222
1+1
T
2 1
2
ClafT Σ 1
+
3k 1 - 3x
8x
1 -
3k
14

---

Under review as a conference paper at ICLR 2022
When & 0. ||ubll O, and
7
s <1 (1- - 80)5 Bo (88V2+ +
2
1 30
cggg
+
2
c
T
)
3
1
30
1=1
= (1 - B0)50 = - 8
(34)
Similarly, have
1 S (1 - -1))s + 3,1
(35)
$ $ (1 $ + 2
Here, for i > t
4
II
i-1
(1-
11]
B2
83
j=i-(-1
+
caa
E
(1.)1
(36)
1
B
+
2
Cla
T
5(1 441
82
1
B
1=1
for 0 <ist. t,
4 = -B. V2 2
+
2
C9asE [F(()))
32
3
T
(37)
+ 8 1
cta?
T
1
B
1=1
Because $6 = 0, we can recursively write:
s(1) <3,40")
(1) S(1 -1)8040 (1) + (
s( S(1 -1)((1 - 31)8.4 (1) +(1 - 32) (1) + +,22
(38)
s()) 5(1 - -8) 8.) (1--8)8--44 (1) + (1
Bx) :.) (-)---((1BB)))1))) +...
+(1 (1
12 + 8.
Σ W (1)
where W/.k = (1 3x) - 1.
For 1 > 1, 330 can be rewritten as
(() S641 < 3k) 5(
C7
11
27
k-1
(1 (1-3) 2,) E
(1) 27
+ 32V2
BE (1 3x)
u
j=k-
(Lemma 3)
S (1-Bk) (
B&C
((1-1) -.
(1 Bx)²
(39)
15

---

Under review as a conference paper at ICLR 2022
where
k-1 (1-
10 !1) 17]
Cf
k-1
1 13 1
B&C V2
B,)² E
II j=k-t+1
(1- 3,)²
+ S2V2
5
B (1
3x)
1 Bk
(40)
follows that
BaC2 s(1)
(22) 5(1 k
k+1 + 1,22(
(1 -1-33 -x
Accordingto
38
B,C3
(1 - 3x)
+ (1 Bx)² i=0
Σ
A + BzZ
(41)
C2
-(1 - 3x) + BB
Wi 1 (1) + 7(22
(1 - Bp 2
1=0
Following the same steps as 38). by recursively plugging { into S Dk+1 we can obtain
$
Σ
C2
Wi A + +2,00
Wi,k
(1
1=
Chüjk
Wi,k A
(1)
Σ
Wik 2,,
(42)
B₂) 1=0
j=U
k
C2 B
(1)
Σ
Wi wi 20
B,)²
1=0
According to 38
it easy to find Σ} Wjia < 1. Thus, we have
Chwik
< Σ Chwik $
C2
k
C2
Σ
Σ
wjik S
(43)
B3)²
(1 3,)² (1 - 312 j=i
(1 - 32) 31-
5=i
Combining 43 and 42
we have
k
C2
((2)
(1 - B.) Wi A w.i
k+1
1=0
k
C2
Wiik
(1 (1-3,13 B,)2
(1)
+ +22-0)
(44)
1=0
Wi (
(2)
Similarly, for any >> 1, we have
k Σ
5(())
S
Wi 0 A
(45)
1=0
16

---

Under review as a conference paper at ICLR 2022
where
C
4
(1)
+ +2.0)
(1 (1- (1-3,)²
C
4
(2)
+ 7
(1 8,)
(46)
C3
C
(1)
(2)
+ z
(3)
(1 3,)
(1 3,)
C2C
C ... C2
0 ... Cf
4
4,
(1)
+
-
+
+ + 2
3.) 21
(1 2( 2)
(1 3, 2(1-3)
Let Cmaz = mar
-7 C2, C2C C. ... 19,1), E [1, T7 and 2,maz defined as follows:
Omar
(1 - 3,) D² + 53, + B,Cmar V²
Z
(1- (1-3,) D² +
II
8 B.) j=i-
1 B.
(+1
(47)
Plugging (46 into 45
we obtain
k+1
Cuar
3,)
Wi A
(1)
+
Σ
k
Wi,k
(1
Cmaz
B,)
(48)
1=0
1=0
2=
Summing (48)
from 1 to T, setting Bx = B and 0g
a, then substituting A we have:
K-1
Σ
K
C man
1)2(T-1) wi A. (1)
+
Wikk
Cmar
1)2(T-1) 2,00
k= t=1
k=0
k=
i=0
1=1 1=1j=2
K K
CmazT
K- K-1
Oman T22
(1)
+
Σ
()2 -1. Zimax
-1)(T-1)
k= s=
Oman'
K-1K-1
Omaz7 T2
(1)
Σ Σ
13)(T-1) Wi Z.mar
(1)
k=
OmaxT T
K-1
Σ
8² + 2Caa²
|VF(BN)) + 207a2T T
Σ
((0)
$ (1 1)
g2 B)
83(1 -6 3) I=1
k+1
k==0
Craz TD2K
Cmaz T2K
+ B3 ())2(-1--1)
(1 11)
(49)
It follows that
ΣΣ k+1 < C - 3)
K-1 T
K-1
B2V2 + 2C7a²
5² 3) [IVF(0.>17)
3² - 3)2T - 22 22T 272
k= lml
Am
Cmaz T K(1 - -)
C Oman? T T2 -3)KZma.
+ B3 - -1 - 207C 3070maaz 12228
82 -011-3927-- 20 CCCamaa 2T2
(50)
17

---

Under review as a conference paper at ICLR 2022
If we set 8 S V2 and a I
20,T V
8
2(1 211-8)o-1-11
Cmaz
we can ensure B - -322-1
10 2 2 /2, and (50 can be simplified as
K-1 T
40max C-Ta2
K-1
9)
E
[VF((0))1
k+1
B
k= 1=1
R=
@0marTK(L - -B)2t1
D2 + 20 T ((1-3)) B)
g3
man 333 3)2 40 40 C2T
Σ E [IVF((W))1
B
20 20 TK(1 -B)2t+1
D2 + 2C T K ( (32
3Cmax V2
+
33
1 3
(51)
20man T² - 1) (1 +
Cmaa D2
B3
3
4Cmaz T K-1
32
k=0
-
3)20-1
Cmar - ())((=-1)
(1 - 1))
20 20maaz T
D2
g3
83
T33
+ 20 20mast K |8Coa + (²(1-
- B) + +T)) V2
8.1.2 REMAINING STEPS TOWARDS THEOREM
Using the smoothness of F(Ox), we have
T.
F(0++1) & F((&) + (VF(()), 06+1 - -0a)
+
|10k+1 - 0xl1
2
L
F(Ok) as (VF())).9k))) 91++1
2 ax
119++1l1 1|
+ La
= =((O) agE
VF())))
[1gh+1 212 + az (VF())), VF(O.) M6+1)
2
La
= F((k) agE
[VF())))
+ 2
|19++111 + a (VF(O.), VF(O.) V+) +az as (VF(Oe), V -k+1))
(52)
Conditioning on FR and taking expectation of both sides w.r.t. &k. we have
[ (0.+1) [Fa]
L
<F(O.)) a E
(+&))) 12]]
+ E
1
0ull FR + (VF va(FA))
2
L
<F(Ok) F [V+((0))) ]13]
+ 2
CP ...
+ a .G.
1118 VF
(Lemmaa4 4)
< F(Ot)) E (1=)(())11
|1]
+
L
ct
Ch + az Σ (A VF
1
for (ub+t)) ) Fr
<F((2) 04k 1
a
Σ
T
A?
VFF()))
+ &x Σ
T
| - ( /|
1Fg
+
c c ... ...Ga
L
4
2
1=1
(53)
18

---

Under review as a conference paper at ICLR 2022
Summing from &s = 0 K 1, we have
K-
K-1 1
K-1
T'
[[F(0s+1(FR))
Σ F(O))
Σ
02
0hk
Σ
(
4ßp 1=1
k=
k=0
k=0
(54)
K-1
8k
K-1
Σ
1
C..k.
k+1
2
0
k=0
Substitute (50)
into the above equation, we have
K
K-1
E [F(00++1FA))
S
F(Ox)=
aa(1
a
A1)
Σ
T (1
43
k=
1=1
k=
4C mon CTTa
K-1
LK Ct... O2a²
8
(1 (1- 3)20-1
Cmaa (1 -3)((-11)
(1 -1-13 11-3)22t1
+ 2C 20maz T2K
D2
$2
83 (1- (12 12
T33
Cmax +
+
T
(55)
If we set a S
we can ensure 1
Q 433
21=1 A7
40man
CPTa 3
2 } and thus,
ET= A7+16C mas C7T
K
E [[((O++1)Fe))
&
K-1
a Σ F(Ok) +
K-1
Σ
+ 2
LK
Ct
C....c ....aaa
2
k=
k=0
(1 (11-3)at B)2011
Cmar (1 -))2(1-1)
(1 (1- 1-3))2++1
+ 22maassTe
D
82
88
T32
(1 - (1 +T)
+ 20mmaz 2 K B +
V2
T
(56)
Combining with the condition for a and B in 50 if we set
B << 1
1112/(2--))
2(1 -/27-11
2
(57)
3 min
2C1T
Omaz
Σ A3 + 111 man CRT
we have
K-1
+ +LC?....O ...aa Σ E (( < 2(F((b) - F())))
Ka
(1 (1-
Cman (1 - (1)
(1 (1- (1-
+ 40
D2
ag32
0,32
To
B8
33 (1)-))(11+ (T)
+ 42
/22
aT
1 Cmaz)) (1 (1-))2((0- (3)
(1
13)20+1
<0( + 40 T2
12
a,z2
Ta332
(58)
This completes the proof of Theorem 1.If set t such that (1 (1) 0(84), the algorithm
achieves O(1/VK) convergence rate.
19

---

Under review as a conference paper at ICLR 2022
8.2 PROOF TO THEOREM
The SCSC algorithm with our sparse moving average can be written as
k
(1) M4+1 (1 -1- (1-B (
(1) JEL (0x) (1 - Bx) (0=-1)
II (1 (1- 8,)uk (1)
(59)
R-1
(1) M4+1
(1 - -b)bbk (1) + S (Wlti - (1 BB) Er, (Uk
(1-1)
II (1 B1)- 2 (60)
I jmn-t
8k+1 0x ax Vx.
(61)
with
"k
(1) -P(LLA- U... U....UELR)))).H..
(62)
and
V
(B&) (8x) VSSTT
(Uk+1 (T+1) (T)
(v++1)
(63)
8.2.1 SUPPORTING LEMMA
Lemma 6. The change of yk in every iteration is bounded, i.e.,
(1)
u/ 11
BE
p() ( ||
E
Uk+1
33
E
Uk+1
1
8k
Bx
22 + 30 1 E |1 2 1/
(64)
3R
k 1
(1 - 3,) |10599
+3 3
II
-=k-t
Proof. According (60), have
(1 [3]
(
(1) = Bk (fe. (b441 -
(1) (
k-1
+ (1 - -3x) (fel) (Ui+11)
-
- (()))
1/ 1))
II (1- B,) !
EeL
j-k-t
-Bp (1r) (vbti)) - (1)
y -y
+ 3r
[ (1-11)
(bk+1
f(1] (wktt!))
k-1
+ (1 3x)) (fel) ( (
((()) V/ (u(-1)))
II (1 - B,)u !1)
j=k-t
(65)
Taking the square of both sides of (65) gives us 664)
Lemma 7. The difference between the composite function and its moving average is bounded, i.e.
E 1 (11) (v < - 3x) E
11 - ((1)
U/ 1 (2)
+ 4 (1 Bu)² CFE || (1-1) 1 +
233r2
(66)
II
(1- B,)²
|1166 11]
3k
j=k-1
20

---

Under review as a conference paper at ICLR 2022
Proof.
(1)
-1 (1--11
Mk+1
=(1 - 3kk) U/ - y(t) U/ 1) + (1 - Bx) -Bx)
(n"((1k
Uk 1 - p(
(Mktt"))
=
+ 33 (1)) Bbb41
f(1)) (
(67)
T2
R-1
+ (1 3x) (Jele
fELL
((-11)
II
(1 - 3))
J k-
: Ta
Conditioned on Fk. taking expectation over Ei, we have:
E [1 Bx) Ti BxT2 + (1 - (z) Tz]
E' (1 3w) p()
(1) yk (1-11) f(() (Mb+i)) + 5(()) (22 -(1 -(1- -1) Sel) (11)
Taking the square of both sides of 667 and taking the expectation conditioned on Fu.n = (1) (1-1)]
Fi Vetti 3/++1 }. we have:
|0 (1)
((9) (uktt))) ||]
E
Mk+1
=E
Bx) Ukk p(() (21 1))=
(1-
B,) u
(1)
j=k-t
E
[11 Ti 3aT2 + (1- B&) T
k-1
$ (1 - 1 ||0500 1 (0% (
||
(1 [,)
[116 (11
Bx -=
2E [I(1
Ba) Ti + Tx |FFkm
+ 3 R
||77||| |F
<(1 B&)
1 p( U 1) ||²)
+ 3
[ITT] 11 |F
2,3
[ITTa 12 FF
k-1
+2 Ba) [|/T3|1 |Fkm
+ 3x カ=ルーt
(1- (1-8,)
[1 11u [12]
(1 - Bb) E
11 (0) f())
(vb 11)
|||
2 Bx)2
[|5000 ( (1--)) p(() (DITTT) ||'"]
[1 |1:00 (1(-11))
(ll (ubtt11) > 113
2 Ba)
+ 286
k-1
II
(1- 3,) |1 (2) [P]
3k j=k-t
(68)
21

---

Under review as a conference paper at ICLR 2022
$ (1--8h 101-Bp 3k) |1h grt (wk- ||
+4(1 - 3x TF 1 1111) - wict1 1
23
+
(69)
II
(1 - 3,)2 B [1166" [1]]
B j=k-t
8.2.2 REMAINING STEPS TOWARDS THEOREM 2.
Using the smoothness of F(Ox), we have
L
F(0x+1) F(0)) + (VF(O)), - 06) +
|10x+1 - 0xl1
2
L
=F(0k) ag (VF(O)), Va)
11x+1 1xl1
2
L
=((O))
|1
11
0x11 + ap (VF(O))) VA).
(70)
Conditioning on Fk and taking expectation of both sides w.r.. Ek. we have
[[ (0x++) [Fa]
L -0ll 1 + ao (VF(()) Va(FAl)
<F(Ok)) F
[0
+
L
<F((k) B
(VF I1 |1
CT
Cf....C
+ a .2+11
VF(OA)I
Lemmma
F((x)) F
[VF(()))
+
1 + CP
[ (0x) E yk4l f (u (T-1) |>
[F
2
1=1
<F((k) ak
1 1-
A
E
|F(ON)1
34
Σ
E
Mk+1
(T)
((
( 1/
FFx
23
1=1
1=1
/ c Cf
L
2
(71)
The subsequent analysis builds the following Lyapunov function:
T
V4 = F(t.) F(8.)
Σ
E y
(1)
(0)
(116-11)/11
(72)
where 0, is the optimal solution of the problem.
Conditioning Fx and taking expectation of Ve+1 w.r.t. εx, have
22

---

Under review as a conference paper at ICLR 2022
E E| SV/ - aak
1
0kk
Σ 1=1
Af
E [IV
+ 2 _ ... G7+10
Cc....GT+118
233
T
T
+ (1+ 3a)
E
uk+1 10 (uRt=") IF -
E
Uik
- )()
(1h "1"" Fr
1=1
3R T
Σ
E
(1)
p(h
(wb-11)) ||2 |F4
2 1=1
(Lomma 8) S
1/8 ax
1
0ik
Σ
T
Af
E [
+ L c ... -7
2B3
2
1=1
T
EE 1| - 1 (2ft ا 1 |Fx
+ +(1++ - Ba) 1)
Σ
1=1
+4(1+ (1
|10 0k-211 1 [Ta]
T
+
[4(1+ B1) - O2f w] E Mett1 - 4/x
1-1) [FF
1=2
k-1
T Σ 1m1
+ 2(1 + 3.) NV2
1+ 3k
II
(1
8,)
E
[P]
Bx
- Σ B
T
3k+1
v/
(-1)
|Fx
5k
T Σ
E
| - (( 11]
2 1=1
1
T
SVh ak
1
ak
Σ
Ai
VF (0x)) + L
cF... .f....c7+14 + +2(1+ + Bx)
233 1=1
2
+ 4CPB
110k
0k-1l1 [Fx]
+
T
(4F + 7)) E)
|| U/
1111) 2
FF
T
h |5 - 3x
T Σ
((0(( 12
Σ
MB || v/
E
2
1=2
1=1
+
1+ 3k
II (1
k-1
(1-
Σ
E
|11000 (0
[P]
3k
j=k-1
1=1
23

---

Under review as a conference paper at ICLR 2022
(Lemma 7)
Vk= 0.h
1
OC
Σ
Af
E
| (0w))
c
L 2
2,3k 1=1
1C
110k
0x 1 11a |FF
Bk
2 T
1utt1 - g0 (x(tt)) 22
+3
(10 + w) E
1 -
BR
1=2
://1
8k
B
yk++1
(1)
10 (ubtt)) ||]
17
:112
T
+3
(1C9 + 7() 02 E
Mk+1
(1-2)
Bk
11
1
1=2
1=/kg
T
Σ
BB
(1-)))
U/
1/z (1-1)
[Fa]
1-2
:11:
21 + Bx) B +
1 (1-
3x
T
(1C t1i V2
Bk
1=2
1+ 8k 1-1
T
k-1
T
(1- (1)
Σ
[
1 [12]
+3 II
(1- - 3,) Σ (407 + +m) E
jmk-t
1=1
j-k-et
(73)
If we define 7/t such that:
2 2
8x
(4C +7) < 8x
Σ 1=2
(74)
1 Bk
2
and
3 (1C9 + +1) Cp-1 < --
(75)
then
Ik. Ix2 <0
(76)
Ikg + Ike 0.
(77)
follows that
[V++1 [Fx] SV/= 0%k
0kk
T Σ
A3
E [VF((=))))
+ L
CR....C7.110 C7+10
2
1=1
+ (3(4C) 72) + A)C
|18g - 8x-21l 11 1|FA]]
+ 21 + 3e) 32 +
(1
Bx
2 T
(AC + m1) V2
1- 8k
1=2
+
1+ 1+
II (1- 3,)² Σ E
1-1
|1
(1) [12]
+3 II (1 B,)² Σ
1-1
T
(1C + 7)) E
2
a
||]
3x
j=k-t
j=--t
1=2
(78)
24

---

Under review as a conference paper at ICLR 2022
Setting 3x at Ei=1 1 A,, we have
E [V++|[Fr)
SV4 |1l V (0+)
-
+ (3(4C) +2) 4)0 [10-- 02-111 |Fa)
2
(1-
BR
2
+
21+ 3x) BENN +
(4C7 m) V2
8k
+
1 3k
II (1 (1-3,)
k-1
3,)² 2
T
E
(1)
+ j=k-t
A-1 1
II (1 - 3,)
Σ
T
(40p + +7) E
1
1 |2
3k
j=k-t
1=2
(79)
Setting 0 =
Co VR
and BB
and summing up both sides of (79 from 0 K 1-
VK
we have
1
2Vo
VF (0W1)
+ LC9 + 2(3(4C3 + +22 4)) C7
K
Ka
k=0
(1-
2 Σ
+
2 8) N
1 3
(40 + mi)
V2
2(1 + () (1 ((-1)
K-1 T
(1)
E
K
k= 1=1
6 - 8) (( 1)
(40P
m)) x)) E
1-1) 2
(80)
a
(Assumption 5)
VK
2(1 + B) (1 3) ((-1)
T
Σ Dj
a3
1=1
6 - (1-1)
Co
Σ
1=1
where C. = max (40P + v) for I...T.
This completes the proof of Theorem 2. If we can set & such that (1 -)) -(33), the
algorithm achieves O(1/V K) convergence rate.
25


Reviews:
[{"review_id": "rEZGf6ZOAT", "reviewer": "Reviewer_pkB7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "### Strengths:\n1. This paper has done a thorough theoretical analysis of convergence. And the experimental results are presented in detail.\n\n### Questions:\n1. Why is the performance of Adam_Sample with GCN on ogbn-arxiv (Table 2) much lower than the Adam_Full's? Since in the last paragraph of Section 5 and in Figure 4, it is explained that `For arxiv, since it is a small graph, full neighbor aggregation has almost the same memory consumption as sampled neighbor aggregation.` If the sampling rate is large for the arxiv dataset and almost all neighbors are considered, the performance should be close to Adam_Full.\n2. It seems that the hit rate (the ratio of sample nodes that can be found in the buffer) can be significantly affected by the sampling strategy. For example, the hit rate might be low if randomly sampling nodes on a large graph, while it might be relatively high if the center nodes are sampled through a random walk (there are lots of common neighbors of two neighboring nodes). Do we need to control the hit rate for the theoretical results (it seems that none of the assumptions is about this)? And how does the hit rate affect the efficiency/performance? In Figure 3, it is not evident that using larger $t$ (thus larger hit rate) can bring any gain in performance/convergence speed.\n\n### Weaknesses:\n1. The paper did not compare the proposed algorithm with the state-of-the-art sampling strategies. In section 5, it is said that `We adopt the layer-wise sampling method in Zou et al. (2019) for neighbor sampling.` I assume this layer-wise sampling strategy is used for the Adam_Sample baseline and the proposed Sparse_SCO algorithm (please correct me if wrong). However, it is known that some other subgraph sampling strategies may be better on the considered datasets in terms of performance (e.g., on YELP, GraphSAINT-RW can achieve 0.653±0.003; see Table 2 in the GraphSAINT paper (Zeng et al., 2019), while the Adam_Sample reported is 0.631) and convergence speed & training time (e.g., Figure 2 in (Zeng et al., 2019)). In general, given that there are many sampling strategies available now, considering only one sampling method (as baselines and used in Sparse_SCO) is insufficient. The paper said, `it is hard to draw a direct comparison with GraphSAINT because the sampling methods and the model architectures are different.` However, GraphSAINT can be applied to any model architecture. And it is not only when the sampling method is exactly the same, the two scalable approaches are comparable.\n2. The paper considered limited GNN backbone architectures/aggregators. Firstly, because of Assumption 3, i.e., sampled neighbor aggregation is unbiased, the aggregator considered might be limited to some elementary ones, e.g., mean aggregator in GCN and GraphSAGE. However, even if it is hard to be incorporated into the theoretical framework, it is interesting to try other aggregators in GIN, GAT, and PNA. The practical usefulness might be limited if the algorithm cannot be applied to these famous GNN backbones.", "summary_of_the_paper": "This paper proposed an improved variant of the Stochastic Compositional Optimization (SCO) framework to train GNNs, replacing all nodes' moving averages with a sparse representation. The proposed algorithm only requires a fixed-size buffer, regardless of the graph size, solving the memory issue of SCO algorithms and making it practically applicable to large graphs. The paper showed that the proposed algorithm preserves the convergence rate of the original SCO algorithm and experimentally validated that the algorithm could outperform the traditional Adam SGD for GNN training with a small memory overhead.", "summary_of_the_review": "This paper proposed an improved variant of the Stochastic Compositional Optimization (SCO) framework to train GNNs, using a memory buffer to approximate the moving averages of all nodes. Such a fixed-size buffer solution makes the SCO algorithms practical for large graphs. However, limited intuitions are provided to understand the design of such buffer and its effectiveness in practice. Most importantly, the proposed Sparse_SCO algorithm is not superior to Adam_Sample in terms of memory and time efficiency. The performance and convergence speed are better than layer-wise sampling method (Zou et al., 2019), but it is questionable whether it can outperform other sampling strategies like GraphSAINT (Zeng et al., 2019) and ClusterGCN (Chiang et al., 2019). Moreover, the proposed SpSC algorithm is only evaluated with GCN and GraphSAGE and using one sampling algorithm in (Zou et al., 2019). It is unclear if it can be applied to other GNN backbone models and combined with other sampling strategies. Given the reasons above, I cannot recommend the current manuscript for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "mU0vD3v3luJ", "reviewer": "Reviewer_7iri", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Pros:\n1. The idea of reducing the memory cost is interesting. It does help to apply the stochastic compositional gradient descent method to train GNN.\n\n2. The experimental results show improvement over existing methods. \n\nCons:\n\n1. The writing is not clear, e.g. what's the meaning of the last term in Eq.(11)? More explanation is needed. \n\n2. The definition for the projection matrix is not very clear. Is it a  matrix with binary values?\n\n3. The proof is not correct. If I am right, you cannot guarantee $\\lambda_1>0$ in Theorem 1. Hence, the convergence rate is not true.\n\n4. Assumption 4 is not reasonable. No literature about the stochastic compositional optimization problem used this assumption.  According to the value of $\\beta_k$ in Theorem 1, when $K$ approaches infinity, the variance approaches zero. It is not reasonable. Even though the full gradient approaches zero when it converges, we cannot say the stochastic gradient approaches zero. Thus, the variance could be large. I don't think this assumption is reasonable. \n\n5. Given Assumption 4, why is Assumption 6 introduced?\n\n=======after response=====\n\nThanks for your response. But there are still some fatal flaws in the theoretical analysis.\n\n1. Assumption 4 is still NOT reasonable. Considering that we just use a small subset of neighboring nodes, then the variance is large. But, based on Assumption 4, the variance could approach zero when $\\beta$ approaches zero. Hence, this assumption is definitely NOT reasonable. \n\n2. Theorem 1 still fails to provide a feasible $\\beta$. The authors give an inequality constraint: $\\beta\\leq f(\\beta)$. But it is unclear whether this inequality has a feasible solution. ", "summary_of_the_paper": "This paper formulated the graph neural network as a stochastic compositional optimization problem and then developed a new optimization algorithm to train GNN. However, there are some errors. It is not ready for publication.", "summary_of_the_review": "The idea of reducing the memory cost is interesting and useful. However, there are so many flaws in the theoretical analysis. Hence, I recommend rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_SKFfh-ZDB", "reviewer": "Reviewer_xK4K", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strengths:\n1. The SCO perspective of sampling-based GNN training seems an interesting direction. The idea of improving existing SCO algorithms by only storing the data for nodes sampled in the past few iterations in SCO algorithms is simple and effective.\n2. Compared to SCO and Adam-sample, SpSC has overall better performance.\n3. Under certain assumptions, SpSC has non-trivial convergence guarantees, which is an advantage against many sampling-based approaches. \n\nWeaknesses:\n1. I think the technical novelty of SpSC is not significant. The difference between SCGD and SpSC is incremental. Also the analysis on convergence mainly follows the framework introduced in prior work.\n2. I find that the description of SpSC is difficult to understand. The convergence analyses are quite complicated, and I think some intuition should be provided. \n3. The convergence results depends on many assumptions. I think more comments on these assumptions should be helpful. \n4. In the experiments, it seems that the time and space consumptions of SCO are comparable to those of SpSC, except for the product dataset. Can you provides an explanation on this phenomenon? \n5. There has been lots of recent work on scalable training of GNNs. I think the authors should compare more baselines in the experiments, e.g., VR-GCN, GraphSAINT, or more recently AutoScale GNN. Otherwise, the value and impact of SpSC is unclear. ", "summary_of_the_paper": "This paper studies neighbor sampling techniques for training GNNs. Previous work has observed that sampling-based GNN training can be formulated as a Stochastic Compositional Optimization (SCO) problem. The authors argue that naive implementation of existing SCO algorithms incurs huge memory cost for training GNNs. This paper propose a Sparse Stochastic Compositional (SpSC) gradient method, which only stores the data for nodes sampled in the past few iterations. Convergence analysis on SpSC is provided and empirical results show that SpSC has better performance than naive SCO. ", "summary_of_the_review": "Overall, I think the SCO perspective is interesting, and SpSC demonstrates the possibility of using SCO algorithms to improve the scalability of sampling-based training methods. However, the technical novelty may not be enough. Moreover, I think authors should compare more baselines in the experiments and the presentation could also be improved.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AeT4hTyxHhC", "reviewer": "Reviewer_YqXv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper develops a variant of SCO algorithms using a sparse moving average. The resulting method can be applied to large-scale graph training with sampling-based methods. My main concerns of this paper are the novelty and the unconvincing experiments.\n\n#####Pros#####\n\n1. This work considers the GNN training problem of large-scale graphs. The studied problem is quite interesting and really useful for real-world applications.\n\n\n2. The organization of this manuscript is good and easy to follow.\n\n#####Cons#####\n\n1. The main concern is that the novelty of this work is not enough. It is presented in previous works [Cong et al., 2020; 2021] that sampling-based GNN training can be understood as an SCO problem. Considering this point and the existence of SCGD work [Yang et al., 2019], this work only introduces the sparse version of the moving average, which can hardly be considered as a novel idea. In addition, the advantages in terms of time and memory of this method over SCO are not obvious, as shown in Table 3 and Figure 4. Therefore, the novelty and advantages of the proposal are limited.\n\n\n\n2. The second concern is about the experiments. (1) This work only compares with original GCN and GraphSAGE, and does not include many recent methods on large-scale graph training, such as GNNAutoScale [1]. As far as I know, the performance of this method is not as good as the recent methods. (2) The current version does not provide a clear explanation of why Sparse_SCO can be better than SCO. The authors mention that it could be over-fitting. However, according to the training loss in Figure 3, we cannot observe obvious phenomenon of over-fitting. Hence, this point should be clarified. \n\n\n[1] Fey, Matthias, et al. \"GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings.\" arXiv preprint arXiv:2106.05609 (2021).", "summary_of_the_paper": "This paper studies the problem of training GNNs on large-scale graphs. Specifically, it proposes to use sparse moving average for sampling-based GNN training strategies. The convergence rate of the proposed approach has been proved under several assumptions. The authors conduct experiments on several large-scale datasets to show the effectiveness and efficiency of the proposal.", "summary_of_the_review": "Overall, I think the current version is not ready for publishing on ICLR due to the limited novelty and unconvincing experiments. I recommend authors to strengthen its novelty and make the experiments to be more convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes to train large-scale graph neural networks by replacing the moving averages used in the stochastic compositional optimization (SCO) framework with sparse moving averages. This reduces the memory required for SCO, allowing their algorithm to scale  to larger graphs. 

The consensus is that the approach is reasonable, but incremental both in the change over SCGD and the change in the analysis. More importantly, the reviewers identified several sampling-based methods for scaling up training of GNNs that are important baselines for the proposed algorithm; the relative merits of the method against these approaches should be established with further experiments.
Decision: Reject