Cooperative Minibatching in Graph Neural Networks
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.
Muhammed Fatih Balin, Dominique LaSalle, Ümit V. Çatalyürek
# Cooperative Minibatching in Graph Neural Networks

###### Abstract

Significant computational resources are required to train Graph Neural Networks (GNNs) at a large scale, 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) 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 per seed vertex 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.

## 1 Introduction

Graph Neural Networks (GNNs) have become de facto deep learning models for unstructured data, achieving state-of-the-art results on various application domains involving graph data such as recommendation systems (Wu et al., 2020; Ying et al., 2018), fraud detection (Liu et al., 2022; Patel et al., 2022), identity resolution (Xu et al., 2019), and traffic forecasting (Jiang and Luo, 2022). However, as the usage of technology continues to increase, the amount of data generated by these applications is growing exponentially, resulting in large and complex graphs that are infeasible or too time-consuming to train on a single processing 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.

Due to the popularity of Deep Neural Networks (DNNs) and the need to support larger models and datasets, a 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 (Narayanan 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 and Iyer, 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 a distributed setting. Minibatch training (Bertsekas, 1994) is the go-to method to train DNN models as it outperforms full-batch training in terms of convergence (Allen-Zhu and Hazan, 2016; Li et al., 2014; Keskar et al., 2016; Wilson and 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/backward operations on their minibatches. The only communication required is an all-reduce operation for the gradients.

Unfortunately, minibatch training a 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 a few hops.

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; Waleffe 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 settings by reducing bandwidth requirements, as seen in Section 4.

A single epoch of full-batch GNN training requires computation proportional to the number of layers \(L\) and the size of the graph. However, minibatch training requires more operations to process a single epoch due to repeating calculations in the \(2\)nd 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 in the \(L\)-hop neighborhood. Thus, it is 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 a concave function of the batch size (Theorems 3.1 and 3.2).
* Utilize this relationship by combining data and intra-layer parallelism to process a minibatch across multiple PEs for reduced work (Section 3.1), 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). This approach can reduce the transfer amount of vertex embeddings up to \(4\times\), without harming model convergence.
* Show that the two approaches are orthogonal. Together, the reduced work and decreased cache miss rates result in up to \(1.64\times\) speedup over Independent Minibatching with identical global batch size.

## 2 Background

A graph \(\mathcal{G}=(V,E)\) consists of vertices \(V\) and edges \(E\subset V\times V\) along with optional edge weights \(A_{ts}>0,\forall(t\to s)\in E\). Given a vertex \(s\), the \(1\)-hop neighborhood \(N(s)\) is defined as \(N(s)=\{t|(t\to s)\in E\}\), and it can be naturally expanded to a set of vertices \(S\) as \(N(S)=\cup_{s\in S}N(s)\).

GNN models work by passing previous layer embeddings (\(H\)) from \(N(s)\) to \(s\), and then combining them using a nonlinear function \(f^{(l)}\) at layer \(l\), given initial vertex features \(H^{(0)}\):

\[H_{s}^{(l+1)}=f^{(l)}(H_{s}^{(l)},\{H_{t}^{(l)}\mid t\in N(s)\}) \tag{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_{t}\subset V\) for _full-batch_ training. In \(L\)-layer full-batch training, the total number of vertices that needs to be processed is \(L|V|\).

### Minibatching in GNNs

In minibatch training, a random subset of training vertices, called _Seed Vertices_, is selected, and training is done 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_{t}\).

Given a set of vertices \(S\), we define \(l\)-th layer expansion set, or the \(l\)-hop neighborhood \(S^{l}\) as:

\[S^{0}=S,\ \ \ S^{(l+1)}=S^{l}\cup N(S^{l}) \tag{2}\]

For GNN computations, \(S^{l}\) would also denote the set of the required vertices to compute (1) at each layer \(l\). Using the same notation, \(\{s\}^{l}\) denotes \(l\)-layer expansion set starting from single vertex \(s\in V\).

For a single minibatch iteration, the total number of vertices that need to be processed is \(\sum_{l=1}^{L}|S^{l}|\). There are \(\frac{|V|}{|S^{0}|}\) minibatches assuming \(V_{t}=V\). Since each \(|S^{l}|\geq|S^{0}|\), and a single epoch of minibatch training needs to go over the whole dataset, the work \(W(|S^{0}|)\) for a single epoch is:

\[W(|S^{0}|)=\frac{|V|}{|S^{0}|}\sum_{l=1}^{L}E[|S^{l}|]\geq\frac{|V|}{|S^{0}|} \sum_{l=1}^{L}|S^{0}|=L|V|\]

where \(E[|S^{l}|]\) is the expected number of sampled vertices in layer \(l\) and \(|S^{0}|\) is the batch size. That is, the total amount of work to process a single epoch increases over full-batch training. The increase in work due to minibatch training is thus encoded in the ratios \(\frac{E[|S^{l}|]}{|S^{0}|},1\leq l\leq L\).

Next, we will briefly present some of the sampling techniques. 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 2.

### 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 is a function of the batch size. All these methods are applied recursively for GNN models with multiple layers.

#### 2.2.1 Neighbor Sampling (NS)

Given a fanout parameter \(k\) and a batch of seed vertices \(S^{0}\), NS by (Hamilton et al., 2017) samples the neighborhoods of vertices randomly. Given a batch of vertices \(S^{0}\), a vertex \(s\in S^{0}\) with degree \(d_{s}=|N(s)|\), if \(d_{s}\leq k\), NS uses the full neighborhood \(N(s)\), otherwise it samples \(k\) random neighbors for the vertex \(s\).

One way to sample \(k\) edges from \(d_{s}\) options is to use the reservoir algorithm (Vitter, 1985). In this algorithm, the first \(k\) edges are included in the reservoir. For the rest of the \(d_{s}-k\) edges, the \(i\)th edge \((t\to s)\) rolls the uniform random integer \(0\leq r_{ts}\leq i\) and replaces the item in slot \(r_{ts}\) if \(r_{ts}<k\).

#### 2.2.2 LABOR Sampling

Given a fanout parameter \(k\) and a batch of seed vertices \(S^{0}\), LABOR-0 (Baln & Catalyurek, 2023) samples the neighborhoods of vertices as follows. First, each vertex rolls a uniform random number \(0\leq r_{t}\leq 1\). Given batch of vertices \(S^{0}\), a vertex \(s\in S^{0}\) with degree \(d_{s}=|N(s)|\), the edge \((t\to s)\) is sampled if \(r_{t}\leq\frac{k}{d_{s}}\). Since different seed vertices \(\in S^{0}\) end up using the same random variate \(r_{t}\) 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\to s)\) if \(r_{t}\leq c_{s}\pi_{t}\), where \(\pi\) is importance sampling probabilities optimized to minimize the
expected number of sampled vertices and \(c_{s}\) is a normalization factor. LABOR-* samples fewer vertices than LABOR-0 in expectation.

