Distributed Training of Graph Convolutional Networks using Subgraph Approximation
Authors: Alexandra Angerd
Keshav Balasubramanian
Murali Annavaram
Venue:  (2021)

Abstract: Modern machine learning techniques are successfully being adapted to data modeled as graphs. However, many real-world graphs are typically very large and do not fit in memory, often making the problem of training machine learning models on them intractable. Distributed training has been successfully employed to alleviate memory problems and speed up training in machine learning domains in which the input data is assumed to be independently identical distributed (i.i.d). However, distributing the training of non i.i.d data such as graphs that are used as training inputs in Graph Convolutional Networks (GCNs) causes accuracy problems since information is lost at the graph partitioning boundaries.

In this paper, we propose a training strategy that mitigates the lost information across multiple partitions of a graph through a subgraph approximation scheme. Our proposed approach augments each sub-graph with a small amount of edge and vertex information that is approximated from all other sub-graphs.  The subgraph approximation approach helps the distributed training system converge at single-machine accuracy, while keeping the memory footprint low and minimizing synchronization overhead between the machines. 

Under review as a conference paper at ICLR 2021
DISTRIBUTED TRAINING OF GRAPH CONVOLUTIONAL NETWORKS USING SUBGRAPH APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Modern machine learning techniques are successfully being adapted to data mod- eled as graphs. However, many real-world graphs are typically very large and do not fit in memory, often making the problem of training machine learning models on them intractable. Distributed training has been successfully employed to allevi- ate memory problems and speed up training in machine learning domains in which the input data is assumed to be independently identical distributed (i.i.d). However, distributing the training of non i.i.d data such as graphs that are used training inputs in Graph Convolutional Networks (GCNs) causes accuracy problems since information is lost at the graph partitioning boundaries.
In this paper, we propose training strategy that mitigates the lost information across multiple partitions of graph through a subgraph approximation scheme. Our proposed approach augments each sub-graph with a small amount of edge and vertex information that is approximated from all other sub-graphs. The sub- graph approximation approach helps the distributed training system converge at single-machine accuracy, while keeping the memory footprint low and minimizing synchronization overhead between the machines.
INTRODUCTION
Graphs are used to model data in diverse range of applications such as social networks (Hamiltor al.] 2017a). biological networks (Fout et al.) 2017) and e-commerce interactions (Yang) (201)). Recently, there has been an increased interest in applying machine learning techniques to graph data. breakthrough was the development of Graph Convolutional Networks (GCNs), which generalize
the function of Convolutional Neural Networks (CNNs), operate on graphs (Kipf & Welling 2017).
Training GCNs, much like training CNNs, is a memory and computationally demanding task and may take days weeks to train on large graphs. GCNs are particularly memory demanding since processing a single vertex may require accessing a large number of neighbors. If the GCN algorithm accesses neighbors which are multiple hops away, it may need to traverse disparate sections of the graph with no locality. This requirement poses challenges when the graph does not fit in memory, which is often the case for large graph representations. Previous approaches to alleviate issues of memory and performance seeks to constrain the number of dependent vertices by employing sampling-bat based methods (Hamilton al., 2017b] Chen al. 2018 Huang al., 2018 2018|Chiang et al. 2019). However, sampling the graph may limit the achievable accuracy (Jia et al. 2020).
CNN training turned to data parallel distributed training to alleviate the memory size constraints and the computing capacity of a single machine. Here, number of machines independently train the same neural network model but on an assigned chunk of the input data. To construct single global model, the gradients or parameters are aggregated at regular intervals, such as at the completion of batch (Dean et al. 2012). While this approach works well for CNNs, it more challenging for GCNs due to the nature of the input data. If the training input is set of images, each image is independent. Hence, when the dataset is split into chunks of images, no information is directly carried between the chunks. In contrast, if the input is graph, the equivalent of splitting the dataset into chunks is to divide the large graph into a number of subgraphs. However, GCNs train on graphs which rely not only information inherent vertex but also information from its neighbors.
When a GCN trains on one subgraph and needs information from a neighbor in another subgraph, the information from the edges that span across machines creates communication bottleneck. For

---

Under review as a conference paper at ICLR 2021
example, in our experimental evaluations note that when the Reddit dataset (Hamilton al.) 2017b) is partitioned into five subgraphs, there are about 1.3 million (bidirectional) edges that span across machines. If each edge is followed, 2.6 million messages would be sent, each containing feature vector of 602 single-precision floats, summing up to about 6.3 GB of data transferred each epoch, where one epoch traverses the entire graph. Each training typically requires many epochs. In our experiments running distributed training on the GCN proposed by [Kipf & Welling (2017) one epoch takes about one second. Thus the bandwidth required is enormous. This issue: since the time it takes to finish one epoch decreases when the training is scaled out on more machines, the required bandwidth increases. Even with optimizations such as caching that might be possible (e.g. vertex caching (Yang. 2019)), the amount of communication is significant.
serious scalability
Alternatively, instead of communicating between subgraphs, GCN may ignore any information that spans multiple machines (Jia et al.) 2020). However, we observe that this approach results in accuracy loss due to suboptimal training. For example, when distributed on five compute nodes and ignoring edges that span across machines, we note in our evaluations that the accuracy of GraphSAGt trained on the Reddit dataset drops from 94.94% to 89.95%, a substantial loss in accuracy.
To mitigate this problem, we present distributed training approach of GCNs which reaches an accuracy comparable with training on a overhead low. This allows for GCNs to train very large graphs using distributed system where each machine has limited memory, since the memory usage on each machine scales with the size of its allotted (local) subgraph. We achieve this by approximating the non-local subgraphs and making the approximations available in the local machine. We show that, by incurring a small vertex overhead in each local machine, high accuracy can be achieved. Our contributions in this paper are:
system, while keeping the communication
A novel subgraph approximation scheme to enable distributed training of GCNs on large graphs using memory-constraämg machines, while reaching an accuracy comparable that achieved on single machine.
An evaluation of the approach on two GCNs and two datasets, showing that considerably increases convergence accuracy, and allows for faster training while keeping the memory overhead low.
The rest of the paper is organized as follows. Section 2 walks through the necessary background 3 describes our approach to
and presents experimental data that motivates our approach. Section efficiently distribute GCNs. Section describes our evaluation methodology, while Section presents the results of our evaluation. Section 6 discusses related work before we conclude in Section 7
2 BACKGROUND AND MOTIVATION
In this section we first describe GCNs. Then, we show that GCNs are resilient to approximations in the input graph, and describe how that motivates our approach Section
2.1 GRAPH CONVOLUTIONAL NETWORKS
GCNs are neural networks that operate directly graphs the input data structure. A GCN aims to define an operation similar to a convolutional layer in CNNs, where a parameterized filter is applied to a pixel and its neighbors in an image (Fig D]. In the graph setting, the pixel corresponds vertex, and the edges from the vertex point out its neighbors FFg(2). Early approaches to define this operation used graph convolutions from spectral graph theory (Bruna et al. 2014 Henafl et al. 2015). While theoretically sound, these approaches are difficult to scale to large graphs. (Wu et al. 2020). Recent research (e.g. (Hamilton et al. [0176] Chen et al. 2018) instead takes spatial based approach, which enables computation in batches of vertices.
The goal of GCN is a set of vertices and E is a set of edges. The input is feature matrix X, where each row represents the feature vector 2. for every vertex v E V, and an adjacency matrix A which represents the edges E E. Each layer in can be described H² f(H ( A), H X, where is the layer order and ff is a propagation rule (Kipf & Welling (017). The number of layers and the propagation rule differ between GCNs. While our proposal is general to all GCNs of this type, we evaluate it on the GCN proposed by Kipf & Welling (2017). which we call KW-GCN, and GraphSAGE proposed by Hamilton al. (2077b). Both GCNS are described in more detail in Section 4.1
learn the parameters of a neural network given a graph G= (V, F) where V
2

---

Under review as a conference paper at ICLR 2021
micee
GropeSAGL
0.2
0.4
0.6
3.0
Fraction trwining ng verlices removed
Figure 1: convolution.
Image
Figure 2:
Graph Figure Accuracy when randomly removing a certain fraction of the training vertices.
convolution.
2.2
LIMITATIONS TO INPUT APPROXIMATIONS
Our proposal builds upon the observation that GCNs may be resilient to approximations in the input graph. To investigate the extent of resilience, we trained both KW-GCN and GraphS on the Reddit dataset (Hamilton al. 2017b), described in Section 4.2 for the task of vertex classification.
To introduce approximations in the input graph, we randomly select an increasingly larger fraction of the training vertices to be deleted. We then use the approximated graph to train each GCN and compute the micro Fl score (the micro-averaged harmonic mean of precision and recall, which we call accuracy) on the complete test set. observation: while GraphSAGE and KW-GCN are not equivalent in their resiliency towards vertex deletion, both networks demonstrate that up until a certain point it is possible to delete vertices without large accuracy drop. While this might seem like trivial but promising approach train more efficiently by simply dropping vertices, in practice the threshold for deletion must be large to make a significant impact on the memory footprint: 50% of the vertices has to be removed to reduce the memory footprints by 2X. Such a high deletion fraction incurs an unacceptable accuracy penalty,
shows the results. We make the following qualitative
In this work, we instead leverage this observation to gain partial knowledge about non-local subgraphs in distributed setting. While this approach increases the total workload by introducing redundancy. we show Section that only small overhead is needed substantially increase accuracy. In the next section we describe our proposed solution that exploits the approximation resilience property.
3 DISTRIBUTED TRAINING OF GCNS USING SUBGRAPH APPROXIMATION
A common approach achieve distributed training is leverage data parallelism: the training data divided into mutually exclusive sets, and each machine assigned one of these sets. Aside from decreasing training time, data parallelism also reduces memory footprint by lowering the amount of data each machine has to handle. If the graph does not fit in memory, the performance will be significantly impacted due storage access time (Ham al. 2016 Ahn et al. 2015).
The main challenge of distributed subgraph training is accuracy. Each machine has only knowledge about the graph structure in its own partition. The result is that important information embedded in other parts of the graph is not captured in local subgraphs. Therefore, the local neural network may not learn global patterns. This is a unique problem graph data structures.
If the input to the neural network consists of images, no information is lost when the dataset is distributed, since each image is an independent data element. If the input a graph, some edges that span the partitions are essentially unaccounted for during training. If the convolution operator (Figure 2) targets vertex at the edge the subgraph, the neighbor data needed not available the local machine. A choice has to be made: either acknowledge the edge by trying fetch the missing data from the non-local machine, or ignore the edge. Both approaches introduce inefficiencies.
If the edge is acknowledged, there is a risk of overflowing the network with communication calls, since the machine that holds the neighboring vertex first has to be identified, and then that machine has to send out its data. The number of communication calls grows with the number of machines. However, the edge is ignored, the execution time of each machine decreases since the communication overhead is minimized, but information is lost: the convolution will be approximate.
3

---

Under review as a conference paper at ICLR 2021
Algorithm I: Breadth-firss random sampling of vertices
Input: Np: number of vertices in partition pt M: number of partitions; P: partitions: O: overlap
Output: P,: Partitions with overlap O
for in do
O-Na. p nts = xr
for op P p sample(P..pp. op, nts)
Function sample(Pa/pl, p. op, nts):
selection = neighhors(p. op)
if size of selection >= nts then
sn = random(sclection, nts); P.[p] P.[p]
10
Polp) = selection U Polpl
I1
hop neighhors(selectinn op) selection
if hop is empry then samplc(P..pl. hop, op, nts size of sclection);
3.1 SUBGRAPHI APPROXIMATION
We overcome the problem of information loss by approximating the subgraphs which are not locally available. The intuition behind this approach is that each machine will have a complete view of one partition, and an approximate view of the rest of the partitions.
After partitioning the graph into number of subgraphs, the following steps are taken for each subgraph g:: 1) A fixed number of vertices are randomly sampled from each of the other subgraphs, the vertex has a path to gi- 2) The subgraph gi is extended to include these vertices from other uub-graphs thereby creating approximate view of all the sub-graphs that
other machines.
While there are multiple approaches to sampling, in this work we use breadth first algorithm as shown in Algorithm T First, we calculate how many vertices
need to sample (nts) from the other partitions (line 2) based on an overlap threshold O. O can be determined by the user based on the additional memory overhead that the system is willing to accommodate. For example, when distributed across five machines, 10% overlap threshold means that each partition can hold 2.5% additional vertices from all the other four sub-graphs 24X2.5%) compared the vertex count in its current partition. To select vertices, our algorithm first finds all the one-hop neighbors in the other partition (line 6). If the selection exceeds the number of vertices we wish sample, we randomly select nts vertices from the selection and include them in the new partition (line 8).
If the number of one-hop neighbors is smaller than nís,, we consider vertices farther away. First, we add the current-hop neighbors to the new partition (line 10), and then find the next-hop neighbors (line 11). We then recursively sample next-hop neighbors (line 12) until O is met. We estimate the worst-case complexity of the algorithm to be O(N2), were N is the number of vertices in the graph T
3.2 TRAINING WITH SUBGRAPH APPROXIMATION
The training process with subgraph approximation
master-worker setting. The master acts as a parameter server, and is responsible for initiating the training by partitioning the graph, applying subgraph approximation, and distributing the partitions among the workers.
The workers are responsible for the training. Each worker has local copy W of the neural network, and trains its assigned subgraph. At the end of every epoch k. the worker sends its trained parameters W to the master. The master collects the parameters and averages them before distributing the result, W agg- back to the workers. After receiving the averaged parameters, each worker continues the training on its own subgraph for the next epoch. At the end of the training period, the aggregated parameters from each of the workers form global model.
For derivation, refer Appendix
4

---

Under review as a conference paper at ICLR 2021
Table 1: Dataset Statistics
% of vertices in
Datasel
#Vertices
#Edges
#Labels
#Features
Train/ Train/Val/Test
Reddit
231,443
11,606.919
602
70/20/10
Amazon2M
2,683,902
48,356,954
100
70/20/10
During each epoch the vertices at the frontier of each subgraph use the approximated neighbors to capture the neighborhood information. Recall that during training the vertices at the frontier in each subgraph only need capture information from their immediate neighbors or 2-hop neighbors at most). Our approximate subgraphs capture this information. In the next epoch this information from one subgraph must move deeper into other subgraphs which are not present on the local machine. This is where the parameter aggregation at the end of an epoch plays role in communicating knowledge across subgraphs. Thus intuitively we capture both the local knowledge at each subgraph boundary during an epoch, and then transmit that knowledge across subgraphs between epochs.
EVALUATION METHODOLOGY
We evaluate our approach on a cluster of identical machines, each equipped with an AMD Ryzen 1200 Quad-Core processor, 32 GB memory, and a NVIDIA GeForce GTX 1080 Ti. The cluster is configured as described in Section 3.2 For graph partitioning we use the METIS library (Karypis) Kumar 1997), choosing edge cut as the minimization objective. Each subgraph has approxi- mately equal number of vertices. After including sampling of edges from other sub-graphs using Algorithm aall other edges between the subgraphs are dropped.
4.1 INVESTIGATED GCNs
We implement distributed versions of the KW-GCN and GraphSAGE in PyTorc (Paszke et al. 2017 and apply them in an inductive setting. We give a brief overview of the GCNs and a specification of the applied hyperparameters. For in-depth description we refer the reader to the original papers.
KW-GCN builds on an approximation of spectral graph convolutions (Kipf Welling 2017).
The propagation rule is defined as H = - W HO = x For evaluation we use the Adam (Kingma & Ba 2014) optimizer, 128 hidden dimensions, learning rate of 0.02, and 2 layers.
GraphSAGE employs a spatial-based approach which uses sampling to aggregate feature information. It learns in three steps: 1) Sample fixed number of neighbors. 2) Derive the vertex embedding by aggregating its neighbors' feature information. 3) Use the embedding to predict the graph label. We the element-wise mean as propagation rule together with 2 layers, batch-size of 256, the Adam optimizer, and learning rates of 0.0001 (Reddit) and 0.0002 (Amazon2M).
4.2 DATASETS
We evaluate our approach by classifying vertices in the Reddit and Amazon2M datasets (Table D.
The Reddit dataset (Hamilton et al. 2017b) is a graph representation of Reddit posts made during one month, where each vertex in the graph is post. There an edge between two posts if the same user commented on them both. The vertex label is the community a post belongs to. The features consist of embedding of post information, created using GloVe CommonCrawi (Pennington et al. 2014). The first 20 days of posts are used for training, while the rest are used for testing and validation.
The Amazon2M dataset presented by Chiang al. 2019) represents purchases where each vertex is an item and an edge represents that the items were bought together. Our graph is based on the same raw data, but we extract 100-dimensional vertex features from the item descriptions using Word2 Vec (Mikolov et al., 2013) instead of bag-of of--oofwords. In the raw data, each item has many categories. We assign labels by counting the categories and selecting the fret-ffryyyntly occurring category the label. The vertices in the dataset split are randomly selected.
-A: normalized adjacency matrix, X: feature matrix, h trainable weight matrix for layer L.
5

---

Under review as a conference paper at ICLR 2021
1.00
1.00
0.40
0.40
0.80
Ners
0.75
0.72
Sing machins
Ooerheed 10%
0.70
0.70
500
1000
1.500
1000
3520
2000
Triniin tine
Figure 4: Training GraphSAGE with the Reddit dataset without subgraph upproximation.
Figure 5: Training GraphSAGE on 5 workers with the Reddit dataset, using subgraph approximation.
RESULTS
5.1 IMPACT CONVERGENCE
shows example of training GraphSAGE the Reddit dataset using both single- machine and a distributed approach but without using subgraph approximation. the latter approach, the graph is partitioned into mutually exclusive subgraphs. We let the model train until convergence.
Figure 5.4
When training the model using the full graph on a single machine, the model converges at an accuracy of 94.89%. However, when training in a distributed setting without subgraph approximation technique the accuracy converges at 93.09% and 89.88% for and 5 workers respectively. When the number of partitions increase. the model converges at an increasingly lower accuracy. This behaviour due to the reasons we described in Section i.c. that each machine only has a local view of the graph, and that dropping edges creates a loss information about neighbouring vertices in other subgraphs.
5.2 IMPACT OF SUBGRAPH APPROXIMATION
Figure shows an example of how subgraph approximation can increase both accuracy and training time of distributed GCN training. We five workers and let the model train until convergence using four overlap thresholds (O in Algorithm []: 0%, 10%, 25%, and 50%. These overlaps correspond to an overhead of 0%, 2%, 5%, and 10% the total number of vertices in each partition.
Without overhead, the model converges at substantially lower accuracy than the single-machine case. In contrast, an overhead of 2% (10% overlap) increases the convergence rate and allows the model to converge to single-maching accuracy. A further overhead increase helps the model to converge even faster but does not necessarily increase accuracy. We now provide more details from each dataset.
Subgraph Approximation on the Reddit Dataset
Table 2 summarizes results for training KW-GCN and GraphSAGE using the Reddit dataset three and five workers. When training GraphSAGE on three workers, the accuracy converges at about percentage units below the single-machine case without any overhead. However, when adding an overhead of 3.3% (10% overlap) in each worker, the model reaches single-machine accuracy.
We see similar behaviour when training on five workers: small overhead 2% (10% overlap) considerably improves the accuracy. However, an overhead slightly larger than 2% is needed to reach dingle-machine accuracy. We notice that as the number workers increase, the overhead necessary to reach single machine accuracy increases slightly but not substantially.
The speedup for each configuration reported in Table 2 Note that speedup is sub-linear with the number of machines. This is because the parameters must be aggregated at the end of cach epoch which is a serialization bottleneck. Our machines are connected with 1Gbps Ethernet links due to cost limitations, which acts scalability barriers. We believe that using e.g. Infiniband will improve the scalability, but even within the limited cost we were able to achieve about 2X speedup.
As observed in Figure 3] KW-GCN is less resilient to input approximations than GraphSAGE is. This reflected the distributed behaviour KW-GCN. As Table shows, KW-GCN is more sensitive partitioning: with overhead the accuracy converges about 0.27 (three workers) and 0.42 (five

---

Under review as a conference paper at ICLR 2021
Table Results for training GraphSAGE (GS) and KW-GCN (KW) using Reddit.
Three workers
Accuracy [Miero Fi]
Training
Speedup
Allocated GPU
Time [s]
Memory [GB]
KW
GS
KW
GS
kW
G8
KW
GS
Single machine
92,90
94.94
784
2056
1.86
2.79
0% overbead
63.13
93.12
376
1182
2.08
1.74
0.53-0.68
0.93-10
3,3% overhead
91.87
95.50
406
1035
1.93
1.99
0.58-0.72
1.26- 1.27
8.33% overhead
92.27
95.65
453
1144
1.73
1.80
0.65-0.78
1.50-153
16.67% overhead
92.71
95.61
528
1098
1.48
1.87
0.82-0.93
1.86-1.89
Five workers
Accuracy [Miero F1]
Training
Speedup
Allocated GPU
Time [s]
Memory [GB]
KW
GS
KW
GS
kw
G8
KW
GS
Single machine
92.90
94.94
784
2056
1.86
2.79
0% overbead
50.20
89.95
333
991
2.35
2.07
0.31-0.41
0.51-0.55
2% overhead
88.88
94.87
368
889
2.13
2.31
0.33-0.44
0.57-0.62
5% overbead
91.80
95.35
385
735
2.03
2,80
0.37-0.42
0.71-0.76
overhead
91.93
0.45-0.51
0.97-0,99
Note: All revulis averuged muliiple
Table 3: Training KW-GCN on Amazon2M until convergence on five workers.
Table 4: Training GraphSAGE on Amazon2M for a fixed time (2386 s) on 20 workers.
Overhead
Miero FT
Time
Alloc. GPU Memory
Overhead
Micro FT
Epochs
Alloc, GPU Memory
0%
78.40
1022s
1.83-2.1
0%
83.35
80
0.89
2%
79.10
1148s
2.06-2.52 GB
0.5%
86.60
63
0.90 GB
5%
79.50
1290s
2.39-2.52 GB
125%%
86.89
53
0.93 GB
2.97-3.43
2.50%
87.01
40
Note: All results are averuged over maltiple rinus.
Note: All results are averaged over maliple runs.
workers) units below the single-machin bascline, which is an unacceptable loss. However, adding small overhead substantially increases the model accuracy bringing it very close to the baseline.
Subgraph Approximation on the Amazon2M Dataset
To explore how subgraph approximation scales with larger datasets we also investigate the Amazon2M dataset, which has about 10 times more vertices than the Reddit dataset. This dataset is challenging to train on a single machine for both GCNs, for different reasons: for KW-GCN, the adjacency matrix is too large to fit in GPU memory. For GraphSAGE, the training time is very long.
For KW-GCN, distribution of Amazon2M is not just an optional exercise but it critical for training even start. All our graphs were able to fit within the system memory limitations once they are divided into at least three subgraphs. For instance, the Amazon2M dataset was unable to fit in any single GPU memory but when sub-divided into five subgraphs it was able fit across all the five GPU memories. Hence, at least it is now feasible to train Amazon2M on reasonably priced GPU. Table shows the result of training KW-GCN on five workers. While it's not possible to train on one machine, the distributed approach enables training of KW-GCN. Furthermore, subgraph approximation significantly increases the accuracy: a 2% overhead results in 1.5% higher accuracy.
We also train GraphSAGE on the Amazon2M dataset, distributed on 20 workers. Adding an overhead increases the per-epoch execution time. However, this increase in traverse time is worthwhile, since fewer epochs are needed to reach higher accuracy. We show this in Table here, each overhead configuration has been trained for 2386 seconds, which is the time it takes to train the non-overhead configuration for 80 epochs. The accuracy increases significantly with an added overhead, although the number of epochs decrease: a small overhead of 2.5% increases accuracy from 85.55% to 87.01 %.
5.3 DISCUSSION
In GCN and dataset combinations, we see substantial increase in accuracy when adding a small overhead. This behaviour is due to 1) the number of GCN layers, and 2) the graph density.
When it comes to property 1), for both KW-GCN and GraphSAGE we use two layers, which means that they aggregate information from neighbors two hops away. When adding single vertex from
All memory measurements retrieved with torch. cuda located
7

---

Under review as a conference paper at ICLR 2021
non-local partition, it's not only the one-hop neighbors that benefit, but also all two-hop neighbors. Hence, the importance of each added vertex is super-linearly beneficial. However, the importance is less pronounced as the overlap grows: at some point, each vertex has enough information of its neighbors for the neural network to be able to learn from that vertex.
Another reason for the benefit from overlapped sub-graphs is the vertex degree. Reddit and Ama- zon2M are datasets with a relatively high average vertex degree (100.03 and 36.02, respectively). Naturally, if the added vertex has many edges the local subgraph, the information from that single vertex will be beneficial to many vertices in the local subgraph. Hence, datasets with reasonable vertex degree are more likely to derive super-linear benefits from adding just few vertices.
5.4 CONVERGENCE RATE ANALYSIS
To compare the convergence rate of our distributed solution with ClusterGCN which allows large- graph training on single machine, we trained ClusterGCN implemented in PyG (Fey & Lenssen 2019) using the hyperparameter setting from the original paper. Our goal is not compare execution time, which depends on the implementation, but rather to study the convergence rate, which depends on the number of epochs needed to reach convergence and the per-epoch training time. We find experimentally that ClusterGCN and GraphSAGE distributed on machines with 2% overhead converges in about the same number of epochs. Hence, the per-epoch time decides convergence rate.
To compare per-epoch training time, we investigate the time complexity for the two algorithms. According the original paper, time complexity for ClusterGCN for an N node graph with F features is [[]||AO|| + F2)" and Or and are small constants, we simplify to AO| NF2) and O(N
for single machine GraphSAGE Assuming L
Given the above, the time complexity of distributed GraphSAGE is O (N-O))= ) where M is the number of machines and O is the overlap from subgraph approximation. Given that can be held low as we have shown previously (< 1.2 according to Section 5.2), our conclusion is that distributed GraphSAGE converges faster than ClusterGCN if they't 're implemented in the same framework.
RELATED WORK
The importance of distributing the training of neural networks has driven large body of work. The crucial aspect of efficiently sharing parameters across the distributed models has been rigorously investigated, for example in terms of compression (Yu al. 2018 Alistarh et al., 2017 Dryden et al.
2016 Wen et al. 2017 Lin et al.) (018) and parallel aggregation (Thakur et al. 22005 Goyal et al. 2017). Optimization of parameter sharing is relevant also in the setting of a distributed GCN, but is orthogonal to the problem we aim to mitigate (communication overhead caused by the input graph).
NeuGraph Ma al. 2019) and Cluster-GCN (Chiang al., 2019) are frameworks which enable parallel GNN training on a single machine. However, they do not consider a fully distributed setting. Furthermore, they assume that the full graph is readily available, which is not the case in distributed setting. Since they do not target accuracy loss inflicted by lost edges, their approaches are orthogonal.
Aligraph YYang) 2019) and Roc (Jia et al. 2020) are both frameworks which targets distributed GNN training. Aligraph communicates all neighbor information between the subgraphs, while Roc trains on isolated subgraphs. Subgraph approximation can be applied to further improve these frameworks by removing unnecessary communication (Aligraph) and increase accuracy (Roc).
7 CONCLUSION
While distributing the training of GCNs is an efficient approach to reduce execution time and memory footprint, it also causes accuracy problems since information is lost between the graph partitions. In this paper, we propose a technique for mitigating the lost information by introducing subgraph approximation. By letting the subgraphs overlap slightly, the system can reach state-of- the-art art accuracy while still keeping the memory footprint low and at the same time avoiding costly synchronization caused by acknowledging edges between subgraphs placed on different machines.
4I, #layers, |AO]|= #non-zeros in adjacency matrix, #sampled neighbors
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
J. Ahn, S. Hong, S. Yoo, O. Mutlu, and K. Choi. A scalable processing-in -em-morr accelerator for parallel graph processing. In 2015 ACM/IEEE 42nd Anmual International Symposium on Computer Architecture (ISCA), pp. 105-117, June 2015. doi:
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1709-1720. Curran Associates, Inc., 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14- 16, 2014, Conference Track Proceedings. 2014.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018. URL
https://spenreviii
net. /ent//oorrii wtw.rrummdddryttttt.mmmmmmm
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 257-266, New York, NY. USA, 2019. Association for Computing Machinery. ISBN 47014503 doi: 10.1145532225003333995 URLhttpp:://ao http://///o..../0.1111111..//1/0
3292500. 3330925
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Mare aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang. Quoe V. Le, and Andrew Y. Ng. Large scale distributed deep networks. In Pereira, C. J. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1223-1231, Curran Associates, Inc., 2012.
Nikoli Dryden, Sam Ade Jacobs, Tim Moon, and Brian Van Essen. Communication quantization for data-parallel training of deep neural networks. In Proceedings of the Workshop Machine Learning in High Performance Computing Environments, MLHPC 16, pp. 1-8, Piscataway, NJ, USA, 2016. IEEE Press. ISBN 978-1
doi: 10.1109/MHPC..216..
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp. 6530-6539, Curran Associates, Inc., 2017.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in I hour. CoRR, abs/ 726.02677, 2017. http htttt:://arxiii org.
02677
Tae Jun Ham, Lisa WU, Narayanan Sundaram, Nadathur Satish, and Margaret Martonosi. Graphi- cionado: A high-performance and energy-efficien accelerator for graph analyties. The 49th Annual IEEE/ACM International Symposium Microarchitecture, MICRO-49, pp. 56:1-56:13, Piscataway, NJ, USA, 2016. IEEE Press.
William I.. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40:52-74, 2017a.
William I.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 3 1st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1025-1035, USA, 2017b. Curran Associates Inc. ISBN 1-0---6960--666644
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. CoRR, 1iss15066.5663.

---

Under review as a conference paper at ICLR 2021
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems (NIPS), 2018.
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy, scalability, and performance of graph neural networks with roc. In Proceedings of Machine Learning and Systems 2020, pp. 187-198, 2020.
George Karypis and Vipin Kumar. Metis a software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing ordering of sparse matrices. Technical report, 01 1997.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24- 26, 2017, Conference Track Proceedings, 2017. URL BeLLhttan https:://ppeneeview http:/ewwwwe......eoeeeeeee id=SJU4ayYqq
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018. URL /tttts:://ppereeeeeeee
Lingxiao Ma. Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. Neugraph: Parallel deep neural network computation on large graphs. In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC '19, pp. 443-457, Berkeley, CA, USA, 2019, USENIX Association. ISBN 378-1-939133--00
Tomas Mikolov, Iya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representa- tions of words and phrases and their compositionality. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, NIPS' 13, pp. 3111-3119, 19, Red Hook, NY, USA, 2013. Curran Associates Inc.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1532- 1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v1/114-11622
Rajeev Thakur, Rolf Rabenseifner, and William Gropp. Optimization of collective communica- tion operations in mpich. Int. J. High Perform. Comput. Appl., 19(1):49 66, February 2005. ISSN 1094-3420. doi: 10.1177/1044422000551122
BtRLhttp:////
/xx doi wtt.oo...../..1/7/////.1../
1094342005051522
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnttt (eds.), Advances in Neural Information Processing Systems 30, pp. 1509-1519, Curran Associates, Inc., 2017.
Z. WU, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-21, 2020.
Hongxia Yang. Aligraph: A comprehensive graph neural network platform. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 11,, pp. 3165-3166, New York, NY, USA. 2019. Association for Computing Machinery. doi: 100.1145/3292500333444400
ISBN 978145036200
htts::: orq/10.1145.
3292500. 3340404
10

---

Under review as a conference paper at ICLR 2021
Mingchao Yu, Zhifeng Lin, Krishna Narra, Songze Li, Youjie Li, Nam Sung Kim, Alexander Schwing, Murali Annavaram, and Salman Avestimehr. Gradiveq: Vector quantization for bandwidth- efficient gradient aggregation in distributed emn training. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 5129-5139, USA, 8. Curran Associates Inc.

---

Under review as a conference paper at ICLR 2021
A APPENDIX: SUPPLEMENTARY MATERIAL TO SECTION 3.1
Here, we give the reader insights into the time complexity of Algorithm complexity to be ((V2), where N the number of vertices in the graph.
We estimate the
The estimation derived from the following observations:
1) The outer and nested loops of Algorithm I (line and 3) are both executed P times, where P is the number of partitions, for total number of p2 executions.
2) Execution time of function sample (line 5) is dominated by fuucction neighbors(p, op) (line 6) and the recursive call to sample (line 12).
3) The number of recursive calls to sample depends on the number of vertices to sample nts O-N₂ and N, = F. where O is the overlap. It also depends on sig__dgeShopp hoo which denotes the average number of edges between hop and hop x+1, where hop 0 is partition and hop is different partition op. This is because we sample breadth-first: if there are more than nís edges between p and op, no recursive call is needed. Otherwise, sample first selects the direct edges between p and op and then moves to sample more edges farther away (in terms of hops). The number recursive steps necessary to reach nts samples can be described as:
P-T
nts
avg mog_eddeshop hop
O.N, P-1
N (P P)
avg_ mogg_ddeshop..o hopprt hops+1
O. N
p2. avg mngg_egeshop..hppe
where O is the overlap.
4) The function neighbors finds the one-hop neighbors between partitions p and op, which means that it has traverse the vertices in p and determine which of its neighbors belong to op. Hence, its worst-case complexity is O(N,- avg_edgess.ong of direct edges between the vertices in and op, and Np the number of vertices p. How- ever, goggeddesspogg is bounded upwards by the average vertex degree AVD which gives that also complexity is bounded upwards by O(N, DV.
where avg_edgesp.op is the average number
Putting all the observations together, the complexity of the full algorithm can be estimated as:
NN
N2 AVD) (N, = -)
O(p2. ang gogg_edgeshop.ooo hopet1 hopp
O N AVD O(N2)
O P avggaeeee poog_eegeSoop.hhee hop211
assuming that O and P are constants, and that AVD D as well as properties of the input graph.
are fixed
Note however that the execution time is sensitive to the property ang_ togg__dgeshpp.. hops+ : if the graph very sparse many recursive calls has be made meet the sample number criteria, which increases execution time. For the graph and overlap combinations we evaluate, however, no recursive calls are necessary.
12

---

Under review as a conference paper at ICLR 2021
B APPENDIX: SUPPLEMENTARY MATERIAL TO SECTION 5.2
per-epoch comparison of the effect of training GraphSAGE on the Amazon2M dataset, distributed on 20 workers. Figure 6 shows the resulting accuracy for epochs 80. We consider an overhead of 0%, 0.5%, 1.25%, and 2.5% of the total vertices in each partition. We observe a clear and substantial increase in accuracy: small overhead of 2.5% increases accuracy from 85.55% 87.62% (at 80 epochs).
0.90
0.88
0.86
Micro F1
0.84
0.80
Overhead 0.00%
0.78
Overhead = 0.50%
Overhead 1.25%
0.76
Overhead 2.50%
10
60
80
Epoch
Figure 6: Accuracy per epoch when training GraphSAGE on twenty workers with the Amazon2M
dataset, using subgraph approximation.
13

---

Under review as a conference paper at ICLR 2021
C APPENDIX: SUPPLEMENTARY MATERIAL TO SECTION 5.3
This section shows an example of how the number of hidden layers has an impact on the super-linear property we discuss in Section 5.3.
Figure 8 shows an example where Reddit is trained on five machines using GraphSAGE with only layer (cf. Figure 7 which shows the same situation but for two layers). In comparison to GraphSAGE with two layers, 2% overhead (which is 10% overlap) gives much lower increase in accuracy. In addition, appears that partitioning affects the one-layer GraphSAGE less than two-layer GraphSAGit since the one-layer scenario does not really benefit from the upper-lnnerrty of including additional vertices.
0.95
0.55
0.90
0.80
Sig machine
Overbeed 0%
0.80
Snille necsns
Ovathcad - 0%
Overheed 2%
Overhead 2%
Overtead 5%
Overhead 5%
Overhead 10%
Overhead = 10%
0.70
500
1000
1500 Traiinn Ume
2000
2500
3000
0.70
20
40
100
120
140 160
Training time
Figure Accuracy training time when training two-layer GraphSAGE on five workers with the Reddit dataset.
Figure 8: Accuracy training time when training one-layer GraphSAGE on five workers with the Reddit dataset.
14


Reviews:
[{"review_id": "q5rvUkAVdN1", "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 studies how to do distributed training for GNNs. For GNNs, nodes are connected so that it is not trivial to do distributed training, because it needs message passing across machines, incurring communication costs. If no message passing across machines, the performance will be bad. To address this problem, this paper stores a subset of the neighbors from other machines to reduce the cost for message passing across machines. The experimental results show improvement to some extent. \n\nHowever, I have some concerns as follows:\n\n1. In the proposed method, each machine should keep a copy for the subset of neighbor nodes from other machines. Then, the frontier nodes for the subgraph on this machine can aggregate the information from these copied neighbor nodes. However, it is a recursive procedure. These copied nodes should also aggregate their neighbors. How to handle these nodes? Only do aggregation at the end of each epoch? If so, within each epoch, its information is outdated. \n\n2. In the experiment, the used GNNs only have two layers. It is known that GNNs need to recursively aggregate its neighbors. For deeper GNNs, the frontier nodes will aggregate larger-hop neighbors. It is not clear how this method work for deep GNNs.\n\n3. In table 2, for GS, why is the acc of distributed method better than that of a single machine? \n\n4. In this method, there is a critical parameter: overlap. The experiments show how this parameter affect the accuracy. However, a large overlap may include all the immediate neighbors on other machines. If it is the case, the experiments tell us nothing. Thus, it is critical to show the percent of immediate neighbors in the overlap\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "S4XDagbDQfE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a subgraph approximation method to reduce communication in distributed GCN training. The authors observe that up until a certain point it is possible to delete vertices in a graph without a large accuracy loss for GCN training.  Based on the observation, the authors propose the subgraph approximation idea. They claim that if the subgraph on each machine has additional information of 1 or 2 hop neighbors, the accuracy of GCN training can be maintained. \n\nThe results are surprising since many information is lost for the border nodes. I am curious how many border nodes are labeled. I suspect that if most of the border nodes are labeled and are used for computing the loss, the model cannot be trained very well.  \n\nI don't understand the reason for random sampling in algorithm 1. Since this step is done before the actual training, it is not a stochastic procedure. I suspect the performance will vary in different runs. The authors need to add some explanation and experimental evidence for this design. In my opinion, because different nodes carry different amounts of information, we should select the set of nodes that carry the most information, for example, a node should be added to a partition if it has the most number of connections with the nodes in that partition. I don't see how random selection can perform better than this. \n\nAlso, I notice that the authors only tested with GNN with 2 layers in the experiment. Many GNN models have more than 2 layers. I am curious whether the proposed method will still work for GNN with more layers. \n\nMy main concern about this paper is its lack of justification. For a heuristic method, I would like to see more experimental results. The authors only experiment with two models on two graphs. It is not convincing that the method is generally applicable to GCN training.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "EB0DGJiTryx", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the problem of training GNNs in a distributed environment (e.g., with multiple machines communicated through a network). In such a setting, the training of GNNs for node classification problems substantially differs from the training of other neural networks, because if the graph and node data are partitioned and distributed across machines, the data held by each machine may not be enough to compute a local gradient. \n\nThe proposed solution is simple: augment the data held by each machine in order that they are enough for computing the local gradient. Specifically, the augmented data are nodes that do not belong to the current partition but are within multi-hop neighborhoods of the nodes in this partition. If the augmented data do not all fit in memory (GPU memory in the authors' work), sample the neighborhoods.\n\nThis idea is a practical and effective solution. However, the authors' work leaves a lot to be desired. In what follows are questions and suggested work that may help enrich the contribution.\n\n- Section 2.2. It is not entirely clear what \"approximated graph\" means. Did the authors reduce the training set, cut the graph to a smaller one (but keep the training set), sample multi-hop neighbors for each node in the training set, or do something else? If the approximation means using a smaller training set (which is suggested by the caption of Figure 3), this is not the same as sampling neighbors but keeping the training set. In other words, how does the motivation suggested by Figure 3 support the proposed method?\n\n- Section 3.1. Why breadth-first and uniform sampling? How about nonuniform sampling (e.g., according to node degrees)? How about deterministic sampling (also according to node degrees but done in a deterministic order)?\n\n- Section 3.1. Evenly spreading the overlap across partitions appears too naive. Since the augmentation is done only once at the beginning and does not involve repeated communication, why not adding nodes as many as needed, regardless which partition they come from?\n\n- Section 3 overall. An important point the authors have neglected is load balancing. Since the proposed distributed training is synchronous, load imbalance may be a critical issue. Have the authors considered a more elegant augmentation that encourages load balance, in the sense that each partition may include a different number of additional nodes?\n\n- Section 5.2. The authors mention that the observed speedup (with respect to time) is restricted by ethernet connection, which offers a much smaller bandwidth than infiniband. However, network bandwidth is not the only factor that affects speedup (for example, load imbalance may play a role also). It is important to understand how much each factor contributes. The authors are encouraged to conduct a thorough investigation, convey findings, and design mitigations.\n\n- Figure 5. What does Figure 5 look like if the horizontal axis is epoch? Figure 6 in the appendix partly answers the question, but the \"single machine\" baseline is missing therein.\n\n- Section 5.2. The authors state \"KW-GCN is less resilient to input approximations than GraphSAGE is.\" Can the authors articulate the reason?\n\n- Section 5.3. What happens if the GNN has more than two layers? Is the proposed method still effective, facing a much larger neighborhood? How would prediction accuracy be affected? The authors are encouraged to conduct investigations.\n\n- Section 5.4. The local time complexity per machine is not the most important factor in distributed computing. Load imbalance, communication, and synchronization costs should all be factored in.\n\n- Additional question to consider for enriching contribution: When a vast amount of computing resources is available (e.g., 100 machines), do the authors recommend using them all, using as few as possible, or somewhere in between? What are the trade offs between overlap size, communication/synchronization cost, and monetary cost?", "extra_scores": {}, "extra_text": {}}, {"review_id": "10x2ANP0wqh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Graph Convolutional Networks (GCNs) have inspired state-of-the-art methods for learning representations on graphs. However, training GCNs for very large graphs remains an issue because of their memory, computation demands. Towards addressing this issue, the paper proposes a distributed GCN training scheme based on subgraph approximation, and demonstrates its empirical effectiveness on medium-to-large datasets.\n\n\n\n## Strengths\n1) (Motivation) The paper considers an important and fast-growing topic. Training GCNs for large graphs is important for real-world applications. But, GCNs are known to suffer from large memory footprints. \n2) (Motivation) While many previously proposed schemes train GCNs on a single machine, this paper considers a fully distributed setting. As opposed to single-machine GCNs, distributed GCNs do not need the entire graph information for training. \n3) (Presentation) The paper is easy to read, and seems well-organised.\n\n\n\n## Weaknesses\n1) (Significance) An important baseline to compare against is SGC [Simplifying Graph Convolutional Networks, In ICML'19]. SGC is a (non-neural) logistic-regression-based method, of the form $\\tilde{X}=A^kX$, that can easily scale to very large graphs. Moreover, since $\\tilde{X}$ is pre-computed in SGC, the vertices can be seen as i.i.d instances facilitating distributed training of SGC.  \n2) (Originality) The novelty of the paper is quite limited as it explores two well-known existing methods viz., GCN [Kipf and Welling, ICLR'17], and GraphSAGE [Hamilton et al., NeurIPS'17] in the distributed setting.  The main modification is the proposed subgraph approximation scheme which seems quite ad-hoc. A lack of theoretical understanding of the approximation scheme limits the contributions. \n3) (Quality) The paper can be significantly improved by positioning with and/or exploring many other (more recent) large-scale single-machine graph neural networks (GNNs). It is currently unclear why / whether the proposed subgraph approximation can / cannot be applied to such GNNs for distributed training. Recent publications include (but are not limited to)\ni) GraphSAINT: Graph Sampling Based Inductive Learning Method, In ICLR'20,\nii) L^2-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks, In CVPR'20,\niii) Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks, In NeurIPS'19.\n\n\n\n## Comments\n1) The authors are encouraged to position their work with / compare against the following contemporaneous distributed GNNs in the camera-ready / a future version.\n(a) Scaling Graph Neural Networks with Approximate PageRank, In KDD'20.\n(b) Reducing Communication in Graph Neural Network Training, In SC'20.\n2) The experiments on Reddit and Amazon datasets have demonstrated the effectiveness of the proposed method (which is commendable). Experiments on additional datasets would add great value to the paper. The authors could consider, for example, large-scale datasets considered in publications a) and b) listed above (Microsoft Academic Graph, and Protein graph respectively) for distributed GCN training. \n\n\n\nOverall, the motivations are clear and the biggest strengths of the paper. But the major weaknesses especially along the axes of significance, and originality outweigh the strengths.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new distributed training method for graph convolutional networks, using subgraph approximation. The reviewers raised multiple challenges, such as novelty, validity of experiments, and some technical issues. The authors did not respond to the reviewers' comments. The AC agreed with the reviewers that the paper, in the current form, is not ready for publication.
Decision: Reject