LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence
Authors: Zhihao Shi
Xize Liang
Jie Wang
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Graph Nerual Networks
Scalable Training
Provable Convergence
Local Message Compensation

Abstract: The message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications.
However, training GNNs on large-scale graphs suffers from the well-known neighbor explosion problem, i.e., the exponentially increasing dependencies of nodes with the number of message passing layers. Subgraph-wise sampling methods---a promising class of mini-batch training techniques---discard messages outside the mini-batches in backward passes to avoid the neighbor explosion problem at the expense of gradient estimation accuracy. This poses significant challenges to their convergence analysis and convergence speeds, which seriously limits their reliable real-world applications. To address this challenge, we propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC). To the best of our knowledge, LMC is the {\it first} subgraph-wise sampling method with provable convergence. The key idea of LMC is to retrieve the discarded messages in backward passes based on a message passing formulation of backward passes. By efficient and effective compensations for the discarded messages in both forward and backward passes, LMC computes accurate mini-batch gradients and thus accelerates convergence. We further show that LMC converges to first-order stationary points of GNNs. Experiments on large-scale benchmark tasks demonstrate that LMC significantly outperforms state-of-the-art subgraph-wise sampling methods in terms of efficiency.

Published as a conference paper at ICLR 2023
LMC: FAST TRAINING OF GNNS VIA SUBGRAPH- WISE SAMPLING WITH PROVABLE CONVERGENCE
Zhihao Shi Xize Liang ', Jie Wang"!
University of Science and Technology of China
ABSTRACT
The message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications. However, training GNNs on large-scale graphs suffers from the well-known neighbor explosion problem, i.c., the expo- nentially increasing dependencies of nodes with the number of message passing layers. Subgraph-wise sampling methods a promising class of mini-batch train- ing techniques- discard messages outside the mini-batches in backward passes to avoid the neighbor explosion problem at the expense of gradient estimation accuracy. This poses significant challenges to their convergence analysis and con- vergence speeds, which seriously limits their reliable real- wal-world applications. To address this challenge, convergence guarantee, namely Local Message Compensation (LMC). To the best of our knowledge, LMC is the first subgraph-wise sampling method with provable convergence. The key idea of LMC is to retrieve the discarded messages in back- ward passes based on a message passing formulation of backward passes. By effi- cient and effective compensations for the discarded messages in both forward and backward passes, LMC computes accurate mini-batch gradients and thus acceler- ates convergence. We further show that LMC converges to first-order stationary points of GNNs. Experiments on large-scale benchmark tasks demonstrate that LMC significantly outperforms ofte--of-hheart subgraph-wise sampling methods in terms of efficiency.
propose novel subgraph-wise sampling method with
INTRODUCTION
Graph neural networks (GNNs) are powerful frameworks that generate node embeddings for graphs via the iterative message passing (MP) scheme (Hamilton) 2020). At each MP layer, GNNs aggre- gate messages from each node's neighborhood and then update node embeddings based aggre- gation results. Such a scheme has achieved great success in many real-world applications involving graph-structured data, such as search engines (Brin & Page 1998), recommendation systems (Fan et al. 2019), materials engineering (Gostick et al.) (016), molecular property prediction (Moloi &
Ali 2005 Kearnes et al. 2016). and combinatorial optimization (Wang et al. 2023).
However, the iterative MP scheme poses challenges to training GNNs on large-scale graphs. One commonly-seen approach scale deep models to arbitrarily large-scale data with limited GPU memory is to approximate full-batch gradients by mini-batch gradients. Nevertheless, for the graph- structured data, the computational costs for computing the loss across mini-batch of nodes and the corresponding mini-batch gradients are expensive due to the well-known neighbor explosion problem. Specifically, the embedding of a node at the k-thh MP layer recursively depends on the embeddings of its neighbors at the (A: - 1)-th MP layer. Thus, the complexity grows exponentially with the number of MP layers.
To deal with the neighbor explosion problem, recent works propose various sampling techniques to reduce the number of nodes involved in message passing (Ma & Tang 202T). T). For example, node- wise (Hamilton et al.) 2017] Chen et al. 2018a) and layer-wiss (Chen et al. 2018b] Zou al. 2019) Huang et al.]|2018] sampling methods recursively sample neighbors over MP layers to estimate node embeddings and corresponding mini-batch gradients. Unlike the recursive fashion, subgraph-wist
sampling methods (Chiang et al. 2019 Zeng et al. 2020 Fey et al. 2021 Zeng et al.) 2021) adopt
"Corresponding author; jiewangx@ustc.edu..

---

Published as a conference paper at ICLR 2023
cheap and simple one-shot sampling fashion, i.e., sampling the same subgraph constructed based on a mini-batch for different MP layers. By discarding messages outside the mini-batches, subgraph- wise sampling methods restrict message passing to the mini-batches such that the complexity grows linearly with the number of MP layers. Moreover, subgraph-wise sampling methods are applicable to wide range of GNN architectures by directly running GNNs the subgraphs constructed by the sampled mini- mini-batches (Fey et al., 2021). Because of these advantages, subgraph-wise sampling methods have recently drawn increasing attention.
Despite the empirical success of subgraph-wise sampling methods, discarding messages outside the mini-batch sacrifices the gradient estimation accuracy. which poses significant challenges to their convergence behaviors. First, recent works (Chen et al.] [018a]] Cong et al. (2020) demonstrate that the inaccurate mini-batch gradients seriously hurt the convergence speeds of GNNs. Second, in Section 7.3 we demonstrate that many subgraph- wiise sampling methods are difficult to resemble full-batch performance under small batch sizes, which we usually use to avoid running out of GPU memory in practice. These issues seriously limit the real-world applications of GNNs.
In this paper, we propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC), which uses efficient and effective compensations to correct the biases of mini-bated batch gradients and thus accelerates convergence. To the best of our knowledge, LMC is the first subgraph-wist sampling method with provable convergence. Specif- ically, we first propose unbiased mini-batch gradients for the one-shot sampling fashion, which helps decompose the gradient computation errors into two components: the bias from the discarded messages and the variance of the unbiased mini-batch gradients. Second, based on message pass- ing formulation of backward passes, we retrieve the messages discarded by existing subgraph-wise sampling methods during the approximation to the unbiased mini-batch gradients. Finally, we pro- pose efficient and effective compensations for the discarded messages with combination of incom- plete up-to- up-to-date messages and messages generated from historical information in previous iterations, avoiding the exponentially growing time and memory consumption. An appealing feature of the re- sulting mechanism is that it can effectively correct the biases of mini-hatch gradients, leading to accurate gradient estimation and the speed-up of convergence. We further show that LMC con- verges to first-order stationary points of GNNs. Notably, the convergence of LMC is based on the interactions between mini-batch nodes and their 1-hop neighbors, without the recursive expansion of neighborhoods aggregate information far away from the mini-batches. Experiments scale benchmark tasks demonstrate that LMC significantly outperforms state-of-the subgraph- wise sampling methods in terms of efficiency. Moreover, under small batch sizes, LMC outperforms the baselines and resembles the prediction performance of full-batch methods.
large-
RELATED WORK
In this section, we discuss some works related to our proposed method.
Subgraph-wise Sampling Methods Subgraph-wise sampling methods sample mini-batch and then construct the same subgraph based on it for different MP layers (Ma & Tang 2021). For
example, Cluster-GCN (Chiang al. 2019) and GraphSAINT (Zeng al. 2020) construct the subgraph induced by a sampled mini-batch. They encourage connections between the sampled nodes by graph clustering methods (e.g., METIS (Karypis & Kumar, 1998) and Graclus (Dhillon) eet al. 2007)), edge, node, or random-wall baalk-baaedddeee samplers. GNNAutoScale (GAS) (Fey et al.) 1 and MVS-GNN (Cong et al. 2020) use historical embeddings to generate messages outside sampled subgraph, maintaining the expressiveness of the original GNNs.
Recursive Graph Sampling Methods. Both node-wise and layer-wise sampling methods recur- sively sample neighbors over MP layers and then construct different computation graphs for each MP layer. Node-wise sampling methods (Hamilton al. 2017 Chen et al. 2018a) aggregate mes- sages from a small subset of sampled neighborhoods at each MP layer to decrease the bases in the exponentially increasing dependencies. To avoid the exponentially growing computation, layer- wise sampling methods (Chen et al.,, 2018b; Zou et al.) 2019: Huang et al.) (2018) independently sample nodes for each MP layer and then use importance sampling to reduce variance, resulting in a constant sample size in each MP layer.
Pre-Processing Methods. Another line for scalable graph neural networks is to develop pre- processing Methods. They aggregate the raw input features and then take the pro-psscssiing features as input into subsequent models. As the aggregation has no parameters, they can use stochastic gradient descent to train the subsequent models without the neighbor explosion problem. While
2

---