Note that, choosing \(k\geq\max_{s\in V}d_{s}\) corresponds to training with full neighborhoods for both NS and LABOR methods.

#### 2.2.3 RandomWalk Sampling

Given a walk length \(o\), a restart probability \(p\), number of random walks \(a\), a fanout \(k\), and a batch of vertices \(S^{0}\), a vertex \(s\in S^{0}\), a _Random Walk_(Ying et al., 2018) starts from \(s\) and each step picks a random neighbor \(s^{\prime}\) from \(N(s)\). For the remaining \(o-1\) steps, the next neighbor is picked from \(N(s^{\prime})\) with probability \(1-p\), otherwise it is picked from \(N(s)\). This process is repeated \(a\) times for each seed vertex and lastly, the top \(k\) most visited vertices become the _neighbors_ of \(s\) for the current layer.

Notice that random walks correspond to weighted neighbor sampling from a graph with adjacency matrix \(\tilde{A}=\sum_{i=1}^{o}A^{i}\), where the weights of \(\tilde{A}\) depend on the parameters \(a\), \(p\) and \(k\). Random walks give us the ability to sample from \(\tilde{A}\) without actually forming \(\tilde{A}\).

### Independent Minibatching

Independent minibatching is commonly used in multi-GPU, and distributed GNN training frameworks (Cai et al., 2023; Gandhi and Iyer, 2021; Lin et al., 2020; Zheng et al., 2021; Zhu et al., 2019) to parallelize the training and allows scaling to larger problems. Each Processing Element (PE, e.g., GPUs, CPUs, or cores of multi-core CPU), starts with their own \(S^{0}\) of size \(b\) as the seed vertices, and compute \(S^{1},\ldots,S^{L}\) along with the sampled edges to generate minibatches (see Figure 1). Computing \(S^{1},\ldots,S^{L}\) depends on the chosen sampling algorithm, such as the ones explained in Section 2.2.

