Learn Locally, Correct Globally: A Distributed Algorithm for Training Graph Neural Networks
Authors: Morteza Ramezani
Weilin Cong
Mehrdad Mahdavi
Mahmut Kandemir
Anand Sivasubramaniam
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
GNN
GCN
Distributed Training

Abstract: Despite the recent success of Graph Neural Networks (GNNs), training GNNs on large graphs remains challenging. The limited resource capacities of the existing servers, the dependency between nodes in a graph, and the privacy concern due to the centralized storage and model learning have spurred the need to design an effective distributed algorithm for GNN training. However, existing distributed GNN training methods impose either excessive communication costs or large memory overheads that hinders their scalability. To overcome these issues, we propose a communication-efficient distributed GNN training technique named $\text{\textit{Learn Locally, Correct Globally}}$ (LLCG). To reduce the communication and memory overhead, each local machine in LLCG first trains a GNN on its local data by ignoring the dependency between nodes among different machines, then sends the locally trained model to the server for periodic model averaging. However, ignoring node dependency could result in significant performance degradation. To solve the performance degradation, we propose to apply $\text{\textit{Global Server Corrections}}$ on the server to refine the locally learned models. We rigorously analyze the convergence of distributed methods  with periodic model averaging for training GNNs and show that naively applying periodic model averaging but ignoring the dependency between nodes will suffer from an irreducible residual error. However, this residual error can be eliminated  by utilizing the proposed global corrections to entail fast convergence rate. Extensive experiments on real-world datasets show that LLCG can significantly improve the efficiency without hurting the performance.

Published as a conference paper at ICLR 2022
LEARN LOCALLY, CORRECT GLOBALLY: A DISTRIBUTED ALGORITHM FOR TRAINING GRAPH NEURAL NETWORKS
Morteza Ramezani", Weilin Cong,, Mehrdad Mahdavi Mahmut T. Kandemir, Anand Sivasubramaniam Pennsylvania State University, University Park, PA 16802, USA mortezaêcse.c pau.edu, wxc2720psu. edu, mzm61 sesoiippsuuuull anandêcse edu kandemi r rêcse. wsw.ee...edd. psu.edu
ABSTRACT
Despite the recent success of Graph Neural Networks (GNNs), training GNNs on large graphs remains challenging. The limited resource capacities of the existing servers, the dependency between nodes in a graph, and the privacy concern due the centralized storage and model learning have spurred the need design effective distributed algorithm for GNN training. However, existing distributed GNN training methods impose either excessive communication costs or large memory overheads that hinders their scalability. To overcome these issues, we propose a communication -effciittttneeeiiienttt distributed GNN training technique named Learn Locally, Correct Globally (LLCG). To reduce the communication and mem- ory overhead, each local machine LLCG first trains a GNN on its local data by ignoring the dependency between nodes among different machines, then sends the locally trained model to the server for periodic model averaging. However, ignoring node dependency could result in significant performance degradation. To solve the performance degradation, we propose to apply Global Server Corrections on the server to refine the locally learned models. We rigorously analyze the convergence of distributed methods with periodic model averaging for training GNNs and show that naively applying periodic model averaging but ignoring the dependency be- tween nodes will suffer from an irreducible residual error. However, this residual error be eliminated by utilizing the proposed global corrections to entail fast convergence rate. Extensive experiments on real-world datasets show that LLCG can significantly improve the efficiency without hurting the performance.
INTRODUCTION
In recent years, Graph Neural Networks (GNNs) have achieved impressive results across numerous graph-based applications, including social networks (Hamilton et al., 2017; Deng et al., 2019), recommendation systems (Ying et al., 2018; Wang et al., 2018), and drug discovery (Fout al., 2017; Do al., 2019; Ghorbani et al., 2022; Faez et al., (021). Despite their recent success, effective training of GNNs on large-scale real-world graphs, such Face- book social network (Boldi & Vigna, 2004), remains challenging. Although several attempts have been made scale GNN training by sampling techniques (Hamilton et al., 2017; Zou et al., 2019; Zeng al., 2020; Chiang et al., 2019; Chen et al., 2018: Zhang et al., 2021; Ramezani et al., 2020), they are still inefficient for training on extremely large graphs, due the unique structure of GNNs and the limited memory capacity/bandwidth of current servers. One potential solution to tackle these limitations is employing distributed training with data parallelism, which have become almost de facto standard for fast and accurate training for natural language processing (Lin et al., 2021; ; Hard et al.,
Spoclup Menory
10
Memooy CBY
No. Machines
Figure 1: Comparison of the speedup and the memory con- sumption of distributed multi- machine training and central- ized single machine training the Reddit dataset.
"qqual Contribution.

---

Published as a conference paper at ICLR 2022
2018) and computer vision (Bonawitz et al., 2019; Konečný et al., 2018). For example, shown in Figure I, moving from single machine to multiple machines reduces the training time and alleviates the memory burden on each machine. Besides, scaling the training of GNNs with sampling techniques can result in privacy concerns: existing sampling-basee -based methods require centralized data storage and model learning, which could result in privacy concerns in real-world scenarios (Shin al., 2018; Wu et al., 2021). Fortunately. the privacy in distributed learning can be preserved by avoiding mutual access data between different local machines, and using only a trusted third party server to access the entire data.
Nonetheless, generalizing the existing data parallelism techniques of classical distributed train- ing to the graph domain is non-trivial which is mainly due to the dependency between nodes in a graph. For example, unlike solving image classification problems where images are mu- mually independent, such that we can divide the image dataset into several partitions without worrying about the dependency between images; GNNs are heavily relying on the information inherent to a node and its neighboring nodes. As a result, partitioning the graph leads to sub- graphs with edges spanning subgraphs (cul-edges), which will cause information loss and hin- der the performance of the model (Angerd et al., 2020). To cope with this problem, (Md al., 2021; Jiang & Rumi, 2021; Angerd et al., 2020) propose to transfer node features and (Zheng et al., 2020; Tripathy et al., 2020; Scardapane et al., 2020) propose to transfer both the node feature and its hidden embeddings between local machines, both of which can cause signifi- cant storage/communication overhead and privacy concerns (Shin al., 2018; Wu et al., 2021).
To better understand the challenge of distributed GNN training, we compare the validation Fl- score in Figure 2 (a) and the average data com- municated per round in Figure 2 (b) for two dif- ferent distributed GNN training methods on the Reddit t dataset. On the one hand, we can ob- serve that when ignoring the cut-edges, Parallel SGD with Periodic Averaging (PSGD-PA (Dean et al., 2012; Li et al., 2020b)) suffers from sig- nificant accuracy drop and cannot achieve the same accuracy as the single machine training, even by increasing the number of communica- tion. However, Global Graph Sampling (GGS) can successfully reach the baseline by consider- ing the cut-edges and allowing fcature transfer, at the cost of significant communication overhead, and potential violation of privacy.
Giaaa Vallatte
Fi Sone
0.75
Avse Zimmnictaal
10t
0.50
0.25
CCS
PSGAAAA
Bundit: Soars
0.00
20
60
PSODEA
COS
of Commoniocion
(a)
(b)
Figure 2: Comparison of (a) the validation F1-
score and (b) the average data communicated per round (in bytes and log-scale) for two differ- ent distributed GNN training settings, including Parallel SGD with Periodic Averaging (PSGD- PA) where the cut-edges are ignored and only the model parameters are transferred and Global Graph Sampling (GGS), where the cut-edges are considered and the node features of the cut-edges are transferred to the corresponding local ma- chine, on the Reddit dataset using 8 machines.
In this paper, we propose a communication-effin Locally, Correct Globally (LLCG). To reduce the communication overhead, inspired by the recent success of the distributed optimization with periodic averaging (Stich, 2019; Yu et al., 2019), we propose Local Training with Periodic Averaging: where each local machine first locally trains GNN model by ignoring the cut-edges, then sends the trained model to the server for periodic model averaging, and receive the averaged model from server to continue the training. By doing so we eliminate the features exchange phase between server and local machines, but it can result in a significant performance degradation due to the lack of the global graph structure and the dependency between nodes among different machines. To compensate for this error, we propose a Global Server Correction scheme to take advantage of the available global graph structure on the server and refine the averaged locally learned models before sending it back to each local machine. Notice that without Global Server Correction, LLCG is similar to PSGD-PA as introduced in Figure 2.
distributed GNN training method, called Learn
To get deeper understanding on the necessity of Global Server Correction, we provide the first theoretical analysis on the convergence of distributed training for GNNs with periodic averaging. In particular, we show that solely averaging the local machine models and ignoring the global graph structure will suffer from an irreducible residual error, which provides sufficient explanation on why Parallel SGD with Periodic Averaging can never achieve the same performance as the model trained on a single machine in Figure 2 (a). Then, we theoretically analyze the convergence of our proposal LLCG. We show that by carefully choosing the number of global correction steps,
2

---

Published as a conference paper at ICLR 2022
LLCG overcome the aforementioned residual error and enjoys (L/VPT)) convergence rate with P local machines and T iterations of gradient updates, which matches the rate of (Yu et al., 2019) a general (not specific for GNN training) non-convex optimization setting. Finally, conduct comprehensive evaluations on real-world graph datasets with ablation study to validate the effectiveness of LLCG and its improvements over the existing distributed methods.
Related works. Recently, several attempts have been made on distributed GNN training. According to how they deal with the input/hidden feature of nodes that are associated with the cut-edges (i.e., the edges spanning subgraphs of each local machine), existing methods can be classified into two main categories: (1) Input feature only comnunication based methods: In these methods, each local machine receives the imput features of all nodes required for the gradient computation from other machines, and trains individually. However, since the number of required nodes grows exponentially with the number of layers, these methods suffer from a significant communication and storage overhead. To alleviate these issues, (Md et al., 2021) proposes to split the original graph using a min-cut graph partition algorithm that can minimize the number of cut-edges. (Jiang & Rumi, 2021) proposes to use importance sampling to assign nodes on the local machine with a higher probability. (Angerd et al., 2020) proposes sample and save small subgraph from other local machines as an approximation of the original graph structure. Nonetheless, these methods are limited to a very shallow GNN structure and suffer from significant performance degradation when the original graph is dense. (2) Inpul and hidden hiddenfeature communication--eee based methody: These methods propose to communicate hidden features in addition to the input node features. Although these methods reduce the number of transferred bytes during each communication round (due to the smaller size of hidden embedding and less required nodes features), the number of communication rounds grows linearly as the number of layers, and are prone to more communication delay. To address these issues, in addition to optimal partitioning of the graph, (Zheng et al., 2020) proposes to use sparse embedding to reduce the number of bytes to communicate and (Tripathy et al., 2020) proposes several graph partitioning techniques to diminish the communication overhead.
2 BACKGROUND AND PROBLEM FORMULATION
In this section, start by describing Graph Convolutional Network (GCN) and its training algorithm on a single machine, then formulate the problem of distributed GCN training. Note that we use GCN with mean aggregation for simplicity, however, our discussion is also applicable to other GNN architectures, such as SAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018), ResGCN (Li al., 2019) and APPNP (Klicpera et al., 2019).
Training GCN on a single machine. Here, we consider the semi-supervised node classification in an undirected graph G(V,8) E) with N = | nodes and |3| edges. Each node v; E V is associated with pair yx), where x; Id is the input feature vector, y, R is the ground truth label, and is the candidate labels in the multi-class classifications. Besides, let X = [X]..... [xy] E RR. xd denote the input node feature matrix. Our goal is to find a set of parameters O = (W(0) Je=1 by minimizing the empirical loss L(O) over all nodes in the training set, i.e.,
(( = N Σ
((h ,y),,
h 0 = (e(e)) E by W(O).
I
lev
where -b.--) is the loss function (e.g., cross entropy loss), (-) is the activation function (e.g., ReLU), and N (v;)) is the neighborhood of node v, In practice, we can update the model parameters by the stochastic gradient computed on a sampled mini mini-batch (using full-neighbors) by
((A,E) B
Σ vo(h(") (o)))
(2)
where & denotes an i.i.d. sampled mini-batch of size B and we have EV VL(0).
Distributed GCN training with periodic averaging. In this paper, we consider the distributed
learning setting with P local machines and a single parameter server. The original input graph g
is partitioned into P subgraphs, where G, (V,, Ep) denotes the subgraph on the y-th local machine with N₂ 1ypl nodes, and X, Nd as the input feature of all nodes in V, located on the p-th machine. Then, the full- bull-batch local gradient V V.lceal (0,) is computed as
1 clocal (0,) Np EE, Vo(h.") (t) yi), h = =a (Np(xs)
E
( EvENston
1
h (1-1) W(
(3)
3

---

Published as a conference paper at ICLR 2022
Algorithm 1 Distributed GCN training with "Purallel SGD with Periodic Averaging"
Input: Global parameters 0", local parameters 0% 0 time-step 0, learning 1).
for r <- R do
2: for p - to 1' do in parallel
> Parallel training on local machines
3:
Local machine receives the global parameters 0 t- 0¹ Communication
4:
for l: <- 1 K do
5:
+
6:
Local machine constructs the mini-batch &, with neighbor sampling.
Local machine p computes the stochastic gradients V Ci (0 S,).
Local machine p updates the local parameter by 6 0 1) V Ch (0 (
9: end for
10:
Local machine sends the local parameters 0% to the server. b. Communication
11:
end for
12: Server updates the global parameters by parameter averaging 0
Σ 05!
13:
end for
Output: Server returns trained GCN model with min, B[I
where 0, = (W) | is the model parameters on the p-th local machine, (v,) Machine,NN,(v)) Ep} is the local neighbors of node computational complexity of forward and backward propagation could be very high. One practical solution is to compute the stochastic gradient on sampled mini-batch with neighbor sampling, i.e.,
= (wy ( 1y) e
the p-th local machine. When the graph is large, the
v Ceclocal (0p:
Bp Exes, Vo(h (L) yy), h (8) =o (wx)
E h (()""(()) (4)
where &, is i.i.d. sampled mini-batch of B, nodes, nodes, Ny(vs) C (N()) the sampled neighbors.
An illustration of distributed GCN training with Parallel SGD with Periodic Averaging (PSGD-PA) is summarized in Algorithm 1. Before training, the server maintains global model 0 and each local machine keeps a local copy of the same model g. During training, the local machine first updates the local model 0f using the stochastic gradient & L. (line 8), then sends the local model 0 to the server (line 10). At each communication step, the server collects and averages the model parameters from the local machines (line 12) and send the averaged model B5+1 back each local machine.
(0' . $ computed by Eq. for K iterations
Limitations, Although PSGD-PA ring the locally trained models instead of node feature/embedddngss (refer to Figure 2 (b)). it suffers from performance degeneration due to ignorance the cut-edges (refer to Figure (a)). In the next section, introduce communication-effices issue, and can achieve almost the same performance as training the model on a single machine.
PA can significantly reduce the communication overhead by transfer-
algorithm I.LCG that does not suffer from this
3 PROPOSED ALGORITHM: LEARN LOCALLY CORRECT GLOBALLY
In this section, we describe Learn Locally, Correct Globally (LLCG) for distributed GNN training. LLCG includes two main phases, local training with periodic model averaging and global server correction. to help reduce both the number of required communications and size of transferred data, without compromising the predictive accuracy. We summarize the details of L.LCG in Algorithm
3.1 LOCAL TRAINING WITH PERIODIC MODEL AVERAGING
At the beginning of local epoch, each local machine receives the latest global model parameters from the server (line 3). Next, each local machine runs Kp" iterations to update the local model (line 4 to 9), where K and p the hyper-parameters that control the local epoch size. Note that instead of using a fixed local epoch size as Algorithm I, we choose to use exponentially increasing local epoch size in LLCG with p > 1. The reasons are as follows.
At the beginning of the training phase, all local models o are far from the optimal solution and will receive gradient v C.ehall (0), (0),. computed by Eq. 4. Using smaller local update step at the early stage guarantees each local model does not diverge too much from each other before the model averaging step at the server side (line 12). However, towards the end of the training, all local
4

---

Published as a conference paper at ICLR 2022
Algorithm 2 Distributed GCN training by "Learn Locally, Correct Globally"
Input: Global parameters 0", local parameters 0%, time-step t 0, local step size hyper- parameters p. and learning rate 7
1: for r + 1 to 18 do
2: for p to P do in parallel
b Parallel training on local machine
3:
Local machine p receives the global parameters 0 0' 4: for k to p do
D Communication
5:
f ++
6:
Local machine p constructs the mini-batch & with neighbor sampling
7:
Local machine p computes stochastic gradients V L. (0) 4))
Local machine p updates model parameter by 0²- = 0z vVL Closal (0 (p)
9:
end for
10:
Local machine p sends the local parameters 0z to the server Communication end for
11:
12:
Server updates the global parameters using parameter averaging 0+1 ys Ep=
13:
for 4-+11 1 to S do
Server Correction
14:
L 1tt +-t+1
15:
Server constructs mini-batch e with full-neighbors
16:
Server computes the stochastic gradient V VL((0' Et) Server updates the global parameters by 0++1 = -
17:
18:
end for
19:
end for
Output: Server return GCN model with trained min, B|IlV
models 0 will receive relatively smaller gradient V " 4 such that we can chose a larger local epoch size to reduce the number of communications, without worrying about the divergence of local models. By doing so, after total number of T = Σ,=, Kpp iterations, LLCG only requires R = log, K rounds of communications. Therefore, compared to the fully-synchronous method, we can significantly reduce the total number of communications from ((T) to Ollog, k).
p
3.2 GLOBAL SERVER CORRECTION
The design of the global server correction is to ensure that the trained model not only learns from the data each local machine, but also learns the global structure of the graph, thus reducing the information loss caused by graph partitioning and avoiding cut-edges. Before the correction, the server receives the locally trained models from all local machines (line 10) and applies model parameter averaging (line 12). Next, S server correction steps are applied on top of the averaged model (line 13 to 18). During the correction, the server first constructs a mini-batch g using full- neighbors (line 15), compute the stochastic gradient V (L' 5") on the constructed mini-batch by Eq. (line 16) and update the averaged model 0 for S iterations (line 17). The number of correction steps S depends on the heterogeneity among the subgraphs on each local machine: the more heterogeneous the subgraphs are, the more correction steps are required to better refine the averaged model and reduce the divergence across the local models. Note that, the heterogeneity is minimized when employing GGS (Figure 2) with the local machines having access to the full graph, as result. However, GGS requires sampling from the global graph and communication at every iteration, which results in additional overhead and lower efficiency. Instead, in LLCG we are trading computation on the server for the costly feature communication, and only requires periodic communication.
THEORETICAL ANALYSIS
In this section, we provide the convergence analysis on the distributed training of GCN under two different settings, i.e., with and without server correction. We first introduce the notations and assumptions for the analysis (Section 4.1.. Then, we show that periodic averaging of local machine models alone and ignoring the global graph structure will suffer from irreducible residual error (Section 4.2). Finally, we show that this residual error can be eliminated by running server correction steps after each periodic averaging step the server (Section 4.3).
Note that using full neighhors is required for the server correction but not the local machines In practice, we found S
2 works well most datasets.
5

---

Published as a conference paper at ICLR 2022
(a)
(b) Without cross-devicn commonication Without neighbor sampling
(c) Without cross-devicr communication neighbor sumpling
With crocs-devica communication Without neighther sampling
V (0)
vet (0.5)
f=2
f=1
8-
( + (
40000 (4 ()+ (
2(22)) ] (8) 3[900100060 4 ( (0)
VC
Figure 3: Comparison of notations V C. ()), V b (0, Ep). and V v (0) on two local machines, where the blue node and green circles represent nodes on different local machines.
4.1 NOTATIONS AND ASSUMPTIONS
Let us first recall the notations defined in Section 2, where ((O) denotes the global objective function computed using the all node features X and the original graph G, (0) denotes the local objective function computed using the local node features X₂ and local graph L O¹. denotes the model parameters on the p-th local machine at the t-th step, and 0 Σ p=1 of denotes the virtual averaged model at the t-th step. In the non-convex optimization, our goal is to show the expected gradient of the global objective on the virtual averaged model parameters Elll (2((0') decreases as the number of local machines P and the number of training steps T increase. Besides, we introduce v Chull (0) as the gradient computed on the p-th local machine but have access the full node features X and the original graph structure G
VC p
ppl Σ Liv, iEV, Vo(h!")
(V(x)) (o(h))) .1). h ( EjEN (e- b
1
(5)
Please refer to Figure 3 for an illustration of different gradient computations. Besides, we introduce local-global gradient discrepancy as x² x + nix where x² = maxpe {ll V (0)
(Cllll [|2]] [ is the maximum difference between the gradient computed on the local machine with and without having access to the global graph structure, which is mainly due fact that the local machines are oblivious to the full graph information: and x max { V Chill
(=))) the maximum difference between the gradient computed using the local node and all nodes, which is mainly due to the heterogeneity of the node features on each local machine, and we have x* = 0 the nodes are i.i.d. sampled to each local machine. Notice that local gooll-llbbll gradient discrepancy x² plays an important role in our theoretical results.
For the convergence analysis, we make the following standard assumptions.
Assumption The stochastic gradient on the p-th local machine (with neighbor sampling) has stochastic gradient variance bounded by o and stochastic gradient bias bounded by o i.e. B|| Chraa 0 {) E(V SIVVDboro (B: I of B[[[E[V Chocat (6: V (0) S oras
Assumption The stochastic gradient for global server correction (with full neighbors) has stochas- tie gradient variance bounded by o oglobar i.e., E[[ Ch () V. (0)]11 S o2 globall
The existence of stochastic gradient bias and variance in sampling-basee GNN training have been studied in (Cong al., 2020; 2021), where (Cong et al., 2021) further quantify the stochastic gradient bias and variance as a function of the number of GCN layers. In particular, they show that the existence of oi is due to neighbor sampling and non-linear activation, and we have o 0 if all neighbors are used or the non-linear activation is removed. The existence of o is because we are sampling nini-batches compute the stochastic gradient on each local machine during training. As the mini-batch size increases, 0 will be decreasing, and we have o O when using full-batch.
4.2 DISTRIBUTED GNN VIA PARAMETER AVERAGING
In the following, we provide the first convergence analysis on distributed training of GCN. We show that solely periodic averaging of the local machine models and ignoring the global graph structure suffers from an upper bound that is irreducible with the number of training steps. Comparing to the traditional distributed training (e.g., distributed training Convolutional Neural Network for image classification (Dean et al., 2012; Li et al., 2020b)), the key challenges in the distributed GCN training is the two different types of gradient bias: (1) The expectation of the local full-batch gradient is

---

Published as a conference paper at ICLR 2022
biased estimation of the global full-batch gradient, i.e., 7. Σ because each local machine does not have access to the original input graph and full node feature matrix. Note that the aforementioned equivalence is important for the classifcal distributed training analysis Dean et al. (2012); Yu et al. (2019). (2) The expectation of the local stochastic gradient is a biased estimation of the local full-batch gradient i.e., E[V C (0, Ep)l A V V. (0). This is because the stochastic gradient on each local machine is computed by using neighbor sampling, which has been studied in (Cong et al., 2021).
P V
V (0) + VL(O). This is
Theorem (Distributed GCN via Parameter Averaging) Consider applying model averaging for yP and the local step size GNN training under Assumption and 2. If we choose learning rate r VT
/iT1/a K S 8T,5572 then for any T z P.2P steps of gradient updates we have
Σ T-1 =[
1
+ +O(N² + %
VP
Theorem 1 implies that, by carefully choosing the learning rate 1) and the local size K, the gradjent norm computed the virtual averaged model is bounded by (11 / /PT) after R = T K O 7
plya
communication rounds, but suffers from an irreducible residual error upper bound O + o bane ). In the next section, we show that this residual error can be eliminated by applying server correction.
4.3 DISTRIBUTED GCN VIA SERVER ER CORRECTION
Before proceeding to our result, in order to simplify the presentation, let us first define the nota- tion Gilabal
global m [B[ ([()) and Gi = min;g TE [1] Σ V (05)
as the minimum gradient computed at the r-th round global and local step. where Tgaoba (r) and (rea((r) are the number iteration run after the r-th communication round on server and local machine, respectively. Please refer to Eq. 42 in Appendix C.2 for formal definition.
Theorem 2 Consider applying model averaging for GCN training under Assumption and 2. we RT1/2
R /PP the local step size K,, such that Σ K²p²r S 32// and choose learning rate 7 = V/T'
server correction step size S max+E[R]
x² +2
Glocat)
Ke" then for any T 2 L2P steps Ghall
P/L(
of gradient updates we have: + Σ.T E V ( (++))
Theorem 2 implies that, by carefully choosing the learning rates Y and 17. the local step size hyper- parameters K, and the number of global correction steps S. after T steps (R rounds of communica- tion), employing parameter averaging with Global Server Correction, we have the norm of gradient bounded by D(I/VPT). without suffering the residual error that exists the naive parameter averaging (in Theorem 1). Besides, the server correction step size is proportional to the scale of x² and local stochastic gradient bias ois The larger x² and o the more corrections are required to eliminate the residual error. However, in practice, we observe that a very small number of correction steps (e.g.. S 1) performs well, which minimizes the computation overhead on the server.
EXPERIMENTS
Real-world simulation. In real-world distributed setting, the server and local machines located on different machines, connected through the network (Li et al., 2020a). However, for our experiments, we only have access single machine with multiple GPUs As a result, we simulate real-world distributed learning scenario, such that each GPU is responsible for the computation of two local machines (8 in total) and the CPU acts as the server. For these reasons, in our evaluations, we opted to report the communication size and number of communication rounds, instead of the wall-clock time, which can show the benefit of distributed training. We argue that these are acceptable measures in real-world scenarios well since the two main factors in distributed training are initializing connection overhead and bandwidth (Tripathy et al., 2020).
Baselines. To illustrate the effectiveness of LLCG, we setup two general synchronized distributed training techniques as the our baseline methods, namely "Parallel SGD with Parameter Averaging" (PSGD-PA) and "Global Graph Sampling" (GGS), introduced in Figure 2, where the cut-edges in PSGD-PA are ignored and only the model parameters are transferred. but the cut-edges in GGS considered and the node features of the cut-edges are transferred to the corresponding machine.
7

---

Published as a conference paper at ICLR 2022
Flickr
Proteins
Araiv
Redda
Olota Val Vd.F1 Sore
GlAd Wel (0 Syoee
0.50
0.70
0.7
0.65
0.1
U.6
PSGD
0.6
PSGD
0GS
PA
PSGD PA
0.40
10
30
LEDS
40
0.00
20
02-
20
No. Commoiaation
No. Commonicatiios
No. Commoiaation
No. Conmuniations
(a)
(b)
(c)
(d)
Andy
Reddit
Arxiv
Reddit
Comml Tram Law
PSGD-PA
PSrIh- PM
Glbed Seree
0.7
GlAd Va F. Saree
LEQ0
LECG
PSOD PA 11CG
00-
10'
10
16
10.
No. Commutications
No Comraniceions
Sino of Comm Bynsscoog Sealo
Size of Coran. in Bytts 'Log Scale)
(c)
(f)
(g)
(h)
Figure 4: Comparing LLCG against PSGD-PA and GGS on real-world datasets. We show the global the training loss per round of
validation score in terms of the number of communications in
communications in (e,)), and the global validation score per bytes of exchanged data in (g.h).
Table I: Comparison of performance and the average Megabytes of node representation/featuue communicated per round on various datasets.
Method
No.
GCN/ SAGE
GAT
APPNP
Comm.
Performance
Arg.
Performance
Avg.
Performance
Avg. MB
<lickr (FI (Pl-sc
PSGD-PA
19.0
12.57
51.56i+0
4.24
50.81=0.48
8.40
GGS
50
11.22.1011
1849.32
52.4110.
1895.61
51.331
1897.82
LLCG
300.38:0.200
12.57
52.01+0.a
4.24
51.15
8.40
PSGD-PA
72. 72.85
6:20
61.95+100 01
3.14
71.10=0.79
7.31
(ROC-AUC)
0S8-Proteins
GGS
100
74. 78=00.0 36
922-42
68. 11.11 Go
912.79
71. 0..
917.20
LLCG
73.92=0045
6.20
67.62+0.58
3.14
71.18=0.43
7.31
PSGD-PA
69.43
3.55
69.88.10 16
3.50
68.48..0.2
7.71
(FI-score)
OSR-Arxiv
GGS
100
70.51 20.00
3391 .03
70.82++ 23
3896.79
60.01
3394.33
LLCG
70.21 10.15
3.55
30.5810037
3.50
68.73..0.2
7.71
PSGD-PA
71.17
14.83
70.
7.48
83.4810.5
11.63
(Fl-score)
Raddit
GGS
97
3798.81
95.03+:044 48
38015.28
U5,
3770.46
LLCG
94.67 10.15
14.83
94.731025
7.48
94.6410.17
11.63
Note that we choose GGS as a reasonable representation for most existing proposals (Md et al., 2021;
Zheng et al., 2020; Tripathy et al., 2020) for distributed GNN training, since these methods have very close communication cost and also require large cluster of machines to truly show their performance improvement. We also use PSGD-PA as lower bound for communication size, which is widely used traditional distributed training and similar to the one used in (Angerd et al., 2020; Jiang & Rumi, 2021). However, we did not specifically include these methods in our results since we could not reproduce their results in our settings. Please refer to Appendix A for a detailed description of implementation, hardware specification and link to our source code.
Datasets and evaluation metric. We compare LLCG and other baselines on real-works semi- supervised node classification datasets, details of which are summarized in Table 2 in the Appendix. The input graphs are splitted into multiple subgraphs using METIS before training, then the same used for all baselines. For training,
set of subgraphs et al., 2017) with 10 neighbors sampled per node and p = 1.1 for LLCG. For a fair comparison, we chose the base local update step K such that LLCG has the same number of local update steps as PSGD-PA. During evaluation, we use full-batch without sampling, and report the performance on the full graph using AUC ROC and F1 Micro as the evaluation metric. Unless otherwise stated, we conduct each experiment five times and report the mean and standard deviation.
neighborhood sampling (Hamilton
5.1 PRIMARY RESULTS
In this section, we compare our proposed LLCG algorithm with basclines on four datasets. Due to space limitations we defer the detailed discussion on additional datasets to the Appendix A.4.
LLCG requires same number of communications. Figure 4 (a) through 4 (d) illustrate the validation accuracy per communication rounds on four different datasets. We run a fixed number of communication rounds and plot the global validation score (the validation score computed using the full-graph on the server) at the end of each communication step. For PSGD-PA and GGS, the score is calculated on the averaged model, whereas for LLCG the validation is caleulated after the correction
8

---

Published as a conference paper at ICLR 2022
Global Valiaatin Score
Arkiv
Reddit
Anxiv
0.8
Ai 16
Clobal Val F1 Sooee
Clubal Sloee
0.7
0.7
0.6
winamplin 305,3m1
0.6
Wasampiigg 201,5m1
wisasplin 561, Sm]
visaspling 561, Sm
0.5
wisangling 96, Sm2
0.3
w'sanpling 56, 5-1
40 Figure 5: Effect of local
20
40
Number of Communication
Number of Communications
Number Communicaions
Figure 6: Effect of sampling on local machine and num- ber of correction steps the server
epoch size (K)
step. It can be seen that PSGD-PA suffers from performance drop compared to other two methods, due to the residual error we discussed in Section 4, while both GGS and LLCG perform well and can achieve the expected accuracy. Note that the performance drop of PSGD-PA can vary across different datasets; in some cases such as Reddit, PSGD-PA can significantly hurt the accuracy. while on other datasets the gap is smaller. Nevertheless, LLCG can always close the gap between PSGD-PA and GGS with minimal overhead.
LLCG convergences as fast as GGS. To represent the effect of communication on the time- convergence, in Figure 4 (e) and 4 (f), we plot the global training loss (training loss computed on the full-graph on the server) after each communication round. Similar to the accuracy score, the training loss is also computed on the server averaged (and corrected, in case of LLCG) global model. These results clearly indicate that LLCG can improve the convergence over PSGD-PA, while it shows a similar convergence speed GGS.
LLCG exchanges data as little as PSGD-PA. Figure (g) and 4 (h) show the relation between global validation accuracy with the average size (volume) of communication in bytes. As expected, this figure clearly shows the effectiveness of LLCG On the one hand, LLCGG has a similar amount of communication volume as PSGD-PA but can achieve a higher accuracy. On the other hand, LLCG requires significantly less amount of communication volume than GGS to achieve the same accuracy, which leads slower training time in real world settings.
LLCG works with various GNN models and aggregations. We evaluate four popular GNN models, used in recent graph learning literature: GCN Kipf & Welling (2017), SAGE Hamilton et al. (2017), GAT Velickovic et al. (2018) and APPNP Klicpera et al. (2019). In Table 1, we summarize the test score and average communication size (in MB) on different datasets for a fixed number of communication rounds. Note that we only include the results for the aggregation methods (GCN or SAGE) that have higher accuracy for the specific datasets, details of which can be found in Appendix A.2. As shown here, LLCG can consistently improve the test accuracy for all different models compared to PSGD-PA, while the communication size is significantly lower than GGS, since LLCG only needs to exchange the model parameters.
Effect of local epoch size. Figure 5 compares the effect of various values of local epoch size K E [1, 4, 16, 64, 128) for fixed p and S on the OGB-OGGB-AO Arxiv dataset. When using, fully synchronous with K = 1, the model suffers from very slow convergence and needs more communications. Further increasing the K to larger values can speed the training; however, we found a diminishing return point for K 128 in this dataset and extremely large K in general.
Effect of sampling in local machines. In Figure 6, we report the validation scores per round of communication to compare the effect of neighborhood sampling at local machines. We observe that when the neighborhood sampling size is reasonably large (i.e., 20%), the performance is very similar full neighborhood training. However, reducing the neighbor sampling ratio to 5% could result in larger local stochastic gradient bias o which requires using more correction steps (S).
CONCLUDING REMARKS
In this paper, we propose a novel distributed algorithm for training Graph Neural Networks (GNNs). We theoretically analyze various GNN models and discover that, unlike the traditional deep neural networks, due to inherent data samples dependency in GNNs, naively applying periodic parameter averaging leads to residual error and current solutions to this issue impose huge communication overheads. Instead, our proposal tackles these problems by applying correction on top of locally learned models, infuse the global structure of the graph back into the network and avoid any costly communication. In addition, through extensive empirical analysis, we support our theoretical findings and demonstrate that LLLGG can achieve high accuracy without additional communication costs.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was supported in part by CRISP, one of six centers in JUMP, Semiconductor Research Corporation (SRC) program sponsored by DARPA and NSF grants 1909004, 1714389, 1912495, 1629915, 1629129, 1763681, 2008398.
REPRODUCIBILITY STATEMENT
We provide a GitHub repository in Appendix A including all code and scripts used in our ex- perimental studies. This repository includes a README mn file, explaining how to install and prepare the code and required packages. Detailed instruction on how to use the partitioning scripts is provided for various datasets. addition, we provide several configuration files (un- der scripts/ configs) folder for different syper-parameters on each individual dataset, and general script pecriptszzun con configg fig. py) to run and reproduce the results with these configura- tions. Details of various models and parameters used in evaluation studies also be found in Appendix A.
REFERENCES
Alexandra Angerd, Keshav Balasubramanian, and Murali Annavaram. Distributed training of graph convolutional networks using subgraph approximation. arXiv preprini MXXv:20012.04930. 2020.
Paolo Boldi and Sebastiano Vigna. The webgraph framework I: compression techniques. In Proceed- ings of the 13th international conference World Wide Web, WWW 2004, New York, NY, USA, May 17-20, 2004, pp. 595-602. ACM, 2004, doi: 10. 15/118897877229887552
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp. Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konecný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In Proceedings of Machine Learning and Systems 2019, MLSys 2019, Stanford, CA, USA, March 31- April 2, 2019. misys.org, 2019.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 941-949, PMLR, 2018
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, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 257-266. ACM, 2019. doi: 10.1 (4453322550033330222
Weilin Cong, Rana Forsati, Mahmut T. Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 1393-1403. ACM, 2020.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the importance of sampling in learning graph convolutional networks. arXiv preprint 100.::2003.02690 2021.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc' Aurelio Ranzato, Andrew W. Senior, Paul A. Tucker, Ke Yang, and Andrew Y. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pp. 1230-1240, 2012.
Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Learning dynamic context graphs for predicting social events. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining. KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1007-1016 ACM, 2019. doi: 10. 1 00.11455/22250333339999
10

---

Published as a conference paper at ICLR 2022
Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 750-760. ACM, 2019. doi: 10. 04114455329500333399555
Faezeh Faez, Yassaman Ommi, Mahdich Soleymani Baghshah, and Hamid R Rabiee. Deep graph generators: A survey. IEEE Access, 9: 00106667-1067000 2021.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6530 650006659,000 2017.
Mahsa Ghorbani, Anees Kazi, Mahdieh Soleymani Baghshah, Hamid R Rabiee, and Nassir Navab. Ra-gen: Graph convolutional network for disease prediction problems with imbalanced data. Medical Image Analysis, 75:102272, 2022.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint 181iv:8811003660 2018.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Weihua Hu, Matthias Fey. Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprini arXiv:2103.09433 2021.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, Frunce, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 448 456. JoLR. 2015.
Peng Jiang and Masuma Akter Rumi. cummuniiation-eefficce sampling for distributed training of graph convolutional networks. arXiv preprint arXlw:2101.07766. 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Jakub Konečný, H Brendan McMahan, X Yu Felix, Ananda Theertha Suresh, Dave Bacon, and Peter Richtárik. Federated learning: Strategies for improving communication efficiency. 2018.
Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 -Novemeer 2, 2019, pp. 9266-9275. IEBE, 2019. doi: 10.1109/ICCV. 2019.00936.
Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, et al. Pytorch distributed: Experiences on accelerating data parallel training. arXiv preprint arXiv:2006. 15704, 2020a.

---

Published as a conference paper at ICLR 2022
Xiang Li. Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In 8th International Conference on Learning Representations. ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020b.
Bill Yuchen Lin, Chaoyang He, Zihang Zeng, Hulin Wang, Yufen Huang, Mahdi Soltanolkoabbi, Xiang Ren, and Salman Avestimehr. Fednlp: A research platform for federated learning in natural language processing. arXiv preprint arXiv:2 10::22004.88// 2021.
Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexan- der Heinecke, Dhiraj Kalamkar, Nesreen K Ahmed, and Sasikanth Avancha. Distgnn: Scalable distributed training for large-scale graph neural networks. arXiv preprint arXiv: 104.06700 2021.
Morteza Ramezani, Weilin Cong, Mchrdad Mahdavi, Anand Sivasubramaniam, and Mahmut Kan- demir. Gen meets gpu: Decoupling "when to sample" from "how to sample". Advances in Neural Information Processing Systems, 33, 2020.
Simone Scardapane. Indro Spinelli, and Paolo Di Lorenzo. Distributed graph convolutional networks. arXiv preprint arXiv:2007.0628/ 2020.
Hyejin Shin, Sungwook Kim, Junbum Shin, and Xiaokui Xiao. Privacy enhanced matrix factorization for recommendation with local differential privacy. IEEE Transactions on Knowledge and Data Engineeringg (000):1770-1782 2018.
Sebastian U. Stich. Local SGD converges fast and communicates little. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Chuxiong Sun and Guoshi Wu. Adaptive graph diffusion networks with hop-wise attention. arXiv preprint arXiv:2012.1502: 2020.
Chuxiong Sun and Guoshi Wu. Scalable and adaptive graph neural networks with sabf-labcleehhaneed training. arXiv preprint arXiv:2104.09376, 2021.
Alok Tripathy, Katherine Yelick, and Aydin Buluc. Reducing communication in graph neural network training. arXiv preprint arXiv:2005.03300 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
Jizhe Wang, Pipei Huang. Huan Zhao, Zhibo Zhang. Binqiang Zhao, and Dik Lun Lee. Billion-scale commodity embedding for e-commerce recommendation in alibaba. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 839-848. ACM, 2018. doi: 10. 10.1145/2198199:221966
Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for srivacy-preserving recommendation. arXiv preprint arXiv:2102.04925, 2021.
Rex Ying. Ruining He, 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 Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 974-983. ACM, 2018. doi: 10.1145//211811932219999
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 5693-579075 5700, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
12

---

Published as a conference paper at ICLR 2022
Qingru Zhang, David Wipf. Quan Gan, and Le Song. A biased graph neural network sampler with near-optimal regret. arXiv preprint arXiv:2103.0009, 2021.
Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. Distdgl: Distributed graph neural network training for billion-scale graphs arXiv preprint a01vv:2010.05337, 2020.
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 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 11247-11256, 2019.
13


Reviews:
[{"review_id": "jNTQGaiMpz0", "reviewer": "Reviewer_qLfR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper deals with the problem of distributed training of GNNs. Existing methods are either communication-intensive (sampling) or do not achieve good performance (averaging).\n\nThe authors propose a novel method, dubbed \"LLCG: Learn Locally Correct Globally\". Essentially, this method captures the idea of transmitting only local averages but adds a centralized step on the server to account for global structural information lost in the subgraph partition.\n\nThe authors further provide theoretical convergence guarantees. They both show that just averaging leads to an insurmountable residual error that explains the poor performance of averaging methods, as well as prove that this residual error disappears when adding the global correction step.\n\nThe paper is fairly well written and the proposed result, albeit simple, is powerful. The theoretical guarantees provided round up the good work. More importantly, the topic is timely and very relevant, and I, therefore, recommend acceptance in the conference, provided they add standard deviation results to Table 1.\n\nSome questions that could further enhance the discussion are as follows:\n\n1) What would happen if all labeled nodes used for training end up in a single server. How long would it take to converge? Would it be affected?\n\n2) Are there any best ways of partitioning the graphs into the servers? How does partitioning affect convergence?\n\nMinor comments:\n\nBeginning of Section 4.3: where it reads 'before processing' it should read 'before proceeding'\n\nThe paragraph 'datasets and evaluation metric' refers to six semi-supervised classification datasets and points to Table 2. However, the results are for four datasets and referenced in Table 1, not table 2. I understand that there are more experiments on the supplementary material, but refer to table 1 and just four datasets in this section since that are what is being shown in the main matter of the paper.\n\nFig 4 f, I understand this should be Proteins, and not Reddit (Reddit is in Fig 4h)", "summary_of_the_paper": "This paper deals with the problem of distributed training of GNNs. Existing methods are either communication-intensive (sampling) or do not achieve good performance (averaging).\n\nThe authors propose a novel method, dubbed \"LLCG: Learn Locally Correct Globally\". Essentially, this method captures the idea of transmitting only local averages but adds a centralized step on the server to account for global structural information lost in the subgraph partition.\n\nThe authors further provide theoretical convergence guarantees. They both show that just averaging leads to an insurmountable residual error that explains the poor performance of averaging methods, as well as prove that this residual error disappears when adding the global correction step.", "summary_of_the_review": "The paper is fairly well written and the proposed result, albeit simple, is powerful. The theoretical guarantees provided round up the good work. More importantly, the topic is timely and very relevant, and I, therefore, recommend acceptance in the conference, provided they add standard deviation results to Table 1.\n\nMy assigned score is 7.", "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": "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": "iK0_ZedP0Gm", "reviewer": "Reviewer_wvQK", "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": "Major comments: \n\nI am mainly concerned about the novelty of this submission. Local SGD [1] is not very novel in distributional optimization. This submission inserts an additional update on the server to eliminate the sampling error. In my opinion, It is difficult to say that this method was designed specifically for training GNN since one can extend this procedure to any dataset. (This paper argues that training GNN needs this step due to the residual error,  which I will comment on later.) The theoretical results are also not novel. The analysis follows the local sgd method. The only additional condition is the sampling error, which doesn't provide any new insight. \n\nThe motivation regarding the proposed method is not well justified. The main contribution, if any novelty, is the full neighbor updates on the server. Why do local machines use sampled neighbors while the server uses full neighbors? The motivation discussed in the introduction mentioned local devices lack the global graph structure. In my opinion, this setting is more of partitioned graphs rather than sampling. This problem also partially involves my above comment. Since the residual error seems to come from the sampling, the improvement from the update on the server is not exciting.\n\nThe experimental results show some improvement, particularly for Reddit.  Besides numbers of communication, the running time is also necessary since the server requires additional updates. Table 1 and Figure 4 mentioned communication cost, which is not clearly defined anywhere in this submission.\n\n[1] Stich, Sebastian U. ``Local SGD converges fast and communicates little.\" arXiv preprint arXiv:1805.09767 (2018).\n\nMinor comments:\n\nThe experiments use neighbor sampling. It is interesting to see the impact of different samplers, e.g. importance sampling.\n\nTypo and grammar mistakes, e.g., ``we theoretically analysis the convergence of our proposal LLCG'' -- > analyze. ``During the correction, the server first construct a mini-batch...'' -- > constructs. ``however, due to space limitations we differ the detailed discussion on these datasets to the Appendix'' -- > perhaps refer? Etc.\n", "summary_of_the_paper": "Training GNNs is challenging due to high communication costs or large memory overheads. This paper proposes a communication-efficient distributed GNN training technique named Learn Locally, Correct Globally (LLCG) to periodically model averaging on the server using locally trained models.  It also applies global server corrections to refine the locally learned models and solve the irreducible performance degradation caused by ignoring node dependency. This paper provides the convergence analysis and shows the proposed method can address the residual error. The experimental results show significant improvement compared to existing methods.", "summary_of_the_review": "This paper applies local SGD to GNN training. The idea is not very novel. The experimental results are promising, but some important points need clarification.\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "RB7TUkWou0L", "reviewer": "Reviewer_Wu2z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper presents an interesting method for distributed training of GNN which can be helpful when training on very large graphs. The paper is well presented and easy to follow. The theoretical analysis is important in my opinion, as it can provide motivation as to why this method is better than previous ones. Specifically, the importance of having a server correction phase. The empirical part is thorough, providing experiments on several datasets. The proposed training technique is being compared to either PSGD-PA which has worse performance, and GGS which has a much higher communication cost.\n\nI have a couple of concerns regarding the theoretical part:\n\n1) Theorem 1 basically shows an upper bound on the average norm of the gradients throughout T iterations. It is unclear why the “irreducible part” of this bound is really irreducible. I believe that if the authors want to prove that the algorithm from Theorem 2 is better than the one in Theorem 1, then they should show a lower bound in Theorem 1, and make a case that this term is really irreducible. \n\n2) I am not sure if the term discussed in the previous point is really irreducible. Theorem 1 & 2 only shows a bound on the norm of the gradients, averaged over T iterations. If the loss function L is smooth (which may be reasonable), then it would converge eventually to a stationary point. Hence, it is not clear why for a large enough T, this term can be lower bounded by some term independent of T.\n\n3) In Theorems 1 & 2 the authors only show that the loss converges to a stationary point, which may as well be a saddle point or spurious minima. Can the authors elaborate on this? Is there some guarantee on to which point the loss converges to?\n\nAs I said, the empirical part is satisfactory in my opinion and shows the benefits of LLCG. It does seem that all the tasks consider node classification, and I wonder how this method would work on edge classification tasks. This may be an important case study since edges can be cut off when splitting the graph into subgraphs.\n\nA few minor issues:\n\n1) The indexing in algorithms 1 & 2 is a bit confusing because there are three loops (global epochs, local machine’s epochs, and server corrections). I think it would be better to use indices for \\theta which represent the current global epoch, and either local machine epoch or server correction epoch.\n\n2) Figures 4-7 are very small and hard to read. Due to the page limit constraint, I suggest highlighting fewer figures in the main part and giving the rest of the figures on a larger scale in the appendix.\n\nI note that I’m not an expert in distributed computing, and may have missed some related works or important benchmarks which should have been mentioned.\n", "summary_of_the_paper": "This paper proposes a distributed training technique for GNN. This technique includes local computations done in parallel by several machines and a correction phase done by a centralized server. A theoretical analysis is given for this technique, showing that the server correction phase reduces some irreducible error that happens due to splitting the graph and doing a local computation on each subgraph. Several experiments are made on real datasets which show the merits of this technique over previous techniques in terms of performance, communication steps, and size.", "summary_of_the_review": "I think the optimization technique this paper presents is nice. The empirical results are thorough, showing advantages over previous methods. The theoretical part is a bit unclear. specifically, whether Theorem 1 actually shows a lower bound (i.e. is the second term there irreducible). ", "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": "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": "9WKd7bnnAgT", "reviewer": "Reviewer_5Wg7", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well-written and is enjoyable to read. The problem is clearly defined, and the solution steps are thoroughly explained. I do have some concerns, which I hope the authors will address:\n- It would help if the GGS algorithm is explained (at least at a high level) in the paper since it figures some prominently in all the experiments. \n- In equation 1, the h update equation seems independent of input features x. \n- Since server correction is claimed to be crucial for performance, it would help if the authors can do an ablation study without server correction. I wonder if this is the same as PSGD-PA since LLCG uses exponential increasing round lengths whereas PSGD-PA does not. \n- Are the graph partitions at the local machines the same for PSGD-PA and LLCG in the experiments? \n- In the server correct step, does it help for the server to carefully choose the minibatch to include more of the cut-edges (i.e., edges that are not considered by the local machines)?\n- What is T_global(r) and T_local(r) in Section 4.3?\n- In Theorem 2, if T = \\sum_{r=1}^R K\\rho^r, how can \\sum_{r=1}^R K^2 \\rho^{2r} be less than O(\\sqrt{T})? \n- In figure 4 (and others), the performance is plotted as a function of number of communication rounds. How does performance fare as a function of number of local training steps? \n", "summary_of_the_paper": "The paper considers the problem of distributed training for graph learning tasks, under a setting where data privacy is significant for each individual machine and communication to/from a central parameter server is expensive. To preserve privacy each machine has only access to a distinct partition of the overall graph. The central server has access to the full graph. In the LLCG algorithm that the paper proposes, each machine trains on its local graph partition for some time before sending the parameters to the server. The server averages the received parameter, but additionally also does its own training using the full graph available to it. Theoretically the authors show that the proposed method avoids an error gap in the gradient norm that would exist if server correction is not performed. Experimental results show the proposed scheme performing similarly to GGS albeit with much lower communication costs.  ", "summary_of_the_review": "Well-written paper that considers an important problem and presents a simple, effective solution. There are some concerns however which I hope the authors will address. ", "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": "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:

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period. The current discussions mostly lie on the acceptance side. 

Some prons of the paper include:

- Timely topic: This paper deals with the problem of distributed training of GNNs. 
- New algorithm: this method captures the idea of transmitting only local averages but adds a centralized step on the server to account for global structural information lost in the subgraph partition.
- Theory: The authors further provide theoretical convergence guarantees. 
- Clarity: The paper is fairly well written and the proposed result is simple and powerful. 

The current consensus is that the paper deserves publication.

Best AC
Decision: Accept (Poster)