On Batch-size Selection for Stochastic Training for Graph Neural Networks
Authors: Yaochen Hu
Amit Levi
Ishaan Kumar
Yingxue Zhang
Mark Coates
Venue:  (2021)

Abstract: Batch size is an important hyper-parameter for training deep learning models with stochastic gradient decent (SGD) method, and it has great influence on the training time and model performance. We study the batch size selection problem for training graph neural network (GNN) with SGD method. 
To reduce the training time while keeping a decent model performance, we propose a metric that combining both the variance of gradients and compute time for each mini-batch. We theoretically analyze how batch-size influence such a metric and propose the formula to evaluate some rough range of optimal batch size. 
In GNN, gradients evaluated on samples in a mini-batch are not independent and it is challenging to evaluate the exact variance of gradients. To address the dependency, we analyze an estimator for gradients that considers the randomness arising from two consecutive layers in GNN, and suggest a guideline for picking the appropriate scale of the batch size. 
We complement our theoretical results with extensive empirical experiments for ClusterGCN, FastGCN and GraphSAINT on 4 datasets: Ogbn-products, Ogbn-arxiv, Reddit and Pubmed. We demonstrate that in contrast to conventional deep learning models, GNNs benefit from large batch sizes.

Under review as a conference paper at ICLR 2020
ON BATCH SIZE SELECTION FOR STOCHASTIC TRAIN- ING FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Batch size is an important hyyer-parameet for training deep learning models with stochastic gradient decent (SGD) method, and it has great influence on the training time and model performance. We study the batch size selection problem for train- ing graph neural network (GNN) with SGD method. To reduce the training time while keeping a decent model performance, both the variance of gradients and compute time for each mini-batch. We theoret- ically analyze how batch-size influence such metric and propose the formula evaluate some rough range of optimal batch size. In GNN, gradients evaluated on samples in mini-batch are not independent and it is challenging to evaluate the exact variance of gradients. To address the dependency, we analyze an estimator for gradients that considers the randomness arising from two consecutive layers in GNN, and suggest guideline for picking the appropriate scale of the batch size. We complement our theoretical results with extensive empirical experiments for ClusterGCN, FastGCNN and GraphSAINT on 4 datasets: Pgbn-products, Ogbn- arxiv, Reddit and Pubmed. We demonstrate that contrast to conventional deep learning models, GNNs benefit from large batch sizes.
propose metric that combining
INTRODUCTION
Training large neural networks is often time consuming, In many real world scenarios training might take hours or even days to converge Radford al.] (2018); Devlin al. (2018). As consequence, the identification of strategies to reduce the training time while retaining accuracy is an important research objective. The most popular training algorithms for deep learning are Stochastic Gradient Descent (SGD) and its variants such as RMSProp or Adam Graves (2013); Kingma & Ba (2014).
These algorithms work in an iterative manner, such that in each epoch, the data is first partitioned into minibatches and then weight updates are calculated using only the data in each minibatch. It has been observed that the size of the minibatches plays crucial role in the network's accuracy, generalization capability and converge time (Keskar et al. (2016); He et al. (2019); McCandlish et al. 2018); Radiuk (2017).
For typical deep learning tasks, practitioners have observed that small batch sizes, e.g.. (4. 14.16...,,12). lead to a better generalization performance and training efficiency Keskar et al. (2016). For Graph Neural Networks (GNNs) selecting the appropriate batch size remains more of a mystery, and to the best of our knowledge, there has been no published work that focuses on batch size selection for GNNs. The small batch size guidelines for conventional NNs do not carry over because the batches are used to approximate the graph aggregations or convolutions. The ap- proximation error propagates and leads to a much more substantial variance in the gradients than observed for NNs. In practice, based on released code, we see that implementations tend to either use the largest batch size that can fit into memory Li et al. (2020) or use a small batch size similar to those for non-graph settings Chen et al. (2018): Zou et al. (2019).
In this work, we explore the choice batch size for graph neural networks. By means of theoretical investigation, develop guidelines for the choice of batch size that depend on the average degree and number of nodes of the graph. These guidelines lead to intermediate batch sizes, considerably larger than the small NN batch sizes but much smaller than the maximum size dictated by memory limits of a modern GPU. We provide empirical results that demonstrate that the batch sizes derived using our guidelines provide excellent trade-off between training time and accuracy. Substantially

---

