Locality-Based Mini Batching for Graph Neural Networks
Authors: Johannes Klicpera
Chendi Qian
Stephan Günnemann
Venue: ICLR 2022 Submitted (2022)
Keywords: GNN
graph neural network
graphs
scalability
batching
local clustering

Abstract: Training graph neural networks on large graphs is challenging since there is no clear way of how to extract mini batches from connected data. To solve this, previous methods have primarily relied on sampling. While this often leads to good convergence, it introduces significant overhead and requires expensive random data accesses. In this work we propose locality-based mini batching (LBMB), which circumvents sampling by using fixed mini batches based on node locality. LBMB first partitions the training/validation nodes into batches, and then selects the most important auxiliary nodes for each batch using local clustering. Thanks to precomputed batches and consecutive memory accesses, LBMB accelerates training by up to 20x per epoch compared to previous methods, and thus provides significantly better convergence per runtime. Moreover, it accelerates inference by up to 100x, at little to no cost of accuracy.

Under review as a conference paper at ICLR 2022
LOCALITY-BASED MINI BATCHING FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
A ABSTRACT
Training graph neural networks on large graphs is challenging since there is no clear way of how to extract mini batches from connected data. To solve this, previous methods have primarily relied on sampling. While this often leads to good convergence, it introduces significant overhead and requires expensive random data accesses. In this work we propose locality-basod mini batching (LBMB), which circumvents sampling by using fixed mini batches based on node locality. LBMB first partitions the training validation nodes into batches, and then selects the most important auxiliary nodes for each batch using local clustering. Thanks to precomputed batches and consecutive memory accesses, LBMB accelerates training by up to 20x per epoch compared to previous methods, and thus provides significantly better convergence per runtime. Moreover, it accelerates inference by up to 100x, at little to no cost of accuracy.
INTRODUCTION
Modern neural networks commonly use stochastic mini-batch training to leverage large datasots and accelcrate convergence. This strategy becomes highly non-trivial for connected data, since creating mini batches requires selecting a meaningful subset from the dataset, despite its connectedness. Graph neural networks (GNNs) typically rely on sampling a set of nodes from the graph to resolve this issue. However, graph sampling requires non-conliguous memory accesses, which significantly slows down training for large dalasets. This severely lim- its their applicability to real-world graphs, which often consist of millions billions of nodes.
The main question behind the connected mini- mini-batching problem is: How do we choose the best nodes for constructing the next mini batch? To answer this question, we introduce the concept of primary and auciliary nodes. Primary nodes are those for which we compute a prediction in this batch, typically a set of training nodes. Auxiliary nodes only help with computing the primary nodes' outputs. This distinction allows us to provide a meaningful neighborhood for every node's prediction, while ignoring irrelevant. parts of the graph. Note that primary nodes in one batch can be auxiliary nodes in another batch.
This distinction splits the main question into two parts: How do we choose the primary nodes for a mini batch? 2. How do we choose the auxiliary nodes for given set of primary nodes? Having split the problem like this, we see that most previous works actually only focus on the second question and just choose a uniformly random subset of nodes as primary nodes (Hamilton et al. 2017 Zou al. 2019). However, the nodes in graph are not independent, and better approach can lead to large improvements in runtime.
In this work, we propose one simple answer for both questions: Locality. Choosing a set of locally connected nodes is advantageous both from a computational and a predictive perspective. It allows us to share computation between multiple nodes, keeps memory accesses local, and reduces the mini batch's memory footprint. The predictions of most GNNs already leverage the fact that nearby nodes are more important. Previous works have even shown that incorporating locality improve GNN accuracy (Klicpera et al. 2019b Huang et al., 2021). Batching nearby primary nodes together can create synergies since one primary node can leverage another one's auxiliary nodes.
1

---

Under review as a conference paper at ICLR 2022
Large graph
Partition primary nodes
Subgraphs
Select auxiliary nodes
Figure 1: Locality-based mini batching. The primary (e.g. training) nodes are indicated by pentagons. These nodes are first partitioned into batches, e.g. using graph partitioning. We then use local clustering to select the auxiliary nodes of each batch, e.g. the neighbors with top-k personalized PageRank (PPR) scores. Finally, generate a batch using the induced subgraph all selected nodes, but only calculate the outputs of the primary nodes we chose when partitioning, Batches can overlap and do not need to cover the whole graph
More specifically, we propose to use either graph partitioning node distances to select mini batches of primary nodes, and local clustering to select their auxiliary nodes. We then use the subgraph induced by these nodes as mini batch. See Fig. for an overview of this process. Importantly, these mini batches can be computed priori, and loaded from a cache to ensure efficient memory access. During training, we counteract the effect of correlated mini batches with learning rate and batch scheduling. Overall, our method achieves an up to 20x improvement in time per epoch, with similar final accuracy. This faster time per epoch more than makes up for any slow-down in convergence per step. Its speed advantage grows even further for the common setting of low label ratios, since our method avoids computation on irrelevant parts of the graph. As opposed to most previous works, method successfully be used for both training and inference. It accelerates inference by up to 100x compared to previous methods that achieve similar accuracy. In summary, our contributions are:
Locality-based mini batching (LBMB): A general mini-batching method that works for variety of GNNs and datasets. It substantially accelerates both training and inference without sacrificing accuracy, especially for small label ratios.
We examine the impact of fixed, correlated mini batches gradient estimation, and propose training methods to mitigate these effects.
An extensive and fair experimental evaluation scalable training methods, covering four datasets, two GNNs, and both training and inference.
2 BACKGROUND
Graph neural networks. We consider a graph 9 = E) with node set V and (possibly directed) edge set E. N | denotes the number of nodes, E = the number of edges, and A E R N the adjacency matrix. GNNs use one embedding per node h, E R and edge E(un) R Me, and update them in each layer via message passing between neighboring nodes. Most GNNs can be expressed via the following equations:
h (++) Snode (!) Agg fmgg (h (h (,))))
(1)
VEN.
((+1) (edge(h!! (h (un))
(1+)) h (++)) ((n)))
(2)
The node and edge update functions faode and fedges and the message function fisg can be implemented using e.g. linear layers, multi-layer perceptrons (MLPs), and skip connections.
2

---

