Distributed Graph Neural Network Training with Periodic Stale Representation Synchronization
Authors: Zheng Chai
Guangji Bai
Liang Zhao
Yue Cheng
Venue: Submitted to ICLR 2023 (2023)
Keywords: GNN
Distributed training

Abstract: Despite the recent success of Graph Neural Networks (GNNs), it remains challenging to train a GNN on large graphs with over millions of nodes & billions of edges, which are prevalent in many graph-based applications such as social networks, recommender systems, and knowledge graphs. Traditional sampling-based methods accelerate GNN training by dropping edges and nodes, which impairs the graph integrity and model performance. Differently, distributed GNN algorithms accelerate GNN training by utilizing multiple computing devices and can be classified into two types: "partition-based" methods enjoy low communication cost but suffer from information loss due to dropped edges, while "propagation-based" methods avoid information loss but suffer from prohibitive communication overhead caused by neighbor explosion. To jointly address these problems, this paper proposes DIGEST (DIstributed Graph reprEsentation SynchronizaTion), a novel distributed GNN training framework that synergizes the complementary strength of both categories of existing methods. We propose to allow each device utilize the stale representations of its neighbors in other subgraphs during subgraph parallel training. This way, out method preserves global graph information from neighbors to avoid information loss and reduce the communication cost. Therefore, DIGEST is both computation-efficient and communication-efficient as it does not need to frequently (re-)compute and transfer the massive representation data across the devices, due to neighbor explosion. DIGEST provides synchronous and asynchronous training manners for homogeneous and heterogeneous training environment, respectively. We proved that the approximation error induced by the staleness of the representations can be upper-bounded. More importantly, our convergence analysis demonstrates that DIGEST enjoys the state-of-the-art convergence rate. Extensive experimental evaluation on large, real-world graph datasets shows that DIGEST achieves up to 21.82× speedup without compromising the performance compared to state-of-the-art distributed GNN training frameworks

Under review as a conference paper at ICLR 2023
DISTRIBUTED GRAPH NEURAL NETWORK TRAINING WITH PERIODIC STALE REPRESENTATION SYNCHRO- NIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the recent success of Graph Neural Networks (GNNs), remains chal- lenging to train GNN on large graphs with over millions of nodes & billions of edges, which are prevalent in many graph-based applications such as social net- works, recommender systems, and knowledge graphs. Traditional compling-based methods accelerate GNN training by dropping edges and nodes, which impairs the graph integrity and model performance. Differently, distributed GNN algorithms accelerate GNN training by utilizing multiple computing devices and can be clas- sified into two types: "partition-basee but suffer from information loss due to dropped edges, while "propagation- based" methods avoid information loss but suffer from prohibitive communication over- head caused by neighbor explosion. To jointly address these problems, this paper proposes DIGEST (DIstributed Graph reprEsentation SynchronizaTion, distributed GNN training framework that synergizes the complementary strength of both categories of existing methods. We propose to allow each device utilize the stale representations of its neighbors in other subgraphs during subgraph parallel training. This way, out method preserves global graph information from neighbors to avoid information loss and reduce the communication cost. Therefore, DIGEST is both computation-efficient and communication-effienn -effaiiiinnffninntttteme as does not need to frequently (re- Jcompute and transfer the massive representation data across the de- vices, due to neighbor explosion. DIGEST provides synchronous and asynchronous training manners for homogeneous and heterogencous training environment, spectively. We proved that the approximation error induced by the staleness of the representations can be upper- hounded More importantly, our convergence analysis demonstrates that DIGEST enjoys the state-of-the-aat convergence rate. Extensive experimental evaluation on large, real-world graph datasets shows that DIGEST achieves up to 21.82x x speedup without compromising the performance compared state-of-the-an distributed GNN training frameworks.
methods enjoy low communication cost
novel
INTRODUCTION
Graph Neural Networks (GNNs) have shown impressive success in analyzing non-Euclidean graph data and have achieved promising results in various applications, including social networks, rec- ommender systems and knowledge graphs, etc. (Dai et al.) 2016; Ying al.) 2018 Eksombatchal et al., 2018 Lei et al. 2019 Zhu et al. 2019). Despite the great promise of GNNs, they meet significant challenges when being applied to large graphs, which are common in real world-thh number of nodes of large graph can be up to millions or even billions. For instance, Facebook social network graph contains over 2.9 billion users and over 400 billion friendship relations among users") Amazon provides recommendations over 350 million items to 300 million user Further, natural language processing (NLP) tasks take advantage knowledge graphs, such as Freebase (Chah) 2017) with over 1.9 billion triples. Training GNNs on large graphs is jointly challenged by the lack of inherent parallelism in the backpropagation optimization and heavy inter-dependencies among graph nodes, rendering existing parallel techniques inefficient. To tackle the unique challenges in GNN
https://amzsccous htw.:///we...ooo////oooo/oooo//o stat stics

---