Under review as a conference paper at ICLR 2020
smaller sizes may lead to faster convergence but reduced accuracy; using larger sizes can achieve similar accuracy but training may take much longer to converge.
2 RELATED WORK
Graph Neural Networks (GNNs) have become increasingly popular in addressing graph-based tasks
(Kipf & Welling. 2016 Hamilton et al. 2017 Defferrard et al. 2016] Gilmer et al. 2017 Ying al.
2018). One major line of research aims to improve the expressiveness of GNNs via 1) ad advanced
aggregation functions (Veličković et al. 2017; Monti et al. 2017 Liu et al. 2019 Qu et al. 2019
Pei et al. 2020 2) deeper architecture (Li et al. 2019 2020); and 3) adaptive graph structure (Li
ct al. [0188] Vashishth et al., 2019 Zhang et al. 2019). However, training large-scale GNN model
remains challenging because of the large memory consumption, long convergence time, and heavy
computation (Chiang et al. 2019).
Full-batch gradient descent training scheme was commonly used in the earlier GNN research, While this is suitable for relatively small graphs, requires storing all intermediate embeddings, which is not scalable for large graphs. The convergence can be slow since the parameters are updated only once per epoch. Hamillon et al. (2017) and Ying et al. (2018) proposed the training of GNNs with mini-batch stochastic gradient descent (SGD) methods. Mini-batch SGD training suffers from the neighborhood expansion and leads to time-complexity that grows exponential with respect to the GNN depth. To reduce the exponential complexity of receptive nodes, Chen et al. (2018), Huang jet al. (2018), and /Zou et al.] (2019) proposed layer-wise sampling, where a fixed number of nodes are sampled in each layer. Importance sampling techniques were incorporated to reduce variance. Unfortunately the overhead of the iterative neighborhood sampling strategy is still significant and becomes worse as GNNs become progressively deeper.
Chiang et al. (2019) and Zeng et al. (2020) proposed graph-wise sampling to further improve the sampling efficiency. This can be viewed as a special case of layer-wise sampling where the same set of nodes is sampled across all layers. [Chen et al. (2017) and Cong et al. (2020) proposed variance reduction stochastic training frameworks that maintain a cache for the intermediate embeddings of all nodes. This can improve convergence but results in large memory requirements, stretching the capabilities of GPUs when training over large graphs. Due to this drawback, we do not consider such approaches in this paper, but it is intrguing direction for future work.
Most existing graph neural network papers do not clearly address how they set the batch size. Ex- perimentally, we observe that batch size is a critical syper-paramett and can significantly influence training time and test accuracy. The importance of the batch size has been recognized for non-graph deep learning models. Keskar al. (2016), He et al. (019)) and Masters & Luschi (018)) have shown that smaller batch sizes, in the range (4, 16,.., 512). can achieve better generalization per- formance. The randomness of small batches proves beneficial. McCandlish et al. (2018) suggested that the batch size should be selected so that a balance is achieved between the "noise" and "signal" of the gradient. Radiuk (201)) showed that using larger batch sizes, of the order of 1024, can be beneficial when training convolutional neural network models. Gower et al. (201)). Alfarra et al. (2020), and [Smith] (2018) introduced adaptive batch size approaches further improve the con- vergence rate and generalization performance. To the best of our knowledge, no existing work has directly addressed the selection of the batch size for stochastic training for graph neural networks, and the objective of this paper is to fill that gap and provide guidelines for the GNN setting.
PRELIMINARIES
We represent graph G EV) with set of nodes V = (t....., )n and set of edges E (c1,..., eM. by an adjacency matrix A E R==x. For node E V. we let N(v) be the set of neighbors of In addition, X E R be the corresponding feature matrix. Let D be the degree matrix of the graph G, where D..:- Σj Aij and Drjj if i A j. To ease the presentation, we use symbols such R T to denote that there exists absolute constant such that R & c.
associate each node to feature vector &. RIxP, and let
2

---

Under review as a conference paper at ICLR 2020
3.1 GRAPH NEURAL NETWORK MODELS
Graph neural networks (GNNs) can be applied to node prediction, link prediction and graph pre- diction tasks. In this work, we focus on the node prediction task. We are given labels of nodes from a training set and we need to predict the labels for nodes in a testing set. One paradigm for solving this problem is to learn representations for all the nodes and then map the representations to labels. Graph neural network aggregate the representations of neighbors into each node in order to integrate the graph structure into each node's 's representation. Specifically, let H' R be the representation for layer I, where the 1dh row hi is the representation for node i at layer / and F' is the dimension of the representation (H1 is set as the original node features X). The forward propagation for hidden states are defined as:
H = o (H) and H++1= = WH'W
(1)
where W E ==** are trainable parameters, o(-) is an activation function, and À is normal- ization of adjacency matrix A, e.g., the random walk normalization Á A= DD11A A, or the symmetric normalization D-1/2 AD 1/2, The equations in and
1 can be expressed for each node i as:
htt1 = a(h!t))
h
Σ JEN()
Aggh.'
(2)
3.2 STOCHASTIC TRAINING FOR GNN MODELS
Sampling in training GNNs: Label sampling and neighbor sampling. In conventional deep learning models, every sample in a mini-batch contributes independently to the approximated gradi- ent. Including more samples thus reduces the variance of the gradient estimate by statistical power. However, in GNN models, samples in a mini-batch are no longer independent. In fact, we have two different concepts of sampling. First, sample mini-batch of nodes in the training set and we call this label sampling. Since the representation of nodes also depends on neighbor nodes, the receptive field for each selected node grows exponentially as the number of layers increases. Neighbor sam- pling is adopted to constrain the number of receptive neighbor nodes. Existing frameworks use three main approaches to handle sampling for GNNs: node-wise, layer-wise and graph-wise sampling.
Node-wise sampling. Hamilton et al. (017)) and Ying et al. (0018) adopt uniformly random sam- pling of the labels. For neighbor sampling, they recursively sample a certain number of neighbors for each layer. Specifically, to evaluate the aggregation for layer [+ 1, for each node i, a set of nodes
S is sampled from the neighbors of node i, and equation ( evaluated
IN Σ Aghh.w
1111
jESt
|S]] is predefined to limit the sampled nodes, but the size of the receptive field for each included mini-batch node still grows exponentially as the number of layers increases.
Layer-wise sampling. Chen et al. (2018), Huang et al. (00 (011)) Zou et al. (2019) propose different neighbor sampling method to reduce the number of receptive nodes. Nodes are sampled at the layer level instead of the node level. Importance sampling is adopted to reduce the variance of sampling and further improve convergence. Specifically, given the set of sampled nodes 5 in layer 1 1+1 1, nodes in layer are sampled with some probability distribution (i)s(++1 that is derived from minimizing variance of gradients [Cen et al. (2018). where i is the index of the node. For brevity, we denote the sampling distribution as (())). From Chen FromChen
al. (2018) and Zou et al. 20119)
the forward propagation in equation is defined as:
A M.W.
I
Note that by controlling |S the number of receptive nodes only grow linearly with respect to layer size. In this framework, uniformly random sampling is used for labels.
Graph-wise sampling, Zeng et al. (2020) and Chiang et al. (2019) propose graph-wisc sampling. This can be regarded special case of layer-wise sampling, which uses the same set of nodes as
3

---

Under review as a conference paper at ICLR 2020
both the sampled labels and sampled neighbors across all layers. Importance sampling is adopted in Zeng et al. (2020) and normalization is applied on both loss and neighbor aggregations to obtain an unbiased estimator for the gradients.
Since in practice, layer-wise wise sampling and graph-wise sampling are much more efficient in practice than node-wise sampling, we focus on the influence of the batch size for layer-wise sampling and graph-wise sampling. For layer-wise wise sampling, the number of included label samples (the batch size) can differ from the number of neighbours sampled at each layer. In our analysis, focus on the case where these values are equal; see the supplementary material for further discussion.
4 BATCH SIZE SELECTION: THEORETICAL ANALYSIS
When we use SGD training, we sample small proportion of samples to approximate the true dis- tribution of samples and estimate the gradients. In the non-graph setting, samples in the mini-hatch contribute (approximately) independently to the estimates of gradients. In GNN models, the impact more complicated, because node representations are derived using sample of the neighbor- hood. If all nodes were included, node's representation would be calculated based on its entire neighborhood; for small batch sizes, only a few neighbours are included, and the approximation of the aggregation can be very poor. This propagates through the layers leading to highly erroneous gradient estimates. In this section, we consider the selection of the batch size for layer-wise and graph-wise sampling in GNN training and derive guidelines. Our approach to analyse metric which captures both the variance of gradients and compute time for training mini-batch.
4.1
VARIANCE GRADIENT AND VARIANCE ESTIMATOR
The essential goal of sampling in SGD is to approximate the gradients. We aim to obtain an unbiased approximation and minimize the variance of the gradients each mini-batch. Recall the definition of the activation of node from (2) and let L be a loss function. By the chain rule, the gradient with respect to the variables layer 1, when all nodes are included (i.e., no sampling), is:
OL OWi
1
Σ SEV++1
aL ah!
OL Oh THT iEVi+1
Σ
Σ Aggh/.
(5)
V++1
ah
OW
[I+I
JEN())
where V denotes the receptive nodes in layer I. Under layer-wise sampling, the gradient can be expressed as:
OL
aL a
Agj 1
(6)
OWe
S4+1
JES
where St and St++1 are the sets of sampled nodes for layer I and layer 1+ respectively. Since hi is evaluated recursively on the samples of former layers, it introduces more randomness and analyzing the exact variance in general is difficult. Instead, we analyze intermediate estimators, with the view that these can act as valuable proxy for the variance of gradients.
Asy h/ is used the proxy estima- In most existing work, the neighbor aggregation terms Ejes' [
tor (Chen et al. 2018: Huang et al. 2018 Zou et al. 2019 Zeng et al., 2020). This proxy estimator the gradients for the variables in layer is highly related to the nodes sampled in both layer 1 + 1 and layer 1. To ad- dress this issue, we analyze a different estimator which considers the randomness arising from two consecutive layers. Specifically,
does not adequately capture the correlation between layers. The variance
consider the analysis of the following estimator.
Let S1. S2 S V such that each vertex in V is selected to S₁ (respectively S2) with probability p (respectively q). For weight matrix W. we define our estimator as:
Definition 4.1
E
1
IN(U)SS (C))
Σ
A W Bur
Si
S2
DES1
WEN(s)
where 1z is the indicator random variable for the event 7.
4

---