Under review as a conference paper at ICLR 2022
The node's neighborhood Nu is usually defined directly by the graph 9 Kipf & Welling 2017). but can be generalized to consider larger or even global neighborhoods (Klippera et al., 2019b; Alon & Yahav 2021 feature similarity (Deng et al.) 2020). The most common aggregation function Agg is summation, but mean, min, standard deviation, and other alternatives have also been explored (Corso et al. 2020 Geisler et al. 2020 Edge embeddings (uv) are not present in many GNNs, but some variants rely on them exclusively
Chen et al. 2019 GNNs commonly use node features X E RRNxF for the inpul embeddings
h but they can also be augmented with positional encodings (You al., 2019 Dwivedi
ett al. 2020 or node IDs (Vignac et al. 2020 See App. for related work in scalable GNNs.
3 LOCALITY-BASED MINI BATCHING
An efficient GNN mini-batching method needs to consider both computational aspects and convergence per gradient step. Previous works have largely been focused on sampling methods that improve GNN convergence, and treated computations issues mostly as an afterthought. By focusing more on computational aspects like memory access times, we can accelerate training by multiple orders of magnitude, and therefore more than make up for any disadvantage in convergence per step.
If we skip details like caching the computational perspective is rather simple: Save many operations and memory accesscs as possible while maintaining a good GNN approximation. When the auxiliary nodes of different primary nodes in batch are shared, we only have to compute their embeddings once and save computation and memory accesses. We therefore aim to group together primary nodes in way that maximizes the number of shared auxiliary nodes. In locality-based mini batching (LBMB), we do this in two steps:
1. Obtain the k most important auxiliary nodes for each primary node. Batch together primary nodes so that the union of their auxiliary nodes is smallest, yielding the primary node partition P..
Select the most important auxiliary nodes Sn for each subset of primary nodes S E P1.
This process yields a single, fixed set of batches. We thus only need to perform it once during preprocessing. We then cache each mini batch in consecutive blocks of memory, thereby circumventing expensive random data accesses. This significantly accelerates training, allows efficient distributed training, and enables even expensive node selection procodures. In contrast, most previous methods select both primary and auxiliary nodes randomly in each epoch (Ying el al. 2018 Zeng el al.; 2020), which incurs significant overhead. Our experiments show that our more elficient. memory accesses clearly outweigh the slightly better gradient estimates gained from re-sampling in each epoch (see Sec. 5). We will next describe the details of LBMB's two main steps.
3.1 PRIMARY NODE PARTITIONING
Optimal partitioning. In this step we are interested in finding the partition Pi with the highest. number of shared auxiliary nodes. Naïvely, we could find P1 by comparing the auxiliary node overlaps achieved by every possible partition. This is clearly intractable since the number of partitions increases exponentially with the number of primary nodes. An obvious way of accelerating this is greedy approach, in which we itcratively put those nodes into a batch that has the largest overlap. Unfortunately, this would still require computing the overlap for every pair of primary nodes. This requires quadratic runtime O(N2), which is intractable for large datasets. We must therefore rely on heuristics to obtain a scalable, well-performingg primary node partitioning algorithms.
Distance-based partitioning. We propose two methods that leverage graph locality as heuristic for effective node partitioning. The first is based on node distances. In this approach we first compute the pairwise node distances between nodes that are close in the graph. A common node distance mcasure in undirected graphs are random walks with restart, or personalized PageRank (PPR) (Page et al. 1998). The PPR matrix is given by
PP aII -(1 (1-aah -1- A)
33)
3

---

Under review as a conference paper at ICLR 2022
with the teleport probability a E [0, The proximity between nodes u and v is then given by I Calculating this inverse is obviously infeasible. However, we can approximate ITPpr with a sparse matrix IiPpr in time (Gda) per column, with error e deg(u) (Andersen et al. 2006). Next, we greedily construct the partition Pt from IIPPr. To do so, we start by putting every node u into a separate batch {u). We then sort all elements in ΠPpe by magnitude, independent of their row column. We scan over these values in descending order, considering the valuc's indices (u, v) and morging the batches containing the two nodes. Finally, we randomly merge any small leflover batches. We stay within a memory constraint by only merging batches that stay below a maximum batch size. Note that the resulting partition is unbalanced. This method achieves well-overlapping batches and can efficiently add incrementally incoming primary nodes, e.g. in a streaming setting. Our experiments show that this method achieves a good compromise between well-overlapping batches and good gradients for training (sce Sec. 5).
1] and the diagonal degree matrix D,, =x Ansdy.
Graph partitioning. For our second mothod, we note that partitioning primary nodes into overlapping mini batches is closely connected to partitioning graphs. We can thus leverage the extensive amount research on this lopic by using the METIS graph partitioning algorithm (Karypis & Kumar 1998) to find partition of primary nodes P.. Note that this approach completely skips step in the above LBMB process. We found that graph partitioning yields roughly a two times higher overlap of auxiliary nodes than distance- based partitioning, thus leading to significantly more efficient batches. However, it also introduces strong bias in batch selection that we found to be detrimental for training (sce Secc. 5). Note that LBMB with graph partitioning is closely related to Cluster-GCI) (Chiang et al.) 2019). However, in contrast to Cluster-GCN our method ignores irrelevant parts of the graph and can obtain overlapping mini batches. This significantly accelerates training on small training sets and improves the accuracy of primary nodes close to the partition boundary.
3.2 AUXILIARY NODE SELECTION
Generalizing influence scores. The goal of selecting auxiliary nodes is to provide a neighborhood for each primary node that is as small as possible but still contains all relevant information. To quantify a node's importance, we can use the inffuence score of node v on node u, [[E u) Σ, T.X.. Shut. For GCN, this influence is proportional to a slightly modified
random walk (Xu et al. 2018). We can thus select the most. influential nodes for GCN by using this random walk landing probability. Unfortunately, different GNNs have different node influence scores, which are often even data-dependent.
To obtain simple method that works with many different GNNs, we generalize the random walk landing probabilities obtained for GCN using local clustering mothods. This is a well-established class of methods for finding meaningful cluster for selected node based on proximity in the graph. Examples include random walks with restart (or personalized PageRank (PPR), label propagation with return probability) (Andersen et al.) 2006) and heat kernel (HK) diffusion (Kloster & Gleich 2014).. Local clustering only relies on the node's local neighborhood, making its runtime independent of the overall graph size and thus massively scalable. Since it is deterministic, we only need to perform its computation once during preprocessing This allows us to use expensive mothods such as p-norm flow diffusion Foontoulakis et al., 2020), or methods that take node features into account. We leave these advanced methods for future work, and rely on basic PPR clustering in this work.
Node-wise clustering. Local clustering methods provide separate cluster for each node, referred to as the "root node". For example, approximate PPR (Andersen et al. 2006) is guaranteed to provide all nodes with a PPR value IPPe e deg(e) w.r.t. the root node To create a batch of auxiliary nodes we can thus compute the local clusters of all primary nodes in batch St and then merge them. If we partition the primary nodes according to their approximate PPR distances (distanco-based, partitioning) and select auxiliary nodes according to PPR clusters, we only need to calculate the PPR-scores once.
Batch-wise clustering. Considering each primary node separately does not take into account how one auxiliary node jointly affects multiple primary nodes. Fortunately, many
4

---

