GraphSAINT: Graph Sampling Based Inductive Learning Method
Authors: Hanqing Zeng
Hongkuan Zhou
Ajitesh Srivastava
Rajgopal Kannan
Viktor Prasanna
Venue:  (2020)
Keywords: Graph Convolutional Networks
Graph sampling
Network embedding

Abstract: Graph Convolutional Networks (GCNs) are powerful models for learning representations of attributed graphs. To scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. We propose GraphSAINT, a graph sampling based inductive learning method that improves training efficiency and accuracy in a fundamentally different way. By changing perspective, GraphSAINT constructs minibatches by sampling the training graph, rather than the nodes or edges across GCN layers. Each iteration, a complete GCN is built from the properly sampled subgraph. Thus, we ensure fixed number of well-connected nodes in all layers. We further propose normalization technique to eliminate bias, and sampling algorithms for variance reduction. Importantly, we can decouple the sampling from the forward and backward propagation, and extend GraphSAINT with many architecture variants (e.g., graph attention, jumping connection).  GraphSAINT demonstrates superior performance in both accuracy and training time on five large graphs, and achieves new state-of-the-art F1 scores for PPI (0.995) and Reddit (0.970). 

Published as a conference paper at ICLR 2020
GRAPHSAINT: GRAPH SAMPLING BASED INDUCTIVE LEARNING METHOD
Hanqing Zeng"
Hongkuan Zhou"
University of Southern Californa zenghêusc. edu
University of Southern California hongkuaz @usc. edu
Ajitesh Srívastava University of Southern California ajiteshs@usee crscchsuuscc.. edu
Rajgopal Kannan
US Army Research Lab ra jgopal. kannan ei civêmail .mil
Viktor Prasanna
University of Southern California prasannauusea edu
ABSTRACT
Graph Convolutional Networks (GCNs) are powerful models for learning repre- sentations of attributed graphs. To scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. We propose GraphSAINT, a graph sampling based inductive learning method that improves training efficiency and accuracy in a fundamentally different way. By changing perspective, GraphSAINT constructs minibatches by sampling the training graph, rather than the nodes edges across GCN layers. Each iteration, a complete GCN is built from the properly sampled subgraph. Thus, we ensure fixed number of well-connected nodes in all layers. We further propose normalization technique to eliminate bias, and sampling algorithms for variance reduction. Importantly, we can decouple the sampling from the for- ward and backward propagation, and extend GraphSAINT with many architecture variants (e.g., graph attention, jumping connection). GraphSAINT demonstrates superior performance in both accuracy and training time on five large graphs, and achieves new state-of-the-art scores for PPI (0.995) and Reddit (0.970).
INTRODUCTION
Recently, representation learning graphs has attracted much attention, since it greatly facilitates
tasks such as classification and clustering (Wu et al. [2099] Cai et al., (017). Current works on Graph
Convolutional Networks (GCNs) (Hamilton al. 2017]] Chen al. 2018b Gao al. 2018 Huang
et al. 2018 Chen et al., 2018a) mostly Tocus on shallow models (2 layers) on relatively small graphs.
Scaling GCNs to larger datasets and deeper layers still requires fast alternate training methods.
In GCN, data to be gathered for one output node comes from its neighbors in the previous layer. Each of these neighbors in turn, gathers its output from the previous layer, and so on. Clearly, the deeper we back track, the more multi-hop neighbors to support the computation of the root. The number of support nodes (and thus the training time) potentially grows exponentially with the GCN depth. To mitigate such "neighbor explosion", otate-of-the-art methods use various layer sampling techniques. The works by Hamilton et al. (2017); Ying et al. (2018a); Chen al. (2018a) ensure that only small number of neighbors (typically from 2 to 50) are selected by one node in the next layer. Chen et al. (2018)) and Huang et al. (2018) further propose samplers to restrict the neighbor expansion factor to I, by ensuring a fixed sample size in all layers. While these methods significantly speed up training, they face challenges in scalability, accuracy or computation complexity.
"Equal contribution

---