Under review as a conference paper at ICLR 2020
4.2 PSEUDO PRECISION RATE
In practice, one of the major purposes of sampling is to improve training efficiency and reduce the time for training the model. Existing methods only aim reduce the variance of the estimators and do not take the computational cost into account Chen et al. (2018): Huang et al. (0188: Zou et al. 2019 Zeng al. (2020). When we evaluate the impact of batch size, larger batch size will gen- erate better approximation of gradient, but this comes at the cost of significantly more computation. Therefore, we need a better metric that can better capture the trade-off between variance reduction and computation cost. McCandlish et al. (0118) propose metric that balances the noise scale and gradient value each minibatch to determine the optimal batch size, but does not explicitly model the computational cost in the metric. In the context of variance reduction for Monte Carlo sampling, Owen (2013) introduces an efficiency metric for an estimator. If there a reference estimator that has compute time co and achieves variance oi then the efficiency of an alternative estimator with coog variance of and compute time C1 is defined as clo+"
Normalizing compute time so that the reference
estimator satisfies Guol = 1, we derive the metric 1
cgt, which we call the pseudo precision rate:
Definition 4.2 Let& & be an estimator with computation cost c > O and variance o² > 0. then the pseudo precision rate of & is defined as
p Ca2
Intuitively, this metric characterizes how much we can reduce the variance per unit computation time. By maximizing the pscudo precision rate, we can achieve balance between variance reduc- tion and computational cost.
4.3 GUIDELINE FOR BATCH SIZE
We derive the guideline for selecting batch size by analyzing how the batch size influences the pseudo precision rate the estimator & in Definition 4.2 The computation cost e defined as the computation cost for training the model over the minibatch. This is approximately constant times -d, since we have to aggregate the neighbor information for nodes sampled in SJ and S2. We derive a lower bound on the pseudo precision rate p(ε) and observe that this bound converges to some value Φ (G, ........ Te.) - R which independent of the batch size. Therefore, for any batch size n, there is monotone decreasing function 5(m) such that P(E) w(1+5)- The proof of the following proposition is provided the supplementary material.
Proposition 4.1 Let À xx be the normalized adjacency matrix of graph G (V, E) with minimum degree dinin > log n, and suppose that max,,ueV |Au O(1) and for each u E V the attribute I, = (1). Let S₁ and S2 be two random sets such that for every E {1,2}, every v E V picked to S, with probability m/n >> log n/ dmins so that Es, [[:]]
Let & be the estimator from Definition O(1). Then there exists & (G, Tey
4. where W is some weight matrix with max,,u u W
Fee. ) TR. and monotone decreasing function
2d Σ EO.u)E [N())
5(m)
(8)
m.
such that for every <, n. the pseudo precision of is
p(E) Z (6(1 + 8(m)))
where d is the average node degree of the graph G.
Note that for simplicity of the presentation, we assumed that the layers are the same size and that all the attributes 2 are scalars. The bound can be generalized to any dimension by summing the variances of the individual coordinates of E
Remark 4.1
From the expression above, 5(m) decreases, so that for any accuracy 8 >> 0, there exists some m such that the pseudo precision at least 1/(0(1 5)).
that the bound on the pseudo precision converges to 1/ as
5

---