Independent minibatching has the advantage that doing a forward/backward pass does not involve any communication with other PEs after the initial minibatch preparation stage at the expense of duplicate work (see Figure 1).

## 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. We provide their proofs in Appendices A.1 and A.2. After that, we propose two algorithms that can take advantage of this monotonicity.

**Theorem 3.1**.: _The work per epoch \(\frac{E[|S^{l}|]}{|S^{0}|}\) required to train a GNN model using minibatch training is monotonically nonincreasing as the batch size \(|S^{0}|\) increases._

**Theorem 3.2**.: _The expected subgraph size \(E[|S^{l}|]\) required to train a GNN model using minibatch training is a concave function of batch size, \(|S^{0}|\)._

Figure 1: Minibatches of two processing elements may share edges in the second layer and vertices starting in 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 necessitate communication.
### Cooperative Minibatching

As explained in Section 2, Independent Minibatching (I.M.) can not take advantage of the reduction in work with increasing global batch sizes and number of PEs, because it uses separate small batches of sizes \(b\) on each PE for each step of training. On the other hand, one can also keep the global batch size constant, \(bP=|S^{0}|\), and vary the number of processors \(P\). As \(P\) increases, I.M. will perform more and more duplicate work because the local batch size is a decreasing function, \(b=\frac{|S^{0}|}{P}\), of \(P\).

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 batch of size \(bP\) will be processed by all the \(P\) PEs in parallel, eliminating any redundant work across all PEs.

We achieve this as follows: we first partition the graph in 1D fashion by logically assigning each vertex and its incoming edges to PEs as \(V_{p}\) and \(E_{p}\) for each PE \(p\). Next, PE \(p\) samples its batch seed vertices \(S^{l}_{p}\) from the training vertices in \(V_{p}\) for \(l=0\) of size \(b\). Then using any sampling algorithm, PE \(p\) samples the incoming edges \(E^{l}_{p}\) from \(E_{p}\) for its seed vertices. Each PE then computes the set of vertices sampled \(\tilde{S}^{l+1}_{p}=\{t\mid(t\to s)\in E^{l}_{p}\}\). Note that, \(\tilde{S}^{l+1}_{p}\) has elements residing on different PEs. The PEs exchange the vertex ids \(\tilde{S}^{l+1}_{p}\) so that each PE receives the set \(S^{l+1}_{p}\in V_{p}\). This process is repeated recursively for GNN models with multiple layers by using \(S^{l+1}_{p}\) as the seed vertices for the next layer. The exchanged information is cached to be used during the forward/backward passes.