Under review as a conference paper at ICLR 2022
local clustering methods can be adapted to use set of root nodes. For example, in PPR we can use a set of nodes in the teleport vector t instead of a single node, e.g. by leveraging the underlying recursive equation for PPR vector Tppr one-hot, vector in the node-wise setting, while for batched PPR it is 1/|Si| for all nodes in S.. This variant is also known as topic-sensitive PageRank. We found that batched PPR is significantly faster than node-wise clustering, especially in combination with partitioning the primary nodes via graph partitioning. However, can lead to cases where one outlier node reccives almost no neighbors, while others have excessively many. Whether node-wise or batch-wise clustering performs better thus often depends on the dataset and GNN.
(1 - D ATpprr (t) + at. t is
3.3 INFERENCE
In practice, a machine learning model is trained only once, while inference is run continuously once is put into production. Even during training, inference is necessary for early stopping and performance monitoring. However, most previous GNN mini-batching methods only work well for training. These methods thus only have rather limited utility by themselves Locality-based mini batching can be used for inference without any further changes, since it already focuses on the most important auxiliary nodes. It can therefore be used for all steps in the model's life cycle, or be combined with separate method that focuses on training.
4 GRADIENT ESTIMATION WITH CORRELATED BATCHES
Convergence. Partitioning primary nodes based on proximity effectively correlates the gradients sampled in a batch. This might seem ill-motivated from the usual perspective of providing unbiased, low-variance gradient samples sacrilegious even. However, we use every primary (training) node exactly once per epoch. The model thus sees all training labels equally often, ensuring an unbiased training process. Furthermore, there are multiple ways of mitigating the impact of correlated samples. Adaptive gradient descent methods such as Adam (Kingma & Ba 2015) already cope rather well with imperfect gradient samples. We further improve this by adaptively reducing the learning rate when the validation loss plateaus, which ensures that the gradient. step size decreases continuously. The resulting training scheme thus leads to convergence despite correlated samples, as shown in [Sec. 5)
Batch scheduling. While we found Adam with learning rate scheduling to consistently ensure convergence, we still observed downward spikes in accuracy during training. To explain this issue, consider a sequence of multiple mini batches. In regular training every mini batch is similar and the order of these batches is irrelevant. In our case, however, some of the mini batches might be very similar. If the optimizer sees multiple similar batches in a row, it will do increasingly large steps in suboptimal direction, which can lead to sporadic downward spikes in accuracy. To improve convergence we should therefore prevent such sequences of similar batches. To do so, we first quantify batch similarity using the normalized training class label distribution p; = =c//2 E, Cj where e; is the number of training nodes of class i. We then compare these distributions pairwise using the symmetrized KL-divergence, resulting in pairwise batch distance das between batches and b. Based on this, we propose two ways of improving the batch schedule: 1. Find the fixed batch cycle that marimizes the batch distances between consecutive batches. This is a traveling salesman problem for finding the maximum distance loop that visits all batches. It is therefore only feasible for a small number of batches and otherwise must be approximated. 2. Sample the next batch weighted by the distance to the current batch. Both batch scheduling methods improve convergence and increase final accuracy, at almost no computational cost during training.
EXPERIMENTS
Experimental setup. We primarily evaluate two variants of our method: LBMB with PPR distancc-based batches and node-wise PPR clustering, and LBMB with graph partition- based batches and batch-wise PPR clustering. Both variants run in linear time O(N + E). We compare them to four state-of-the mini-batching methods: Neighbor sampling Hamilton et al. 2017). Layer-Dependent Importance Sampling (LADIES) (Zou et. al. 2019
5

---

10a Under review as a conference paper at ICLR 2022
ogbut-arxiv, GCN
ogbn-products, GCN
Reddit, GCN
74
better
Accuracy (%)
92
T2
94
92
70
90
68
88
109
10
10a
10a
10
10a
10a
10a
10"
10
10a
10
ogbn-arxiv, GAT
0g pooo-ppoouuts, GAT
Reddit, GAT
74
96
LBMB, PPR batch.
Accuracy (%)
92
LBMB, graph part.
Cluster-GCN
92
Neighbor sampling
70
90
GraphSAINT-RW
LADIES
68
88 10a
88
10a
102
10a
10a
10
10a
10
10a
10a
10a
ogbriarxiv. GraphSAGE ogbun- products. GraphSAGE
Reddit Graph8AGE
96
Arcuvacy (%)
922
72
94
70
90
90
68
88
10
102
10
10'
10a
10
10
10
10a
Train time (s)
Train time (s)
Train time (s)
Convergence of validation accuracy in log. time. Average and 95 % confidence interval of 10 runs. LBMB converges the fastest 8 of 9 cases.
Figure 2:
GraphSAINT-RW Zeng et al. 2020 and Cluster-GNN (Chiang et al.
2019
We use four Wang et al.
large node classification datasets for evaluation: ogbn-arxiv (Hu et al.)
2020;
2020 ODC-BY), ogbn-products (Wang et al.
2020
Amazon license). Reddit (Hamilton
ct al. 2017 and ogbn-papers1000 100M (Hu et al.
2020 Wang et al. 2020 ODC-BY). While
these datasets use the transductive setting, LBMB makes no assumptions about this and can equally be applied to the inductive setting. We skip the common, small datasets (Cora, Citeseer, PubMed) since they are ill-suited for evaluating scalability methods. We do not strive to set a new accuracy record but instead aim for a consistent, fair comparison based on three standard GNNs: graph convolutional networks (GCN) (Kipf & Welling) 2017 7 graph attention networks (GAT) (Veličković et al. 2018), and GraphSAGE (Hamilton et al. 2017). We use the same training pipeline for all methods, giving them access to the same optimizations. We run each experiment 10 times and report the mean and standard deviation in all tables and the bootstrapped mean and 95 % confidence intervals in all figures. See App. B for further details.
Training. To evaluate training performance we compare how fast the validation accuracy con- vergences for each method. We use LBMB inference since full inference is too slow to execute every epoch, and other approximate methods are either prohibitively slow or less accurate than LBMB. This already demonstrates a major ad advantage of L.MB: It is fast and accurate enough to run inference regularly during training, Fig. shows how the accuracy increases depending on training time. LBMB performs significantly better than previous methods in 8 of 9 cases, converging up to 10x faster. This is despite the fact that we always prefetch the next batch in parallel. Note that GAT is much more computationally heavy than GCN and GraphSAGE, limiting the positive impact of a fast batching method. Computation-come constrrine models are less relevant. in practice since data access is typically the bottleneck for real-world, disk-baser

---

Under review as a conference paper at ICLR 2022
Table Final accuracy and runtime averaged over 10 runs, with standard deviation. "Same method" refers to using the training method for inference, while "full graph" uses the whole graph for inference. LBMB achieves similar accuracy as previous methods when used for training, while using significantly less time per epoch and without requiring expensive full graph inference. LBMB is up to 500x faster than using the full graph for inference, at comparable accuracy. Other inference methods substantially slower less accurate. Note that LADIES incompatible with the self loops in GAT and GraphSAGE.
Time (s)
Test accuracy (%)
Setting
Training method
Preprocess
Per epoch Inference Same method
Full graph
Full graph
ogbn-anxiv,
Neighbor sampling
4.7
70.7+0.2
71.3+0.4
GON
LADTES
0.3
0.62
0.69
71.7+0.2
71.4+0.3
GraphSAINT-RW
0.4
0.42
0.34
68.11002
72.310.2
Cluster-GCN
8.7
0.14
0.14
72.010.1
72.240.1
LBMB, graph part.
14.1
0.14
0.13
72.210.2
72.240.2
LBMB, PPR batching
17.5
0.27
0.16
72.7+0.1
72.7#0.11
Full graph
ogbn-arxii, GAT
Neighbor sampling
4.1
1.97
70.9+0.11
72.1+0.1
GraphSAINT-RW
0.4
1.2
0.38
68.7+0.2
72.6+0.1
Cluster-CNN
7.6
0.69
0.28
69.710.33
71.610.2
LBMB, graph part.
7.7
0.68
0.31
71.020.3
71810.3
LBMB. PPR batching
17.6
1.53
0.98
72.240.1
72.3+0.2
Full graph
2.37
og rebn-arxiix. GraphSAGI
Neighbor sampling
0.3
3.44
1.67
71.100.1
72.0+0.1
GraphISINTTFNY
0.41
69.0++.11
72.2+0.1
Cluster-GCN
8.8
0.15
0.14
71.7+0.1
72.1+0.1
LBMB, graph part.
7.2
0.15
0.13
72.010.2
72.110.1
LBMB, PPR batching
17.5
0.31
0.15
72.410.2
72.410.2
Full graph
130
Neighbor sampling
32
42
433
78.210.2
78.0+0.2
ogbr-product
LADIES
33
22.5
75.9+0.3
79.0+0.4
GCN
GraphSAINT-RRI
20.6
52.6+0.8
77.0+0.3
Cluster-GCN
302
3.7
3.4
76.2+0.3
76.5+0.2
LBMB, graph part.
306
3.5
3.1
76.810.2
77.210.3
LBMB, PPR batching
382
5.5
14.1
77.5++0.2
77.6+0.2
logbn- products loggo--b boggooooobureeee products.
Full graph
1700
Neighbor sampling
33
450
3450
79.140.3
77.240.55
GAT
GraphSAINT-RR
35
140
69.5+0.11
80.8+0.2
Cluster-GCN
626
10.6
76.610.4
78.1100.5
LBMB, graph part.
767
25
10.0
77.010.4
78.910.6
LEMB, PPR batching
378
41
94
79.3+0.33
79.4+0.3
Full graph
88.0
GraphSAGI
Neighbor sampling
31.4
52.0
530
81.0+0.2
81.4+0.2
GraphSAINT-RRV
35.8
10.6
20.0
69.4++0.2
81.3++..2
Cluster-GCN
313
3.1
3.4
79.510.44
79.710..4
LBMB, graph part.
319
2.9
3.1
79.240.3
79.5
LBMB, PPR batching
374
5.0
13.1
80.520.33
80.710.3
Full graph
14.8
Neighbor sampling
14.4
7.3
93.5++0.1
94.8#0.1
Reddit, GCN
LADIES
15.4
11.4
11.4
95.5++0.0
95.3++0.0
GraphSAINT-RIN
17.1
14.6
2.9
93.24.0.1
95.6110.0
Cluster-GCN
175
1.8
1.6
93.710.2
94.810.1
LBMB, graph part.
175
1.4
93.510.4
94.710.11
LBMB, PPR batching
64.8
0.72
0.57
95.7+0.0
95.2+0.0
Full graph
76.9
Neighbor sampling
14.8
32.5
94.3110.1
95.1+0.11
Reddit, GAT
GraphSAINT-RRY
17.9
21
3.2
79.4+0..2
95.4+..1
Chuster-GCN
366
4.7
1.4
91.4:10.1
93.5
LBMB, graph part.
396
4.3
1.2
91.6100.1
92.811.1
LBMB, PPR batching
1.1
0.25
94.2410.2
94.210.1
Full graph
17.3
Redditt GraphSAGI
Neighbor sampling
16.1
7.5
96.24-0.0
96.840.00
GraphSAINT-RV
18.2
14.6
95.9++000
96.8+0.0
Cluster-GCN
173
1.7
1.8
95.5+0.2
96.0++.11
LBMB, graph part.
175
1.6
1.7
95.6
96.11.0.1
LBMB, PPR batching
66.0
0.77
0.65
96.8-10.1
96.4.10.0
Full graph
5700
papers 100M, GCN
Neighbor sampling
739
900
159
64.310.2
61.8102
LADIES
735
2830
05.42-0.2
62.4+0.4
LBMB, PPR batching
1160
104
11.7
66.0++0.1
66.3+0.00

---

103 Under review as a conference paper at ICLR 2022
19661 training nodes
1966 training nodes
86
Accuracy (%)
90
LBMB, PPR batching
89
84
Cluster-GG GCN
88
GraphSAINI-RW
10
10a
10
10
10
Train time (s)
Train time (s)
Figure: 3: Training convergence in log. time for GCN on ogbn-producls with smaller training sets. The gap in convergence speed between LBMB and the baselines grows larger for small training sets, since LBMB scales with training set size and not with overall graph size.
ogbn-arxiv, GON
ogba-products, GCN
Reddit, GCN
72
80
Accuracy
70
beiter
76
94
68
72
92
66
68
64
10
10
10a
10a
10a
10
10a
ogbn-arxiv, GAT
ogbu-products, GAT
Reddit, GAT
Full
72
80
96
LBMB, PPR batch.
Accuracy (%)
LBMB, graph part.
70
76
94
LBMB, rand batch.
72
Chuster-GNN
92
Neighbor sampl.
66
68
90
GraphSAINT-RY
64
64
LADIES
10
10
10a
102
10
10
10
10a
og ogbn-arxiv, GraphSAGE ogbn-products, CraphSACE
Reddit, CraphSACE
72
80
96
Accuracy (%6)
70
76
94
68
72
92
66
68
90
64
64
10-1
10
10
10a
10a
10a
100
10a
10a
Inference time (s)
Inference time (8)
Inference time (s)
Figure 4: Test accuracy and log. inference time for fixed GNN. LBMB consistently provides the best accuracy versus time trade-off (top-left corner).
datasets (Bojchevski et al. 2020). Table 1 furthermore shows that LBMB's time per epoch significantly taster than all sampling based methods. Cluster-GCh has comparable run- time, which is expected due to its similarity with LBMB. However, it converges more slowly than LBMB with PPR batching and reaches a substantially lower final accuracy. Neighbor sampling achieves good final accuracy, but is extremely slow. GraphSAINT-RYS only achieves good final accuracy with prohibitively expensive full graph inference. LBMB with PPR batching achieves the best final accuracy with scalable inference method in 8 out of 10 cases. LBMB requires more preprocessing than previous mothods. However, since LBMB is rather insensitive to hyperparameter choices (see Table 7 Fig. 10), preprocessing rarely needs to be re-run. Instead, its result can be saved to disk and re-used for training different models. Just considering 10 training seeds, preprocessing of LBMB (PPR batching) only took 1.3%
8

---

Under review as a conference paper at ICLR 2022
of the training time for GCN and 0.25 % for GAT on ogbn-arxiv. In some cases, LBMB uses more main memory than previons methods due to overlapping batches. However, it can also reduce memory requirements because it ignores irrelevant parts of the graph (see Table 6). LBMB with GCN outperforms SIGN-XI. ((66.1+0.2) %) (Frasca et al. 2020) on ogbn- papers100M, without any hyperparameter tuning and despite using 30x fewer parameters. LBMB furthermore has a substantially faster time per epoch and lower memory consumption than previous methods on this massive dataset, demonstrating LBMB's favorable scaling with dataset size. Notably, we were unable to evaluate GraphSAINT-RW and Siuster-GCM) on this dataset, since they use more than 256 GB of main memory. Despite its fixed, corrclated batches LBMB even performs similarly well as previous methods in terms of convergence per epoch (see Fig. 5p. This demonstrates the importance of focusing on computations efficiency.
Training set size. The ogbn-arxiv and ogbn-products datasets both contain a large number of training nodes (91k and 197k, respectively). However, labeling training samples is often an expensive endeavor, and models are commonly trained with only a few hundred or thousand training samples. GraphSAINT-RN and Ctuster-GGN are global training methods, i.e. they always use the full graph for training. They are thus ill-suited for the common setting of large overall graph containing a small number of training nodes (resulting in a small label rate). In contrast, the training time of LBMB purely scales with the number of training nodes. To show this, we reduce the label rate by sub-sampling the training nodes of ogbn-products and compare the convergence in Fig. 3. As expected, the gap in convergence speed between LBMB and both Cluster-GCN and GraphSAINT-RN grows even larger for smaller training sets. Final test accuracies of all batching methods remain comparable in this setting.
Inference. Vig. 4 compares the inference accuracy and time of different batching methods, using the same pretrained model and varying computational budgets (number of auxiliary podes/sampleed nodes) at fixed GPU memory budget. LBMB consistently provides the best trade-off between accuracy and time. PPR-based batching mostly performs better, except on ogbn-products, where it performs slightly worse than graph partitioning. LBMB provides a significant speedup over full graph inference, being 10 to 300 times faster at comparable accuracy, All previous methods are either significantly slower or less accurate.
Ablation studies. We ablate our primary node partitioning schemes by instead batching together random sets of nodes. We use fixed batches since we found that resampling incurs significant overhead without benefits- - which is consistent with our considerations on gradient samples and contiguous memory accesses. Fig. 7 shows that this method ("Fixed random") converges more slowly and does not reach the same level of accuracy as our partition schemes. Fig. shows that it (.IBBMB, random batch.") is also substantially slower and often less accurate for inference. This is due to the synergy effects of primary node partitioning: If primary nodes have similar auxiliary nodes, they benefit from each other's neighborhood. We test auxiliary nodc selection by comparing LBMB to Cluster-GCN, since this just uses the graph partition as a batch instead of smartly selecting auxiliary nodes. We use the graph partition size the number of auxiliary nodes for LBMB with graph partitioning to allow for a direct comparison. As discussed above, Cluster-GCN consistently performs worse, especially in terms of final accuracy, for inference, and for small label rates. Finally, Fig. 9 compares the proposed batch scheduling methods. Optimal and weighted sampling- based scheduling improve convergence and prevent or reduce downward spikes in accuracy. We explore further LBMB variants and hyperparameter choices in App.
6 CONCLUSION
We propose locality-based mini batching (LBMB), a method for extracting batches for GNNs. Unlike previous methods, we treat primary (output) and auxiliary nodes separately and focus the computational aspects of training. LBMB can be used both for training and inference, and outperforms previous methods on both tasks. It improves time per epoch by up to 20x and inference time by up to 100x compared to previous methods that reach a similar accuracy. These improvements grow even larger in the common setting of sparse labels and when the pipeline is constrained by data. access speed.
9

---

Under review as a conference paper at ICLR 2022
Reproducibility. We publish reference implementation along with this paper for re- producibility. Additionally, App. BJ contains all hyperparameters, experimental settings, software versions, and the hardware configuration necessary for reproducing our results.
Ethical considerations. Scalable graph-based methods can enable the fast analysis of huge datasets with billions of nodes. While this has many positive use cases, it also has obvious negative reperenssions. It can enable mass surveillance and the rcal-time analysis of whole populations and their social networks. This can potentially be used to detect emerging resistance networks in totalitarian regimes, thus suppressing chances for positive change. Voting behavior another typical application of network analysis: Voters of the same party are likely to be connected to one another. Scalable GNNs can thus influence voting outcomes they are leveraged for targeted ad advertising.
The ability of analyzing whole populations can also have negative personal effects in fully democratic countries. If companies determine credit ratings or college admission based connected personal data, person will be even more determined by their environment than they already are. Companies might even leverage the obscurity of complex GNNs to escape accountability: It might be casy to reveal the societal effects of your housing district, but unraveling the combined effects of your social networks and digitally connected behavior seems almost. impossible. Scalable GNNs might thus make it even more difffcull for individuals to escape the attractive forces the stal us quo.
REFERENCES
Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. In ICLR, 2021.
R. Andersen, F. Chung, and K. Lang, Local Graph Partitioning using PageRank Vectors. In FOCS, 2006.
Dominique Beaini, Saro Passaro, Vincent Lêtourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional Graph Networks. arXiv, 2010.02863, 2021.
Aleksandar Bojehevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rözemberczki, Michal Lukasik, and Stephan Günnemann. Scaling Graph Neural Networks with Approximate PageRank. In KDD, 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Networks via Importance Sampling. In ICLR, 2018.
Fast Learning with Graph Convolutional
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised Community Detection with Line Graph Neural Networks. In ICLR, 2019.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsiih. Cluster- GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In KDD, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liø, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. In NeurIPS, 2020.
Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alexander J. Smola, and Le Song. Learning Steady-States of Iterative Algorithms over Graphs. In ICML, 2018
Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding. In ICLR, 2020.
Johann Dréo, Alain Pétrowski, Patrick Siarry, and Eric Taillard. Metaheuristics for Hard Optimization: Methods and Case Studies. 2006.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. arXiv, 2003.00982, 2020.
10

---

Under review as a conference paper at ICLR 2022
Kimon Fountoulakis, Di Wang, and Shenghao Yang. p-Norm Flow Diffusion for Local Graph Clustering. In IOML, 2020.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. SIGN: Scalable Inception Graph Neural Networks. arXiv, 2004.11198, 2020.
Simon Geisler, Daniel Zügner, and Stephan Günneeaan. Reliable Graph Neural Networks via Robust Aggregation. In NewrIPS, 2020.
Joseph E. Gonzalez, Yucheng Low, Haijic Gu, Danny Bickson, and Carlos Guestrin. Power- Graph: Distributed Graph-Parallel Computation on Natural Graphs. In OSDI, 2012.
Prem K. Gopalan, Sean Gerrish, Michael Freedman, David Blei, and David Mimno. Scalable Inference of Overlapping Communities. In NewrIPS, 2012.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In NeurIPS, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In CVPR, 2016.
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. In NewrIPS, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining Label Propagation and Simple Models out- out-performs Graph Neural Networks. In ICLR, 2021.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive Sampling Towards Fast Graph Reprosentation Learning. In NewrIPS, 2018.
George Karypis and Vipin Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, (0(1):359-392 1998.
Diederik P. Kingma and Jimmy Ba. Adam: Method for Stochastic Optimization. In ICLR, 2015.
Thomas N. Kipf and Max Welling. Semi-Supprrised Classification with Graph Convolutional Networks. In TCLR, 2017.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then Propagate: Graph Neural Networks Meet Personalized PageRank. In ICLR, 2019.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion Improves Graph Learning. In NewrIPS, 2019.
Kyle Kloster and David F Gleich. Heat kernel based community detection. In KDD, 2014.
Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. GraphChi: Large-Scale Graph Computation on Just a {PC). In OSDI, 2012.
Qimai Li, Zhichao Han, and Xiao-Ming Ming Wu. Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning. In AAAI, 2018
Xin Liu, Mingyu Yan, Lei Deng, Guoqi Li, Xiaochun Ye, and Dongrui Fan. Sampling methods for efficient training of graph convolutional networks: A survey, arXiv, 2103.05877 2021.
Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang, Le Song, and Yuan Qi. Bandit Samplers for Training Graph Neural Networks. In NeurIPS, 2020.
Yucheng Low, Danny Bickson, Joseph Gonzalez, Carlos Guestrin, Aapo Kyrola, and Joseph M. Hellerstein. Distributed GraphLab: a framework for machine learning and data mining in the cloud. In VLDBB 2012.
11

---

Under review as a conference paper at ICLR 2022
Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, 2010.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Report, Stanford InfoLab, 1998.
Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, Chloc Hillier, and Timothy P. Lillicrap. Compressive Transformers for Long-Rand Range Soquence Modelling. In ICLR, 2020.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-assingg. In NewrIPS, 2020.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft. Academic Graph: When experts are not enough. Quantitative Science Studies, (11):996-41 -13396633,,, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation Learning on Graphs with Jumping Knowledge Networks. In ICML, 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 KDD, 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware Graph Neural Networks. In ICML, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph Sampling Based Inductive Learning Method. In ICLR, 2020.
Jing Zhu, Xingyu Lu, Mark Heimann, and Danai Koutra. Node Proximity is All You Need: A Unified Framework for Proximity-Preserving and Structural Node and Graph Embedding. In SIAM International Conference on Data Mining (SDM), 2021.
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph Neural Networks with Heterophily. In AAAI, 2021.
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. NewrIPS, 2019.
12

---

Under review as a conference paper at ICLR 2022
A RELATED WORK
Multiple works have proposed massively scalable GNNs that leverage the peculiarities of message passing to limit the model to single mossage passing step, akin to label or feature propagation [Bojchevski et al. 2020 Frasca et al. 2020 In our work we are interested in general, model-agnostic scalability methods.
Scalable GNNs.
Scalable graph learning. Classical graph learning faced issues similar to GNNs when scaling to large graphs. Multiple frameworks for distributed graph computations were proposed to solve this without approximations or sampling (Gonzalez et al. 2012 Low et al. 2012 Malewicz al., [2100] Kyrola et al.) 2012). Other works scaled large graphs via stochastic variational inference, o.g. by sampling nodes and node pairs (Gopalan et al. 2012). Interestingly, this approach is quite similar sampling-bas based mini batching for GNNs.
Mini batching for GNNs. Previous mini-batching methods can be divided into three categories: Node-wise sampling, layer-wise sampling, and subgraph- sampling (Liu el al. 2021 In node-wise sampling, we obt separate set of auxiliary nodes for every primary node, which are sampled independently for each message passing step. Each primary node is treated independently; if two primary nodes sample the same auxiliary node, compute its embedding twice (Hamilton et al. 2017 Ying et al.) 2018 Liu et al. 2020). Layer-wise sampling jointly considers all primary nodes of batch compute stochastic set of activations in cach layer. Computations on auxiliary nodes are thus shared (Chen et al., 2018; Huang al. 2018; Zou al. 2019). Subgraph-based sampling selects meaninglul subgraph and then rums the GNN on this subgraph as if il were the full graph. This method thus computes the oulputs and intermediate embeddings of all nodes in that subgraph (Chiang et al. 2019 Zeng et al. 2020). Our method most closely resembles the subgraph- based sampling approach. We also use the full subgraph induced by the selected nodes and calculate the intermediate embeddings for all nodes in batch. However, we only calculate the outputs of primary nodes, similar to node-wise sampling.
B MODEL AND TRAINING HYPERPARAMETERS
Hardware. All experiments
NVIDIA GeForee GTX 1080Ti. The experiments on ogbn-arxiv and ogbn-products use up to 64 GB of main memory. The experiments on ogbn-papers100M use up to 256 GB.
Packages. Our experiments are based on the following packages and versions:
torch-geometric 1.7.0
torch-cluster 1.5.9
torch-scatter 2.0.6
torch-sparse 0.6.9
python 3.7.10
ogb 1.3.1
torch 1.8.1
cudatoolkit 10.2.89
numba 0.53.1
python-tsp 0.2.0
Preprocessing. Before training, we first make the graph undirected, and add self-loops. The adjacency matrix is symmetrically normalized. We cache the symmetric adjacency matrix for graph partitioning and mini-batching. Instead of re-calculating the adjacency matrix normalization factors for GCN for each mini batch, re-use the global normalization factors. We found this to achieve similar accuracy at lower computational cost.
Models. We use three models for all the experiments: GCN (3 layers, hidden size 256 for the ogbn datasets and 2 layers, hidden size 512 for Reddit), GAT (3 layers, hidden size 128, 4 heads for the ogbn datasets and 2 layers, hidden size 64, 4 heads for Reddit), and GraphSAGE (3 layers, hidden size 256). All models use layer normalization, ReLU activation functions, and dropout. We performed a grid search ogbn-arxiv, ogbn-products, and
13

---

Under review as a conference paper at ICLR 2022
Table Number of batches for graph partition- bassiiioo-bbeed batching.
Number of batches
Model
Dataset
Train Validation Test.
GCN
ogbn-arxiv
4
2
2
GCN
ogbn-products
16
8
GCN
Reddit
8
4
GAT
ogbn-arxiv
8
4
4
GAT
ogbn-products
1024
512
512
GAT
Reddit
400
200
200
GCN
ogbn-papers100x.
256
32
48
Reddit to obtain the optimal model hyperparameters based on final validation accuracy. For ogbn-papers100M we use the same hyperparamoters as for GCN on ogbn-arxiv, but with 32 auxiliary nodes per primary node.
Training. To minimize data loading and memory access overhead we always prefetch the next batch in parallel. We found that using more than one worker for data loading does not. improve runtime, since loading is memory-bound, not. compute-bound. We use the Adam optimizer for all the experiments, with starting learning rate of 10-3, We use an Le regularization of 10 for GCN on ogbu-arxiv and ogbn-produs in all other settings. We use ReduceL decay factor 0.33, pationce 30, minimum lcarning rate 10-4, and cooldown validation loss. We train for 300 800 epochs and stop carly with a patience of 100 epochs, based on validation loss. We determine the optimal batch order for LBMB via simulated annealing (Dréo el. al. 2006).
and no L2 regularization scheduler for the optimizer, with the
10, based on
Graph partition-based batching. We tune the number of batches and thus the size of batches using a grid search (see Table 2). Generally, final accuracy increases with larger batch sizes, but this can lead to excessive memory usage and slower convergence speed. Note that the inference batch size double the sizes of training batches since in this case we do not need to store any gradients.
PPR-based batching. For PPR-based batching we first calculate the PPR scores for each primary node, and then pick the top-k nodes for each primary node its auxiliary nodes. Generally we use the same batch size, i.c. number of nodes batch, as in graph partition-based batching, to keep the GPU memory usage similar. However, if the graph too dense, we might have to increase the batch size of PPR-based batching, because it tends to create sparser batches. Note that the resulting nunber of batches might differ from Table 2] We tunc the number of auxiliary nodes per primary node using a logarithmic grid search using factors of 2. Based on this use 16 neighbors for ogbn-arxiv, 64 for ogbn-products and 8 for Reddit. Note that the number of auxiliary nodes is the main degree of freedom in LBMB. It influences preprocessing time, runtime, memory usage, and accuracy. The number of primary nodes per batch is then determined by the available GPU memory.
Random batching. Random batching similar to PPR-based batching except that the auxiliary nodes are batched randomly. We first calculate the PPR scores and pick the top-k neighbors the auxiliary nodes for a primary node. We choose the same number of neighbors as with PPR-based batching. We investigate 2 variants of random batching: Resampling the batches in every epoch, and sampling them once during preprocessing and then fixing the batches. We only show the results for the second method, since found it to be significantly faster, albeit requiring significantly more main memory.
Hyperparameter tuning. The priorities for tuning the hyperparameters are as follows: To keep methods comparable in a realistic setup, we keep the GPU memory usage constant between methods. 2. When there semantic hyperparameeerss that do not influence performance (such as the number of steps per epoch in GraphSAINN--RW; which only changes how epoch is defined), choose them to be comparable to other methods. We choose all relevant hyperparameters based on validation accuracy. We use this process for both LBMB and the baselines.
14

---

Under review as a conference paper at ICLR 2022
Table 3: Hyperparameters for LADIES
Nodes per layer
Model
Dataset
Train
Validation
GCN GCN GCN
ogbn-arxiv
42.
84 672
ogbn-products
204 085
306 128
Roddit
900000
150 000
Table 4: Hyperparameters for neighbor sampling
Number of batches
Model
Dataset
Train Validation Test Number of nodes
GCN
ogbn-arxiv
12
6, 5,
GCN
ogbn-products
20
200
5, 5, 5
GCN
Reddit
12, 12
GAT
ogbn-arxiv
8
4
8, 7,
GAT
ogbn-prii prodprrductss 1000
150
8000
15, 10, 10
GAT
Reddit
400
400
400
20, 20
Baseline hyperparameters. For Cluster- CCuster-GCN the number of batches are the same as for our graph partition-basel batching variant. Table 3 shows the hyperparameters for LADIES, Table 4 for neighbor sampling, and Table 5 for AITTRSAINT-RR. To ensure that every node visited exactly once during GraphSAINT-RYY inference we use the validation /ees nodes only as root nodes of the random walks.
Full graph inference. We chunk the adjacency matrix and feature matrix for full-graph inference to allow using the GPU even for larger datasets. The only hyperparameter is the number of chunks. We limit the chunk size to ensure that full-graph inference does not exceed the amount of GPU memory used during training.
Table 5: Hyperparameters for GraphSAINT-RW
Batch size
Model
Dataset
Walk length Sample coverage Number of steps
Train
Val Test
GCN
ogbn-arxiv
2
100
000
10000
GCN
ogbn-products
2
100
16
80000
5000
GCN
Reddit
2
100
23 000
6000
GAT
egbn-arxiv
2
100
17
10.000
GAT
ogbn-products
2
100
1024
14000
100
GAT
Reddit
2
100
400
1600
60
15

---

Under review as a conference paper at ICLR 2022
C ADDITIONAL EXPERIMENTAL RESULTS
Main memory usage. Since LBMB saves the preprocessed dataset to memory, it can have rather different main memory footprint than the normal dataset. To illustrate this, consider the Reddit dataset. LBMB uses 8 auxiliary nodes per primary node on this dataset, and the train and validation sets of Reddit contain 177k nodes (of a total of 233k nodes). If there was no overlap, this would translate to 1.4 million auxiliary nodes. However, our method aims at increasing preciscly this overlap between auxiliary nodes a batch (see Sec. 3). With graph partitioning, end up with 466k auxiliary nodes, and with PPR batching auxiliary nodes, across all batches. The number of auxiliary nodes determines the size of the batched feature matrix and thus the memory size. The number of edges per batch also impacts memory usage, but the feature matrix usually the dominant factor. The edges do, however, have major impact on GNN computation time. Overall, should expect memory usage of around 416/233 = 178 % with PPR batching, and 466/233 = 200 % with graph partitioning, compared to the normal dataset. All in all, LBMB's memory usage thus depends on three aspects: 1) How large is the training validation set compared to the full graph? 2) How many auxiliary nodes per primary node batches overlapping?
have 416k
using? 3) How well the
So why are we not seeing memory overhead in the measured usage for Reddit in Table 6 Because LBMB requires no memory for sampling. Constructing and prefetching batches requires surprisingly large amount of memory, especially if you aim saturate main memory or PCIe bandwidth ( (3GB/ss) The memory used by sampling is required in addition to the normal dataset, while LBMB can delete the dataset from memory after preprocessing.
LBMB variants. ig. 7 shows that PPR-based batching converges faster than both graph partition-based and random batching. This suggests that the middle ground between unbiased gradient samples (random batching) and strongly overlapping batches (graph partitioning) is beneficial. Furthermore, graph partition-based batching converges faster than fixed random batching in time, but not per epoch. This demonstrates the impact auxiliary node overlap runtime. We found that LBMB is largely insensitive to different local clustering methods and hyperparameters for selecting auxiliary nodes (see Table 7). Fig. 10 shows that the batch size (number of primary nodes per batch) also only has minor influence accuracy, especially above 1000 primary nodes per batch. Consequently, in practice LBMB only has single free hyperparameter to choose: The number of auxiliary nodes per primary node. This can be determined in few training runs. The number of primary nodes per batch then given by saturating the available GPU memory, and the local clustering method and hyperparameters are not important. Note that Fig. 10 shows that LBMB performs surprisingly well with small batches. LBMB can thus even be used extremely constrained settings with small batches of 100 primary nodes per batch.
Table 6: Main memory usage (GiB). In some cases, LBMB uses more main memory than previous methods due to overlapping batches (c.g. on ogbn-products). However, it can also reduce memory requirements bocause it ignores irrelevant parts of the graph (c.g. on Reddit). Note that chose hyperparameterss in way that keeps GPU memory usage roughly constant between methods (as opposed to main memory usage).
ogbn-arxiv
ogbn-product
Reddit
GCN GAT GraphSAGE GCN GAT GraphSAGE GCN GAT GraphSAGE
Neighbor sampling
3.0
3.6
3.1
8.7
7.9
8.5
7.4
7.5
7.1
LADIES
3.0
6.0
4.8
GraphSAINT-RW
3.5
3.6
3.5
9.6
9.6
9.6
8.4
8.5
8.4
Cluster-GCN
3.5
3.4
3.5
7.8
6.0
7.3
6.1
4.2
6.5
LBMB, graph part.
3.5
3.6
3.5
7.9
7.0
7.8
6.3
4.9
6.3
LBMB, PPR batching
3.8
3.8
4.2
13.0
12.3
13.2
4.5
5.3
5.1
16

---

Under review as a conference paper at ICLR 2022
ogbn-arxiv, GCN
ogbn-products, GON
Reddit, GCN
74
96
Accurary (%)
92
72
94
90
92
88
68
88
200
400
600
0
200
400
600
100
200
300
ogbn-arxiv, GAT
ogbn-products, GAT
Reddit, GAT
74
96
LBMB, PPR. batch.
Ancuracy (36)
92
LBMB, graph part.
Cluster-GCN
90
92
Neighbor sampling
70
GraphSAINT-RW
90
LADIES
68
88
200
400
600
0
100
200
300
100
200
300
ogbn-arxiv, GraphSAGE ogbn-products, GraphSAGE
Reddit, GraphSAGE
96
Arcuracy 1%0)
92
72
94
90
70
90
88
400 Epoch
200
400 Epoch
100
200
300
Epocc
Figure 5: Convergence per epoch. LBMB converges similarly fast in most cases, despite not performing any sampling.
19661 training nodes
1966 training nodes
86
Accuracy (%)
90
LBMB, PPR batching
84
Cluster-GCN
88
GraphSAINT-RN
82
50
100
150
0
50
100
150
Epoch
Epoch
Figure 6: Training convergence per epoch for smaller training sets. All methods converge similarly fast per training step, demonstrating once again the importance a fast. time per training step.
17

---

Under review as a conference paper at ICLR 2022
Accuracy (%
Accuracy
Accuracy
68
72
PPR batch. Graph part.
72
PPR batch. Graph part.
Optimal
66
Sampled
Fixed randorn
Fixed random
Random
71
64
25
50
75
100
200
400
50
100
150
Train time (s)
Epoch
Train time (s)
Convergence per Figure 9: Batch scheduling for time for training GCN on epoch for batching methods GAT ogbn-arxiv. Optimal ogbn-arxiv. Both graph par- when training GCN on ogbn- batch order prevents down- titioning and PPR batching arxiv. PPR-based partition- ward spikes in accuracy and lead to faster convergence ing also converges the fastest leads to higher final accuracy. than fixed random batching. per training step.
Figure 7: Convergence per Figure 8:
Table 7: Methods and hyperparameters for selecting aux- iliary nodes for GCN on ogbn-products. LBMB very robust to this choice. We did observe slightly lower vali- dation accuracy for low alpha (0.05), so we recommend using 0.25.
Accuraccy (%)
Time (s)
Test accuracy (%)
Method
a,
per epoch LBMB inference Full graph
71 10a
10a
10a
PPR
0.05
3.5
76.8+0.3
77.1+:0.3
Primary nodes per batch
PPR
0.15
3.6
76.6:0.4
76.910.44
PPR
0.25
3.5
76.8+0.2
77.2+0.3
Figure 10: Final test accuracy (LBMB inference) when train- ing LBMB with PPR batching with different numbers of pri-
PPR
0.35
3.5
76.9
77.2+0..5
Heat kernel 0.1
3.5
76.5+0.4
76.8+0.3
Heat. kernel
3.5
76.6-10.5
76.9+10.5
Heat kernel
3.5
76.8+0.2
77.140.2
mary nodes per batch (GCN on ogbn-arxiv). LBMB is rather insensitive to this choice.
Heat. kernel
3.5
76.7++0.5
77.0+-0.5
Heat kernel
3.5
76.640.4
76.8+00.4
18

---

Under review as a conference paper at ICLR 2022
D ADDITIONAL CONSIDERATIONS
Experimental limitations. We only tested our method on homophilic node classification datascts. While proximity is central inductive bias in all GNNs, did not explicitly test this on a more general variety of graphs. However, note that LBMB does not require homophily, The underlying assumption is merely that nearby nodes are the most important, not that they are similar. Finally, we expect our method to perform even better in the context of node graphs, but our benchmark datasets still fit into main memory.
Micro batching. To further smoothen the gradients we could accumulate gradients across multiple batches before performing a gradient step, a method known as micro batching. This is especially well-suited for calculating the gradients of multiple batches in parallel, e.g. via distributed training. With some overhead, we can even inchude inter-batch odges in this case, as proposed by Cluster-GCN (Chiang et al., 2019 We found that neither regular micro batching nor parallel micro batching with inter-balch edges yields noticeable improvements for the datasels we considered.
Exponential moving averages. Another common method for smoothing noisy model weight updates are exponential moving averages (EMA) of the model parameters. This approach uses two sets of model parameters: The regular training parameters and the shadow parameters. The shadow parameters are updated in cach step by a fraction of the current training parameters, thus giving an exponential moving average of the regular paramoters. The shadow parameters are never used during training, only for validation and prediction. While this method often has a positive impact on accuracy, we did not use it for the sake of simplicity.
Scalable batch scheduling. The batch scheduling methods we introduced in Sec. 4 are quadratic in the number of batches, which might become problematic for massive datasets. While this was not a problem in our experiments, we can overcome this by scheduling based on batch clusters instcad of individual batches.
Long-range interactions. Many models in deep learning have dozens or even hundreds of 2016). However, modern GNNs typically only have few layers. Intuitively. this might seem like strong limitation, and is often attributed to oversmoothing (Li et al. 2018 However, GNNs that overcome oversmoothing stiill only rely on a close neighborhood
layers He al.)
heterophilic graphs as well (Zhu et al. (2021b) Even structural brsse) embeddings are based on a mcasure of proximity (Zhu et al.) 2021a), which can also be exploited for mini batching. This difference to regular neural networks is most likely due to the message passing dynamics in GNNs. The dynamics are very different due to the permutation invariance required in aggregation. The aggregation mechanism in Eq. (2) means that nodes al a far distance are aggregated across multiple layers, and can thus longer be represented individually AAln & Yahav 2021). b. Only very few models are capable of preserving messages over long distances (Beaini et al.) 2021 Alon & Yahav 202I), and none have demonstrated benefits for large networks. On the contrary. simple label propagation and diffusion methods can substantially improve the accuracy of GNNs on large graphs (Klicpera et al. 2019b; Huang al. (021). Overall, current evidence strongly suggests that in most datasets the close neighborhood is disproportionately more important for GNN predictions than distant neighbors. While the role of range interactions in GNNs still remains an open lopic of research, focusing local clusters thus does not appear to be a limitation for most GNNs. This also evidenced by many previous scalability methods relying on locality well (Zeng et al. 2020 Chiang
[Xu et al. 2018 Klicpera et al. 2019ah. This holds for models focusing
eet al. 2019).
For settings that still require long-range interactions, locality-based mini batching could be
extended using special globally connected nodes, parallel micro batching with inter-batch edges (see Sec. 40, or steady-state learning (Dai et al. 2018) possibly with compression to
enable scaling to large graphs (Rac et al. 2020
19


Reviews:
[{"review_id": "t9olc61AMTO", "reviewer": "Reviewer_AWEr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work studies an important question that plagues the training and inference of graph neural networks in a large scale. Random memory access is not necessarily the root cause that prevents faster training, but indeed the extra cost to reorganize batch data into consecutive memory is an anchor of improvement. The authors precompute the batches and shift the burden from training to preprocessing; this is an interesting idea to explore.\n\nMajor issues:\n\nAlthough generally it is argued that preprocessing is done only once and sounds less important, note that training (and inference) is also done only once for graph neural networks. Hence, a comprehensive study should also compare the total time in preprocessing plus training (possibly including also inference) across different methods. This is lacking in Table 1.\n\nAnother concern is the memory cost incurred to store the mini batches. A node may appear in multiple batches, causing multiple times storage increase compared to usual sampling methods. This problem is more pronounced when the training set is large (causing more overlaps among the batches). Certain analysis would be desirable.\n\nA lot of technical details developed in the paper (such the the partitioning approaches and the approaches to selecting auxiliary nodes) follow straight intuition. The authors provide no theoretical analysis/support and they do not even prefer an approach, when multiple choices are equally plausible. This renders the paper rather empirical. Then, strong experiment results are needed to give a reader confidence to adopt the proposed techniques. However, the current empirical results are not sufficiently strong. For example, Table 1 does not appear to suggest an exclusively advantageous method. Moreover, the experiment section can be stronger if results of more networks (e.g., GraphSAGE and GIN) are demonstrated.\n\nAn important problem is that deterministic batches go entirely outside the realm of stochastic optimization, while also not being applicable to a usual deterministic optimization that requires the full gradient. Convergence and convergence rates are unclear and obviously the authors also face irregularities (such as \"downward spikes\" mentioned in Section 4). More in-depth study, from either the theoretical side or the empirical side, is needed to solidify the proposed work.\n\nMinor issues/questions:\n\nAt the beginning of section 3, it is mentioned that the first step of LBMB obtains the $k$ most important auxiliary nodes for each primary node. However, section 3.1 discusses partitioning without the use of these auxiliary nodes. Could the authors clarify?\n\nIn table 1, preprocessing time for the papers100M data set is missing.\n\nIn table 1, is the inference time using \"same method\" or \"full graph\"?\n\nTable 1 can benefit from also reporting the number of training epochs to reach the test accuracy listed thereof.\n\n---\n\nAfter rebuttal\n\nThe authors made good arguments regarding my initial concerns on expensive preprocessing time and costly memory consumption. I therefore adjust the score. There remain concerns regarding too many options (none preferred) in the proposed method and the unclear impact on training convergence. The idea by itself is illuminating and with polish and prudence in use, it may lead to a leap in the training of GNNs in a large scale.", "summary_of_the_paper": "This paper studies the training of graph neural networks and proposes a mini batching scheme that circumvents the expensive cost of traditional sampling approaches due to random memory access. The authors construct deterministic mini batches so that they can be laid out in consecutive memory, which speeds up training. The authors empirically show that such a mini batching scheme significantly improves training and inference time, at the cost of precomputation.", "summary_of_the_review": "This paper studies an important question. The proposed method, however, has multiple issues including timing, storage, convergence, and insufficient empirical evidence.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Lc1hjwY8fy3", "reviewer": "Reviewer_myta", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths of the paper\n\n1. The paper proposes a novel approach to deriving minibatches for training graph neural networks.\n2. The experiments indicate that the proposed technique achieves a significant reduction in training time and dramatically improves the inference time. The experiments appear to have been executed with care.\n3. The ablation study and analysis of training set size provide useful insight into the behaviour of the algorithm. \n\nWeaknesses of the paper\n1. The envisioned learning pipeline could be better articulated to make the trade-offs clearer in terms of time required for pre-processing and training time (number of epochs, time per epoch).  Related to this are concerns about how hyperparameter tuning factors into an assessment of the practical training time.\n2. The procedure is novel, but Cluster-GCN already proposed the partitioning of the graph as part of the sampling process, so the contribution represents \n3. The proposed technique is heuristic, with existing techniques being selected and combined. The derivation of the overall algorithm is thus not based on a principled procedure. \n \n4. The experiments report results for only one choice of batch size. The batch size has a major impact on the performance of the sampling algorithms (both in terms of accuracy and convergence time), so it is important to explore a range of choices. The procedure for selecting the hyperparameters for the baselines is not entirely clear \n\n5. The experiments are only conducted for GAT and GCN. While these may be considered to be representative of many GNNs, they are no longer state-of-the-art. It is not entirely clear that the results will carry over to more recent methods that achieve considerably better performance for the addressed learning tasks. \n\nRecommendation and major reasons for the recommendation\n\nI have recommended a “marginally below the acceptance threshold”. \n\nI think the core idea is clever and the authors have exhibited considerable skill in constructing the overall algorithm. On the other hand, there are several concerns that prevent me from recommending that the paper be accepted. \n\n(1) Novelty & heuristic nature: While I do acknowledge the novelty of the technique, the approach is strongly related to Cluster-GCN, and although the proposed method does represent a clear improvement over that approach, this does limit the novelty of the contribution. The technique is heuristic in nature, and is not developed based on a principled foundation. There is no theoretical characterization of the proposed method.  The results are reported for specific choices of local clustering and graph partitioning, so it’s not entirely clear whether the performance is strongly dependent on these selected methods (having said this, the paper does explore two different types of partitioning, and both yield similar performance, so this points in the direction of the technique performing satisfactorily for any reasonable graph partitioning strategy).  \n\n(2) Application in practice and nature of the trade-off: It would be very helpful if the paper better articulated how the method would be applied in practice. In addition to the depicted training time, there is a hidden cost of determining hyperparameters that involves a grid search. The proposed method appears to introduce more hyperparameters than some of the other approaches. Moreover, the selected hyperparameters change from dataset to dataset, suggesting that the hyperparameter selection procedure needs to be performed for every dataset (although perhaps Table 6 hints that this is not the case). It then becomes questionable how valuable it is to reduce the training time for a dataset, since it would form only a small portion of the overall training overhead. \n\nThe paper states in Section 3.3 that “a machine learning model is trained only once”, but later makes the argument that the pre-processing overhead involved in constructing the partitions is a one-time overhead compared to the training cost. If the model is only trained once, then is it fair to exclude the pre-processing time from the plots in Figure 1?\n\n(3) Experimental procedure: The authors report that a grid search was conducted to find suitable parameters such that there was a similar memory usage, similar number of iterations per epoch, and maximum validation accuracy. Since there seem to be competing criteria and the ranges of the hyperparameter tuning process are not provided, it is difficult to understand exactly how the hyperparameters were selected. \n\nThe performance when training on large graphs tends to be quite sensitive to batch size. It would be much better if results could be included for multiple batch sizes. At the least, it should be clear which range of batch sizes was selected for the hyperparameter tuning process. \n\nQuestions\n\n(1) GAT and GCN, while representative of many graph models, are not the state-of-the-art for many learning tasks. Is it clear that the results provided in the paper are likely to generalize to other GNN models? If so, why? \n\n(2) If possible, please provide a clarification of the hyperparameter tuning process, particularly for the baselines. \n\n(3) Please clarify the intended use of the approach (how would it be incorporated in a machine learning pipeline in a practical application). How long does hyperparameter tuning take relative to training time? If it takes as long or longer, is this an important consideration, or is it reasonable to focus entirely on training time? Is there an example scenario where training would be repeated multiple times without a requirement for re-tuning the hyperparameters. Is it clear that the pre-processing time should be excluded when comparing two methods?\n", "summary_of_the_paper": "The paper addresses the task of training graph neural networks on large graphs. The authors propose a strategy to extract mini-batches that are locally connected. The technique involves dividing nodes into primary and auxiliary nodes, where the primary nodes are those for which an prediction is formed during the batch (usually training nodes). The auxiliary nodes are used for computation of the predictions. The authors propose two procedures for selecting the primary nodes in a minibatch. One uses distance-based partitioning (a greedy procedure building on personalized page rank as a distance measure). The other applies graph partitioning (METIS). After the primary nodes have been partitioned, auxiliary nodes are selected using local clustering techniques (a form of topic-sensitive PageRank is employed). The authors observe that this construction of mini-batches is also useful in the inference process. The paper proposes methods to mitigate the effect of the introduction of correlation in the gradients that arises due to the proximity-based partitioning. There are also strategies to prevent the optimizer from processing consecutive batches that are very similar. \n\nThe paper provides experimental results for GAT and GCN for four large graph datasets, with a comparison to four baselines.  The results provide evidence that the proposed strategy leads to a significant reduction in training time and also has a major benefit during inference. The authors the impact of training set size and conduct an ablation study to verify that all proposed aspects of the proposed method yield performance improvement. \n", "summary_of_the_review": "** After modifications and discussion, I have increased the score to \"marginally above the acceptance threshold\".\n\nThe recommendation of the review is “marginally below the acceptance threshold”. \n\nThe paper is considered to propose sufficiently novel techniques, although aspects of the approach are similar to prior work. The impact of the paper may be somewhat limited because of the heuristic nature of the proposed methodology. \n\nThe paper introduces an increased pre-processing overhead in order to achieve a speed-up in training time. Although the pre-processing time is reported in tables, it is excluded in the figures that compare the overall train times. There appears to be a need for considerable hyperparameter tuning. This process, conducted via grid search, might take considerably longer than the actual reported training.\n\nAlthough the experiments appear to have been conducted thoroughly, results are reported for only one set of hyperparameters. The selection process of these for the baselines is not particularly clear.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1A3XlLXi9a", "reviewer": "Reviewer_WNRe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes LBMB, a scalable and effective method for extracting mini batches (subgraphs) by primary node partitioning, followed by auxiliary node selection. This method can be applied to both training and inference, which is a strength of this work. Evaluation demonstrates that LBMB spends much less epoch time for training than existing methods, while maintaining comparable accuracy. Inference also shows significant speedups than existing methods (especially than those using the full graph). However, I still have several concerns/questions about this proposal as follows:\n\n* *Methodology* - While the mini-batch precomputation is the major source of performance gains in LBMB, I am wondering how many sub-processes the authors used for runtime sampling (i.e., *num_workers* in PyTorch). I am asking because a runtime sampling method can often be fully pipelined with GNN computation if a sufficient number of sub-processes are used [R1][R2].\n\n* *Space Overhead* - This work leverages space-time tradeoffs in extracting mini-batches via precomputation. That said, I am curious about the *space (memory) overhead* incurred by the proposed mini-batch precomputation.\n\n* *Cost of Preprocessing* - The preprocessing time seems to be substantially higher than other schemes. The authors argue that the preprocessing is one-time cost, but this overhead can be compounded by hyperparameter tuning for LBMB such as the number auxiliary nodes per primiary node, batch size, and so on. Furthermore, the proposed preprocessing approach seems not feasible to am *inductive* setting where the GNN should deal with unseen data.\n\n* *Applicability of Preprocessing* - Can the preprocessing idea be applied to the other mini batching methods for GNNs such as node-wise and layer-wise sampling methods?\n\n\n[R1] Dong et al., Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs, KDD'21\n\n[R2] Min et al., Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture, VLDB'21\n\n", "summary_of_the_paper": "This paper proposes locality-based mini batching (LBMB), a method for extracting batches for GNN training. LBMB aims to reduce the computation cost of GNN training by treating primary (output) nodes and auxiliary nodes separately.  LBMB can be used for both training and inference, and speeds up both tasks substantially while maintaining comparable accuracy.", "summary_of_the_review": "This paper proposes a scalable and effective method for extracting mini batches (subgraphs), which can be applied to both training and inference of GNNs. However, I still have several major issues/questions about this work, and would ask the authors to address them in their rebuttal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper suggests a non-random strategy for selecting minibatches of nodes for training graph neural networks. The main argument is that consecutive memory accesses are faster than random accesses, and thus they claim a 20x speedup per epoch by precomputing batches at a small cost to accuracy. 

There are a number of discussion points. One reviewer finds the results hard to believe because previous work has shown that runtime sampling can be fully pipelined. The authors agree but say their speedups are still better, which isn’t a fully satisfying response, and it calls into question the quality of the baseline implementation. Another concern is about the effect of deterministic minibatches. The authors argue that the empirical results speak for themselves, while the reviewer worries about robustness. There also are some concerns about methodology around hyperparameters and special-casing of preprocessing for one dataset, though those appear mostly resolved.

On the whole, this is a borderline paper that lands just on the side of rejection. I’d encourage the authors to more thoroughly address the questions about quality of the baseline implementation and the reviewer’s concern about robustness of deterministic minibatches, and then resubmit to the next conference.
Decision: Reject