Under review as a conference paper at ICLR 2020
Table 1: Datasets statistics.
Dataset
Nodes
Edges
Avg deg
Features
Labels
Train/Val//ee Split
Pubmed 19,717
44,338
4.5
500
3
0.6/ 0.2 /0.2 0.66/ 0.1 /0.24 0.53/ 0.17 /0.3
Reddit 232,965
11,606,919
100
602
41
Ogbn-arxiv 169,343
1,166,243
14
128
40
Ogbn-products
2,449,029
61,859,148 140
50
100
47
0.08/ 0.02 /0.9
Table 2: Hyper-parameter setting and our suggested optimal batch size scale.
Dataset
Hidden size
Batch size test
Optimal batch size scale
Pubmed
128
512, 1k, 2k, 4k, 8k, 16k, 32k, 64k, full
4k
Reddit
128
512, 1k, 2k, 4k, 8k, 16k, 32k, 64k, 128k, full
2k
Ogbn-arxiv 256
512, 3k, 6k, 12k, 24k, 48k, full
12k
Ogbn-product 256
512, 12k, 24k, 48k, 96k, 128k
48k
Although the expression for 8(m) hard to parse in general, we show that for d-regular graphs (i.e.,
all degrees are d), Proposition 4.1 yields simplified bound 8(m):
Corollary 4.2 Let G (V, F.) be a d-regular graph. There exists @ (G, F + IR, such that for any 5 > 0 there exists m 6) = (n/d8)) for which
1
p(E) 2 6(1 +
For practical purposes, although the graphs deal with not d-regular, we propose set the batch size to approximately n/d, where d is the average degree of the graph. The intuition behind this guideline is that with this choice the bound the pseudo precision rate reaches 1/2 of its maximum value. Beyond this setting, there are diminishing returns - the required compute time is increasing, but the variance has been reduced sufficiently so that additional decreases do not improve accuracy.
EXPERIMENTS
5.1 EXPERIMENT SETTING
We evaluate our theoretical findings regarding batch size selection using three state-of-the-art al- gorithms: ClusterGCN Chiang al. (2019) (graph-wise sampling), FastGCN Chen et al. (2018) (layer-wise sampling) and GraphSAINT Zeng et al. (2020) (graph-wise sampling). We test each of the above algorithms against four public datasets: Pubmed, Reddit, Ogbn-arxiv and Ogbn-products Hu et al. (2020). The statistics of each dataset are shown in Table Despite the different statistics among different datasets, can evaluate the optimal scale batch size from our theoretical result, which is shown in Table 2 For Pubmed dataset, we repartition the data with a train/ htti//vaiiaaion/testt split ratio of 2 We keep the original partition for the remaining datasets. For all the tests, we use 3 layers of GCN. We use adam optimizer with an initial learning rate of 0.01 and the default values for remaining hyper parameters. For Pubmed and Reddit, we run training for 100 epochs. For Ogbn-arxiv and Ogbn-products, we run training for 200 epochs. We use "node" sampler in GraphSAINT. The remaining settings are shown Table 2
For ClusterGCN and GraphSAINT, we conduct our experiments based on their published github repositories. For FastGCN, we implemented a version that can utilize GPU computation. All of our experiments are tested server equipped with NVIDIA Tesla V100 GPU (32GB memory), and Intel Xeon Gold 6140 CPU (2.30GHz).
5.2
NUMERICAL RESULTS
Fig. shows the relation between validation accuracy and training time with different batch size setting for various datasets with various algorithms. We also mark the positions that achieves best validation accuracy, 95% of best accuracy and 99% of best accuracy.

---

Under review as a conference paper at ICLR 2020
Table 3: Training performance Pubmed.
ClusterCCN
FastGCN
GraphSAINT
Batch size
Val ACC
Test ACC
Train time
Val ACC
Test ACC
Train time
Val ACC
Test ACC
Train time
512
86.80:10.11
85.63110.48
10.7:14.8
84.77.10.04
84,9310.04
10.7==1.5
86.24:10.16
87.95:10.46
6.8.1333
0..1
86.19410.33
84.62410.11
84.66:0.119
5.342.1
88.134.0.28
87.90:1-0.12
7.9.33.3
2k
0.31
86.35=00.13 13
3.6+0.44
84.73+0.04
84.86=0.233
3.140.88
88.09=0.11 11
88. 08.20=+0.442
5.2+:0.7
4k
87.14:00.12
86.26:1:025
5.1+0.7
85.25-+:020
85.07=0.13
2.1+0.1
88. 88.19:#0.17
08.06+00443
6.5+22.1
8k
86.98-10.114
86. 36.16:10.07
7.320.55
85.55:10.20
85.47:0.30
2.0::0.1
87.57:0.122
87.81:1:0.33
4.3:10.77
full
06.099:00009
86.03=0.166
14.2#0.8
85.79::0.09
85.61
3.3+1.6
86.29:
86. 86.12:::025
6.3+0.3
Table Training performance on Reddit.
ClusteGCN
FastGCN
GraphSAINT
Batch
Val
ACC
Train
ACC
Train
ACC
ACC
Train
512
96.10:1 0.04
95.96.1: 0.04
7524: 36
93.24:10005
93.34:10.088
519:1299
93.64:100.06
93.63:10.10
688 139
Ik
10:10:00.02
95.92.1.0.5
328.1 92
93.57 0.004
93.65.10.04
278.1499
95.13:10.14
94.98.10.16 16
617.1566
2k
16:0300
05.94-10.06
3534
94.17
94.31+0.09
177
95.67.10.05
95.53-20.04
579::999
4k
96.18:00.03
95.99=00.01
281 86
94.67=20.04
94, 94.82:00.03
93:119
95. 95.94::0005
95.97=00.03
530:1-55
8k
96.17:1:0003
06.05--0003
95.04:1:0033
95.14:1:0.04
96.20:100.07
96.14:10:04
516:1:66
16k
96.30.1..04
96.08
291. 83
95.30.1..000
95.43.10..2
45.18
96.35
96.28.10.00
568.116
32k
96.3940.003
96.18:00:01
3401993
95.48-10.00
05.56:10.02
96.44110.03
06.36110.07
64k
96.44..0.09
96.29.10008
390.183
95.6010.02
95.61110.01
75.1
96.53100.3
96.43.10.03
565.100
128k
0.006
96.35-10.06
546:1
95.55
95.56:10.04
119:551
full 96.33+0.07
96.28:00.06
95.47:20.04
95.51+00.44
248::411
The implementation from GraphSAINT will report GPU memory error for the batch size setting of 128 ls and full batch.
Table 5: Training performance on ogbn-arxiv.
ClusterGCN
FasGGCN
GraphSAINT
Batch size
Val ACC
Test ACC
Train time (s)
Val ACC
Test ACC
Train time
Val ACC
Test ACC
Train time
512
70.42.10.06
69.24.10.41
131:1 17
71.7411..16
70.60.10.18
350
61.24:10.18
59.92.10.49
9611:
3k
70.80:10.08
69 0.00033
564:6
12.18:10.07
70.98:10.07
15
63.90:10.11 16
63.1540..10
6k
70.96=00110
69.98:10.31
59 3
72.56=+0.007
71.50=00.00
46:55
65.14=20.11
64.62=0.39
70-:10
12k
71.25:+0.99
70.15:1::24
75::10
72.87:+0.06
71.73+00.09
26:1-6
66.12:40.13
65.8610..20
72:::17
24k
71.38+0007
00.52:+0.17
118+ 20
73.36=00.06
72.27=0.19
22:25
66.78:10.09
66.64=0.11
62=7
48k
71883:0011
70.93:1:0.09
229 30
73.70:+0.005
72.67=0.044
23:1:1
67.48:1:0008
0..5020.32
72-9
96k
0.06
70.67 0.021
191.1.24
12.69
34.14
67.95.10.13
1.028
full
71.72-40.30
70.69-10.21
319: 17
72.84:10.13
71.98.10122
45:16
68.75-1-0.08
68.70-10.25
122.88
Table 6: Training performance on ogbn-products.
ClusterGCN Test ACC
FastGCN
GraphSAINT
Batch size
Val ACC
Train time (s)
Val ACC
Test ACC
Train time (s)
Val ACC
Test ACC
Train time (s)
312
91.11=00006
75.13:50.37
1080:4236
89.24:10002
76.37=0.04
863:1:4
88 09.00:0003
72.82+0.00
3623=353 358
12k
91.30:10.04
75.16:10.155
993-2-407
90.93:1:0007
79.25=20118
83:122
91445:0003
71.57=0.32
1234:::47
24k
91.25
75.23:10.10
1128.1400
91.38.10.06
79.16.10.26
75.18
91.95.10.04
78.76110.33
969
48k
91.02:t: 0.02
75.22:1:0.40
337
91.27-::0.01
77.58=00004
86::55
92.13-100.01
79.52-10.23
930-t: 138
96k
90.60:1:0005
74.72:10.15
407-1:21
90.8111.0.08
76.14.10.33
180::101
92.23:10.07
79.57-10.15
890::98
128k
90.80-10.12
74.70:10.09
408:112
90.72-1.0.04
75.68-10.17
133:1200
92.07-10.09
79.52.10.14
749-
Table Table 4
Table 5 and Table 6 shows the detailed results at the epoch with best validation accuracy for Pubmed, Reddit, Ogbn-arxiv and groductss respectively.
Under the batch size of 256, typical setting for conventional deep learning models, all the scenarios show a slow convergence rate and a bad validation/test accuracy. When the batch size increases, both the training efficiency and testing accuracy improve substantially. The reason is that the accuracy of neighbor aggregation rapidly increases when batch size is small. For FasIGCN and GraphSAINT, testing accuracy will increase as increase the batch size. However, there is some turning point in each dataset, beyond which the testing accuracy does not increase too much. This confirms our theoretical conclusion about diminishing returns. Reddit is a typical example where testing accuracy is boosted to batch size of 8k and beyond that value, it grows slowly. On the other hand, there is sweet-spot for the fastest convergence rate, not necessary aligned with the turning point of testing accuracy. Above sweet-spot, variance of gradients in each minibatch does not decrease too much as batch size grows but computation cost keep increasing. Below the sweet-spot, rapid reduction of variance results faster convergence. Our suggested scale of optimal batch size usually falls close to those two important points. For CluserGCN, the testing accuracy does not change too much, but the sweet point for convergence is close to suggested optimal batch size too. In general, guideline suggests some batch size that is much larger than conventional batch size setting like 512 and it is close to the spot where can get decent testing accuracy with efficient convergence rate.

---

Under review as a conference paper at ICLR 2020
0.9
0.90
Validation accuracy
Jalidation accuracy
Validation accuracy
Pubmed
0.8
0.85
0.825
0.7
0.800
0.80
0.775
0.0.0
0.75
2.5
5.0
7.5
10.0
12.5
15.0
0
2
6
8
10
2
10
12
Training time
Training time (s)
Training time (s)
Validation accuracy
0.96
0.950
Validation accuracy
Reddit
512
0.925
51.
0.9
Validation
0,900
16k
0.8
0.875
64t
30k
16k
32K
64k
0.90
0.850
0.7
50
100
150
200
250
50
100
150
200
200
400
600
800
1000
Training time (s)
Training time
Training time (s)
0.75
Validation accuracy
0.70
Validation occuracy
Validation accuracy
ogbn-arxiv
0.65
0.65
0.70
6k
0.60
0.60
12k
24k
0.65
24k
0.55
48k
0.55
4Bc
96k
0.50
0.50
50
100
150
200
250
300
20
40
60
80
100
50
100
150
200
Training time
Training time (s)
Training time (s)
accuracy
Validation accuracy
Validation accuracy
0.92
ogbn product
0.90
0.90
0.88
512
24k
12k
0.88
0.80
24k
12k
0.86
0.86
96k
48k
0.75
96k
128k
128k
0.84
200
400
0.84
0.70
500
750
1000
Training time (s)
Training time (s)
Training time (s)
(a) ClusterGCN
(b) FastGCN
(c) GraphSAINT
Figure 1: Training time v.s. validation accuracy with different batch size settings for various datasets
with various algorithms. *: best validation ACC (BA), Q: the first reach of 0.95 BA, or the first reach of 0.99 BA.
Interestingly, on Reddit Mataset[Chen et al. (2018) : Zou et al. 2019); Zeng et al. (2020) Chiang et al. (2019) report that graph-wise sampling (testing accuracy 0.96+) performs much better than the layer-wise sampling (testing accuracy of around 0.93). We found that the difference mainly comes from the fact that experiments in graph-wise sampling have better batch size setting (8k in Graph- SAINT) while the layer-wise experiment set small batch size (400 in FastGCN), In our experi- ments, when we properly set the batch size, performances from layer- wise sampling and graph -hihhwiiee sampling are close, which indicates the importance of batch size selection in GNN training.
CONCLUSION
We studied the batch size selection for SGD training of GNN models. We proposed pseudo precision rate metric that reflects training efficiency. We analyzed how the batch size influences this metric on an estimator that considers the randomness arising from two consecutive layers in GNN. By extensive experiments, we show that the batch size for GNN models should be much larger than
8

---

Under review as a conference paper at ICLR 2020
..... 512] from conventional deep learning models. With suggested scale of batch size n/d, n being the total number of nodes and d being the average node degree, GNN model can achieve decent testing performance efficiently.
typical setting of {4. .6...........

---

Under review as a conference paper at ICLR 2020
REFERENCES
Motasem Alfarra, Slavomir Hanzely, Alyazeed Albasyoni, Bermard Ghanem, and Peter Richtarik.
Adaptive learning of the optimal mini-batch size of sgd. arXiv preprint arXiv:2005.01097, 2020.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference Machine Learning, 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 10247, 2018.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pD- 257-266, 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sam- pling with provable guarantees for fast training of graph neural networks. arXiv preprint arXiv:2006. 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, pp. 3844-3852, 2016.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:7810.0480) 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proc. Int. Conf. Machine Learning. 2017.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. arXiv preprint 1rXiv:1901.091 2019.
Alex Graves. Generating sequences with recurrent neural networks. arxiv preprint arxiv: 1308.0850. 2013.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, pp. 1143-1152 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 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.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609 04836,, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint vrXiv:1412.6968 69800, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1009.00999.00 2016.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276, 2019.
10

---

Under review as a conference paper at ICLR 2020
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. In International Conference on Machine Learning, 2020.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Thirty-second AAAI conference on artificial intelligence, 2018
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song. and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4424 4431, 2019.
Dominic Masters and Carlo Luschi. Revisiting small batch training for deep neural networks, arXiv preprint ar 1rXiv:/804..00 07000000..2..... 2018.
Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAl Dota Team. An empirical model of large-batch training. arXiv preprint arXiv:1812.06/2 2018.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pp. 5115- 5124, 2017.
Art B. Owen. Monte Carlo theory, methods and examples. 2013.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov neural networks. In Proc. Int.
Conf. Machine Learning, 2019.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training, 2018.
Pavlo M Radiuk. Impact of training set batch size on the performance of convolutional neural networks for diverse datasets. Information Technology and Management Science, 20(1):20-24, 2017.
Leslie N Smith. A disciplined approach to neural network hyper-parameters: Part 1 l-learning rate, batch size, momentum, and weight decay. arXiv preprint arXiv:/80. 000188803000000 2018.
Shikhar Vashishth, Prateek Yadav, Manik Bhandari, and Partha Talukdar. Confidence- based graph convolutional networks for semi-supervised learning. arXiv preprint 10Xiv:190..08255, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
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. In International Conference Learn- ing Representations, 2020. URL htttts:://ppeeeeet///////
net/ wttp://ormmmmddeeeppeeeeee
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for cemi-supervised classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5829-5836, 2019.
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. 11247-11256 2019.
11

---