For the forward/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. Algorithm 1 details cooperative sampling and cooperative forward/backward passes for a single GNN training iteration. Independent minibatching works the same except that it lacks the all-to-all operations and has \(\tilde{A}^{l+1}_{p}=A^{l+1}_{p}\) 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 a variable \(\tilde{A}^{l+1}_{p}\) into \(A^{l+1}_{p}\) during the forward pass and \(A^{l+1}_{p}\) into \(\tilde{A}^{l+1}_{p}\) during sampling and the backward passes for any variable \(A\). We refer the reader to Appendix A.3 for the complexity analysis of Cooperative and Independent Minibatching approaches, and to Appendix A.7 to see the relation between the approach proposed here and the work of Jia et al. (2020) on redundancy-free GCN aggregation.
### 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 \(\kappa b\)-sized minibatch for \(\kappa\) iterations. In light of Theorems 3.1 and 3.2, consider doing the following: choose \(\kappa\in\mathbb{Z}^{+}\), then sample a batch \(S^{0}\) of size \(\kappa b\), i.e., \(\kappa b=|S^{0}|\) to get \(S^{0},\ldots,S^{L}\). Then sample \(\kappa\) minibatches \(S^{0}_{i}\), of size \(b=|S^{0}_{i}|\) from this batch of size \(\kappa b\) to get \(S^{0}_{i},\ldots,S^{L}_{i},\forall i\in\{0,\ldots,\kappa-1\}\). In the end, all of the input features required for these minibatches will be a subset of the input features of the large batch, i.e. \(S^{j}_{i}\subset S^{j},\forall i,j\). This means that the collective input feature requirement of these \(\kappa\) batches will be \(|S^{L}|\), the same as our batch of size \(\kappa b\). Hence, we can now take advantage of the concave growth of the work in Theorem 3.2 and Figure 2.

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 \(l\)-hop neighborhood of a batch of size \(\kappa b\) will always be equal to the union of the \(l\)-hop neighborhoods of batches of sizes \(b\). However for sampling algorithms, any overlapping vertex sampled by any two batches of sizes \(b\) might end up with different random neighborhoods resulting in a larger number of sampled vertices. Thus, having a single large batch ensures that only a single random set of neighbors is used for any vertex processed over a period of \(\kappa\) batches.

The approach described above has a nested iteration structure and the minibatches part of one \(\kappa\) group will be significantly different than another group and this might slightly affect convergence. In Appendix A.4, we propose an alternative smoothing approach that does not require two-level nesting and still takes advantage 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 a 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 speed of change in the sampled neighborhoods is \(\frac{1}{\kappa}\), and after every \(\kappa\) iterations, one gets fully independent new random neighborhoods for all vertices. 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 are discussed in Appendix A.4.

## 4 Experiments