Published as a conference paper at ICLR 2020
Present work We present GraphSAINT (Graph SAmpling based INductive learning meThod) to efficiently train deep GCNs. GraphSAINT is developed from a fundamentally different way of minibatch construction. Instead of building a GCN on the full training graph and then sampling across the layers, we sample the training graph first and then build a full GCN on the subgraph. Our method is thus graph sampling based. Naturally, GraphSAINT resolves "neighhor explosion", since every GCN of the minibatches is small yet complete one. On the other hand, graph sampling based method also brings new challenges in training. Intuitively, nodes of higher influence on each other should have higher probability to form subgraph. This enables the sampled nodes to "support" each other without going outside the minibatch. Unfortunately, such strategy results in non-identical node sampling probability, and introduces bias in the minibatch estimator. To address this issue, we develop normalization techniques so that the feature learning does not give preference to nodes more frequently sampled. To further improve training quality, we perform variance reduction analysis, and design light-weight sampling algorithms by quantifying "influence" of neighbors. Experiments on GraphSAING using five large datasets show significant performance gain in both training accuracy and time. We also demonstrate the flexibility of GraphSA INT by integrating our minibatch method with popular GCN architectures such as JK-net (Xu et al. 2018) and GAT (Veličković et al.) (0117) The resulting deep models achieve new state-of-the-art Fl scores on PPI (0.995) and Reddit (0.970).
2 RELATED WORK
A neural network model that extends convolution operation to the graph domain is first proposed by Brunna et al.] (003)). Further, Kipf & Welling (2016); Defferrard et al. (2016) speed up graph convolution computation with localized filters based on Chebyshev expansion. They target relatively small datasets and thus the training proceeds in full batch. In order to scale GCNs to large graphs layer sampling techniques (Hamilton et al.) 2017 Chen et al. 2018b] Ying et al., 201 8a Chen et al., 2018al Gao et al.] 2018; Huang et al., 2018) have been proposed for efficient minibatch training. All of them follow the three meta steps: I. Construct complete GCN the full training graph. 2. Sample nodes or edges of each layer to form minibatches. 3. Propagate forward and backward among the sampled GCN. Steps (2) and (3) proceed iteratively to update the weights via stochastic gradient descent. The layer sampling algorithm of GraphSAGE (Hamilton et al. (017) performs uniform node sampling on the previous layer neighbors. It enforces pre-defined budget on the sample size, so as to bound the minibatch computation complexity. Ying et al. (2018a) enhances the layer sampler of Hamiiton et al. (2017) by introducing an importance score to each neighbor. The algorithm presumably leads to less information loss due to weighted aggregation. S-GCN (Chen et al., 2018a) further restricts neighborhood size by requiring only two support nodes in the previous layer. The idea is to use the historical activations in the previous layer to avoid redundant re-evaluation. FastGCN (Chen et al. 2018b) performs sampling from another perspective. Instead of tracking down the inter-layer connections, node sampling is performed independently for each layer. It applies importance sampling to reduce variance, and results in constant sample size in all layers. However, the minibatches potentially become too sparse to achieve high accuracy. Huang et al. (2018) improves FastGCN by an additional sampling neural network. It ensures high accuracy, since sampling is conditioned on the selected nodes in the next layer. Significant overhead may be incurred due the expensive sampling algorithm and the extra sampler parameters to be learned.
Instead of sampling layers, the works of Zeng et al. (0188) and Chiang et al. (2019) build mini- batches from subgraphs. Zeng et al. (2018) proposes a specific graph sampling algorithm to ensure connectivity among minibatch nodes. They further present techniques to scale such training on shared- -eireey multi-core platforms. More recently, ClusterGCN (Chiang et al. 2019) proposes graph clustering based minibatch training. During preopeeesssig. the training graph is partitioned into densely connected clusters. During training, clusters are randomly selected to form minibatches, and intra-cluster edge connections remain unchanged. Similar to GraphSAINT, the works of Zeng et al. (2018) and Chiang et al. (2019) do not sample the layers and thus "neighbor explosion" is avoided. Unlike GraphSAINT, both works are heuristic based, and do not account for bias due to the unequal probability of each node / edge appearing in minibatch.
Another line of research focuses on improving model capacity. Applying attention on graphs, the architectures of Veličkovéé et al. (2017): Zhang (2018): Lu et al. (2019) better capture neighbor features by dynamically adjusting edge weights. Kllipprr et al. (2018) combines PageRank with GCNs enable efficient information propagation from many hops away. To develop deeper models,
2

---

Published as a conference paper at ICLR 2020
"skip- connection" is borrowed from CNNs (He et al.) 2015 Huang al. 2017) into the GCN context. In particular, JKt Xu et al. (2018) demonstrates significant accuracy improvement on GCNs with more than two layers. Note, however, that JK-net (Xu et al. 2018) follows the same sampling strategy as GraphS AGE (Hamilton et al. 2017). Thus, its training cost is high due to neighbor explosion. In addition, high order graph convolutions layers (Zhou 2017 Lee et al. 2018 Abu-FI-Haija al.. 2019) also help propagate long-distance features. With the numerous architectural variants developed, the question of how to train them efficiently via minibatches still remains be answered.
3 PROPOSED METHOD: GRAPHSAINT
Graph sampling based method is motivated by the challenges in scalability (in terms of model depth and graph size). We analyze the bias (Section 3.2) and variance (Section 3.3) introduced by graph sampling, and thus, propose feasible sampling algorithms (Section 3.4). We show the applicability of GraphSAINT other architectures, both conceptually (Section 4 and experimentally (Section 5.2
In the following, we define the problem of interest and the corresponding notations. A GCN learns representation of an un-directed, attributed graph (V,E), where each node V has length-f attribute a.. Let A be the adjacency matrix and A be the normalized one (i.c., A = D-1 A, and D the diagonal degree matrix). Let the dimension of layer-& input activation be f() The activation of node is { E R and the weight matrix is ( E 1 ( Note that D. = x! Propagation rule of layer defined as follows:
De (f+1)
Σ Auy (W()) (0(()
where A a scalar, taking an element of A. And (.) the activation function (e.g., ReI.U).
We use subscript "s" to denote parameterd of the sampled graph (e.g., 9s, E.).
GCNs can applied under inductive and transductive settings. While GraphSAINT is applicable to both, in this paper, we focus inductive learning. It has been shown that inductive learning is especially challenging (Hamilton et al. (017) - during training, neither attributes nor connections of the test nodes are present. Thus, inductive model has to generalize to completely unseen graphs.
3.1 MINIBATCH BY GRAPH SAMPLING
0
S
7
3
0
0
G. (A)
Full GCN G.
Figure 1: GraphSAINT training algorithm
GraphSAINT follows the design philosophy of directly sampling the training graph 9, rather than the corresponding GCN. Our goals to 1. extract appropriately connected subgraphs that little information is lost when propagating within the subgraphs, and 2. combine information of many subgraphs together so that the training process overall learns good representation of the full graph.
Figure I and Algorithm I illustrate the training algorithm. Before training starts, we perform g with the given sampler SAMPLE. The processing estimates the probability of a node v e V and an edge e E E being sampled by SAMPLE. Such probability is later used to normalize the subgraph neighbor aggregation and the minibatch loss (Section 3.2). A Afterwards,
weight pre pre-procss
3

---

Published as a conference paper at ICLR 2020
Algorithm 1 GraphSAINT training algorithm
Input: Training graph 9 (V, X); Labels Y; Sampler SAMPLE:
Output: GCN model with trained weights
1: Pre-processing: Setup SAMPLE parameters; Compute normalization coefficients a, A.
2: for each minibatch do
3: Go E,) + Sampled sub-graph of & according to SAMPLE
4: GCN construction G..
5: fye E V.} t Forward propagation of { V E V.J. normalized by
6:
Backward propagation from A-normalized loss L (yev T.). Update weights.
7:
end for
training proceeds by iterative weight updates via SGD. Each iteration starts with an independently sampled 9, (where [=al < (V). We then build full GCN on G. to generate embedding and calculate loss for every v E V.. In [ node representation is learned by performing node classification in the supervised setting, and each training node comes with a ground truth label ye
Intuitively, there are two requirements for SAMPLE: 1. Nodes having high influence on each other should be sampled in the same subgraph. 2. Each edge should have non-negligible probability to be sampled. For requirement (1), an ideal SAMPLE would consider the joint information from node connections as well as attributes. However, the resulting algorithm may have high complexity as define "influence" from the
would need to infer the relationships between features. For simplicity, graph connectivity perspective and design topology based samplers. Requirement (2) leads to better generalization since it enables the neural explore the full feature and label space.
3.2 NORMALIZATION
A sampler that preserves connectivity characteristic of & will almost inevitably introduce bias into minibatch estimation. the following, we present normalization techniques to eliminate biases.
Analysis of the complete multi-layer GCN is difficult due to non-linear activations. Thus, we analyze the embedding of each layer independently. This similar to the treatment of layers independently by prior work (Chen et al. 2018b Huang et al. 2018). Consider layer-(E + 1) node and layer- node u. v is sampled (i.e., U. E Va), we can compute the aggregated feature of v as:
(e+1)
Σ NEV
Au,
(wra)
(E) x a u/j
1
Σ WEV
A (() 1 ulp:
(2)
Cuuv
Qu,v
where (1( (9) T ( and Lujo E [0, the indicator function given is in the subgraph (u, v) E Ex: un not defined if Vs). We refer
(i.e., 1 ale 0 if V. A v) & Es; ll to the constant Oure as aggregator normalization. Define Pu, = Pu.u as the probability of an edge (u, v) being sampled in a subgraph, and Pe as the probability of node u V being sampled.
Proposition 3.1. ço (l+1) is an unbiased estimator of the aggregation of in the full (E + 1)th GCN layer, if au,o
Pa. i.e., E (s!(t)))= Σ P.
An, (())
NEV
Assuming that each layer independently learns an embedding, we use Proposition 3.1 to normalize feature propagation of each layer of the GCN built by GraphSAINT. Further, let L, be the loss on in the output layer. The minibatch loss is calculated as Thatch = Eveg, Tee/ Av. where X, is a constant
that we term loss normalization. We set A = | Pe so that:
(Trbatch)
Σ G.EG NEV.
Σ
Σ I
X
V
DEV
Feature propagation within subgraphs thus requires normalization factors a and X, which are com- puted based on the edge and node probability Pu,v, Pv. In the case of random node or random edge samplers, Pa,, and p. can be derived analytically. For other samplers in general, closed form expression is hard to obtain. Thus, perform pre-processing for estimation. Before training starts,
4

---

Published as a conference paper at ICLR 2020
run the sampler repeatedly obtain a set of N subgraphs G. We setup a counter C. and Cu,v for each v E V and (u, u) E ε, to count the number of times the node or edge appears in the subgraphs Cu."
of G. Then we set Cuue Cv C,
N. The subgraphs G, E G can all be reused as minibatches during training. Thus, the overhead of pre-processing is small (see Appendix D.2)
Cv. and A C,
3.3 VARIANCE
We derive samplers for variance reduction. Let e be the edge connecting u, v, and b.
Ao, tt 1((-1))
A t. (f-1), It is desirable that variance of all estimators çt is small. With this objective, define:
A Pr, 0,
(
< <=Σ> VEG.
Po ΣΣ
11
ΣΣ
Pe 19
(4)
where 1. = l & Exi = 0f & &s. And -
= Of & V.. The factor pu in the first equality is present so that Ç is unbiased estimator of the sum of all node aggregations all layers: E (C) E. Evey E (5: Note that ( 1e Vl, since once an edge is present in the sampled graph, it is present in all layers of our GCN.
We define the optimal edge sampler to minimize variance for every dimension of Ç. We restrict ourselves to independent edge sampling. For each e E E, we make independent decision on whether it should be in GG not. The probability of including is pe. We further constrain Σ Pe m, so that the expected number of sampled edges equals to m. The budget m is a given sampling parameter. Theorem 3.2. Under independent edge sampling with budget m, the optimal edge probabilities to (2)
minimize the sum of variance of each Ç's dimension is given by: Pe
Ee
be
To prove Theorem we make use of the independence among graph edges, and the dependence among layer edges to obtain the covariance of { Then using the fact that sum of pr. is a constant, use the Suuchy-Schwazz inequality to derive the optimal Pe- Details are in Appendix A
Note that calculating (! requires computing Ze (É-1) which increases the complexity of sampling. As reasonable simplification, we ignore (:()) to make the edge probability dependent on the graph topology only. Therefore, we choose Pe x A Au,o deg(u)
dog(v)
The derived optimal edge sampler agrees with the intuition in Section If two nodes connected and they have few neighbors, then u and v are likely to be influential to each other. this case, the edge probability Pu.. Pu.u should be high. The above analysis on edge samplers also inspires us to design other samplers, which are presented in Section 3.4
We can also apply the above edge sampler to perform layer sampling. Under the indepen- dent layer sampling assumption of Chen et al. (2018b), would sample connection (u(t), e((+)) with probability pu, & dog(u)
Remark
1 + dog(u)) For simplicity, assume a uniform degree graph (of degree d).
Then pe (2) p. For an already sampled (4) connect layer + 1, least one of its edges has to be selected by the layer E + sampler. Clearly, the probability of an input layer node to "survive" the
number of independent sampling process is (1 (1- (1 )) L-1
Such layer sampler potentially returns an overly sparse minibatch for L > 1. On the other hand, connectivity within minibatch of GraphSAINT never drops with GCN depth. If an edge is present in layer E, it is present in all layers.
3.4 SAMPLERS
Based on the above variance analysis, present several weight and efficient samplers that GraphSAINT has integrated. Detailed sampling algorithms are listed Appendix B
Random node sampler
We sample [V.] nodes from V randomly, according to node probability
distribution P (u) x A. This sampler is inspired by the layer sampler of Chen et al. (2018b)
5

---

Published as a conference paper at ICLR 2020
Random edge sampler We perform edge sampling described in Section 3.3
Random walk based samplers Another way to analyze graph sampling based multi-layer GCN is to ignore activations. In such case, layers can be represented as single layer with edge weights given by B Ä Following a similar approach as Section 3.3 if were possible to pick pairs of nodes (whether or not they are directly connected in the original A) independently, then we would set Pu.e X B B where Bu. can be interpreted as the probability of random walk to start at u and end at u in L hops (and B.,, vice-versa). Even though it is not possible to sample subgraph where such pairs of nodes are independently selected, we still consider a random walk sampler with walk length L as a good candidate for L-layer GCNs. There are numerous random walk based samplers proposed in the literature (Ribeiro & Towsley] 20T0: Leskovec & Faloutsos 2006; Hu & Lau, 2013) Li et al. 20155.. In the experiments, we implement regular random walk sampler (with r root nodes selected uniformly at random and each walker goes / hops), and also a multi-dimensional random walk sampler defined in |Ribeiro & Towsley (2010).
For all the above samplers, we return the subgraph induced from the sampled nodes. The induction step adds more connections into the subgraph, and empirically helps improve convergence.
4 DISCUSSION
Extensions GraphSAINT admits two orthogonal extensions. First, GraphSAINT can seamlessly integrate other graph samplers. Second, the idea of training by graph sampling applicable to many GCN architecture variants: 1. Jumping knowledge (Xu et al. 2018): since our GCNs constructed during training are complete, applying skip connections to GraphSAINT is straightforward. On
the other hand, for some layer sampling methods (Chen et al., 201 Huang et al.) 2018). 8), extra modification to their samplers is required, since the jumping knowledge architecture requires laver-& samples to be subset of layer- 1) samples") 2. Attention (Veličković et al. 2017 Fey 2019 Zhang et al. 2018): while explicit variance reduction is hard due to the dynamically updated attention values, it is reasonable apply attention within the subgraphs which are considered representatives of the full graph. Our loss and aggregator normalizations are also applicable
3. Others: To support high order layers (Zhou 2017 Lee et al., 20188] Abu-El EE--aaja et al. 2019) or even more complicated networks for the task of graph classification (Ying et al. (2118)), we replace the full adjacency matrix A with the (normalized) one for the subgraph A, to perform layer propagation.
Comparison GraphSAINT enjoys: 1. high scalability and efficiency, 2. high accuracy, and 3. low training complexity. Point (1) is due to the significantly reduced neighborhood size compared with Hamilton et al. (2017): Ying et al. (2018)): Chen al. (2018a), Point (2) is due to the better inter- layer connectivity compared with Chen et al. (2018b), and unbiased minibatch estimator compared with Chiang al. (2019). Point (3) is due the simple and trivially parallelizable pre-processing compared with the sampling of Huang et al. (2018) and clustering of Chiang et al. (2019).
5 EXPERIMENTS
Setup Experiments are under the inductive, supervised learning setting. We evaluate GraphSAINT on the following tasks: 1. classifying protein functions based on the interactions of human tissue proteins (PPI), 2. categorizing types of images based on the descriptions and common properties of online images (Flickr), 3. predicting communities of online posts based on user comments (Reddit), 4. categorizing types of businesses based on customer reviewers and friendship (Yclp), and 5. classifying product categories based on buyer reviewers and interactions (Amazon). For PPI. we use the small version for the two layer convergence comparison (Table 2 and Figure 2). since Hamilton et al.) ()17)) and[Chen et al. (2018a) report accuracy for this version in their original papers. We use the large version for additional comparison with Chiang et al. (2019) to be consistent with its reported accuracy. All datasets follow sxxeddpartition" " splits. Appendix C.2 includes further details.
"The skip-connection design proposed by Huang et al. (018) does not have such "subset" requirement, and based methods.
thus is compatible with both graph sampling and layer sampling
When applying GraphSAINT to GAT /Veličković et al. 2017), remove the softmax step which normalizes attention values within the same neighborhood, as suggested by Huang al. (2018. See Appendix
6

---

Published as a conference paper at ICLR 2020
Table 1: Dataset statisties ("m" stands for multi-class classification, and "s" for single-class.)
Dataset
Nodes
Edges
Degree
Feature
Classes
Train Val / Test
PPI 14,755
225,270
15
50
121 (m)
0.66 / 0.12 / 0.22
Flickr
89,250
899,756
10
500
(s)
0.50 / 0.25 0.25
Reddit
232,965
11,606,919
50
602
41 (s)
0.66 / 0.10 / 0.24
Yelp 716,847
6,977,410
10
300
100 (m)
0.75 / 0.10 0.15
Amazon
1,598,960
132,169,734
83
200
107 (m)
0.85 / 0.05 0.10
PPI (large version)
56,944
818,716
14
50
121 (m)
0.79 0.11 /0.10
We open source GraphSAIN1 We compare with six baselines: vanilla GCN Kipf Welling 2016), 2. GraphSAGE (ALGGEHHamiin (Hamilton et (017)) 3. FastGCN (Chen et al. 2018b), 4. S-GCN (Chen et al. 2018a). AS-AAS-CC (Huang et al. 2018), and ClusterGCN CChang et al. 2019). D. All baselines are executed with their officially released code (see Appendix C.3 for downloadable URLs and commit numbers). Baselines and GraphSAINT are all implemented in Tensorflow with Python3. We experiments NVIDIA Tesla P100 GPU (see Appendix C. for hardware specification).
5.1 COMPARISON WITH STATE-OF-THE-ART
Table 2 and Figure 2 show the accuracy and convergence comparison various methods, All results correspond to two-layer GCN models (for GraphSAGE, we use its mean aggregator). For given dataset, we keep hidden dimension the same across all methods. We describe the detailed architecture and hyperparameter search procedure in Appendix C The mean and confidence interval of the accuracy values Table 2 time of Figure 2 excludes the time for data loading, pre-processing, validation evaluation and model saving. Our pre-processing incurs little overhead in training time. See Appendix [D.2 for cost of graph sampling. For GraphSAINT, we implement the graph samplers described in Section 3.4 In Table 2. "Node" stands for random node sampler; "Edge" stands for random edge sampler; "RW" stands for random walk sampler; "MRW" stands for multi-dimensional random walk sampler.
are measured by three runs under the same hyperparameters. The training
Table 2: Comparison of test set F1-micro score with state-of-the-art methods
Method
PPI
Flickr
Reddit
Yclp
Amazon
GCN
0.515+0.006
0.492+-0.003
0.933++0.000
0.378+00.00
0.281+00.005
GraphSAGE
0.637=0.006 0.50110.003
0.953:10.001
0.63410.006
0.758+1.002
FastGCN
0.513+0.032 0.504++0.001
0.924+0.001
0.265+00053
0.174+0.021
S-GCN
0.963=1.010 0.482:10.003
0.9641100011
0.640=10.002
AS-GCN
0.681=0.012 0.504
0.958+10001
ClusterGCNN
0.875=10.004
0..005
0.954
0.609-10.005
0.759-10.008
GraphSAINT-
0.960=10.001
0.507=10.01
0.962+10.01
0.641#0.000
0.782++0.004
GraphSAINT-BaR
000007
0.510-10.002
0.000
0.653100.003
0.807+0.0001
GraphSAINT-RW
0.981=0.004
0.511
0.966100001
0.653+0.003
0.815+0.000
GraphSAINT-MRW
0.980=10.006
0.510-10.001
0.000
0.652-10.001
0.809
Table 3: Additional comparison with ClusterGCN (test set F1-micro score)
PPI (large version)
Reddit
2 x 512
5 x 2048
2 x 128
4 x 128
ClusterGCN
0.903--0.002
0.994
0.954+0.001
0.966-10.001
GraphSAINT
0.901000003
0.99510.000
0.966110.001
0.970=10.001
Open sourced code: https: : / /ttp//gttbt..tt//////// com/ /tt.::aaSa.NN///aaaaaSA...
The codes throw runtime error the large datasets (Yelp or Amazon).
7

---

Published as a conference paper at ICLR 2020
PPI
Flickr
Reddit
1
0.98
0.52
0.8
0.5
0.96
0.48
M
0.94
Validation FI F1-micro
0.6
0.46
0.92
0.44
0.4
0.9
0
20
40
60
0
10
20
30
40
0
50
100
150
Yelp
Amazon
0.65
0.8
GCN
GraphSAGE
0.6
FastGCN*
S-GCN
0.45
0.4
AS-GCN
ClusterGCN
GraphSAINT-RY
0.25
0.2
CPU execution time
0
200
400
600
800
0
200
400
Training time (second)
Figure 2: Convergence curves of 2-layer models on GraphSAINT and baselines
Clearly, with appropriate graph samplers, GraphSAINT achieves significantly higher accuracy on all datasets. For GraphSAINT-Noods we use the same node probability as FastGCN, Thus, the accuracy improvement is mainly due to the switching from layer sampling to graph sampling (see "Remark" in Section 3.3). Compared with AS-GCN, GraphSAINT is significantly faster. The sampler of AS-GCN expensive to execute, making its overall training time even longer than vanilla GCN. We provide detailed computation complexity analysís on the sampler in Appendix D.2] For S-GCN on Reddit, it achieves similar accuracy as GraphSAINT, at the cost of over 9x longer training time. The released code of FastGCN only supports CPU execution, its convergence curve is dashed.
Table 3 presents additional comparison with ClusterGCN. We use L x f to specify the architecture, where L and f denote GCN depth and hidden dimension, respectively. The four architectures the ones used in the original paper (Chiang et al.) 2219). Again, GraphSAINT achieves significant accuracy improvement. To train models with L >> 2 often requires additional architectural tweaks. ClusterGCN uses its diagonal enhancement technique for the 5-layer PPI and 4-layer Reddit models. GraphSAINT uses jumping knowledge connection (Xu et al. 2018) for 4-layer Reddit.
Evaluation on graph samplers From Table 2 random edge and random walk based samplers achieve higher accuracy than the random node sampler. F sensitivity analysis on parameters of "RW". We use the same hyperparameters (except the sampling parameters) and network architecture those the "RW" entries Table 2 We fix the length each walker to (i.e., GCN depth), and vary the number of roots r from 250 to 2250. For PPI, increasing from 250 to 750 significantly improves accuracy. Overall, for all datasets, accuracy stabilizes beyond 750.
5.2 GRAPHSAINT ON ARCHITACTURE VARIANTS AND DEEP MODELS
In Figure 4 train 2-layer and a 4-layer model of GAT Veličković al. 2017) and JK-net (Xu et al. 2018), by using minibatches of GraphSAGE and GraphSAINT respectively. On the two 4-layer architectures, GraphSAINT achieves much better scalability on deep models. From accuracy perspective, 4-layer GAT-SAGE and JK- SAGE do not outperform the corresponding 2-layer versions, potentially due the smoothening effect caused by the massive neighborhood size. On the other hand, with minibatches returned by our edge sampler, increasing model depth of JK-SAINT leads noticeable accuracy improvement (from 0.966 of 2-layer to 0.970 of 4-layer). Appendix D.I contains additional scalability results.
orders of magnitude speedup than GraphSAGE. indicating
6 CONCLUSION
We have presented GraphSAINT, a graph sampling based training method for deep GCNs on large graphs. We have analyzed bias and variance of the minibatches defined subgraphs, and proposed
8

---

Published as a conference paper at ICLR 2020
* PPI * Flickr
+
Reddit
GraphSAINT 2-layer
GraphSAINT 4-layer
*
Yelp
Amazon
GraphSAGE 2-layer
GraphSAGE 4-yye
Validation FI-micro
Test F F1-micro
0.97
GAT
JK-net
0.8
0.96
0.95
0.6
0.94
0.93
A
0.4
1,000
2,000
10"
10a
10
10"
10a
10*
Number of walkers
Training time (second)
Figure 3: Sensitivity analysis
Figure 4: GraphSAINT with JK-net and GAT (Reddit)
normalization techniques and sampling algorithms to improve training quality. We have conducted extensive experiments to demonstrate the advantage of GraphSAINT in accuracy and training time.
interesting future direction to develop distributed training algorithms using graph sampling based minibatches. After partitioning the training graph in distributed memory, sampling can be performed independently on each processor. Afterwards, training on the self-supportive subgraphs can significantly reduce the system-level communication cost. To ensure the overall convergence quality, data shuffling strategy for the graph nodes and edges can be developed together with each specific graph sampler. Another direction is perform algorithm-systerr -ystttmm--sstmm co-optimization to accelerate the training of GraphSAINT on heterogeneous computing platforms (Zeng et al.] 2018 Zeng & Prasannal 2019). The resolution of "neighbor explosion" by GraphSAINT not only reduces the training computation complexity, but also improves hardware utilization by significantly less data traffic to the slow memory. In addition, task-level parallelization easy since the light-weight graph sampling is completely decoupled from the GCN layer propagation.
ACKNOWLEDGEMENT
This material is based on work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract Number FA8750-17-C-0086 and National Science Foundation (NSF) under Contract Numbers CCF- 11F-1911289 and OAC-191 1229. Any opinions, findings and conclusions or recommendations expressed in this material those of the authors and do not necessarily reflect the views of DARPA or NSF.
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolution architec- tures via sparsified neighborhood mixing. arXiv preprint arXiv:1905.00067 2019..
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. CoRR, abs/1312.6203. 2013. URL httt:tttaaxii...rrg/g/ abs/
1312.62 6203
Yun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques and applications. CoRR, abs/1709.07604, 2017. URL
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. ICML, pp. 941-949, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations (ICLR), 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gar An ef- ficient algorithm for training deep and large graph convolutional networks. CoRR, abs/ Abs/1905.07953, 2019. URL URL //a rxi v. org/ abs 9005 07953

---

Published as a conference paper at ICLR 2020
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pp. 3844-3852, 2016.
Matthias Fey. Just jump: Dynamic neighborhood aggregation graph neural networks. CoRR, abs/1904.04849, 2019. http:////aaxx org/ aaaaab//1999 1904. 04849
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 1426-1424, New York, NY, USA, 2018. ACM. ISBN
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30, pp. 1024-1034. 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, abs/1512.03385,, 2015. URL
wwtp:///g/aaaaaaaaaoaoooo 03385
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()):
7735-17801 1997.
Pili Hu and Wing Cheong Lau. A survey and taxonomy of graph sampling. arXiv preprint 130iv 5865, 2013.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances Neural Information Processing Systems, pp. 4558 4568,, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint (tf.:1411269000 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classsfictton with graph convolutional networks. 02907
CoRR, 0tas/1609.02900 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Personalized embedding propa- gation: Combining neural networks on graphs with personalized pagerank. CoRR, ahss/8810.05997 2018. /ttp:ttp///axxi.cco
als http://aass//.a....///
1810. 05997
John Boaz Lee, Ryan Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. Higher- order graph convolutional networks. CoRR, abs/ 1atps/087,7777, 2018. URLhttp: wtt.vv..xvv.//////
07697
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 631-6366 ACM, 2006.
R. Li, X. Yu, L. Qin, R. Mao, and T. Jin. On random walk based graph sampling. In 2015 IEEE 31st International Conference on Data Engineering, pp. 927-938, April 2015. doi: 10.1109/CCE. 2015.7113345
Haonan Lu, Seth H. Huang, Tian Ye, and Xiuyan Guo. Graph star net for generalized multi-task learning. CoRR, abs/1906.11 12330, 2019. URL. httpttp:://awww.o/////aa///////e
12330
Bruno Ribeiro and Don Towsley. Estimating and sampling graphs with multidimensional random walks. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, pp. 390-403. ACM, 2010.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
10

---

Published as a conference paper at ICLR 2020
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. CoRR, abs/1901.00596, 2019. URL http:
//azxiv.org//
00596
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint
0rX.v:1806.03366,, 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, KDD '18 2018a. ISBN 978-1-4503-5552-0.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS' 18, pp- 4805-4815. USA, 2018b. Curran Associates Inc. URL http: / acm. ptgg/citatiiin cfm? ?id= 3327345. 3327389
Hanqing Zeng and Viktor Prasanna. GraphACT: Accelerating GCN training on CPU-FPGA hetero- geneous platforms. arXiv preprint arXiv:2001.0244 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Accurate, efficient and scalable graph embedding. CoRR, abs/1810.11899) 2018. URL http:
//axxiv.crg/bb//1110...
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated atten- tion networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.000 07,944 2018
Zhenpeng Zhou. Graph convolutional networks for molecules. CoRR, abs/ 706.09916, 2017. URL
http://arxx..orr//s5/776555.-559
A PROOFS
Proof of Proposition
3.1
Under the condition that v is sampled in subgraph:
Ava
E
(((+1))
=E
Σ
(x
ulv
Ouvy
NEE
Aviu
(0 (1uje)
Ohuy
A (() P ((,,)) sampled/u sampled)
F
Cu,y
NEV
Aou (1) P ((u, v) sampled)
Cu,y
P (v sampled)
NEY
Avu (1) Pu.v
(5)
Olu,v
Po
where the second equality is due linearity of expectation, and the third equality (conditional edge probability) is due to the initial condition that is sampled in a subgraph.
It directly follows that, when 0a,
Pa.v
Pv
E
c
-E
-AAo,ue!!
Ao,u
NEV
11

---

Published as a conference paper at ICLR 2020
Proof of Theorem 3.2 Below, Cov (-) to denote covariance and Var (-) to denote variance.
For independent edge sampling as defined in Section
3.3 Cov
(8)) ((a)) 0, Ve1 * ez. And for
full GCN the subgraph, Cov (Le 1e (E>)
pē. To start the proof, we first assume that
Pe
the be is one dimensional (i.e., a scalar) and denote it by (()) Now,
b Cov (1(6), ((ba))
be
Var (5) =
Σ
Var
(1()
+
Pe
0
(1)
b be
[ta)
Σ
((t))
Σ
(pe - P&.
Pe
Pr
e,t
e,t
Ee
2
Σ
b
(6)
Pe
Let a given constant m
Ee Pe be the expected number of sampled edges. By Cauchy-Schwarz in-
equality:
E.
(.) m Ee
((t)
E. (vPe)* 2 EEee" ((
2
The equality is achieved
Σ, 60) Pa. i.e., variance is minimized when Pa. x
E (1))
when
vPc
directly follows that:
m
Σ
60
Eee
Ee
For the multi-dimensional case of (0) following similar steps as above, is easy to show that the optimal edge probability to minimize E, Var (4:) (where is the index for ("s dimensions) is:
m
Σ
En
Σ
2 6
B SAMPLING ALGORITHM
Algorithm lists the four graph samplers we have integrated into GraphSAINT. The naming of the samplers follows that of T Note that the sampling parameters and m specify a budget rather than the actual number of nodes and edges in the subgraph G,. Since certain nodes edges in the training graph G may be repeatedly sampled under single invocation of the sampler, we often have [V2l < n for node and MRW samplers, [Val < 2m for edge sampler, and V/ < h for RW sampler.
approximate version of the independent edge sampler defined in Section 3.4 Complexity (excluding the subgraph induction step) of the original version in Section 3.4 is O (ET), while complexity of the approximate one is O (m). When m < [E), the approximate version leads to identical accuracy as the original one, for a given m.
Also note that the edge sampler presented in Algorithmßiss
C DETAILED EXPERIMENTAL SETUP
C.I HARDWARE SPECIHICATION AND ENVIRONMENT
We run our experiments on single machine with Dual Intel Xeon CPUs (E5-2698 v4 @ 2.2Ghz), one NVIDIA Tesla P100 GPU (16GB of HBM2 memory) and 512GB DDR4 memory. The code is written in Python 3.6.8 (where the sampling part is written with Cython 0.29.2). We use Tensorflow 1.12.0 on CUDA 9.2 with CUDNN 7.2.1 to train the model on GPU, Since the subgraphs are sampled independently, we the sampler in parallel on 40 CPU cores.
12

---

Published as a conference paper at ICLR 2020
Algorithm 2 Graph sampling algorithms by GraphSAINT
Input: Training graph g (V;E); Sampling parameters: node budget n; edge budget m; number of roots r; random walk length h
Output: Sampled graph Gs E,)
1: function NODE(G,n)
D. Node sampler
2:
( A. /vvvv
3:
V. f nodes randomly sampled (with replacement) from V according to P
4: G. f Node induced subgraph of & from V,
5: end function
6: function EDGE(G.m)
D Edge sampler (approximate version)
7:
((u,z)) = deg(as
dog(v) /E (or wiEEs deg(ue) + deg(v")
8:
E, 4 m edges randomly sampled (with replacement) from & according to P
9:
V. + Set of nodes that are end-points of edges in &
10:
Go Node induced subgraph of G from V.
11: end function
12: function RW(G.r.h)
Random walk sampler
13: VrouE <- r root nodes sampled uniformly at random (with replacement) from
14: V. Viont
15:
for E Vmna do
17:
for d = 1 to h do
Node sampled uniformly at random from u's neighbor V. < V. U (u}
19:
end for 21: end for
22:
G. + Node induced subgraph of & from V.
23: end function
24: function MRW(G,n.r)
> Multi-dimensional random walk sampler
25:
Vrs root nodes sampled uniformly random (with replacement) from V
26:
V. - Vis
27:
for + to do
28:
Select u E VFs with probability deg(u)/ Evers deg(v)
29:
v' + Node randomly sampled from u's neighbor
V/s t (Vis \ {u)) {u/}
31:
V V.U
32:
end for
33:
G- <- Node induced subgraph of G from V-
34:
end function
13

---

Published as a conference paper at ICLR 2020
100
11
PP
Flickr
P (degree > k)
Reddit
10-2
Yelp
Amazon
10
10-6
1mm
10
10
10a
103
10
10
Degree
Figure 5: Degree Distribution
C.2 ADDITIONAL DATASET DETAILS
Here present the detailed procedures to prepare the Flickr, Yelp and Amazon datasets.
The Flickr dataset originates from NUS-wide The SNAP website collected Flickr data from four different sources including NUS-wide, and generated un-directed graph. One node in the graph represents one image uploaded to Flickr. If two images share some common properties (e.g.. same geographic location, same gallery, comments by the same user, etc.), there is an edge between the nodes of these two images. We use as the node features the 500-dimensional bag-of-woo word representation of the images provided by NUS-wide. For labels, we scan over the 81 tags of each image and manually merged them to 7 classes. Each image belongs to one of the 7 classes.
The Yelp dataset is prepared from the raw json data of businesses, users and reviews provided in in the raw
the open challenge website For nodes and edges, scan the friend list of each json file of users. If two users are friends, we create an edge between them. We then filter out all the reviews by each user and separate the reviews into words. Each review word is converted 300-dimensional vector using the Word2 Vec model pre-trained on GoogleNews The word vectors of each node are added and normalized serve as the node feature (i.e., 2t)). As for the node labels, we scan the raw json file of businesses, and use the categories of the businesses reviewed by user v as multi-class label of v.
For the Amazon dataset, node is product the Amazon website and an edge (u, v) is created if products u and y are bought by the same customer. Each product contains text reviews (converted to 4-gram) from the buyer. We use SVD to reduce the dimensionality of the 4-gram representation to 200, and use the obtained vectors as the node feature. The labels represent the product categories (e.g., books, movies, shoes).
Figure 5 shows the degree distribution of the five graphs. A point (k, p) in the plot means the probability of node having degree at least & is p.
C.3 ADDITIONAL DETAILS IN EXPERIMENTAL CONFIGURATION
Table summarrzes the URLs to download the baseline codes.
The optimizer for GraphSAINT and all baselines is Adam (Kingma & Ba 2014). For all baselines and datasets, we perform grid search on the hyperparameter space defined by:
Hidden dimension: {128, 256, 512]
http:///aaccccoc...u...seeeeeaea htm
attps//ww..yeep.com//ttteeet
fttpst//code.googlee.coo
14

---

Published as a conference paper at ICLR 2020
Table URLs and commit number run baseline codes
Baseline
URL
Commit
Vanilla GCN
qi github. wi aim f/Graph
atfdef
GraphSAGE
LLUD C05s/ wi
a0fdef
FastGCN
G1 hub, zom http//mttcuureeereeeeeeeee
b8c6e6
S-GCN
github. thu 01/Stocasttcccccccccccccco gen
da7b78
AS-GCN
huuh com/ http:///o//oo/nnaaaaaoaoa.
5436ec
ChusterGCN
github. ctttia...o//ggggleego wwt..rargooooooooc---eee--rre-ee //
99021e
Table 5: Training configuration of GraphSAINT for Table
Training
Sampling
Sampler
Dataset
Learning rate
Dropout
Node budget
Edge budget
Roots
Walk length
PPI
0.01
0.0
6000
Flickr
0.01
0.2
8000
Node
Reddit
0.01
0.1
8000
Yelp
0.01
0.1
5000
Amazon
0.01
0.1
4500
PPI
0.01
0.1
4000
Flickr
0.01
0.2
6000
Edge
Reddit
0.01
0.1
6000
Yelp
0.01
0.1
2500
Amazon
0.01
0.1
2000
PPI
0.01
0.1
3000
2
Flickr
0.01
0.2
6000
2
RW
Reddit
0.01
0.1
2000
Yelp
0.01
0.1
1250
2
Amazon
0.01
0.1
1500
2
PPI
0.01
0.1
8000
2500
Flickr
0.01
0.2
12000
3000
MRW
Reddit
0.01
0.1
8000
1000
Yelp
0.01
0.1
2500
1000
Amazon
0.01
0.1
4500
1500
Dropout: (0.0, 0.2,0.2,0.3)
Learning rate: (0.1, 0.01, 0.0001
The hidden dimensions used for Table 2 Figure Figure 3 and Figure are: 512 for PPI, 256 for Flickr, 128 for Reddit, 512 for Yelp and 512 for Amazon.
All methods terminate after fixed number of epochs based on convergence. We the model producing the highest validation set F1-micro score, and reload it to evaluate the test set accuracy.
For vanilla GCN and AS-GCN, use the mean aggregator with the default batch size 512. For S-GCN, we set the flag -cv -ovd (which stand for "control variate" and "control variate dropout") with pre-computation of the first layer aggregation. According to the paper (Chen et al. 2018a). such pre-computation significantly reduces training time without affecting accuracy. For S-GCN, we use the default batch size 1000, and for FastGCN, we use the default value 400. For ClusterGCN, its batch size is determined by two parameters: the cluster size and the number of clusters per batch. We sweep the cluster size from 500 to 10000 with step 500, and the number of clusters per batch from {1, 10, 20, 40} to determine the optimal configuration for each dataset / architecture. Considering that for ClusterGCN, the cluster structure may be sensitive to the cluster size, and for FastGCN, the minibatch connectivity may increase with the sample size, we present additional experimental results to reveal the relation between accuracy and batch size in Appendix D.3
the batch size their default value 512. For GraphSAGE,
15

---

Published as a conference paper at ICLR 2020
Table 6: Training configuration of GraphSAINT for Table
Training
Sampling
Arch.
Sampler
Dataset
Learning rate
Dropout
Node budget
Edge budget
Roots
Walk length
2 x 512
MRW
PPI (large)
0.01
0.1
1500
300
x 2048
RW
PPI (large)
0.01
0.1
3000
2
2 x 128
Edge
Reddit
0.01
0.1
6000
4 128
Edge
Reddit
0.01
0.2
11000
Table 7: Training configuration of GraphSAINT for Figure (Reddit)
2-luyer GAT-SAINT
4-layer GAT-SAINT
2-1ayer JK-SAINT
4-layer JK-SAINT
Hidden dimemsion Atlention K
128
128
128
128
8
Aggregation +
Concat. Edge (budget: 6000) 0.01
Concat.
RW
RW
Edge (budget: 11000)
Sampler
(root:
3000; length: 2)
(root: 2000; length: 4)
I. learning rate Dropout
0..1
0.01
0.01
0.2
0.2
0.1
0.2
Configuration of GraphSAINT to reproduce Table 2 results is shown in Table 5 Configuration of GraphSAINT to reproduce Table results shown in Table
Below we describe the configuration for Figure 4
The major difference between normal GCN and JK-net (Xu et al. 2018) that JK-net has an additional final layer that aggregates all the output hidden features of graph convolutional layers 1 to L. Mathematically, the additional aggregation layer outputs the final embedding øyK as follows:
W JK
(
where based on Xu et al. 22018 + vector aggregation operator: max-pooling, concatenation
or LSTM (Hochreiter & Schmidhuber 1997) based aggregation.
The graph attention of GAT (Veličković et al. 2017) calculates the edge weights for neighbor aggregation by an additional neural network. With multi-head (K) attention, the layer- 1)
features propagate to layer-(E) as follows:
K
(9)
Σ
au ax (f-1))
(8)
k=1
(Encighbor(r))
where || is the vector concatenation operation, and the coefficient is calculated with the attention weights a by:
0 = LeakyRelLU ((at) [ s.
W* x...)
Note that the calculation is slightly diffferent from the original equation in Veličković et al. (2017). Namely, GAT-SAINT does not normalize a by softmax across all neighbors of v. We make such modification since under the minibatch setting, node does not all its neighbors in the training graph. The removal of sofumax also seen in the attention design of Huang et al.) (2018). Note that during the minibatch training, GAT-SAINT further applies another edge coefficient top of attention for aggregator normalization.
Table 7 shows the configuration of the GAT-SAINT and JK-SAINT curves in Figure
16

---

Published as a conference paper at ICLR 2020
GraphSAINT: Reddit
S-GCN: Reddit
Node
Edge RW
MRW
GraphSAINT: Yelp
S-GCN: Yelp
Fraction trainnni time
Normalized training time
8
1.5
6
4
0.5
2
2
5
PPI
Flickr
Reddit
Yelp
Amazon
GCN depth
Figure Comparison of training efficiency
Figure Fraction of training time on sampling
D ADDITIONAL EXPERIMENTS
D.1 TRAINING EFFICIENCY ON DEEP MODELS
We evaluate the training efficiency for deeper GCNs. We only compare with S-GCN, since implemen- tations for other layer sampling based methods have not yet supported arbitrary model depth. The batch size and hidden dimension are the same as Table On the two large graphs (Reddit and Yelp), we increase the number of layers and measure the average time per minibatch execution. In Figure 6, training cost of traphSAINT is approximately linear with GCN depth. Training cost of S-GCN grows dramatically when increasing the depth. This reflects "neighbor explosion" phenomenon (even though the expansion factor of S-GCN is just 2). On Yelp. S-GCN gives "out-of-memory" enror for models beyond 5 layers.
D.2 COST OF SAMPLING AND PRE-PROCESSING
Cost of graph samplers of GraphSAINT Graph sampling introduces little training overhead. Let l, be the average time to sample one subgraph on multi-core machine. Let l be the average time perform the forward and backward propagation the ratio tx/t, for various datasets. The parameters of the samplers are the same Table 2 For Node, Edge and RW samplers, we observe that time to sample one subgraph is in most cases less than 25% of the training time. The MRW sampler is more expensive to execute. Regarding the complete pre-processing procedure, we repeatedly run the sampler for N 50 /V / times before training, estimate the node and edge probability discussed in Section 3.2 (were V. is the average subgraph size). These sampled subgraphs are reused as training minibatches. Thus, training runs for more than N iterations, the pre-processing is nearly zero-cost. Under the setting of Table 2 pre-processing on PPI and Yelp and Amazon does not incur any overhead in training time. Pre-processing Flickr and Reddit (with RW sampler) takes less than 40% and 15% of their corresponding total training time.
minibatch on GPU. Figure shows
Cost of layers sampler AS-GCN AS-GCN uses an additional neural network estimate the conditional sampling probability for the previous layer. For node already sampled in layer e, features of layer-(e- 1) corresponding to all v's neighbors need be fed to the sampling neural network to obtain the node probability. For sake of analysis, assume the sampling network is single layer MLP, whose weight WMLP has the same shape as the GCN weights (()), Then we can show, for I--layer GCN on a degree-d graph, per epoch training complexity
AS-GCN is approximately = (d. EL-I d' times that of vanilla GCN. For L = 2, we have Y z 2. This explains the observation that AS-GCN is slower than vanilla GCN in Figure [ Additional, Table @ shows the training time breakdown for AS-GCN. Clearly, its sampler is much more expensive than the graph sampler of GraphSAINT.
17

---

Published as a conference paper at ICLR 2020
Table Per epoch training time breakdown for AS-GCN
Forward / Backward propagation time (sec)
Dataset
Sampling time (sec)
PPI Flickr
1.1
0.2
5.3
1.1
Reddit
20.7
3,5
Cost of clustering of ClusterGCN ClusterGCN uses the highly optimized METIS softward perform clustering. Table summarizes the time to obtain the clusters for the five graphs. On the large and dense Amazon graph, the cost of clustering increase dramatically. The pre-processing time of ClusterGCN on Amazon is more than 4x of the total training time. On the other hand, the sampling cost of GraphSAINT does not increase significantly for large graphs (see Figure 7
Table Clustering time of ClusterGCN
PPI
Flickr
Reddit
Yelp
Amazon
Time (sec)
2.2
11.6
40.0
106.7
2254.2
Taking into account the pre- pre-proeessing time, sampling time and training time altogether, we sum- marize the total convergence time of GraphSAINT and ClusterGCN in Table TO (corresponding to T configuration). On graphs that are large and dense (e.g., Amazon), GraphSAINT achieves significantly faster convergence. Note that both the sampling of GraphSAINT and clustering of ClusterGCN can be performed offline.
Table 10: Comparison of total convergence time (pre-processing + sampling + training, unit: second)
PPI
Flickr
Reddit
Yelp
Amazon
GraphSAINT-Edge
91.0
7.0
16.6
273.9
401.0
GraphSAINT-RW
103.6
7.5
17.2
310.1
425.6
ClusterGCN
163.2
12.9
55.3
256.0
2804.8
D.3 EFFECT OF BATCH SIZE
Table IT] shows the change of test set accuracy with batch sizes. For each row of Table TT we fix the batch size, tune the other hyperparameters according to Appendix C.3] and report the highest test set accuracy achieved. For GraphS S-GCN and AS-GCN, their default batch sizes (512, 1000 and 512, respectively) lead to the highest accuracy all datasets. For FastGCN, increasing the default batch size (from 400 to 4000) leads to noticeable accuracy improvement. For ClusterGCN, different datasets correspond to different optimal batch sizes. Note that the accuracy in Section 5.1 is already tuned by identifying the optimal batch size on a per graph basis.
For FastGCN, intuitively, increasing batch size may help with accuracy improvement since the minibatches may become better connected. Such intuition is verified by the rows of 400 and 2000. However, increasing the batch size from 2000 to 4000 does further improve accuracy significantly, For ClusterGCN, the optimal batch size depends on the cluster structure of the training graph. For PPI, small batches are better, while for Amazon, batch size does not have significant impact on accuracy. For GraphSAGE, overly large batches may have negative impact on accuracy due to neighbor explosion. Approximately, GraphSAGE: expand 10x more neighbors per layer. For 2-layer GCN, a size 2 x 10 minibatch would then require the support of 2 x 10 nodes from the
/ aaro//aarrrroooooo dt.c umn, wttp///hone//mmtii//msssiiiiiiie
Default batch
The training does not converge.
The codes throw runtime the large datasets (Yelp or Amazon).
18

---

Published as a conference paper at ICLR 2020
Table 11: Test set F1-micro for the baselines under various batch sizes
Method
Batch size
PPI
Flickr
Reddit
Yelp
Amazon
256
0.600
0.474
0.934
0.563
0.428
512
0.637
0.501
0.953
0,634
0.758
GraphSAGE
1024
0.610
0.482
0.935
0.632
0.705
2048
0.625
0.374
0.936
0.563
0,447
400*
0.513
0.504
0.924
0.265
0.174
FastGCN
2000
0.561
0.506
0.934
0.255
0.196
4000
0.564
0.507
0.934
0.260
0.195
500
0.519
0.462
1000*
0.963
0.482
0.964
0.640
S-GCN
2000
0.646
0.482
0.949
0.614
4000
0.804
0,482
0.949
0.594
8000
0.694
0.481
0.950
0.613
256
0.682
0.504
0.950
512*
0.687
0.504
0.958
AS-GCN
1024
0.687
0.502
0.951
2048
0.670
0.502
0.952
500
0.875
0.481
0.942
0.604
0.752
1000
0.831
0.478
0.947
0.602
0.756
1500
0.865
0.480
0.954
0.602
0.752
2000
0.828
0.469
0.954
0.609
0.759
ClusterGCN
2500
0.849
0,476
0.954
0.598
0.745
3000
0.840
0.473
0.954
0.607
0.754
3500
0,846
0,473
0.952
0.602
0.754
4000
0.853
0.472
0.949
0.605
0.756
input layer. Note that the full training graph size of Reddit is just around 1.5 x 105. Thus, no matter which nodes are sampled in the output layer, GraphSAGE would almost always propagate features within the full training graph for initial layers. We suspect this would lead to difficulties in learning. For S-GCN, with batch size 500, fails to learn properly on Reddit and Yelp. The accuracy fluctuates in region of very low value, its accuracy not sensitive to the batch size, since AS-GCN addresses neighbor explosion and also ensures good inter-layer connectivity within the minibatch.
after appropriate hyperparameter tuming. For AS-GCN
19


Reviews:
[{"review_id": "rJlxKLYhcH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "Scaling GCNs to large graphs is important for real applications. Instead of sampling the nodes or edges across GCN layers,  this paper proposes to sample the training graph to improve training efficiency and accuracy. It is a smart idea to construct a complete GCN from the sampled subgraphs.  Convincing experiments can verify the effectiveness of the proposed method.  It is a good work.\n\nQuestion: \n1. How can the authors guarantee that subgraphs are properly sampled? Are there any  theoretical guarantee?  \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "SJe_auDjFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new sampling method to train GCN in the mini-batch manner. In particular, unlike existing methods which samples the mini-batch in the node-wise way, GraphSAINT proposed to sample a mini-batch in the graph-wise way. As a result, GraphSAINT uses the same graph across different GCN layers, while most existing methods use different graphs across different GCN layers.  In addition, the authors show that this sampling method is unbiased. Extensive experimental results have shown improvement over existing methods. Overall, this idea is interesting and well presented. \n\nPros:\n1. A new sampling method for the stochastic training of GCN. Have good performance.\n2. Extensive experiments to verify the performance of the proposed method.\n3. The theoretical analysis looks sound.\n\nCons:\n1. GraphSAGE and FastGCN use different graphs across different GCN layers, while ClusterGCN and GraphSAINT use the same graph across different GCN layers. To make a fair comparison, it is necessary to have the same batch size for different methods. How do you deal with this issue in your experiment?\n2. For ClusterGCN, the clustering procedure is done before the training. So, it needs much less computational overhead for sampling in the training course. However, GraphSAINT needs to do the heavy sampling online. Thus, it may consume more time than ClusterGCN for large graphs. It's better to show the running time of these two methods. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BJeVLY_aFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 proposes a training method for graph convolution networks on large graphs. The idea is to train a full GCN on partial samples of the graph. The graph samples are computed based on the graph connectivity, and the authors propose methods for reducing the bias and variance in the training procedure. \n\nThe idea is elegant and intuitive, and the fact that the approach can work with various graph sampling methods adds to its generality. The paper is well-written and the fact that code is published is valuable.\n\nThe results on bias and variance are under the assumption that each layer independently learns an embedding. This would be clearer if added explicitly in the theorem statements (and not as part of the main text). It would be interesting to discuss how realistic this assumption is, and how large the actual bias is. Perhaps this can be measured empirically? \nNevertheless, the empirical result indeed support the claim that this simplifying assumption is enough to derive useful learning rules.\n\nOverall, I believe this is a solid contribution, and I can foresee future extensions that improve the results with more complex graph sampling methods.\n\nQuestion to the authors: I did not understand the second equality in Eq. 3. Could there be a typo?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers advocated acceptance. The AC agrees, feeling the paper is interesting. 
Decision: Accept (Poster)