PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication
Authors: Cheng Wan
Youjie Li
Cameron R. Wolfe
Anastasios Kyrillidis
Nam Sung Kim
Yingyan Lin
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
Graph Convolutional Networks
Distributed Training
Asynchronous Training
Full-Graph Training
Large-Graph Training
Stale Features

Abstract: Graph Convolutional Networks (GCNs) is the state-of-the-art method for learning graph-structured data, and training large-scale GCNs requires distributed training across multiple accelerators such that each accelerator is able to hold a partitioned subgraph. However, distributed GCN training incurs prohibitive overhead of communicating node features and feature gradients among partitions for every GCN layer during each training iteration, limiting the achievable training efficiency and model scalability. To this end, we propose PipeGCN, a simple yet effective scheme that hides the communication overhead by pipelining inter-partition communication with intra-partition computation. It is non-trivial to pipeline for efficient GCN training, as communicated node features/gradients will become stale and thus can harm the convergence, negating the pipeline benefit. Notably, little is known regarding the convergence rate of GCN training with both stale features and stale feature gradients. This work not only provides a theoretical convergence analysis but also finds the convergence rate of PipeGCN to be close to that of the vanilla distributed GCN training without any staleness. Furthermore, we develop a smoothing method to further improve PipeGCN's convergence. Extensive experiments show that PipeGCN can largely boost the training throughput (1.7×~28.5×) while achieving the same accuracy as its vanilla counterpart and existing full-graph training methods. The code is available at https://github.com/RICE-EIC/PipeGCN.

Published as a conference paper at ICLR 2022
PIPEGCN: EFFICIENT FULL-GRAPH TRAINING OF GRAPH CONVOLUTIONAL NETWORKS WITH PIPELINED FEATURE COMMUNICATION
Cheng Wan
Youjie Li UICC li238@illinois.co
Cameron R. Wolfe
Rice University chwangrice.
Rice University crw138rice edu
Anastasios Kyrillidis
Nam Sung Kim
Yingyan Lin Rice University y1150@rice. edu
Rice University anastasios@rice.u
UICC nam. sung. kim@gmail. com
ABSTRACT
Graph Convolutional Networks (GCNs) is the state-of-ther of-thh-art method for learning graph-structured data, and training large-scale GCNs requires distributed training across multiple accelerators such that each accelerator is able to hold partitioned subgraph. However, distributed GCN training incurs prohibitive overhead of com- municating node features and feature gradients among partitions for every GCN layer during each training iteration, limiting the achievable training efficiency and model scalability. To this end, we propose PipeGCNN, simple yet effective scheme that hides the communication overhead by pipelining inter-partition communi- cation with intra-partition computation. It is non-trivial to pipeline for efficient GCN training, communicated node features/gradients will become stale and thus can harm the convergence, negating the pipeline benefit. Notably, little is known regarding the convergence rate of GCN training with both stale features and stale feature gradients. This work not only provides a theoretical convergence analysis but also finds the convergence rate of PipeGCN to close that of the vanilla distributed GCN training without any staleness. Furthermore, we develop a smoothing method to further improve PipeGCN's convergence. Extensive experi- ments show that PipeGCN can largely boost the training throughput (1.7x~28.55 while achieving the same accuracy as its vanilla counterpart and existing full-graph training methods. The code is available at http:://thuub.com//IEEEEE///C//D
INTRODUCTION
Graph Convolutional Networks (GCNs) (Kipf & Welling, 2016) have gained great popularity recently as they demonstrated the state-of-the-an (SOTA) performance in learning graph-structured data (Zhang & Chen, 2018; Xu al., 2018: Ying al., 2018). Their promising performance is resulting from their ability to capture diverse neighborhood connectivity. In particular, a GCN aggregates all features from the neighbor node set for a given node, the feature of which then updated via multi-layer perceptron. Such a two-step process (neighhor aggregation and node update) empowers GCNs better learn graph structures. Despite their promising performance, training GCNs at scale is still challenging problem, as prohibitive amount of compute and memory resources are required to train real-world large-scale graph, alone exploring deeper and more advanced models. To overcome this challenge, various sampling-basee methods have been proposed to reduce the resource requirement at a cost of incurring feature approximation errors. straightforward instance is to create mini-batches by sampling neighbors (e.g.. GraphSAGE (Hamilton et al., 2017) and VR-GCN (Chen et al., 2018 2018)) or to extract subgraphs as training samples (e.g., Cluster-GCN (Chiang et al., 2019) and GraphSAINT (Zeng et al., 2020)).
In addition to sampling-basee methods, distributed GCN training has emerged as a promising alternative, it enables large full- full-graph training of GCNs across multiple accelerators such GPUs.

---

