Cooperative Minibatching in Graph Neural Networks
Authors: Muhammed Fatih Balin
Dominique LaSalle
Umit Catalyurek
Venue: Accepted by TMLR ()

Abstract: Training large scale Graph Neural Networks (GNNs) requires significant computational resources, and the process is highly data-intensive. One of the most effective ways to reduce resource requirements is minibatch training coupled with graph sampling. GNNs have the unique property that items in a minibatch have overlapping data. However, the commonly implemented Independent Minibatching approach assigns each Processing Element (PE, i.e., cores and/or GPUs) its own minibatch to process, leading to duplicated computations and input data access across PEs. This amplifies the Neighborhood Explosion Phenomenon (NEP), which is the main bottleneck limiting scaling. To reduce the effects of NEP in the multi-PE setting, we propose a new approach called Cooperative Minibatching. Our approach capitalizes on the fact that the size of the sampled subgraph is a concave function of the batch size, leading to significant reductions in the amount of work as batch sizes increase. Hence, it is favorable for processors equipped with a fast interconnect to work on a large minibatch together as a single larger processor, instead of working on separate smaller minibatches, even though global batch size is identical. We also show how to take advantage of the same phenomenon in serial execution by generating dependent consecutive minibatches. Our experimental evaluations show up to 4x bandwidth savings for fetching vertex embeddings, by simply increasing this dependency without harming model convergence. Combining our proposed approaches, we achieve up to 64\% speedup over Independent Minibatching on single-node multi GPU systems, using same resources.

Published in Transactions on Machine Learning Research (01/2025)
Cooperative Minibatching in Graph Neural Networks
Muhammed Fatih Balm"
balin Balénnggatechcoo edu
School of Computational Science and Engineering Georgia Institute of Technology, Atlanta, GA, USA
Dominique LaSalle
Alasalle@nvidie com
NVIDIA Corporation, Santa Clara, CA, USA
Ümit V. Çatalyürek!
umit edu
School of Computational Science and Engineering
Georgia Institute of Technology, Atlanta, GA, USA
Reviewed on OpenReview: https: // opw.reveee.r...e...em net/ forum? id- 16yMdmrD2g
Abstract
Training large scale Graph Neural Networks (GNNs) requires significant computational resources, and the process is highly data-intensive. One of the most effective ways to reduce resource requirements minibatch training coupled with graph sampling. GNNs have the unique property that items in a minibatch have overlapping data. However, the commonly implemented Independent Minibatching approach assigns each Processing Element (PE, i.e., cores and/or GPUs) its own minibatch to process, leading to duplicated computations and input data access across PEs. This amplifies the Neighborhood Explosion Phenomenon (NEP), which is the main bottleneck limiting scaling. To reduce the effects of NEP in the multi-PE setting, we propose a new approach called Cooperative Minibatching. Our approach capitalizes on the fact that the size of the sampled subgraph is a concave function the batch size, leading to significant reductions the amount of work as batch sizes increase. Hence, work on a large minibatch
it is favorable for processors equipped with a fast interconnect together as single larger processor, instead of working separate smaller minibatches, even though global batch size is identical. We also show how to take advantage of the same phenomenon in serial execution by generating dependent consecutive minibatches. Our experimental evaluations show up to 4x bandwidth savings for fetching vertex embeddings, by simply increasing this dependency without harming model convergence. Combining our proposed approaches, we achieve up 64% speedup over Independent Minibatching on single-node multi-GPU systems, using same resources.
1 Introduction
Graph Noural Networks (GNNs) have become de facto deep lcarning models for unstructured data, achiov- ing state-of-the-art results on various application domains involving graph data such as recommendation systems (Wu et al. 2020 Ying al.] 2018), fraud detection (Liu et al. 2022; Patel et al. 2022), identity rosolution (Xu et al. 2019 and traffic forccasting (Jiang & Luo 2022). However, as the usage of technology continues to increase, the amount of data generated by these applications is growing exponentially, resulting single processing
in large and complex graphs that are infeasible or too time-consuming to train element (Ying et al.) 2018 Zhu et al. 2019).. For example, some social media graphs are reaching billions of vertices and trillions of interactions (Ching et al.) 2015). Efficient distributed training of GNNs is essential for extracting value from large-scale unstructured data that exceeds the cost of storing and processing such data.
Part of this work was done during an internship NVIDIA Corporation in the summer of 2022.
Amazon Web Services. This publication describes work performed the Georgia Institute of Technology and is not. assciiated with AWS.

---