Published as a conference paper at ICLR 2023
they efficient in training and inference, they are not applicable to powerful GNNs with trainable aggregation process.
Affordable Approximation. The historical values are affordable ap- proximations of the exact values in practice. However, they suffer from frequent data transfers to/from the GPU and the staleness problem. For example, in node-wise sampling, VR-GCN (Chen et al. 2018a 8a) uses historical embeddings to reduce the variance from neighbor sampling (Hamilton
Historical Values
al. 2017). GAS (Fey et al., 2021) proposes concurrent mini-batch execution to transfer the active historical embeddings to and from the GPU, leading to comparable runtime with the standard full-batch approach. GraphFM-IB and GraphFM-OB (Yu al., 2022) apply a momentum step on historical embeddings for node-wise and subgraph-wis wise sampling methods with historical embed- dings, respectively, alleviate the staleness problem. Both LMC and GraphFM-OB use the node embeddings in the mini-batch to alleviate the staleness problem of the node embeddings outside the mini-batch. We discuss the main differences between LMC and GraphFM-OB in Appendix C.1
3 PRELIMINARIES
We introduce notations and graph neural networks in Sections 3.1 and 3.2 respectively.
3.1 NOTATIONS
A graph G (V,E) is defined by a set of nodes V = fui, ..,,.., bn and set of edges & among these nodes. The set of nodes consists of labeled nodes V. and unlabeled nodes Vo == V \ VL. Let node vy V, ((,) (0z Vl(es, vy) E (w, vz) & denote an edge going from node v; denoteeN(xs))U (uz) We assume that G is undirected, denote the neighborhood of node us, and and ((es) denote
i.., " E (M))) + i E (n;))- Let (SS) {u Vl(u,, 15) E &, v S} denote the neighhorhoods of a set of nodes S and ((S) denote (S)) U.S. For a positive integer I,, [T.] denotes (1...., [.}. Let the boldface character x, E Rd denote the feature of node us with dimension d.,, Let h, E R be the d-dimensional embedding of the node v. Let X = X2,,
E Rd=x* and H
(h1,
E Rd*=, We also denote the embeddings of a set of nodes S = 1 by H
(ha,) k=1 E gax|s1, For p x matrix A E 18*8, A E 18" denotes the vectorization of A, i.c.,
A.) = A1 We denote the j-th columns of A by A,,
3.2 GRAPH NEURAL NETWORKS
For the semi supervise node-level prediction, Graph Neural Networks (GNNs) aim to learn node embeddings with parameters e by minimizing the objective function V Eie,, (w, ys) such that = GNN((X, 0), where Ey is the composition of an output layer with parameters w and loss function.
1
GNNs follow the message passing framework in which vector messages are exchanged between nodes and updated using neural networks. An L-layer GNN performs L message passing iterations with different parameters e = (f to generate the final node embeddings H= H as
H' for (H' (H'-):), E [Z],
where H and for the message passing function of the 1-th layer with parameters 0%
The message passing function for follows an aggregation and update scheme, i.c.,
h = up- [ ( x:): mw = +o (( (h)) l0 E N(x.)), Le [4],
(2)
where 90 is the function generating individual messages for each neighbor of in the I-th mes- sage passing iteration, &g is the aggregation function mapping a set of messages to the final mes- sage m and dgt is the update function that combines previous node embedding h(-), message 1-1 and features x, to update node embeddings.
4 MESSAGE PASSING IN BACKWARD PASSES
In Section 4.1
we introduce the gradients of GNNs and formulate the backward passes message passing. Then we propose backward SGD, which is an SGD variant, in Section 4.2
4.1
BACKWARD PASSES AND MESSAGE PASSING FORMULATION
The gradient v.. is easy to compute and we hence introduce the chain rule to compute V in this section, where θ (8)) Let v á V for I [L.] be auxiliary variables. It is easy to compute
3

---

Published as a conference paper at ICLR 2023
Vz V C. C. By the chain rule, iteratively compute V based on V as
V Eg ( (V(+1) a (V (o V
(3)
and
V = Optti c ................................ 0g. (V4).
(4)
Then, we compute the gradient Vgch (Varfe M [T.] by using autograd packages for vector- Jacobian product.
We formulate backward passes, i.e., the processes of iterating Equation message passing. To see this, we need to notice that Equation (3) is equivalent to
V
Σ (in (h/y m()())))3))) Vitt, i [n], eyEA(
(S)
where VA is the k-th column of v and mirto) function of hy defined in Equation 2 Equa- tion uses (Vig (lh), mixtey) xx) Vjt1, sum aggregation, and the identity mapping as the generation function, the aggregation function, and the update function, respectively.
4.2 BACKWARD SGD
In this section, we develop an SGD variant- backward SGD, which provides unbiased gradient estimations based on the message passing formulation of backward passes. Backward SGD the basis of our proposed subgraph- wiiee sampling method, i.e., LMC, in Section
Given sampled mini-batch Vs, suppose that we have computed exact node embeddings (H > and auxiliary variables (Vig)== of nodes in Vs. To simplify the analysis, we assume that VB is uniformly sampled from V and the corresponding set of labeled nodes VL. := VB O V2 is uniformly sampled from VL. When the sampling not uniform, we use the normalization technique (Zeng et al. 2020) to enforce the assumption (please see AA..nd
First, backward SGD computes the mini-batch gradient g.. for parameters w by the derivative of mini-batch loss Liv
[vggl EnjeVin Emr(,,, Us) as
gw (VB) = |Vbel
Σ
(hy.
(6)
My MgEV
Then, backward SGD computes the mini-batch gradient Bar (Vs) for parameters as
Se (VB)
Σ
(V Verugi (h//
1-1 ) xx) V E [4].
VB
BYEVB
Note that the mini-batch gradients gai Bat (Vs) for different E [L] are based on the same mini-batch Vs. which facilitates designing subgraph- abbrepp-wiise sampling methods based on backward SGD, Another appealing feature of backward SGD is that the mini-batch gradients g.. (Vs) and gor (Vs), I E [L] are unbiased, as shown in the following theorem. Please see Appendix [ for the detailed proof.
Theorem 1. Suppose that mini-batch Ve is uniformly sampled from and the corresponding labeled nodes VLg = Vs Vt uniformly sampled from Vt. Then the mini-batch gradients (Vs) and Ba (Vs), [Z.] in Equations (6) and ( are unbiased.
LOCAL MESSAGE COMPENSATION
The exact mini-batch gradients g (Vs) and gar Ba(Vs) (Vs), E [T.] computed by backward SGD depend on exact embeddings and auxiliary variables of nodes in the mini-batch Vs rather than the whole graph. However, backward SGD not scalable, as the exact (Hb ) and (Vi Vi are expensive compute due the neighbor explosion problem.
In this section, to deal with the neighbor explosion problem, we develop a novel and scalable subgraph-wise sampling method for GNNs, namely Local Message Compensation (LMC). LMC first efficiently estimates (H and (Vi by convex combinations of the incomplete up- to-date values and the historical values, and then computes the mini-batch gradients as shown in

---

Published as a conference paper at ICLR 2023
Layer2
Layer2
V
Lopert
Layer2
Lapero
Lagerd
(a) Original graph
(b) Forward passes of GAS
(c) Forward passes of LMC
Layar?
V/3
1xyer2
batch nodes
1-hop out-of-batch
V/3
V4
Other out-of-batch
Message passing
Historical message passing
(d) Backward passes of GAS
Backward passes of LMC
Figure 1: Comparison of LMC with GNNAutoScale (GAS) (Fey et al. 2021). (a) shows the orig- inal graph with in-batch nodes, I-hop nut-of-batch nodes, and other out-of-batch nodes in orange, blue, and grey, respectively. (b) and (d) show the computation graphs of forward passes and back- ward passes of GAS, respectively. (c) and (e) show the computation graphs of forward passes and backward passes of LMC, respectively.
Equations and Section 6 In Algorithm| D and Section 6 we denote a value in the I-th layer at the k-th iteration by Lk but elsewhere we omit the superscript and denote by (-)*.
We show that LMC converges first-order stationary points of GNNs in
In each training iteration, we sample mini-batch of nodes Vas and propose to approximate values, i.e. node embeddings and auxiliary variables, outside Vs by convex combinations of historical values, denoted Hyv, and Virve and incomplete up-to-date values, denoted H(p,,, and VArve
In forward passes, we initialize the temporary embeddings for = as ñ = X and update historical embeddings of nodes in Vs, i.e.. Hyg. in the order of I 1,2,..., L. Specifically, in the I-th layer, we first update the historical embedding of each node v E V as
h [h; . x:);
m ( = Do (f (ho (1,"") 1 E (NN) u (h: 1 us E ((()) vss)).
(8)
Then, we compute the temporary embedding of each neighbor E (V2=)) V as h (1 3.)h +3
where B, E [0, 1] the convex combination coefficient for node v, and
hi ugi (b)- m xs);
m m @e (1
1-1
1-1 1 E (N()) u {90 (b, 10 (N(Vs) [B8) (Ds))
(10)
We call C²2 2 4 (fov (h,) NN (s))) the local message compensation in the i-th layer
in forward passes. For / E [L]. F. an approximation to hf computed by Equation (2) Notice that the total size of Equations { TOp is linear with [W((s)] rather than the size of the whole graph. Suppose that the maximum neighborhood size is nmax and the number of layers is L, then the time complexity in forward passes is (TT (Vsldd+
In backward passes, we initialize the temporary auxiliary variables for I = L V VHC and update historical auxiliary variables of nodes in Vs. i.e., V in the order of 1 I. 1,
5

---

Algorithm Crforithm[summannnn summarizes LMC. Unlike above, we add a superscript & for each value to indicate that the value at the k-th iteration. At preprocessing step, we partition y into B parts (Va) At the k- th training step, LMC first randomly samples a subgraph constructed by Vo,- Notice that we sample more subgraphs to build a large graph in experiments whose convergence analysis is consistent with that of sampling single subgraph. Then, LMC updates the stored historical node embeddings H Published as a conference paper at ICLR 2023
Specifically, in the 1-th layer, we first update the historical auxiliary variable of each
Va as
Σ
(Vnjugit)
(T). m m x5) V
oy (e
E
(VnugrrnCii T xx))))))) Vit1
(11)
where Fi m and fij, are computed as shown in Equations temporary auxiliary variable of each neighbor os EN((V)) VB as
10).
Then, we compute the
V = =1 (1-1--1 V. : +3..
(12)
where 3, is the convex combination coefficient used in Equation 9 and m m' xi) ylt
Σ
2 VeNinnn
Σ
(Vigurra (h', I m x3)) Vit1
(13)
We call C A EujeN (Vngiget (hi, mirco) x;)) V the local message compensation in
the 1-th layer in backward passes. For E [L], V is an approximation to V computed by Equation
B). Similar to forward passes, the time complexity in backward passes is (L [LLddax VVll+ Valld)),
where Tmax is the maximum neighborhood size and L is the number of layers.
LMC additionally stores the historical node embeddings H' and auxiliary vari- ables V for E [L]. As pointed out in (Fey
Algorithm Local Message Compensation
1: Input: The learning rate and the convex combi- nation coefficients (8:)==-
et al.] 2021), we can store the majority of historical values RAM or hard drive storage rather than GPU memory. Thus, the active historical values in forward and backward passes employ (vrmax V' and ( Vssd) GPU memory, respec- tively (see Appendix B). As the time and memory complexity are independent the size the whole graph, i.e., [V], LMC is scalable. We summarize the computa- tional complexity in Appendix B
2: Partition y into B parts (V))
3: for k 1....,A N do
4: Randomly sample Vo, from (1b)
5: Initialize H 0.A A
6: for 1,..., L do
7:
Update H Compute i end for
b
and (0)
9:
10: Initialize V
Litk 4L.
VHLC
11:
for 1 L
1 do
[igure[[shows the message passing mech- anisms GAS (Fey al., (221] and
12:
Update
Vag
11
13:
Compute NiV 100 end for
V
12 and
13
LMC. Compared with GAS, LMC pro- poses compensation messages between in- batch nodes and their I-hop neighbors si- multancously in forward and backward
14:
15:
Compute gú and E I E [L]
b and
16:
Update parameters by
17:
w² === -- 7
passes. This corrects the biases of mini- batch gradients and thus accelerates con- vergence.
18:
gi. = gl.k 78 I [T]]
19:
end for
in the order | 1, ..... by Equations (8) 10p. and the stored historical auxiliary variables v in the order of I I. - ......1 by Equations (11) (T).. By the randomly updating, the historical values get close to the exact up-to-date values. Finally, for / [L] and ey Vi,, by replacing hy*
f.k (ety) and vi..t in Equations ( and (7) with In m (e and V respectively, LMC computes mini-bated gradients g.. Ba B....... Hor. update parameters w, 0 "......".

---

Published as a conference paper at ICLR 2023
6 THEORETICAL ANALYSIS
In this section, we provide the theoretical analysis of LMC. Theorem shows that the biases of mini-batch gradients computed by LMC can tend to an arbitrarily small value by setting proper learning rate and convex combination coefficients. Then, Theorem B shows that LMC converges to first-order stationary points of GNNs. We provide detailed proof' of the theorems in Appendix [ In the theoretical analysis, we suppose that the following assumptions hold in this paper.
Assumption 1. Assume that (1) at the k-th iteration, a batch of nodes V's is uniformly sampled from and the corresponding labeled node set Vi. = n is uniformly sampled from Vt. (2) functions
fel. Pai, WwC, V Lc, Vulw, and Villg are 7-Lipschitz with y > 1, vl [T.] (3) norms || [|,,
[Ir, | "Ir,,
| I V Ir. |[,,, V [r. Vl VV l lla. and
gl 2l2 are bounded by G 1, VI kE.
Theorem 2. Suppose that Assumption 7 holds, then with 17 O(52) and 3. O(E2), E (n), there
existy C > 0 and E (0, 1) such that
E [l Bau (w** M(l Ce Cp E (wF)), AA EN,,,
- E Bl (OL.hr- v (o [aal] S Cs Cs+ CC Cp= + Var(Ba (O. VI VIE14),
Theorem 3. Suppose that Assumption 7 holds. Besides, assume that the optimal value L" inf f(w, θ) is bounded by G. Then, with " OOE*). B. O iE [nl), and N = O)= LMC ensures to find an e-stationary solution such that vellVv..e @%)llal S after running for N iterations, where is uniformly selected from [N] and @ = (
EXPERIMENTS
We then evaluate the convergence and efficiency of LMC in Sections 7.2 and 7.3 Finally, we conduct ablation studies about the proposed compen-
We introduce experimental settings in Section 7.1
sations in Section 7.4 We run all experiments on single GeForce RTX 2080 Ti (11 GB).
7.1 EXPERIMENTAL SETTINGS
Datasets. Some recent works (Hu et al. 2020) have indicated that many frequently-used graph datasets are too small compared with graphs in real-world applications. Therefore, we evaluate I.MC on four large datasets, PPI, REDDIT, FLICKR (Hamilton et al. (2017). and Ogbn-arxiv (Hu et al.]
2020). These datasets contain thousands or millions of nodes/edges and have been widely used in previous works (Fey et al. 2021 Zeng et al. 2020 Hamilton et al. 2017 Chiang et al. 2019 Chen
et al. 2018a|b) b). For more details, please refer to Appendix
Baselines and Implementation Details. In terms of prediction performance, our baselines in- clude node-wise sampling methods (GraphSAGE (Hamilton al.) (017) and VR-GCN (Chen al. 2018ab), layer-wise sampling method (FASTGCN (Chen et al. 2018h) and LADIES (Zou et al,
2. subgraph-wise sampling methods (CLUSTER-GGY, (Chiang et al. 2019), GRAPHSAINT ZZng et al., (2020). FM (Yu et al. (2022), and GAS (Fey et al. (021)), and precomputing method (SIGN (Rossi al. 20200). By noticing that GAS and FM achieve the state-of-the-ar art prediction performance (Table 1 among the baselines, we further compare the efficiency of LMC with GAS, FM, and BUSTER--GNN another subgraph-wis sampling method using METIS partition. We im- plement LMC, FM, and CLUSTER-GCH, based on the codes and toolkits of GAS (Fey et al. 2021) to ensure a fair comparison. For other implementation details, please refer to Appendix A.3
To ensure fair comparison, we follow the data splits, training pipeline, and most hyperparameters in (Fey et al. 202I) except for the additional hyperparameters in LMC such as Br. We use the grid search to find the best B, (see Appendix A.4 for more details).
Hyperparameters.
7.2 LMC IS FAST WITHOUT SACRIFICING ACCURACY
Table I reports the prediction performance of LMC and the baselines. We report the mean and the standard deviation by running each experiment five times for GAS, FM, and LMC. LMC, FM, and GAS all resemble full-batch performance on all datasets while other baselines may fail, especially on the FLICKR dataset. Moreover, LMC, FM, and GAS with deep GNNs, i.e., GCNII (Chen et al.) 2020) outperform other baselines on all datasets.
7

---

Published as a conference paper at ICLR 2023
As LMC, FM, and GAS share the similar pre- diction performance, we additionally compare the convergence speed of LMC, FM, GAS, and CLUSTER- another subgraph-wise sam- pling method using METIS partition, in Figure 2 and Table 2 We use a sliding window to smooth the convergence curve in Figure 2 as the accuracy on test data is unstable. The solid curves correspond to the mean, and the shaded regions correspond to values within plus mi- nus one standard deviation of the mean. Table reports the number of epochs, the runtime to reach the full-batch accuracy in Table and the GPU memory. As shown in Table 2 and Figure LMC is significantly faster than GAS, espe- cially with speed-up of 2x on REDDIT. No-
Table Prediction performance on large graph datasets. OOM denotes the out-of- memoryy issuc. Bold font indicates the best result and underline indicates the second best result.
modes Pedges
230K
57K 794K
169K
11.0
450K
1.2M
Method
REDDIT
PPI
FLICKR
ogion- arxiv
GRAPESAGE
95.40
61.20
50.10
71.49
VR-GCN
85.60
FASTGCN
93.70
50,40
LADIES
92.80
2
CLUSTER-GCN GRAPESAINT
99.36
97.00
99,50
$1.10
SIGN
96.80
97.00
51,40
GCN
95.43
97.58
53.73
71.64
GCNII
00M
00M
55,28
72.83
2a
GAS
95.35_mm
98.91
1314
.1.54.c.19
GCNII
96.73
99.36 22022
55.42
72.50
tably, the test accuracy of LMC is more stable than GAS, and thus the smooth test accuracy of
LMC FM
GCN
95.27
98.91
53.48
=1.49:003
GCNII
96.52 nos
99.34 p013
54.68 1omn
72. 72.54_007
LMC outperforms GAS in Figure 2b Although GAS finally resembles full-batch performance in Table I by selecting the best performance on the valid data, it may fail to resemble under small batch sizes due to its unstable process (see Section 7.3). Another appealing feature of LMC that LMC shares comparable GPU memory costs with GAS, and thus LMC avoids the neighbor explo- sion problem. FM is slower than other methods, as they additionally update historical embeddings in the storage for the nodes outside the mini-batches. Please see Appendix E.2 for the comparison in terms of training time per epoch.
GCN
95.44
98.87
53.80
71.44
GCNII
96.88
99. 99
55.36
72. 72.76:0022
Table 2: Efficiency of CLUSTER-GCN, GAS, FM, and LMC.
Epochs
Runtime (S)
Memory (MB)
Dataset& GNN
CLUSTER
GAS
FM
LMC
CLUSTER
GAS
LMC
CLUSTER
LMC
Ogbn-arxiv & GCN
211.0
176.0
152.4
124.4
108
79
115
55
424
452
460
557
FLICKR & GCN
379.2
389.4
400.0
334,2
127
117
181
85
310
375
380
376
REDDIT GCN
239.0
372.4
400.0
166.8
516
790
2269
381
1193
1508
1644
1829
PPI & GCN
428.0
293.6
286.4
290.2
359
179
224
179
212
214
218
267
Oghn-arxiv & GCNH
234.8
373.6
197.4
218
381
178
453
454
568
FLICKR & GCNII
352
400.0
356
465
576
475
396
402
468
To further illustrate the convergence of LMC, we compare the errors of mini-batch gradients computed by CLUSTER, GAS, and LMC. At epoch training step, we record the relative errors gg V Cll2 / V Clla, where V C is the full-batch gradient for the parameters at the I-th MP layer and the Sø: is mini-batch gradient. To avoid the randomness of the full-batch gradient a C, we set the dropout rate as zero. We report average relative errors during training in Figure enjoys the smallest estimated errors in the experiments.
LMC
Ogbn Ogbn-andtr& andr & GCN
FUCKKR & GCN
REDDIT & GCNI
1120
PPI & GCNII
TrensLas
Trainooo ose
000 0.5
1122
E37e
1022
Runtime (5)
Rumtime
Rundine (s)
Runime (5)
(a) Training loss
Ogbn ardt
REDDIT GCNI
&
0.74
1:52
Sase 3:00
Toallkc
8.00
3.00
R000 Runtimm (5)
Runt me (8)
Runtinm (5)
Rumiim (s)
(b) Testing accuracy
Figure 2: Testing accuracy and training loss w.r.t. runtimes (s).
8

---

Published as a conference paper at ICLR 2023
00
1442
New
(a) Oghn-arxiv
(b) FLICKR
(c) REDDIT
Figure 3: The average relative estimated errors of mini-batch gradients computed by CLUSTER, GAS, and LMC for GCN models.
Table Performance under different batch sizes on the Ogbn-arxir arxiv dataset.
7.3 LMC IS ROBUST IN TERMS OF BATCH SIZES
An appealing feature of mini-batch training methods that they can avoid the out-of-memory issue by de- creasing the batch size. Thus, we evaluate the pre- diction performance of LMC on Ogbn-arxiv datasets with different batch sizes (numbers of clusters). We conduct experiments under different sizes of sampled clusters per mini-batch. We each experiment with the same epoch and search learning rates in the same set. We report the best prediction accuracy in Table [ sizes (batch size = or 2) and achieve comparable performance with GAS (batch size = 5 or 10).
GCN
GCNII
Batch size
GAS
LMC
GAS
LMC
1
70.56
71.65
71.34
72.11
2
71.11
71.89
72.25
72.55
5
71.99
71.84
72.23
72.87
10
71.60
72.14
72.82
72.80
LMC outperforms GAS under small batch
7.4 ABLATION
The improvement of LMC is due to two parts: the compensation in forward passes Cj and the compensation in back passes Cj Compared with GAS, the compensation in forward passes Cy additionally combines the incomplete up-to-date messages. Figure shows the convergence curves of LMC using both C₁2 and C (denoted by Cy&C,), LMC using only C₁ (denoted by Cý), and
GAS on the Ogbn-arxiv dataset. Under small batch sizes, the improvement mainly is due to C and the incomplete up-to-date messages in forward passes may hurt the performance. This is because the mini-batch and the union of their neighbors are hard to contain most neighbors of out-of-hatch nodes when the batch size is small. Thus, the compensation in back passes C is the most im- portant component by correcting the bias of the mini-batch gradients. Under large batch sizes, the improvement due C,, as the large batch sizes decrease the discarded messages and improve the accuracy of the mini-batch gradients (see Table 7 in Appendix). Notably, C still slightly improves the performance. We provide more ablation studies about 3 in Appendix
E.4
GCN
GCNI
GCN
GONII
E35
2.39
Trainiecc
Trainiece
254
900
6.6g
26 366 SAL Epochs
110
Epochts
Us 24 24
20
6.7g
000
20
(a) Under small batch sizes
(b) Under large batch sizes
Figure The improvement of the compensations on the Ogbn-arxiv dataset.
CONCLUSION
In this paper, we propose novel subgraph-wise sampling method with convergence guarantee, namely Local Message Compensation (LMC). LMC uses efficient and effective compensations to correct the biases of mini-batch gradients and thus accelerates convergence. We show that LMC converges to first-order stationary points of GNNs. To the best of our knowledge, LMC the first subgraph-wise sampling method for GNNs with provable convergence. Experiments on large-scale benchmark tasks demonstrate that LMC significantly outperforms state-of-the art subgraph-wise sampling methods in terms of efficiency.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
The authors would like to thank all the anonymous reviewers for their insightful comments. This work supported in part by National Nature Science Foundations of China grants U19B2026, U19B2044, 61836011, 62021001, and 61836006, and the Fundamental Research Funds for the Central Universities grant WK3490000004.
REFERENCES
Sergey Brin and Lawrence Page. The anatomy of large-scale hypertextual web search engine. In Proceedings of the Seventh International Conference on World Wide Web 7, WWW7, pp. 107-117, NLD, 1998. Elsevier Science Publishers B. V.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with vari- ance reduction. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 942-950 PMLR, 10-15 Jul 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b. URL
https://openrew/
net.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th ternational Conference on Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 1725-1735. PMLR, 13-18 Jul 2020. URL httt:://proceedigg..... ftess/vi19/chenle html
html
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsich. 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.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mchrdad Mahdavi. Minimal variance sam- pling with provable guarantees for fast training of graph neural networks. In Proceedings the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, pp. 1393-1403, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379984. doi: 10.1145/394486.34031999
URL
3394486. 3.0369444392
Inderjit Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE Trans. Pattern Anal. Mach. Intell,, 19111);1944-1955 nov 2007.
ISSN 0162-8828.
doi: 10.109/TPAMI.207.11155 URL httpppt::/e....ooooooooot/
TPAM1 2007 1115
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural net- works for social recommendation. In The World Wide Web Conference, WWW '19, pp. 417-426, 2019.
Matthias Fey and Jan F. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICER Workshop on Representation Learning on Graphs and Manifolds, 2019.
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and
expressive graph neural networks via historical embeddings. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3294-33900 3304. PMLR, 18-24 Jul 2021. URL btttss:/pprocediiee ptepp//cccc.ciiiaee.eeeeeeeeeeee wtt.a..peesss////ee///e2///
mlr
J. Gostick, M. Aghighi, J. Hinebaugh, T. Tranter, M. A. Hoeh, H. Day, B. Spellacy, M. H. Sharqawy, A. Bazylak, A. Burns, W. Lehnert, and A. Putz. Openpnm: A pore network modeling package. Computing in Science & Engineering. 18(04):60-744 jul 2016. ISSN 1558-366X. doi: 10.1109/ MCSF.2016.49.
10

---

Published as a conference paper at ICLR 2023
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent EI Ghaoui. Implicit graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.),
Advances in Neural Information Processing Systems. volume 33, pp. 11984-11995. Curran As- sociates, Inc., 2020. URL httpttpppss//ppppeeeesnsseeeeeee meu.
neurips ps. cc/ wwtpppppp///////ccccccc pdf
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information P Processing Systems, pp. 22118-22133, 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biin Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018 URL http:: //ttteee// neurips. httprrpppp..pppppe///111/1 httpe/O0ceeee0eee226666666668889
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal scientific Computing, 20(1):359-392, 1998.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: Moving beyond fingerprints. Journal of Computer-Aided Molecular Design, 30, 08 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR (Poster). OpenReview.net, 2017.
Yao Ma and Jiliang Tang. Deep Learning on Graphs. Cambridge University Press, 2021.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed repre- sentations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26, 2013.
N. P. Moloi and M. M. Ali. An iterative global optimization algorithm for potential energy mini- mization. Comput. Optim. Appl., 119-1321 2005.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Veti Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035, 2019.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word rep- resentation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), ). pp. 1532-1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/w1/D14-1111 112..
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. CoRR, abs/2004. 11000000.1119.. 1198. 2020. URL
200/ 11198
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396- 413, 2020.
Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed mixed-integer linear programming via hierarchical sequence model, 2023. URL URL htapps:///rxiiae org 2330 00244

---

Published as a conference paper at ICLR 2023
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 40-48, New York, New York, USA, 20-22 Jun 2016. PMLR. URL. html
nttps://proceedinng wtw.:gg............mmmm /epress/v48//e http://v////aggggg
Haiyang Yu, Limei Wang. Bokun Wang, Meng Liu, Tianbao Yang, and Shuiwang Ji. GraphFM: Improving large-scale GNN training via feature momentum. In Kamalika Chaudhuri, Stefanie Jegelka, Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 25684-25701, PMLR, 17-23 Jul 2022. URL https: httpsss///poceeeigg.mmimm
(ress/v162/ynn
html
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020. URL httpps://oper.rveeee..ee. foreemiiioooeoeeeeeeee Bew.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kan- nan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. A. Beygelzimer, Y. Dauphin. P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL htt.h: /ttp:///epeeeeeeeeeeemmoe / net. forum? id= IY3 4psXuf
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 H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso-
ciates, Inc., 2019. URL
12

---

Published as a conference paper at ICLR 2023
A MORE DETAILS ABOUT EXPERIMENTS
In this section, we introduce more details about our experiments, including datasets, training and evaluation protocols, and implementations.
A.1 DATASETS
We evaluate LMC on four large datasets, PPI, REDDIT, FLICKR (Hamilton et al. 2017). and Ogbn- arxiv (Hu al. 2020). All of the datasets do contain personally identifiable information or offensive content. Table shows the summary statistics of the datasets. Details about the datasets are follows.
PPI contains 24 protein-protein interaction graphs. Each graph corresponds to a human tis- sue. Each node indicates a protein with positional gene sets, motif gene sets and immuno- logical signatures node features. Edges represent interactions between proteins. The task to classify protein functions.
REDDIT is a post-to-post graph constructed from REDDIT. Each node indicates a post and each edge between posts indicates that the same user comments on both. The task is to classify REDDIT posts into different communities based on (1) the GloVe CommonCrawl word vectors (Pennington et al. (0144) of the post titles and comments, (2) the post's 's scores, and (3) the number of comments made on the posts.
Daxivv is directed citation network between all Computer Science (CS) arXiv papers indexed by MAG (Wang et al., 2020). Each node is an arXiv paper and each directed edge indicates that paper cites another one. The task is classify unlabeled arXiv papers into different primary categories based on labeled papers and node features, which are com- puted by averaging word2vec (Mikolov et al. 2013) embeddings of words in papers' title and abstract.
FLICKR categorizes types of images based on their descriptions and properties (Fey et al, 2021
Zeng al. 2020
Table 4: Statistics of the datasets used in our experiments.
Dataset
#Graphs
#Classes
Total #Nodes
Total #Edges
PPI REDDIT
24
121
56,944
793,632 11,606.919
41
232,965
Ogbn-arxiv FLICKR
40
169,343
1,157,799
7
89,250
449,878
A.2 TRAINING AND EVALUATION PROTOCOLS
We run all the experiments plemented in Pytorch (Paszke et al. 2019) and Py PoTch Geometric (Fey & Lenssen 2019) based
single GeForce RTX 2080 Ti (11 GB). All the models are im-
on the official implementation of (Fey al 2021 The code of LMC available on GitHub https: thu.. www.:/t....oo............. Wwto/M/IRAaab-... USTC CNN-CCCGGNNMCC
Data Splitting.
We use the data splitting strategies following previous works (Fey al. 202
et al. 2020).
A.3
IMPLEMENTATION DETAILS
A.3.1 NORMALIZATION TECHNIQUE
In Section 4.2 in the main text, we assume that the subgraph Vg is uniformly sampled from V and the corresponding of labeled nodes Vi, = Ve Vy is uniformly sampled from Vz. To enforce
The does mention the license.
13

---

Published as a conference paper at ICLR 2023
the assumption, use the normalization technique reweight Equations 6 and 7 in the main text.
Suppose partition the whole graph V into b parts (Vis, Miz1 and then uniformly sample clus- ters without replacement to construct subgraph Vg. By the normalization technique, Equation ( becomes
gm (Vs) = blVLo
Σ
Vullo (aj. (b).
(14)
c|V2
VLS
&lVigl c/V
where
is the corresponding weight. Similarly, Equation becomes
b/Va|
|
go
Σ
Vou(h,, m.
(15)
c/V
VB
EyEVo
where
biVel cgT
the corresponding weight.
A.3.2 INCORPORATING BATCH NORMALIZATION
We uniformly sample mini-batch of nodes V/8 and generate the induced subgraph of E (VV)). we directly feed the H (((w) batch normalization layer, the learned and standard deviation of the batch normalization layer may be biased. Thus, LMC first feeds the embeddings of the mini- batch H (!)
Ve to batch normalization layer and then feeds the embeddings outside the mini-batch H
(1)
VV to another batch normalization layer.
A.4 SELECTION OF 3
We select B; score(i)a for each node where E [0. is hyperparameter and score function measure the quality of the incomplete up-to-date messages. We search score in {f(x) = x² fxx = 2x x² fzz z, fxx 1 degiocat (1) /egglooal (i)), where degglobat (i) the degree of node the whole graph and degrocat(1) the degree of node in the subgraph induced by (VB).
B COMPUTATIONAL COMPLEXITY
We summarize the computational complexity in Table 5 where mmax is the maximum of neighbor- hoods, L is the number of message passing layers, VB is set of nodes in sampled is the embedding dimension, V is the set of nodes in the whole graph, and E is the set of edges in the whole graph. As GD, backward SGD, CLUSTER, GAS, and LMC share the same memory complexity of parameters ((t), we omit in Table 5
Table 5: Time and memory complexity per gradient update of message passing based GNNs (e.g.
GCN (Kipf & Welling 2017) and GCNII (Chen et al. 2020
Method
Time
Memory
GD and backward SGD
(LL(EEdd + ||d3))
VlL)
CLUSTER (Chiang et al. 2019)
O (T Vgld + 1/ (2))
(T.
GAS (Fey et al. 2021
((L (umax VB + VV8 (d))
(n L Ve
LMC
V/ / OLL(mmax
V/ ld
O O L Vsld)
C ADDITIONAL RELATED WORK
C.I MAIN DIFFERENCES BETWEEN LMC AND GRAPHEM
First, LMC focuses on the convergence of subgraph- wise sampling methods, which is orthog- onal to the idea of GraphFM-OB alleviate the staleness problem of historical values. The
14

---

Published as a conference paper at ICLR 2023
advanced approach to alleviating the staleness problem of historical values can further improve the performance of LMC and it is easy to establish provable convergence by the extension of LMC.
Second, LMC uses nodes in both mini batches and their 1-hop neighbors compute incomplete up-to-date messages. In contrast, GraphFM-O05 only uses nodes in the mini-batee bani-batches. For the nodes whose neighbors are contained in the union of the nodes in mini-batches and their 1-hop neighbors, the aggregation results of LMC are exact, while those GraphFM-OB are not.
mini-batches
Third, by noticing that aggregation results are biased and the I/O bottleneck for the history ac- cess, LMC does not update the historical values in the storage for nodes outside the mini-batches, However, GraphFM-OB updates them based on the aggregation results.
D DETAILED PROOFS
Notations, Unless otherwise specified, C and C' with any superscript or subscript denotes constants. We denote the learning rate by 77.
In this section, we suppose that Assumption holds.
D.1 PROOF OF THEOREM 1 UNBIASED MINI-BATCH GRADIENTS OF BACKWARD SGD
In this subsection, we give the proof of Theorem which shows that the mini-batch gradients computed by backward SGD unbiased.
Proof. As Vin VB8 O Vr. is uniformly sampled from V,,, the expectation of g.: (VB) is
(Vg)( = E M2 es eyEVLs
Vill (hj. U₁)1
= (le Vz)l
-wL.
As the subgraph VB is uniformly sampled from V, the expectation of go: (VB) is
|
E Elgo (Vs))
E
1-1 ) x5)) V'll
VB
IVITE V oi uge (h
m )i V
-MM|n Volugl (h m / X,) V
VVEV
Σ V Up (h i-1 - X.
"YEV
Volh, [T)
D.2 DIFFERENCES BETWEEN EXACT VALUES AT ADIACENT ITERATIONS
We first show that the differences between the exact values of the same layer in two adjacent itera- tions can be bounded by setting a proper learning rate.
Lemma 1. Suppose that Assumption holds. Given an L-layer GNN, for any > O. by letting
7 5 [2
<
we have
H || <e, VI E [4], k EN
15

---

Published as a conference paper at ICLR 2023
Proof. Since 1 S (27)=a ((27)=-16. we have
H +++
H 1
[ - Soru (X)lle
1 x0100 - -01.41
> Soi ||1
7GE
-27)4-11
(27)1-11
Then, because
S (27)-6 <
(27)2 10 we have
2
222 = || (H!) - S0z. |
< || (Hl - -oz (HI++))] Ir + Io (HLtt)) - S0a (H)
- 7 711022-11 022 + HH*
E
- G + 2(27) L-
8
+ 2(2
2(27))-2
8
(27)
And so on, we have
h+1 H < (27)1--1)
4le [L], & E e
Since (27) >
we have
H 1811 H <E, V [4] KN..
Lemma 2. Suppose that Assumption
hwids. Given an L-layer GNN, for any > 0, by letting
n I (2 SE
we have
|V 1i,+i-vibll <,, VI [L], e
Proof. Since 1) S (27)4-16 < " have
| v1- || = ||0AL (V doc. (VHC)
I > 1- 1 -
I > ol l|n
7G
(2x)
127)
16

---

Published as a conference paper at ICLR 2023
Then, because (27)
(24) 26 have
|VL-2 VL-2. ||
10ge 1 (VL-1
0g 1.2 (VL-LK))
S logc 11 (VL-1A++)) - 00 1. (VL-1 3|1
+ 10g (on0--1((VVV- (V4-18+1) - 11 (VL
1,,41 -1 + V -V-LLMl
7Gn + 2(27))1-3
E
+
2(2
2(27)
(2-)2-3'
And so on, we have
| -1-11-1 (27)1-1) 4E [4], k E
Since (27)²=1 > 1, we have
|| - <E, Vle [4,,
D.3 HISTORICAL VALUES AND TEMPORARY VALUES
Suppose that we uniformly sample a mini-batch V C at the k-th iteration and [V]] = S. For the simplicity of notations, denote the temporary node embeddings and auxiliary variables in the I-th layer by H and Vilk: respectively, where
6
L kk
N(V \ Vg.
H
otherwise,
and
N( \ Vg.
ViL
hewwrisse.
We abbreviate the process that LMC updates the node embeddings and auxiliary variables of V in the I-th layer at the k-th iteration as
L. H [Sor (A (H'11,)) Myg.
v/
(H (A
VA
For each vi E V the update process of ;s in the I-th layer at the k-th iteration can be expressed by
h k = fark -1
= Øer 1.k (V)+
where fark, and 0attLA, are the components for node u; of for. and dertL,, respectivel.
D.3.1 CONVEX COMBINATION COFFFICIENTS
We first focus convex combination coefficients 3r. [n]. For the simplicity of analysis, assume 8; = 3 for E [i]. The analysis of the case where (3,) are different from each other is the same.
17

---

Published as a conference paper at ICLR 2023
Lemma 3. Suppose that Assumption
7 holds. For any 0, by letting
B s
VIE [4], i E [n].
2G'
we have
[
H S
H 1.ke
H VI [4], k KN..
Proof. Since
H
11--31 3)H 1.
3H. we have
H
H
II(1 B)
B - (1 -1-13)
(1 B) H
H k |F + B|| k H|*
H
H + 23G.
Hence letting 3 < 2G
leads to
H H H
H +
Lemma 4, Suppose that Assumption hhols. For any e > 0, by letting
B 2 2G
Vle [4] E [n].
we have
Vl r| < V - vir
Proof. Since H
(1 3 H 1.
+ +H 1.
we have
H k = [ - H) *
+ HH I.k
(1 H + 3H MIl
$ (1 - 3) H k
H
F i H
k
1 1 +
Hence letting 3 & leads to
20
H
H
tE.
D.3.2 APPROXIMATION ERRORS OF HISTORICAL VALUES
Next, we focus on the approximation errors historical node embeddings and auxiliary variables
j.l = [EIIIH* H1:) 1/ . [L],
aL. = [EI] - v((
IE [T.
Lemma 5. For an L-layer GNN, suppose that Assumption holds. Besides, we suppose that
1. (d) is bounded by G >> 1, 1 (z).
2. there exists N E No such that
L.k H
H + N vi [L] & E
H k
H
H
N VkeN.
18

---

Published as a conference paper at ICLR 2023
then there exist constants C C222, and C,3 that do not depend on k,1, N, and n, such that
C.33
(dh & C O
VIE kEN,
N
where p 8-8 <1, [V1 and S is number of sampled nodes at each iteration.
Proof. We have
12
H
+1,+1
H
[1:]]
1+1,41
E
h
E
[|
H (
fotti,+1, H )|
w
1+1,
fottLAt,, 1H
8y V
E
1o 1o (fthtt) , (H ||
(
11
S
1+1. h
Sottie (+)++))))
n
1=1
5
n1
E k-
(ALtt1)
solt1. (H |1
11
1=1
S
E Bi|b,
fectINt1, ( (H
About the first term, for l 2 1, we have
Bll (H
( (a,
$ ~ 11
H
[]:]
$ >>-E[(
k+1
H l.+
|| + 1
N )
< 2
H !-/-
H
H
||% +
2x2
N
2y2
2- (d
+
No.
For / 0, we have
Egll ( (ft - , (HL
fol (H 0 f0r.4 s 1 ||
[al (X) (x)n1,,;())111
O.
19

---

Published as a conference paper at ICLR 2023
About the second term, for / 2 1, we have
B|[lh 11
< Biilh; 1+1,k - h.
h b Soit14+1, (H+++)))
s Biilh; 1+1,2
- h
||:.1
+ IB[l + 10 (HL
+ (
1+1.8
h
+ h b forrae ( (H(
$ B|
1+,
h
1|21
+ +
1+
(H ; fouLAss, (HH 1
+ (b;
1-1,k h
h/+1/
b/+L fo (H))++))]]
h
11
+ 2 h + for 1.k 1 (H + 2E]1 fa ( - for 10r1,112, ( (H+*+))13
+ 4GGE|Ib
1-1,
So (H [1)
11
- h 11
+ 22 0 2 + H 11
+ 44G7B1104411 g/+1++11111111111111111111 + || l: H ||,|
< BBllh,
1+1. h
1.+111111 11: + G2 + 40- + 272
No + 4G-
N
1 20 2)n + 2x + 2G)
N3
For 1 = O, we have
B 1+1
sott (HH (H!
< Bliih, 1+1,
h
141 h b1 Sottia+ ; (H (H+++)))
< BlIlh; 1+1,
h [
+ 1Bllbb +11kk (H
+ k
1.1.
h
++1 h
1,
< BlIlh, 1+1,
h
11
+ +
fott1e41,
(HH + fottie a (H sott (Hb++)))
+ kh
(1,,
h1
1+1, foetie (H4
S B||[h, 1+1,2 - h 11
+ 23 [|| 1+1,
for
>1 + 2B for na (H. 1o (H*++)))
+ +4GG|[[h
S (H(++))|[]]
< B[[[h; 1+1,8
+ 27 2 231110 +1 - 0 + 4G 01+1,++1|||
< B[[lh 1+1,8 - ||] + 2- 2²22 + 40
< B|]l
141. - h
++1. 12 20 /0 2)n + 40
Hence we have
( <
(n- S) Sn
11 + 2(n S)1(+
+ 2
0.
1 0,
kukkktk + Amvlo+t
12 1.
20

---

Published as a conference paper at ICLR 2023
Let n-8 < 1. For I 0, we have
(dh (dh 2(n -5-7(7 2)
I p((() 2(n - 5)-(1= 22)
1-p
1-p
2(n- + 2)
p² ((d
1 1-p p
$ ...
s ((d) - 5h17 + 2)G²
1-p
S SpG,
which leads
( =2 2(n +
7 = P.G.
1-p
Then, for we have
C2
(d
22 & p(d + C2.1 + C2.22 +
N
where 12 C2,2, and C2.3 are all constants. Hence we have
(dr 2 C2 + C222 +
C2.3 Nº
C2,11 C2.22
C2.
S p(
Nº.
1-
1-p
C2,17 + C22pº & +
C2.3 N
< 50 ((ob.))2-
1- p
s P'
which leads to
C2,3
(d 12 & C2 + Capp* +
N
And so there exist constants C² C222, and C¹,s that are independent with 1), K., N such that
Ch VL KEN.
(d s C,,,"' n Ch
Lemma 6. For L-layer GNN, suppose that Assumption hoold. Besides, suppose that
1. (d, y bounded by V [L].
2. there exists N E N' such that
VV vlk
I
v.k
|F
VI WE
N
IVLK
VIA- |F
NO VkEN.
then there exist constants Ch C₂ and C.,3 that are independent with k, I, e", and v, such that
Cha
(dl.tly < C. Ch
VLE [L], KEN,
N
where p = 2-8 n = VV. and S is number of sampled nodes at each iteration.
Proof. Similar the proof of Lemma
21

---

Published as a conference paper at ICLR 2023
D.4 PROOF OF THEOREM 2 APPROXIMATION ERRORS OF HINI-BATCH GRADIENTS
In this subsection, we focus on the mini-batch gradients computed by LMC, i.e.,
1
Bi (w c VBB
V Vulla (h2, (h).Ws) yj)
IVEE
and
Ko (0
1
Σ EVV
(Voruora (hy (h/
1-1,6
1-1k ((e,)) x5)) v LE [4].
where V/8 is the sampled mini-batch and V is the corresponding labeled node set at the k-th iteration. We denote the mini-batch gradients computed by backward SGD by
1
gu (w ; VB8 =
Vuluk (hf U3)
IV
and
Sei (6 ;18)
M
Σ
(-1k (V (orrugru (b)-t m)(s)) (1))))()))))) v/a. LE [L].
1-1k xz)
D
Below, omit the sampled subgraph V and simply write the mini-batch gradients ga. (w*).
go: (0l.k,, ). (wr*,, and ga ()l.k). The approximation errors of gradients are denoted by
k A (w( V ((w*)
and
A got (BI-)) Vol
We restate Theorem 2 as follows.
Theorem 4. For any k N and i [L], the expectations of | A. (. V C=
and || A k 11 a /o (OL.)) V ((0L-))11 have the bias-variance decomposition
[ (Bias E. ( (w) + Var(g (w*)
ge (Bias Be (Bl + (ar (0**)),
where
Bias (g (w²)) (B - gm (w )12)
Var(g (w*) Ev (w*) V -w ) >12)
Bias (B: (0L*a) = (E(llgo (0L-A) - 80 ((al(t)
Var(go (01A*)) Blllgo (0-A)- V Vol ((B
Suppose that Assumption 7 holds, then with n OEe2) and 3: O i E [n], there exist C
and p (0, 1) such that for any K E 14* and l E [L], the bias terms can be bounded as
Bias(E. (w=)) < Ce Cp Bias (B)*)) < CE + Cp
Hence we have
B & w [2]] Ce Cp 1-1
+ Var(g (ur(g((w*)) )w² 1
B||| K 112] < Ce + Cp+Cp - Var(go: )
Lemma 7. Suppose that Assumption 7 holds. For any K. E N², the difference between (w and gi (w*)) can be bounded as
(w gi (wo S H H
22

---

Published as a conference paper at ICLR 2023
Proof. We have
(w*)
Bw
1
Σ
Vulla (h, .91) V woluh (hgi l1))ll2
1
Σ
VV
Vuelu (b, .4)) - V wel (h3. ,5)
2 LEVE
7
Σ
h
1 112
0 LEVE
7
Σ
L.k
H
1
IVE
L.
H
|
H
L.k
H
Lemma 8. Suppose that Assumption 7 holds. For any & E N and I [L]. the difference between ge (f and gai (B%-)) can be bounded as
lo (B) Bo: (8. 12 MIGIV
vl MI H H Ip.
Proof. As AAaBBble S |a B /////bl2. we can bound by
|| (0L-A) Bo (0%.k) )l2
go (OL#)
Bar (0%.)))12
V
Σ
(VorugL (h)
1,
m
1-1,6
V
((Vouugu (b/- m 1-1,k
N x,)) V/ 112
< | max
Vor ugr. (h,
1-1k
(x,,) x5)
1-1,
3
(Vorugl:(h)
mx(e)))))))
1-1 x5)) V//0/22
< | max [ Ugt h EVV
1,k
m 1-1k
X²) |||||||
V k
V/
N(v,))
Var
( xy) V gi Ugr. (h)-
1-1,6
1,k mitt +
< | &
-v*
M
H H
Lemma 9. For an I-layer ConvGNN, suppose that Assumption holds. For any N E N", by letting
1
n 5
O
G
N3
N
and
B. 2G N
0
i In].
N
there exists G2,, > 0 and p e (0, 1) such that for any lo E No we have
[ & m [12] = (Bias(B. (10* 1))² + Var(g. )): (Bias (B (0)+)))) Var(go (0%.)))
B k
where
Var(gw [E (w - V Cw > [12]] Bias( (w ()) [ ow (w= (w (11))
Var(go (OL-k)
Eillgo (0/.k) V C(0 )1ā)
(ia (0%+k) (Bill (0/.h) go C( (11))
23

---

Published as a conference paper at ICLR 2023
and
Bias (Bu(()))) (2 + tp + 1
N3 )
1
Bias (Ba (0)+)) < (n + +p=
Na
Proof. By Lemmas
and 2 we know that
1
H k- H
1/ [4], KEN'
N
| - vl*
VL [4], KEN.
N
By Lemmas
3 and
we know that for any k E No and I E [L] we have
1
H H
H
H le +
N
and
I ville S
vlbll
N
Thus, by Lemmas 5 and 6 we know that there exist C, C2 and C.,3 that do not depend on k N such that for vl E [Z] and l E N hold
C²a3
t S V C. C. 22
N
$ Vi,, + V2,0000 + VC N
and
Ch
deth 1 V C. +
N
Vornn + VO2.20 t-1 + V²,, N
We can decompose
| 112 as
|| l1
(ww" vn 112
(w=" gm (w²) gv((w - V V(
= (ww* Sw Bw (w + 1|g (w²) - V ww 112
+ 2 (. gw (wx), (w V ((w
We take expectation of both sides of the above expression, leading to
E E (Bias (w²))))² (w
(16)
where
Bias (wx = (wllii(c gw (w )l1)) Var(g.. (w²) BBllgw(w - V C(w )113]
E (uw -B (w g. v. 0.
24

---

Published as a conference paper at ICLR 2023
By Lemma 7 we can bound the bias term
Bias(g (w)))
(Ei) gu (w*) gu (w #
S ( I - -H $
dh
S 7( / C²,11² + v C22 t-2
VV N
+
s (1) + E-1 +
(17)
N3
where G2,1 y max
CC,,, VC,2. v CCaat.
Similar to Eq. equation
16
we can decompose E|| / [2 as
[ (Bias (0% ))² + Var(ge (0/.a)),
where
Bias Bo (0**)) (Bl Bo (01.1) Soi go: 1/4
Var(go: go: (0--1)) = Eollgo (0/.t) - Vo ()))
By Lemma we can bound the bias term as
Bias Co (0l = BBl - go )111) 7
s (21/GG<E|I Vl. |1211
+ ?
H H
< f2lyGGd + 2 V
s G2a(n² + +p t + N
(18)
where G2 = V2//GG(1 + 7) max( /o V. /Cas).
Let G2,- = max 22 then we have
Bias Bias(@n(w"))) S (1 +p 1
+ 1
N
Bias (0)+h) < (n (n² + +p=
1-1 +
N
By letting = = + and C' = 2G2,,, we have N3
(B.n s C8 + =
Bias (Ba (01-)) < CE Cp 1_d =
which leads to
(BIJ [[]
(13)
< ((Bias (g. ( ())2 + Var(g (. (w) 3
< Bias @g (w* + Var @g ()
< Cs + Cp 1 + Var (w ))
25

---

Published as a conference paper at ICLR 2023
and
B Blll [12] - (B k gl 121)
s (Bias Bo (0)+ + Var(go (0)
- Bias (go: (0) + Var (0)
I Ce + Cp =p=++ + Var(ga (Bl.
Theorem and Theorem 4 follow immediately.
D.5 PROOF OF THEBREM CONVERGENCE GUARANTEES
In this subsection, we give the convergence guarantees of LMC. We first give sufficient conditions for convergence.
Lemma 10. Suppose that function f RR + T. is continuously differentiable. Consider opti- mization algorithm with any bounded initialization x! and an update rule the form of
x++1= x ndd(x))
where yj > 0 is the learning rate and ddxxt) ) the estimated gradient that can be seen as a stochastic vector depending on x² Let the estimation error of the gradient be A d(x*)- [x**). Suppose that
1. the optimal value f = = fxx is bounded;
2. the gradient of f is L-ipschitzz i.e.,
IVf(y) - fx()))l2 S rlly x112, Vx.y ER"
3. there exists Go > 0 that does not depend on v such that
B < Go. YKEN 4. there exists N E No and E (0, 1) that do not depend on such that
E [ A")] S Go(n + +p N )
VkEN
where Gu is the same constant that in Condition
then by letting = min , 1 }. we have
NE
E Vf 2(f(x)) f+ Go)
GGo
Go
0
N
N
N(1
vp)
N 7
where chosen uniformly from [N].
Proof. As the gradient of f is 7-Lipschitz, we have
f(y) f(x) Vf(z) dz
-x() + {' (Vf(x t(y x)),y x) dt
=f(x) + (Vf(x), - -x)+ [ [V](x +1y+ - v/(xx) x)
$ fx() + (Vf(x), x) + [ [V + t(y x)) v/(x)llalyy
- x dt
5x(x) (V)(x), x) f 7lly x1 dt
/x( + (V/()),) -x)+
Ily -x122
2
26

---

Published as a conference paper at ICLR 2023
Then, we have
f(x
S 51(x)) + (VI((*)), x++ x++x1 -x² + -
31x xx xx113
2
- -1(x*) - (Vf(x) + n²y
)13
2
n²7 (1 * 1/ + [V 112 + 2(A vf((x)))
= =f(x²) (V 7/ (x(* 112 +
2
= =1(x²) - (11 - ()))) 17(1
777
|[V )1
+
12
2
2
By taking expectation of both sides, we have
[[
12 " 113].
< [x] - my(1 (VV()))( )+1 -1 Th
><) (11 +
2
By summing up the above inequalities for k [N] and dividing both sides by Ni )), ), we have
Σx f 1|
N
f(*2) - )
T/
Σ
E
I
(1-77)
E
[V A
N1 2)
2 77
N
77)
N
1(x2) - + N1 )
117
Σ
1
E
A
EN
[V ) A A
2 nyy
N
N
where the second inequality comes from ryy > 0 and f(xx) 2 fr, tions, we have
According to the above condi-
EM E |131
f(x²) ft
77
N
17 +
p
k-1
Go
<
+
Go + Go
N11(1 47)
2 m
N
N
k=
f(x!) - 8³
Go 8
Go
Ny(11 -
+
m
Go + 17 +n +
N
p
N
f(x') f³
+
n
Go + n G +
Go
+
Go
Ny(1 my)
2 - m
N(1 - vp)
N
Notice that
Ck=l E [[(>|(
E V || = [x|EI|[V((> R]
where R is uniformly chosen from [N], hence have
E
[ )1 f(x²) - 5r +
my
Go + +
Go
Go
Nn )
2 1
N(1
vp)
N1
By letting 77 = m (,, N J. we have
B||VF((* |1 2(f(x)) - )() Go
Go
Go
G
+
No
N N
N(1 vp)
N
2(s(xt)
+ Go)
Go
Go
+
N +
N
N(1 vp)
1
0
N
27

---

Published as a conference paper at ICLR 2023
Given L-layer GNN, forllowing (Chen et al. 2018a), we directly assume that:
1. the optimal value
C inf w w,0' 00.,0%
is bounded by G > 1;
2. the gradients of L with respect to parameters w and 0', i.e,
V vu V C
are 7-I.ipschitz for AI E [T.].
To show the convergence of LMC by Lemma
10 suffices to show that
3. there exists G1 0 that does not depend on 77 such that
B||l
A 121 S G1, A E";
B
A | S Gi, VI [4], KEN;
4. for any E N", there exist G2 and p E (0, 1) such that
E C, - G2 + - + +
1
AKEN',
N
[V S
G1 + -
VI [L), k E N"
by letting
7. (G N
0
N
and
B 5
= 0 No
i [n].
2G No
Lemma 11. Suppose that Assumption holds, then
B A
[
< G1 4G. VKEN",
G1 4G², VLE (L), E
Proof. We have
=|| = (w (w² - V V. ((w*)) ||
2 a.. (w (w0) E V 1())
$ 4G²
and
|| 12
E
E
/ (BL.))
V C(BLk)))
$ 2 B (BL+ + E(l L(Bl+>
< 4G
Lemma 12. Suppose that Assumption holds. For any N N", there exist G2 0 and (0,1) such that
[ C, اللل < G2(n +
VkEN',
N
o اللل < Gz(n
+
VlE E
N
28

---

Published as a conference paper at ICLR 2023
by letting
1
17
(2 N
=0(
N
and
B. 5
2G N = 0
i i [n].
N
Proof. By Eqs.
17 and
18 we know that there exists G2,, such that for any h E No we have
Bw [la - (1 (w*) Bw(
I G2 (n² + 1 + N
1
and
B Bor (0'+h) - Bar (O%.)) - (Blll (0%.k) - 8oi (0 (0*)
22 (n} + =11 1
N )
where p n-8 < is constant. Hence
EKV c,
[K[V C.C, gw V v(w
[B[[ w. (w()) ) - Bu (w=))]
< E 222
Sw (w*)
GIElIl (w.) (m((w)lll))
/ + $ G2(n +
N
and
B[(V of C, |
B[(V L, Ro (01.)) Vo
E[(V L, Bo (01.K) (B(
[||] V L1 | (0Lh) - Bor (())
GE Bo (g%.k)
go (0(-)))la)
< G2(11 + k-
+
N!
where G2 GG2,..
According to Lemmas
11 and 12 the conditions Lemma 10 hold. By letting
2(f(x²) ft + Go)
Goo
Go
+
v
= O
N
N
N(1
N
Theorem 3 follows immediately.
E MORE EXPERIMENTS
E.1 PERFORMANCE SMALL DATASETS
Figure reports the convergence curves GD, GAS, and LMC for GCN on three small datasets, i.e.. Cora, Citeseer, and PubMed from Planetoid Yang et al., 2016). LMC faster than GAS, especially on the CiteSeer and PubMed datasets. Notably, the key bottleneck on the small datasets is graph sampling rather than forward and backward passes. Thus, GD is faster than GAS and LMC, as avoids graph sampling by directly using the whole graph.
29

---

Published as a conference paper at ICLR 2023
Cora
CiteSeer
PubMed
BAX
0.84
0.80
Test/Acc
Test/Acc
0.70
Test/Acc
0.78
0.80
0.76
0.65
0.76
0.6g
BB.
Runtime
Runtime (s)
Runtime (s)
Figure 5: Testing accuracy w.r.t. runtimes (8).
E.2 COMPARISON IN TERMS OF TRAINING TIME PER EPOCH
We evaluate the training time per epoch of CLUSTER, GAS, FM, and LMC in Table 6 Compared with GAS, LMC additionally accesses historical auxiliary variables. Inspired by GAS (Fey et al. 202T, we use the concurrent mini-batch execution asynchronously access historical auxiliary variables. Moreover, from the convergence analysis of LMC, we can sample clusters to construct fixed subgraphs at preprocessing step (Line 2 Algorithm rather than sample clusters to construct various subgraphs at each training step This further avoids sampling costs. Finally, the training time per epoch of LMC is comparable with GAS. CLUSTER is slower than GAS and LMC, as prunes edges in forward passes, introducing additional normalization operation for the adjacency matrix of the sampled subgraph by [Avgls// /dgvv, (d)degv (j), where degvg (t) is the degree in the sampled subgraph rather than the whole graph. The normalized adjacency matrix is difficult to store and reuse, the sampled subgraph may be different. FM is slower than other methods, they additionally update historical embeddings in the storage for the nodes outside the mini-bac batches.
Table 6: Training time (s) per epoch of CLUSTER, GAS, FM, and LMC.
Dataset GNN
CLUSTER
GAS
FM
LMC
Ogbn-arxiv & GCN
0.51
0.46
0.75
0.45
FLICKR & GCN
0.33
0.29
0.45
0.26
REDDIT & GCN
2.16
2.11
5.67
2.28
PPI & GCN
0.84
0.61
0.78
0.62
Ogbn-arxiv & GCNII
0.92
1.02
0.91
FLICKR & GCNII
1.32
1.44
1.33
REDDIT GCNII
4.47
7.89
4.71
& GCNII
4.61
5.38
4.77
"CLUSTER-GCY proposes sample clusters construct various subgraphs each training step and LMC follows it. subgraph-wij wise sampling method prunes an edge the current step, GNN may observe the pruned edge at the next step by resampling subgraphs. This avoids GNN overlitting the graph which drops some important edges as shown in Section 3.2 in (Chiang et al. 2019) (we also observe that GAS achieves the accuracy of 71.5% and 71. 11.1% % under stochastic subgraph partition and fixed subgraph partition respectively on the Oghn-arxiv dataset).
30

---

Published as a conference paper at ICLR 2023
E.3 COMPARISON TERMS OF MEMORY UNDER DIFFERENT BATCH SIZES
In Table we report the GPU memory consumption, and the proportion of reserved messages Ei-1 [Avi |lo/|lAA| in forward and backward passes for GCN, where A the adjacency matrix of full-batch GCN, Aats is the adjacency matrix used in subgraph-wise method alg (e.g., CLUSTER, GAS, and LMC), and - llo denotes the & fo-norm As shown in Table 7 LMC makes full use of all sampled nodes in both forward and backward passes, which is the same full-batch GD. Default indicates the default batch size used in the codes and toolkits of GAS (Fey et al. 2021
Table 7: GPU memory consumption (MB) and the proportion of reserved messages (%) in forward and backward passes of GD, CLUSTER, GAS, and LMC for training GCN. Default indicates the default batch size used in the codes and toolkits of GAS (Fey et al. 2021).
Batch size
Methods
Ogbn-arxiv
FLICKR
REDDIT
PPI
Full-batch GD
681/100%/1000%
411/100%//009
2067/100%//0005
605/100% /11/00%%%/0%%
CLUSTER
177/ 67% 67%
138/ 57% 57%
428/ 35% 35%
189/ 90% 90%
GAS
67% 178/100%
168/100%/
482/100%
35%
190/100%
90%
LMC
207/100%6/10%%
177/100%//00%%
610/100%%/1005/
197/100%/1009%
CLUSTER
424/ 83% 83%
310/ 77% 77%
1193/ 65% 65%
212/ 91 91%
Default
GAS
452/100% 83%
375/100% 77%
1508/100% 65%
214/100% 91%
LMC
557/100%//100%
376/100%//100%
1829/100%//000%
267/100%/100
E.4 ABLATION ABOUT B
As shown in Section A.4 3; score(i)a in LMC. We report the prediction performance under
a E {0.0, 0.2, 0.4, 0.6, 0.8, 1.0] and score E {f(z) = f(z) = 2z f() x, f(x = 1; deglocal (i) (eggtbbas in Tables and g respectively. When exploring the effect of specific
parameter, we fix the other hhper-paramedee parameters as their best values. Notably, a = implies that LMC directly uses the historical values affordable without alleviating their staleness, which is the same as that in GAS. Under large batch sizes, LMC achieves the best performance with large B, 1, large batch sizes improve the quality of the incomplete up-to-date messages. Under small batch sizes, LMC achieves the best performance with small B 0. 0.4score2--pt (i), as small learning rates alleviate the staleness of the historical values.
Table 8: Prediction performance under different a on the Ogbn-arxiv dataset.
Batch Sizes
learning rates
Qt
0.0
0.2
0.4
0.6
0.8
1.0
le-4
71.34
71.39
71.65
71.31
70.86
70.57
40
1e-2
69.85
69.12
69.89
69.61
69.82
71.44
Table 9: Prediction performance under different score the Ogbn-arxiv dataset.
Batch Sizes
learning f(z) 2n x²
score
f(x) =1
f(x) = x²
f(x) =x f(x) sin(z)
le-4
71.35
70.84
71.32 69.91
71.30 70.03
71.13
40
lc-2
67.59
71.44
70.32
F POTENTIAL SOCIETAL IMPACTS
In this paper, propose novel and efficient subgraph-wise sampling method for the training of GNNs, i... LMC. This work is promising in many practical and important scenarios such as search engine, recommendation systems, biological networks, and molecular property prediction.
31

---

Published as a conference paper at ICLR 2023
Nonetheless, this work may have some potential risks. For example, using this work in search engine and recommendation systems to over-mine the behavior of users may cause undesirable privacy disclosure.
32


Reviews:
[{"review_id": "VlaFMEoSYmU", "reviewer": "Reviewer_7N9L", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This research proposes a subgraph sampling method(LMC) with provable convergence for graph neural networks. Training Graph neural networks suffer from neighbor explosion problems. Subgraph sampling methods apply to a wide range of GNN architectures by directly running GNNs on the subgraphs constructed by the sampled mini-batches and showed great empirical success in prior works, while inaccurate mini-batch gradients hurt the accuracy and performance of GNNs. The key idea of LMC is effective compensation in backward and forward passes, which computes accurate mini-batch gradients and thus accelerate convergence.", "summary_of_the_review": "This research proposes a subgraph sampling method(LMC) with provable convergence for graph neural networks.  The key idea of LMC is effective compensation in backward and forward passes, which computes accurate mini-batch gradients and thus accelerate convergence. Numeric experiments and theoretical analysis are great, while more explanations are needed for the difference and key development with the prior works.", "strength_and_weaknesses": "Strength:\n1. Key idea of effective compensation is great, and they explain their idea clearly.\n2. First subgraph sampling method with provable convergence for graph neural networks. Their theoretical analysis shows that mini-batch gradients are unbiased and their algorithm can converge to the stationary point of GNNs.\n3. Numeric experiments are sufficient, it's worth mentioning that the experiments on compensation terms are great.\n\nWeaknesses:\n1. Some typo, denote the j-th columns of A by $A_j$ not $A_i$, forward not froward.\n2. More explanations are needed for the difference of GAS and LMC, why more information keeping can get the algorithm more robust the the graph size. On some datasets, GAS performs better, why?   ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8ZkntwpW5TY", "reviewer": "Reviewer_LGPo", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposed a new subgraph sampling method: Local Message Compensation (LMC) for speeding up GNNs training. The general subgraph sampling method will dscard information outside the mini-batches, and thus brings in performance degradation and slow convergence. LMC deals with this issue by retrieving the discarded information in backward passes based on a message passing formulation of backward passes. This paper also provides convergence analysis. The experiment is promising and achieves good convergence speed and accuracy.  ", "summary_of_the_review": "The paper is in easy to understand and the proposed method is making sense and achieves good convergence. I am mostly concerning about the memory usage and space to maintain all the layers historical information. ", "strength_and_weaknesses": "Strength:\n\n1: A reasonable method for retrieval information outside the mini-batches. \n2: Providing convergence analysis. \n2: Comprehensive experiments show fast convergence.\n\nWeakness:\n\n1) One thing I am confused is that do you need to maintain the all the node embeddings for all the layers? If that is the case, what if the number of layer is too large, would it be OOM issue? Traditional subgraph sampling methods such as ClusterGCN does not need to main such embeddings for all the layers, as it is computed on-the-fly, and thus more memory efficient.\n\n2) how is the subgraph sampling method playing a role during the convergence? For example, what if using random partition vs metis?\n\n3) how is the per epoch time comparing with different methods? The result presented in the paper is mostly on total training time  (or total epochs ) vs accuracy or loss. It would interesting to see per epoch time as well. As I feel seems there are more variables needing to be updated from traditional subgraph sampling method, LMC will need more time per epoch.\n\n4) how the proposed method compared with GraphFM, which seems quite similar to the proposed method.\n\n5) also some ablation over the combination coefficients beta_i.\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4-_utS5IQo", "reviewer": "Reviewer_DdvT", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The authors proposed a novel subgraph-wise sampling method, Local Message Compensation(LMC), to accelerate the training of GNNs on large-scale graphs. They mainly focus on solving the neighbor explosion problem. Their main concern is finding a solution to the neighbor explosion issue. I think their research has a significant impact on the advancement of GNNs.", "summary_of_the_review": "Even though their work aids in the development of GNNs, these are insufficient for being strongly accepted.", "strength_and_weaknesses": "Strength:\n(1) Their approach helps to avoid the neighbor explosion problem to a certain extent.\n(2) The convergence of their method is provable.\n\nWeaknesses:\n1. one typo is that in table 1 GraphSAINT's 97.0 reaches the best.\n2. It seems to me that the authors claim that their method is more efficient than other methods, which means the \"proportion of reserved messages (%) in forward and backward passes\" based on their response, but in terms of memory in Table 2, for example, 1892 for LMC is about 2 times more than 1193 for CLUSTER and 557 is about 1.3 times more than 424, which may confuse others in terms of memory efficiency. It would be clearer to modify Table 2 and add \"proportion of reserved messages (%) in forward and backward passes\" to it.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3_l8B1NFKdy", "reviewer": "Reviewer_p4iX", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "In this work, the authors proposed a subgraph sampling training technique to solve the neighbor-exploding issues commonly seen in GNN training. The proposed methods named Local Message Compensation is claimed to debias the mini-batch gradient in a one-shot sampling setting hence accelerate convergence of training. Both theoretical and experimental results shows the efficacy of the proposed method. \n", "summary_of_the_review": "This work is a step forward from FAS. Though the two shares some similarity, the authors shown the improvements with both theoretical guarantee and detailed experiments. Overall I would recommend the paper to be accept. ", "strength_and_weaknesses": "Pros: \n- The paper is well-written with wide coverage of related works. \n- The deviate of backward SGD is intuitive and make it easy to follow the further approximation and compensation. \n- The claimed theorems and illustration in Figure 1 make the difference between LMC and other methods straightforward. \n- Space and time complexity analysis in Appendix adds more concrete supports to the efficiency of LMC\n- The uniform sampling and variance reduction technique using neighbors’ historic inform resemble some of the accelerated SGD method, and the authors provided theoretical rate of convergence in a similar way which is good to compare the ideal performance. \n- Complete and detailed experiments showing the convergence and efficiency of proposed method.  \n\nCons: \n- In equation (7), on the left hand side shouldn’t the gradient for \\theta^l depends on V_j^{l + 1} instead of V_j^l  (same for u_{\\theta}) ? \n- Does the classification performance of GAS and LMC always stay at the same level? What if you change a different base GNN (maybe less expressive and prone to error by gradient variance)? \n - Please add indicator (such as different font, color, etc) in the tables so that its easier to find the winner. \n- Is the method universally adapted? What is the performance when applying to small/medium size graph?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%