Published as a conference paper at ICLR 2022
This approach first partitions a giant graph into multiple small subgraps, each of which is able to fit into a single GPU, and then train these partitioned subgraphs locally on GPUs together with indispensable communication across partitions. Following this direction, several recent works (Ma et al., 2019; Jia et al., 2020; Tripathy et al., 2020; Thorpe et al., 2021; Wan et al., 2022) have been proposed and verified the great potential of distributed GCN training. p8 (Gandhi & Iyer, 2021) follows another direction that splits the data along the feature dimension and leverages intra-layer model parallelism for training, which shows superior performance on small models.
In this work, we propose a new method for distributed GCN training, PipeGCN, which targets achieving a full- full-graph accuracy with boosted training efficiency. Our main contributions are following:
We first analyze two efficiency bottlenecks in distributed GCN training: the required significant communication overhead and frequent synchronization, and then propose a simple yet effective technique called PipeGCN to address both aforementioned bottlenecks by pipelining inter- seterppatition communication with intra- sara--artition computation to hide the communication overhead.
We address the challenge raised by PipeGCN, i.e., the resulting staleness in communicated features and feature gradients (neither weights nor weight gradients), by providing theoretical convergence analysis and showing that PipeGCNNs convergence rate is OTT 3), i.e., close to vanilla distributed GCN training without staleness. To the best of our knowledge, we are the first to provide a theoretical convergence proof of GCN training with both stale feature and stale feature gradients.
We further propose a low-overhead smoothing method to further improve PipeGGN's convergence by reducing the error incurred by the staleness.
Extensive empirical and ablation studies consistently validate the advantages of PipeGCN over both vanilla distributed GCN training and those SOTA full-graph training methods (c.g.. boosting the training throughput by 1.7xx~28.5x while achieving the same better accuracy).
2 BACKGROUND AND RELATED WORKS
Graph Convolutional Networks, GCNs represent each node in a graph as feature (embedding) vector and learn the feature vector via two-step process (neighbor aggregation and then node update) for each layer, which can be mathematically described as:
5()) (fn (nl--" | (EN(())))
(0) = 200 (= 1
where ((v) is the neighbor set of node in the graph, h represents the learned embedding vector
of node v at the ε-th layer, ((() is an intermediate aggregated feature calculated by an aggregation function ((0), and ((() is the function for updating the feature of node v. The original GCN (Kipf
& Welling, 2016) uses a weighted average aggregator for ((t) and the update function ((()) is a single-layer perceptron (WV()22() where (-) is non-linear activation function and (()) is weight matrix. Another famous GCN instance is GraphSAGE (Hamilton et al., 2017) in which ((()) is
(WO) CONCAT
(c()) 1he -)
Distributed Training for GCNs. A real-world graph can contain millions of nodes and billions of edges (Hu et al., 2020), for which a feasible training approach is to partition it into small subgraphs (to fit into each GPU's resource), and train them in parallel, during which necessary communication is performed to exchange boundary node features and gradients to satisfy GCNs's neighbor aggregation (Equ. 1). Such an approach is called vanilla partition-parallel training and is illustrated in Fig. 1 (a). Following this approach, several works have been proposed recently. NeuGraph (Ma et al., 2019), AliGraph (Zhu et al., 2019), and ROC (Jia et al., 2020) perform such cartition-paaalley training but rely on CPUs for storage for all partitions and repeated swapping of partial partition to GPUs Inevitably, prohibitive CPU-GPU swaps are incurred, plaguing the achievable training efficiency. CAGNET (Tripathy et al., 2020) is different in that it splits each node feature vector into tiny sub-vectors which are then broadcasted and computed sequentially, thus requiring redundant communication and frequent synchronization. Furthermore, pa (Gandhi & Iyer, 2021) proposes to split both the feature and the GCN layer for mitigating the communication overhead, but it makes a strong assumption that the hidden dimensions of a GCN should be considerably smaller than that of
2

---

Published as a conference paper at ICLR 2022
Timeline of (a)
Timeline PipeGCN
Graph
Mevation
Berrtion
Iteraion
#2
Partition
Part
2
3art
@
2
D
Compute
Part 2 Communicate Compute
Communicatee Compute
Communicate
Compute
Communicane
Inner Node
O
3
Pipaline
Boundary Node
Part
Communicate Boundary Feature & Grad (a) Vanilla partition-parallel training
(b) Timeline of vanilla partition-paralle training
(c) PipeGCN
Figure 1: An illustrative comparison between vanilla cnrtition-paralle training and PipeGCN.
input features, which restricts the model size, concurrent work Dorylus (Thorpe et al., 2021) adopts fine-grained pipeline along each compute operation in GCN training and supports asynchronous usage of stale features. Nevertheless, the resulting staleness of feature gradients is neither analyzed nor considered for convergence proof, let alone error reduction methods for the incurred staleness.
Asynchronous Distributed Training. Many prior works have been proposed for asyn- chronous distributed training of DNNs. Most works (e.g.. Hogwild! (Niu et al., 2011), SSP (Ho et al., 2013), and MXNet (Li et al., 2014)) rely parameter server with multiple work- ers running asynchronously to hide commu- nication overhead of weights//weight gradi- ents) among each other, at cost of using stale weight gradients from previous itera- tions. Other works like Pipe-SGD (Li et al.,
Table I:
Differences between conventional asyn- chronous distributed training and PipeGCN.
Hogwild!, SSP,
Method
MXNet, Pipe-SGD,
PipeGCN
PipeDream, PipeMare
Large Model.
Target
Large Feature
Small Feature
Features and Feature Gradients
Staleness
Weight Gradients
2018b) pipeline such communication with local computation of each worker. Another direction is to partition a large model along its layers across multiple GPUs and then stream in small data batches through the layer pipeline, c.g.. PipeDream (Harlap et al., 2018) and PipeMare (Yang et al., 2021). Nonetheless, all these works aim at large models with small data, where communication overhead of model weights/weight gradients are substantial but data feature communications are marginal (if not none), thus not well suited for GCNs. More importantly, they focus on convergence with stale weight gradients of models, rather than stale features/feature gradients incurred in GCN training. Tab. summarizes the differences. In nutshell, little effort has been made to study asynchronous or pipelined distributed training of GCNs, where feature communication plays the major role, let alone the corresponding theoretical convergence proofs.
GCNs with Stale Features/Feature Gradients. Several recent works have been proposed to adopt either stale features (Chen et al., 2018: Cong et al., 2020) or feature gradients (Cong et al., 2021) in single-GPU training of GCNs. Nevertheless, their convergence analysis considers only one of two kinds of staleness and derives convergence rate of ( for pure sampling-basedd methods. This is, however, limited in distributed GCN training as its convergence simultaneously affected by both kinds of staleness. PipeGCN proves such convergence with both stale features and feature gradients and offers better rate of - )). Furthermore, none of previous works has studied the errors incurred by staleness which harms the convergence speed, while PipeGCN develops low-overhead smoothing method reduce such errors.
3 THE PROPOSED PIPEGCN FRAMEWORK
Overview. To enable efficient distributed GCN training, we first identify the two bottlenecks associated with vanilla partition-parally training: substantial communication overhead and frequently synchronized communication (see Fig. 1(b)), and then address them directly by proposing novel strategy, PipeGCN, which pipelines the communication and computation stages across two adjacent iterations in each partition of distributed GCN training for breaking the synchrony and then hiding the communication latency (see Fig. Icc)). It is non-trivial to achieve efficient GCN training with such pipeline method, staleness is incurred in communicated features/feature gradients and
3

---

Published as a conference paper at ICLR 2022
Time
Current Iteration
Inner Festure
L1 Feat
Feature Gradient
Keep Send
Received from other subgraphe
Boundary Feat.
Communicate
Forward
Communicate
Forward
Backward
Communicate
Back.
Update
(a) Vanilla partition-paralle training of GCNs (per-partition view)
Previous Iteration
Current Iteration
From Current lteration
From Provious lteration
L1 For L2 For.
L2 Back. L1 Back.
Up.
L1 Forward
L2 Forward
L2 Backward
L1 Backward
Update
Communicate for Next
Forward
Communicate
Communicate for Next Forward
Communicate
Communicate for Next L1 Backward
Communicate
(b) PipeGCN (per-partition view)
Figure 2: A detailed comparison between vanilla partition-paralled training of GCNs and PipeGCN
more importantly little effort has been made to study the convergence guarantee of GCN training using stale feature gradients. This work takes an initial effort to prove both the theoretical and empirical convergence such pipelined GCN training method, and for the first time shows its convergence rate to be close to that of vanilla GCN training without staleness. Furthermore, we propose a low-overhead smoothing method to reduce the errors due to stale features/feature gradients for further improving the convergence.
3.1 BOTTLENECKS IN VANILLA PARTITION- AARITTIO--PARALELL TRAINING
Significant communication overhead. Fig. ((a) illus- trates vamilla purtition-paralle training, where each partition holds inner nodes that come from the original graph and boundary nodes that come from other sub- graphs. These boundary nodes are demanded by the neighbor aggregation of GCNs across neighbor parti- tions, e.g., Fig. 1 (a) node-5 needs modes-[3.4,6 from other partitions for calculating Equ. 1. Therefore, it the features/gradieetts of boundary nodes that dom- inate the communication overhead in distributed GCN training. Note that the amount of boundary nodes can be excessive and far exceeds the inner nodes, as the boundary nodes are replicated across partitions and scale with the number of partitions. Besides the sheer size, communication of boundary nodes occurs for (1) each layer and (2) both forward and backward passes, making communication overhead substantial. We evaluate such overhead in Tab. and find communication to be dominant, which is consistent with CAGNET (Tripathy et al., 2020).
Table 2: The substantial communication
overhead in vanilla partition-parallel train- ing, where Comm. Ratio is the communica- tion time divided by the total training time.
Dataset
# Partition Comm. Ratio
65.83%
Reddit
82.89%
76. 16%
ogbn-prodduct
10
85. 75.79%
61.
Yelp
76.84%
Frequently synchronized communication. The aforementioned communication of boundary nodes must be finished before calculating Equ. and Equ. 2, which inevitably forces synchronization be- tween communication and computation and requires a fully sequential execution (see Fig. 1(b)). Thus, for most of training time, each partition waiting for dominant features/gradients communication to finish before the actual compute, repeated for each layer and for both forward and backward passes.
3.2 THE PROPOSED PIPEGCN METHOD
Fig. 1(c) illustrates the high-level overview of PipeGCN, which pipelines the communicate and compute stages spanning two iterations for each GCN layer. Fig. 2 further provides the detailed end-to-end flow, where PipeGCN removes the heavy communication overhead in the vanilla approach by breaking the synchronization between communicate and compute and hiding communicate with compute of each GCN layer. This is achieved by deferring the communicate to next iteration's compute (instead of serving the current itcration) such that compute and communicate can run in
The detailed setting can he found in Sec.
4

---

Published as a conference paper at ICLR 2022
Algorithm 1: Training GCN with PipeGCN (per-partition view).
Input: partition id i, partition count n., graph partition Gt. propagation matrix P. node feature X;, label Y, boundary node set B,, layer count L., learning rate initial model Wo
Output: trained model Wr after T iterations
Vi f (node E Gi
]
b create inner node set
Broadcast B, and Receive [B .B.]
SS.,]] [.,,,...
[B, V1, B. 0 V.
Broadcast V; and Receive [ V.l
[Si,, Sn.a] + [3, n V1 ... B. V.l
(1)
X;
initialize node feature, set boundary feature 0
0
for =
do
for == 1 + do
> forward pass
i > then
10
wait until thread, completes
[ H1 Sn.
[B] ,... B3!
update boundary feature
12
end
13
with thread
communicate boundary features in parallel
14
Send S1.1
(6-1)
Si.
to partition [I,"* and Receive [B]] ..... _B(+]
0 + (P
end 15
update inner nodes feature
1/ +- ( (1
17
18
e === do for
b> backward pass
0 + [P. ( (1
19
b calculate weight gradient
ift then
J(--)) P.T ( [W["]T
21
calculate feature gradient
22
ift 1 then
23
wait until thread, completes
for j = + do
11-11 + ((-11)
S.s + ((
b accumulate feature gradient
end
27
end
28
with thread 16)
I communicate boundary feature gradient in parallel Send (JS..] (1-1) .... _S_. to partition [l,..", n²]
and Receive [C[ ,", c!f
29
30
end
end
32
+- AllReduuce(Gi)
synchronize model gradient
33
W. + W -
b update model
end
return Wr
parallel. Inevitably, staleness is introduced in the deferred communication and results in a mixture usage of fresh inner features/gradienss and staled boundary features/gradieens:
Analytically, PipeGCN is achieved by modifying Equ. 1. For instance, when using a mean aggregator, Equ. 1 and its corresponding backward formulation in PipeGCN become:
(t.6) MEAN
(1h u E (ENN()) (B())
(A (1---1 Iue B(U))
(3)
(60 h.
Σ
1
Σ
1 1-1-1
(4)
d
d
where B(v) is node o's boundary node set, d, denotes node e's degree, and s((.() and 62:-)) rep- resent the gradient approximation of h, and 2, at layer & and iteration t, respectively. Lastly, the implementation of PipeGCN are outlined in Alg.
5

---

Published as a conference paper at ICLR 2022
3.3 PIPEGCN's CONVERGENCE GUARANTEE
As PipeGCN adopts a mixture usage of fresh inner features/gradients and staled boundary fea- tures/gradients, its convergence rate is still unknown. We have proved the convergence of PipeGCN and present the convergence property in the following theorem.
Theorem (Convergence of PipeGCN, informal version). There exists a constant such that for any arbitrarily small constant > O, we can choose learning rate V and number of training E
iterations T (C(0()) [(0*) EE à such that:
T
I 5(e))
T
where LL-) is the loss function, ( and 0 represent the parameter vector at iteration L. and the optimal parameter respectively.
Therefore, the convergence rate of PipeGCN is O(T- which is better than sampling-based method (O(T 2)) (Chen et al., 2018; Cong et al., 2021) and close to full-graph training (O(T
The formal version of the theorem and our detailed proof can be founded in Appendix A.
3.4 THE PROPOSED SMOOTHING METHOD
To further improve the convergence of PipeGCN, we propose a smoothing method to reduce errors incurred by stale features/feature gradients at minimal overhead. Here present the smoothing of feature gradients, and the same formulation also applies to features. To improve the approximate gradients for each feature, fluctuations in feature gradients between adjacent iterations should be reduced. Therefore, we apply a light-weight moving average to the feature gradients of each boundary node as follow:
g(1. = 8(1-111) + -1-7))64
where ((t.)) is the smoothed feature gradient at layer l and iteration t, and y is the decay rate. When integrating this smoothed feature gradient method into the backward pass, Equ. can be rewritten as:
Σ
gl1,441)
Σ 1 -.8--144
do
(TNE
((
Note that the smoothing of stale features and gradients can be independently applied to PipeGCN.
4 EXPERIMENT RESULTS
We evaluate PipeGCN on four large-scale datasets, Reddit (Hamilton et al., 2017), ogbn-prooucee (Hu al., 2020), Yelp (Zeng al., 2020), and ogbn-papers 100M (Hu al., 2020). More details provided in Tab. 3. To ensure robustness and reproducibility, we fix (i.e., do not tune) the hyper- parameters and settings for PipeGCN and its variants throughout all experiments. To implement partition parallelism (for both vanilla distributed GCN training and PipeGCN), the widely used METIS (Karypis & Kumar, 1998) partition algorithm is adopted for graph partition with its objective set to minimize the communication volume. We implement PipeGCN in Py PyTorch (Paszke et al., 2019) and DGL (Wang et al., 2019). Experiments are conducted on machine with 10 RTX-208011 (11GB), Xeon 6230R @ 2. 10GHz (187GB), and PCIe3x16 connecting CPU-GPU and GPU-GPU, Only for ogbn-papers 100M, we use 4 compute nodes (each contains MI60 GPUs, an AMD EPYC 7642 CPU, and 48 lane PCI 3.0 connecting CPU-GPU and GPU-GPU) networked with 10Gbps Ethernet. To support full-graph GCN training with the model sizes in Tab. 3, the minimum required partition numbers are 2, 32 for Reddit, egbn-product. Yelp, and ogbn-papers 100M, respectively.
For convenience, we here name all methods: vanilla partition-parall parallel training of GCNs (GCN), PipeGCN with feature gradient smoothing (PipeGCN-G), PipeGCN with feature smoothing (PipeGCN-FF. and PipeGCN with both smoothing (PipeGCN-GF), The default decay rate y for all smoothing methods is set to 0.95.

---

Published as a conference paper at ICLR 2022
Table Detailed experiment setups: graph datasets, GCN models, and training hyper-parametten
Dataset
Nodes
# Edges
Feat, size
GraphSAGE model size
Optimizer
LearnKtaee
Dropout
# &Epoch
Rediit
253K
114M
602
4 layer, 256 hidden units
Adam
0.01
0.5
3000
oghn-prnducts
layer, hidlen units
0.3
500
Yelp
716K
7.0M
300
4 layer. 512 hidden units
Adam
0.001
0.1
3000
ogbo-paperst00M
111M
166
128
layer, 48 hidden units
Adam
0.01
0.0
1000
Throughput (epochs/s)
Reddit
Throughput (chs/s)
ogbn-products
Throughput (epochs/s)
Yelp
4.0
4
BROC
CAGNET [c=1]
GCN
MpcGGN
3.5
BROC
CCGGNET [c=1]
PpaGCN
GCN
1- 2 w 5
CCGGNET [c-1]
BROC
GCN
PieGGN
3
CAGNNTT (c=2)
PlpeGCN.GE
3.0
2.5
CAGGET [C-2)
PipeGCN-
C (c-2)
PipeSCN-Gr GF
2-
2.0
1.5
1.0
0.5
0.0
Number of GPUs
Number of GPUs
Number of GPUs
Figure 3: Throughput comparison. Each partition uses one GPU (except CAGNET (c=2) uses two).
4.1 IMPROVING TRAINING THROUGHPUT OVER FULL-GRAPH TRAINING METHODS
Fig. 3 compares the training throughput between PipeGCN and the SOTA full-graph training methods (ROC (Jia et al., 2020) and CAGNET (Tripathy et al., 2020)). We observe that both vanilla partition- parallel training (GCN) and PipeGCN greatly outperform ROC and CAGNET across different number of partitions, because they avoid both the expensive CPU-GPU swaps (ROC) and the redundant node broadcast (CAGNET). Specifically, GCN is x1..4x faster than ROC and 2.1x~10.21 faster than CAGNET (c=2). PipeGCN further improves upon GCN, achieving a throughput improvement of 5.6x~28.5x over ROC and 3.9x~17.7x over CAGNET (c=2)². Note that compare PipeGCN with NeuGraph (Ma et al., 2019), AliGraph (Zhu et al., 2019), and ps (Gandhi & Iyer, 2021) as their code are not publicly available. Besides, Dorylus (Thorpe et al., 2021) is not comparable, as it is not for regular GPU servers. Considering the substantial performance gap between ROC/CAGNET and GCN, we focus on comparing GCN with PipeGCN for the reminder of the section.
not able to
4.2 IMPROVING TRAINING THROUGHPUT WITHOUT COMPROMISING ACCURACY
We compare the training performance of both test score and training throughput between GCN and PipeGCN in Tab. 4. We can see that PipeGCN without smoothing already achieves a comparable test score with the vanilla GCN training on both Reddit and Yelp, and incurs only a negligible accuracy drop (-0.08% on ogbn-products, while boosting the training throughput by 1.72 x ~2116 across all datasets and different number of partitions,, thus validating the effectiveness of PipeGCN.
With the proposed smoothing method plugged in, SmeGCN-G//FGE is able to compensate the dropped score of vanilla PipeGCN, achieving an equal or even better test score as/than the vanilla GCN training (without staleness), e.g., 17.14% vs. 97.1 % on Reddit, 79.36% vs. 79.14% on ogbn-products and 65.28% vs. 65.26% on Yelp. Meanwhile, PipeGCN-G/F/GF enjoys similar throughput improvement as vanilla PipeGCN, thus validating the negligible overhead of the proposed smoothing method. Therefore, pipelined transfer of features and gradients greatly improves the training throughput while maintaining the full-graph accuracy.
Note that our distributed GCN training methods consistently achieve higher test scores than SOTA sampling-be based methods for GraphS AAN-SAGE-baass models reported in (Zeng et al., 2020) and (Hu et al., 2020), confirming that full-graph training preferred to obtain better GCN models. For example, the best campling-based method achieves a 96.6% accuracy on Reddit (Zeng et al., 2020) while full-graph GCN training achieves 97. %, and PipeGCN improves the accuracy by 0.28% over sampling- based GraphSAGE models on gennuuroducts (Hu et al., 2020). This advantage of full-graph training is also validated by recent works (Jia et al., 2020; Tripathy et al., 2020; Liu et al., 2022; Wan et al., 2022).
A Moore detailed comparisons among full- graph training methods can be found in Appendix B. Mooe details regarding PipeGCN's advantages in training throughput be found in Appendix C.
7

---

Published as a conference paper at ICLR 2022
Table 4: Training performance comparison among vanilla partition-parallee training (GCN) and
PCpeGCN variants ( where we report the test accuracy for Reddit and ppon-prosucts, and the F1-micro score for Yelp. Highest performance in bold.
Dataset
Method
Test Score (%)
Throughput
Dataset
Method
Test Score (%)
Throughput
GCN
97.11=0.022
1x (1.94 epochsis)
GCN
97.11-20.02
1x (2:07 epochals)
Roddit
PipsGCN
PipoGCN-G
97.14:20.03
97.12:+0.02
x
1
Roddit
PipeGCN
PipoGCN-G
97.09=+0.03
97.04:1:.03
2.12x
2.07
partitions)
PipeGUN-F
97.09-10002
1
4 partitions)
PipeCICI-F
97.10:10.00
2.10x
PipeGCN.Gr GF
97.12.10.02
x
PipeGCN GF
97.10:10.00
2.06
GCN
79.14:00,35
1x (1.45 epocis/s)
GCN
79.14:20.35
1x (1.28 epochsis)
PipeGCN
79.06.10042
1,94%
PipeGGN
78.91
1.87x
pron-products
partitions)
PipeGCNNF
PipeGGN-G
79,20=2:0388
79.36:10.38
1990
1,90x
oghn products
(10 partitions)
PipeGCNN-F
PipeGCN-G
79.21:10.31
79.08:+0.58
1881
1.82x
PF
78.86.1.0.4
1,91 x
PipGGNN-GF
78.77:10.23
1.82
GCN
65,26:1:0.02
1x (2.00) epachs/s)
GCN
65.26:1:0.2
1x (2.25 epocha/s)
(3 partitions)
Yelp
PipsGCN-F
PipeGCN-G
PipeGCN
65.27:10.01
65.26:t0.03
65.26:1:0.22
x
2.16%
2.15x
(6 partitions)
Yelp
PipoGCN-F
PipeGCN
PipeGON-G
65.24:10.02
65.28:10.02
65.25=+0.04
1,72
1.69
1.68x
PipeGCN-GF
65.26-1:0.04
2
PipeGNN-GF
65.26:1:004
1.67
Roddit partitions)
Reddit partitions)
oghn- products partitions)
ogbn products partitions)
Tesn Accurccy 180
07
52
Teet Aus.Aucoe Aucuraa Pad
Test Accunery
GON PIONOIN
GCN
GCN
GCN
Pieeacc
HovGCN
PlocGCN
PipeSCh
HocGCNNG G
PipeGCh-
PlocGCN
PipeSCN
PipeSCN
PlpeGCN
1000
2000
5007
3200
2000
3000
5:3
1002
500
3000
Epoch
Epoch
Epoch
Epach
Figure 4: Epoch-to-accuracy comparison among vanilla partition-paralle training (GCN) and PipeGCN variants (PipeGCN*), where PipeGCN and its variants achieve a similar convergence as the vanilla training (without staleness) but are twice as fast in wall-clock time (see Tab. 4).
4.3 MAINTAINING CONVERGENCE SPRED
To understand PipeGCN's influence on the convergence speed, we compare the training curve among different methods in Fig. 4. We observe that the convergence of PipeGCN without smoothing is still comparable with that of the vanilla GCN training, although PipeGCN converges slower at the early phase of training and then catches up at the later phase, due to the staleness of boundary features/grn graaiinns/ With the proposed smoothing methods, PipeGCN-G/F boosts the convergence substantially and matches the convergence speed of vanilla GCN training. There is no clear difference between PipeGCN-G and PipeGCNNFF Lastly, with combined smoothing of features and gradients, PipeGCN-GF can acheive the same or even slightly better convergence speed as vanilla GCN training (e.g., Reddit) but can overfit gradually similar to the vanilla GCN training, which is further investigated in Sec, 4.4. Therefore, PipeGCN maintains the convergence speed w.r. the number of epochs while reduces the end-to-end training time by around 50% thanks to its boosted training throughput (see Tab. 4).
4.4 BENEFIT OF STALENESS SMOOTHING METHOD
Error Reduction and Convergence Speedup. To understand why the proposed smoothing tech- nique (See. 3.4) speeds up convergence, we compare the error incurred by the stale communication between PipeGCN and PipeGCN- G/F. The error is calculated as the Frobenius-nowe norm of the gap between the correct gradient/feature and the stale gradient/feature used in PipeGCN training. Fig. compares the emror at each GCN layer. We can see that the proposed smoothing technique (PipeGCN- G/F) reduces the error of staleness substantially (from the base version of PipeGCN) and this benefit consistently holds across different layers in terms of both feature and gradient errors, validating the effectiveness of our smoothing method and explaining its improvement to the convergence speed.
Overfitting Mitigation. To understand the effect of staleness smoothing also evaluate the test-accuracy convergence under different decay rates ? in Fig. 6. Here ogbn- products is adopted as the study case because the distribution of its test set largely differs from that of its training set. From Fig. 6, we observe that smoothing with a large y (0.7/0.95) offers a fast convergence, i.e., close to the vanilla GCN training, but overfits rapidly. To understand this issue,
model overfitting, we
8

---

Published as a conference paper at ICLR 2022
Backward Gradient Efror
Forward Feature Ertor
Miseee (ayer 11 poSD-- (layer
PPcCC laayer HocoCh- lays
78-
Frobeniig Norm (x10")
HiedON Dayer
HoedON Dlyer 21
pecCk 0 (aayer 2)
peGCN 6 (ayer
k100
PpuOCh laayer HacoChi flyct
Pp:OCh llayer
HacoCh++ llyct 21
70-
Test Acturacy
Frobamiue Nomm
SON (Mpaacc))
-3
ym0.5
V- 0.7
74-
0.95
Epoch
Epech
Figure 5: Comparison of the resulting feature gradient error and feature error from PipeGCN and PipeGCN-Gii each GCN layer on Reddit (2 partitions). PipeGCN-G/F here uses a default smoothing decay rate of 0.95.
Figure 6: Test-aceuracy convergence comparison among different smooth- ing decay rates y in PipeGCN-GF on ogbn- gebn-products (10 partitions).
Gradient Error (Layer 1)
Gradient Error (Layer 2)
Feature Error (Layer 1)
Feature Error (Layer 2)
yma.
ym30
5=00
y=03
y-33
y- y- A
v-3.5
v-077
6-
y ouss
y=
Frobperiug
Epech
Epoch
1006
Epoch
Epazh
1895
Figure Comparison of the resulting feature gradient error and feature error when adopting different decay rates y each GCN layer ggbn-products (10 partitions).
further provide detailed comparisons of the errors incurred under different y in Fig. We can see that larger enjoys lower approximation errors and makes the gradients/feature more stable, thus improving the convergence speed. The increased stability on the training set, however, constrains the model from exploring more general minimum point the test set, thus leading to overfitting as the vanilla GCN training. In contrast, a small (0 ~ 0.5) mitigates this overfitting and achieves better accuracy (see Fig. 6). But too-small y (e.g., 0) gives high error for both stale features and gradients (see Fig. 7), thus suffering from a slower convergence. Therefore, a trade-off between convergence speed and achievable optimality exists between different smoothing decay rates, and 0.5 combines the best of both worlds in this study.
4.5 SCALING LARGE GRAPH TRAINING OVER MULTIPLE SERVERS
To further test the capability PipeGCN, we scale up the graph size to wwwnnppaeeteee 100M 100M and train GCN over multiple GPU servers with 32 GPUs. Tab. shows that even such large-scale setting where communication overhead dominates, PipeGCN still reduce communication time by 61 %, leading total training time reduction of 38% compared to the vanilla GCN baseline* 4.
Table 5: Comparison of epoch training time on ngbn-papers100M.
Method
Total
Communication
GCN
1.00x (10.5s)
1.00x (6.6s)
PipeGCN PipeGCN-GF
0.62x (6.5s)
0.39x (2.6s)
0.64x (6.7s)
0.42x (2.8s)
CONCLUSION
In this work, we propose a new method, PipeGCN, for efficient full-graph GCN training. PipeGCN pipelines communication with computation in distributed GCN training hide the prohibitive communication overhead. More importantly, we are the first to provide convergence analysis for GCN training with both stale features and feature gradients, and further propose light- smoothing method for convergence speedup. Extensive experiments validate the advantages of PipeGCN over both vanilla GCN training (without staleness) and state-of-the-ar full-graph training.
'More experiments on multi-server training can he found Appendix F.
9

---

Published as a conference paper at ICLR 2022
6 ACKNOWLEDGEMENT
The work is supported by the National Science Foundation (NSF) through the MLWINS program (Award number: 2003137), the CC Compute program (Award number: 2019007), and the NeTS program (Award number: 1801865).
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942-950.. PMLR, 2018.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1393-1403, 2020.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the importance of sampling in learning graph convolutional networks. arXiv preprint 1.Xiv:2103302690 2021.
Swapnil Gandhi and Anand Padmanabha lyer. P3:
Distributed deep graph learning at scale. 15th USENIX Symposium Operating Systems Design and Implementation (OSDI 21), pp. 551-568, 2021.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430. PMLR, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017.
Aaron Harlap, Deepak Narayanan, Amar Phanishayee, Vivek Seshadri, Nikhil Devanur, Greg Ganger, and Phil Gibbons. Pipedream: Fast and efficient pipeline parallel dnn training. arXiv preprint arXiv:1806.03337. 2018
Qirong Ho. James Cipar, Henggang Cui, Jin Kyu Kim. Seunghak Lee, Phillip B Gibbons, Garth A Gibson, Gregory R Ganger, and Eric Xing. More effective distributed ml via a stale synchronous parallel parameter server. Advances in neural information processing systems, 2013: 2013.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0060 000887 2020.
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 (MLSys), pp. 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):359-395 1998.
Thomas Kipf and Max Welling. Semi- semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609: (00.66699022290 2016.
10

---

Published as a conference paper at ICLR 2022
Mu Li, David G Andersen, Alexander J Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 27:19-27, 2014.
Youjie Li, Jongse Park, Mohammad Alian, Yifan Yuan, Zheng Qu, Peitian Pan, Ren Wang, Alexander Gerhard Schwing, Hadi Esmaeilzadeh, and Nam Sung Kim. network-centric hard- ware/algorithm co-design accelerate distributed training of deep neural networks. In Proceedings of the s1 IEEE/ACM International Symposium on Microarchitecture (MICRO' 18), Fukuoka City, Japan, 2018a.
Youjie Li, Mingchao Yu, Songze Li, Salman Avestimehr, Nam Sung Kim, and Alexander Schwing. Pipe-SGD: A decentralized pipelined sgd framework for distributed deep net training. Advances in Neural Information Processing Systems, 2018b.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach generalization bounds for graph neural networks. arXiv preprint arXiv:2012.0700 07690, 2020.
Zirui Liu, Kaixiong Zhou, Fan Yang. Li Li, Rui Chen, and Xia Hu. EXACT: Scalable graph neural networks training via extreme activation compression. In International Conference on Learning Representations, 2022. URL https: opwprevieneeeeeeeeeeeeeeeeeeeewe net / forum ? wwa.aiaa
Lingxiao Ma. Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. Neugraph: parallel deep neural network computation on large graphs. 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 443-458, 2019.
Feng Niu, Benjamin Recht, Christopher Ré, and Stephen Wright. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. arXiv preprint 100.::1000.7000 2011.
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, pp. 2019,
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pant aata-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association. Citeseer, 2014.
John Thorpe, Yifan Qiao, Jonathan Eyolfson, Shen Teng, Guanzhou Hu, Zhihao Jia, Jinliang Wei, Keval Vora, Ravi Netravali, Miryung Kim, et al. Dorylus: affordable, scalable, and accurate gnn training with distributed cpu servers and serverless threads. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pp. 495-514, 2021.
Alok Tripathy, Katherine Yelick, and Aydin Bulue. Reducing communication in graph neural network training. arXiv preprint arXiv:2005.0333 2020.
Cheng Wan, Youjie Li, Ang Li, Nam Sung Kim, and Yingyan Lin. BNS-GCN; Efficient full-graph
training of graph convolutional networks with paraiiinn- and random boundary node sampling. Fifth Conference Machine Learning and Systems, 2022.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma. Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, geglyy-perfommnt package for graph neural networks. arXiv preprint 19t9.0999900...... 2019.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergradd: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
Bowen Yang, Jian Zhang. Jonathan Li. Christopher Ré, Christopher Aberger, and Christopher De Sa. Pipemare: Asynchronous pipeline parallel dan training. Proceedings of Machine Learning and Systems, 3, 2021.
11

---

Published as a conference paper at ICLR 2022
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.
Mingchao Yu, Zhifeng Lin, Krishna Giri Narra, Songze Li, Youjie Li, Nam Sung Kim, Alexan- der Schwing, Murali Annavaram, and Salman Avestimehr. Gradiveq: Vector quantization for Sandwidth-efficient gradient aggregation in distributed cnn training. In Proceedings of the 32nd Conference on Neural Information Processing Systems (NIPS' 18), Montreal, Canada, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- 2020.
saint: Graph sampling based inductive learning method. arXiv preprint
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
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 19Xiv:1902.087750 2019.
12

---

Published as a conference paper at ICLR 2022
A CONVERGENCE PROOF
In this section, we prove the convergence of PipeGCN. Specifically, we first figure out that when the model updated via gradient descent, the change of intermediate features and their gradients are bounded by constant which is proportional to learning rate under standard assumptions. Based on this, we further demonstrate that the enror occurred by the staleness proportional to 7) which guarantees that the gradient eπrоr is bounded by nE where E is defined in Corollary A010, and thus PipeGCN converges in (e 3) iterations.
A.1 NOTATIONS AND ASSUMPTIONS
For a given graph 9 = (V.&) with an adjacency matrix A, feature matrix X, we define the propagation matrix P as P := D-1/2AD- where A = A + Du,u. = E, Au,.- One GCN layer performs one step of feature propagation (Kipf & Welling, 2016) as formulated below
H X
Z PH(
H = o(Z(0)
where H1),, W(O), and Z denote the embedding matrix, the trainable weight matrix, and the intermediate embedding matrix in the E-th layer, respectively, and a denotes a non-linear activation function. For an L-layer GCN, the loss function is denoted by L(O) where 0 vec(W((), W(2), ..., ..(]]..... We define the l-th layer function (t..).
(H w()) = a (PH((-)))())
Its gradient w.r.t. the input embedding matrix can represented as
J(H-1) " ((-1)), w(9) = PT M WloTT
and its gradient w.r.. the weight can represented as
g V H((-1), w(0) = (PH((11) M()
where M(4) = J d and denotes Hadamard product.
For partition-paraln paaalleel training, we can split into two parts p= Pin. + Pha where P... represents intra- partition propagation and Pbd denotes inter-partition propagation. For PipeGCN, represent one GCN layer as below
(1.00) X
(0,0) P. (t. + P-e-
7(.0 (Z((.1))
where is the epoch number and (((+() is the weight at epoch layer f. We define the loss function for this setting as [((())) where g(t) vec[W[(r.)) W(t.)).... W...... We can also summarize the layer as a function (.).)),)))
(H W((.)) H... 1-
Note that (11--11111 is not part of the input of f().)).)) because it is constant for the 1-th epoch. The corresponding backward propagation follows the following computation
J(---1) Vn (1.00 (1--1) (.W+))))
(0.0 = Vw (Tt.)) (1,--1) W(100)
where
Ml.0 = J(..) o' o (111-11 Pod P 1111--1-111
13

---

Published as a conference paper at ICLR 2022
V VHf (000 H wil)) P, (1) [i..000 + P W
V (i H w((l))) = [P H (1 + Poall (t - 11 M ((.))
Again, J(--1,0) is not a part of the imput of V V f(.0) (,, or Vw f(c.0) (....)) because is constant for epoch i. Finally, we define V(((()) = vec (((11) ((1,2) ....D.. It should be highlighted that the 'gradient' Fi..0. :) f .) and Vl((() are not the standard gradient for
the corresponding forward process due to the stale communication. Properties of gradient cannot be directly applied to these variables.
Before proceeding our proof, we make the following standard assumptions about the adopted GCN architecture and input graph.
Assumption A.1. The loss function Loss(-;)) is Cl continuous and Toos- w.r.t. to the input node embedding vector, i.e., (oss(h(4), y) Loss(h v)1 S Ctosellh(() - 11'2) ||2 and V Loss(h()) (L), -u) - (ooss(h(()) v)ll2 S T ( - 1/120112 where h is the predicted label and the correct label vector.
Assumption A.2. The activation function o-) Co-Lipschitz continuous and -mooth,, i.e. [|o (z S Co ||2(() 212 and [la' (2(9)) - dz(211))]l S Lollz(t) - 2/10
Assumption A.3. For any & [L.]. the norm of weight matrices, the propagation matrix, and the input feature matrix are bounded: [| || Bw ||||| Bp,1|X|] S Bx. (This generic assumption is also used in (Chen et al., 2018; Liao et al., 2020; Garg et al., 2020; Cong et al., 2021).)
A.2 BOUNDED MATRICES AND CHANNES
Lemma A.1. For any l [L], the Frobenius norm of node embedding matrices, gradient passing from the 1-th layer node embeddings to the (f - 1)-th, gradient matrices are bounded, i.e.,
[1 ||, (1))).2) |F S BH:
1| 11, | 1| B,,
|M
(7 ||5 S BM. F1.
|G
(0 1| S Ba
where
Bи max 1S1S
(C y' Bx
B, max
(C Ciose 2CPSI.
By = C.
Bę Bp BM
Proof. The proof of ||H| I Bμ and || I B, can be found in Proposition I in (Cong al., 2021). By induction,
11
|r = Io (( W1L0 -
< C. Pn + Poal (Co B-x
s BC,
|.TT (Jhel oo o' (Z(00)) [ITA.O0T + PTT (Ju- o o (Z(0-10)))) [
s C Bw | Pmn + Pool p F(Co 1
< (C,, Bw 1+1 Closs
| = (1)((0) o o o0(210)) S C.Bs
| J((00) o' 17 C.B,
14

---

Published as a conference paper at ICLR 2022
G 1P M((
< BpBuBn
((0 = [Pin (()-1) + Pod P M7a
SBPBuBM
Because the gradient matrices are bounded, the weight change bounded.
Corollary A.2. For any t, l, || -wt--.0 || S BAw BBa where ni is the learning rate.
Now we can analyze the changes of intermediate variables.
Lemma A.3. For any t, we have (Z 1 || S Baz. [1 1100 S Ban
where Baz Σ Bpt B BB Baw and BAZ C.Baz.
Proof. When f. = 0, || [T.00 H = -X-1|| 1-] = O. Now we consider f > 0 by induction.
|| 7(0-1.00| = (P (P. Pau P
(Pm W (t-1f() + P (1-201)) ((-18))
IP
(1))))
Pba H W (1.8) (1-26-1
Then analyze the bound of [| W (1,e) H W 1.1 || which is denoted by s(t,9)
s(t,e) < - (1- || + |1 (1-11) - 11
(1,8
s Bn W(L0 1 || + Bw (1,-1)) -1--16--11
According to Corollary A.2. [iite. w S Baw- By induction, (1.-1111))
t-2
11--16-1) < Σ C++1 BJ+1 Bly Bh Baw. Combining these inequalities. 1=0
6000 < BaBaW + Σ Br
Plugging it back, we have
(12 - -0- < S (1
W(() - H (t- 11-- 11-1--117(--1110
1-- H 210--2e-1 2711
SBp
Baw + Σ BBy Bu Baw
Σ
C B Bu BAW
1=0
10000 ( 1.0 =110 -(
<Ca SCa 1(000 10-16
SC,Ba
15

---

Published as a conference paper at ICLR 2022
Lemma A.4. [|J(,0 - -00-1.011 s Bas where
BaJ max (BpBwCa)t- Ban Laass + (BMBaw + La ByBaa Bw) 2505L
Bir Big Co
km0
Proof. For the last layer (E - L). ( - 110-1,1) < Lioss] (((,) - For the case of & < L, we prove the lemma by using induction.
(1( |F S LiaBBH
Min M Po 1. -
[ - -(1
(1 ( 
(
(i NT 1.0 1000)))))))
(i -o - (101 21 ( 
We denote
17(1 1,10 -
by ((1,6) and analyze its bound.
s(1,0) $ ( - -
+ -iraoooooool -
|
F
17 wil.
F
<BM
[10011]] - 1LL0-11 ||=
+ Bw |M
M 1,0)
According to Corollary A.2.
- 1, S Baw. For the second term,
| M
-IIJ0000 o (Z(00) 1(0-1,0) oo -z
)[{ <1|J000 o )2(00))) - -J((.. o' (1 )1) + 1J d (Z(1-1.0) - Jt- o o0 (.
{B)1)o(((110)) - d' d( + C. (T - j((-1.1) ||F
(5)
According to the smoothness of a and Lemma A.3, (12((()))))) o' (Z S L,BBA By induction,
- 1 -
L-P-1
$ (.) BAH Tosss (BMBAw Lo ByB Bw)
Σ
B BiyC
As result,
((1.0) <BMBAw + BwB,LaBaz + Bw -
=(BMBAW + BwBBLoBaz) + (L-)) (1I--e-1) c(L--et) B
w
I.-
+(BMBAW + L, Σ Cr
SBL B( ( B.HHttBBBHHL.. BAHL
L-t Σ
+BM + LL
BBBBy Co.
1=0
16

---

Published as a conference paper at ICLR 2022
[j(e-1) - -01-1.--1
-= =|pp. PM ( (MULOIT - (
+ Plb (M (M M 11- -
<Bpsl0e)
C(BpBwCo)) (L- (+1) BAH Looss
1-tt Σ i=0
+ +BMMAw + Lo
B Ci
From Equation 5, we can also conclude that Corollary A.S. || - M((-1,0 S BAM with BAM = By Baz + C.Bas
A.3 BOUNDED FEATURE ERROR AND GRADIENT ERROR In this subsection, we compare the difference between generic GCN and PipeGCN with the same parameter set, i.e., ===00 g(t).
Lemma A.6. [| 2 |1 Ez. E2.1 -1 S En where Ez BAll Σ Cz C Bip
L
and En = BAH > BB)W'
Proof.
(Z((,0)
1:00|| 11 1111e-11 Pos P-
1 (1 H(t.e-1) Poo (t-11--)))1 (H
Bw Bw - ((-)))) + Poel (1 H
I Bv (1 ((1-1) BAH
1-1 By induction, we assume that [[((tt-1)) - H((e S BAR Σ (C. Bp) Therefore,
11(00 - -200 S BwBBBBAB (C.,BBBp)
BAH Ci-1Bi Bip
177000000 1| F = 110 (((00))) - ((((
S Co 1 ((100) - z(0 IF
Ban Σ
CC, Br)*
Lemma A.7. [[(())] - -[00 S E3 and (M,+)) - ( || S EM with
1-3
F, max (Br BB)B - En Br Bw B,, Fez I.,, BAM) )+ Baw BM) 25E5L
Σ
Br Bw Br
FM C. F., + Top Fz
17

---

Published as a conference paper at ICLR 2022
Proof. When E = L, [|J().)) 1( I LHo For any we assume that
1-P-1
[| - 1 S (BpBwCo)) Lioss
+ U
Σ
(BpBwC.)
(6)
1=0
L-t-1
- -M S (BPBBCC)L
+ UCo
E
(B) Lo Lo (7)
1=0
where U = BB B3 BzL + BawBM + Bw BwBAM) We prove them by induction as follows.
| M ||
= =I1 o o' (2(10)) - o o' (Z("))l
$ |1 o 0' ((((0)))) - -J((.0) o' dz(z + | o oz j(0) o o (z(
s BBllld 0'(2())11F + C. 1 - ||
Here (10'(Z((.0) d' (2(0)) S Lo E'. With Equation 6,
1-
- M S (Bp C,) 1- '-a LooSEE + UC,
Σ
(BpBwCo)*+ Lo
On the other hand,
[ 1(6-1)11e
( + PMM ( - M (ii..)1)))))))
(IPT(TTi..) - 1(0) +
< (PT(it)))) - M M
I BB (0.0) - 11 + Bp ( 1.6) W - Mw..
The first part is bounded by Equation 7. For the second part.
| ( (1 M7 ( ||
S ||M 1 (1-1) (W + | M.W
I Baw BMs Bw BAM
Therefore,
|| ( - J((-1)l1r
< <BpBwllM M F ( 1,0 -
1--
< (Bp 1- LOGEE +U
BpBWCo) +U
(B)PW Eo + U Σ
(BpBwC.)
==0
Lemma A.8. -(00l= S EG where Eg Bp FM + B EH)
Proof.
PPn 1( Pod Pa (0- M PH(OOTMMO)
Pmn Hltee-11 + Pod (1 (1- M40 P M
|PH((L-1) (1.11 ((-1) (
< {B (48-1) (((-1)) + Pau H 1,11)
- (((,)11)]]l) + Br Es
Br BaH) Bp E.
18

---

Published as a conference paper at ICLR 2022
By summing up from ( = to & = I. to both sides, we have
Corollary A.9. |V[(()) V ( l2 S Eloss where Etoss = LEG-
According to the derivation of Ej we observe that Eisss contains factor To simplify the expres- sion of Floss we assume that Bp S 2 without loss of generality, and rewrite Corollary A.9 as the following. Corollary A.10. |VE - V2(0)122 S n where
B3 Closs Co (3BxC2Lng 6Bx + 10Closs C2))
A.4 PROOF OF THE MAIN THEOREM
We first introduce a lemma before the proof of our main theorem.
Lemma A.11 (Lemma in (Cong al., 2021)), An L-layer GCN is Lipsschit smoothness, i.e., [|VC(0,) V ((2))) & Lyl10 82
Now prove the main theorem.
Theorem A.12 (Convergence of PipeGCN, formal). Under Assumptions A.I, A.2, and A.3, we L and number of training iterations can derive the following by choosing learning rate = E
(C() EE
T Σ
(V
where E is defined in Corollary A. & > O is an arbitrarily small constant, L(-) is the loss function, ((0) and 0* represent the parameter vector at iteration and the optimal parameter respectively.
Proof. With the smoothness of the model.
+ Ly *p(t+t)) 0
((0(++1)) - L()()) + )((()))) -0())
= L()()) VL((())) VE(((()) 2 V (V
Let g(0) = vī(0(0)- - VL(0()) and // - 1/1,, we have
((g(++1)) < C(((1)) (L)((()) VC(A()) + 56()) + "
VL((() + 500
2
< ((0 3/ 1V
113
" 11000011 2
From Corollary A.10 know that ||000
2 < <nE. After rearranging the terms,
2 (C((()) - c(o(e=1))) + + E²
|VC(0())
5 "
Summing up from = 1 to T and taking the average.
1 T
2
< (C(((2) - -C(O(T+1)1) 2
T
1/
2 (C(002) L((*)) + 122
ny
where 0* is the minimum point of C(-). By taking 77 an arbitrarily small constant e > 0, we have
and T (L(((1) E(())) with E
T
|VL()())) s 38
19

---

Published as a conference paper at ICLR 2022
B TRAINING TIME BREAKDOWN OF FULL-GRAPH TRAINING METHODS
To understand why PipeGINN significantly boosts the training throughput over full-graph training methods, we provide the detailed time breakdown in Tab. 6 using the same model Tab. (4-layer GraphSAGE, 256 hidden units), in which "GCN" denotes the vanilla partition-parall training illustrated in Fig. ((a). We observe that PipeGCN greatly saves communication time.
Table 6: Epoch time breakdown of full hall-graph training methods on the Reddit dataset.
Method
Total time (s)
Compute (s)
Communication (s)
Reduce (s)
ROC (2 GPUs)
3.63
0.5
3.13
0.00
CAGNET (c=1, GPUs)
2.74
1.91
0.65
0.18
CAGNET (c=2, GPUs)
5,41
4.36
0,09
0.96
GCN (2 GPUs)
0.52
0.17
0.34
0,01
PipeGCN (2 GPUs)
0.27
0.25
0.00
0.02
ROC (4 GPUs)
3.34
0.42
2.92
0.00
CAGNET (c=1, 4 GPUs)
2.31
0.97
1.23
0.11
CAGNET (c=2, GPUs)
2.26
1.03
0,55
0.68
GCN (4 GPUs)
0.48
0.07
0.40
0.01
PipeGCN (4 GPUs)
0.23
0.10
0.10
0.03
20

---

Published as a conference paper at ICLR 2022
C TRAINING TIME IMPROVEMENT BREAKDOWN OF PIPEGCN
To understand the training time improvement offered by PipeGiCN, we further breakdown the epoch time into three parts intrra-artiiiin computation, inter-partition communication, and reduce for aggregating model gradient) and provide the result in Fig. 8. We can observe that: 1) inter- partition communication dominates the training time in vanilla partition-parall training (GCN); 2) PipeGCN (with or without smoothing) greatly hides the communication overhead across different number of partitions and all datasets, e.g., the communication time is hidden completely in 2-partition Reddit and almost completely in 3-partition Yelp, thus the substantial reduction in training time; and 3) the proposed smoothing incurs only minimal overhead (i.e., minor difference between PipeGCN and PipeGCN-GF), Lastly, we also notice that when communication ratio is extremely large (85%+). PipeGCN hides communication significantly but not completely (c.g., 10-partition ogbn-producee which case
in employ those compression and quantization techniques (Alistarh et al. (2017); Seide et al. (2014); Wen et al. (2017); et al. (2018a); Yu et al. (2018) from the area general distributed SGD for further reducing the communication, as the compression is orthogonal to the pipeline method. Besides compression, we can also increase the pipeline depth of PipeGCN, e.g.. using two iterations of compute to hide one iteration of communication, which is left future work.
Reddit
obgn-products
Yelp
1.0
computation
1.4
computation
computation
Epoch time (s)
0.8
communication
communication
communication
Epoch time
1.0
Epoch time
0.6
Feeetker
0.4
0.6
Hachh
0.4
Paach
0.2
2
5
10
Number of partitions
Number of partitions
Number of partitions
Figure 8: Training time breakdown of vanilla crrriilon-ppaallel training (GCN), PipeGCN, and
PipeGCN with smoothing (PipeGCN-GF).
21

---

Published as a conference paper at ICLR 2022
D MAINTAINING CONVERGENCE SPEED (ADDITIONAL EXPERIMENTS)
We provide the additional convergence curves on Yelp in Fig. 9. We can see that PipeGCN and its variants maintain the convergence speed w.r.I the number of epochs while substantially reducing the end-to-end training time.
Yelp partitions)
Yelp (6 partitions)
64-
Score (%6
Tolt F1
PPpGGCN
58
PipcCIN
PPpGGCNGG
PppGCCNGG
HlpeGCN-F
MppGCNN-
PPpxGCN-GF
MPpGGNNGGF
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Epoch
Epoch
Figure 9: The epoch-to-accuracy comparison "Yelp" among the vanilla portitio--paaalle training (GCN) and PipeGCN variants (PipeGCN*), where PipeGCN and its variants achieve a similar convergence as the vanilla training (without staleness) but are twice as fast in terms of wall-clock time (see the Throughput improvement in Tab. 4 of the main content).
22

---

Published as a conference paper at ICLR 2022
E SCALING GCN TRAINING OVER MULTIPLE GPU SERVERS
We also scale up PipeGCN training over multiple GPU servers (each contains AMD Radeon Instinct MI60 GPUs, an AMD EPYC 7642 CPU, and 48 lane PCI 3.0 connecting CPU-GPU and GPU-GPU) networked with 10Gbps Ethernet.
The accuracy results of PipeGCN and its variants summarized in Tab. 7:
Table The accuracy of PipeGCN and its variants on Reddit.
#partitions (#node x #gpus)
PipeGCN PipeGCN-F PipeGCN-G
PipeGCN-GF
2 (1x2)
97.12%
97.09%
97.14%
97.12%
(1x3)
97.01%
97.15%
97.17%
97.14%
4 (1x4)
97.04%
97.10%
97.09%
97.10%
(2x3)
97.09%
97.12%
97.08%
97.10%
8 (2x4)
97.02%
97.06%
97.15%
97.03%
9 (3x3)
97.03%
97.08%
97.11%
97.08%
12 (3x4)
97.05%
97.05%
97.12%
97.10%
16 (4x4)
96.99%
97.02%
97.14%
97.12%
Furthermore, we provide PipeGCN's speedup against vanilla partition-paralley training in Tab. 8:
Table 8: The speedup of PipeGCN and its vatiants against vanilla partition-paralle parallel training Reddit.
#nodes #gpus
GCN
PipeGCN
PipeGCN-G
PipeGCN-F
PipeGCN-GF
1x2
1.00x
1.16x
1.16x
1.16x
1.16x
1 1x3
1.00x
1,22x
1.22x
1.22x
1.22x
1x4
1,00
1.29
1.28x
1.29x
1.28x
2x2
1.00
1.61x
1.60x
1.61
1,60x
2x3
1.00
1,64x
1.64x
1.64x
1.64x
2x4
1.00
1,41x
1.42x
1.41x
1.37x
3x2
1.00
1.65x
1.65
1.65x
1.65
3x3
1.00
1,48x
1.49x
1.50x
1.48
3x4
1.00
1.35x
1.36x
1.35x
1.34x
4x2
1.00
1.64x
1.63x
1.63X
1.62X
4x3
1.00
1,38x
1.38x
1.38x
1.38x
4x4
1.00
1.30x
1.29X
1.29X
1.29x
From two tables above, we can observe that our PipeGCN family consistently maintains the accuracy of the full-graph training, while improving the throughput by 15 15%~~66 % regardless of the machine settings and number of partitions.
23

---

Published as a conference paper at ICLR 2022
F IMPLEMENTATION DETAILS
We discuss the details of the effective and efficient implementation of PipeGCN in this section.
First, for parallel communication and computation, second cudaStream is required for communica- tion besides the default cudaStream for computation. To also save memory buffers for communication, batch all communication (e.g., from different layers) into this second eudaStream. When the popular communication backend, Gloo, is used, we parallelize the CPU-GPU transfer with CPU-CPU transfer.
Second, when Dropout layer is used in GCN model, it should be applied after communication. The implementation of the dropout layer for PipeGCN should be considered carefully so that the dropout mask remains consistent for the input tensor and corresponding gradient. If the input feature passes through the dropout layer before being communicated, during the backward phase, the dropout mask is changed and the gradient of masked values is involved in the computation, which introduces noise to the calculation of followup gradients. As result, the dropout layer can only be applied after receiving boundary features.
24


Reviews:
[{"review_id": "mRmlrfVy21A", "reviewer": "Reviewer_cPnX", "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": "I think the paper is a well-executed work: the discussions about related works are extensive, the idea behind PipeGCN is clearly explained, the convergence speed of PipeGCN is analyzed theoretically and the experiments are comprehensive. \nI have some concerns on the novelty of the paper. As mentioned by the authors, Dorylus considered using stale features. To my knowledge, using stale gradients is well studied in Pipe-SGD related works. PipeGCN seems to combine the two ideas by using both stale features and stale gradients. Thus, the core problem is the technical contribution of the analysis of PipeGCN, which I do not have the technical expertise to evaluate. \nI think the paper can be improved by fixing the following problems.\n1. Experimental comparisons with Dorylus may be included to show the benefits of using stale gradients.\n2. Figure 1 and Figure 2 can be improved. In Figure 1(b), the “…” for Part 2 should be removed and all communication tasks should be explicitly listed (e.g., communicate features, communicate gradients, and note that communicate gradients happen after some computation). In Figure 1(b) and (c), the computation and communication tasks should have iteration counts such that the pipelining idea can be understood. In Figure 2, “communicate for Next L1 backward” happens before the L1 backward of the current iteration, how is that possible? Is it a typo?\n3. The influence of the smoothing technique can be better analyzed. In Table 4, there is not a consistent winner among PipeGCN, PipeGCN-G and PipeGCG-F in model accuracy. \n", "summary_of_the_paper": "This paper proposes PipeGCN, which pipelines communication and computation in distributed GCN training to improve training throughput. Analysis is conducted to show the convergence speed when using both stale gradient and feature vectors. Extensive experiments are conducted to show that PipeGCN significantly improves the efficiency of vanilla distributed GCN training without hurting model accuracy.  ", "summary_of_the_review": "The paper is complete but lacks comparison with an important related work and a justification of the technical challenges.", "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": "ZOqiGv0Sqk", "reviewer": "Reviewer_KmNe", "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 proposes a distributed GCN training on large graphs named PipeGCN. Specifically, the authors hide the communication time by parallelizing the communication and computation process in each layer and using the stale information for parameter updates.  The idea seemed simple and straightforward, and experiments show that the algorithm can achieve up to 2.2x speedup. The authors provide the convergence proof for PipeGCN and propose two smoothing methods for faster convergence. \n\n Several limitations of this paper are listed as follows:\n1. The proof of convergence should be justified better. The author didn’t claim how can the proposed model satisfy Assumptions 3.1-3.3, such as whether the loss function they chose satisfies the Lipschitz continuous condition mentioned in Assumption 3.1. In addition, the convergence proof is not applicable if PipeGCN uses the most commonly used ReLU activation function, as ReLU doesn’t satisfy Assumption 3.2.\n2. Some statements in the paper are not clear enough.  For example, in Table 1 the authors didn’t mention AllReduce of Weight Gradient PipeGCN, whereas it appears in line 32 in Algorithm 1. \n", "summary_of_the_paper": "This paper proposes a distributed full-graph GCN training method to speed up GCN training for large-scale graphs.  Experiments demonstrate its performance and efficiency. Convergence proof is also provided.", "summary_of_the_review": "The authors designed a pipelined distributed GCN training algorithm to speed up large-scale GCN training and demonstrated the performance and efficiency with abundant experimental results. The paper can be accepted if the authors improve the convergence proof and modify the uncleared statements.", "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": "Y7QuRnCusL1", "reviewer": "Reviewer_L5WF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- Simple method that is relatively easy to implement compared to other parallel GNN systems. Does not require complex memory management (e.g. involving CPU memory). That makes it potentially easy to extend to a distributed network setting (multiple machines).\n- The staleness is in activations/gradients, not weights. Intuitively, this leads to more stable convergence (vs stale weights) because (1) the stale activations/gradients only occur on the partition boundaries; (2) the activation/gradient for a neuron on the boundary is a combination of stale (inter-partition) and non-stale (intra-partition) activations/gradients\n- I did not evaluate the theoretical proofs or convergence rate for mathematical correctness, but the fact that the method converges at all is intuitively reasonable, given that stale gradient systems are already known to converge.\n\nWeaknesses\n- It is rather surprising that vanilla partition parallel, a simple baseline that many other GNN systems are adapted from, beats recently published (2020) methods by a very wide margin, such as ROC and CAGNET. Although the authors did give some analysis as to why this is the case, I am not convinced those could be the major factors. It is more likely that the baselines have been misconfigured. For the avoidance of doubt, the authors should provide numerical evidence that their obtained results are consistent with the results reported in the ROC and CAGNET papers.\n- The method relies on a somewhat brittle assumption that inter-partition communication time is roughly equal to activation/gradient computation time. If the communication time for a given model and partitioning were significantly smaller or larger than the computation time, the throughput gain from parallelizing computation with communication would be much less impressive. Ultimately, the method does not truly solve the issue of overwhelming communication volume - which sampling-based methods do address. The paper should acknowledge this limitation, rather than claiming superiority in all scenarios to sampling based methods.\n\nMinor issues and suggestions\n- The authors should not use the word \"distributed\" unless the implementation and experiments support networked machines. The hardware configuration in the experiments is a single machine with multiple GPUs.\n- It is interesting that the experiments were performed on commodity hardware with what I understand to be no NVLink, and only PCIe v3 x16 connections. The bandwidth of PCIe v3 connections is roughly comparable to 100-200Gbps network connections. I take that as a promising sign that the method will continue to perform well with distributed network machines.\n", "summary_of_the_paper": "A method of partitioning GNNs, and using stale versions of activations across partitions. This allows activations to be communicated in parallel (rather than sequentially) across GPUs, which improves throughput. Theoretical results show that the stale activations still result in convergence, and empirically the method appears to perform better than the rate given by the theory.", "summary_of_the_review": "While the idea of stale activations/gradients is not new (as the authors have acknowledged in the related work), the convergence result seems new to the best of my limited knowledge. I am positive that (1) validation accuracy is essentially equal to the non-stale version; (2) based on the PCIe bandwidth in the experiments, the method should also work in distributed inifiniband or 100+Gbps ethernet settings. However, I do have concerns about (A) how the ROC and CAGNET results were obtained, and (B) the method only performs well in a narrow \"Goldilocks zone\" where computation time is roughly equal to communication time.\n\nOn the last point - the authors might want to consider what happens at the billion+ node scale. In my experience, the distribution of very high degree nodes increases, and it is likely that nodes with an extreme number of neighbors will end up on the boundary. This could greatly increase communication time relative to computation, and the method would no longer perform well.\n\nOverall, it is an interesting if slightly flawed paper, and I lean towards acceptance.", "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": "M1HdqQw8QIR", "reviewer": "Reviewer_59N6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n1. It analyzes two efficiency bottlenecks in distributed training, including communication overhead and synchronization, and proposes PipeGCN to pipelining the inter-partition communication with intra-partition computation.\n2. The paper provides novel theoretical proof of the convergence of GCN training with stale feature and feature gradients, which is useful for future work.\n3. The experiment results show a significant speedup of the training for the GCN model on multiple reported datasets and compares it with the other latest methods.\n\n**Weakness**\n1. The PipeGCN aims at scaling graph neural network training, but the setup of the largest dataset, ogbn-papers100M, is not practical. With only 2 layers and 8 hidden units, the GNN may not learn anything from the graph. Also, the accuracy on ogbn-papers100M is missed in the result table. With that in mind, I am concerned about the scalability of the system.\n2. For each dataset, the paper only shows the results for a fixed number of partitions. It would be great to see how the speed and convergence differ when the number of partitions and computation nodes increases. \n3. The results in Table 6 are vague, without showing the dataset used and what is the dist GCN method.", "summary_of_the_paper": "The authors propose PipeGCN - a method for efficiently distributed full-graph GCN training. The method pipelines communication with computation in distributed GCN training to hide substantial communication overhead. The paper leads an effort to study pipelined and asynchronous distributed training of GCNs with a new smoothing method aimed at reducing the error incurred by stale features/feature gradients at minimal overhead.", "summary_of_the_review": "The paper proposes an interesting framework to speed up the GCN training with the theoretical proof for the complexity. However, as mentioned in the weaknesses above, the weird setup on the largest dataset, ogbn-papers100M, and lacking the evaluation on a different number of computation nodes, it is hard to understand the scalability of the system.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes PipeGCN, a system that uses pipeline parallelism to accelerate distributed training of large-scale graph convolutional neural networks. Like some pipeline-parallel methods (but unlike others), PipeGCN involves asynchrony in the sense that its features and feature-gradients can be stale. The paper provides theoretical guarantees on the convergence of PipeGCN in the presence of this staleness, which is a nice contribution in itself. In discussion, the reviewers found the work to be well-executed and sound. All reviewers recommended acceptance, and I concur with this consensus.
Decision: Accept (Poster)