Published in Transactions on Machine Learning Research (01/2025)
Due to the popularity of Deep Neural Networks (DNNs) and the need to support larger models and datasets, great deal of research has focused on increasing the scale and efficiency of distributed DNN training. Techniques such as data parallelism (Ginsburg et al. 2017 Goyal et al. 2018), pipelining (Naayaaaa et al., 2019), and intra-layer parallelism (Dean et al.) 2012) have been employed. Following the success of traditional distributed DNN training, the same techniques have also been adapted to GNN training, such as data
parallelism (Gandhi & Tyer 2021 Lin et al. 2020: Zheng et al., 2021 Zhu et al.) 2019) and intra-layer
parallelism (Tripathy et al., 2020).
The parallelization techniques mentioned earlier are used to scale both full-batch and minibatch training in distributed setting. Minibatch training (Bertsckas] 1994) is the go-to method to train DNN models as it outperforms full-batch training in terms of convergence (Allen-Zhu & Hazan 2016 Li et al. 2014 Keskar et al. 2016 Wilson & Martinez, 2003), and more recently has been shown to also offer the same benefit for GNNS (Zheng et al. 2021). ). In the distributed setting, minibatch training for DNNs using data parallelism is straightforward. The training samples are partitioned across the Processing Elements (PE) and they compute
the forward/ forward/backwardd backward operations on their minibatches. The only communication required is an all-reduce operation for the gradients.
Unfortunately, minibatch training GNN model is more challenging than a usual DNN model. GNNs turn a given graph encoding relationships into computational dependencies. Thus in an L-layer GNN model, each minibatch computation has a different structure as it is performed on the L-hop neighborhood of the minibatch vertices. Real-world graphs usually are power law graphs (Artico et al. 2020) with small diameters, thus, it is a challenge to train deep GNN models as the L-hop neighborhood grows exponentially w.r.t. L, reaching almost the whole graph within few hops. This is especially the case for the node classífication and link prediction scenarios where the graph can be large and a single connected component contains almost all the data.
Very large GNN datasets necessitate storing the graph and node embeddings on slower storage mediums. To enable GNN training efficiently in such a setting, several techniques have been proposed (Park et al. 2022 Walelle et al. 2022). These studies assume that the graph and its features are stored on disks or SSDs and design their systems to reduce data transfers. The methods proposed in this paper directly apply to these scttings by reducing bandwidth requirements, as scen in Section 4
A single epoch of full-batch GNN training requires computation proportional to the number of layers I. and the size of the graph. However, minibatch training requires more operations to process a single epoch due to repeating calculations in the 2nd through L-th layers. As the batch size decreases, the number of repeated calculations increases. This is because the vertices and edges have to be processed each time they appear the L-hop neighborhood. Thus, it natural to conclude that using effectively larger batch sizes in GNNs reduces the number of computations and data accesses of an epoch in contrast to regular DNN models. Our contributions in this work utilizing this important observation can be listed as follows:
Investigate work vs. batch size relationship and present theorems stating the cost of processing a minibatch is concave function of the batch size (Theorems 3.1 and 3.2
Utilize this relationship by combining data and layer parallelism to process a minibatch across multiple PEs for reduced work (Section 3.1b, with identical global batch size. We call this new approach Cooperative Minibatching.
Use the same idea to generate consecutive dependent minibatches to increase temporal vertex embedding access locality (Section 3.2). Dependent Minibatching can reduce the transfer amount of vertex embeddings up to 4x, without harming model convergence.
Show that the two approaches are orthogonal. When combined, they result in up to 1.64x speedup over Independent Minibatching with identical global batch size.
Further show the applicability of Cooperative Minibatching to the subgraph sampling methods and prove that sampled subgraph density is a nondecreasing function of the batch size (Theorem 3.3)
2

---

Published in Transactions on Machine Learning Research (01/2025)
2 Background
A graph G = E) consists of vertices V and edges E C V x V along with optional edge weights Ats > 0, V(t - s) E E. Given vertex 8, the 1-hop neighborhood (s) is defined as N(s) = { + s) E E}, and it can be naturally expanded to a set of vertices as ((S) = Uses (s)).
GNN models work by passing previous layer embeddings (H) from N(s) to s, and then combining them using nonlinear function f()) layer I, given initial vertex features H
H (H) (E
(1)
If the GNN model has L layers, then the loss is computed by taking the final layer L's embeddings and averaging their losses over the set of training vertices V₁ C V for full-batch training. In L-layer full-batch training, the total number of vertices that needs to be processed is L.[]
2.1 Minibatching in GNNs
In minibatch training, random subset of training vertices, called Seed Vertices, is selected, and training is donc over the (sampled) subgraph composed of L-hop neighborhood of the seed vertices. On each iteration, minibatch training computes the loss on seed vertices, which are random subsets of the training set V,-
Given a set of vertices S, we define (-th layer expansion set, or the L-hop neighborhood S as:
= =
=
(2)
For GNN computations, St would also denote the set of the required vertices to compute 1 at each layer I. Using the same notation, {s}' denotes l-layer expansion set starting from single vertex V.
For single minibatch iteration, the total number of vertices that need to be processed is Σt |5 There IV minibatches assuming V = V. Since each | 2 | and single epoch minibatch training needs are [so to go over the whole dataset, the work W (I for single epoch is:
V S
V
L L
W(IS"))
Σ
E
Σ
S
(3)
S
where E]|S'|] is the expected number of sampled vertices in layer and |S is the batch size. That is, the total amount of work to process single epoch increases over full-batch training. The increase in work due to minibatch training is thus encoded in the ratios E||S' T 15
When sampling is used with minibatching, the minibatch subgraph may potentially become random. However, the same argument for the increasing total amount of work holds for them too, as seen in Figure 3
2.2 Graph Sampling
We focus on samplers whose expected number sampled vertices is a function of the batch size. Neighbor Sampling (NS) (Hamilton et al. 2017), LABOR (Balin & Çatalyürek 2023 and RandomWalk (RW) Sampling YYigg et al. (2018) all have this property and they are all applied recursively for GNN models with multiple layers. Appendix A.1 describes the details of these sampling methods.
2.3 Independent Minibatching
Independent minibatching commonly used in multi-GPU, and distributed GNN training frameworks (Cai ct al. 2023 Gandhi & Tyer 2021 Lin et al.] 2020; Zheng et al. 2021 Zhu al. 2019) to parallelize the training and allows scaling larger problems. Each Processing Element (PE, e.g., GPUs, CPUs, or cores of multi-core CPU), starts with their own 5 of size the seed vertices, and compute S1 ,h,...,,S Sh along
3

---

Published in Transactions on Machine Learning Research (01/2025)
Figure 1: Minibatches two processing elements may share edges in the second layer and vertices starting the first layer. For independent minibatching, the solid green edges shared by both processing elements represent duplicate work, and input nodes B through G are duplicated along with the directed endpoints of green edges. However for cooperative minibatching, the vertices and edges are partitioned across the PEs with no duplication, and the edges crossing the line between the two PEs necessilate communication.
PE 0
PE
S2
S Sg
with the sampled edges to generate minibatches (see Figure 1 Computing St, depends on the chosen sampling algorithm, such as the ones explained in Appendix [A.1] It has the advantage that doing a forward/backe backward pass does not involve any communication with other PEs after the initial minibatch preparation stage at the expense of duplicate work.
3 Cooperative Minibatching
In this section, we present two theorems that show the work of an epoch will be monotonically nonincreasing with increasing batch sizes. After that, we propose two algorithms that can take advantage of this monotonicity. Due to lack of space, we provide their full proofs in Appendices A.2 and
Theorem 3.1. The work per epoch Elis [
required to train a GNN model using minibalch training is
monotonically nonincreasing as the batch size |5º| increases.
have the corresponding set S We can shrink 5 by removing random elements E So from it to get 5 (s). If we compare (5"- (s))² to St, will see that any difference will come from elements that are contained only in {s}s. If we count such elements for each E 5 and sum them, it will be bounded by |.S More concretely if we let S = S - {s} be a random subset of 50 with one element missing, we have:
Proof. (Idea) Given any random 5 and 1 2
Σ |s 1(S (s)) S s = -Is1 #E50
Σ 1(S {lti = |s'1ls s |SS $ES0
(4)
Empirical evidence can be seen in Figures 3 and In fact, the decrease is related the cardinality of the following set:
(²) = tw E S w E (s)) Ets e 5
(5)
When T(S*) equal to St, the work is equal well. In the next section, further investigate the effect of [T(S)) I]
In addition to the definition of T(S) above, if we define the following set Ty(S):
TX(S) {w s {s) n s's,s') S
(6)
Theorem 3.2. The expected subgraph size E||S'|] required to train a GNN model using minibatch training is concave function of batch size, |5%).
4

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. (Idea) Note that we have:
[T'(s)] -
Σ
IT'SS) (T()) (5 - E
5 CS"
|s*|+1=|s"|
= - 1)T (5 (T()
E ((T))
|
15
We have just shown that. EILT (SP)) monotonically nonincreasing as increases. we let S denole a random subset of S of size have:
|sa
(ST
E1S
As 1]|S is the sum of monotonically nonincreasing parts, we conclude that it is concave function of the batch size, 1.%.
So, the slope of the expected number of sampled vertices flattens as batch size increases, see the last row in Figure and the first row in Figure 6 Note that this implics work monotonicity as well.
3.1 Cooperative Minibatching
As explained in Section 2 Independent Minibatching can not take advantage of the reduction in work with increasing global batch sizes and number of PEs, because uses separate small, local, batches sizes on each PE for each step of training. On the other hand, one can also keep the global batch size constant, 6P - and vary the number of processors P. As P increases, Independent Minibatching will perform more and more duplicate work because the local batch size is a decreasing function, b = s5 P. of P.
Algorithm Cooperative minibatching
Input: seed vertices Sp for each PE p P, # layers L for all I E (O...., I, 1} do (Sampling)
for all E P do in parallel
Sample next layer vertices 5t+1 and edges Ey for St.
all-to-all to redistribute vertex ids for 5141 to get S1+1 for all E P do in parallel (Feature Loading)
Load input features H. from Storage for vertices sp all-to-all to redistribute H to get H for all / e {L- 1--1 1,...,0} 0} do (Forward Pass) for all P do in parallel
if l < L then
all-to-all to redistribute Hi+1 to get Hr+1
Forward pass on bipartite graph 51+1 + St with edges E,, input A8t1 and output H
for all E P do in parallel
Compute the loss and initialize gradients G
for all E (O...., L 1} do (Backward Pass}
for all p E P do in parallel
Backward pass on bipartite graph Sy + 3(++) with edges Ey input Go. and output Gl+1 if [++1+ L then
all-to-all to redistribute G/+1 to get G++1
Here, we propose the Cooperative Minibatching method that will take advantage of the work reduction with increasing batch sizes in multi-PE settings. In Cooperative Minibatching, a single global batch of size bP will be processed by all the P PEs in parallel, eliminating any redundant. work across PEs.
5

---

Published in Transactions on Machine Learning Research (01/2025)
We achieve this as follows: we first partition the graph in 1D fashion by logically assigning each vertex and its incoming edges to PFs as V, and Ep for each PE Next, PE, samples its batch seed vertices Sy from the training vertices in vp for = 0 of size b. Then using any sampling algorithm, PE p samples the incoming edges Ep from Ep for its seed vertices. Each PE then computes the set of vertices sampled - = {t (t + s) E E,). Note that, -/+1 has elements residing on different PEs. The PEs exchange the vertex ids 5/+1 so that each PE receives the set St+ E Vp. This process is repeated recursively for GNN models with multiple layers by using S/+1 the seed vertices for the next layer. The exchanged information is cached to be used during the
passes.
For the forward/ herward/backward backward passes, the same communication pattern used during cooperative sampling is used to send and receive input and intermediate layer embeddings before each GNN layer invocation. Algorithu [ details cooperative sampling and cooperative forward/ forward/backward backward passes for a single GNN training iteration. Independent minibatching works the same except that it lacks the all-to-all operations and has A/+1 A for any given variable A instead. The redistribution of vertices during sampling happens according to the initial graph partitioning and the rest of the redistribution operations follow the same communication pattern, always converting variable A into At+1 during the forward pass and A into A!+1 during sampling and the backward passes for any variable A. Cooperative Minibatching was first proposed in Balin et al. (2022 2023) and was later re-discovered in Polisetty et al. (2023) as Cooperative Training, which was used during the feature loading and the forward/ bbckkard passes of their work while sampling of each minibatch was performed on a single CPU thread and the edges were split among the GPUs. We refer the reader to Appendix A.10 to see the relation between the approach proposed here and the work of Jia al. (0200) redundancy-free GCN aggregation.
Table 1: Algorithmic complexities of different stages of GNN training at layer 0 L with L total layers and batch size B = | with P PFs. Note that 1s (B) = (B)) [B.) [B)) since the PFs process the partitioned subgraphs. Feature loading happens only at layer L.
Stage
Independent
Cooperative
Sampling
Feature loading
OQJ5 4 de) O(M(S' (B), 51+1
(B)
Forward/ Forward/Backward /Backward
B
(D)
(
Complexity Analysis: Let M(V, E. V2) denote the work to process bipartite graph 1/2 + Vi with edges E' for a given GNN model M. Assuming cross PE communccation bandwidth a, Storage (e.g., disk, network, or DRAM) to PE bandwidth as 3 and PE memory bandwidth 7, and cache miss rate p. we have the time complexities given in Table I to perform different stages of GNN training per PE. We also use d for embedding dimension and c for the cross edge ratio, note that e P=1 for random partitioning, and smaller for smarter graph partitioning with P standing for the number of PEs. Also the sizes of Št become smaller when graph partitioning is used due to increased overlap.
We see that 7 R 2 TB/s, 2020ah. Due to a being relatively fast compared to Åे and 3, our approach brings performance benefits. On newer systems, the all-to-all bandwidth continues to increase (NVIDIA 2023 decreasing the cost of cooperation on a global mini-batch. However, on systems where the interconnect does not provide full bandwidth for all-to-all operations, our approach is limited in the speedup it can provide. Our approach is most applicable for systems with relatively fast all-to-all bandwidth compared to M and 3 and large P. In particular, starting from P 2, cooperative starts to outperform independent. even on F/B with the mag240M dataset and the R-GCN model in Section and Tables and More discussion on this topic can be found in Appendix A.6
300 GB/s and 8 x 30 GB/s in today's modern multi-GPU systems (VVIIIA
6

---

Published in Transactions on Machine Learning Research (01/2025)
k=2
3
r==0.7
k=2
3
r==0.6
k=2
3
n=00.5
2
2
2
3
3
3
4
r
4
r4=0.55
4
r4=0.8
d==3
d==3
d==3
2
2
5
n=00.
4
5
n=003
4
5
n==0.2
d2=4
2
d2=4
d2=4
6
n=00.6
6
r==0.65
6
r==0.7
n=0.9
n=0.6
n=0.3
Figure 2: A smoothed dependent minibatching example for x = 2. The middle minibatch is interpolated between the two independent minibatches on the left and the right by interpolating the random numbers used during sampling.
3.2 Cooperative Dependent Minibatching
Just as any parallel algorithm can be executed sequentially, we can reduce the number of distinct data accesses by having a single PE process b-sized parts of a single xb-sized minibatch for K iterations. In light of Theorems 3.1 and 3.2 consider doing the following: choose K E Z=, then sample batch 5 of size wb, Le., kb | to get 50 ,...., SL. Then sample к. minibatches Sp, of size b = |S from this batch of size sb to get St. , Vi E {0, R 1). In the end, all of the input features required for these minibatches will be subset of the input features of the large batch, i.c. S C S Vi,j. This means that the collective input feature requirement of these batches will be 18 the same our batch of size xb. Hence, we can now take advantage of the concave growth of the work in Theorem 3.2 and Figure 3
Note that, if one does not use any sampling algorithms and proceeds to use the full neighborhoods, this technique will not give any benefits, as by definition, the I-hop neighborhood of a batch size sb will always be equal to the union of the I-hop neighborhoods of batches sizes b. However for sampling algorithms, any overlapping vertex sampled by any two batches of sizes b might end up with different random neighborhoods rosulting in larger number of sampled vertices. Thus, having single large batch ensures that only single random set of neighbors is used for any vertex processed over period of k batches.
The approach described above has a nested iteration structure and the minibatches part of one k group will be significantly different than another group and this might slightly affect convergence. In Appendix A.7 we propose an alternative smoothing approach that does not require two-level nesting and still takes ad vanlaaee of the same phenomenon for the NS and LABOR sampling algorithms.
The main idea of our smoothing approach is as follows: each time one samples the neighborhood of vertex, normally it is done independently of any previous sampling attempts. If one were to do it fully dependently, then one would end up with an identical sampled neighborhood at each sampling attempt. What we propose is to do something inbetween, so that the sampled neighborhood of a vertex changes slowly over time. The x and after every к iterations, one gets fully independent new random neighborhoods for all vertices, see Figure g We will experimentally evaluate the locality benefits and the overall effect of this algorithm on convergence in Sections 4.2 and 4.3.1 and more details on our smoothing approach discussed in Appendix A.7
speed of change in the sampled neighborhoods is 1
3.3 Relation to subgraph sampling methods
Existing subgraph sampling met methods Chiang et al. 2019 Zeng et al. (2020): Hu el al. (202bb: Zeng el al. (202)): Fey et al.] [2021): Shi et al. (2023) randomly sample a subset S of the vertices and use the same subset for all layers of GNN training,
5 = SL. The edges Se used for training are obtained by taking the vertex induced subgraph Sg (t- + (t E EAt, 5}. We utilize the same observation
Theorems 3.1 and 3.2 and state:
7

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 3.3. The expected sompled subgraph density E|l is nondecreasing the batch size
|S] increases.
Thus, having multiple PEs cooperate and work larger minibatch together instead of processing independent smaller minibatches is theoretically expected to converge faster, as the higher density leads to better approximations. The proof of Theorem 3.3 is provided in Appendix A.4
4
Experimental Evaluation
We first compare how the work to process an epoch changes w.r.t. to the batch size to empirically validate The- orems 3. and 3.2 for different graph sampling algorithms. Next, we show how dependent batches introducod in Section 3.2 benefits GNN training. We also show the runtime benefits of cooperative minibatching compared to independent minibatching in the multi-GPU setting. Finally, we show that these two techniques are orthogonal, can be combined get multiplicative savings. Table 2 experiments. Details our experimental setup can be found in Appendix A.5
lists details of the datascts we used in
Table 2: Traits of datasets used in experiments: numbers of vertices, edges, avg. degree, features, cached vertex embeddings, and training, validation and test vertex splits. Last column has # minibatches in an epoch during model training with 1024 batch size including validation.
Dataset
V
E
E
# feats.
cache size
train val test (%)
# minibatches
[V]
flickr
89.2K
900K
10.09
500
70k
50.00
25.00 25.00
65
yelp
717K
14.0M
19.52
300
200k
75.00
10.00 15.00
595
reddit
233K
115M
493.56
602
60k
66.00
10.00 24.00
172
papers100M
111M
3.2B
29.10
128
2M
1.09
0.11 - 0.19
1300
mag240M
244M
3.44B
14.16
768
2M
0.45
0.06 0.04
1215
4.1 Demonstrating monotonicity of work
We use three sampling approaches, NS, LABOR, and RW, to demonstrate that the work to process an epoch decreases as the batch size increases for the 3 layer case across these three different classes of sampling algorithms. We carried out evaluation in two problem settings: node and edge prediction. For node prediction, batch of training vertices sampled with given batch size. Then, the graph sampling algorithms described in Appendix A.1 are applied to sample the neighborhood of this batch. The top s
of Figure 3 shows how many input vertices required on average to process an epoch, specifically [S" For edge prediction, we add reverse edges to the graph making it undirected and sample batch of edges. For each of these edges a random negative edge (an edge that is not part of E)) with one endpoint coinciding with the positive odge is sampled. Then, all of the endpoints these positive and negative edges are used seed vertices to sample their neighborhoods. The bottom row of Figure shows E||S*I].
We that in all use cases, datasets and sampling algorithms,, the work to process epoch is monotonically decrcasing as we proved in Theorem 3.1 We also see the plot of the expected number of vertices sampled, 1]
], is concave with respect to batch size as we already know from Theorem 3.2
Another observation that the concavity characteristic of E||S seems to differ for different sampling algorithms. In increasing order of concavity we have RW, NS, LABOR-0 and LABOR- The more concave a sampling algorithm's I] curve the less it is affected from the NEP and more savings are available through the of the proposed methods in Sections 3.1 and 3.2 Note that the differences would grow with larger choice of layer count L.
4.2 Dependent Minibatches
We vary the batch dependency parameter λ introduced in Section 3.2 for the LABOR-0 sampler with a batch size of 1024. Our expectation is that consecutive batches become more dependent. each other,

---

Published in Transactions on Machine Learning Research (01/2025)
mag240M
papers100M
yelp
reddit
700
250
150-
predictin
200
500
125
400
150
100
300
100
75-
200
50-
50-
100
20000
40000
20000
40000
60000
20000
40000
60000
40000
60000
1e7
batch size
167
batch size
3e55
batch size
batch size
5-
-4-
RIV
6-
E15"1) predictinn
LABOR-O
LABON-0
LABOR=
LABORU
3-
4-
1.5
3-
1.0
2-
1-
0.5
1-
20000 40000 60000
20000
40000
60000
20000
40000
60000
20000
40000
60000
batch s2z
batch size
batch size
batch size
E1|s. (sec Theorem 3.1 for
Figure 3: Monotonicity of the work. x-axis shows the batch size, y-axis shows
[89]
node prediction (top row) and F[[[S|]] (see Theorem 3.2 for edge prediction (bottom row), where E. | denotes the expected number of sampled vertices in the 3rd layer and |St| denotes the batch size. RW stands for Random Walks, NS for Neighbor Sampling, and LABOR-0/* for the two different variants of the LABOR sampling algorithm described in Section 2.2
reddit
papers100M
yelp
flickr
velitaeion ?1sscore sempling
0.96
0.68
0.60
0.53
16
0.95
0.64
0.55
0.51
64
0.94
0.62
0.50
0.50
236
0.93-
16
16
0.45
0.58
256
256
0.48
0.92
0.56
0.47
0
2500
5000
7500
10000
12500
20000
40000
60000
80000
10000
20000
30000
40000
1000
2000
3000 4000 5000 step
step
step
Figure 4: The validation F1-score with NS sampled neighborhoods trained with the LABOR-0 sampling algorithm with 1024 batch size and varying x dependent minibatches, meaning the neighborhood sampled for a vertex stays static during training. See Figure 5a for cache miss rates. See Figure for the training loss and Fl-score with the dependent sampler.
denotes infinite dependency,
the subgraphs used during consecutive steps of training would start overlapping with each other, in which case, the vertex embedding accesses would become more localized. We attempted to capture this increase in temporal locality in verlex embedding accesses by implementing an LRU cache to fetch them, the cache sizes used for different datasets is given in Table 2 Note that the cache miss rate is proportional to the amount of data that needs to be copied from the vertex embedding storage. The Figure 55 shows that as k increases, the cache miss rate across all datasets drops. On reddit, this is a drop from 64% to 16% on, [ a 4x improvement. We also observe that the improvement is monotonically increasing as a function of [V] given in Table 2 Table 3 and Figure show that training is not negatively affected across all datasets up lo k = 256 with less than 0.1% Fl-score difference, after which point the validation Fi-score with w/o sampling starts to diverge from the k = 1 case. Runtime benefits of this approach can be observed by comparing the Cache and Cache, & columns in Table ! Appendix ( additional discussion about the effect of varying and the last column of Table 2 shows the number of minibatches in epoch during training.
9

---

Published in Transactions on Machine Learning Research (01/2025)
Table 3: Test Fl-scores at the highest validation F F'l-score corresponding to Figure using early stopping. Averages of 40 runs are presented.
reddit
papers100M
yelp
flickr
96.72 +: 0.06
66.58 + 0.17
63.40 0.18
53.82 1 0.21
4
96.71 + 0.05
66.60 = 0.13
63.39 + 0.19
53.87 + 0.18
16
96.70 + 0.05
66.58 0.20
63.42 0.18
53.90 + 0.17
64
96.67 + 0.05
66.55 = 0.20
63.35 + 0.18
53.88 + 0.20
256
96.65 + 0.06
66.56 0.14
63.35 0.19
53.86 = 0.24
95.01 + 0.30
66.46 + 0.15
62.88 + 0.18
53.84 + 0.19
0.0
caene miss rate
cathe mibs rate
0.4
0.4
0.2
0.2
0.0
0.0
reddit
papers100M
yelp
mag240M
paperS100M
datasct
dataset
(a) 1 GPU, cache sizes are listed in Table
(b) 4 cooperating GPUs, each having a cache of size 1M.
Figure 5: LRU-cache miss rates for LABOR-0 sampling algorithm with 1024 batch size per GPU and varying k dependent minibatches, K = oo denotes infinite dependency.
4.3 Cooperative Minibatching
We use our largest datasets, mag240M and papers100M, as distributed training motivated by large-scale datasets. We present our runtime results on systems equipped with NVIDIA GPUs, with and A100 80 GB (NVIDIA 2021) and 16 V100 32GB (NVIDIA) 2020b), all with NVLink interconnect between the GPUs (600 GB/s for A100 and 300 GB/s for V100). The GPUs perform all stages of GNN training and the CPUs only used to launch kernels for the GPUs. Feature copies are performed by GPUs well, accessing pinned fcature tensors over the PCI-e using zero-copy access. In cooperative minibatching, both data size and computational cost are shrinking with increasing numbers of GPUs, relative to independent minibatching. We use the GCN model for papers100M and the R-GCN model (Schlichtkrull et al. 2017) for mag240M. As seen in Table $ cooperative minibatching reduces all the runtimes for different stages GNN training, except for the F/B (foward/bbackwar /backward) times on papers100M where the computational cost is not high enough to hide the overhead of communication.
If we take the numbers in the Total columns from Table divide independent runtimes by the corresponding cooperative ones, then we get Table 5 We can see that the thcoretical decrease in work results in incrcasing speedup numbers with the increasing number of PFs, due to Theorem 3.1 We would like to point out D that 1S0 curves in Figure 3 are responsible for these results. With PEs and |Sa| global batch size, the
work performed by independent minibatching vs cooperative minibatching can be compared by looking - 115 x S respectively.
We also experiments that show that graph partitioning using METIS Karypis & Kumar 1998 prior to the start of training can help the scenarios where communication overhead is significant. The forward-backwan time decreases from 13.0ms to 12.0ms on papers100M with LABOR-0 on 4 NVIDIA A100 GPUs with partitioning due to reduced communication overhead using the same setup as Table
Increasing the number of GPUs increases the advantage cooperative minibatching compared to independent minibatching, The forward-back 194, 187 and 183 with 1, 2, 3 and 4 cooperating GPUs, respectively measured the NVIDIA DGX
time on mag240M with LABOR-0 200 (same independent baseline),
10

---

Published in Transactions on Machine Learning Research (01/2025)
Table 4: Cooperative vs independent minibatching runtimes per minibatch (ms) on three different systems with and 8 NVIDIA A100 80 GB GPUs, and 16 NVIDIA V100 32GB GPUs. I/C denotes whether independent or cooperative minibatching used. Samp, short for Graph Sampling, Feature Copy stands for vertex embedding copies PCI-e and Cache denotes the runtime of copics performed with cache that can hold 10 vertex embeddings per A100 and 5 10y per V100. к denotes the use of batch dependency haward/backwarr. backward. Total time is computed by the fastest available Feature Copy time, the sampling time, and the F/B time. |Sa| is the global batch size and the the batch size per GPU. a stands for cross GPU communccttio bandwidth (NVLink), 3 for PCI-e bandwidth and y for GPU global memory bandwidth. Green was used to indicate the beller result between independent and cooperative minibatching, while Bold was used to highlight the feature copy time included the Total column.
K = 64. F/B means forward/
# GPUs, Y a, 8, |
Dataset & Model
Feature Copy
Sampler
I/C
Samp.
F/B
Total
Cache
Cache,
K
Indep
21.7
18.4
16.8
11.2
8.9
41.8
LABOR-O
4 A100
paPers100M GCN
Coop
17.7
14.0
10.1
5.8
13.0
36.5
2TB/s
Indep
16.1
26.5
22.1
10.1
48.3
NS
a = 600GB/s
Coop
11.9
21.3
12.9
15.0
39.8
64GB/8 | 212
Indep
26.0
57.9
56.0
41.0
199.9
266.9
LABOR-0
mag240M R-GCN
Coop
20.0
51.1
36.9
23.4
183.3
226.7
b 1024
Indep
14.4
78.0
71.2
223.0
308.6
NS
Coop
12.3
73.9
47.5
215.6
275.4
Indep
21.3
21.1
18.7
12.0
9.3
42.6
LABOR-0
8 A100
papers100M GCN
Coop
16.5
12.4
7.1
4.0
13.5
34.0
= 2TB/s
Indep
15.8
31.0
24.5
10.3
50.6
NS
600GB/s
Coop
12.5
19.4
9.0
15.6
37.1
64GB/s | 23
Indep
30.6
70.1
66.2
46.8
202.1
279.5
LABOR-0
mag240M R-GCN
Coop
21.6
50.6
29.0
19.3
172.2
213.1
b 1024
Indep
15.0
94.9
80.9
224.8
320.7
NS
Coop
14.9
71.6
39.6
209.0
263.5
Indep
39.1
44.5
40.2
29.4
15.1
83.6
LABOR-0
16 V100
papers100M GCN
Coop
26.9
22.7
10.4
4.9
19.1
50.9
Y 0.9TB/s
Indep
18.0
61.3
52.0
16.2
86.2
NS
300GB/s
Coop 19.2
34.9
13.0
21.3
53.5
8 32GB/s
Indep
50.8
128.8
121.3
96.2
156.1
303.1
LABOR-0
|S = 213
mag240M R-GCN
Coop 29.2
78.1
42.8
23.5
133.3
186.0
512
Indep 19.3
167.3
152.6
170.9
342.8
NS
Coop
19.3
116.1
53.1
160.4
232.8
Table Runtime improvements of Cooperative Minibatching over Independent Minibatching compiled from the Total column of Table This is a further improvement on top of the speedup of independent minibatching already achieves using the same number GPUs.
Dataset & Model
Sampler
4 GPUs
8 GPUs
16 GPUs
LABOR-0
15%
25%
64%
papers100M & GCN
NS
21%
36%
61%
LABOR-0
18%
31%
63%
mag240M & R-GCN
NS
12%
22%
47%
Station A100 machine with R-GCN. When using a different GNN model such as GATs (Velicković et al., 2018), the forward-backward runtime 190 ms on GPU 172 ms on GPUs on mag240M The decrease runtime with increasingly cooperating GPUs is due to the decrease in redundant work they have perform. Even though the batch size per GPU is constant, the runtime goes down similar to the plots in the top
11

---

Published in Transactions on Machine Learning Research (01/2025)
of Figure except that it follows, with fanout ko is used.
kB|15"D
the average number of edges in the 3rd layer when a sampler 199 11
Additionally, we demonstrate that there is no significant model convergence difference wetween independent. vs cooperative minibatching in Appendix A.9 A.9
4.3.1 Sopperative-Dependeen Minibatching
Table 6: Runtime improvements of Dependent Minibatching, for Independent and Cooperative Minibatching methods, compiled from the Cache, R and Cache columns of Table 4 with LABOR-0. Making consecutive minibatches dependent increases temporal locality, hence reducing cache misses.
Dataset & Model
I/C
CPUs
8 GPUs
16 GPUs
Indep + Depend
50%
57%
37%
papers100M & GCN
Coop + Depend
74%
78%
112%
Indep Depend
37%
41%
26%
mag200M & R-GCN
Coop + Depend
58%
50%
82%
We use the same experimental setup as Section 4.3 but vary the x parameter to show that cooperative minibatching can be used with dependent batches (Figure 5bp. We use a cache size of 1M vertex embeddings per GPU. Cooperative feature loading effectively increases the global cache size since each PE (GPU) caches only the vertices assigned to them while independent feature loading can have duplicate entries across caches. For our largest dataset mag240M, cache miss rates were reduced by more than 2x, making the total improvement 3x. Runtime results for k E (1, 256) are presented in Table the Feature Copy Cache and Cache, k columns. Table s summarizes these results by dividing the runtimes in Cache by Cache, k. and reporting percentage improvements.
top of 1.4x reduced work due to cooperative minibatching alone, the
5 Key insights of Cooperative Minibatching
In Section [] the work l(( to process an epoch (full pass over the dataset) for a given minibatch size |Sa] is characterized by the number of minibatches in epoch IV| x the amount of work to process single [
minibatch, which is approximated by the sum of the number of sampled vertices in each layer (E/1 (S
This can be seen in Equation (3)
Equation 3 only considers the number of processed vertices and it is good enough for our purposes. Since all the sampling algorithms we consider in Section 2.2 have fanout parameters k the number of edges sampled for each seed vertex has an upper bound So, given vertices S for the ith layer, the number of sampled odges in that same layer will be I k/S"|. Clearly for almost any GNN model, the runtime complexity process layer l is linearly increasing w.r.t. the number of vertices (IS')) and edges (W kJS')) processed, so the runtime complexity is O(IS') + s) O(S')).
A more comprchensive analysis of the runtime complexities of Cooperative and Independent Minibatching approaches is provided in Appendix A.6 taking into account the exact numbers of sampled vertices (IS*), edges (IE'), and various communication bandwidths (a, 7, (8) and even graph partition quality c and cache misses p.
As Cooperative Minibatching considers a single minibatch of size B for all P PEs, the growth of the number of sampled vertices and edges is characterized by B as the minibatch size. In contrast, Independent Minibatching assigns different minibatches of sizes & to each PE, the growth of the sampled vertices and edges is characterized by as the minibatch size. Due to Theorems 3.1 and 3.2 the work W(B) with respect to minibatch size B is a concave function, we have W(B) < PW H); meaning that Cooperative Minibatching is theoretically faster than Independent Minibatching, if communication between PEs is infinitely fast. For empirical data, can look at the first-row of Figure 3 at the æ-axis B for Cooperative and for Independent,
12

---

Published in Transactions on Machine Learning Research (01/2025)
due to:
B 6 P W(B) PW
W(B) W(P) P
E||
as proven by Theorem 3.1 As |S" curves in Figure are docreasing, the work of Cooperative Minibatching is significantly less than Independent Minibatching, Finally, modern multi-GPU computer systems have very fast int communication bandwidths, e.g. NVLink, which is why we are able to show favorable results compared to Independent Minibatching despite performing scemingly unnccessary commuicatiinn.
6 Conclusions
In this paper, we experimentally and theoretically demonstrated that the cost of processing minibatch is a concave function of batch size in GNNs, unlike DNNs where the cost scales linearly. We then proposed two approaches to take advantage of cost concavity. The first approach, which we call cooperative minibatching proposes to partition a minibatch between multiple PEs and process it cooperatively. This is in contrast. to existing practice of having independent minibatches per PE, and avoids duplicate work that is a result of vertex and edge repetition across PEs. The second approach proposes the use of consecutive dependent minibatches, through which the temporal locality of vertex and edge accesses is manipulated. As batches get more dependent, the locality increases. We demonstrated this increase in locality by employing an LRU-cache for vertex embeddings on GPUs. Finally, we showed that these approaches can be combined without affecting convergence, and speed up multi-GPU GNN training by up to 64%.
Acknowledgements
We would like to thank Kaan Sancak for their feedback the manuscript, and also Murat Guney for their helpful discussions and for enabling this project during the author's time at NVIDIA Corporation. This work was partially supported by the NSF grant CCF-1919021.
References
Zeyuan Allen-Zhu and Flad Hazan. Variance reduction for faster non-convex optimization. In Proceedings of The 33rd International Conference on Machine Learning, pp. 699 707. PMLR, 20 22 Jun 2016. URL https://proceeddnng mlr, prwss//48/allenn wataan-hhal....... html
1. Artico, 1. Smolyarenko, V. Vinciotti, and E. C. Wit. How rare are power-law networks really? In Royal Society, volume 476, 2020. URL http::/doi. org/10 1098/rspa. 2019
Muhammed Fatih Balin and Úmit Çatalyürek. Leyer-neighbor sampling defusing neigh- borhood explosion in gnns. In Advances in Neural Information Processing Systems, vol- ume 36, 2023. URL
neurips cc/paper_ faaarrfflls///eee http:/pappe////11//12 ff00 PoneeeeeePaaaee--ooeeeeeeeeeee pdf Also available as a Tech Rep on ArXiv.
Muhammed Fatih Balin, Dominique LaSalle, and Ümit V. Çatalyürek. Cooperative minibatching, August 2022. URL
Muhammed Fatih Balin, Dominique LaSalle, and Ümit V. Çatalyürek. Cooperative minibatching in gnns, Jan 2023. URL
http://twhw...cmmo///oaaaaaa/aaa httpa////i...ii//////////aaaaaaa httpollcc/ppppr///6/10 Choperative__Mmniatchhhiin .pff] ICML Submission #6621. (Rejected).
D.P. Bertsckas. Incremental least squares methods and the extended kalman filter. In Proceedings of 1994
33rd IEEE Conference on Decision and Control, volume 2, pp. 1211-1214 vol.2, 1994. doi: 10.1109/CDC. 1994.411166.
13

---

Published in Transactions on Machine Learning Research (01/2025)
Zhenkun Cai, Qihui Zhou, Xiao Yan, Da Zheng, Xiang Song, Chenguang Zheng, James Cheng, and George Karypis. Dsp: Efficient gnn training with multiple gpus. In Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP '23, pp. 392 404, 2023. 35777528.
doi:
Wei Lin Chiang, Yang Li, Xuanqing Liu, Samy Bengio, Si Si, and Cho Jui Hsieh. (Custer-GNN: An efficient algorithm for training deep and large graph convolutional networks. Tn Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Minóng, pp. 257-266. Association for Computing Machinery, jul 2019. doi: 111145/3292500.
Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. One trillion edges: Graph processing facebook-scale, Proc. VLDB Endow., 8(12):1804-1815, aug 2015. doi:
011,7778/222243222224007
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc Le, and Andrew Ng. Large scale distributed deep networks. F. Percira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), Advances in Newral Information Processing Systems, volume 25. Curran Associates, Inc., 2012. URL htttps://proceedinggg wtwpeeeeddinnnn.e.iisseee neurips.er..m cc/ pdf
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Reseavch, pp. 3294 3304. PMLR, 18 24 Jul 2021. URL httts::/ppooceedings mlr. pttpp//e19//ee///////// 2tmmllll..mmmm
Swapnil Gandhi and Anand Padmanabha Iyer. P3: Distributed deep graph learning at scale. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pp. 551-568, 2021.
Boris Ginsburg, Igor Gitman, and Yang You. Large batch training of convolutional networks with layer- wise adaptive rate scaling. Technical Report arXiv:1708.0388 ArXiv, September 2017. URL http:
aatp///a.////..../. 11111708003300 03888
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. Technical Report arXiv:1706.02677, ArXiv, April 2018. URL http://arxiv. httt:://axxv.orrr/bbb///t
02677
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pp. 1025-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Newral Information Processing Systems, (eeoeeeeeeNeurrS)
2020a.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-lsc: A large-scale challenge for machine learning on graphs, 2021. URL https://arxii...... wwwpsiiv.orrgeoooooo httgg/ab/211000 014310943300000
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous Graph Transformer. The Web Conference 2020- Proceedings of the World Wide Web Conference, WWW 2020, pp. 2704-2710, 2020b. doi: 10. 10.1145/33668 0333664233330002,,
Zhihao Jia, Sina Lin, Rex Ying, Jiaxuan You, Jure Leskovec, and Alex Aiken. Redundancy-free computation for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, pp. 997 1005. Association for Computing Machinery, 2020. URL https:///oi..og 000...11///3946.4000000
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 207:1 17921, nov 2022. doi: 22.1066/.eewa..2222.11777
14

---

Published in Transactions on Machine Learning Research (01/2025)
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. STAM Journal on Scientific Compuling, 20(1):359-333) 1998. doi: 10.113//5106682755222777777
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On harge-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv::6090 669.048866 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL https:
//arxiv.org httpi/.orrgbbb///11111 6980
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '14, pp. 661-670, 2014. doi: 10.1145 00055//22233.22233666
Zhiqi Lin, Chong Li, Youshan Miao, Yunxin Liu, and Yinlong Xu. Pagraph: Scaling gun training on large graphs via computation-awarr caching. In Proceedings of the 11th ACM Symposium on Cloud Compuling, SoCC '20 pp. 415, 2020. doi: 11144//319111.3422223
Yajing Liu, Zhengya Sun, and Wensheng Zhang. Improving fraud detection via hierarchical attention- graph neural network, 2022.
Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R. Devanur, Gregory R. Ganger, Phillip B. Gibbons, and Matei Zaharia. Pipedream: Generalized pipeline parallelism for dnn training. In Proceedings of the 27th ACM Symposium on Operaling Systems Principles, SOSP '19, pp. 1 15, 2019. doi: 04.145/3341301.33355
NVIDIA. NVIDIA DGX A100 system architecture: The universal system for Al infrastructure. Tech- nical report, NVIDIA Corporation, July 2020a. URL httph/ht/::/www..iiddd wttp:://wwwwwwiia....m.. www.:.vviiiiii.. com/ /wtp///t/dd//ennntttnn///
pdf
NVIDIA. NVIDIA V100
datasheet.
Technical report, NVIDIA Corporation, Jan-
uary 2020b.
URL https://tmage..nvida.. www.iiiiiiico.mmm wwt..aaaa..c//ocoattteeeeeeeeeee aww.aaacowrroooooeee//eeeeellled
volta-vio0-dataaai update us- 1as-165301-r6...
NVIDIA. NVIDIA A100 tensor core GPU datasheet. Technical report, NVIDIA Corporation, June 2021. nvidia- avidia-al00- aal0:odatceeeeeet--aaaaaaaaa-1--
NVIDIA. NVIDIA DGX H100: The gold standard for Al infrastructure. Technical eichnicallrpport... NVIDIA Corpora- tion, March 2023.
NVIDIA. NVIDIA GB200 NVL72: Powering the new era of compuling Technical Technpallliinnneiiiiaaaalllll March 2024. URL http:///s/ww.aaaaaaa....///////r
NVIDI NVIDIA Corporation,
Yeonhong Park, Sunhong Min, and Jae W. Lee. Ginex: Ssd-enabled billion-scale graph neural network training on a single machine via provably optimal in-memory caching. Proc. VLDB Endow., (6(11):2626222) jul 2022. ISSN 2150-8097. doi: 10.14778/3551198.5555
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NewrIPS, 2019.
Vatsal Patel, Sutharshan Rajasegarar, Lei Pan, Jiajun Liu, and Liming Zhu. Evangen: Evolving graph deep neural network based anomaly detection in blockchain. In Weitong Chen, Lina Yao, Taotao Cai, Shirui Pan, Tao Shen, and Xue Li (eds.), Advanced Data Mining and Applications, pp. 444-456, 2022.
Sandeep Polisetty, Juelin Liu, Kobi Falus, Yi Ren Fung, Seung-Hwai Lim, Hui Guan, and Marco Serafini. Gsplit: Scaling graph neural network training on large graphs via split-parallelim,, 2023.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks, 2017.
Zhihao Shi, Xize Liang, and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference Learning Representations, 2023. URL https
//openreview.net// wtt.://wwww.tttrrrrrrdd/e/A/aaA
Alok Tripathy, Katherine Yelick, and Aydın Buluç. Reducing communication in graph neural network training. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2020.
Petar Veličković, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Lió, and Yoshua Bengio.
Graph attention networks. In International Conference on Learning Representations, 2018, URL https //openreview.netee http://www.tttoooommmrrraaaaaaaa
Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman. Mariusgnn: Resource- efficient out-of-core training of graph neural networks, 2022.
Minjic Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang, Deep graph library: A graph-centrie, highly-performant package for graph neural networks, 2019. URL https:
//axxiv.org/ab//10. ottg//bb//99..01/33333
D Randall Wilson and Tony R Martinez. The general inefficiency of batch training for gradient descent. learning. Neural networks, 16(10):1429 1451, 2003.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: A survey, 2020.
Nuo Xu, Pinghui Wang, Long Chen, Jing Tao, and Junzhou Zhao MR-GNN: Multi-resolution and dual graph neural network for predicting structured entity interactions. In Proceedings of the Twenty-Eight International Joint Conference on Artificial Intelligence, aug 2019. doi: (0.24963/ijcal) /jjccai2009/551
Rex Ying, Ruining He, Kaifeng Chen, Pong Fksombatchai, 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 and Data Mining, KDD '18, pp. 974-983, 2018. doi: 11144//3211199322
Hanqing Zeng. Hongkuan Zhou, Ajilesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020. URL https:///peereeveww het:/forunndd-Beeppte..
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL htttp:://pppteeeeee.eeee////
Da Zheng, Xiang Song, Chengru Yang, Dominique LaSalle, Qidong Su, Minjie Wang, Chao Ma, and George Karypis. Distributed hybrid cpu and gpu training for graph neural networks on billion-scale graphs. arXiv preprint arXio:2112. 15345, 2021.
Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. Aligraph: A comprehensive graph neural network platform. Proc. VLDB Endow., 12(12):2094 2105, aug 2019. doi: 10. 01.14778/3352063.333
16

---

Published in Transactions on Machine Learning Research (01/2025)
A Appendix
A.1 Graph Sampling
Below, we review three different sampling algorithms for minibatch training of GNNs, Our focus in this work is samplers whose expected number of sampled vertices function of the batch size. All these methods are applied recursively for GNN models with multiple layers.
A.1.1 Neighbor Sampling (NS)
Given a fanout parameter and a batch of seed vertices S NS by (Hamilton et al. 2017) samples the neighborhoods of vertices randomly. Given a batch of vertices S a vertex s S with degree d [N(s),, if d, S h; NS uses the full neighborhood N(s), otherwise it samples k random neighbors for the vertex
A.1.2 LABOR Sampling
Given a fanout parameter & and a batch of seed vertices 5 LABOR-0 (Balin & Çatalyürek 2023) samples
the neighborhoods of vertices follows. First, cach vertex rolls uniform random number 0 S 92 S 1. Given batch of vertices 5 verlex E S with degree d, = [s)], the edge (t + s) is sampled if r. S d, Since different sced vertices E 5 end up using the same random variate rt for the same source vertex t, LABOR-0 samples fewer vertices than NS in expectation.
&
The LABOR-* algorithm is the importance sampling variant of LABOR-0 and samples an edge (t - s) if ra E C,,,, where is importance sampling probabilities optimized to minimize the expected number of sampled vertices and c, is a normalization factor. LABOR-* samples fewer vertices than LABOR-O in expectation.
Note that, choosing & 2 max,ev d, corresponds to training with full neighborhoods for both NS and LABOR methods.
A.1.3 RandomWalk (RW) Sampling
Given a walk length o, a restart probability p, number of random walks a, a fanout k; and batch vertices So, a vertex e 5 Random Walk (Ying et al.) 2018)) starts from s and each step picks a random neighbor s' from N(s). For the remaining otherwise it is picked from ((s). This process is repeated a times for each seed vertex and lastly, the top k visited vertices become the neighbors of for the current layer.
1 steps, the next neighbor is picked from N(s') with probability 1 p,
Notice that random walks correspond to weighted neighbor sampling from a graph with adjaconcy matrix À Σi= A', where the weights of depend on the parameters a, p and k. Random walks give us the ability to sample from Á without actually forming Å.
A.2 Work Monotonicity Theorem
Theorem A.1. The work per epoch required to train a GNN model using minsbatch training monotonically nonincreasing the batch size increases.
Proof. Given any n 2 2, lct's say we uniform randomly sample without replacement 5 C V, where n | Now note that for any 500 C S", using the definition in (2), we have s C C,S.V V.. We will take advantage of that and define n0 50 (s) in following expression.
17

---

Published in Transactions on Machine Learning Research (01/2025)
Σ
1 = Σ
Σ WES!
1/w & s
$ES0 8 =S (fs}
&ES
=S ({+}
Σ
Σ "E(s)
1/w & s")
SE90 8 808
(8)
Σ
Σ
1/ $ (5), Vs' ST9]
SESO
wEfs}'
9 ===="((aa)
= Σ
Σ
1/2 & {s') Vs E 5o {s}]
WES! SESO WE{s}
In the last expression, for given S if there two different elements 8, S such that {s} and w {s')', then the indicator expression will be O. It will be 1 only if w {s} for unique E S So:
ΣΣ WES! SES" (E)
1/ $ (8), AA' E 5O [6]]=
Σ
1
WES' St
(9)
BIsES (a)
=w st
fs) s S 154
Using this, we can get:
Σ
|S 1S S S
8 CS" 1
|5-||-11
Σ
|S S |
S C |+1||1
| 1)
Σ
1S
8 S
18 |+1=
| - 1) S S E
|
E
<
|S
S
Since 5 was uniformly randomly sampled from V, its potential subsets S are also uniformly randomly picked from V as a result. Then, taking an expectation for the random sampling of 5 C V, we conclude that S s| i.e., the expected work of batch size is not greater than the work of batch of size S [5
1. This implics that the work with respoct to batch size monotonically nonincrcasing function. 0
A.3 Overlap monotonicity
Theorem A.2. The expected subgraph size E]JS'1] required to train a GNN model using minibatch training is concave function of batch size, |5%].
Proof. Given any n 2 2, let's say we uniformly randomly sample without replacement S C of size Note that the T and T3 as defined in Equations (5) and (6)
18

---

Published in Transactions on Machine Learning Research (01/2025)
-|
Σ
-T(
S CSO
+11151
= |S ( (5
- (s10) 1))T" 150
(10)
(5
(5
2 (59
|
1
S S
[5') |S
((()\
S
where the first equality above is derived similar to Equations between vertices increases as the batch size increases. Utilizing our finding from Equations have:
8 and 9 Overall, this means that the overlap
and
(9
we
Σ -
cs |1=1=1
- 159 (S')
(11)
| = E (
|
S|SS = FllS + ETT (S")
|S
Note that the last step involved taking expectations for the random sampling of S See the recursion embedded in the equation above, the expected size of the subgraph S with batch size |S depends on the expected size of the subgraph s" with batch size |S -1. Expanding the recursion, we get:
|sa
(SP)
EIS
(12)
(1T)
where S is random subset of S of size i. Since
is monotonically nonincreasing as increases as we showed in 110, we conclude that E|| is a concave function of the batch size, |Sº
A.4 Subgraph density monotonicity
Theorem A.3. The expected sampled subgraph density
E[Sa is nondecreasing the batch size increases.
Proof. Given n 2 1 and any probability distribution p V such that P. denotes the probability of including in our minibatch S of size [S] n. the probability of including the edge - s becomes PiP.. Since p.(n) is linear as function of n, Vs E V, it can be decomposed as pa(n) = p'n
S S
Σ P(EESΛ&ES)=
Σ
P.P.
Σ (t-b)EE
p.pp'n n
Σ P'P's
(13)
S
S
n.
({=S)EE
((-S)EE
((-s)EE
We can see that the expected sampled subgraph density is a linear function of the batch size |S| n and this implies that it is nondecreasing the batch size |S] increases.
19

---

Published in Transactions on Machine Learning Research (01/2025)
mag24DM
papers100M
yelp
reddit
1.0
(1151) -node prediction
1.5
0.4
1.0
0.2
20000
40000
60000
20000
40000
60000
20000
40000
60000
20000
40000
60000
batch
batch 9220
size
2000
2500
11N
RW
175
IWW
15
K5
N5
no:
prediction
LAZON-
LABOR
2000
LAB03-0
LABOK
LASON-0
LASON
150-
LABOR-0
LABOR
1500
250
1500
100
1000
1000
150
75-
100
50-
25
20000
40000
60000
20000
40000
60000
20000
40000
60000
20000
40000
60000
batch size
batch size
batch size
batch size
Figure 6: Monotonicity of the work. x axis shows the batch size, y axis shows E||sa for node prediction (top row) and 1 for edge prediction (bottom row), where E[]S*[] denotes the expected number of vertices sampled in the 3rd layer and |S denotes the batch size. RW stands for Random Walks, NS stands for Neighbor Sampling, and LABOR-O/* stand for the two different variants of the LABOR sampling algorithm described in Section 2.2 Completes Figure 3
150
A.5 Experimental Setup
Setup: In our experiments, we use the following datasets: reddit (Hamilton et al. 2017).
papers100M (Hu
et al. 2020a), mag240M (Hu et al.) 2021). yelp and flickr (Zeng et al. 2020), and their details are given in Table 2 We use Neighbor Sampling (NS) (Hamilton et al. 2017 ; LABOR Sampling (Balin & Çatalyürek 2023 and Random Walks (RW) Yinng et al. 2018) to form minibatches. We used fanout of A: 10 for the samplers. In addition, Random Walks used length of o = 3, restart probability p 0.5 and number of random walks from each seed = 100. All our experiments involve a GCN model with L = 3 layers (Hamilton cct al. 2017), with 1024 hidden dimension for mag240M and papers100M and 256 for the rest. Additionally, papers 100M and mag240M datasets were made undirected graphs for all experiments and this reflected in the reported edge counts in Table Input features of mag240M are stored with the 16-bit floating point type. We use the Adam optimizer Kingma & Ba 2014) with 10-3 learning rate in all the experiments.
Implementation: We implemented T our experimental code using C++ and Python in the DGL frame- work (Wang et al. 2019) with the Pytorch backend (Paszke et al. 2019). All our experiments were repeated 50 times and averages are presented. Early stopping was used during model training runs. So as we go to the right along the x-axis, the variance of our convergence plots increases because the number of runs that were ongoing is decreasing.
A.6 Complexity Analysis (cont.)
Our goal in this section is to empirically show the work reduction enjoyed by cooperative minibatching over independent minibatching by reporting the number of vertices and edges processed per PE. We also report the number of vertices that are communicated for cooperative minibatching during its all-to-all calls in Algorithm and Figure 7b. The results are given in Table 7
Looking at Tables D and 7 we make the following observations:
Source code is available at httpp::/githhbb www.commoaaaeeeeeeeeeee 2 "Copperative and dependent minitatching are also available GraphBoll GNN dataloading library.
20

---

G for cooperative to get speedup over Published in Transactions on Machine Learning Research (01/2025)
Commediitinn Wakmre acotvv to mpo rodel
Vilame Retorie
kppt nodas,
COmTTNA Valume Ralattve 12 post nollss
ferourd
Nanward
Bachward
Backoard
Forwarti
Narword
Balhatt
un secuuuii pare
Forwart
Feoward
Rockward
Rachward
Upcare
farwert
Eacoward
Uozals
Vilune Relitive
nodiindds, 2
(a) Independent Minibatching
(b) Cooperative Minibatching
Figure 7: A comparison of Independent and Cooperative Minibatching approaches in the feature loading and backwrd GNN stages. The thickness of the red arrows indicates the data volume. Due to redundant vertices across PEs, Independent Minibatching wastes (PCT-e) bandwidth for vertex embedding copies from Storage. Moreover, the PEs perform identical computations for redundant edges across PEs in Independent Minibatching.
Table 7: Average number of vertices and edges sampled in different layers with LABOR-0 per PE, reduced by taking the maximum over 4 PEs (All the numbers in thousands, lower is better) with batch size [Sa 1024. c|$*| shows the number of vertices communicated at layer 1. Papers and mag were used short versions of papers100M//CN and mag240M/R-GCN dataset model pairs respectively. Last column shows forward-backward (F/B) runtime in ms.
Dataset
Part.
I/C
|S$
c| S
|S$11
|E²]
S
c|
|S
EE
S
F
F/B
random
Indep
463
0
463
730
74.8
0
74.8
93.6
9.63
8.9
papers
random
Coop
318
311
463
608
62.4
56.8
82.8
89.9
9.28
13.0
metis
Coop
328
179
402
615
63.1
34.0
73.8
90.8
9.35
12.0
random
Indep
443
443
647
67.9
67.9
82.0
8.78
199.9
mag
random
Coop
324
310
459
566
59.8
53.1
77.3
80.4
8.62
183.3
metis
Coop
334
178
419
576
60.6
31.0
71.3
81.8
8.80
185.1
1. All runtime complexities for cooperative minibatching scales with [B) (B)) and (B)(B)) [E'( < (B)( and for independent minibatching with [5)( and [E'( |s'( for sampler with fanout Since EI(S (B)] concave function, [ S E and this corresponds to looking at Figure 3 first row with x = B for coop and x = P for independent if one wanted to guess how their runtime would change with changing and P. For an example, the runtime numbers we have provided in the Table | are for GPUs. Going from to 8 would increase the edge of cooperative over independent even more, Table
2. Sampling and Feature loading over PCI-e requires independent.
In order for cooperative F/B improve against independent, we need that g 3
4. Cross edge ratio reduces all communication between PEs. In particular, graph partitioning will lower both and (B)), lowering the communication overhead, see c| columns in Table 7
The model complexity M is small for the GCN model (papers100M) but large for the R-GCN model (mag240M), as shown by the F F/B runtime numbers in Table Also, the communication overhead between the scenarios similar, meaning communication can take from upto 30% less than a few percent depending M. For the papersl 00M dataset, communication makes up more of the D00
21

---

Published in Transactions on Machine Learning Research (01/2025)
runtime, so graph partitioning helps bring the F/B runtime down. However, the load imbalance caused by graph partitioning slows down the F/B runtime despite lowered communication costs for the mag240M dataset.
A.7 Smoothed Dependent Minibatching
As described in Section 2 NS algorithm works by using the random variate rts for each odge (t - s). Being part of the same minibatch means that single random variate rts will be used for each edge. To generate these random variates, we initialize Pseudo Random Number Generator (PRNG) with random seed along with and to ensure that the first rolled random number Yts from the PRNG stays fixed when the random seed z is fixed. Given random seeds and 22, let's say we wanted to use for the first k iterations and would later switch to the seed 22. This switch can be made smoothly by interpolating between the random seeds 21 and 22 while ensuring that the resulting sampled random numbers are uniformly distributed. If we are processing the batch number i < k. in the group of k batches, then we want the contribution of 22 to be c L, while the contribution of 2 is 1 1--c We can sample nis ~ (0 1) with seed 21 and ni, ~ >N(0, 1) with sced 22. Then combine them
CT Jmds + sin( 2
CR
(c)(c) cos(
2 )mi
note that n.. = n/, (1) = ni,, and (c) (0, 1), VC E also, then we can set Tts = (c)), where ((x) - P S x) for Z ~~ NO, 1), to get Tra ~ (0, 1) that the NS algorithm can use. Dropping 8 from all the notation above gives the version for LABOR. In this way, the random variates change slowly as we are switching from one group of batches to another. When i i= K, we let 21 <- 22 and initialize 22 with another random seed. To use this approach, only the random variate generation logic needs modification, making its implementation for any sampling algorithm straightforward compared to the nested approach initially described. Figure 2 shows an example of this approach for K =2
A.8 Dependent batches (cont.)
Looking at the training loss and validation Fl-score with sampling curves in Figure S we notice that the performance gets better as is increased. This is due to the fact that vertex's neighborhood changes slower and slower K is increased, the limiting case being K co, in which case the sampled neighborhoods are unchanging. This makes training casier so k = co case leads the pack in the training loss and validation F1- score with sampling curves.
A.9 Comparing a single batch vs P independent batches convergence
We investigate whether training with a single large batch P-GPU training shows any convergence differences to the current approach of using P separate batches for each of the GPUs. We use global batch size of 4096 and divide a batch into P < 8 independent batches, with each batch having a size of 4096 and LABOR-0 samplers with fanouts of k = 10 for each of the 3 layers. Figure g shows that there are no significant differences between the two approaches, we present the results averaged over the samplers to save space.
p We use NS
A.10 Redundancy Free GCN aggregation
Jia et al. (2220) proposes method of reducing processing during neighborhood aggregation by finding common sub-neigliborhoods among aggregated vertices, whether using full-batch minibatch training. That is, if two vertices have the neighborhoods {A, B,C) and {B, C, D), and a summation operator is used for aggregation, then instead of computing four additions: A + B + C and B + + D concurrently, the three additions BC = B + C, A + BC, and BC + D can be computed. This approach is orthogonal to the approaches proposed in Section 3 in that it reduces redundant aggregation steps, whereas our approach reduces redundant input nodes and edges in parallel computations. As such, the two approaches could be employed together.
22

---

Published in Transactions on Machine Learning Research (01/2025)
reddit
papers100M
yelp
flickr
1.00
0.65
0.95
0.60
0.90
0.55
0.60
0.50
0.7-
16
16
0.6-
15
64
64
64
256
0.5
0.50
80000
30000
40000
2000
5000
step
step
step
step
1.0
0.22
16
16
0.20
64
16
1.25
64
16
0.6
1.4
0.75
0.4
1.2
0.50
0.14
0.25
1.0
10000 12500
40000
80000
20000 30000
40000
5000
stop
stop
stop
stop
Figure 8: LABOR-O sampling algorithm with 1024 batch size and varying dependent minibatches, = xc denotes infinite dependency, meaning the neighborhood sampled for vertex stays static during training.
The first row shows the training Fl-score with the dependent sampler. The second row shows the training loss curve. Completes Figure
052
635
6.5-
0.4
6.54
6:5
0.0
11g
34-
3.2
3.00
67-
33
1300
7030
10030
15530
20030
20530
30030
2003
6000
70089
1430 1903
Figure 9: Convergence difference between cooperative independent minibatching with global batch size of 4096 averaged over Neighbor and LABOR-0 samplers.
A.11 Limitations
Our proposed Cooperative Minibatching approach requires a relatively fast interconnect between the Processing Elements. Modern multi-GUU systems usually have such interconnect between the GPUss Nowadays, such fast. interconnects are being extended the multi-node setting, for up to 72 GPUs connected via NVLink (NVIDIA)
2024
23

---

Published in Transactions on Machine Learning Research (01/2025)
On distributed training, each computing node equipped with multiple cores and/or GPUs, the interconnect between cores and/or GPUs of the same node, are also relatively much faster than the interconnect among nodes.
The proposed dependent minibatching approach does not have any such limitation.
24


Reviews:
[{"review_id": "FEju27lwqI", "reviewer": "Reviewer_udeZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strength**\n- The paper addresses a broad and universal technique, making its contribution valuable to the large community. \n- The proposed methods are inspired from solid theoretical investigation, and supported by thorough empirical validations. This combination of rigorous theory and experimental results demonstrates the robustness and practical relevance of the approach. \n\n### **Weakness\n- It would be helpful if the authors provided a figure comparing the minibatching techniques used in GNNs and DNNs, along with a visual comparison between independent minibatching and the proposed cooperative minibatching.\n- Including a dedicated section that clarifies the scope and potential applications of this technique could further enhance the paper's contribution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates minibatching in GNNs. Due to the distinct architecture of GNNs compared to traditional Deep Neural Networks (DNNs), the authors highlight the inefficiency of independent minibatching for GNNs. To address this, they propose cooperative minibatching, which leverages work reduction as batch sizes increase in multi-PE settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CoqnrYc8iP", "reviewer": "Reviewer_ERzP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper introduced good reading materials for the backgrounds that sets the stage. This is valuable for non-experts in the related field (such as myself) to understand the contexts. I also find the diagrams in the paper helpful\n- The proposed idea that leverages multiple PEs to process mini batches seems to be a nice extension to some of the existing approaches. I personally find it novel, especially that the paper is supported by good theorems. \n- Experimental results on some GNN evaluation benchmarks shows the effectiveness of the approach. \n\nI don't find gnawing issues for this particular work. The work has good contents that suits this journal and I think it has values to the research communities working in the GNN domains.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduced a mechanism to parallel processing the group convolutions. Traditionally, the Independent Minibatching in GNNs leads to duplicated computations and data access, amplifying the Neighborhood Explosion Phenomenon (NEP). The proposed Cooperative Minibatching approach leverages the concave relationship between subgraph size and batch size to reduce work and improve scaling. For performance improvement, the approach achieves up to 64% speedup over Independent Minibatching on single-node multi-GPU systems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "K0zlnJURzw", "reviewer": "Reviewer_qgVk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- The paper provide theoretical background showing the concavity of cost function as batch size increases.\n- Experiments are comprehensive in terms of evaluating in different setting, including different GPUs and bandwidth.\n\nWeakness\n- Dependency on hardware setting is not fully clarified. How does the acceleration ratio differ where the GPU communication cost is not trivial, (e.g., multi-node setting or without NVLink)?\n- How does cooperative minibatching strategy performs compared to more recent data-parallel GNN training system such as Quiver [1] that leverages NVLink?\n\n[1] https://github.com/quiver-team/torch-quiver", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper identifies that the cost of processing minibatch in GNN is a concave function of batch size, unlike in DNNs where it scales linearly. Exploiting this fact, the paper introduces Cooperative Minibatching and dependent minibatching variant of it, targeting to reduce computation (work) in processing the minibatch. Results demonstrate meaningful speedup over Independent Minibatching on single-node multi-GPU system.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Experiments showing how the effectiveness of the proposed method differs on multi-node setting would be a good addition.\n- Comparison with more recent data-parallel GNN training system such as Quiver [1] would be helpful.", "broader_impact_concerns": "Broader Impact section is not provided.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: N/A
Decision: Accept (poster)