Under review as a conference paper at ICLR 2023
training, distributed GNN training is a promising open domain that has attracted fast-increasing attention in recent years. A classic and intuitive way is by sampling. Until now, a good number of graph-sampling- based GNN methods have been proposed, including neighbor-sampling -aasdd based methods (e.g., GraphSAGE (Hamilton et al., 2017), VR-GCN (Chen et al. 2018)) and subgraph- sampling-basee methods (e.g.. Cluster-GCN (Chiang et al.) 2019), GraphSAINT (Zen et al. 2019)). These methods enable a GNN model to be trained over large graphs on single machine by sampling subset of data during forward or backward propagation. While sampling operations reduce the size of data needed for computation, these methods suffer from degenerated performance due to unnecessary information loss. To walk around this drawback and also to leverage the increasingly powerful computing capability of modern hardware accelerators, recent solutions propose to train GNNs on a large number of CPU and GPU devices (Thorpe et al. 202T Ramezani et al. 2021 Wan 2022) and have become the de facto standard for fast and accurate training over large graphs. et al.
Existing methods in distributed training for GNNs can be classified into two categories, namely "partition-based" and "propagation-baseed
by how they tackle the trade-off between computa- tion/comuunicatinn cost and information loss. "Partition-based" methods (Angerd et al. 2020; Jia et al., 2020 Ramezani et al., 2021) partition the graph into different subgraphs by dropping the edges across subgraphs. This way, the GNN training on a large graph is decomposed into many smaller training tasks, each trained in siloed subgraphs in parallel, reducing communications among subgraphs, and thus, tasks, due to edge dropping. However, this will result in severe information loss due to the ignorance of the dependencies among nodes across subgraphs and cause performance degeneration. To alleviate information loss, "propagation- bassdd"dd--d-e-ae methods (Ma et al. 2019: Zhu et al. 2019 Zheng al. 2020 Trippthy et al. 2020 Wan et al.) 2022) do not ignore edges across different subgraphs with neighbor communications among subgraphs to satisfy GNN's neighbor aggregation. However, the number of neighbors involved in neighbor aggregation grows exponentially as the GNN goes deeper (i.e., neighborhood explosion (Hamilton et al., 2017)) ). hence inevitably suffering huge communication overhead and plagued training efficiency.
Therefore, although "partition-
methods can parallelize training job among partitioned subgraphs, they suffers from information loss and low accuracy. "Propagation-batt based"" methods, on the other hand, use the entire graph for training without information loss but suffer from huge communication overhead and poor efficiency. Hence, it is highly imperative to develop a method that can jointly address the problems of high communication cost and severe information loss. Moreover, theoretical guarantees (e.g.. on convergence, approximation error) are not well explored for distributed GNN training due to the joint sophistication of graph structure and neural network optimization.
To address the aforementioned challenges, we propose a novel distributed GNN training framework that synergizes the complementary strengths of both partitioning- based and propagating- -ased meth- ods, named DIstributed Graph reprEsentation SynchronizaTion. or DIGEST. DIGEST does not completely discard node information from other subgraphs in order avoid unnecessary information loss; DIGEST does not frequently update all the node information in order to minimize commu- nication costs. Instead, DIGEST extends the idea of single-GPU Gau-baeed GCN training with stale representations (Chen et al. 2018 Fey et al.] 2021) to distributed setting, by enabling each device to efficiently exchange relatively stale version of the neighbor representations from other subgraphs, to achieve scalable and high-performance GNN training. This effectively avoids neighbor updating explosion and reduces communication costs across training devices. Considering naive synchronous distributed training that inherently lacks the capability of handling stragglers caused by training environment heterogeneity (e.g. GPU resource heterogeneity), we further design an asynchronous version of DIGEST (DIGEST-A), where each subgraph follows non-blocking training manner. The synchronous version is a natural generalization of Fey et al. (2021) while the asynchronous version can handle the straggler issue (Chen al. 2016 Zheng al. 2017) in synchronous version and enjoys even better performance. From the system aspect, DIGEST (I) enables efficient, cross-device representation exchanging by using shared memory key-value storage (KVS) system, (2) supports both synchronous and asynchronous parameter updating, and (3) overlaps the computation (layer training) with I/Os (pushing/pulling representations to/from the KVS.
Furthermore, we proved that the approximation error induced by the staleness of representation can be bounded. More importantly, global convergence guarantee is provided, which demonstrates that DIGEST has the state-of-the-art convergence rate. Our main contributions can be summarized as: Proposing a novel distributed GNN training framework that synergizes the benefits of partition-based and communication- methods. Existing work in distributed GNN training
2

---

Under review as a conference paper at ICLR 2023
focus two contradictory objectives: partition-basse based methods target minimizing the communica- tion cost while propagation- based methods aim to minimize information loss. DIGEST drops no edges while avoiding communication overhead by integrating the strengths of both categories. Developing a periodic stale representation synchronization technique for distributed GNN training. DIGEST utilizes the entire graph for training by separating in- and out-of-uubgrahh neighbor nodes and approximating the latter with stale representations. Instead of making strictly synchronous pull/push operations for the representations of all layers before/after training, DIGEST overlaps pull/push operations with layer training to minimize the overall training time. Furthermore, a shared- moeddd-mmooobaeeeeee -ased KVS is used among subgraphs for efficiently exchanging representations. Providing extensive thcoretical guarantee on both performance and convergence of the proposed algorithm. We proved that DIGEST's convergence rate is OTT M- with T iterations and M subgraphs, which is close to vanilla distributed GNN training without staleness. Convergence guarantee for both synchronous and asynchronous versions of DIGEST is provided. We also showed the upper bound on the approximation error of gradients due to the staleness.
Conducting comprehensive empirical results on both performance and speedup. We perform extensive evaluation four benchmark with classic GNNs (e.g., GCN (Hamilton et al. 2017) and GAT (Velččkoićć et al., 2017)) J. The experimental results show that for the best case DIGEST improves the performance by 14%, and achieves 21.82x speedup in training time compared to two state-of of-the-art distributed GNNs training frameworks.
BACKGROUND AND PROBLEM FORMULATION
In this section, we first introduce the Graph Neural Network (GNN) and its training on a single machine, and then formulate the problem of distributed GNN training.
Graph Neural Networks. GNNs aim to learn a function of signals/features on a graph G(V,E) with node representations X E R/V xd where d denotes the node feature dimension. For typical semi- supervised node classification tasks (Kipf & Welling, 2016), where each node e E V is associated with a label ye. a L-layer GNN f is trained to learn the node representation h, such that yu can be predicted accurately. The training process of a GNN can be practically described as the node representation learning based on the message passing mechanism (Gilmer et al. 2017). Analytically, given a graph G(V,E) and a node E V, the (E + 1)-th layer of the GNN is defined as
h ((+1) = (((11)=f() ((+2)) (h(9) (b u E = (((+2) (h!0) ((+1) ((h : E(())) (I)
where h denotes the representation of node v in the ê-th layer, and h being initialized to x, (v-th row in X), and (u)) represents the set of direct 1-hop neighbors for node v. Each layer of the GNN, i.e. f((), can be further decomposed into two components: 1) Aggregation function (1)), which takes the nodes representations of node v's neighbors as input, and output the aggregated neighborhood representation. 2) Updating function (()), which combines the representation of and the aggregated neighborhood representation to update the representation of node v for the next layer. Both ((() and (i()) can choose to use various functions in different types of GNNs. To train a GNN on a single machine, one can minimize the empirical loss L(W) over the entire graph in the training data, i.c., L(W) = (1/IV) EvEv Loss (h (4) y.), where Loss(-:-) -) denotes a loss function (e.g., cross entropy loss), and n denotes the representation of node e from the last layer of the GNN and can be calculated by following Eq. [ recursively.
Distributed Training for GNNs. Distributed GNN training means to first partition the original graph into multiple subgraphs without overlap, which can also be considered as mini batches. Then different mini-batches are trained in different devices in parallel. Here, Eq. I can be further reformulated as
h ((+1) ((+1) h ((++)) (h(5) E (u)) (()) U (h(2 (v)) ((v))) (2)
In-subgraph nodes
Out-of-subgraph nodes
where S(v) denotes the subgraph that node belongs to. In this paper, we consider the distributed training of GNNs with multiple local machines and a global server. The original input graph & is first partitioned into M subgraphs, where each (Vm, Em) represents the subgraph m. Our goal is to find the optimal set of parameters W in a distributed manner by minimizing each local loss, i.e.,
1
minw CLocal (Wm)
Σ
Loss (h( y.), m = 1,2, .,, ,M in parallel, (3)
1mml vVV.
3

---

Under review as a conference paper at ICLR 2023
Machine 2's neighbor explosion & communication overhead
Stale Representation (Key-value store)
16--2
H(-1)
Machine 1
PULL
PUSH
Machine 2
1-hop neighbor
Machine 3
layer 2
layer
layer L
Propagation-bused methods
Machine
All machines suffer from information loss due to dropped odges
Machine 2
Machine
Machine 3
Machine 2
layer I.
layer
layer I.
Machine 3
Wil-2)
W((
W(4)
layer L- layer L 1 layer L
Parameter Server
(b) Partition-based methods
(c) Distributed Graph Representation Synchromization (DIGEST)
Figure I: Distributed GNN training methods. (a): Propagation- based methods rely on commu- nication of out-of-subgrapp neighbor nodes for exact message passing even in distributed setup. (b): Partition-basee methods decompose the original problem into multiple smaller ones and directly apply data parallelism onto partitioned subgraph data. (c): In DIGEST each device utilizes the stale representations of all its neighbors from other subgraphs. Propagation- communication cost (red vertical double arrows in (a)) due neighbor explosion, while partition- based methods suffer severe information loss due to dropped edges (red crosses in (b)). DIGEST combines the best of both worlds. ALL nodes utilized in DIGEST achieve full-graph awareness, while periodic stale representation synchronization keeps the communication cost low.
methods suffers high
where W.,. m (W(0) J. Jé=1 are local parameters and h follows Eq. recursively.
Challenges. The main challenges for distributed training of GNNs lie in the trade-off between communication cost and information loss. "Partition-baut based" method generalizes the existing data parallelism techniques of classical distributed training i.i.d data to graph data and enjoys minimal communication cost. However, directly partitioning a large graph into multiple subgraphs can result in severe information loss due the ignorance huge number of cross-subgraph edges and cause performance degeneration (Angerd et al. 2020; Jia et al. 2020 Ramezani et al. (202I). For these methods, the representation of neighbors out of the current subgraph (second representation set in Eq. 2) are dropped and the connections between subgraphs are thus ignored. Hence, another line of work (Wang et al., 2019), namely "propagation- based"" method considers using communication of neighbor nodes for each subgraph to satisfy GNN's neighbor aggregation, which minimizes the information loss. shown in Eq. - the representations for neighbor nodes outside the current subgraph is swapped between different subgraphs. However, the number of neighbors involved in the neighbor aggregation process expands exponentially as the GNN model goes deep, which is known the neighborhood explosion problem. Hence, though edges dropped in this case, inevitable communication overhead is incurred and plagues the achievable training efficiency (Ma et al.) [2019] Zhu et al. 2019 Zheng et al. 2020 Tripathy et al.) 2020 Wan et al.) [022]. Moreover, theoretical guarantees (e.g., on convergence, approximation error) are not well explored for distributed GNN due to the joint sophistication of graph structure and neural network optimization.
PROPOSED METHOD
In this section, introduce the proposed GNN training framework DIGEST. DIGEST leverages both types of representations in 2q address the information loss issue. In addition, instead of exchanging real-time representations during the training process between the subgraphs, DIGEST only pull and push the stale representations before or after each step of training periodically. With this strategy, the communications turn be more efficient, which are illustrated in Figure [an analyzed in more details in Section 3.3) Moreover, we prove that the error introduced by the staleness of the stale representation upper-bounded while the convergence is also guaranteed.
and
4

---

Under review as a conference paper at ICLR 2023
3.1 DISTRIBUTED GNN TRAINING WITH FULL-GRAPH AWARENESS
In DIGEST, each copy of GNN trained on a local machine will make use of available graph information, i.e. no edges are dropped in both forward and backward propagation. Analytically, calculating each local gradient V as defined in Eq. will involve out-of- -l--o---uubraphhhhhh neighbor information. For out-of-subgraph neighbor nodes,
approximate their representations via stale rep- resentations acquired in previous training, denoted by h Formally, given a node E 9n Em), the forward propagation for the (E + 1)-th layer of DIGEST is achieved by modifying Eq. 2 as
h ((+1)) (((+1)) h!! (((+1)
(n,90) u (Ne)
u [ (
E Vm )m)
(4)
Stale represeniation
As can be seen, DIGEST considers ALL neighbor nodes information during forward propagation. On the other hand, leveraging the entire graph data in forward propagation will in turn improve the estimation of gradient in backpropagation. To see this, we reformulate Eq. into the matrix form:
H ((+1m)) F (
Fr(mm)) o (P( (m)
H (f.m)
(f+
(m))
(L.)) w((+)))
(5)
where ( and H ((.)) denotes the matrix of iuuuurppp node representations and out-of-subgraph stale representations at 8-th layer on subgraph Gm. respectively. I' denotes the forward propagation function of one layer of GNN for compact formula. We consider the GCN model as an example for
illustration but our analyses apply to general cases of any GNN models. p(m) and ((m) out denotes the propagation matrix for in-subgraph nodes and out-of-subgraph nodes of Gm. respectively, and have Pm = (mm) + (m())
in
out where Pm is the original propagation matrix for subgraph 9m- (..) is the activation function following GCN's definition. Hence, the gradient over model parameters
in
F
H [f.m)
(t.m) H Dutt
P (m)
(E,m)
((++1)
+ P out H
(mm) (6,m) w((+1)
aw Ow(e+1
(e+1)
(e+1)))
in
out
m
[P mm) H (f.m)
P
H
(f.))
P (m)
(f.m) ((+1)) +
(m)) out
H (f.m) ( out
w((+1))
out
The key observation here is that ALL neighbor nodes are involved in the backpropagation since the gradient above depends on H (f.m), The separation of in-subgraph nodes and -fubbr--ubgraph nodes,
and their approximation via stale representation form the very foundation of DIGEST.
3.2 SYSTEM DESIGN
This section presents the overall system design of DIGEST as depicted in Figure DIGEST maintains serredd-emory-basse KVS for storing and retrieving representations, KVS can be easily extended to truly distributed storage to support large-scale distributed training spanning multiple servers.
We first introduce two operations used by DIGEST to store and retrieve representations. The stale representations of layer for all nodes in V can be formulated as ( (T. E v). For any subgraph Gm. start the forward process of layer f, the necessary stale representations (((f.m)) out = (h()) u e N(v)) \ Vn, e E Vm are pulled from the KVS that stores representations; this is called "pull" operation denoted as H (l.m) t- H (f.m) See Figure c). After the end of epoch, the newly-computed representations (f.m) = (h V E Vm are pushed to the KVS, and these newly-stored representations will be fetched stale representations in future epochs; this called "push" operation denoted as H (f.m) (f.m)
in
in
DIGEST features two training modes: (1) DIGEST: a synchronous mode designed ideal for ho- mogencous training environments. (2) DIGEST-A: an asynchronous mode that better fits for heterogeneous training environment. DIGEST and DIGEST-A follow different parameter and rep- resentation updating strategies. DIGEST, for each global round, before fetching the aggregated parameters and pulling the stale representationns, each subgraph has to wait for other subgraphs to finish updating the latest parameters to the parameter server (PS) and their local representations to the KVS. However, some subgraphs may have lower computing resource compared to other
5

---

Under review as a conference paper at ICLR 2023
subgraphs, which call stragglers. This may lead to imbalanced local training times. In this case, with the synchronous mode, the overall training process can bottlenecked by the slowest subgraph, therefore suffering from prolonged training time. To address this issue, DIGEST-A applies asyn- chronous, non-blocking strategy, where each subgraph directly pulls/pushes stale representations of other subgraphs from the shared KVS and downloads/uploads, parameters from the PS without blindly waiting for the slowest subgraph to finish. For better scalability, we will explore disaggregated
storage techniques (Klimovic et al. 2016 Nanavati al.) 2017: Amaro et al.) (020) as part of our future work, where DIGEST can utilize detwork-attaches
far memory storage
system for representation storage and retrieval. We summarize our algorithm in Algorithm i the
appendix due to limited space.
In addition, DIGEST and DIGEST-A use several optimizations to minimize the I/O overhead intro- duced by pulls and pushes. First, we observe that there are large number of node representations involved in both pull and push operations, and more importantly, nodes are independent of each other on these two operations. Hence, is inherently suitable for parallel I/O at the granularity of node level. For subgraph 9m. the total number of stale representations needed to be pulled from the KVS is (E.m)))) Assume that it takes time / to pull the stale representation of one node, the total time cost out should be (f x being pulled serial. But with parallel I/O where needed representations are pulled in parallel, theoretically we can still keep the pull time for E V... as l. Additionally, we
observe that the pull operation for H (f.m)
can be overlapped with the forward process of layer (f,m) can be overlapped with the forward process of layer + 1.
similarly, the push operation for H in
The training process on each subgraph is depicted in Figure The cost of pull/push operations
hidden by the layer forward process, therefore, is eliminated.
Second, further reduce the I/O overhead, DIGEST uses a periodic representation syn- chronization strategy, which pushes up- dated representations to the KVS once ev- cry N epoches. This introduces a trade-off in I/O overhead and training performance. Increasing the frequency of the periodic synchronization will benefit performance, but this will introduce more I/O overhead. We analyze this trade-off in Section 5.2
Time
Round t
Round
PULL
H (24-11
H
(100 Aat
1
(1/+1)
osc
Forward
L1
L2
L2
L3
PUSH
H (2
H
(1:+1)
H (260))
Figure 2: Illustration of DIGEST's concurrent pull/push and forward propagation operations on a 3-layer GNN.
3.3 COMPLEXITY ANALYSES
Here we analyze the memory and communication complexity of DIGEST. DIGEST pulls the required out-of-subgraph node representations and keeps them locally for each local machine. For the mi-hh local machine and the corresponding subgraph it, i.e. 9m Em), the memory complexity per training iteration is O( ([ N(v) {x) Ld). which scales linearly with respect to the number of GNN layers. DIGEST's communication cost per round can be expressed ((M Ld
ΣM UvEV ((u) \ Vm Ld + NL). Again, the communication cost of DIGEST is only linear with respect to GNN depth L.
THEORETICAL ANALYSES
In this section, we provide theoretical analyses of the propose distributed strategy DIGEST, including the bound of error induced by the staleness of node representations, and convergence guarantee for DIGEST under both synchronous and asynchronous settings. All proofs can be found in the appendix.
4.1 ERROR BOUND ON GLOBAL APPROXIMATED GRADIENTS
Our first theorem shows that under the distributed setting, the approximation error of the global model's gradients can be upper bounded by the staleness of node representations.
Theorem 1. Given a L-layer GNN fw with r -ipischhitz smooth & and -i-sshhti smooth V.
Denote A (()) the maximal node degree for graph G. Assume V E V and V f (1,2, ... -L-

---

Under review as a conference paper at ICLR 2023
11 < cl9, where he (1) and h denotes the node representation computed by DIGEST and the stale one, respectively. Further assume each local loss function L is T-Lipschitz smooth w.r.t the node representation. Then, we have that [ VwL S
we have !
(T/M) Ei=l "
|A(G)) where VwL and W denotes the global gra- dient computed by DIGEST and the exact global gradient without any staleness.
4.2 CONVERGENCE OF SYNCHRONOUS DIGEST
As both fresh inner-subgraph and stale oft-of- -ubgrrah representations are adopted in our algorithm, its convergence rate is still unknown. We have proved the convergence of DIGEST and present the convergence property in the theorem blow. First, we introduce some assumptions:
Assumption 1. The loss function Loss(,,)) :) is CLoss-Lipchin contimuous and -Loos-Lipschit smooth
with respect to the last layer's node representation, i.e.. [Loss(h))) (1) ,Y.) Loss (I.) (h yy)l I
Loss h - b 1l2 and Lossss (1.) .y)) - Voss(hhi (1.) yu)lle I Looss |b h ( 112
Assumption 2. The activation function o-)) is Co-Lipchitz continuous and L. -Lpiscchittz smooth, i.e. (z(0) - ( (z.")) Ill S C. (Z)l 7,011e ll2 and [o'( - o' d'(2g") S To (o(l( 7 1l2-
Assumption 3. vt= 1,2,, Ir, we have [| S Kw, ||P(0 S Kw, | S Kx. Theorem 2. Consider GCN with L layers that is Ly-Lipschitz smooth. V > 0, 3 constant
E 0 such that, we can choose a learning rate 1 E - s.t., T T 2t=1 [ I O(T-0/11/ M 1-/s), where T (C(W()) [(W")) 7M
VMC and number of training iterations
E
W denotes the optimal parameter.
Our convergence rate of DIGEST is 2(T-2/33--/33 which is better than pipeline-parallelin parallelism method 22/3) (Wan et al. 2022) and sampling- based method ((2-1/2) (Chen et al. 2018
Cong et al. 2021 and very close to full-graph training ((
4.3 CONVERGENCE OF ASYNCHRONOUS DIGEST
Convergence for asynchronous distributed algorithms could be even harder obtain due to the delay in parameter's 's update (the global model's parameters may have been updated several times when the slowest local machine finishes its computation.) Our main result is shown below:
Assumption 4. V E [M], (VVm
I V. [V ll2. and (VL(W), V... Z 8. [[VC(W) Iig where V and B are positive real numbers, i.e. V Rt.
Theorem 3. Assume the global model L(W) is Cy-Lipschitz continuous and the delay is bounded,
V2 > 0. There exist constant B and second-order polynomial of learning rate y,, i.e., P(π) such that after T global iterations on the server, asynchronous DIGEST (1TT) ((W(+))) + P where B 3 and P(n) = 1n K2 (1+ (1+V)nK
i.e., T < K. Further, assume 3 z
converges to the optimal parameter W by T-1 Et (V((W)))
V2
5 EXPERIMENTS
In this section, we evaluate DIGEST and compare DIGEST against two state-of-the-ee distributed GNNs training frameworks as baselines in terms of training efficiency and scalability. Considering the distinct training time per epoch between DIGEST and other baselines, we report the Fl scores on validation dataset and training loss over training time, instead of over communication rounds, in the results. This way it makes fairer comparison in terms of training performance and efficiency.
5.1 EXPERIMENT SETTING
Implementation and Setup. We have implemented DIGEST and other comparison GNNs training methods all in Py Torch (Paszke et al. 2019). For all the experiments, we simulate a distributed training environment using an EC2 g4dn. metal virtual machine (VM) instance on AWS, which has 8 NVIDIA T4 GPUs, 96 vCPUs, and 384 GB main memory. We implemented the shared- shared-memory KVS using the Plasma in-memory object store" for representation storage and retrieval.
html
7

---

Under review as a conference paper at ICLR 2023
Training LoSs
Teghil Las
Training Loss
1.
Training
1.
0:94
0.70
Validation
Validation
0:35
Valiciatoon
Validation
LLCG DGL
LLCG
LLCG
LLCG DGL
8.40
DGL
DGL
DIGEST
DIGEST DIGESTA
DIGEST
DIGESTA
625
DIGESTA
DIGESTA
6.50
356 15o 290 250
300
130
300
200
0.
25
555
350
1890
3230
6.2
202
420
500
360 3009
Training Timels)
Training Timeis)
Training Timels)
Training Time(s)
(a) OGB-Arxiv
(b) Flickr
(c) Reddit
(d) OGB-Producee
Figure 3: Performance comparison of the GCN training frameworks on four benchmark datasets. The top four subfigures show the training loss over training time, and the bottom four subfigures show the global validation scores during the whole training process. (Best viewed color.)
Table 1: Performance comparison of distributed GNNs frameworks. Fl score on validation dataset reported. Speedup is calculated by normalizing per-epoch training time against that of DGL.
Method
Metric
OGB--Ardv
Flickr
Reddit
OGB--Pooducts
DGB-Arriv
Flickr
Reddit
69.8
50.73 = 0.15
0.411
90.79
08.84
0.22
43.98
0.32
91.
0.17
Speedup
2.35x
0.88x
1.47x
1.306x
1.787x
0.523x
9.966x
Fl
69.9 0.11
0.13 50.9
87.12 0.23
91.01 1..12
70.34 0.17
51.50
0.27
92.58
0.12
DGL
Speedup
1x
1x
1x
1x
Fl
72 0.23
53.73
= 0.21
0623
91.35
0.1
08.33 0.11
52.08
I 0.21
61,9 0.15
DIGEST
Speedup
7.86x
3.006x
11.40x
21.817x
DIGEST-A
Fl
71.9 1 0.18
53.1 0.32
94.55
1. 0.37
91.34 1 0.1
69.04 a 0.13
52.16
16 0.17 93.95
0.22
Baselines. Recall in Section 2 we categorize existing distributed GNN training into two types of general methods. In evaluation, choose state-of-the-art distributed training frameworks, one from each category as the baseline. For the first category, we choose LLCG (Ramezani et al. [222]] which partitions graph into subgraphs and trains each subgraph strietly independently without incurring any communication among subgraphs. LLCG uses central server to aggregate local models from each device and performs global training using mini-batchis with full neighbor information to ensure that the model learns the global structure of the graph. LLCG uses this additional step to reduce the information loss caused by graph partitioning. For the second category, we choose distributed GNN training framework.
to use DGL (Wang et al. 2019). which is commonly- In contrast to LLCG, DGL requires exchanging node representations among partitioned subgraphs. DGL requires frequent swap operations with other subgraphs for representations during subgraph's local training each epoch, and therefore, DGL incurs high communication cost.
LLCG
14
0.990
Time/epachis
8-
DIGEST
DGL
Speeds
LLCG
Validatio
10
DGL
0325
DIGEST
0.00
10
20
0.055
200
420
to0
1000 1200
2600
4
Training Time(s)
OCB-Arsh
flterr
of GPUs
Figure 6: Synchronization inter- val. Better seen in color.
Figure 4: Training time/epoch.
Figure 5: Scalability.
5.2 EXPERIMENTAL RESULTS
In this section, we evaluate both sync & async versions of DIGEST, LLCG, and DGL on the four datasets. Due to the page limit, move parts of our evaluation results the Appendix.
8

---

Under review as a conference paper at ICLR 2023
Efficiency of DIGEST. We first evaluate the training performance of DIGEST and DIGEST-A. As shown in Figure 3 DIGEST outperforms both LLCG and DGL for all the datasets when performing distributed training a pure GCN. LLCG performs worst particularly for the Reddit dataset, because in the global server correction of LLCG, only a mini-batch is trained and is not sufficient to correct the plain GCN. This is also the reason why the authors of LLCG report the performance of complex model with mixing GCN layers and GraphSAGE layers Ramezani et al. (2021). DGL achieves good performance on some dataset (e.g., OGB-products) with uniform node sampling strategy and real- time representation exchanging. However, frequent communication also leads to slow performance increasing for dataset Flickr (Figure and poor performance for all four datasets. DIGEST and DIGEST-A avoid these issues and therefore achieve satisfying performance over the training time. DIGEST-A slowly catching up DIGEST due to the diverse model parameters used by subgraphs in the early training period.
We measure the training time per epoch as shown Figure Since the representation synchronization only performed before the start after the end of local training, DIGEST takes significantly shorter training time per epoch than that of LLCG and DGL. Furthermore, DIGEST performs periodic synchronization instead of per-epoch synchronization, which further shortens the training time.
Table I presents the detailed numbers for the comparison of three frameworks on the four datasets. For all the cases except GAT on OGB-Arxiv, DIGEST achieves leading Fl scores the validation dataset, demonstrating the efficacy of DIGEST's design.
Scalability of DIGEST. We evaluate the scalability of three frameworks by training a GCN on OGB-Products with varied number of GPUs. We use average training time per epoch against that of DGL with single GPU to calculate the speedup results. As shown in Figure 5 DIGEST shows the best scala- bility compared to the other two. The speedup rises with the number of GPUs used during training. We observe similar trend for DGL, but the relative speedup for DGL. is significantly smaller than that for DIGEST, due to the using of real-time representations instead of stale representations.
0.94
Validation F1
0.90
LLCG
0.86
DGL
DIGEST
0.84
DIGEST-A
Synchronization frequency. We next perform sensitivity analysis by varying the synchronization intervals for OGB- Products to study how the synchronization frequency would affect the training performance. As shown in Figure 6 DIGEST achieves the highest F1 score over training time when config- ured to perform synchronization of stale representations every 10 epochs. A large interval (20) or a small interval (1) results in performance degradation, due to the long term loss of graph information or additional communication cost.
0.02
500
1000
1500
2000
2500
Training Time(s)
Figure 7: Performance comparison of OGB-Products when trained in a heterogeneous environment.
Finally, test DIGEST's asynchronous training mode. As stated in Section 3.2, asynchronous training is better suited for GNN training in heterogencous environments. this test, we randomly select one subgraph the straggler before the training starts, To simulate the straggler lagging caused by limited computing capability, a random delay ranging from 10 seconds added the chosen straggler during the whole training process. We can see from Figure 7 that DIGEST-A performs much better than other three synchronous methods and converge to high FI-score at the early stage of the training. This is because asynchronous mode effectively eliminates GPU's blocking caused by waiting with significantly improved GPU utilization.
Training in heterogeneous environment.
6 CONCLUSION
There are two general categories in distributed GNN training. Partition- based methods suffer from graph information loss, while propogation- methods suffer from high communication cost. In this work we present DIGEST, novel distributed GNN training framework that synergizes the complementary strengths of both methods by leveraging stale representations intelligently. We provide rigorous theoretical analysis prove that DIGEST has competitive convergence rate and bounded error due to staleness. Extensive experiments on four benchmark datasets validate our analysis and demonstrate the efficiency and scalability of DIGEST.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Emmanuel Amaro, Christopher Branner-Augnn Augmon, Zhihong Luo, Amy Ousterhout, Marcos K. Aguil- cra, Aurojit Panda, Sylvia Ratnasamy, and Scott Shenker. Can far memory improve job throughput? In Proceedings of the Fiffeenth European Conference on Computer Systems, EuroSys '20, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450368827. 10.1 10.1145/3342115.338777
doi:
org/10. 1144/ 0e1./442155.3375559 3387522
Alexandra Angerd, Keshav Balasubramanian, and Murali Annavaram. Distributed training of graph convolutional networks using subgraph approximation. arXiv preprint arXiv:2012.04953 2020.
Niel Chah. Freebase-triples: A methodology for processing the freebase data dumps. arXiv preprint
arXiv:1112.08777, 2017.
Zheng Chai, Yujing Chen, Ali Anwar, Liang Zhao, Yue Cheng, and Huzefa Rangwala. Fedat: a petthrrerrrmmce and communication-cffiiene federated learning system with asynchronous tiers. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-16, 2021.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference Machine Learning, pp. 942-950. PMLR, 2018.
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint arXiv:1604.000
2016.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 IEEE International Conference on Big Data (Big Data), pp. 15-24. IEFE, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gon gen:t An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 257-266, 2019.
Sangjin Choi, Taeksoo Kim, Jinwoo Jeong, Rachata Ausavarungnirun, Myeongjae Jeon, Youngjin K Kwon, and Jeongseob Ahn. Memory harvesting in Multi-GPU systems with hierarchical unified virtual memory. 2022 USENIX Annual Technical Conference (USENIX ATC 22), pp. 038-638. Carlsbad, CA. July 2022. USENIX Association. ISBN 978-1-939133322966 URL https
7/www. usenix wwwp///o//oooooooooo http:///cceeeeeeeeee///eeeeeeeee
choi -sagiiins
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the importance of sampling in learning graph convolutional networks. arXiv preprint arXiv:2133.02690 2021.
Hanjun Dai. Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In International conference machine learning, pp. 2702-27 1. PMIR, 2016.
Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. Pixie: A system for recommending 3+ billion items to 200+ million users in real-time. In Proceedings of the 2018 world wide web conference, pp. 1775-1784, 2018.
Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning, pp. 3294-3304. PMLR, 2021.
Swapnil Gandhi and Anand Padmanabha Iyer. P3: Distributed deep graph learning at scale. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pp. 551-568. USENIX Association, July 2021. ISBN 978-1-939133-22-9 URL httttttt///ww/ www.:////wwuuuixix
http://seeeeeeeeeeeeeeeaa. iandhi
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2023
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Weihua Hu, Matthias Fey, Marinka Zimikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18-22213, 2020.
Chien-Chin Huang, Gu Jin, and Jinyang Li. Swapadvisor: Pushing deep learning beyond the gpu memory limit via smart swapping. In Proceedings of the Twenty-Fifth International Con- ference on Architectural Support for Programming Languages and Operating Systems, ASP- LOS '20, pp. 1341-1355, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 470340057 doi: 10. 12111///373376.33788830 URL.https://doi wttp//i.oog//.1.1////111 3373376. 3378530
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy. scalability, and performance of graph neural networks with roc. Proceedings of Machine Learning and Systems, 2:187-198, 2020.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):35--392, 1998.
Thomas Kipf and Max Welling. Semi- semi--upervised classification with graph convolutional networks. arXiv preprint arXiv:
2016.
Ana Klimovic, Christos Kozyrakis, Eno Thereska, Binu John, and Sanjeev Kumar. Flash storage dis- aggregation. In Proceedings of the Eleventh European Conference Computer Systems, EuroSys '16, New York, NY. USA, 2016. Association for Computing Machinery. ISBN 9781450342407. doi: 10. 10.1145/2901311 29011999777 URL doi wtg/1..rg11... 1145/ 2901318 2901337
Kai Lei, Meng Qin, Bo Bai, Gong Zhang, and Min Yang. Gen-gan: A non-linear temporal link prediction model for weighted dynamic networks. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications, pp. 388-396. IEEE, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450 2020.
Lingxiao Ma, Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. [NeuGraph]: Parallel deep neural network computation on large graphs In 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 443-458, 2019.
Mihir Nanavati, Jake Wires, and Andrew Warfield. Decibel: Isolation and sharing in disag- gregated Rack-Scale storage. In 14th USENIX Symposium Networked Systems Design and Implementation (NSDI 17), pp. 17-33, Boston, MA, March 2017. USENIX Association. ISBN 978-1-931971-37--. URL https: http://wwwwww..wi.o/// usenix wttp:///oo.eeeeeeessail.... Bechhiccl-eeesstssspppeeerattta-
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Xuan Peng, Xuanhua Shi, Hulin Dai, Hai Jin, Weiliang Ma, Qian Xiong, Fan Yang, and Xuehai Qian. Capuchin: Tesser-based gpu memory management for deep learning. In Proceedings of the Twenty-Fifh International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '20, pp. 891-905, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371025.
doi: 10.11453373376.338500 URL
https://dde //o:: org/10. 100.0.11453330 wtt.://o./....1133333331
3378505
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Mahmut T Kandemir, and Anand Sivasubrana- niam. Learn locally, correct globally: A distributed algorithm for training graph neural networks.
arXiv preprint arXiv:21/1.0880 (tt::2////000022 2021.
11

---

Under review as a conference paper at ICLR 2023
John Thorpe. Yifan Qiao, Jonathan Eyolfson, Shen Teng, Guanzhou Hu, Zhihao Jia, Jinliang Wei, Keval Vora, Ravi Netravali, Miryung Kim, and Guoqing Harry Xu. Dorylus: Afford- able, scalable, and accurate GNN training with distributed CPU servers and serverless threads. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2/), pp. 495-514. USENIX Association, July 2021. ISBN 978-1-939133-22-9. URL https
www. usenix http:////.ooteeeeeeoooo/ee/aaaae
Alok Tripathy. Katherine Yelick, and Aydın Buluç. Reducing communication in graph neural network training. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14. IEFE, 2020.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Cheng Wan, Youjie Li, Cameron R Wolfe, Anastasios Kyrillidis, Nam Sung Kim, and Yingyan Lin. Pipegen: Efficient full-graph training of graph convolutional networks with pipelined feature communication. arXiv preprint arXiv:2203.10422 2022.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprini 1909v0090.00133 2019.
Yuke Wang, Boyuan Feng, Gushu Li, Shuangchen Li, Lei Deng, Yuan Xie, and Yufei Ding. GN- NAdvisor: An adaptive and efficient runtime system for GNN acceleration on GPUs. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pp. 515-531. USENIX Association, July 2021. ISBN 978-1-939133-22-- URL wwt.htttps//// www hwtp://wwww..i.x..o//////.
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 on knowledge discovery data mining, pp. 974-983, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint D0XXiv:9977049999 2019.
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. In 2020 JEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), pp. 36 44. IEEE, 2020.
Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Ree Liu. Asynchronous stochastic gradient descent with delay compensation. In International Conference on Machine Learning, pp. 4120-4129, PMLR, 2017.
Rong Zhu, Kun Zhao Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. Aligraph: comprehensive graph neural network platform. arXiv preprint arXiv: 1002:1990.0000 087300 2019.
12

---

Under review as a conference paper at ICLR 2023
A APPENDIX
In this section, we clarify our contributions made in this work and describe detailed experimen- tal setup, additional experimental results, and complete proofs. We reuse part of code adopted from GNNAutoScale Fey et al. (202T); our code is available at: btttps://anoyymouu 1.es..oppp 4open seience/r DAIcee//DDIESSA--PEEE prove the readability.
Please note that the code is subjected to reorganization to im-
A.1 CONTRIBUTIONS AND NOVELTY
The contributions and novelty of this work are multi-fold. In this paper, we propose a new, highly- parallel, and full-graph-aware distributed GNN training method; on top of this new method, design novel, allow distributed GNN training to potentially benefit from emerging computing paradigms and hardware; finally, we deduce new theoretical guarantees and analyses for the co-designed algorithms and systems.
training system to enable better scalability and
(1). Methodology Novelty in Algorithm-System Co-design: Our paper is mainly motivated from distributed training perspective, where the proposed framework synergizes the best of both partition-based and propagation-base foundation, which exposes potential opportunities that can be harnessed by and co-designed with new distributed training system infrastructures to enable goes beyond GNNAutoScale in that we built a novel distributed training framework that effectively decouples the management of state (i.e., representations) and compute (i.e., GNN training).
distributed training; GNNAutoScale provides a theoretical
GNN training. DIGEST
(2). System Architecture Novelty: The disaggregated architecture of DIGEST is the result of an algorithm- system do-design mentioned in the Methodology Novelty, and enables great properties including high scalability and low training time, as demonstrated in our paper. More importantly, this disaggregated architecture could enable fundamental opportunities for GNN training systems to take advantage of emerging computing paradigm such as elastic serverless computing as well as emerging hardware such as Zoned Namespace SSD (ZNS) and smart programmable network hardware (SmartNIC); in this work, we have shown the promising scalability and speedup that DIGEST offers, which establishes a solid system foundation for further system-level optimizations and innovations. This demands//nspires future research along the line, which we plan to do as part of our future work.
All of our theoretical analyses are tailored for distributed training setup, while GNNAutoScale only considers single-GPU training.
(3). Theoretical Novelty:
A.2 EXPERIMENTAL SETUP DETAILS
As mentioned in Section 5.1 all the experiments are done on EC2 g4dn metal virtual machine (VM) instance on AWS, which has 8 NVIDIA T4 GPUs, 96 vCPUs, and 384 GB main memory. Other important information including operation system version, Linux kernel version, and CUDA version is summarized in Table For fair comparison, we use the same optimizer (Adam), learning rate, and graph partition algorithm for all the three frameworks, DIGEST, LLCG, and DGL.. For parameters that are unique to both LLCG and DGL, such as the number of neighbors sampled from each layer for each node, we choose the default value for both LLCG and DGL. Each of the three frameworks has a set of parameters that are exclusively unique to that framework; for these exclusive parameters, we tune them in order to achieve the best performance. Please refer to the configuration confconf/ / /moee 1 for detailed configuration setups for all the models and datasets.
files under run/ conf
Table 2: Summary of environmental setup of our testhed.
OS Ubuntu 18.04
Linux kernel
CUDA
Driver
PyTorch
PyTorch Geometric
PyTorch Sparse
5.4.0
11.6
510.47.03
1.10.0
2.0.4
0.6.13
We use four datasets: OGB-Arxvv Hu et al. (2000), Flickr Zeng et al. (2019), Reddit Zeng al. (2019) and CGB-Products Hu et al. (2000) for evaluation. The detailed information of these datasets summarized in Table
13

---

Under review as a conference paper at ICLR 2023
Table Summary of dataset statisties.
Dataset
Nodes
# Edges
Features
Classes
Train % Validation % Test %
Flickr
89,250
899,756
500
50% 25% / 25%
Reddit
232.965
23,213,838
602
41
66% / 10% / 24%
OGB-Arixi
169.343
2.315,598
128
40
53.7% 17.6% 28..7%
OGB-Products
2,449,029
123,718,280
100
47
8% 2% / 90%
3.5
3.5
10
3.0
Training Loss
Training Loss
Training Loss
2.5
2.0
1.0
1.5
0.5
1.0
0.75
1.0
0.54
0.52
0.8
Validation F7
0.05
Validation F1
Validation
0.50
0.60
0.48
LLCG
LLCG DGL
DGL DIGEST DIGEST-A
DGL DIGEST
0.50
DIGEST DIGEST-A
DIGEST-A
8.40
0.40
50
100
150
200
50
160
150
200
50
100 150
260
230 300
Training Time(s)
Training Time(s)
Training Time(s)
(a) OGB-Arxiv
(b) Flickr
(c) Reddit
Figure 8: Performance comparison of different distributed GAT training methods four benchmark datasets. The top three subfigures show the training loss during the whole training process; the bottom three subfigures show the global validation Fl scores during the whole training process.
A.3 ADDITIONAL EXPERIMENTAL RESULTS
A.3.1 PERFORMANCE GAT TRAINING
We first show the learning curves of training GAT with three methods on three different datasets. As shown in Fig- ure g for dataset Flickr and Reddit, DIGEST acheives the best validation frameworks. For dataset OGB-Arxiv, the performance of DIGEST is slightly worse than DGL but still outperforms LLCG. Specifically, LLCG's training curves are not sta- ble and fluctuate dramatically for both GCN and GAT on Reddit. This because Reddit is much denser compared to other datasets, and in this case, the sampling process of the global server correction in L.LGG has difficulty captur- ing all the information loss due to the cut-edges. Unlike LLCG, DIGEST's training curves are much smoother not only for GCN training but also for GAT training.
140.39
140
score over training time of all the three
120
110.61
Memary Ratio(%)
100
80
58,43
40
35.87
20
Arii
Flickr
Reddit OGB- Products
A.3.2 MEMORY OVERHEAD
Figure 9: The average ration of the num- ber of sub-oaa-ub nodes to the num- ber of in-subgraph nodes when training a GCN over the four datasets.
In this section we quantify the memory overhead intro- duced by DIGEST.
14

---

Under review as a conference paper at ICLR 2023
Ratio of out-of-subgraph nodes and in-subgraph nodes.
Figure[ishan shows the ratios of the number of -fu-o---u nodes to the number of in-subgraph nodes across four datasets. This ratio quantifies additional memory consumption compared to methods that does not use any information of the neighboring nodes during training.
Denser graphs like Flickr and Reddit require more memory to store representations of off-subgraph nodes than OGB-Arxiv and DGB-produee memory storage and gained benefits in reduced communication and preservation of global graph information. We argue that modern GPU servers are equipped with ample GPU memory resources to buffer the out-of-subgraph representations Gandhi Iyer (202T); y Wang et al. (202T); if indeed more memory is required, our research will benefit from the recent advancement of unified memory Choi et al. 2022); Huang et al. (2020): Peng et al. 2020). where DIGEST can use both the host and GPU
This introduces an interesting tradeoff between extra
memory more efficiently.
In the worst case, GPU memory limited, DIGEST can implement a multi-tier storage system that uses the limited memory level-one cache and the host memory backing store. For large graphs that are sparse (OGB-pu JoGo-productt), the extra memory cost can be bounded to a relatively lower ratio (3%...).
Host memory cost of stale representations. The KVS is responsible for storing the representations of all the nodes in graph. The representations are stored in the memory of the host server instead of the GPUs, the latter of which is rather limited. We implemented the in-memory KVS with Apache Plasma, which is a shared memory storage that supports efficient, communication (IPC) for multiple training processes located on the same server. However, extending our current KVS implementation to fully-distributed storage system is trivial. Using off-the-shelf, high-performance distributed in-memory KVSes such as Redis is one option. Alternatively, we could also implement simple client library, which can be used by the training process for key-value item mapping ge using the commonly-used consistent hashing algorithm) and remote representation retrieval/storage, and with the client library, we could deploy a cluster of Plasma storage processes either on a dedicated storage cluster or on the same training server cluster to support distributed representation storage.
inter-process
The overall memory consumption required to store representation data can be calculated with the following equation:
KVS memory usage- (L. 1I x dim x V
where I. is the total number of layers of the model, dim denotes the hidden dimension, |V| represents the number of nodes in the graph, and s is the size of data type in Python numpy. For the float32 data type, it takes 4 bytes for each single value. With the provided formula, for a 3-layer GNN model, training large graph dataset such as OGB-Products (with 2, 449, 029 nodes and 128 hidden dimensions), the extra host memory consumption for the representations is around 2 128 * 2449029 4/ 4/1024/1000 10////024///00 1024 2.336 GB. DIGEST exhibits interesting tradeoff: it uses small amount of extra memory overhead for storing stale representations to enable the disaggregation of the compute and storage for higher scalability and more flexibility. We also argue that a small host memory cost of several GBs is negligible considering today's 's multi-GPU servers are equipped with hundreds of GBs if not more than a few TBs of host memory"
Table 4: GPU memory consumption.
Model
OGB-Arxiv
PGoduuossucs
GraphSAGE
0.40 GB
0.92 GB
DGL
0.64 GB
1.78 GB
LLCG
0.23 GB
0.36 GB
DIGEST
0.22 GB
0.36 GB
'For example. AWS EC2's p3. 16.1agee is equipped with 8 Nvidia Tesla V100
GPUs
with 488 GBs of host memory: https://aws amazon com/b bl ogs/ /ww/
new- lox-amazoo--el2 1et2--iinnanccesiithhee www---oo----iiiannneeeeee -pps-pppppppp3333
15

---

Under review as a conference paper at ICLR 2023
GPU memory consumption. For the concern of GPU memory consumption, compare DIGEST with GraphSAGE, LLCG, and DGL by including all the information inside a GNN's receptive field in single optimization step. The comparison results in Table A that DIGEST has the lowest GPU memory consumption across all four systems.
A.3.3 EMPIRICAL VALIDATION OF GRADIENT APPROXIMATION ERROR
In this section, we empirically evaluate the gradient approximation error due the usage of stale representation. We conduct this experiment to show that the actual approximation error of gradients of DIGEST compared with the ground-truth gradients (i.e., gradients calculated without any stale representation) can be negligible in practice.
02
Gradient Error (MSE)
Gradient Error (MSE)
12
25
52
75
100
125
150
175
200
25
50
75
185
325
150
175
703
Training Epoch
Training Epoch
(a) OGB-Arxiv
(b) Flickr
Figure 10: Error between the gradients calculated by DIGEST and full-graph baseline (i.e., without any staleness). Zoom in for detail.
As can be seen in Figure TO, during the training phase the gradient calculated by DIGEST quickly converge to the ground-trute gradients typically after fewer than 10-20 epochs. Hence, for the majority training epochs the error of gradients very small and the impact is negligible, which in turn validate our theoretical analyses in Theorem |
A.3.4 OTHER COMPARISONS
In this section, we compare DIGEST/DIGEST- with PipeGCN and GNNAutoScale. We train OGB- Products with DIGEST/DIGEST-A PipeGCN and GNNAutoScale in the heterogeneous environment mentioned in Section 5.2, and report the training time taken to reach the target validation Fl score and time per epoch in Firgure TI since there is "epoch" in asynchronous setting, the value of time per epoch for DIGEST-A A is omitted. We can see that DIGEST gets slight higher time epoch than GNNeutoScale but reduces the time per epoch by 24.13% compared with PipeGCN, Meanwhile, DIGEST-A gets the lowest training time to reach the target F1 score and saves 48.98% and 19. 12% training time compared with PipeGCN and GNNAutoScale, respectively.
We further evaluate DIGEST, PipeGCN and GNNAutoScale on a large graph AGB-papers 100m 100m which consist of 111 million nodes 1.6 billion edges to show the efficiency DIGEST. The experiments are done in homogeneous environment with 32 GPUs. Since mini-batches in GNNAutoScale are trained serial manner instead of a parallel distributed setting, only one GPU is used. DIGEST reduces the time per epoch by 23.13% compared with distributed GNN training algorithm PipeGCN.
A.4 ALGORITHM
Algorithm I shows the process of DIGEST's synchronous mode. At the beginning of training, the original graph is partitioned into several subgraphs with off-the-shelf graph clustering methods;
16

---

Under review as a conference paper at ICLR 2023
2152.00
124.40
2000
120
PipeGCN GNNAutoScale DIGEST
1795.90
Training time(s)
Time/epoch(s)
100
1500
80
1132.70
1000
916.12
60
40
500
20
15.87
11.70.2.04
5.60
0
PipeGCN
DIGEST DIGEST-A
Products
OGB-papers100m
(a) Training time to reach the 91% validation F1- score on OGB-Products
(b) Time/epoch comparison
Figure 11: Time comparisons with PipeGCN and GNNAutoScale.
DIGEST uses the widely-used METIS algorithm Karypis & Kumar (1998) Then the mini-batches are distributed to distinct workers, each of which handles training on a GPU device. Depending on the multiple subgraphs. DIGEST has two types
size of the mini-batch, single worker can handle of 1/Os: storing and retrieving the model weights and stale representation as illustrated in Figure is performed for each epoch by aggregating all the model weights of other subgraphs in parallel (Line 13). For the stale representation synchronization, we synchronize every N epochs, where we empirically tune N obtain the optimal performance over training time with the defined pull and push operations (Lines 1,6,9,10). To support the asynchronous mode (DIGEST-A), we can simply remove the loop of training epoch and move the parameter aggregation (Line 13) into the subgraph loop.
The former
A.S THEORETICAL PROOF
In this section, we provide the formal proof for all the theories presented in the main paper.
A.5.1 PROOF OF THEOREM
Theorem 4 (Formal version of Theorem D. Given L-layer GNN fw with r ri-Lipschitz smooth & and Li-iiicciitz smooth V. Denote (G)) ) as the maximal node degree for graph G. Assume E and V & {1, 2, L 1} have [lh (() S (()) where he and h. denotes the node representation computed by DIGEST and the stale one, respectively. Further assume each local loss function L is T T-Lipschitz smooth w.r. node representation. Then the global gradient computed by DIGEST has the following error bound
L-1
M
VWC - C
10
AG
(8)
M
where
VWC
1
Σ
V Clocol (b(
M
Vm
and
VwL
1 1
Σ
Σ
V Clocol (h" (L)),
(10)
M
[vml
VEVm
where (f) denotes the exact output from the E-th layer of GNN without any staleness.
Proof. As stated in Theorem 2 in Fey et al. (20TI). under the single-GPU training setup. with Lipschitz smooth & and V well not stale node representations, the GNN last layer's output
17

---

Under review as a conference paper at ICLR 2023
Algorithm Distributed GNN training with periodic stale representation synchronization
Input: Graph G(V,E) E); GNN depth L; training epoch R; global parameters W = +W
local parameters / [wls JE=1 m [M].r [A]; non-linearity activation
function o; neighborhood function A : + 2V; synchronization interval N; learning rate
Output: The trained model weights W(R+1)
DIGEST ():
Initialize W(1)
(9m() m 1, .., M] t- METIS(()
> graph partition
for R...R
for m = 1, .... M in parallel do
W W(r)
for I...L do
if % N = 0 and E + L then
(f.m) H (f.m) out
PULL
out
for v E Vm do
h h [h! a (N(u) Vmn
h (hl E ((() n
h (win CONCAT(b, (2) h h h
if 1) % N and f then (m)))
H (f.m)
10
PUSH
11
+ h / 112. V Vm
> representation normalization
W (x++1)
(r. 17 Whh.
update local parameters
W(- AGG(W( (r+1)
(r+1) .... ((r+!))
update global parameters
return (R+1)
14
can be bounded by
[ h (L)
T- I- (-((()) T2
(11)
Now consider the distributed GNN training setting, First, notice that in our distributed setting, the stale node representation ((99) is shared for all subgraphs. In other words, for m 1, 2,., M we can apply the conclusion above with the Lipschitz smooth asumption and have
V CLocal (h(a) (L(()) Ww (h (1))
ST h - h-((1)
L-
(12)
ST Σ
Notice that (W(w) < (GGm), v Vm, where A(Gm) is defined the maximal node degree for subgraph Gm. We can sum over all nodes E Vm and take average on both sides of Eq 12 to get
1-1 10
Σ
V V (h( Vw CLoad (h (n
ST
Σ
1
A-0 (13)
|m
18

---

Under review as a conference paper at ICLR 2023
Finally, since apply average to aggregate each local subgraph's gradient to get the global gradients, by the triangle inequality, we have
Vw - Vw
1
W
( (h()))
Σ
V w
(L)) (h (())
(h
M
Vml
M
Vm
m=1
VEV..
M
1
V Vw Chocaal(h
V
Coocal
M
Vml
1m
(14)
veV.
2
M
V W Cla - Vw C/
Clocal (h (L)
M
V
m
VVVm
1
Σ
10
1 Ammml 1m 6ー
M
which finishes the proof.
A.5.2 PROOF OF THEOREM 2
In this section, we prove the convergence of DIGEST under the synchronous setting. First, we introduce some notions, definitions and necessary assumptions.
Preliminaries. We consider GCN in our proof without loss of generality. We denote the input graph (V, E), L-layer GNN f, feature matrix X, weight matrix as W. The forward propagation of one layer of GCN is
z (((0, H(++1)= =o((1)
(15)
where l is the layer index, is the activation function, and P the propagation matrix following the definition of GCN (Kipf & Welling 2016). Notice H = X. We can further define the (e + 1)-th layer of GCN as:
f(++1) w(0) = ((1)
(16)
The backward propagation of GCN can be expressed follow:
d V н ((+1)((H())
wlf.. (o = pT PTD(
(17)
d(--1) Vw ((t))))) w ((+))) (PH())
(18)
where
p(e+1)= = G
oo (PH
(19)
and o represents the Hadamard product.
Under distributed training setting, for each subgraph 9n (Um, Em), m 1.2,...,, M, the propagation matrix can be decomposed into two independent matrices, i.c. p= Pm,in + out where P. Pm.in denotes the propagation matrix for nodes inside the subgraph Gm while Pm,out denotes that for neighbor nodes outside Gm- If it will not cause confusion, we will use Pnn and P Pout in our future proof for simpler notation.
For DIGEST, the forward propagation of single layer of GCN can be expressed as
(0,+++1 -P,,, -t. + Poux (1)
(20)
((,++1) = ((.0)))) m
where we use H differentiate with the counterpart without staleness, i.c., H (same for other variables). is the training iteration index. Similarly, we can define each layer as single function
f(e,e+1) (f W((..)) aPP,. (1.00) Paut
(21)
19

---

Under review as a conference paper at ICLR 2023
Note that A is not part of the input since it is the stale results from the previous iteration, ie., it can be regarded as a constant in the current iteration.
Now can give the definition of back-propagation in DIGEST:
G(t.f) H.m
V W WHJm
100 (H W(( 1,0,,,H,, )
(22)
P. ( +Pow (e0--e+))((W m
m
Vw -wJeett 1( (1..++1) WiL0 ((LEEt) H,m
(23)
Para Po = (Pon H
where D(L++1 =
= GH.m o (P m + Pout H -
(24)
H.m
In our proof, we use ((W()) to denote the global loss with GCN parameter W after iterations, and use L. (W(h)) to denotes the local loss for the m-th subgraph with model parameter wi(f) after t iterations computed by DIGEST.
Assumptions. Here we introduce some assumptions about the GCN model and the original input
graph. These assumptions are standard ones that are also used in (Chen et al. 2018 Cong et al. 2021 Wan et al. 2022).
Assumption 5.
The loss function Loss(-)) -) is Loos Loeos-Lipphii Lipchitz continuous and Loss Liasa--Lppchhisssmmoan smooth with respect to the last layer's node representation, i.e.
Loss(h (1), yy)) - Loss(h (1) ,y)) S CLossllh -h("1 l|2
(25)
and
Losss(( (4) y.) Loss(hh! ,.)llz S L ( bL 1|2
(26)
Assumption
The activation funncton (-) is Ci-Lipchitz continuous and Lipschitz smooth, i.e.
- - -2,01 and
La Lo (12
||2
(27)
Assumption 7. V that l 1,2,... we have
|| & Kw: ||p(0]]r S Kw, |X S Kx.
(28)
Now introduce the proof of our Theorem We consider GCN with L layers that is Ly-Lipschitz smooth, i.e., [)V((W)) - VL(W2)ll S L W2l12- Theorem (Formal version of Theorem 2}. There exists constant such that for any arbitrarily VMce and number of training iterations small constant > O, we can choose learning rate E
(C(W()) [(W*)) V
#, such that
T (VCWW
Σ
O
(29)
T
T
where (00 and W* denotes the parameters at iteration and the optimal one, respectively.
Proof. Beginning from the assumption of smoothness of loss function,
((Wi+1) < L(W') + (VL(W)) w(++1) - w(0) -w(+))-W())
+ Lg - -
(30)
2
Recall that the update rule DIGEST is
M Σ
((++1) = ((()) TJ
Vim (e)
(31)
M
m=
20

---

Under review as a conference paper at ICLR 2023
we have
+ by
L(W") ( (
- -
1
-
-m mn (VE(W"). Σ M
M
Vim (W,11) )
M
(32)
=L(W")
Σ
v Lm (
M
Denote 6/1) v ( - VLm V. (Will)), we have
f(W SR(W")
VL(W"),
1
Vm. (W + +550)
M
m=1
(33)
r + 2
L
M
2
Lm (Wi()) + 8(()
+
M m=1
Without loss of generality, assume the original graph can be divided evenly into M subgraphs and denote = [V] as the original graph size, i.e., M S, where each subgraph size. Notice that
N N
M
s
VL(W)
=
(oss(()) ,3:) = M
V Loss( (11.) Bm.si)
(34)
m=
which is essentially
1 M
VC(W")
v Vm (W(!))
(35)
M
m==
Plugging the equation above into Eq. 33 we have
L
<(W*-1) -
8(t)
(36)
2
M
which after rearranging the terms leads
M
|V 2 (CG[W))-((Wt)))) + nLا
Σ m=11
(37)
M
m
By taking y < 1/L,, using the three assumptions defined earlier and Corollary A.10 in Wan et al. (002)) and summing up the inequality above over all iterations, i.e., 1,2, T, we have
T
(C(W))- - L(WT+1)) ( + F22
VL(W(9))2
T
n/T
M
(38)
(C(W)) L(W")) + E2 < T/T
M
where 4 denotes the minima of the loss function and E' is a constant depends on E",
Finally, taking 17 /M and T (C(W()) L(W*)) E e finishes the proof.
A.5.3 PROOF OF THEBOREM 3
By following Li et al. 2020); Chen et al (000): Chai et al. 2021 we make the assumption as below: Assumption 8. A
[M]. / (W) < V VV llz. and (VL(W), VL.. 2 3. (VV((W) g where V and positive real numbers, ie, V, IR..
21

---

Under review as a conference paper at ICLR 2023
We naturally assume that each local copy of the global GCN model is also Ly Lipsschhit smooth, i.e., | (Wi)- v.m. (W2)ll2 S L W2ll2. V m 1.2, MM
Now we can give the proof of Theorem Theorem 6 (Formal version Theorem
Assume the global model L(W) is Cy-Lipschitz contin-
wous and the delay is bounded, i.e., T < K. Further, assume the constants defined in Assumption g
satisfy 3 - V22 0. Then, after T global iterations on the server, asynchronous DIGEST converges al to the optimal parameter W by
1 (C(W())- (((()))) P(n) TTTB where = 33 2 and P(n) k + (1+
1
(39)
B
V2
Proof. By the smoothness assumption of global model,
((w(++1)) S ((W(()) + + (VL(W(()) w((+1) - w(()
L 2
|w(+))
1
(40)
Suppose at global iteration & + 1, the server receives an update from subgraph m, where m could be any value from up to M. Then,
Sا 2
L(W S L(W(()) v (VL(W(()) (mm(((
[
)|
(41)
where T the delay for subgraph m when sending server its update.
Denote I'm = VLm Vmm((--r)) v (W()). Since S K, by the Lipschitz smoothness of 6.s
||mm 122 | | (W(--T)) v (W()))l2
s Ly ||W()- w 1|2
(42)
Ly Σ 1oll12
S ,H,,C where 9: is the gradient or update the global server receives at iteration i. Therefore,
((w(t+))) L(W(())
TP
--n (VC(W()) vêm (w(()) + +rm)
| (w(())
+ rmml
2
=-n VL(W(()) V.n (W/l)) T2L1 V Em (WV
2g
m 11
(43)
2
(CC(W(O)TTm) Ls (Vm Tm
Now we want to find bounds for (I - V) above.
By Assumption
g we have
(I) < - VL (1)
(44)
and
(II) < 12
(45)
By our previous result on ||rmlll we have
< 12,03 (III)
(46)
22

---

Under review as a conference paper at ICLR 2023
Taking 77 $ 1, have
(IV) (V) S (V (W())) 1 VL(W(())
(47)
By Cauchy- Schhhat-- incquality, triangle inequality and Assumption 8
(IV) S ( VL(W(9))l2 ||rmll2
S k (VVm - - [V
k /V
(48)
S <1L+V)
Put everything together, we have
((W(+1))- L(W(1)) - (((W()))
1, 1118--18)
|[ + 1 | +
(49)
Hence,
[VC(W())1 - n/3 2 2712)
(C(W()) ((w(ttt((())))))
(50)
n 2 V713
Summing up from = 1 to T and taking the average.
FL(W")) <
((W()))-(((()))
[113 1
+ n/3 2 )11z)
1
+
(51)
(CW())- + P(n)
< 1/BB
B
where = 333-1 V2 2
and P(r) = -
23


Reviews:
[{"review_id": "w-uJosYVlGf", "reviewer": "Reviewer_2my9", "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": "", "summary_of_the_paper": "This paper proposes a method to achieve a trade-off between information loss(partition-based) and communication cost(propagation-based) distributed GNN training. The key design is to synchronize representation to an in-memory KV store periodically with pipelined IO, so that the GNN training is aware of the full graph and without frequent communication overhead.", "summary_of_the_review": "This paper proposes a distributed GNN training framework by balancing partition-based and propagation-based distributed GNN training. The key designs are periodic stale representation synchronization with pipelined I/O. The results are convincing and I think the merits outweigh the flaws.", "strength_and_weaknesses": "Strengths:\n1. The distributed training of GNNs is an important problem. The motivation of this paper is clear and the proposed method is simple yet effective.\n2. The experiments show the speedup and scalability are good.\n3. This paper gives theoretical bound and convergence analysis of the proposed training method.\n\nConcerns:\n1. A question is, if the I/O is pipelined and hidden as in Figure 2, why is it still needed to sync **periodically**(as we should be able to sync in each epoch without much addition time cost)? And as shown in Figure 6, is there any way to determine or suggest the best synchronization frequency?\n2. This method proposed in this paper shows nice scalability in a single-machine multi-GPU environment. It could be more interesting if it could be extended to a multi-machines environment with nice scalability.", "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": "Z0D4BhexO5q", "reviewer": "Reviewer_xBXJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 considers the problem of distributed training of Graph Neural Networks (GNNs) over large-scale graphs. The authors proposed a framework called Distributed Graph Representation Synchronization (DIGEST), which leverages the stale representation of neighbors from other subgraphs to eliminate the information loss caused by dropped edges in partition-based methods and avoid communication overhead as in propagation-based methods. Specifically, the stale representations are stored in the central server and each subgraph communicate with the server to pull / push the stale representations during training. From system design perspective, the authors proposed both synchronous and asynchronous versions of DIGEST to further handle the straggler issue. Also, a key-value storage (KVS) design is introduced to implement the shared memory for the stale representations for better efficiency. Extensive theoretical analyses are provided, including convergence guarantee and the error bound of approximated gradients. Experimental results on several large-scale real-world graph datasets showed great performance and speedup of the proposed method compared with other distributed GNN methods.\t", "summary_of_the_review": "In summary, this paper delivered a non-trivial and meaningful exploration of distributed partition-parallel training of GNNs. Both system design and theoretical analyses are novel and interesting. Empirical results are provided with great performance. Also, the paper presentation is good to me. Hence, I would recommend accept of this paper. ", "strength_and_weaknesses": "Strengths:\n\n1.\tAs far as I know, the originality of this paper is good. Considering stale representation under distributed training of GNNs is interesting and important.\n\n2.\tThe proposed method is both theoretically and technically sound to me.\n\n3.\tThis paper makes non-trivial contribution on system design and implementation, including both synchronous and asynchronous variants of the proposed method, and the key-value storage (KVS) for stale representations.\n\n4.\tThe authors provided very extensive and novel theoretical analyses over the proposed methods. Convergence guarantees for both versions of DIGEST and the error bound of the approximated gradients due to the staleness are given with rigorous proof.\n\n5.\tThe empirical results show a significant speedup of the proposed methods compared with other state-of-the-art distributed GNN methods on large real-world graph datasets.\n\nWeaknesses:\n\n1.\tThe authors are encouraged to better discuss the motivations and technical details of the asynchronous version of DIGEST. Also, how is the algorithm of asynchronous DIGEST different from that of synchronous one as shown in Algorithm 1 in appendix?\n\n2.\tSince graph partition algorithms can play an important role in distributed partition-based training of GNNs, I am curious how does different partition affect the performance of DIGEST? \n", "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": "VPmHBRFWOt", "reviewer": "Reviewer_yVeu", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper introduces a distributed extension of GNNAutoScale (DIGEST) and proposes an asynchronous representation update mechanism (DIGEST-A) to reduce communication overhead for node embedding updates. Theoretical analyses such as forward error bound and convergence analysis are provided. Experiments show promising speedup in training time. ", "summary_of_the_review": "The paper introduces a simple and practical distributed GNN framework. Theoretical analyses are presented but concerns need to be addressed. Experiments demonstrate significant speedup but more baselines will be beneficial.  ", "strength_and_weaknesses": "# Strength \n\n1. The paper proposes a distributed GNN training framework that synergies the benefits of partition-based and propagation-based methods. The motivation is clearly demonstrated and the approach is valid.\n\n2. Theoretical analyses demonstrate the impact of embedding error and staleness bound on prediction error and convergence behavior. This helps justify the impact of the staleness (but concerns are discussed below).\n\n3. The experiments validate the effectiveness of the proposed algorithm, and the improvement over baselines is significant.\n\n# Weakness\n\n1. The major idea of the paper follows GNNAutoScale, and the asynchronous update is inspired by extensive research on asynchronous distributed optimization. The theoretical analyses and assumptions closely follow PipeGNN [1]. Overall, the originality is a bit weak.\n\n2. The theoretical statements of the paper need further clarification. Assumptions being made need to be clearly clarified in the main theorem. For instance, there are lots of assumptions being made in the proof but they are never mentioned in Theorem 2 and Theorem 3. Furthermore, the constants in the Theorem need to be explained, such as $E, M, P(\\eta)$ in Theorem 2 and 3.\n\n3. There are multiple concerns with the theoretical analysis. \n\n(1) First, the error presented in Theorem 1 can be potentially very large, which grows exponentially with the number of layers and has a bad dependency on the maximum node degree. A detailed empirical study of this approximation error will be helpful to clarify the impact of the error.\n\n(2) Second, the backward propagation process for gradient computation neglects the gradient computation through the out-subgraph stale representations. In other words, each local model considers the node representation from other machines to be constant. The paper and the corresponding theorem do not take this into account. In fact, this will invalidate one important step in the theoretical proof Eq. (34): $\\nabla L(W^t) = 1/M \\sum_1^M \\nabla L_m(W_m^t)$. This might cause major flaws in the proof and need to be addressed.\n\n4. The algorithm is only compared with 2 baselines that do not represent the state-of-art algorithms. It is suggested to also compare with algorithms such as PipeGNN and sampling-based methods such as GNNAutoScale.\n\n[1] PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NyTfDRZt1bZ", "reviewer": "Reviewer_UPkq", "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": "", "summary_of_the_paper": "This paper explores the trade-off between partition-based and propagation-based distributed training methods, taking advantage of both low communication overhead and no information loss. To do this, it saves a subgraph on each device and allows each device utilizes the stale representation of the neighbors of the subgraph saved on other devices. The results show more than 20 times speedup compared with the state-of-the-art distributed GNN training frameworks. This paper also proves the convergence of the proposed method. ", "summary_of_the_review": "The paper is well written. The proposed technique is intuitive, but not very impressive.  The experiments are insufficient. ", "strength_and_weaknesses": "## Strength:\n1. The GNN training framework proposed in this paper drops no edges while avoiding communication overhead, showing both good performances of accuracy and speedup.\n\n2. The periodic stale representation synchronization technique using periodically synchronous pull/push operations for the representations is novel and able to approximate the representations of nodes.\n\n3. The authors provide detailed proof of performance and convergence for both synchronous and asynchronous versions.\n\n## Weakness:\n1. Does KVS stores the representations of all the nodes on a graph? It would be better if the authors could provide the memory consumption of different methods. If the memory consumption of DIGEST is large, it may be hard for it to handle as large graphs as both partition-based and propagation-based methods.\n\n2. The experiments should use larger datasets, such as ogbn-papers100M and mag-240. The datasets used in this paper can be easily saved on a single machine. (The data size of the largest dataset ogbn-products is only 2.8G.) ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject