BDS-GCN: Efficient Full-Graph Training of Graph Convolutional Nets with Partition-Parallelism and Boundary Sampling
Authors: Cheng Wan
Youjie Li
Nam Sung Kim
Yingyan Lin
Venue:  (2021)
Keywords: Graph Neural Networks
Graph Convolutional Networks
Full-Graph Training
Large-Graph Training
Distributed Training
Partition Parallelism
Sampling

Abstract: Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art model for graph-based learning tasks. However, it is still challenging to train GCNs at scale, limiting their applications to real-world large graphs and hindering the exploration of deeper and more sophisticated GCN architectures. While it can be natural to leverage graph partition and distributed training for tackling this challenge, this direction has only been slightly touched on previously due to the unique challenge posed by the GCN structures, especially the excessive amount of boundary nodes in each partitioned subgraph, which can easily explode the required memory and communications for distributed training of GCNs. To this end, we propose BDS-GCN, a method that adopts unbiased boundary sampling strategy to enable efficient and scalable distributed GCN training while maintaining the full-graph accuracy. Empirical evaluations and ablation studies validate the effectiveness of the proposed BDS-GCN, e.g., boosting the throughput by up-to 500% and reducing the memory usage by up-to 58% for distributed GCN training, while achieving the same accuracy, as compared with the state-of-the-art methods. We believe our BDS-GCN would open up a new paradigm for enabling GCN training at scale. All code will be released publicly upon acceptance.

Under review as a conference paper at ICLR 2021
BDS-GCN: EFFICIENT FULL-GRAPH TRAINING OF GRAPH CONVOLUTIONAL NETS WITH PARTITION- PARALLELISM AND BOUNDARY SAMPLING
Anonymous authors
Paper under double-bling brindd review
ABSTRACT
Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art model for graph-based learning tasks. However, it is still challenging to train GCNs at scale, limiting their applications to real-world large graphs and hinder- ing the exploration of deeper and more sophisticated GCN architectures. While it can be natural to leverage graph partition and distributed training for tackling this challenge, this direction has only been slightly touched previously due the unique challenge posed by the GCN structures, especially the excessive amount of boundary nodes in each partitioned subgraph, which can easily explode the re- quired memory and communications for distributed training of GCNs. To this end, we propose BDS-GCN, method that adopts unbiased boundary sampling strat- egy to enable efficient and scalable distributed GCN training while maintaining the full- tull-graph accuracy. Empirical evaluations and ablation studies validate the effec- tiveness of the proposed BDS- DCDN, e.g., boosting the throughput by up-to 500% and reducing the memory usage by up-to 58% for distributed GCN training, while achieving the same accuracy, as compared with the state-of-the-e tfrt---rt methods. We believe our BDS-GCN would open up new paradigm for enabling GCN training at scale. All code will be released publicly upon acceptance.
INTRODUCTION
Graph convolutional networks (GCNs) (Kipf & Welling 2016) have gained increasing attention as they recently demonstrated the ofte-oo-thh-aae performance in number of graph-based learning tasks, including node classification (Kipf & Welling 2016), link prediction (Zhang & Chen 2018)) graph classification (Xu et al. 2018), and recommendation systems (Ying al. 2018).. The excellent performance of GCNs is attributed to their unrestricted and irregular neighborhood connectivity which provides them greater applicability to graph-based data than convolutional neural networks (CNNs) that adopt a fixed regular neighborhood structure. Specifically, given a node in a graph, a GCN first aggregates the features of its neighbor nodes, and then transforms the aggregated feature through (hierarchical) feed-forward propagation to update the given node feature. The two major operations, i.c., neighbor aggregate and update node features, enables GCNs to take advantage of the graph structure and outperform their dtruture-unawwen alternatives.
Despite their promising performance, training GCNs has been very challenging, limiting their ap- plication to large real-world graphs and hindering the exploration of deeper and more sophisticated GCN architectures. This is because as the graph size grows, the sheer number of node features and the large adjacency matrix can easily explode the required memory and communications. To tackle this challenge, several sampling-bon
methods have been developed for reducing the memory re- quirement cost of approximation errors. For example, GraphSAGE (Hamilton al. (001)) and others (Chen et al., 2017,Huam et al. (2188) reduce the full-batch of a large graph into a mini-batch via neighbor sampling: alternative methods (Chiang al. 2019 Zeng al. 2019) use sub-graph sampling to extract induced sub-graphs as training samples.
In parallel with sampling-basee methods, recently emerged and promising direction for handling large graph training is the distributed training of GCNs, which aims to train large full-graphs over multiple GPUs without degrading the accuracy. The key idea is to partition giant graph into small

---

Under review as a conference paper at ICLR 2021
subgraphs such that each could be fit into GPU, and train them in parallel with necessary commu- nication. Following this paradigm, pioneering efforts, including NeuGraph (Ma et al. 2019). ROC Jia et al. 2020), and CAGNET (Tripathy al. 2020), demonstrate the great potential of distributed GCN training. but with different trade-offs. Grphh and ROC store entire (sub)graphs in CPU for overcoming the hurdle of still severe requirement of GPU memory, which yet relies on heavy GPU- CPU communications. CAGNET splits the feature vector of nodes into small sub-vectors to reduce the granularity of computation for potential memory saving, which however requires repeated and redundant broadcast of all node features across all subgraphs. As result, these methods not only require either extra CPU resources or communication traffic, but also hurt training performance.
To enable efficient full- -ullggraphhhh training of GCNs without these aforementioned issues. this work sets out to understand the underlying cause of the memory and communication explosion distributed GCNs training by carefully analyzing the training paradigm - partition parallelism. We find that even with partition parallelism GCN training can still be ineffective not designed properly, which motivates us make the following contributions:
We identify and formalize two main challenges in partition parallel training of GCNs: prohibitive memory requirement and communication volume. We further identify the cause of these chal- lenges to be excessive number of boundary nodes within each partitioned graph and such cause is unique in GCNs architecture due to neighbor aggregation. These findings provide researchers better understanding in distributed GCN trainings and potentially inspires further ideas in this direction.
We propose BDS-GCN, a simple yet effective boundary sampling method for overcoming both challenges above, which enables more scalable and performant large-graph training of GCNs while maintaining full-graph accuracy. BDS-GCN randomly samples features of boundary nodes during each training epoch, aggressively shrinking the required memory and communica- tion volume without compromising the accuracy.
Experiments and ablation studies consistently validate the effectiveness of the proposed BDS- GCN in terms of training performance and achieved accuracy, e.g.bboottng the throughput by up-to 500% and reducing the memory usage by up-to 58% while achieving the same or even better accuracy, as compared with the wate-of-the-aae art methods when being applied to Reddit and aghn-products datasets.
BACKGROUND AND RELATED WORKS
Graph Convolutional Networks. A GCN takes graph-structured data input and learn a feature (embedding) vector representing each node in the graph. To learn the feature vector, GCN performs two major steps in each layer, i.e., neighbor aggregate and updale, which can be represented as:
a -(() (h(01) N(e)))
h - (a (...)-1)
(2)
where N(v)) denotes the neighbor set of node in the graph and h denotes the learned feature vector of node at the I-th layer. ((1) aggregation function that takes neighbor features generate aggregation result de for node v. Then (0()) gets the feature of node updated. A famous instance of GCN is GraphSAGE with mean aggregator (Hamilton et al. 2017), in which (0)) is mean function and (()) is a W CONCAT (a()) A. ")) where W the weight matrix and or is non-linear activation. This instance is the focus of our work, but our approach can also be extended easily to other popular aggregators and update functions.
Large Graph Training. Real-world graphs consist of millions of nodes and billions of edges (Hu ct al. 2020), which are beyond the capability of vanilla GCNs (Hamilton et al. 2017 Jia et al. 2020). especially due to the constraint of GPU memory capacity. To tackle this issue, several sampling-
based methods were proposed, such as neighbor sampling (Hamilton et al.) 2017 Chen et al. 2017) layer sampling (Chen et al.] 2018 Huang et al., 2018 Zou et al. 2019). and subgraph sampling (Chiang et al. 2019 Zeng et al. 2019: Wang et al. 2019). However, these methods suffer three major drawbacks:
2

