Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks
Authors: Peng Jiang
Masuma Akter Rumi
Venue:  (2021)
Keywords: Graph Convolutional Networks
Sampling
Distributed Training

Abstract: Training Graph Convolutional Networks (GCNs) is expensive as it needs to aggregate data recursively from neighboring nodes. To reduce the computation overhead, previous works have proposed various neighbor sampling methods that estimate the aggregation result based on a small number of sampled neighbors. Although these methods have successfully accelerated the training, they mainly focus on the single-machine setting. As real-world graphs are large, training GCNs in distributed systems is desirable. However, we found that the existing neighbor sampling methods do not work well in a distributed setting. Specifically, a naive implementation may incur a huge amount of communication of feature vectors among different machines. To address this problem, we propose a communication-efficient neighbor sampling method in this work. Our main idea is to assign higher sampling probabilities to the local nodes so that remote nodes are accessed less frequently. We present an algorithm that determines the local sampling probabilities and makes sure our skewed neighbor sampling does not affect much to the convergence of the training. Our experiments with node classification benchmarks show that our method significantly reduces the communication overhead for distributed GCN training with little accuracy loss. 


Under review as a conference paper at ICLR 2021
COMMUNICATION-EFFICCNNN SAMPLING FOR DIS- TRIBUTED TRAINING OF GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Training Graph Convolutional Networks (GCNs) is expensive it needs ag- gregate data recursively from neighboring nodes. To reduce the computation overhead, previous works have proposed various neighbor sampling methods that estimate the aggregation result based on a small number of sampled neighbors. Although these methods have successfully accelerated the training, they mainly focus on the single-machine setting. As real-world graphs are large, training GCNs distributed systems is desirable. However, we found that existing neighbor sampling methods do not work well in distributed setting. Specif- ically, a naive implementation may incur a huge amount of communication feature vectors among different machines. To address this problem, propose communication-effiicn neighbor sampling method in this work. Our main idea is assign higher sampling probabilities to the local nodes so that remote nodes are accessed less frequently. We present an algorithm that determines the local sam- pling probabilities and makes sure our skewed neighbor sampling does affect much to the convergence of the training. Our experiments with node classifica- tion benchmarks show that our method significantly reduces the communication overhead for distributed GCN training with little accuracy loss.
INTRODUCTION
Graph Convolutional Networks (GCNs) are powerful models for learning representations of at- tributed graphs. They have achieved great success in graph-based learning tasks such as node clas- sification (Kipf & Welling 2017 Duran & Niepert 2017). link prediction (Zhang & Chen 2017 2018), and graph classification (Ying et al. 2018b Gilmer et al. 2017).
Despite the success of GCNs, training deep GCN large-scale graphs is challenging. To compute the embedding of a node, GCN needs to recursively aggregate the embeddings of the neighboring nodes. The number of nodes needed for computing single sample can grow exponentially with respect to the number of layers. This has made mini-batch sampling ineffective to achieve efficient training of GCNs. To alleviate the computational burden, various neighbor sampling methods have been proposed (Hamilton et al. 2017 Ying et al. 2018a Chen et al. 2018b; Zou et al.) 2019 Li al. 2018 Chiang et al. 2019; Zeng et al. 2020). The idea is that, instead of aggregating the embeddings of all neighbors, they compute an unbiased estimation of the result based on a sampled subset of neighbors.
Although the existing neighbor sampling methods can effectively reduce the computation overhead of training GCNs, most them assume single-machine setting. The existing distributed GCN sys- tems either perform neighbor sampling for each machine/GPU independently (e.g., PinSage (Ying) ct al., 8a) AliGraph (Zhu et al. 2019), DGL (Wang et al. 2019 ) or perform a distributed neigh- bor sampling for all machines/GPUs (e.g., AGL (Zhang et al. 2020 If the sampled neighbors on a machine include nodes stored on other machines, the system needs to transfer the feature vectors of the neighboring nodes across the machines. This incurs a huge communication overhead. None of the existing sampling methods or the distributed GCN systems have taken this communication overhead into consideration.

---

Under review as a conference paper at ICLR 2021
In this work, we propose communication-efio eefficient neighbor sampling method for distributed train- ing of GCNs. Our main idea is to assign higher sampling probabilities for local nodes so that remote nodes will be accessed less frequently. By discounting the embeddings with the sampling probabil- ity, we make sure that the estimation is unbiased. We present an algorithm to generate the sampling probability that ensures the convergence of training. To validate sampling method, conduct experiments with node classification benchmarks on different graphs. The experimental results show that our method significantly reduces the communication overhead with little accuracy loss.
2 RELATED WORK
The idea of applying convolution operation to the graph domain first proposed by [Bruna et al. 2013). Later, Kipf & Welling (2017) and Defferrard et al. (2016) simplify the convolution compu- tation with localized filters. Most of the recent GCN models (c.g., GAT (Velickovic et al.) (0188). GraphSAGE (Hamilton al. 2017), GIN (Xu ct al. 2019)) are based on the GCN in Kipf & Welling (207)) where the information is only from 1-hop neighbors in each layer of the neural network. In Kipt & Welling (0117), the authors only apply their GCN to small graphs and use full batch for training. This has been the major limitation of the original GCN model as full batch training is expensive and infeasible for large graphs. Mini-batch training does help much since the number of nodes needed for computing a single sample can grow exponentially as the GCN goes deeper. To overcome this limitation, various neighbor sampling methods have been proposed to reduce the computation complexity of GCN training.
Node-wise Neighbor Sampling: GraphSAGE (Hamilton et al. 2017 proposes to reduce the re- ceptive field size of each node by sampling fixed number of its neighbors in the previous layer. PinSAGE (Ying al. (018a) adopts this node-wise sampling technique and enhances it by intro- ducing an importance score to each neighbor. It leads to less information loss due to weighted aggregation. VR-GCN (Chen et al. 2018a) further restricts the neighbor sampling size to two and uses the historical activation of the previous layer to reduce variance. Although it achieves compara- ble convergence to GraphSAGE, VR- RCG incurs additional computation overhead for convolution operations historical activation which can outweigh the benefit of reduced number of sampled neighbors. The problem with node-wise sampling is that, due to the recursive aggregation, it may still need to gather the information of large number of nodes to compute the embeddings of mini-batch.
Layer-wise Importance Sampling: To further reduce the sample complexity, FastGCN (Chen
et al. (2018)) proposes layer-wise importance sampling. Instead of fixing the number of sampled neighbors for each node, fixes the number of sampled nodes in each layer. Since the sampling is conduced independently in each layer, it requires a large sample size to guarantee the connectivity between layers. To improve the sample density and reduce the sample size, Huang et al. (2018) and Zou et al. (019)) propose to restrict the sampling space to the neighbors of nodes sampled in the previous layer.
Subgraph Sampling: Layer-wise sampling needs to maintain a list of neighbors and calculate a new sampling distribution for each layer. It incurs an overhead that can sometime deny the benefit of sampling, especially for small graphs. GraphSAINT (Zeng et al. 2020) proposes to simplify the sampling procedure by sampling a subgraph and performing full convolution on the subgraph. Similarly, ClusterGCN (Chiang et al. 2019) pre-partitions graph into small clusters and constructs by randomly selecting subsets of clusters during the training.
All of the existing neighbor sampling methods assume single-mache machine setting. As we will show in the next section, a straightforward adoption of these methods to a distributed setting can lead to a large communication overhead.
3 BACKGROUND AND MOTIVATION
In a -layerr GCN, the 1-th convolution layer defined 1100 Po where (1)) represents the embeddings of all nodes layer / before activation, (0) X represents the feature vectors, is the activation function, P is the normalized Laplacian matrix of the graph, and ( is
2

---

Under review as a conference paper at ICLR 2021
GPU-1
GPU-2
GPU-3
Figure I: An example of distributed GCN training. Left: A graph with 8 nodes are divided into four parts and stored on four GPUs. Right: For a two-layer GCN, to compute the embedding of node A, need the feature vectors of node A. B, E, and F; to compute the embedding of node B, need the feature vectors of node B, C. D, E, F, G. Nodes that are not on the same GPU need to be transferred through the GPU connections.
the learnable weights at layer 1. The multiple convolution layers in the GCN can be represented as
H(M) Po (
HO3
The output embedding H(M) is given to some loss function for downstream learning tasks such node classification or link prediction.
GCN as Multi-level Stochastic Compositional Optimization: As pointed out by Cong et al. 2020), training GCN with neighhor sampling be considered multi-level stochastic com- positional optimization (SCO) problem (although their description is not accurate). Here, we give a more precise connection between GCN training and multi-level SCO. Since the convergence prop- erty of algorithms for multi-level SCO has been extensively studied (Yang et al.) 2019 Zhang & study the convergence of GCN trainig with different neighbor sampling methods. We can define the graph convolution at layer 1 E M1 as a function ( = ()) The embedding approximation with neighbor sampling can be considered as a stochastic function fur pp0 (0000(000 ( where p()) is
Xiao 2019 Chen al. 2020), this connection will allow
stochastic matrix with Eu, [P00] = P. Therefore, we have f()) = Eu, (00) The loss function of
the GCN can be written as
(0)) = EWENCH
(M++1) (HM+))
(Ewsc
((M)
(2)
Here, 0 is the set of learnable weights at all layers (W()),... W(A0 ((M+1) F(H(M)), and the stochastic function ( corresponds to the mini-batch sampling.
Distributed Training of GCN: As the real-world graphs are large and the compute/memory ca- always desirable to perform distributed training GCNs. A possible scenario would be that train GCN on multi-GPI system. The global memory of single GPU cannot accommodate the feature vectors of all nodes the graph. It will be inefficient store the feature vectors the CPU main memory and move the feature vectors GPU in each iteration of the training process because the data movement incurs a large overhead. We want to split the feature vectors and store them on multiple GPUs so that each GPU can perform calculation on its local data. Another possible scenario would be that we have large graph with rich features which cannot be store a single machine. For example, the e-commerce graphs considered in AliGraph (Zhu et al. 2019) can 'contain tens of billions of nodes and hundreds of billions of edges with storage cost over 10TB easily'. Such graphs need be partitioned and stored on different machines in distributed system. Figure shows an example of training two-layer GCN four GPUs. Suppose full neighbor convolution is used and each GPU computes the embeddings of its local nodes. GPU-0 needs to compute the embeddings of node A and B and obtain stochastic gradient ýo based on the loss function. GPU-1 1 needs to compute the embeddings of node and D and obtain stochastic gradient 91. Similarly, GPU-2 and GPU-3 compute the embeddings of their local nodes and obtain stochastic gradient ÿ2 and Gs- The stochastic gradients obtained on different GPUs are then averaged and used to update the model parameters.
pacity a single machine is limited,
Communication of Feature Vectors: As shown in Figure I the computation of a node's 's embed- ding may involve reading the feature vector of remote node. To compute the embedding of node
3

---

need to Under review as a conference paper at ICLR 2021
A on GPU-O, we need the intermediate embeddings of node B and E, which in turn need the feature vectors of node A, B, C. and F (Note that the feature vector of node E itself is needed to compute its intermediate embeddingg the same for node B). Since node C, E, F are not GPU-0, send the feature vectors node C from GPU-1 and node E, from GPU-2. Similarly, to compute need feature vectors of node B, C, D, E, F and G, which
the embedding of node B on GPU-O, means that GPU-0 needs to obtain data from all of the other three GPUs. This apparently incurs large communication overhead. Even with neighbor sampling, the communication of the feature vectors among the GPUs are unavoidable. In fact, in our experiments on a four-GPU workstation, the communication can take more than 60% of the total execution time with naive adoption of neighbor sampling. The problem is expected to be more severe distributed systems with multi- ple machines. Therefore, reducing the communication overhead for feature vectors critical to the performance of distributed training of GCNs.
4 COMMUNICATION-EFFIIII
NEIGHBOR SAMPLING
To reduce the communication overhead of feature vectors, a straightforward idea is to skew the probability distribution for neighbor sampling so that local nodes are more likely to be sampled. More specifically, to estimate the aggregated embedding of node i's neighbors (i.e., LjEN() WiyTy where (i)) denotes the neighbors of node i, æij is the embedding of node j. and waj is its weight), we can define a sequence of random variables E, ~ Bernoulli(p)) where Py is the probability that node j in the neighbor list is sampled. We have an unbiased estimate of the result as
Σ JEN(()
(3)
The expected communication overhead with this sampling strategy is
comm_overhead or E
Σ E Σ Pj
(4)
JER
jER
where R is the set of remote nodes. Suppose we have a sampling budget B and we denote all the local nodes as We can let EjEN(O) Pj = Ej Pj ΣjER Pj = B so that neighbors are sampled on average. It is apparent that, if we increase the sampling probability of local nodes (i.e., EjeLP;), the expected communication overhead will be reduced. However, the local sampling probability cannot be increased arbitrarily. As extreme case, if we let ΣjeL Pj B, only the local nodes will be sampled, but we will not be able to obtain an unbiased estimate of the result, which can lead to poor convergence of the training algorithm. We need sampling strategy that reduce the communication overhead while maintaining an unbiased approximation with small variance.
4.1 VARIANCE OF EMBEDDING APPROXIMATION
Consider the neighbor sampling layer I ++ Suppose S is the of sampled nodes layer sample from all the neighbors of nodes in S; and estimate the result for each of the node using (3). The total estimation variance
7. We
V E
Σ ieS:
Σ
1 E Pj
Σ JEN(S))
WigJy
Σ JEN(S.)
( (2-11)
||wai|l |,311 (5)
JEN(S))
Here ||w.,|1² Eies, w is the sum of squared weights edges from nodes S to node j. Clearly, the smallest variance achieved when p, 1, Vj. and corresponds to full computation. Since we are given sampling budget, we want to minimize V under the constraint EjeN(s,) P5 S
B. The optimization problem is infeasible because the real value of || / is unknown during the sampling phase. Some prior work uses ||=; from the previous iteration of the training loop to obtain an optimal sampling probability distribution (c.g., (Cong et al. (0200). This however incurs an extra overhead for storing 2y for all the layers. A more commonly used approach is consider
4

---

Under review as a conference paper at ICLR 2021
2 bounded by constant C' and minimize the upper bound of V Chen et al. 2018b
Zou
et al. 2019).
The problem can be written as a constrained optimization problem:
(-) -1
min
Σ
||w=ill C
Pj
(EN(S.)
subject to JEN(S.)
Σ
Pj S B.
0 Pj S
The Sampling Method Used in Previous Works: Although the solution to the above problem can
be obtained, it requires expensive computations. For example, Cong al. (2020) give algorithm that needs sort |w,il' 2 and searches for the solution. As neighbor sampling is performed each layer of the GCN and in each iteration of the training algorithm, finding the exact solution to (6)
may significantly slowdown the training procedure. Chen al. (2018b) and Zou et al. (2019) adopt a simpler sampling method. They define discrete probability distribution over all nodes in ((S) and assign the probability of returning node j as
0j Σ EKEN(S.) ||
They the sampling for B times (without replacement) to obtain B neighbors. We call this sampling method linear weighted sampling. Intuitively, if a node is the neighbor list of many nodes in Sj (i.e., ||w,p|| is large), has high probability of being sampled. More precisely, the probability of node j being sampled is
Pj = (1-9)) 9.
we can obtain an upper bound of the variance of embedding approxi- mation with this linear weighted sampling method as
Plugging into 8 and 6
Vin
[N(S) B
1)
Σ kEN(S.)
|| C
Due to its easy calculation, adopt this sampling strategy in work, and skew the sampling probability distribution to the local nodes so that the communication overhead can be reduced.
4.2 SKEWED LINEAR WEIGHTED SAMPLING
Our idea is scale the sampling weights of local nodes by factor > More specifically, divide the nodes in N (S)) into the local nodes L and the remote nodes R, and we define the sampling probability distribution as
Wey 1|
ifjeL L
9j = Exer. s|I 12
+
EVER
(10)
if E R.
Enel e|lw.all
Compared with (7). (10) achieves a smaller communication overhead because ΣjER Pj is smaller. We call our sampling method skewed linear weighted sampling. Clearly, the larger we use, the more communication we save. Our next task is to find that can ensure the convergence of the training.
We start by studying the approximation variance with our sampling method. Plugging 10p into (
and (6. we can obtain an upper bound of the variance as
[ sB
R
Vakewed
+
Σ KEL
|| 112 + Σ
||wasll"
Σ |
C
(11)
B
KER
KEN(SE
(8
1)
R
| C (1
8)
Vinr
| C.
B
&B
KEL
RER
5

---

Under review as a conference paper at ICLR 2021
Note that the variance does not necessarily increase with the skewed neighbor sampling (the last term of (1I) is negative).
Since GCN training is equivalent to multi-level SCO explained in the Background section,
can use the convergence analysis of multi-level SCO to study the convergence of GCN training with skewed neighbor sampling. Although different algorithms for multi-level SCO achieve different convergence rates (Yang et al.] 2019; Zhang & Xiao 2019] Chen et al.] 2020), for general non- convex objective function L, all of these algorithms have the optimality error (f(x C*) or V V((+++1)) bounded by some terms that are linear to the upper bound of the approximation variance each level. This means that if we can make sure Vekewed O ((Viar). our skewed neighbor sampling will not affect the convergence of the training. In light of this, we have the following theorem for determining the scaler (10)
Theorem 1. When the number of remole nodes |R] > 0, with some small constant D, if set
(()N(()) B) + -
(12)
R
the training algorithm using sampling probability in (T0) will achieve the same convergence rate
as using the linear weighted sampling probability in 7
Proof. If we set Vekewed S D1 Ving with some constant D1, we can calculate an exact upper bound
of by solving the equations with 7 and (10 The upper bound is Ti+Tz + TT22+ where T2 ((D) -11)))1()))))-----001100- -B) Exegllwalll T3 | Eegllel
Ti (Di (D1-1)( 10[-)111))
74
[M]] Enez llock
[T]] Enez m
[L] is the number of local nodes. |/ is the number of remote nodes, and B is the sampling budget. For simple computation, we ignore all the terms dependant on ΣvEL |w 112 and EvER ||
and it gives us a feasible solution s _/2 (()
+ where = Pi-1
R
is large), we can sample the local nodes more frequently, and (12) gives us a larger If we have a large sampling budget B, the estimation variance of the linear weighted sampling (9) is small. We will need to sample enough remote nodes
Intuitively, if there are few remote nodes (i.c., [N(S)) R
to keep the variance small, and (12) gives us a smaller s.
5 EXPERIMENTAL RESULTS
We evaluate our communication-efficiii sampling method in this section.
5.1
EXPERIMENTAL. SETUP
Platform: We conducted our experiments on two platforms: a workstation with four Nvidia RTX 2080 Ti GPUs, and eight machines each with an Nvidia P100 GPU in HPC cluster. The four GPUs in the workstation are connected through PCle 3.0 x16 slot. The nodes in the HPC cluster connected with 100Gbps InfiniBand based on fat-tree topology. Our code is implemented with PyTorch 1.6. We use CUDA-aware MPI for communication among the GPUs. To enable the send/recv primitive in PyTorch distributed library, compile Py Torch from source with OpenMPI 4.0.5.
Datasets: We conduct our experiments on five graphs as listed in Table ! Cora and CiteSeer are two small graphs that are widely used previous works for evaluating GCN
Table 1: Graph datasets.
Graph
#Nodes
#Edges
Cora
2.7K
10.5K
performance (Zou et al.) 2019 Chen et al.] 2018b) Zeng jet al. 2020). Reddit is a medium-size graph with 233K
CiteSeer
3.3K
9.2K
Reddit
233K
58M
nodes and average degree of 492. Amazon is large graph with more than 1.6M nodes and 132M edges (Zeng) al. 2020), We use the same configurations of training set. validation set, and test set for the graphs as in previous works Zou et al., 2019 Chen et al. 2018b
Tube
1.1M
6.1M
Amazon
1.6M
132M
Zeng et al. 2020). Youtube is large graph with more than 1M nodes (Mislove al. 2007). Fach