Under review as a conference paper at ICLR 2020
A BATCH SIZE ANALYSIS
In this section, we prove Lemma 4.1 and Corollary 4.2
We start by stating straightforward lemma from probability theory, whose proof is a direct appli- cation Chernoff bounds.
Lemma A.1 Let U be finite set, and consider random set S U drawn such that each element in U is picked to S with probability p independently. Then, with probability at least 1 - p
p|U1 v p|U| v / [S]
log
For fixed vertex u, we let v. Wa Tus so that our estimator
1 NN))
E
Auςu Z.
S1
"EN(v)n82
Note that we considered the more general case where is picked according to probability m1/n and S₂ is picked according to probability m2 n.
We start with the proof of Proposition 4.1
Proof of Proposition 4.1;
We start with computing the mean of our estimator.
uu
Xu
S1,82
[
St. S2
[S
(C
ns
DES1
rESt
wEN(v)nS2
An,
E
Loes, IN(N)SS70 IuESonN(o)
S S2
[S1]
S2 n [())
V.VVV
Σ
E S1.52
LUES
LuES2 [N(
Au
S1
(o,a)EE
where for an event Z we let 17 denote the indicator random variable for Z.
Note that by the fact that each vertex is picked to S1 (respectively S2) independently w.p we can apply Lemma A. and conclude that with very high probability [$1] = pm /pn log = (pm)
By the independence of S1 and S2, and an application of Jensen's 's inequality, we can establish the following bound:
E LvESs 1ues, S1.²
1.ES,
1
E
E S2
20
[SI]
[N())
[S
[
leading to mean of Ω (+
( E(.a)E
A.uuuu [NV
Next, we compute the second moment of our estimator.
E
Xei "1
S1
11
Σ
m Tu An Fas Ang ueg Twus
S1
1
N(e)) S2
(vs (22
Σ
1 1n ug
Agy uy Beg Auz Rug-
S1.S2
|1 av, avy (N())) n S ((())
Similarly to before, we inspect the above expectation. In here, there are four cases corresponding to the following sets.
12

---

Under review as a conference paper at ICLR 2020
1. C1 {U1, u1), (22 u2)
E
U2, U1 # U2 in similar way to before, by #
Lemma A.1
we obtain
p
1 10,
S1.92
1
(N(w)) S2 ((2)) n
(pn)² S2
n S2
p²q²
(pn)² S2
(1) n (2 n nS
In order analyze the above expectation, consider the random variable |S n (u:)) (the case corresponding to IS n (N2)) is identical) and note that
S()((e) = (S n (v)) \ ((v,, e2)))) U(s o2)), and in particular, the sets (v1) \ (e1, 12) and (u1, 22) are disjoint so that [S:) ( (N(m) \ N(m, o2)) |S n (2).
Now let's analyze each of the following terms separately. By applying Chernoff bounds (Lemma A.I we get that with probability at least ((1/poly(n) we have that
n (N()) \ (ei, 02)) (l)((o)) \ (N1,, u2)] + / (wi) \ (Vi,, log log
( 12)] = ( 12) = V9l,V(u1, 22) log n.
Which implies that,
(S:N() g(N((1)) N(11, 02)1 + q ((), 02) + v ( u2) log + V q) (11, U2) log [v)N(v)) + (V log (v (w1) ((),, 02) + v vN((1, (2),
S < /22/ (vi))
where the last inequality follows from the fact that q > log n/ /mmi- which makes the first term the dominant one.
Now, with this at hand, can union bound over U1 and and get that with probability at least o(1 (/ppooyy)n)
1
S
p(N((1)) (2
so overall
S1
(2)))))))) (1) ns
n ( IN(22)
2. C2 = ((V1, 41), (U2, u2) E E # 02, = w2): similarly to the previous case,
1 ms,, 1 ugES
E
S 2 (S nS
qn ((1)))))))))
3. C3 = (111 (U2, u2) E V1 = U2 41 # u2). This case requires extra care, since in this case, the neighborhoods of 02 and are correlated (actually the same).
1 PsES, 1 22E3,
2q²
E Si S²
E
| 2 (N1) n (2)) n nS2
(pm)²
[N
n S2
By Lemma A.I
with very high probability
(e)) S2 [g([ log. v (1))
and by our constraint that 2(log m/dmmn)) = 2llog///oo/ (v))l.. we have that with high probability
Sp
S2
(g)N(()) + V (N)
(2)
so that
pq²
(pn)²
N())
pn2|
13

---

Under review as a conference paper at ICLR 2020
4. C. U11, (u2, u2) E E 02, u1
uz). Similarly to the previous case,
12E, wus.
pq (pm)²
E
E
Sr
S 2
N2))2
Combining the above and subtracting the expectation squared yields,
An, A uyg. 52 ((t))
Vars..2
X
E
S1
n2a
oES1
(19,01)
1
A un Tu. Au, u2
1 n
Σ
A T v.a
1 Σ
Au [N(w)]
n22 (Gs
[Q)
(V.a)EE
After rearranging we get
(
Σ
[N(ei)]N((22] Aer Aro
n?
(IN(()))INN)))))
U2))
Σ
A Avr Da, un Buz +
Σ
P|N(v))
[N(2)
[N(6)]
(0) (22
(C,u)EB
If we let m1/n and q m2/n so that Es, [[S]]] mı and Es,1[S21| m2, get that
Vars
[S1]
BESi
A Agy Aug Lu
Am un Tuz Anr Tug
Σ
Σ
n
(
P|N(1))2
Pg
(NAJEE
Åv À Apg.e 22
Ā Ån Jay Art.wg
Σ
Σ
nm2
[No2)
[1 -
[N())
(9))
A 2
Σ (..))E
mi m2
[2)
Note that the variance decreases as m., m2 increase. Therefore, we assume for simplicity that m2 m the variance is bounded by
Am Av Pu
A Bu, Av, ug Pug
Vars, S.2 [5] - nm
Σ EC,
Σ
[N(2)]2
(01,0)))
Σ (V,))E
1 m2
À?
(10)
[N())]
Let's consider the pseudo precision of our estimator. Note that the cost generating the estimator approximately 2m d, where d the average degree of the graph. This since we have roughly 2m vertices to generate and for each vertex sampled we need to aggregate its neighbors information (which is approximately d).
2d
Åon Agz.u Z2
Åny Tuy An Twz
p(() (Var(g) Cost(E))
Σ
Σ
[N(2)]2
(1
2d
12 2 x2
(11)
m
[v)
14

---

Under review as a conference paper at ICLR 2020
Let
2d Φ
Any ay A Anzan 22
Auy Buy Au ung Fuzz |N(v)]2
Σ
Σ
n
(22,
and note that as m increase, the efficiency converges to ø. we define
A S 2d Σ (U,N)E [N(O]]
5(m)
(12)
we get that ((E) 2 0(1+8) as claimed.
Now we show that if we assume that the graph d-regular, we can get a clean relation between the efficiency of estimator and the size of the batch.
Proof of Corollary 4.2 Fix any >> 0. By Equation
12
2d
(D.U)EE [W(2]
5Φ
so that the pseudo precision is at least
p(E) 2 (6(1 + o(m)))
By assuming that the graph is d-regular, and using the definition of
2d Σ
Σ 1/df
(U,))E
[
m7
25d Eer MV)i))
Ec, [+)
Ec, 1/d2 + Ecs 1/d2
nd/2
n
n (1) + (2)
=
d6
B ADDITIONAL EXPERIMENT RESULTS
To better demonstrate the results shown in Table 3 Table 4 Table 5 and Table 6 we create the box
plot for training time and testing accuracy for different batch size settings in Fig. 2
15

---

Under review as a conference paper at ICLR 2020
Test acc.
Train time
Test acc.
Train time
Test acc.
Train time
0.865
15
0.860
12.5
Pubmed
Train Time (s)
10.0
0.88
12.5
0.860
10
Test acc.
0.855
7.5
Train Test acc
10.0
Train Time
Test
0.855
0.850
5.0
0.87
7.5
0.850
0.845
2.5
0.86
5.0
512
1K
full
512
1k
2k
4k
Bk
full
512
1k
4k
full
Batch size
Batch size
Batch size
Test acc.
Train time
Test acc.
Train time
Test acc.
Train time
0.964
800
0.96
Reddit
Test acc.
0.962
600
Time
Test acc.
0.95
400
Test acc.
800
Train Time
0.960
400
0.94
Train
600
0.94
512
8k 16k 32k 64k128kfull Batch size
512
2k
4k 8k Batch size
512
4k
8k
16k
32k
64k
Batch size
Test acc.
Train time
Test acc.
Train time
Test acc.
Train time
0.675
120
300
agbn-arxiv
Test acc
0.70
Train Time
Test acc.
0.72
Train Time
100
Time
200
0.625
0.69
0.71
0.600
512
12k
24k
48k 64k
512
12k
24k
48k
96k Full
512
3k
6k
12k
24k
48k
96k full
Batch
Test acc.
Train time
Test acc.
Train time
Test acc.
Train time
0.760
0.80
4000
oghn- product
1500
0.79
800
Train Time (
0.78
Test 30
0.755
Test acc.
0.78
Train Time
Test acc
1000
0.76
0.77
400
2000
0.750
500
0.76
200
0.74
1000
0.745
512
12k
24k
48k
96k
128k
512
12k
24k
48k
96k
128k
48k size
96k
128k
Batch
Batch size
(a) ClusterGCN
(b) FastGCN
(c) GraphSAINT
Figure 2: Box plot for training time and testing batch size.
16


Reviews:
[{"review_id": "xFB4RlqwqAT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The goal of the paper is to propose a principled strategy to select batch size for training graph neural networks with SGD. Training (using GNNs) real world graphs with a large number of nodes/ edges may not always fit in CPU /GPU memory, hence constructing mini-batches is important. Specifically, the authors propose a strategy for the task of node classification - where they aim to select batch size based on number of nodes and average degree in a graph and show that their proposed guidelines have benefits in terms of training time as well as accuracy. The authors propose a metric - pseudo precision rate which is dependent on the computation cost and the variance of the gradients and derive a lower bound for this metric which factors into account the batch size.\n\nPros:\n1. The idea to study the effect on batch sizes for non -i.i.d data is interesting\n2. Authors provide results on 3 large number of datasets  for 3 scalable GNNs\n\nConcerns:\n1. (Learning rate) - There have been lots of work which understand the connections between learning rates and batch sizes - their impacts on rate of convergence, local minima reached, variance in the gradients etc. In this work the authors use the same fixed learning rate for all batch sizes (which goes against many previous works without justification for the same).\n2. (Confidence Intervals/ number of epochs) - The values presented in Tables 3-6 do not have any confidence intervals - with values which are so close of each other - it is crucial to have confidence interval. Also the authors use a fixed number of epochs for each of the batch sizes to compute training time - this is problematic  - the training time should only be considered up to the point it converges (for e.g. with early stopping).\n3. (Clarity) - Section 3.2 What is $S_i^l$, $q^l$ - mathematically? - This is not clear from the text in the paras (vague) - Can you express S in terms of the k-hop neighborhood, is division by $q^l(i)$ well defined in equation (4), etc. Paragraph above - def 4.1 - \" Proxy estimator does not adequately...\" - what do you mean by this statement - the word 'layers' refers to what? Please see other concerns below as well\n4. (Estimator and bounds) - From the text, it is unclear how the estimator in definition 4.1 is connected with the variance of the estimator and the computation costs used in definition in 4.2 . This flows into the proposition 4.1 and the corollary as well. Many of the computations in def 4.1 can be parallelized - so a clear definition of the variance of the estimator and computation costs are required.\n5. Effect of distributed frameworks - another aspect to consider here - which is crucial to performance is the ability of GNN tools such as DGL an Pytorch-geometric to perform distributed training at scale (model parallel approaches) - this impacts the batch size as well.\n\n\nOther concerns:\n1. Please don't include very generic statements which don't any much value to the reader - like \"SGD performs well when mini-batch size is small\" (abstract and second para of intro) - this is dependent on the task, whether the data is i.i.d etc and also too small minibatches is bad as well. Early graph neural networks clearly showed that larger batch sizes for SGD training was always better (with full batch gradient descent achieving fast convergence as well as convergence to local minima which achieved highest test accuracy).\n2. Typo - para 1 -  intro  - minibatch\n3.  3rd para - (i) reduced instead of reduce (ii) training may take instead of training take\n4. Section 3.1 - classify the labels of nodes\n5. Proposition 4.1 - what is d?? you have defined d_min, but nothing about \n\nIf made more clear and the concerns are addressed, I will be happy to improve my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "uRG8bjXlkhP", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nIn this paper, the authors studied the problem of batch size selection in graph neural networks. Since scaling up the batch size is the most efficient way to increase parallelism, this topic seems to be very important for making full use of modern computer architectures like GPUs or TPUs. The authors conduct a detailed analysis on the impact of batch size in graph neural networks. After a series of discussions, the authors conclude that an ideal batch size should be n/d where n is the total number of nodes and d is the average node degree. The authors suggested that this batch size should be able to give the best convergence/generalization performance for graph neural networks. Overall, the paper is properly written. In terms of presentation, the structure is clear and the idea is easy to understand.\n\nInteresting point:\n\nAs suggested by many previous papers, large-batch training typically suffers a generalization problem found in [1]. However, the results in this paper (e.g. Tables 3-6) show that large-batch training generalizes very well for graph neural networks. For example, a batch size of 32K may make the training crash by using stochastic gradient descent for convolutional neural networks. That seems to be interesting, the authors may need to explain the reason behind that.\n\nMain concern:\n\nIn this paper, the authors did not provide any algorithmic contributions. As mentioned in the paper, the only contribution of this paper is a theoretical analysis. The authors conduct some experiments to support their theoretical analysis. To be honest, I do not find enough interesting points in the theoretical analysis. Considering the experiments are fairly easy to be conducted, the contribution of this paper seems to be incremental.\n\nQuestions:\n\n(1) In Tables 3-6, did the authors fix the number of epochs when they change the batch size?\n\n(2) Can the authors provide more information on optimizers and hyper-parameters?\n\n(3) The horizontal axis of Figure 1 is “training time”, can the authors add another figure with the horizontal axis as “epochs”.\n\nMinor concerns:\n\n(1) In the introduction section, the authors claimed “The maximum size of the minibatch is limited by the available memory”. That’s not true. If the authors have out-of-memory issues with limited hardware resources, please check [2]. If the hardware can run with a batch size of 1, it can run whatever batch size.\n\n(2) The lines in Figure 1 are hard to tell from each other. The authors may consider adding different markers to different lines.\n\n(3) The evaluated datasets/models seem to be small. Even though the authors only use one GPU, they managed to train almost all of them within one hour.\n\n[1] Keskar, Nitish Shirish, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. \"On large-batch training for deep learning: Generalization gap and sharp minima.\" arXiv preprint arXiv:1609.04836 (2016).\n\n[2] https://discuss.pytorch.org/t/how-to-implement-accumulated-gradient/3822\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "s7USH2rCCP", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study an important problem on how the choice of batch size (i.e., the number of sampled nodes) affects the training efficiency and accuracy of graph neural networks (GNN). Focusing on the layer-wise and graph-wise sampling for training, the authors theoretically characterize the impact of batch sizes on the efficiency (measured by a product of computation time and variance) of the algorithms. Especially, in order to better capture the randomness of two-consecutive layers, the authors investigate a different estimator rather than the one truly used in the training of GNN. The resulting theory suggests a choice of the batch size to be n/\\hat d, where n is the total number of nodes and \\hat d is the average degree of the graph. The authors empirically show that compared to the training of NN, the training of GNN requires a much larger batch size to achieve an efficient training. In addition, the experiments show that the best batch size is much smaller than the full batch that is widely adopted in the training of GNN.\n\nStrength: \n\n   (1) This paper studies an interesting and important problem on the selection of batch size for GNN training. The results may be useful for practitioners to accelerate the training for GNN depending on different settings. \n\nWeakness:\n\n  (1) This paper is not well written and some parts can be clearer. For example, from my reading, the layer-wise sampling plays an important role in the analysis. However, It is not directly clear to me about the derivation of equation (4). As a result, I do not get the point of your estimator design in Definition 4.1. Specifically, more intuitions and explanations on the design of your theoretical estimator in Definition 4.1 should be given, and clarify whether this estimator can truly capture the training of GNN, e.g., whether it will change the convergence of SGD during the training. \n\n  (2) The theoretical results seem not to well support the empirical results. For example, the theoretical results suggest some optimal batch sizes given by theory, e.g., 4K for Pubmed, 2k for Reddit, 12k for Ogbn-arxiv, 48k for Ogbn-products. However, from the experiments in Tables 3,4,5,6 suggest that the best choices are 512-1k for Pubmed, 4k-8k for Reddit, 8k for Ogbn-arxiv, 8k-32k for Ogbn-products. There seem to be some big gaps between the theory and the experiments. \n\n  (3)\tIt seems to me that the analysis only studies the two-consecutive layers. However, in practice, GNN often contains far more than two layers. The authors should discuss whether such analysis is still applicable to larger GNN or provide a corollary to present such results. \n\n  (4)\tAssumption  A.1 is restrictive. It requires that the intersection of the neighborhoods of any two points has nearly no correlation. In practice, this assumption is hard to satisfy because the neighborhoods of points always contain big overlaps. I think this assumption is made in order to derive or simplify the analysis. The authors may try another more reasonable and practical assumption or show why this assumption is necessary and practical in some settings. \n\nAlthough I think studying the batch size selection for GNN is very important, I am not convinced or excited by the results in this paper. For me, it is more interesting to provide a better and  comprehensive theoretical result  beyond the simplified case in this paper, or develop a new batch size selection scheme (e.g., adaptation) to accelerate the training of GNN. However, I do not get such points from the current version. For these reasons, I tend to reject this paper. However, since I am not an expert in this area, i.e., GNN training, I am open to change my mind based on other reviews and the authors’ response. \n\n--------------------------------------------------------------------------------------------------------------------------\nPost rebuttal:\n\nI first want to thank the authors for their response to my concerns. My concerns have been partially addressed, but some concerns still exist. For example, I am not clear about whether the simplified theoretical estimator in Definition 4.1 really captures the training of GNN. To achieve this goal, some simulations or theoretical justifications should be provided. In addition, the analysis fails to motivate some useful and meaningful algorithmic designs for GNN acceleration, which I believe is much more interesting. For these reasons, I tend to keep my score unchanged. \n\nHowever, I  think the authors take a very good start in studying the impact of batch sizes for GNN training, and I encourage the authors to further enhance their papers from both the theoretical and practical perspectives. For example, it would be much better to explore some new designs for accelerating GNN training based on the developed analysis (e.g., batch size adaptation). Theoretically, the authors can study a more practical and general estimator (perhaps beyond two layers). With these improvements, I believe this can be a very good paper to be published in top venues. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gg1Yp2wbM_f", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-------------\nSummary\n-------------\n\nThis paper presents analysis how the batch size in GNNs would affect the tradeoff between accuracy and computation cost. The paper defines the gradient estimator for minibatches constructed by layer-wise random node sampling. Then the authors analyze the variance of such estimator in order to guide the hyperparameter tuning on batch size. I think it is an interesting idea to quantify the accuracy-computation tradeoff with the metric \"pseudo precision rate\", $\\rho$ (as mentioned in the paper, $\\rho$ is the normalized efficiency metric (Owens, 2013)). The authors calculate the bound for $\\rho$ and then derive the optimal batch size based on full graph size and average degree. Experiments on three state-of-the-art GNN training methods verify that 1). the batch size for GNNs needs to be larger than that of other models on I.I.D. data; 2). there exists an optimal batch size to balance the accuracy and training cost. \n\n------\nPros\n------\n\n+ Training GNNs to achieve scalability and accuracy at the same time is a relatively underexplored problem. But it is indeed very important. The authors made a good attempt to unify both accuracy and scalability under the pseudo precision rate metric $\\rho$. \n+ The paper is well-organized, and it is easy to grab the main idea. \n+ Extensive experiments have been conducted. These help the readers better understand the training behavior of existing state-of-the-art methods. \n\n-------\nCons\n-------\n\nSince the theme of the paper is to guide the tuning of existing methods rather than proposing new methods, it becomes more critical that the analysis is performed rigidly and under realistic assumptions. However, after reading the derivations carefully, I have the following concerns:\n- Some fundamental assumptions on sampling are inconsistent with the setup of the state-of-the-art training methods. All of the analysis is based on the process of independent and uniform random sampling in each GNN layer (i.e., to construct the set $S_1$ and $S_2$). Unfortunately, none of the existing training methods follow such setup. For example, for GraphSAINT and Cluster-GCN, $S_1$ and $S_2$ are strongly dependent on each other as $S_1 = S_2$. For FastGCN, the sampling in each layer is not uniformly at random due to importance sampling. For other layer-sampling methods (e.g., GraphSAGE, VR-GCN, AS-GCN, LADIES), $S_1$ and $S_2$ are also not independent since the sampling of $S_2$ follows the inter-layer connections defined by $S_1$. \n    * If we remove such unrealistic assumptions on sampling, the derivations in the paper would fail. For example, if $S_1$ and $S_2$ are no longer independent, $\\xi$ would have non-zero bias and then such definition of the estimator is questionable. The bias can be seen from the last equation of page 11 in the Appendix: without independence, $\\mathbb{E}_{S_1, S_2}[...]$ is not equal to the product of $\\mathbb{E}S_1$ and $\\mathbb{E}S_2$. Assumption A.1 is also questionable since nodes in $S$ may have strong correlation depending on the subgraph sampler. Similarly, the derivation on the variance (page 12) would not hold without assuming independent $S_1$ and $S_2$. \n    * Following the setup of this paper, I think independent and uniform sampling of each $S$ may likely cause difficulty in GNN learning. Suppose the max sampling size is $O(1)$, due to the fixed GPU memory capacity. Now with the growth of the full graph size $n$ and under independent, uniform sampling, the probability that $S_1$ and $S_2$ have any connection will vanish. i.e., $1_{N\\cap S_2\\neq \\emptyset}$  in the $\\xi$ definition will almost always equal to 0 with a large enough $n$. The issue of unconnected minibatch will be much worse if we consider the sampling across multiple layers. \n    * Therefore, the analysis on variance gives limited practical insights due to those assumptions. \n- Some important assumptions on the graph property are either unrealistic or not well-justified. The derivation of Propsition 4.1 relies on $m/n >\\log n / d_{min}$. In other words, $d_{min} > (n/m)\\log n$. Let's consider a median-scale graph in OGB with $10^6$ nodes. Suppose the batch size is $100$K (which is already much larger than the one tried in this paper). Then $d_{min}$ is already in the order of $10^2$ --- minimum degree is of similar scale to the avarage degree. Therefore, such assumption is unrealistic, especially considering the power-law. Assumption A.1 is not well-justified. A.1 requires weak correlation between sampled nodes. Such weak correlation probably does not hold for many well-performing graph sampling algorithms (e.g., random walk), where nodes in $S$ should be \"close\" to each other. \n- The conclusion from the main analysis (Proposition 4.1) is confusing. It is stated that $\\delta$ is monotonically decreasing with batch size $m$. It seems to imply that the larger the batch size, the better the metric $\\rho$ (such understanding is also verified by the case study of Corollary 4.2). So shouldn't we simply increase the batch size until we reach the GPU memory limit? Why concluding on $n/\\overline{d}$ instead?\n- The bound on $\\rho$ is too loose to derive the practical batch size value of $n/\\overline{d}$. The process to derive the suggest value $n/\\overline{d}$ doesn't seem convincing. By looking at the bound $1/(\\phi(1+\\delta))$, the authors suggest that setting the coefficient $1/(1+\\delta)$ may be good enough. However,\n    * $\\phi$ itself is not a constant. $\\phi(1+\\delta)$ jointly depend on $m$. Then we cannot simply treat $1/(1+\\delta)$ as an independent coefficient. \n    * Even though we can set the coefficient $1/(1+\\delta)$ to be $1/2$, and thus make $\\delta=1$, it is still far away from concluding $m=n/\\overline{d}$. Recall that in Corollary 4.2, $m=O(n/d\\delta)$ is only describing the order. How can we simply ignore the constants hidden by the $O(..)$ notation? Especially, the derivation in Appendix seems to depend on multiple constants which could be of arbitrary scale. \n\nMinor concern:\n\nThe fact that larger batch size may help with GNN accuracy has already been observed (e.g., check the batch size configuration for the OGB results). The intuitive explanation from variance perspective has also been made in the literature. For example, GraphSAINT idenfieis the sparse connection issue within minibatches and performs additional experiments to study the effect of large batch sizes. Therefore, bringing up the issue of large batch training is not enough to be considered as a major contribution. The much more important contribution of this paper should lie in the analysis portion. \n\n\n---------------------------------------\nRecommendation: Rejection\n---------------------------------------\n\nConsidering the above, I feel that this paper makes limited contribution to deepen the understanding on the effect of batch size for GNNs. \n\n--------------\nQuestions\n--------------\n\nDetailed concerns are listed in the \"Cons\" section. Below is a short summary:\n1. Please justify the assumptions on sampling.\n2. Please justify the assumptions on the graph property.\n3. Please clarify how to derive the $n/\\overline{d}$ value. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers find the problem studied in the interesting. However all of them raise concerns about the assumptions made in the paper for the analysis. Reviewers find the assumptions very limiting and far from the practical training of GNNs. Improving the analysis by relaxing the assumptions further can significantly help the paper. 
Decision: Reject