---

training of GCNs with a simple yet Under review as a conference paper at ICLR 2021
Store Partitions in CPU Memory
Store Partiions in GPU
Store Partiions in GPU
Graph
Parittion
Slice Node
Swap detween CPU and GPU
Boundary Sampling
B
Broadcast and Compute
Siice-by-Slloe Synchronously
Communication
Compute Sub-Partitions in GPU
Point2Point Communication (d) BDS-GCN
(a) Vanilla Partition Paralletism
(b) ROC
(c) CAGNET
Figure I: Comparison among different approaches of distributed GCN training for large graphs.
Inaccurate feature estimation: although most sampling methods provide unbiased estimation of node features, the variance of these estimation hurts the model accuracy. As Chen al. (2017) shows, sampling-bast methods with a smaller variance is beneficial to improving the accuracy.
Neighbor explosion: [amilton et al. (2017) first uses node sampling that randomly selects sev- eral neighbors in the previous layer, but as the model getting deeper the size of selected nodes exponentially increases. Chen al. (2017) and [Huagg et al. (2018) further propose samplers for restricting the size of neighbor expansion, which yet suffers from heavy memory requirements.
Extra time cost for sampling batches: All sampling based methods require to take some extra time for generating nini-batches, which hurts the efficiency of model training.
Distributed Training for GCNs. To train GCNs for large graphs without limitations, distributed training rises promising solution leveraging cluster of GPUs to enable full-graph training. is tempting to directly take classical distributed training approaches (such as data and model parallelism) for GCNs. Unfortunately, GCNs training is diverged from the setting of those classical approaches where data samples are small yet the model is large (e.g, model parallelism) and data samples do not have dependency (e.g.. data parallelism), both of which violate the nature of GCN training. A GCN- -CN-oriented method should be: partition the full (giant) graph into small sub- graphs such that each could be fit into one GPU memory, and train them parallel, where communication across sub-graphs (GPUs) is necessary to exchange boundary node features to perform neighbor aggregation of GCNs, which called vanilla partition parallelism shown in Fig. (a).
Following this paradigm, several works were proposed recently. ROC (Jia et al. 2020) partitions large graphs but stores all partitions in CPU and swaps fraction of each partition to compute on GPU (see Fig- (b)). It relies swaps to overfit the GPU memory for large graphs, thus inevitably demanding heavy swap communications, which not only require extra CPU resources and traffic but also hurt the performance. Similar swap-based works NeuGraph (Ma et al.) 2019) and AliGraph (Zhu et al. 2019). CAGNET (Tripathy et al. 2020) also partitions graphs but further splits node feature vectors into small sub-vectors such that communication and compute smaller granularity for memory savings (see Fig. (c)). However, this strategy requires broadcast of each sub-vector for every node in fully sequential manner, which could incur both redundant communications and an excessive synchronization overhead.
reduced to
Distributed Graph Systems. Distributed graph systems were proposed for analyzing large graphs to solve general graph problems (Shun & Bleiloch 2013 Nguyen et al. [003 Gonzalez et al. 2012 Zhu al. 2016 Chen 2016|Cheneee et al. 2019). Lerer al. (2019) also proposes distributed learning system for graph embedding. However, none considers node features and cannot be used to for GCN training.
3 PARTITION-PARALIAA GCN TRAINING WITH BOUNDARY SAMPLING
Overview. To address the aforementioned challenges (i.e., (1) accuracy loss incurred by existing sampling-based methods and (2) heavy swaps and redundant communications imposed by existing distributed training methods), we propose a partition-paralle effective boundary sampling, dubbed BDS-GCN, shown in Fig. (d). Specifically, BDS-GCN partitions a given full-grap with minimized boundary node set and further samples them to shrink both the required memory storage and communication costs in each partition/subgraph, enabling
3

---

Under review as a conference paper at ICLR 2021
Graph
Fealore Grad
Partttinn
Exchange
GCN
Compute
Exchaige Node Feature
Compute Layer-2
Backward Update
Henar
Foature
Layan1
Pass
Model
8 Boundary
6
Weight Grad
Next Neration
Figure 2: Illustrating vanilla partition parallel GCN training, where large graphs are partitioned into smaller sub-graphs (see inner nodes) with each can be fit into one GPU memory. But exces- sive boundary nodes (in orange) are introduced in each sub-graph, by GCNs' neighbor aggregation, which not only drastically increases memory cost of each subgraph but also incurs heavy commu- nication overhead between subgraphs, rendering such partition parallelism ineffective.
efficient and scalable large-graph training of GCNs on memory-constrainn accelerators without necessitating neither extra host resources nor communication traffics. Notably. ADS-GCN's advan- tage in substantially reducing hardware costs for training large graphs does not compromise the accuracy, i.e., BDS-GCN maintains the full-graph accuracy.
We develop BDS-GCN by first analyzing and identifying the two major challenges (i.e., large mem- ory and communication requirements; see Fig. ( in existing partition-paralle training of GCNs, and then pinpoint the underlying cause to be the excessive number of boundary nodes inherited from GCNs' unique neighbor aggregate operator. To tackle this cause directly, we design an unbi- ased random sampling method that solves both above challenges.
3.1 CHALLENGES IN VANILLA PARTITION- PARALLEL TRAINING
To enable full- graph training. the original large graph can be partitioned into smaller subgraphs such that each subgraph can potentially be fit into one GPU memory, and then all subgraphs are trained in parallel, i.e., performing GCN compute locally each subgraph while also communicating dependent node features across subgraphs, which we call partition parallelism.
As illustrating in Fig. 2 each subgraph in partition parallelism contains subset of nodes in the original graph, which can be called inner node set (shown in the dash block) and is unique for each subgraph. In addition, each subgraph is also required to hold boundary node set (shown orange) which contains dependent nodes from other subgraphs. Such boundary node set is dictated by the nature of GCNs neighbor aggregate of node features that can span multiple neighbor sub- graphs. For instance, the node-5 requires the features of nodes-[3,4,6] residing on other subgraphs to perform Equ. 1 thus creating the boundary nodes associated to the subgraph hosting node-5. To compute each GCN layer, features of boundary nodes are communicated, i.e,, exchanged, across subgraphs (shown in red) before the features of inner nodes get updated (e.g., nodes-[2.. [2,5] shown in blue). These updated features are again exchanged across subgraphs compute the next GCN layer, so on and so forth, until the final layer. The backward pass processes inversely as the forward pass, except that it communicates the gradients of boundary nodes instead of their features. Then GCN model get updated by aggregating weight gradients (e.g, via allreduce) among all partitions. Note that common GCN models are relatively small compared the features in subgraphs, rendering their hardware cost negligible (Jia et al. 2020).
Although it seems such vanilla partition parallelism can be used to handle large graph training of GCNs, we find that it neither ineffective nor scalable due to the following challenges:
Challenge I: Even with partition, each subgraph can still require prohibitive memory budget to
hold both the inner and boundary sets, which can easily overflow GPU memory capacity.
Challenge 2: The partition parallelism can suffer from severe communication overhead, slowing
down the training and limiting its scalability for adopting more partitions/GPUS.
We further identify that both the above challenges share the same underlying cause - the overhead of extra boundary node within each partition, elaborated below:
4

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison between number boundary and inner nodes partitioned Reddit graph with METIS.
Partition Index
2
3
4
5
6
7
8
10
Inner Nodes
14k
15k
15k
15k
15k
15k
14k
15k
14k
15k
# Boundary Nodes
39k
15k
86k
78k
86k
62k
6k
46k
71k
23k
Ratio Boundary to Inner
2.64
1.00
5.45
4.95
5.49
4.11
0.42
3.04
4.81
1.52
Each boundary node requires both storage and communication for calculating every layer of GCNs and for both forward and backward pass (as illustrated in Fig. 2
The boundary nodes can have duplication across subgraph.
The boundary node set can be much larger than the inner node set in each subgraph.
As shown in Tab. D the number of boundary nodes in each subgraph can be 5.5x of the number of inner nodes for the real-world Reddit (Hamilton et al.) 2017) graph partitioned using the METIS algorithm (Karypis & Kumar 1998), leading to both memory and communication overhead. Ana- lytically, we formalize both cost caused by boundary nodes in partition parallelism as below:
Analysis of Memory Cost. For the /-th layer, suppose the input feature of dimension ( and the (4)
(4) numbers of inner nodes and boundary nodes in partition/subgraph P: are Rin and ! respectively.
Considering general cases where we save all node features and inner nodes" aggregated features for supporting the back propagation of both Equ. [ and Equ. 2 When using GraphSAGE layer with mean aggregator, the memory cost is as follows:
Mem (P = (3n + Tnd (9
As result, the number of boundary nodes increases the memory requirement linearly.
Analysis of Communication Cost. For the partition P.. the communication volume can be defined Vol(P:) Ever, (1)) where D(c) denotes the number of different partitions in which has neighbor node, excluding P; (Buluę et al., 2016). This value quantifies the total amount of features P; needs to send during each propagation. As the total number of received messages equals to the total number of sent messages, the total communication volume equals to the total boundary nodes:
Σ vol(P.) = Σ
add
(4)
(4)
3.2 THE PROPOSED BDS-GCN TECHNIQUE
3.2.1 BDS-GCN: GRAPH PARTITION
As boundary nodes are the cause for ineffective partition parallelism, the graph partition has to minimize all boundary node sets prevent subsequent memory and communication overheads, dubbed Goal-1. Furthermore, the graph partition must also achieve balanced computation time across all partitions, dubbed Goal-2, since the partition parallelism is synchronous paradigm that requires frequent synchronization at layer granularity (again due to neighbor aggregate nature of GCN), where unbalanced partition can result in stragglers blocking other partitions train.
Many existing graph partition methods aim to achieve the aforementioned Goal-2 yet ignoring Goal- In this work, we adopt METIS (Karypis & Kumar 1998) to implement BDS-GCN Considering both Goal-1 and Goal-2, we first approximate the compute complexity to determine the size of parti- tions (e.g., when Equ. is dominated by matrix multiplication, the complexity proportional the number of nodes, across all partitions. After that, we set the objective of METIS to minimize the total communication volumes, which is to minimize the size of boundary node sets, according to Equ 4
set partitions with equal size in this case), aiming to balance computations
3.2.2 BDS-GCN: BOUNDARY SAMPLING
Even with optimal graph partition, the boundary node issue still remains (see Tab. 1p, calling for innovative methods to trim down the boundary nodes for enabling efficient and scalable partition parallelism. Ideally, such method should achieve all following goals: 1) substantially shrinking
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Boundary sampling for partition-paralle training (per-partition view)
Input: graph partition G. boundary node set N, node features X, labels Y, sampling rate p.
initial model w=[0], learning rate y, number of partitions Output: trained model [T]
V t {node E g $ NN:/// create inner node set
H X:// initialize input features
for 4- 1:
N₁ f randomly select elements in AV with probability p:
... Broadcast N₂ and Receive [4, ... _mm]: // notify selection to all
[Vi...., Vn]] < [21 ...... Um n nV;; // record selection of others Go t node induced subgraph of 9 from VUNG
for +-11 do
Send [HT ,'. "
Vin to partition [1.... m] and Receive H!-")); N.
H + GCNNO concat coneat(H((1)) ",, ())
10
11
end
fg - Evey [(h? yo)); // calculate loss
12
Docal [1] +- 05.. // backward pass
13
Bw[lj
14
git] - AllReduce (Qocac()((()
15
vc((] w|l 1] 7 7/9
end
17 return [Z]
boundary set, 2) incurring only minimal overhead, and 3) maintaining full-graph accuracy of GCNs. As such, we propose an unbiased random sampling method called boundary sampling. (The phrase 'unbiased' refers to the mean aggregator and ignores activations, as in Chen et al. (2017) and Zeng eet al. (2019))) The key idea is to select a subset of boundary nodes independently from each partition, then to store and communicate merely those selected boundary nodes instead of the full set, and to update the selection randomly for every epoch.
Algorithm [ outlines our boundary sampling method for partition parallel training of GCNs. In each partition, we randomly keep boundary nodes with a probability of p. and drop the rest at the beginning of each epoch. Then these selected node indices are shared across all partitions such that each partition can "know" others' selections and can record its local node V. that is selected by the other i-th partition. During forward pass of every layer, each partition sends those features Hi, of previously recorded nodes to the corresponding i-th partition, respectively. and meanwhile receives features of own selected boundary nodes to perform GCN operations. (Here, if mean aggregator is used, replace sent/received feature vector /t with h/p for unbiased feature estimation.) During backward pass of every layer, each partition sends and receives feature gradients of the selected boundary nodes while generating weight gradients of the GCN model. Lastly, weight gradients are aggregated across all partitions via AllReduce to perform local weight updates.
The proposed boundary sampling reduces the number of boundary nodes by factor of 1. together p. with the same factor of reduction in memory and communication costs (according to both Equ 3a and 4). Meanwhile, boundary sampling introduces only negligible overhead due to random sampling on node indices, making it cenple-yet-effeettvy approach. Note that our boundary sampling can not only boost the efficiency and scalability of vanilla partition parallelism, but also be easily plugged into any partition parallel training methods (such as ROC (Jia et al. 2020) and CAGNET (Tripathy et al. 2020)) for furthering their training efficiency.
Lastly, we compare the proposed boundary sampling with existing sampling methods:
Node Sampling: GraphSAGE (Hamilton et al. 2017). VR-GCN (Chen et al., 2017). AS-GCN (Huang et al.] 2018) propose node sampling, which would sample the same nodes multiple times from the previous layers, which restricts the depth of GCNs and training efficiency. Furthermore, BDS-GCN does not sample neighbors in each subgragh, reducing estimation variance.

---

Under review as a conference paper at ICLR 2021
Layer Sampling: Boundary sampling is similar to layer sampling nodes in the same subgraph share the same sampled boundary nodes in the previous layer. Different from layer sampling such as FastGCN (Chen al. 2018), boundary sampling has much denser sampled layers, and thus potentially improves the training quality.
Subgraph Sampling: Boundary sampling can be viewed as one kind of subgraph sampling that drops boundary nodes from other "hographs/partttios ClusterGCN (Chiang et al., (019) and GraphSAINT (Zeng et al. 2019) propose subgraph sampling. yet their number of selected sam- ples are small (e.g., ClusterGCN and GraphSAINT sample only 1.3% and 5.3% of nodes, respec- tively), leading to a higher variance of their feature estimation.
DropEdge and Dropout: These techniques can be potentially integrated into BDS-GCN, However, applying them directly is not practical as they do not directly reduce boundary nodes. Most experiments in DropEdge drop at most 50% edges (Rong et al. 2019) and the resulting dropped boundary nodes are still too few to support large graph training.
4 EXPERIMENTS
Datasets and Setup
We evaluate the efficacy of our methods on two standard large-scale datasets, Reddit (Hamilton al. 2017) and ogbn-products (Hu al. 2020), and list used GCN models as following:
Reddit: An inductive classification task. The graph consists of 233K nodes and 114M edges with feature size of 602. We use 4-layer model with 256 hidden units and set learning rate 0.01 for Adam optimizer with 1500 epochs.
ogbn-products: A transductive classification task. The graph consists of 2.4M nodes and 62M edges with a feature size of 100. We use a 3-layer model with 128 hidden units and set learning rate as 0.001 for Adam optimizer with 500 epochs.
Yelp: An inductive mubti-label classification task. The graph consists of 716K nodes and 7.0M edges with a feature size of 300. We use a 4-layer model (2 GraphSAGE layers and 2 linear layers) with 512 hidden units and set learning rate 0.001 for Adam optimizer with 3000 epochs.
To ensure the reproducibility and robustness of BDS-GCN, we do not tune but fix hyperparameters for boundary node sampling throughout all experiments.
We implement BDS-GCN PyTorch (Paszke et al. 2019) and DGL (Wang et al. 2019). All experiments are conducted on single machine with 10 RTX-20800T (11GB).
Performance Benefit of BDS-GCN
Throughput (epochsis)
1.75
BDS-GCN (p-
We evaluate the training performance of BDS- GCN and compare it with the state-of-the-arr works, ROC (Jia et al.) 2020) and CAGNET
1.50
CAGNET 1c=1]
BDS-GCN (p 0.1)
CAGNET 2c
BDS-GCN (0.0.01)
1.25
1.00
Tripathy et al., 2020). for distributed training
of GCNs full large graphs. The result is
0.50
shown in Fig. 3 where each partition uses a sin- gle GPU for all methods except that CAGNET
(c=2) requires doubled GPUs From Fig. 3 observe that BDS-GCN outperforms other methods consistently across different number of partitions and different boundary sampling
0.00
Number of partitions
Throughput comparison on Reddit data. Each partition uses one GPU, except rate p. When p = 0.01, BDS- GCN offers CAGNET(c=2) uses doubled GPUs.
Figure 3:
promising throughput improvement of up-to 500% compared with ROC and 118% compared with Cc=N Even when p = 1, BDS-GCN still improves the throughput by up-to 190% com- pared with ROC and 49% compared with CAGNET(c=I). The advantage of BDS-GCN can be attributed to not only the reduced communication overhead with boundary sampling, but also no swap between CPU and GPU (as in ROC) nor redundant broadcast and synchronization overhead (as in CAGNET). Meanwhile, boost the performance for all methods, because the issue of boundary nodes can become more severe and incur more communication overhead.
also find that increasing the number of partitions do not always
7

---

Under review as a conference paper at ICLR 2021
Reddit
obgn-products
Reddit
ogbn-products
2.00
computation
2.00
Memory reduction (%)
p=
Memory reduction (%)
30
Nordalized egach
1.25
1.75
1.50
resuce
wikk
communicaiin
1.75
1.50
1.25
0.1
0.01
25
20
1.00
Norma permalzzd
1.00
15
0.75
0.75
20
10
0.50
0.50
0.25
0.25
10
0.00
2
4
0.00
10
2 Number partitions
8
10 Number of partitions
Number of partitions
Number partitions
Figure 4: Training time breakdown of BDS- GCN with different boundary sampling rates. Time are normalized against baselines without sampling each number of partitions.
Figure 5: Application-level memory usage re- duction achieved by BDS-GCN. Reduction are against baselines without sampling in each num- ber of partitions.
Detailed Performance Benefits of BDS-GCN
To further understand the performance of BDS-GCN, we breakdown the training time into four major components (local computation, communication for boundary nodes, wait, and allreduce on model gradient) and present them in Fig. 4 We observe that local computation time is relatively small but communication (and wait) dominate the total training time, i.e,, up-to 52% and 48% of the epoch time are paid for communication in baselines (p=1) on Reddit and obgn-products, respec- tively. With boundary sampling (p < 1), such heavy overhead is reduced substantially. Especially, the y=0.01 almost removes entire communication time for 4 10 partitions on Reddit and obgn- products, thus significantly cutting the total training time of GCNs. Note that this experiment is conducted in single machines where all traffics enjoy high high-bandwidth PCIe, but when scaling up further with multiple machines connected via lower bandwidth Ethernet, the distributed GCNs training could suffer from more severe communication bottleneck and thus making the proposed boundary sampling more desirable.
Besides, we also examine benefit of BDS-GCN memory saving. We measure the application- level memory usage of BDS-GCN under the same experiment setting, and summarize the achieved
memory usage reduction in Fig. 5 where EDS-GCN(p=L) serves as the baseline. From Fig. 5 observe that boundary sampling consistently reduce memory usage across different number of partition on two datasets. For the denser Reddit, BDS-G ADS-GCN(p=0.01) saves 58% memory for GPUs. For the sparser products, BDS (DS--GN(p=0001) also still saves 27% memory for 10 GPUs.
Full-Graph Accuracy of BDS-GCN
Besides improving system performance, BDS-GCN also maintains the accuracy of full-graph train- ing. To validate this, we have conducted extensive experiments to evaluate the test accuracy under the settings of various sampling rates and different numbers of partitions in distributed GCN train- ing, and compare the results with the state-of-the-art sampling-basse
methods (using GraphS AGE
architecture) in Tab. 2 Hu et al. 2020 with Code 2020. Chiang et al. 2019 Chen et al. 2017
Zeng et al. 2019) Hamilton et al. [201]] Cong et al. 2020: Zou et al. 2019 Chen et al.) 2020).
From Tab. 2 we observe that full-grap graph training (BDS-GCh with p=l) always achieves a higher
accuracy than exisiting sampling-bie saasingg-baedd methods, regardless of different datasets or number of par-
titions, which is consistent with results of ROC (Jia et al. 2020).
More importantly, BDS-GCN always maintains or even increases the full-graph accuracy, regard- less of the sampling rates (e.g., 1=0.1/).01), the number of partitions, or different datasets. For instance, on Reddit, p=0.1 achieves test accuracy of 97. 10%, 97. 12%, 97.07% under 2, 4, and 8 partitions, respectively, which are consistently equal or better than the 97.07% of full-graph unsam- pled training, thus validating the effectiveness and robustness of boundary node sampling.
However, we also observe that the special case of BDS-GCN (p=0) always suffers from the worst test accuracy/score on the three datasets, compared with other cases (p=1/0. 1/0.01. We understand that the accuracy/score drop is due to the full isolation of each partition after completely removing all boundary nodes, leading to no boundary node features during "neighbor aggregation" throughout the end-to-end training. Therefore, to retain a full-graph prediction accuracy, a relatively high sampling rate like 1/0.1/ is preferred when using BDS-GCN.
8

---

Under review as a conference paper at ICLR 2021
Table 2: Comparison of test accuracy (%) with the state-of-the-at methods on Reddit and ogbn- products, and comparison of test set F1-micro score (%) on Yelp. BDS-GCH with various (bound- ary sampling rate) and under different numbers of partitions are shown. Symbol denotes the equivalence of full-graph training across different number of partitions.
Method
Reddit
Yelp
Sampling-baselt methods
FastGCN
93.7
26.5
GraphSAGE
95.4
78.70
63.4
AS-GCN
96.3
LADIES
94.3
60.2
VR-GCN
96.3
64.0
ClusterGCN
96.6
78.97
60.9
GraphSAINT
96.6
79.08
64.7
BDS-GCO
# Partitions
2
8
5
8
10
6
10
BDS-GCN (1.0)
97.07
79.29
64.91
BDS-GCN (0.1)
97.10
97.12
97.07
79,45
79.44
79.41
65.29
65.38
65.47
BDS-GCN (0.01)
97.03
96.94
96.89
79.53
79.44
79.24
65.29
65.40
65.44
BDS-GCN (0.0)
96.94
96.83
96.78
79.27
79.18
79.19
64.87
64.84
64.85
2 partitions
4 partitions
8 partitions
97.0
97.0
Validation Accuracy
96.5
Validation Accuracy
96.5
Validation Accuracy
96.5
96.0
96.0
96.0
95.5
p=1
95.5
95.5
p=1
p
p 0
0=0.01
0=0.01
0=0.1
94.5
0
94.5
p
94.5
p-0
94.0
94.0
94.0
0
500
1000
1500
500
1000
1500
500
1000
1500
Epoch
Epoch
Epoch
Figure 6: Convergence comparison between unsampled full-graph distributed training (i.e., BDSS-
GCN with p=1) and boundary-node sampled distributed training (i.e., BDS-GCN with p < 1) over different numbers of partitions on Reddit.
To the best of our knowledge, BDS-GCN achieves the best accuracy of training GraphSAGf-llaye based GCNs on both Reddit and ogbn-pun gebn-prrduct dataset compared with all existing works.
Convergence Speedup of BDS-GCN
To further understand the affect of BDS- DDDS-GNN on convergence of distributed GCNs training, we also evaluate the validation accuracy under the same settings of Tab. 2 Fig. c compares convergence speed of those settings on Reddit. From Fig. 6 we observe that the boundary node sampling method demonstrates desirable convergence speed at a high sampling rate. Specifically, p=0.1 achieves the same (or even slightly better) convergence speed as the full-graph training, regardless of differ- ent numbers of partitions. We also notice that (1) p=0 suffers from the slowest convergence (i.e., 0.1 ~ 0.4% drop in validation accuracy from p=l) across different number of partitions, and (2) the convergence gap between p=0 and p=1/0.1 worsens as partitions involved.
CONCLUSION
In this paper, partition parallel training of GCNs on large full-graph is studied, and its major chal- lenges and underlying cause are identified. With careful analysis of the partition parallelism, a boundary-sampie based method, BDS-GCNs. is proposed and its effectiveness is validated by empirical evaluations. These findings and the proposed method can provide researchers better un- derstanding in distributed GCN trainings and potentially inspires further ideas in this direction.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Aydin Bulug, Henning Meyerhenke, llya Safro, Peter Sanders, and Christian Schulz. Recent ad- vances in graph partitioning. In Algorithm Engineering, pp. 117-158. Springer, 2016.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv: 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv: 2018.
Ming Chen, Zhewei Wei, Bolin Ding. Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scal- able graph neural networks via bidirectional propagation. Advances in Neural Information Pro- cessing Systems, 33, 2020.
Rong Chen, Jiaxin Shi, Yanzhe Chen, Binyu Zang, Haibing Guan, and Haibo Chen. Powerlyra: Dif- ferentiated graph computation and partitioning on skewed graphs. ACM Transactions Parallel Computing (TOPC), 5-3): 2019.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1393- 1403, 2020.
Joseph Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. Powergraph: Distributed graph-parallel computation natural graphs In Presented part of the 10th {USENIX) Symposium on Operating Systems Design and Implementation ({OSDI) 12), pp. 17- 30, 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00663 2020.
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.
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy, scala- bility, and performance graph neural networks with roc. Proceedings of Machine Learning and Systems (MLSys), pp. 187-198, 2020.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal scientific Computing, 20(1):359-392, 1998.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 1rXiv:1609.0222 1609.02907, 2016.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. Pytorch- Pytorch-biggraph: A large-scale graph embedding system. arXiv preprint arXiv:1903. 2019.
Lingxiao Ma. Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. Neu- graph: parallel deep neural network computation on large graphs. In 2019 (USENIX) Annual Technical Conference (USENIX) 19), pp. 458. 2019.
10

---

Under review as a conference paper at ICLR 2021
Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure for graph an- alytics. Proceedings of the Twenty-Fooid Fourth ACM Symposium on Operating Systems Principles, pp. 456-471, 2013.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances neural information processing systems, pp. 8026 8026-8037,001 2019.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
Julian Shun and Guy E Blelloch. Ligra: lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 146,146, 2013.
Alok Tripathy, Katherine Yelick, and Aydin Buluc. Reducing communication in graph neural net- work training. arXiv preprint WxXi:2005.033000 2020.
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song. Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centrie, highly-performant package for graph neural networks. arXiv preprint ar arviv:1909.00331
2019.
Papers with Code. Node Classification on Reddit, sep 2020. wtt.ttps://ppperrtttto... com/ sota/node wwwsssliaassiiioooooooooooo on reddit
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1810.0081000026 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint MKXVv1997.04991 2019.
Muhan Zhang and Yixin Chen. Link prediction based on 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. arXiv preprint arXiv: 10XX::9902.08700 2019.
Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. Gemini: computation distributed graph processing system. In /2th {USENIX) Symposium on Operating Systems Design and Implementation ( ((ODD)) 16), pp. 301-316, 2016.
Difan Zou, Ziniu Hu, Yewen Wang. Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 11249- 1259, 2019.
11


Reviews:
[{"review_id": "cmKI2iJ-Itv", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the efficiency issue raised by GNN training on large graphs. The proposed solution falls in the category of data parallelism, which aims to partition graph into smaller parts while reduce the communication cost caused by extensive number of boundary nodes. The proposed idea is interesting and practical, and the experimental results have demonstrated the superiority of the proposed approach.\n\nStrengths:\n1.\tThis paper successfully identifies the issues in the data parallelism-based GNN training algorithms – each graph partition share too many nodes with other partitions, called boundary nodes, which significantly affect memory and communication cost.\n2.\tThe proposed solution is simple yet neat, which is to sample the boundary nodes to reduce memory and communication cost.\n3.\tThe experiments are convincing, boosting the throughput (meaning number of epochs per sec) by up-to 500% and reducing the memory usage by up-to 58%, while achieving the same or even better accuracy.\n\nWeaknesses:\n1.\tThe graph partition idea is interesting, but more details on how to apply METIS is expected.\n2.\tThe experiments can be further enriched.  \n\n\nDetailed comments:\n1.\tIn this paper, it has mentioned many related studies. But in the experiment section, only a small subset of the mentioned methods are treated as baselines. Also, for the data partition-based baselines, only throughput is compared. How about the accuracy comparison? Which method needs more epochs to converge, which will affect the run-time in addition to the throughput? For the sampling-based methods, more methods are expected to be compared to the proposed approach. In addition to accuracy, run-time comparison is also expected.\n\n2.\tFor the sampling-based approach, one more baseline is expected: \n\nZou et al., Layer-Dependent Importance Sampling for TrainingDeep and Large Graph Convolutional Networks, NeurIPS 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y8tvm06WUmB", "reviewer": "AnonReviewer3", "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": "-------------\nSummary\n-------------\nThis paper presents a system design method to train GNNs on large graphs in a distributed manner. Due to the irregular edge connectivity and the limited GPU memory, intelligent graph partitioning is necessary to support full-batch computation. The authors identify the challenges in computation and communication due to inter-partition connections. Then with the objective of minimizing the edge-cut and improving load balance, the authors use the existing METIS partitioning algorithm to obtain node assignments. To further reduce the amount of communication across GPUs, the author further apply random sampling on the boundary (i.e., inter-partition) nodes. The sampling rate is considered as a hyperparameter to control the tradeoff between accuracy and efficiency. Experiments on two large benchmark graphs show that the proposed method achieves significantly higher hardware efficiency without loss of accuracy, compared with various baselines. \n\n------\nPros\n------\n+ Clearly defined the motivation and techniques. The overall paper is easy to follow.\n+ Strong experimental results (see also cons below for experiments)\n+ Distributed GPU training is an important topic\n\n-------\nCons\n-------\n- Limited novelty: the main algorithmic steps, partitioning and sampling, seems straight-forward. Specifically, the partitioning is based on the well-known METIS algorithm (However, METIS may not be scalable by itself). The \"boundary sampling\" simply performs IID sampling on the inter-partitioning nodes. This is a simple extension to the random layer sampler of the GraphSAGE minibatch method. \n- Motivation for full-graph training: Limited GPU memory is not the only reason for minibatch GNN training. Compared with full-graph training, it is also likely that minibatch training can improve the generalization of the model and thus achieves higher accuracy (as can be verified by the GraphSAGE vs. GraphSAINT rows in Table 2). Therefore, how to justify that full-graph training is important?\n- Insufficient experiments: The authors only evaluate the proposed method on two graphs, Reddit and ogbn-product. More importantly, it is not justified why we even need distributed training for Reddit in the first place. The training graph of Reddit can fit in the memory of a single GPU. What is the speedup obtained compared with single GPU training of Reddit? In addition, it seems that the accuracy is not significantly affected with very small p (Table 2). This implies that maybe we don't need boundary sampling at all, and can drop the boundary nodes entirely. \n- Unclear experiment setup: the GNN architecture details and the hyperparameter tuning procedures are completely missing. This makes the Table 2 results less convincing. \n- Where does the accuracy gain come from? Due to the lack of GNN architecture details, it is hard to judge where the accuracy gain comes from in Table 2. Supposedly, the \"GraphSAGE\" row corresponds to the case of full-batch training of the GraphSAGE architecture. According to the claim of the paper that dropping neighbors incurs information loss, the BDS-GCN accuracy should achieve at most the accuracy of GraphSAGE. Why the accuracies are higher?\n\n-----------------------------------\nRecommendation: Reject\n-----------------------------------\nIn summary, I think this paper lacks motivation and novelty. The experiments are not thorough enough. \n\n\n--------------\nQuestions\n--------------\n\n1. There is a claim in page 3 that all the sampling based methods have \"extra time cost for sampling batches\". How significant is such overhead? It seems that the sampling of GraphSAGE and GraphSAINT are pretty cheap -- they are just based on random neighbor selection and random walks. For Cluster-GCN, it seems that the overhead is the same as the proposed BDS-GCN, since both use METIS. \n\n2. Claim on unbiased sampling: Such claim should be more carefully phrased. Under what condition is the sampling unbiased? Only for GraphSAGE-mean? Ignoring the activations?\n\n3. In Figure 4, it seems that increasing the number of GPUs does not give any benefit in terms of training time. What about the time for a single GPU training without any partitioning?\n\n4. In Figure 5, the reduction in memory seems inconsistent with the measurement in Table 1. I would expect that reducing p from 1 to 0 would reduce the memory by multiple folds (since the number of boundary nodes is an order of magnitude larger than the number of inner nodes). However, in Figure 5, the memory is reduced only twice. Why is it the case?\n\n5. What is the GNN architecture and what is the hyperparameter tuning procedure for Table 2?\n\n6. Where does the accuracy gain come from compared with GraphSAGE row in Table 2 (see above \"Cons\" paragraph)?\n\n7. What is the accuracy if we completely drop the boundary nodes (i.e., setting p=0)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "LcRu734gLE", "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 developed a simple method for the distributed training of GCNs. In particular,  the excessive amount of boundary nodes in each partitioned subgraph, which can easily explode the required memory and communications for distributed training of GCNs. To address this problem, this paper proposed BDS-GCN, a method that adopts unbiased boundary sampling strategy to enable efficient and scalable distributed GCN training while maintaining the full-graph accuracy. The experimental results show good performance on large graphs. \n\n1. The writing is good and the idea is clearly presented.\n\n2. The idea is straightforward. It just communicates a subset of neighboring nodes to reduce the communication cost. However, this simple sampling method may incur large variance, slowing down the convergence speed and degenerate the prediction performance. \n\n3. In table 1, why is the number of boundary nodes larger than that of inner nodes?\n\n4. What is the difference between this method and DropEdge (https://arxiv.org/abs/1907.10903)? It seems that this method is identical to DropEdge. In particular, this method drops the edges across different machines. Thus, it is critical to discuss the difference between these two methods, and conduct experiments to compare these two methods.  Otherwise, it is diffcult to see the novelty of this method. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BNqeJKHx0Jk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "How to perform GCN on large-scale graphs efficiently is crucial in graph learning. Towards this goal, this paper proposes distributed GCN training, BDS-GCN. In particular, it first conducts graph partition and then allocate different partitions into different GPUs.  For each partition,  BDS-GCN samples a portion of boundary nodes (that are shared across partitions) and broacasts the features of the sampled boundary nodes over all partitions. After the message exchanging, BDS-GCN computes one-layer forward pass for each partition  in parallel. The backward pass is done similarly.  \n\nIn contrast to previous sampling-based methods, this paper can potentially avoid information loss by only sampling the boudery nodes while awalys keeping the inner nodes and their connections. \n\nIn contrast to typical distributed graph frameworks, this paper stores each partition locally in each gpu, and the communitation time can be reduced by boundery sampling.\n\nOverall, this paper is good written, the idea is valuable, and the exerimental results generally support the claims the authors have proposed.  Below are some concerns for the current version:\n\n1. It seems in Table 2 that BS-GCN can still obtain promising results when p is small. The reviewer wonders what will happen if p=0, when no boundery node is sampled. This is a crucial baseline that should be compared, as it can tell how important the message exchanging between partitions is, and thus what the boundery sampling stands for. \n\n2. The authors claim that DropEdge is not practical in distributed graph learning, which seems problematic. The communication cost indeed depends on the number of edges between two different partitions. In this sense, it will be interesting if we conduct boundery edge sampling like DropEdge to save communication time. Different from boundery node sampling, boundery edge sampling will keep all nodes (including the boundery nodes) and all connections (including the ones between inner nodes and boundery nodes) within each partition to preserve the information as much as possible, and only those edges connecting different partitions are randomly dropped. It is expected to explore this kind of baseline, and compare it with boundery node samling method. \n\nOther minor issues:\n\n3.   Are the weights stored globally? In a parameter server?\n\n4. What do U1, Um mean in Line 5 in Algorithm 1? Algorithm 1 is only under the per-partition view, and including a global view will better help readers to understand the whole framework. \n\n5.  Some previous results on Reddit by FastGCN, AS-GCN, etc are missing in Table 2.\n\n6. In figure 3, it seems increasing the number of partitions does not necessarily reduce the time cost, why? And how does the accuracy change if we use different number of partitions?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is concerned with improving the scalability of GCNs which is an important problem and relevant to the ICLR community. For this purpose, the authors propose a new distributed training method for GCNs which uses a boundary sampling strategy to reduce the number of boundary nodes. The paper is written well and, overall, good to follow. Reviewers highlight the promising improvements in throughput and memory footprint as well as and the possibility to avoid potential loss of information compared to other methods.

However, currently there exist still concerns around the manuscript. Reviewers raised concerns with regard to the novelty of the method (straightforward combination of existing techniques) as well as the experimental evaluation (overhead of METIS, full-batch accuracy, edge boundary vs node boundary, etc.) The revised version addresses some concerns (comparison to DropEdge, p=0, etc.) and clearly improves the paper. However, given the aforementioned issues and the absence of strong support from reviewers, I agree to that the current version would require an additional revision to iron out these points. The presented results are indeed promising and I'd encourage the authors to revise and resubmit their work considering the reviewers' feedback.
Decision: Reject