---

Under review as a conference paper at ICLR 2021
Table Comparison of our sampling method with naive adoption of the LADIES sampler on Cora and CiteSeer.
Graph
Sampling Method
F1-Score (%)
Communication Data Size (#nodes)
Full
74.46 I.36
402582291 1 410933
Our (D=4)
74.82 0.97
316248197 1 165161
Cora
Our (D=8)
75.84 + 1.05
299891935 1 267364
Our (D=16)
75.80 + 1.69
284031348 = 295241
Our (D=32)
74.96 + 1.15
270444788 = 290565
Full
66.54 1.80
900858801 + 595144
Our (D=4)
65.58 + 2.52
722616380 = 588753
CiteSeer
Our (D=8)
65.50 + 2.43
704497231 = 518062
Our (D=16)
65.36 + 2.48
689739665 = 438101
Our (D=32)
65.64 + 2.51
679202038 = 413854
node represents user, and the edges represent the links among users. The graph does not have feature vector or label information given. We generate the labels and feature vectors based on the group information of the nodes. More specifically, we choose the 64 largest groups in the graph as labels. The label of each node is a vector of length 64 with element value of O or 1 depending on whether the node belongs the group. Only the nodes that belong to least one group are labeled. For feature vector, we randomly select 2048 from the 4096 largest groups. If a node does not belong to any group, its feature vector We use 90% of the labeled nodes for training and the remaining 10% for testing.
Benchmark and Settings: We use 5-layer standard GCN (as in Formula (I) perform node classification tasks on the graphs. For Cora, CiteSeer, Reddit and Amazon whose labels are single value, we use the conventional cross-entropy loss to perform multi-class classification. For YouTube, since the nodes' labels are vectors, we use binary cross entropy loss with a rescaling weight of 50 to perform multi-label classification.. The dimension of the hidden state is set to 256 for Cora, CiteSeer and Reddit. The dimension of the hidden state is set to 512 for YouTube and Amazon. For distributed training. we divide the nodes evenly among different GPUs Each GPU runs sampling- independently, with the gradients averaged among GPUs in each iteration.
training
We incorporate our skewed sampling technique into LADIES (Zou et al. 2019) and Graph SAINT (Zng et al. 2020), both of which use linear weighted sampling in (7) The only dif- ference is that LADIES uses all neighbors of nodes at layer as N(S) when it samples nodes at layer/+1. while GraphSAINT considers all training nodes ((i) when it samples the subgraph.
We compare the performance of three versions. The first version (Full) 1) uses the original linear weighted sampling and transfers sampled neighbors among GPUs. The second version (Local) also uses linear weighted sampling but only aggregates neighboring nodes on the same GPU. The third version (Our) uses our skewed sampling and transfers sampled neighbors among GPUs.
5.2
RESULTS ON KINGLE-MACHIG WITH MULTIPLE GPUs
2.0
We use LADIES to train the GCN with Cora, CiteSeer, Reddit and Youe graph on the four-GPU workstation. The batch size on each GPU is set to 512, and the number of neighbor samples in each intermediate layer is also set 512.
Training Loss
1.5
Full
1.0
Local
Cora and CiteSeer Results: Although these two graphs are small and can be easily trained on a single GPU, we apply distributed training to these two graphs and measure the total communication data size to show the benefit of our sampling method. Table 2 shows the best test accuracy and the total communication data size 10 epochs training. The results are collected in 10 different runs and we report the mean and deviation of the numbers. Compared with the colmunicmnii version, our sampling method does not cause any accuracy loss for Cora with D (in Formula (12) set to 4, 8, 16, 32. For CiteSeer, the mean accuracy in different runs decreases by about 1% with our sampling method. However, the best accuracy in different runs matches the best accuracy of full-communication version. Figure
(D=4)
Our (D=B)
0.5
Our (D-16)
Our (D=32)
0.0
Epochs
Figure 2: Training loss over epochs on Cora
7

---

Under review as a conference paper at ICLR 2021
3000
Computation Communication
Execution Time (sex)
Training Loss
F1-Score (%
2000
Local
Our (D+4)
60
2
(D=8)
(D=16)
1000
Our (D.44)
(D-8)
1
Our (D-16)
10
30
40
50
0
10
20
30
50
Full
Our (D=4) (D+8)
Our (D-16)
Epochs
Epochs
(a) Training Loss
(b) Validation Accuracy
(c) Execution Time
Figure 3: Results on Reddit graph.
6000
Full
Computation Communication
30
Execution Time [Sec)
30
Training Loss
Our (D-B)
Our (0m-4)
4000
(D=16)
1-Sccre
20
10
Local
2000
10
Our (D-4)
JNN
(D=
(0m16)
0
100
200
300
100
200
300
Our (D=4)
Our (D=8)
(D=16)
Epochs
Epochs
Training Loss
(b) Validation Accuracy
(c) Execution Time
Figure 4: Results on YouTube graph.
shows the training loss over epochs with different sampling methods on Cora. We can see that local aggregation leads poor convergence, due the loss of information in the edges across GPUs. The other versions have the model converge to optimal after 3 epochs. The training loss on CiteSeer follows a similar pattern. The results indicate that our sampling method does not impair the convergence of training.
The execution times of different versions almost the same on these two small graphs because the communication overhead is small and reducing the communication has little effect to the overall performance. Therefore, instead of reporting the execution time, we show the communication data size of different versions. The numbers in Table are the numbers of nodes whose feature vectors are transferred among GPUs during the entire training process. We can see that the communication is indeed reduced. When D = 32, our sampling method saves the communication overhead by 1.48x on Cora and 1.32x on CiteSeer.
These are two larger graphs for which communication overhead more critical to the performance of distributed training. Figure 3 shows the results on Reddit graph. We run the training for 50 epochs and compare the training loss, validation accuracy and exccution time of different versions. The breakdown execution time is shown in Figure Bcl We can that communication takes more than 60% of the total execution time if naively adopt the linear weighted sampling method. Our sampling method reduces the communication time by 1.4x, 2.5x and 3.5x with D
Reddit and You Tube Results:
16, respectively. The actual communication data size is reduced by 2.4x, 3.6x and 5.2x. From Figure Bal we can see that our sampling method converges at almost the 4 or 8. The training converges slower
same rate as the full-communication version when D is when D = 16, due to the large approximation variance. Figure 35 shows the validation accuracy of different versions. The best accuracy achieved by full-communication version is 93.0%. Our sampling method achieves accuracy of 94.3%, 92.4%, 92.2% with D set to 4, 8, 16, respectively. The figures also show that training with local aggregation leads to a significant accuracy loss.
Figure 4 shows the results YouTube graph. We run the training for 300 epochs. As shown Figure 4cc the communication takes more than 70% of the total execution time in the full- communication version. Our sampling method effectively reduces the communication time. The larger we use, the more communication time we save. The actual communication data size is reduced by 3.3x, 4.6x, 6.7x with D set to 4, 8, 16. Despite the communication reduction, sam- pling method achieves almost the same convergence as full-communication version, as shown in Figure 4a and 4b The full-communication version achieves best accuracy of 34.0%, while
8

---

Under review as a conference paper at ICLR 2021
1250
Computation
Training Loss
Local
Our (2+4)
(D=8)
F1-Score (%
Execution Time (ser)
1000
Communication
(Ite16)
750
40
4-
500
20
Our (D.4)
(D=8)
2
0
(D-16)
10 Epochs
10
15
Full
Our (D+4)
(D+6)
Our (D-16)
Epochs
(a) Training Loss
(b) Validation Accuracy
(c) Execution Time
Figure 5: Results on Amazon graph
sampling method achieves best accuracy of 33.4%, 36.0%, 33.2% with D set to 4, 8. 16. In contrast, local aggregation leads to a noticeable accuracy loss. The best accuracy achieves is 28.5%
Comparison with Centralized Training:
Table 3: Execution time of the full-communication version with distributed features on GPUs (Time- Distr) and centralized version with all features stored on CPU and copied to GPU in each iteration Centr).
As we described in Section 3 the motiva- tion of partitioning the graph and splitting the nodes' features among GPUs in a single machine is that each GPU cannot hold the feature vectors of the entire graph. As op: pose this distributed approach, an alterna- tive implementation is to store all the features on CPU and copy the feature vectors of the sampled nodes to different GPUs in each ite eration. For example, PinSage (Ying et al.) 2018a) adopts this approach for training large graphs. To justify our distributed storage of the feature vectors, we collect the performance results of GCN training with this centralized storage of feature vectors CPU. Table 3 lists the training time for different graphs. Even compared with the full-communication baseline in Figure 3c and 4c this centralized approach is 1.2x 13x slower. This is because the centralized approach in- curs large data movement overhead for copying data from CPU to GPU, The results suggest that, for training large graphs on single-machine with multiple GPUs, distributing the feature vectors onto different GPUs is more efficient than storing the graph on CPU,
Graph
Time- (sec)
Time-Centr (sec)
Cora
4.8
58.1
Citeseer
59.8
Reddit
2763.
6622.0
YouTube
5852.2
7028.9
5.3 RESULTS ON MULTIPLE MACHINES
We incorporate our sampling method to GraphSAINT and train a GCN with Amazon graph eight machines in HPC cluster. The subgraph size is set to 4500. With our skewed sampling method, subgraph is more likely to contain nodes on the same machine, and thus incurs less communication among machines. We run the training for 20 epochs. As shown in Figure 5c the communication takes more than 75% of the total execution time the full-communication version. Our sampling method effectively reduces the communication overhead. The overall speedup is 1.7x, 2.8x, 4.2x with set to 4, 8, 16. As shown in Figure Sa and 5b) our sampling method achieves almost the same convergence as full mullccommuiiattoon version. The full-communication version achieves best accuracy of 79.31% 3,,, while our sampling method achieves best accuracy of 79.5%, 79.19%, 79.29% with D set 4, 8, 16. Although the training seems converge with local aggregation on this dataset, there is a clear gap between the line local aggregation and the lines of other versions. The best accuracy achieved by local aggregation is 76. 12%.
CONCLUSION
In this work, we study the training of GCNs in distributed setting. We find that the training per- formance is bottlenecked by the communication of feature vectors among different machines/GPUs. propose the first communication- efficcient sampling method for dis-
Based on the observation, tributed GCN training. The experimental results show that our sampling method effectively reduces the communication overhead while maintaining good accuracy.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203. 2013.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with
variance reduction. In Proceedings of Machine Learning Research, pp. 942-950, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b, 8b.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. arXiv preprint arXiv:2008. 10847, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1393- 1403, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, pp. 0-844388222 2016.
Alberto Garcia Duran and Mathias Niepert. Learning graph representations with embedding propa- gation. In Advances neural information processing systems, pp. 5119-5130, 2017.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272, 2017.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558-4567, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Ruoyu Li. Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In AAAI Conference on Artificial Intelligence, 2018.
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattachar- jee. Measurement and Analysis of Online Social Networks. In Proceedings of the ACM/Useeii Internet Measurement Conference (IMC 07)), San Diego, CA, October 2007.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning graphs. arXiv preprint 19X9v: 01100990.111...... 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Shuoguang Yang, Mengdi Wang, and Ethan X Fang. Multilevel stochastic gradient methods for nested composition optimization. SIAM Journal on Optimization, 2911)61166659 2019..
10

---

Under review as a conference paper at ICLR 2021
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 974 983, 8a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in neural infor- mation processing systems, pp. 4800-4810 2018b.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Raigopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
Dalong Zhang, Xin Huang, Ziqi Liu, Jun Zhou, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Lin Wang, Zhiqiang Zhang, and Yuan Qi. Agl: A scalable system for industrial graph ma- chine learning. In VLDB Endowment, pp. 3125-3137, 2020.
Junyu Zhang and Lin Xiao. Multi-level composite stochastic optimization via nested variance re- duction. arXiv preprint arXiv: 1468, 2019.
Muhan Zhang and Yixin Chen. Weisfeiler-lchman neural machine for link prediction. In Proceed- ings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 575-583. 2017.
Muhan Zhang and Yixin Chen. Link prediction based 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: A comprehensive graph neural network platform. Proc. VLDB Endow. pp. 2094-2105, 2019.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Leyer-dep importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 1129--11259 2019.


Reviews:
[{"review_id": "xtPcPNvrmt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a simple method to reduce the communication for the distributed sampling-based training of GCN. Specifically, communication is reduced by sampling local nodes more and remote nodes less.\n\nThe paper is well written, and motivation has been clearly conveyed. Related works in sampling-based training of GCN are well summarized and categorized. The communication ratio of the proposed skewed linear weighted sampling method explored in experiments is around x1 ~ x7 without noticeable performance degradation.\n\nMajor concerns:\n1) The experiments only explore 4 workers with a compression ratio less than 7. How does the proposed method scale with more workers and larger compression ratios?\n\n2) The proposed sampling method and the original sampling method.\n\nIn Section 4.2, the authors managed to achieve the same sampling variance for linear weighted sampling and the proposed skewed linear weighted sampling, which may partially due to that the variance of the original linear weighted sampling is not optimal. How will the idea of sampling local nodes more frequently work for other sampling methods?\n\nIn experiments, the authors compared the proposed skewed linear weighted sampling with the LADIES sampling method. Why is the original linear weighted sampling method not compared with the proposed skewed linear weighted sampling?\n\n3) It seems that the authors distribute the graph to workers and each worker only holds the local nodes' original data and intermediate activations during training. How the graph is distributed in experiments needs more clarification.\n\n4) The importance of distributed sampling-based training of GCN is not explained. Naive distributed training as in 3) is certainly inefficient involving too much communication of neighborhood nodes' features. However, there seem to be some simple alternatives of 3) as in 4.1) and 4.2).\n\n4.1) Sampling-based training of GCN already makes it feasible to train GCN on large datasets in the single-machine setting. Why can't we just use multiple workers to do the training as in single-machine settings and then average the gradient or average the model periodically like Local SGD [1]?\n\n4.2) Cluster-GCN may also be another alternative as it also makes it feasible to train large GCN in the single-machine setting. Can we make it work for distributed training the same way as in 4.1)?\n\nReferences:\n[1] Stich, Sebastian U. \"Local SGD converges fast and communicates little.\" arXiv preprint arXiv:1805.09767 (2018).\n[2] Chiang, Wei-Lin, et al. \"Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks.\" Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "oQTzbffAw0", "reviewer": "AnonReviewer5", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work considers the challenge of distributed training for GNNs. The approach is a locality-aware importance weighted sampling procedure. I was not given much time to read the paper but it seems like a decent contribution, albeit too minor of a contribution to the existing literature to be considered a bonafide research paper.\n\n### Quality\n\n- There is nothing clearly wrong with the paper. I did not have time to go through all the equations but I can believe the approach.\n\n### Clarity\n\n- The writing is clear and the approach is well described.\n\n### Originality\n\nThere is not a whole lot of originality. Prior work (appropriately cited) has consider a similar approach. The main difference is the locality of sampling to avoid communication.\n\n### Significance of this work\n\n- Important topic, not exciting as a research paper. \n\n### Pros\n\n- Scalability of GNNs is a very important topic that deserves more attention.\n\n- The writing is good; the reader can quickly understand the approach and the main points of the paper. It also helps that the approach is well-known and relatively simple.\n\n### Cons\n\n- Experiments: For a work studying distributed training over graphs with \"billions of nodes\", it is certainly disappointing to see that the datasets contain up to 1.1M nodes. \n\n- The work seems like a direct application of importance weighting and stratified sampling to sampling the neighborhood of node in a GNN. Locality-aware importance sampling is a common approach used in industry, and rather trivial as a method.\n\n\n### Other comments\n\n- Regarding the bound V, it would be nice to get a sense of its magnitude. It does not look very efficient. What if we performed a push sampling operation (where the node that has x_j will sample it with probability ||x_j||^2  and push it to the servers that need it) rather than the proposed pull sampling (where each node requests the samples)? That way we don't need to guess or bound the value of ||x_j||^2. Just a quick thought. \n\n-------\n\nThe rebuttal did not meaningfully addressed my concerns.\n\nApologies to the authors for not providing a reference for my comment on approaches for reducing communication in graph-optimization methods being widely known in industry. GraphLab is an example (https://en.wikipedia.org/wiki/GraphLab)\n\n- Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin and J. Hellerstein. GraphLab: A New Framework for Parallel Machine Learning. In the 26th Conference on Uncertainty in Artificial Intelligence (UAI), Catalina Island, USA, 2010\n- Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin and Joseph M. Hellerstein (2012). \"Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud.\" Proceedings of Very Large Data Bases (PVLDB).\n- Joseph Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, Carlos Guestrin (2012). \"PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs.\" Proceedings of Operating Systems Design and Implementation (OSDI).\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YTs-4WBkV0Y", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a sampling-based approach to speeding-up training of GCNs in distributed systems. The key step in this task involves exchanging and aggregating messages sent along the edges of the graph. If the nodes of the graph are partitioned between several machines, then exchanging those messages involve costly communication between the nodes. To reduce this communication, the paper introduces a variant of the node sampling approach of Chen et al. (2018b) and Zou et al. (2019), where the probabilities of nodes in other machines are scaled down by some factor s. The approach is evaluated experimentally, showing that it reduces the amount of communication while (essentially) preserving the accuracy.\n\nPROS:\n- The first implementation of sampling-based training for GCNs in the distributed scenario (this is according to the authors, but I am not aware of any prior work of this type either)\n - Experimental evaluation shows significant improvement to the communication cost\n\nCONS:\n- The new sampling process is a relatively simple modification of prior work, so there isn't much conceptual novelty in here\n\nOverall, a solid contribution to the area.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-x1PPh8dev", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new distributed training method for GNNs. Specifically, unlike traditional distributed training methods for CNNs where data points are independent, nodes in a graph are dependent on each other. Thus, this dependence incurs communication between different workers in the distributed training of GNNs. This paper aims to reduce the communication cost in this procedure. Here, this paper proposed to sample more neighbor nodes within the same worker while reducing the sampling probability for the neighbor nodes on other workers. It also provides some theoretical analysis and conducts the experiments to verify the proposed method. \n\n1. The idea is simple. It is just a trad-off between intra-worker sampling and inter-worker sampling. In fact, it does not address the real challenge in distributed training of GNNs. Even though sampling more intra-worker neighbor nodes can reduce the communication cost, it will impair the prediction performance. A good solution should reduce communication costs and try to make the prediction performance as good as possible. However, this method only focuses on the former one. \n\n2. In the proof of Theorem 1, this paper assumes there exists a constant $D_1$, and further claims that $D$ is small. However, no evidence is provided to verify $D$ is small.  Thus, the claim in Theorem 1 does not hold. Moreover, without any knowledge regarding $D$, the bound for $s$ is useless. \n\n3. Regarding experiments, an important baseline is missed. Specifically, the method only using intra-worker neighbor nodes should be used. Otherwise, the current experimental results cannot support the efficacy of the proposed method. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new locality-aware importance weighted sampling procedure for distributed training of GNNs. While the paper is interesting, the reviewers raised some fundamental concerns about it.

The focus on the paper is on scalable methods and the experiments or only run on medium-size datasets(<2m nodes). For such a paper larger scale experiments are expected.

Furthermore, the novelty of the paper is limited.

Overall, the paper is below the high acceptance bar of ICLR.
Decision: Reject