**Setup:** In our experiments, we use the following datasets: reddit (Hamilton et al., 2017), papers100M (Hu et al., 2020), mag240M (Hu et al., 2021), yelp and flickr (Zeng et al., 2020), and their details are given in Table 1. We use Neighbor Sampling (NS) (Hamilton et al., 2017), LABOR Sampling (Balm & Catalyurek, 2023) and Random Walks (RW) (Ying et al., 2018) to form minibatches. We used a fanout of \(k=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 \(a=100\). All our experiments involve a GCN model with \(L=3\) layers (Hamilton et al., 2017), with 1024 hidden dimension for mag240M and papers100M and 256 for the rest. Additionally, papers100M and mag240M datasets were made undirected graphs for all experiments and this is reflected in the reported edge counts in Table 1. 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.

\begin{table}
\begin{tabular}{r|r|r|r|r|r|r} \hline \hline
**Dataset** & \(|V|\) & \(|E|\) & \(\frac{|E|}{|V|}\) & **\# feats.** & **cache size** & **train - val - test (\%)** & **\# minibatches** \\ \hline 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 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Traits of datasets used in experiments: numbers of vertices, edges, avg. degree, features, cached vertex embeddings, and training, validation and test vertex split. The last column shows the number of minibatches in an epoch during model training with 1024 batch size including validation.
**Implementation:** We implemented5 our experimental code using C++ and Python in the DGL framework (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.

Footnote 5: Source code is available at [https://github.com/GT-TDAlab/dgl-coop/tree/dist_graph_squashed_wip_cache](https://github.com/GT-TDAlab/dgl-coop/tree/dist_graph_squashed_wip_cache)

We first compare how the work to process an epoch changes w.r.t. to the batch size to empirically validate Theorems 3.1 and 3.2 for different graph sampling algorithms. Next, we show how dependent batches introduced 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 to get multiplicative savings.

### 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 \(L=3\) layer case across these three different classes of sampling algorithms. We carried out our evaluation in two problem settings: node and edge prediction. For node prediction, a batch of training vertices is sampled with a given batch size. Then, the graph sampling algorithms described in Section 2.2 are applied to sample the neighborhood of this batch. The top row of Figure 2 shows how many input vertices is required on average to process an epoch, specifically \(\frac{E[|S^{3}|]}{|S^{0}|}\). For edge prediction, we add reverse edges to the graph making it undirected and sample a 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 edge is sampled. Then, all of the endpoints of these positive and negative edges are used as seed vertices to sample their neighborhoods. The bottom row of Figure 2 shows \(E[|S^{3}|]\).

We can see that in all use cases, datasets and sampling algorithms, the work to process an epoch is monotonically decreasing (see Appendix A.1 for the proof). We also see the plot of the expected number of vertices sampled, \(E[|S^{3}|]\), is concave with respect to batch size (proof in Appendix A.2).

Another observation is that the concavity characteristic of \(E[|S^{3}|]\) 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 \(E[|S^{L}|]\) curve is, the less it is affected from the NEP and

Figure 2: Monotonicity of the work. x-axis shows the batch size, y-axis shows \(\frac{E[|S^{3}|]}{|S^{0}|}\) (see Theorem 3.1) for node prediction (top row) and \(E[|S^{3}|]\) (see Theorem 3.2) for edge prediction (bottom row), where \(E[|S^{3}|]\) denotes the expected number of sampled vertices in the 3rd layer and \(|S^{0}|\) 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.
more savings are available through the use of the proposed methods in Sections 3.1 and 3.2. Note that the differences would grow with a larger choice of layer count \(L\).

### Dependent Minibatches

We vary the batch dependency parameter \(\kappa\) introduced in Section 3.2 for the LABOR-0 sampler with a batch size of \(1024\). Our expectation is that as consecutive batches become more dependent on each other, 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 vertex embedding accesses by implementing an LRU cache to fetch them, the cache sizes used for different datasets is given in Table 1. 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 3(a) shows that as \(\kappa\) 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 \(\frac{|E|}{|V|}\) given in Table 1. Figure 3 shows that training is not negatively affected across all datasets up to \(\kappa=256\) with less than \(0.1\%\) F1-score difference, after which point the validation F1-score with w/o sampling starts to diverge from the \(\kappa=1\) case. Runtime benefits of this approach can be observed by comparing the **Cache** and **Cache, \(\mathbf{\kappa}\)** columns in Table 2. Appendix A.5 has additional discussion about the effect of varying \(\kappa\) and the last column of Table 1 shows the number of minibatches in an epoch during training.

### Cooperative Minibatching

We use our largest datasets, mag240M and papers100M, as distributed training is motivated by large-scale graph datasets. We present our runtime results on systems equipped with NVIDIA GPUs, with 4 and 8 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 are only used to launch kernels for the GPUs. Feature copies are performed by GPUs as well, accessing pinned feature tensors over the PCI-e using zero-copy access. In cooperative minibatching, both data size and computational cost are shrinking

Figure 4: LRU-cache miss rates for LABOR-0 sampling algorithm with \(1024\) batch size per PE and varying \(\kappa\) dependent minibatches, \(\kappa=\infty\) denotes infinite dependency.

Figure 3: The validation F1-score with the full neighborhoods for LABOR-0 sampling algorithm with \(1024\) batch size and varying \(\kappa\) dependent minibatches, \(\kappa=\infty\) denotes infinite dependency, meaning the neighborhood sampled for a vertex stays static during training. See Figure 3(a) for cache miss rates. See Figure 3(c) for the validation F1-score with the dependent sampler and the training loss curve.
with increasing numbers of PEs, 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 2, cooperative minibatching reduces all the runtimes for different stages of GNN training, except for the F/B (forward/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 2, divide independent runtimes by the corresponding cooperative ones, then we get Table 3. We can see that the theoretical decrease in work results in increasing speedup numbers with the increasing number of PEs, due to Theorem A.1. We would like to point out that \(\frac{\bar{E}[|S^{3}|]}{|S^{0}|}\) curves in Figure 2 are responsible for these results. With

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c} \hline \hline
**\# PEs, \(\gamma\)** & **Dataset** & \multirow{2}{*}{**Sampler**} & \multirow{2}{*}{**I/C**} & \multirow{2}{*}{**Samp.**} & \multicolumn{4}{c|}{**Feature Copy**} & \multirow{2}{*}{**F/B**} & \multirow{2}{*}{**Total**} \\ \(\alpha,\beta,|S^{0}|\) & & & & & & **Cache** & **cache**, \(\kappa\) & \\ \hline \multirow{4}{*}{\(4\) A100} & \multirow{2}{*}{papers100M} & LABOR-0 & Indep & 21.7 & 18.4 & 16.8 & **11.2** & \(8.9\) & 41.8 \\  & & & Coop & 17.7 & 14.0 & 10.1 & 5.8 & 13.0 & 36.5 \\ \cline{2-10}  & \multirow{2}{*}{GCN} & & \multirow{2}{*}{NS} & Indep & 16.1 & 26.5 & **22.1** & - & 10.1 & 48.3 \\ \cline{6-10} \cline{6-
PEs and \(|S^{0}|\) global batch size, the work performed by independent minibatching vs cooperative minibatching can be compared by looking at \(x=\frac{1}{p}|S^{0}|\) vs \(x=|S^{0}|\) respectively.

We also ran experiments that show that graph partitioning using METIS (Karypis and Kumar, 1998) prior to the start of training can help the scenarios where communication overhead is significant. The forward-backward time goes from 13.0ms to 12.0ms on papers100M with LABOR-0 on 4 NVIDIA A100 GPUs with such partitioning due to reduced communication overhead using the same setup as Table 2.

Increasing the number of GPUs increases the advantage of cooperative minibatching compared to independent minibatching. The forward-backward time on mag240M with LABOR-0 is 200 (same as independent baseline), 194, 187 and 183 ms with 1, 2, 3 and 4 cooperating PEs, respectively measured on the NVIDIA DGX Station A100 machine. The decrease in runtime with increasingly cooperating PEs is due to the decrease in redundant work they have to perform. Even though the batch size per PE is constant, the runtime goes down similar to the plots in the top row of Figure 2, except that it follows \(\frac{kE[|S^{2}|]}{|S^{0}|}\), which gives the average number of edges in the 3rd layer when a sampler with fanout \(k\) is used.

Additionally, we demonstrate that there is no significant model convergence difference between independent vs cooperative minibatching in Appendix A.6.

#### 4.3.1 Cooperative-Dependent Minibatching

We use the same experimental setup as Section 4.3 but vary the \(\kappa\) parameter to show that cooperative minibatching can be used with dependent batches (Figure 3(b)). We use a cache size of 1M per PE. Cooperative feature loading effectively increases the global cache size since each PE caches only the vertices assigned to them while independent feature loading can have duplicate entries across caches. For our largest dataset mag240M, on top of \(1.4\times\) reduced work due to cooperative minibatching alone, the cache miss rates were reduced by more than \(2\times\), making the total improvement \(3\times\). Runtime results for \(\kappa\in\{1,256\}\) are presented in Table 2, the Feature Copy **Cache** and **Cache, \(\mathbf{\kappa}\)** columns. Table 4 summarizes these results by dividing the runtimes in **Cache** by **Cache, \(\mathbf{\kappa}\)** and reporting percentage improvements.

## 5 Conclusions

In this paper, we investigated the difference between DNN and GNN minibatch training. We observed that the cost of processing a minibatch is a concave function of batch size in GNNs, unlike DNNs where the cost scales linearly. We then presented theorems that this is indeed the case for every graph and then proceeded to propose 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 demonstrate this increase in locality by employing an LRU-cache for vertex embeddings on GPUs. Finally, we show that these approaches can be combined without affecting convergence, and speed up multi-GPU GNN training by up to \(64\%\) for free.

\begin{table}
\begin{tabular}{c|c|r|r|r} \hline
**Dataset \& Model** & **I/C** & **4 GPUs** & **8 GPUs** & **16 GPUs** \\ \hline papers100M & Indep & \(50\%\) & \(57\%\) & \(37\%\) \\ GCN & Coop & \(74\%\) & \(78\%\) & \(112\%\) \\ \hline \hline mag240M & Indep & \(37\%\) & \(41\%\) & \(26\%\) \\ R-GCN & Coop & \(58\%\) & \(50\%\) & \(82\%\) \\ \hline \end{tabular}
\end{table}
Table 4: Runtime improvements of Dependent Minibatching for Independent and Cooperative Minibatching methods compiled from the **Cache, \(\mathbf{\kappa}\)** and **Cache** columns of Table 2 with LABOR-0. Making consecutive minibatches dependent increases temporal locality, hence reducing cache misses. This speeds up feature loading runtime.