HierBatching: Locality-Aware Out-of-Core Training of Graph Neural Networks
Authors: Tianhao Huang
Xuhao Chen
Muhua Xu
Arvind Arvind
Jie Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Network
Out-of-Core Training
Spatial Locality
Temporal Locality
Hierarchical Batching

Abstract: As graph neural networks (GNNs) become increasingly more popular for analyzing data organized as massive graphs, how these models can be efficiently trained under economic computing resources becomes a critical subject that influences the widespread adoption of GNNs in practice. We consider the use of a single commodity machine restrained by limited memory but otherwise is attached with ample external storage. In such an under-explored scenario, not only the feature data often exceeds the memory capacity, but also the graph structure may not fit in memory as well. Then, with data stored on disk, gathering features and constructing neighborhood subgraphs in a usual mini-batch training incur inefficient random access and expensive data movement.

To overcome this bottleneck, we propose a locality-aware training scheme, coined HierBatching, to significantly increase sequential disk access, while maintaining the random nature of stochastic training and its quality. HierBatching exploits the memory hierarchy of a modern GPU machine and constructs batches in an analogously hierarchical manner. Therein, graph nodes are organized in many partitions, each of which is laid out contiguously in disk for maximal spatial locality; while the main memory stores random partitions and is treated as the cache of the disk. Its content is reused multiple times for improving temporal locality. We conduct comprehensive experiments, including locality ablation, to demonstrate that HierBatching is economic, fast, and accurate.

Under review as a conference paper at ICLR 2023
HIERBATCHING: LOCALITY-AWARE OUT-OF-CORE TRAINING OF GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
Graph neural networks (GNNs) have become increasingly popular for analyzing data organized massive graphs. Efficient training of GNN models under limited computing resources is critical for GNN's widespread adoption. We consider the use of single commodity machine with limited memory (e.g., 128GB) but ample external storage (c.g., ITB). On such platform, the feature data or even the graph may not fit in the memory. When data is stored on external storage, gathering features and constructing neighborhood subgraphs in typical mini-batch training incurs random storage accesses and thus, causes expensive data movement.
To overcome this bottleneck, we propose a locality aware training scheme, coined HierBatching, which significantly increases training speed while retaining the training quality. The key idea is to exploit the memory hierarchy of a modern GPU machine by constructing batches in analogously hierarchical manner. HierBatching groups nodes in partitions, each of which is laid out contiguously in the disk for maximal spatial locality. Meanwhile, the main memory is treated as cache that holds meta-batch, which is random collection of partitions. Mini-batches are sampled for GPU training from the mega-batch the main memory. Fach mega-batch is reused multiple times to improve temporal locality. Our experiments show that on machine with 128GB main memory, HierBatching is 3x to 20x x faster than a straightforward out-of-core training approach by using mmap, while maintaining the prediction accuracy.
INTRODUCTION
Graph neural networks (GNNs) have emerged as effective machine learning models for many practical applications, such as social network analysis, financial forensics, recommendation, and traffic forecasting (Hamilton et al., 2017b). Training GNNs has become increasingly challenging as the size of the graphs has increased rapidly. Even benchmark datasets that mimic real-life applications have grown to sizes that forbid the use of commodity laptops or servers for experimentation and model development. For example, the MAG24 4 OM dataset (Hu et al., 2020) has 407GB of raw data (where 349GB accounts for node features). The storage requirement easily exceeds the memory capacity of single machine; hence, one considers either exploiting external storage or using a distributed-memen memory cluster. The latter imposes natural cost barrier for many individuals and organizations, and also has been demonstrated to be often heavily communication-A bound (Ramezani et al., 2022).
In this work, we exploit external storage (e.g., SSD) and perform out-of-core GNN training on single machine with one few GPUs. Fig. ((a) illustrates the typical memory hierarchy of such machine. The ample external storage is assumed be able to store the entire dataset in a format that facilitates processing and training, while the main memory cannot. Each GPU, as is common in machine architectures encountered nowadays, has an even smaller memory capacity than the main memory. We use one multiple GPUs to perform mini-batch training.
Traditional wisdom suggests that key to the exploitation of the memory hierarchy of a machine is locality: spatial locality that takes advantage of sequential data accesses and thus reads data in blocks instead of single words, and temporal locality, which takes advantage of the fact that recently accessed data will be accessed again in the near future, and thus, put it at place closer to the processors computing, for spatial locality the operating system retrieves
to reduce access time. In data from disk to memory in fixed-sized 4KB to 8KB blocks, called pages. This avoids the read

---

Under review as a conference paper at ICLR 2023
GPU;
G
GPU Memory
Main Memory
Disk
node partition
100B
GPU Memory
GPU
training nodes
PCio
static cache
static nodes
1000G8
Main Memory
dynamic cache
Storage Disk
Memory
mega-batch
-T2
mini-batch
(a) memory hlerarchy of a single machine
(b) hlerarchical batching
Figure 1: Overview of hierarchical batching. The disk stores the entire graph which is divided into partitions. Multiple (four in this example) partitions randomly selected and loaded into the main memory form mega-batch, from which mini-batches are sampled and moved the GPUs for training.
amplification problem (which dramatically reduces the effective disk bandwidth) when disk is read in cache-line-size blocks. For temporal locality, it is desirable that data loaded from the disk be reused as often as possible, given the significant latency caused by moving data from disk memory.
Following this intuition, we propose a hierarchical batching scheme, abbreviated as HierBatching, to exploit locality in modern commodity memory hierarchy (external storage, main memory, and GPU memory). HierBatching batches data in an analogously hierarchical fashion: the entire set of graph nodes (with features and edge lists) stored in external storage, while a mega-batek of nodes is sampled and copied to the main memory serving cache; mini-batches are then sampled from the cache for gradient- training. We make this scheme locality-aware by partitioning the graph nodes into many small partitions that stored consecutively in the disk (spatial locality), and performing mini-batch training with the same cache multiple rounds (temporal locality). HierBatching preserves the random nature of stochastic training, as it forms each mega-batch with random combinations of from the mega-batch randomly.
partitions and samples
A realization of HierBatching incurs subtle challenge because some of the neighbors of node in a mega-batte batch may not be included in the cache, thereby degrading the training quality and the prediction accuracy. To maximally increase the node degrees with small memory, we propose to permanently store the highest-degree nodes in the memory, because they are more likely to be connected to nodes in the mega-batch. We thus divide the main memory into static cache and dynamic cache and use the former to accommodate these nodes, such that their features are always reachable without repetitive transfers from the external storage. See Fig. 1(b) for preview.
Our work makes the following contributions:
We study practical but under-explored scenario for training GNNs on massive graphs using external storage and propose HierBatching, locality-aware batching scheme that fully leverages the memory hicrarchy of a machine, particularly disk, to improve training efficiency.
We introduce static cache compensate the loss of node degrees in the formation of the batching hierarchy, retaining model accuracy obtained by standard in-memory mini-batch training.
We demonstrate empirically that, on a GPU equipped machine with 128GB main memory. Hier- Batching is 3x to 20x faster than DGL with mmap support, while retaining prediction accuracy. HierBatching also competitive with in-memory DGL, which requires times more memory.
PRELIMINARIES AND RELATED WORK
In this work, consider message-passing GNNs that act given graph G(V, E), where V is the node set and E is the edge set. For each node u E V. let h. be the initial feature vector. A K-layer GNN uses message passing to iteratively update the feature vector and produces an output vector h Specifically, the update at the k-th layer (1 < k S K) reads
he update* (nt: k-1
aggregate & ((h | M A(o))))
where / (v) denotes the h-hop neighborhood of v, and update and aggregate" are operators on the feature vectors, generally layer-dependent. Common GNNs, such GCN (Kipf & Welling,
2

---

Under review as a conference paper at ICLR 2023
2016), GraphSAGE (Hamilton al., 2017a), GAT (Veličković et al., 2018), and GIN (Xu et al., 2019), follow this framework but differ in the design of the two operators.
To scale GNNs massive datasets, frequently studied approach is distributed-memno train- ing (Yang, 2019; Zhang et al., 2020; Zheng et al., 2020; Jia et al., 2020; Tripathy et al., 2020; Hoang et at 2021; Md et al., 2021; Gandhi & Iyer, 2021; Kaler et al., 2022). However, such an approach often requires frequent and voluminous inter-machine communication, including features, edge lists, models, and gradients, causing substantial challenges in parallelization, synchronization, and pipelining. LLCG (Ramezani et al., 2022) reduces communication by using local training and global correction; however, it requires a powerful global server that can process the entire graph, at odds with limited memory budget.
GNN training is generally done by following the mini-batch training scheme, propelled by the advances in stochastic optimizations and widely adopted by the designers of neural networks. Mini- batch training on graph data, however, suffers the well-known neighhorhood explosion problem: for a K-layer GNN, the loss of training example requires information of its K-hop neighborhood, whose size is exponential
K the worst case. Therefore, sampling techniques (Hamilton et al., 2017a; Chen et al., 2018; 8; Chiang et al., 2019; Zeng et al., 2020) have been proposed to limit the size of the neighborhood. This batching-ples pplu--sampling approach effectively reduces memory consumption, but data movement remains bottleneck that hampers training efficiency. Prior work that aims reducing data movement exists. GNS (Dong et al., 2021), PaGrapp (Lin et al., 2020) and GNNLab ( (Yang al., 2022) all employ GPU memory cache of main memory and keep likely-reusable data for fast accesses; GNS further prioritizes sampling from the cache nodes to reduce the cache misses. LazyGCN (Ramezani et al., 2020) recycles the already-sampled data in GPU memory, also reducing sampling and data movement overhead. However, none of the approaches handles the out-of-core scenario; in particular, they do not eliminate random accesses or consider the spatial locality, which are critical for data stored in the disk. MariusGNN and its prequel (Waleffe et al., 2022; Mohoney et al., 2021) 1) are rare works that studied out-of-core training. Yet, they employ random partitioning that could render the in-memory graph overly sparsified and hurt the GNN prediction accuracy. A detailed analysis of MariusGNN and a comparison with our approach are provided in Appendix D.2.
Other approaches to scaling up GNNs include GNNAutoScale (Fey et al., 2021), graph coarsen- ing (Huang et al., 2021), compression (Liu et al., 2021), and quantization (Ding et al., 2021). They orthogonal to approach and can be applied together with HierBatching in practice.
LOCALITY-AWARE HIERARCHICAL BATCHING
The typical mini-batching and sampling method for training GNNs works well in the in- in-memory training setting, but is not efficient for the out-of-core setting. This is because the batching approach is not aware of the memory hierarchy in real machine. More specifically, external storage accesses are much slower than memory accesses. The random nature of mini-batching causes random disk accesses, rendering out-of-core training orders of magnitude slower than in-memory training. Even if disk data is treated as a memory-mapped file (mmap), page alignment will inevitably cause movement of unneeded data from disk to memory. Moreover, neighborhood sampling can be rather inefficient, if in in-memory sampling is interleaved with moving edge lists from disk to memory, hop by hop.
We thus propose HierBatching, an out-of-core scheme that effectively leverages the memory hierarchy for efficient training. The development of HierBatching undergoes series steps, including exploiting spatial locality through graph partitioning ($3.1), compensating degree loss by using a static cache ($3.2), and improving temporal locality through mega-batch reuse and pipelining ($3.3). We summarize the overall training algorithm in $3.4 and analyze the training speedup in $3.5.
3.1 HIERARCHICAL BATCHING AND SPATIAL LOCALITY
The first step of an efficient solution is to create a hierarchy for the batches, analogous to the memory hierarchy of typical machine for training neural networks (external storage main memory - GPU memory; see Fig. (a)). We treat the main memory as cache for the disk and call data residing in the main memory a mega-batch. Once the mega- bathh is formed through disk I/O, we may sample mini-batche from it, eliminating extra disk accesses. It has been demonstrated that if the mega-batch
3

---

Under review as a conference paper at ICLR 2023
is sampled randomly from the entire graph, training will converge and the resulting model is as good as that trained without using mega-batcher batches (Ramezani et al., 2020).
The solution above reduces disk accesses, but the accesses are still random. To improve spatial locality, we divide the nodes into partitions and randomly sample partitions instead of nodes to form mega-batch. Node data of a partition, i.e., feature vectors and edge lists, are laid out contiguously in disk, so that accesses to the nodes in the same group are sequential. An obvious benefit of grouping is the reduction of random disk accesses; moreover, it leads to the I/O of more consecutive data, reducing the collateral movement of unneeded data due to page alignment. This mechanism is illustrated in Fig. 1(b). where a box denotes a partition and the dots inside are the training nodes.
The number of partitions is chosen to balance two factors: too large partition weakens the random- ness of the mega-batch, compromising training quality; too small a partition weakens spatial locality, slowing down the disk data transfer. One rule of thumb is to ensure that the edge lists of a partition occupy only a few pages, given a specific page size and the average node degree. Moreover, is set
desirable to use the minimum edge cut as the partitioning objective, so that the mega-batch, of partitions, loses as few neighbors as possible. For a proof of concept, we use the off-the-shelf partitioner METIS (Karypis & Kumar, 1998) in our experiments. In cases when the graph storage is beyond the memory capacity, an out-of-core partitioner (Kaur & Gupta, 2021) is used.
3.2 STATIC AND DYNAMIC CACHES
Let the graph be divided into N₂ disjoined partitions and the capacity of the cache (main memory) allows holding No (< Np) partitions. In each training epoch, we randomly shuffle the partitions and move Ne partitions from the disk to perform in-memory training. The cache contains a subgraph induced by the nodes inside these No partitions. We enumerate mini-batches and sample neighbors for each layer from this subgraph to perform model updates. Compared with the full graph, however, such a subgraph will inevitably lose edges between the nodes in it and those outside it. This fact causes the degradation of prediction accuracy on some of the large graphs we experimented with.
To mitigate the performance loss due to insufficient neighbors, we permanently store in the memory some high-degree nodes that are helpful to increase the overall node degree. The part of the memory that holds these nodes called the static cache. The rest of the memory acts as a dynamic cache, which holds the randomly selected partitions from the disk. As we can only allocate small amount of memory for the static cache, we want to maximize its usage. A natural question which static nodes are the most beneficial. Let Cs with cardinality l be the node set in the static cache and let (C be the node set in the dynamic cache for the i-th mega-batch. Then, the objective is to maximize the sum of increased degrees over all mega-batches:
ΣA(c/, Css.
max CsCV, [Csl=k
(1)
where for each mega-batch,
(CD.CCs):
Σ I(u,v)
Σ [(u, v),
(2)
DECD VECDUCS
NECD vECd
with 1 (u, v) being the indicator function which denotes the existence of an edge between nodes and v. is not hard to see that the solution to Eq. (1) is
Cgp first & nodes in the decreasing order of degree(v) degree (v) },
(3)
where degree(r) (v) and degree (v) denote the degree of in the full graph and the degree in the subgraph induced by c(.). respectively. See Appendix for proof.
Note that the optimal selection for the static cache derived in Eq. (3) is not "static": it depends on the content in the dynamic cache, as degrec...s (v) changes over epochs due to the shuffling of partitions. In practice, we use degree(v) to approximate degree(v) - degree,,n (v) when forming the static cache; that is, it contains the l nodes with the highest degrees. Inclusion of these nodes is intuitively sensible: a high-degree node connects more neighbors and offers larger degree increase. Moreover, if all nodes have similar degrees in the subgraph as those in the full graph, then the first nodes in the ordering of (u)ree(u) would be similar to those in Eq. (3).
4

---

Under review as a conference paper at ICLR 2023
Fig. 2 illustrates the degree increase due the of static cache, among nodes grouped by their degrees in the mega-batch. The orange part is the total degree increase for all nodes in the group. One that the group of lowest-degree nodes (0-5) incurs the most increase, benefiting the most significantly from the inclusion static nodes; whereas the highest-degree nodes (>50) incurs the least amount of degree increase. Implementation details of the static cache are in Appendix C.I.
3.3 PIPELINING AND MEGA-BANE -BTCH REUSE
Given a mega-hatch, we enumerate mini-batches of training nodes from it perform training on GPUs. We define a "pass" as using every training node in the mega-batch exactly once. The data transfer from disk to form mega-batch usually takes more time than that of executing one pass on GPUs. This means HierBatching's 's speed can still be limited by the disk data transfer time. On the other hand, for datasets with a low training node ratio, performing one pass may underutilize the data in the memory, i.c., some of the nodes in the mega-batch may not even be sampled.
full graph
500k
d-cache+
Sum of node degroes
d-cache only
400k-
300k
200k
Hence, employ two techniques cooperatively, pipelining and mega-batad reuse, to overcome this bottleneck. The idea is repeatedly use the cur- ren! mega-batch in memory while waiting for the disk transfer for the next mega-batch, in an ex- change of lowering the number of epochs required to reach training convergence. In the context of HierBatching, pipelining refers to overlapping the computation, i.e., training with the current mega- batch, with communication, i.e., the data transfer of the next mega-batch. In addition, mega-batch reuse lets the training go through a mega-batch in multiple passes to exhaust the disk transfer time for the next mega-bate batch.. Repeated use of the mega-batel in the cache improves temporal locality.
5-10 10-20 20-50 >50 Degree buckets (d-cache only)
Node degree increase for five groups of nodes, bucketed by their degrees in the mega-batch. For each group, the green grees before adding the static cache. The orange is the increase of degrees due to the inclusion static cache, while the blue bar shows the loss of degrees.
Figure 2:
shows the of de-
Training with a mega-batch in multiple passes deviates from the usual setting of stochastic optimiza- tion. In our experiments it always converges, but its theoretical analysis is rather challenging and is beyond the scope of this paper. When done in one pass, the training is similar to ClusterGCN (Chiang al., 2019), whose empirical success in convergence supports our proposal. On the other hand, if we are willing to assume that the mega-batches and the mini-batches therein are all sampled with replacement, the setting falls back to standard stochastic gradient descent and do obtain conver- gence guarantees (Bottou et al., 2018). The challenge of analysis lies in the fact that these batches are sampled without replacement. Only very recently, analysis of such a setting was conducted and even so, it considered only strongly convex objective functions (HaoChen & Sra, 2019). We leave the analysis as future work but supplement through empirical evidences $4.1.
3.4 OVERALL ALGORITHM
Let summarize the training procedure in Algorithm 1. We assume that the graph has been partitioned and each of the N₂ partitions is laid out contiguously on external storage. First, fill the static cache (line 9). Then, we train in epochs (line 10), each of which performs a sweep over the entire training set. In each sub-epoch (line 11), Na partitions are sampled and loaded to main memory, forming maga-batch (lines 12-15). This part includes loading node features and edge lists and forming the subgraph induced by the nodes in the dynamic cache and the static cache. Furthermore, this part is pipelined with the rest of the algorithm, which performs GNN training in memory. Therein, the mega-batch is recycled in p passes (line 17). For each pass, standard multi-GPU training procedure is followed update the model parameters (lines 18-23).
5

---

Under review as a conference paper at ICLR 2023
Algorithm I Out-of-core GNN training with hierarchical batching (multi-GPU single-machine)
1:
Input
2:
G(V,E)
input graph, pre-partitioned, with nodes in the same partition stored contiguously in disk total number of partitions
3:
Np
Na
number of partitions the dynamic cache
5:
Ts
the ratio of nodes in V pinned in the static cache
6:
number of passes per mega-batch mini-batch size, i.e., number of training nodes in mini-batch number of GPUs
7:
B
8:
9:
Let the set of rs [V] highest-degree nodes he P. Move features of P the main memory. static cache
10: each epoch Ne N do for each [0, Na
11:
hierarchical batching the main memory level lines 12-15 are pipelined with lines 16-23
12:
Random sample Na node partitions and sampled node set Move the features of T to the dynamic cache the main memory Move the edge lists of T (N(T) P) to the main memory
13:
P disk data transfer > (T() is ' neighborhood P new mega-bateh formed
14:
15:
Form subgraph Geashe with node set (M(T)
16:
Let Sy be the number of training nodes in T, and r = Sr. be the number of mini- batches per pass for each pass E [1. p] do
B
17:
reuse the mega-batch in the main memory
18:
Shuffle training nodes in Gearhe into GPU-level mini--atchees [Bi.... Byxr] each mini-batch E [)) r) do
19:
b hierarchical batching the GPU level multi-GPU training
20:
for each GPU d [1, gl in parallel do Sample message-flow flow graph G. from Geacke for the mini-batch Baxetd Move G. the GPU and compute the gradient
21:
22:
23:
All GPUs average the gradient and update the model
3.5
SPEEDUP ANALYSIS
We analyze the speedup of the proposed locality- hierarchical batching scheme, over straight- forward out-of-core training by using mmap without exploiting locality. We use the same notation in Algorithm in which run p passes and execute p r mini-batches for each mega-batch. Let D be the node feature dimension and Seat be the data precision in bytes. Let BW.,. seg and BWrand be the disk bandwidth when performing sequential accesses and random accesses, respectively. Generally, BWrend/ BW seg == x Sace/Sopts where Sace = D x Syeat is the size of single random access and Sopt the optimal disk request size that leads to sequential access. For example, in the MAG240M dataset, D = 768 and Seeat 2B, while Sopt 4KB for a modern flash disk. Then, = 768 x 02/22//000 2/4069- = 0.375, which means that random access of node feature vector leverages only 37.5% of the peak disk bandwidth.
For simplicity of analysis, we neglect the disk transfer the graph, as loading node features is way more time consuming for large D. Using mmap without locality, the time to load one mini-batch where B is the mini-batch size and F the sampling
disk = B x D fanout. Let r be the ratio of training nodes in the graph, and we assume even distribution of training nodes across mega-batches, so that Sy/Ca se 7. Let the time to train one mini- bani- be typu. which includes data transfer from memory to GPUs, doing forward and backward calculations, smint averaging gradients, and updating the model. Typically, disk /typp := B > 1. Assuming pipelining.
mini
emini On the other hand, for the majority time to train x r mini-batches is tmmap = X x disk mega-batch takes time thega HierBatching. loading mega
Ca D Steat/ BW seg and thus training takes time thier = max ( disk p X X g. J. Therefore, the speedup is mmmap/ thier = p x F/a if disk access takes more time in HierBatching: otherwise, lmmap/ / = B.

---

Under review as a conference paper at ICLR 2023
4 EVALUATION
Datasets and evaluation metric. We use large benchmark datasets listed in Table 1. Mag240M and ogbn-* * datasets come from the Open Graph Benchmark Hu et al. (2020; 2021). I), Mag240M-C the subgraph extracted from Mag240M that contains only paper citation edges. All graphs are made undirected if they are originally not. The data statistics after the transformation are listed in Table I. On each dataset, the task is to predict node labels. Although smaller datasets such as ogbn-arxir and ogbn-producte could easily fit into the main memory in our setting, they are included in the evaluation to demonstrate the competitive model quality produced by HierBatching.
Table I: Summary of evaluated datasets
Dutaset
Nodes
# Eddes
Feature
Classes
Multi-label
Train / Val/Tess
Raw data size
ogbo-arxiv
169,343
2,332,486
128
40
No
0,5470.18700
123MB
rggn-proddcte
2,449,029
123,718,024
100
47
No
0.08 0.02 10.90
2,8GB
1gbn-pupers100M
111,059,956
3,231,371,744
128
172
0.01 /0.001 /0.002
103GB
Mag240M-C
121,751,666 666
2.595,497,852
768
153
No 0.01 000001 / 0.001
214GB
Mag240M
244.160,499
3,456,728,464
768
153
No 4.5e-3/ 6c-4 6c-4
407GB
Evaluation platform. We use two compute platforms in our experiments, local cluster and AWS.
Each compute node in the local cluster has 32 CPU cores, ITB DRAM and 4 NVIDIA V100 GPUs. The AWS instance has 24 CPU cores (2-way hyperthreading, 48 threads), 386GB DRAM and 4 NVIDIA T4 GPUs The AWS machine is equipped with a fast local flash storage while the local cluster stores the datasets in a networked file system. The difference of the two is useful in showing how 1/O throughputs could affect training speed. We regulate the DRAM size on both platforms, e.g.. from 128GB to 386GB, to meet the memory budget assumptions of different experiments.
Experimental Setup. We implement HierBatching based on py PyTorch Paszke et al. (2019) and DGL Wang et al. (2019). We use the micro Fi-score measure accuracy. For accuracy-related experiments, we run the training for a fixed number of epochs as listed in Table in the Appendix. We report the test scores produced by the model at the best validation epoch during the training. To obtain the training time per epoch, we run each experiment for five epochs and take an average. Further details of our experimental settings are deferred to Appendix C.
4.1 ACCURACY COMPARISON WITH STANDARD NEIGHBORHOOD SAMPLING
To demonstrate that HierBatching retains the accuracy of standard in-memory training schemes, compare test accuracy of HierBatching (HB) with that of neighbor sampling (NS), the standard mini-batching and sampling method used to train large-scale GNNs (Hamilton et al., 2017a). NS assumes full graph accesses during sampling. We allocate as much memory as NS needs run in memory. For HB, we choose static cache capacity C, = |V|/100 and number of passes = 2. For a given dataset and model, we keep common syper-parameter the same (e.g. GNN layers, hidden dimensions, learning rates) across all methods. Detailed hyper-paramete settings are in Appendix C.
Table lists the test F1-micro scores obtained by NS and HB. We observe that their resulting accuracies are nearly the same across models and datasets. However, without the static cache, HB (-s) suffers notable accuracy degradation (21 1 () many cases, as shown red. This observation demonstrates the importance of static cache for HierBatching, We also observe that HB and the no mega-batch reuse version, HB (-r), achieve a similar accuracy, which means that mega- reuse does not compromise the training quality. Note that similarly to HB (-s), MariusGNN (Waleffe et al., 2022) also suffers accuracy degradation, as it does random partitioning without compensating the edge loss. We conduct a detailed comparison with MariusGNN in Appendix D.2.
4.2 CONVERGENCE RATES AND TRAINING TIME
Fig. 3 shows the model convergence in terms of epochs, for both NS and HB approaches. We observe that without the static cache, HB (-s) not only lowers final accuracy but converges at much slower rate, while HB (-r) converges almost as fast as NS. Even though we follow a non-standard stochastic training approach in HB by reusing each mega-batches, the model still converges well and in some cases even faster than NS (e.g., ogbn-productsy primarily because it perform twice as many gradient updates per epoch. More gradient updates do not necessarily translate into longer training time in HB since the system is bottlenecked by I/O, not gradient computation. As we will show immediately, the training time per epoch in HB is very much comparable to the in-memory NS approach.
7

---

Under review as a conference paper at ICLR 2023
Table 2: Comparison of test accuracies (Fl-micro score) between HierBatching (H2) and neighbor sampling (NS). HB uses |v|/100 and p 2. HB (-s) disables the static cache on top HB. i.e., HB (-r) disables mega-batch reuse on top of EB, ie., = 1. Significant accuracy drops are hignlighted in red.
GNN Model
Dataset
NS
HB (-s)
HB (-x)
HB
oghn-arxiv
7T.52
70.99
71.43
71.42
oghn-products
78.90
78.98
78.90
78.84
SAGE
oghn-papers 100M (00M
64.94
63.85
64.56
64.83
Mag240M-C
65.92
64.94
65.69
65.98
Mag240M
68.83
67.08
68.25
68.56
ogbn-arxiv
71.76
69.58
71.21
71.73
ogbn-products
79.54
79.61
79.58
79.55
GAT
ogbn-papers 100M 10MM
64.58
61.45
64.31
64.20
Mag240M-C
65.74
65.06
65.69
66.09
Mag240M
68.40
67.33
68.07
68.89
ogbn-arxiv
70.24
68.61
70.22
70.10
ogbn-products
75.70
76.58
76.15
76.77
GIN
ogbn-papers
100M 100M
65.07
62.33
64.63
64.81
Mag240M-C
63.73
62.93
63.59
63.36
Mag240M
67.47
66.33
67.02
66.58
ogbn-products
ogbn: ogbn-papers p00nn-ppprr100MMM
Mag240M-C
Vilidetion Score
664
15
2.2-
V5 HBIS)
6:90
HBI 5)
HBL
MB144)
HM(4]
Figure GraphSAGE convergence history neighhor sampling and HierBatching.
We compare the training speed HierBatching with two settings of DGL, DGL* and DGL+mmap. DGL* is the vanilla DGL which requires all data be resident the memory. It uses 386GB main memory. DGL+mmap adds the mmap support on top of DGL. to handle the case of insufficient main memory. This setting uses 128GB main memory.
Table 3 lists the training time per epoch on the AWS machine. The first observation is that HierBatch- ing (HB) run all of the cases, thanks HierBatching's awareness of the memory hicrarchy. In contrast, DGL runs out of memory for the largest dataset, Mag240M, which requires 349GB space to accommodate the feature data and 135GB for the graph structures (DGL maintains all three COO, CSC and CSR formats in memory). Even with mmap support, DGL+nmap can not run Mag240M within the limited memory budget, since it fails hold the graph structures memory.
The second observation is, HB runs significantly faster than mmap, and is only slightly slower than in- memory training. Compared with DGL+nmap, HierBatching achieves 2.6x 20.4 speedup across different datasets and models (4.3x on average), mainly because of the improved spatial locality. As shown in $3.5, speedup depends on training nodes ratio 7 and fanout F, thus speedups vary across different datasets. Compared to DGL*, The training HierBatching can achieve competitive training speed with maximum slowdown 41% (GIN on mag240M-C). even though HierBatching has only one third of the memory capacity. Surprisingly, for some cases, e.g., GIN ogbn- gebn-papers 100M, HB faster than DGL It turns out that these cases are GPU compute bound, and HB usually has smaller sampled graphs than DGL* which means less GPU computation. Overall, these results demonstrate that HierBatching is extremely efficient in taking advantage of the system resources.
Notice that the AWS instance has faster storage than the local cluster. We show the training time per epoch on the the local cluster in Table in Appendix D. Due to slower network-basee storage
We use the PyTorch API torch. Stwrtattereeee.. f from_fi file 1 to create mmap-ed tensors. It is infeasible to mmap graph structure data without significant modifications the DGL codehase. Thus, we only mmap node features.
8

---

Under review as a conference paper at ICLR 2023
Table Comparison of training time (sec) per epoch between HierBatching (HB). DGL* and DGL+mmap, the AWS machine. DGL uses 386GB memory, while HB and DGL+ use 128GB memory.
SAGE
GAT
GIN
Dataset
DGL
DGL+mmap
DGL*
DGLmmmap
DGL*
DGL+
babn-pupers! 100M
202.6
1017.8
278.0
382.3
1426.3
385.8
822.2
9131.6
448.0
Mag240M-C
178.6
678,3
249.4
379.9
1042.7
326,9
183.5
664.6
258.3
Mag240M
OoM
OoM
521.3
OoM
DoM
546.6
OoM
OoM
528.3
papersI00M
Mag240MCC
72.5
67.5
Runtime Percentage
100
72.0
66.5
Accuracy
Accuracy
65.5
71.0
64.5
70.5
test-accuracy
63.5
test-accuracy
10
CPU to GPU
vacurac
62.5
val-accuracy
D.04 0,06
0.08
0,02
Static cache ratio
Static cache ratio
H6
HB.
mmap
HB
HB.
mmap
(a) ogbn-arxiv
(b) ogbn- pabb--apersS00M
Figure 4: Training time break- down. Pipelining is disabled to better illustrate the overhead of each components.
Figure 5: Trade-off static and dynamic cache sizes. 'Static cache ratio' refers
C./[V]. The overall budget dynamic cache and static eache [V] x 1%.
system, we observe even larger speedup (up to 58x) ) of HierBatching over DGL+mmap. Note that this network-based storage architecture is quite common in modern datacenters and supercomputing centers, which means HierBatching will be quite useful in the real systems.
4.3 ABLATION STUDY AND SENSITIVITY STUDY
In order to study the influence of spatial locality, we disrupt HB's feature contiguous layout in disk, denoted as HB-, which thus access node features randomly and can not enjoy spatial locality. HB- differs from DGL+mmap breakdown three approaches. Interestingly, HB- exhibits different behaviors with two datasets. For gebnnpapers papers100M 100M where the node feature size is relatively small, HB- allows the operating system to cache most of the feature data in the memory as training proceeds and yields almost no slowdown. This is possible with + since the full graph structure takes almost all the available memory space, leaving little space for caching. In contrast, the node feature size of Mag240M-CC far exceeds the memory budget and cannot be cached efficiently. In this case, HB- behaves very similarly with DGL+mmap, spending most of the time on gathering node features from the external storage.
it forms mega-batches in memory. Fig. 4 reports the training time
Given a certain memory budget, the static cache capacity C, and dynamic cache capacity Ca are two competing parameters. Increasing C, can keep more high-degree nodes in the memory, but also decreases C₂ and thus reduces randomness. Oppositely, increasing C2 increases randomness but reduces the degrees compensation by the static cache. We conduct an experiment with fixed memory quota for dynamic cache and static cache, and study how the accuracy changes as the static cache ratio changes in Fig. 5. As shown, all curves in both figures peak at static cache ratio between (0, 0.04), which demonstrates that there does exist a sweet spot to pick the sizes of the two caches.
CONCLUSIONS
We have proposed a novel locality-aware GNN training approach, HierBatching, for scaling up GNNs to massive graphs. HierBatching targets a single machine with multiple GPUs but limited memory budget. The core our approach hierarchical batching, which hicrarchically divides the training data to match the memory hierarchy of the machine. The main memory serves cache for the disk, and is fully utilized as a dynamic cache and static cache, to balance training speed and prediction quality. Overall, our approach effectively improves both spatial and temporal locality. Experiment results demonstrate that HierBatching dramatically improves GNN training speed for massive graphs on single machine, while retaining the prediction accuracy.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We provide a link to an ananymous Github repository hosting the code, scripts and instructions to reproduce results in evaluation section: https://github. http:/gihuub.com/Herrrreee Hetr//eeeBBachiggeeeeBaaaae instructions on how to prepare the datasets, build and run the code are included in the README. txt file under the repository.
Detailed
REFERENCES
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference Learning Representations, 2018. URL
https: /ttpp:://pperevviie
net / forum sediiddtttttttt
Wei-Lin Chiang, Xuanqing Liu, Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen. An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 257-266, New York. NY, USA, 2019, Association for Computing Machinery. ISBN 9781450362016. doi: 10.1445/292500:333995. URL https: /to.. www.lorgg100.. 014/10.11555 3292500 3330925.
Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John Dickerson, Furong Huang, and Tom Goldstein. Vq-gnn: universal framework to scale up graph neural networks using vector quantization. Advances in Neural Information Processing Systems, 34:6733-6746, 2021.
Jialin Dong, Da Zheng, Lin F. Yang, and George Karypis. Global neighbor sampling for mixed cpu-gpu training on giant graphs. In Proceedings of the 27th ACM SIGKDD Conference on
Knowledge Discovery & Data Mining, KDD '21, pp. 289-299, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 4783430333 doi: 10.1145/3447548.3444445
URL https:tt////mmm /ooi org/10 1145/344124 3447548 0.888346777 3467437.
Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks historical embeddings. In International Conference on Machine Learning, pp. 3294-3304. PMLR, 2021.
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. USENIX Association, July 2021. ISBN 978-1-939133--2-99 URL https:tttt.........t....ttt //ww://wwwwww////// u.enix. org/ http://offeeeeeeeeeeeeoe asdei/sddi22. /ttpsd/ett/eeeteatttee http:p/eseetaattto/gggaaaeea
on/ gandhi.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS '17, pp. 1025 1035, Red Hook, NY, USA, 2017a. Curran Associates Inc. ISBN 9781510860964.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint arXiv::709.0000 2017b.
Jeff HaoChen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In ICMI., 2019.
Loc Hoang, Xuhao Chen, Hochan Lee, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali. Efficient Distribution for Deep Learning on Large Graphs. Proceedings of the Workshop Graph Neural Networks and Systems, 2021. URL https: http://chhhww.....c github. io/
docs/ / gnnsys-n---ggnmo 2021. pdf.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. sociates, Inc., 2020. URL httpattttaa//prreeeiiigg http:///ppoooeeeennnnnnee....... neurips wcsps.cc//oo F60041116cc522244773327772288663
Curran As- /iile/
10

---

Under review as a conference paper at ICLR 2023
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprint 0rXiv:2103.094:0 2021.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou, Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 675-684, 2021.
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy, scalability, and performance of graph neural networks with roc. In Proceedings of the 3rd Conference on Machine Learning and Systems (MLSys), March 2020.
Tim Kaler, Nickolas Stathas, Anne Ouyang, Aexandros-Stavrg Iliopoulos, Tao Schardl, Charles E. Leiserson, and Jie Chen. Accelerating training and inference of graph neural networks with fast sampling and pipelining. In D. Marculescu, Y. Chi, and C. Wu (eds.), Proceedings of Machine Learning and Systems, volume pp. 172-189, 2022. URL https::////cc........ttt.ttt https::/ / 35 f a 8d4 6el edc05
miays. p.f.
org/paper 2222 fi e
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal scientific Compuring, (O(1):35-3392 1998.
Gurneet Kaur and Rajiv Gupta. Go: Out-of-core partitioning of large irregular graphs. In 2021 IEEE International Conference on Networking. Architecture and Storage (NAS), pp. 1-10, 2021, doi: 10.1 N0.10099NSSS1152222211.333
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, ICLR 16, 2016.
Zhiqi Lin, Cheng Li, Youshan Miao, Yunxin Liu, and Yinlong Xu. Pagraph: Scaling gnn training on large graphs via computation-awas -ware caching. In Proceedings of the 11th ACM Symposium on Cloud Computing, pp. 401-415, 2020.
Zirui Liu, Kaixiong Zhou, Fan Yang, Li Li, Rui Chen, and Xia Hu. Exact: Scalable graph neural networks training via extreme activation compression. In International Conference on Learning Representations, 2021.
Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexan- der Heinecke, Dhiraj Kalamkar, Nesreen K. Ahmed, and Sasikanth Avancha. DisIGNN: Scalable distributed training for large-scale graph neural networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '21, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 470344408, doi: 0tt.:/4445888734488888 URL https: : http//o..oo///////// http://oooo///..//////////////// org/10. 11155/345882 7.3808868.
Jason Mohoney, Roger Waleffe, Henry Xu, Theodoros Rekatsinas, and Shivaram Venkataraman. Marius: Learning massive graph embeddings on single machine. In /5th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pp. 533-549. USENIX Association, July 2021. ISBN 978-1-939133-22-9, URL https: /www http://..w........ org/ conference// mowoone....o.oooooooooooooo
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary 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 H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8026-8037. Curran Associates, Inc., 2019. URL http: hwwpppaappppeaaa/eeeeeeeeeeeeeea .eceerrsssiiiss cc/ httpp/aper//////////// 9015- 1015-pytorch-eee wwwrrrrhh--mmmmeeaitiieeeeeeeeee weiiiipeeaiiiieee wewraativveeyllllleeee wwiggghh-hfffomm pdf.
deep- www.rlleernnnnnnnnnnn
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Anand Sivasubramaniam, and Mah- mut Kandemir. Gen meets gpu: Decoupling "when to sample"fron fromm "how to sample". In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18482-18492. Curran Asso- ciates, Inc., 2020. URL 618877788111118888888 pdd. d714d2c5a 66551 4eleaa5814555558dddddeaa
wttp:ppppp.ccpppe////////////// /ftee//
11

---

Under review as a conference paper at ICLR 2023
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Mahmut T Kandemir, and Anand Sivasubrama- niam. Learn locally, correct globally: A distributed algorithm for training graph neural networks. In The International Conference Learning Representations, 2022.
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, SC '20. IEEE Press, 2020. ISBN 9781728199986
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, ICLR '18 2018. URL htwps:ttt//ttttt /
net/
Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman. Mariusgnn: Resource-efficient out-of-core training of graph neural networks. CoRR, abs/2202.02365,, 2022.
URL pestts://aaxti org/ abs 2202. 02365.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye. Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning on graphs. International Conference on Learning Representations, ICLR '19, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, ICLR '19, 2019. URL https: wpwprevvewww...ec///////. wnt.eewweeeet.......
net/ htw.l//wweet///uuneeeeeaaaa coorum?id=ryGe AA55M.
Hongxia Yang. Aligraph: A comprehensive graph neural network platform. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 3165-3166 New York, NY, USA, 2019. Association for Computing Machinery. ISBN 478145066 doi: 10.1145/229200033344444 URL https: /tw.///ooioio/ org/10.1145; 3292500. 3340404.
Jianbang Yang, Dahai Tang, Xiaoniu Song, Lei Wang, Qiang Yin, Rong Chen, Wenyuan Yu, and Jingren Zhou. Gnnlab: a factored system for sample-based gnn training over gpus. In Proceedings of the Seventeenth European Conference Computer Systems, pp. 417 434, 2022.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020. URL https: / www.reveee....eecooooee w htt////rrmmiii///// BJe.edddBBJBBBBBBBe
Dalong Zhang, Xin Huang, Ziqi Liu, Jun Zhou, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Lin Wang, Zhiqiang Zhang, and Yuan Qi. Agl: A scalable system for industrial- purtroeellpppposeeeeeeee graph machine learning. Proc. VLDB Endow, 13(12):3125-3137, Aug 2020. ISSN 2150-8097, doi: 3.155331555
10.147788/315448.3415557 URL https: /oii
Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. DistDGL: Distributed graph neural network training for billion-scale graphs, 2020.
12

---

Under review as a conference paper at ICLR 2023
A
PROOF OF EQ. (3)
Simplifying Eq. (2), we obtain
ACC,.Cs) (s) = Σ
Σ
1(u,
NECD vECs
E MECD WECs
Σ
v(,
E
1 (u,,))
(4)
vEConCs
Σ vcCy uECp
Σ
1(,,))
Σ
Σ
v(u,v).
vEConCss weOD
Define the partition assignment function f: f(v) = = v E C. Then, by substituting
ACC Cs) with Eq. (4) in Eq. ()), follows that
Σ
Σ
1(u
Σ
Σ ((u,v)
bECs mech
vECD nCs NEC
Σ ΣED
1(,,v) EE
Σ
Σ
1(,
vECs wEC(
DEO
nCs
nC' NECH(W)
(5)
1(,v)) Σ Σ
1(,
vECs NEV
vcCs uEC
Σ VECs
(degree(v) degree sub (v))
Therefore, maximize Eq. (5) with a cache budget we sort all nodes V according to degree dugree (v) and take the first i nodes.
B CHOICE OF PARAMETERS IN ALGORITHM
Choosing Np. Assume that Sp = Np the size of single partition, 1) is the node feature dimension, Sfeat is the data precision in bytes, and Sopt is the optimal disk request size that leads to sequential access. We choose Sp be no less than Sopt/ x Seea)), such that disk accesses are sequential. Hence, Np is no greater than [V] x D x Steat/ S As mentioned in $3.1. the partition should not be too large, either. In practice, we recommend choosing No so that each partition consists several thousands of nodes.
Choosing Na and r.. Let Na/Np- The static cache capacity rs |V| and the dynamic cache capacity гa x |V| are faced with trade off: if the dataset has A GB feature data and B GB edge list data, we require 2(r, + rr) x (A + B) < C' where is the allocated memory space for the static and dynamic cache. The factor 2 comes from double buffering required for pipelining. Typical values of re and Fa in our experiments are r. 0.01 and ra E [0.0625, 0.25].
Choosing It is straightforward to select the reuse ratio p after training for few epochs. Assume the time to load and construct and mega-batch Tioads and the time to train mega-batch with reuse is Teomp. Since the two stages are pipelined, the latency between two mega-batches is marr(Toad. Tcomp]- ). Only when Tioad > Teomp- we select reuse ratio < S Troad/ Taud//Tcunn Teomp to hide the remaining data-loading latency and guarantee that Toomp never becomes the bottleneck.
Other parameters including the bini- size B are common hyper-parametted present in most GNN training systems. We do not have additional constraints for those parameters.
13

---

Under review as a conference paper at ICLR 2023
C EVALUATION DETAILS
C.I IMPLEMENTATION DETAILS
Since static nodes are high-degree nodes, their edge lists may too large to stay in the main memory, especially for power-law graphs. As trade-off, only the features of the static nodes are stored in the cache, while the edge lists are kept the disk. Because the static nodes are scattered in the disk, store another copy of the edge lists for them in the disk contiguously, remain sequential when edge lists are moved to the memory at every reloading of the dynamic cache mega-batch). batch). While loading edge lists, only keep the edges of the induced subgraph the mega-batch in memory, which needs much less memory space.
that disk accesses
(i.e., forming mega-bate
C.2 CLARIFICATION OF DATASETS
The complete Mag240M dataset is a heterogeneous academic graph on which a relational GNN model would work the best. For ease of implementation, the evaluation we treat homogeneous graph and apply non-relational GNN models instead. Only minor accuracy drops are observed when compared with relational GNN baselines posted on OGB-LSC benchmark Hu et al. (2021). For datasets without publicly available test sets (Mag240M-C, Mag240M), report the highest validation F Fl-scores. Considering the scales of large datasets, test and validation are performed with minibatching and sampling, similar to the practice in Kaler et al. (2022).
C.3 HYPER-PARAMETER SETTINGS
Table lists the key hyyer-parameete we use our experiment. Note that when evaluating the training speed, we use the same
except that GAT uses hidden size of 512 in Table 3, but 1024 Table due to the smaller GPU memory on the AWS instance.
Table Training configurations for results in Table
SAGE
Dataset
Epochs
Hidden
Learning
Dropout 0.5
Fanouts
Layers
ogbn-arxiv
256
0.001
(15.10.5))/50050300)
3
ogbn-products
50
256
0.001
0.5
(15,10,5) / (20,20,20)
3
ogbn-papers 100M 00M
25
256
0.001
0.5
(15,10.5) (20.20.20)
3
Mag240M-C
25
1024
0.001
0.5
(25,15) (25.15)
2
Mag240M
1024
0.001
0.5
(25.15) / (25,15)
2
GAT
Dataset
Epochs
Hidden
Learning rate
Dropout
Fanouts
ogbn-arxiv
100
256
0.001
0.5
(15, 10, 5)7 (50,50,00
ogbn-products
512
0.5
(15, 10, 5) (20,20,20)
3
ogbn-papers1100 00M
25
1024
0.001
0.5
(15, 10, 5) (20,20,20)
3
Mag240M-C
25
1024
0.001
0.5
(25.15) (25,15)
2
Mag240M
25
1024
0.001
0.5
(25.15) (25.15)
2
GIN
Dataset
Epochs
Hidden
Learning rate
Dropout
Fanouts (20,20,20) (20,20,20)
ogbn-arxiv
100
128
0.001
0.5
3
ogbn-products
50
512
0.003
0.5
(15,10.5) (20,20,20)
3
ogbn-papers100m 100M 100
25
512
0.003
0.5
(20,20,20) / (20.20,20)
3
Mag240M-C
25
1024
0.001
0.5
(25,15) / (25,15)
2
Mag240M
25
1024
0.001
0.5
(25,15) (25,15)
2
Table 5 shows some extra parameters for HierBatching. Np is the total number of partitions. N₂ is the maximum number partitions held the dynamic cache. r, = Ca/[V| is the ratio of nodes kept in the static cache. p is the number of passes per mega-batch.
14

---

Under review as a conference paper at ICLR 2023
Table Extra training configurations for HierBatching in Table
Dataset
N
Na
Fs
p
ogbn-arxiv
1024
256
0.01
2
ogbu-products
40%6
512
0.01
2
ogbn-papers 100M
16384
1024
0.01
2
Mag240M-C
16384
1024
0.01
2
Mag240M
16384
1024
0.01
2
D ADDITIONAL EXPERIMENTS
D.1 TRAINING PERFORMANCE WITH THE LOCAL CLUSTER
Table shows the training time per epoch on the local cluster. As it has faster GPUs (V100), its in-memory training, i.e., DGL* * is faster than that the AWS machine. However, since it uses network-based storage system, its random access latency is significantly larger than that of the AWS machine. Consequently, the DGL+mmap setting performs dramatically worse than that on AWS. In comparison, HierBatching (HB) becomes faster than that on AWS, as the storage system in the local cluster has similar sequential throughput as that of AWS, and HB can fully enjoy fast sequential accesses, thanks to the spatial locality aware design.
Table Comparison training time (s) per epoch between HierBatching (HBB). DGL* # and DGL+mnap on the local cluster. DGL" uses 386GB memory, while HB and DGL+mmap use 128GB memory. TO: timeout (>5 hours). The unusual long training time with the Mag240M dataset is possibly due to the inefficiency of the network-basse storage system when handling huge files. We forward the readers Table 3 for realistic runtime ratios between Mag240M and other datasets.
SAGE
GAT
GIN DGI.+mmap
Datasel
DGL
DGL+tmapp
HIB
DGL
DGL+tmap
I1B
DGL
HIB
ogbn-papers
105.4
11037.5
190.3
254.2
11850.3
260.7
348.7
TO 238.8
Mag24IM-C
77.7
TO
229.1
142.3
TO
185.8
75.7
TO
193.7
Mag240M
OoM
0oM
1708.3
OoM
OoM
1828.5
OaM
OoM
1788.9
D.2 COMPARISON BETWEEN HIERBATCHING AND MARIUSGNN
Both MariusGNN and HierBatching operate over pre-partitioned graph datasets, loading parts of the graph in the memory for training at one time. MariusGNN proposes two modes for training node-predd mrdecprediction GNNs:
Sequential mode. When the training nodes and its induced subgraph could fit into the main memory, MariusGNN pins all training nodes and selects partitions randomly to form partial in-memory graph. The graph remains unchanged throughout an epoch.
Dispersed mode. When the sequential mode is not applicable, MariusGNN assumes the training nodes are dispersed across partitions. It then loads partitions into the in- in-memory buffer in semi-random fashion until all training nodes appear once in the memory.
Our approach is similar to the dispersed mode of MariusGNN, with several key differences: 1) we identify the importance of min-cut graph partitioning while MariusGNN simply uses random partitioning: 2) MariusGNN in the dispersed mode does not keep a static cache; 3) MariusGNN never uses mega-batch reuse hide extra 10 latency.
An important component in MariusGNN is COMET, a fine-grained partition replacement policy. In addition the number of partitions p. number of in- in-memory partitions c, specifies one extra tunable parameter 1 Σ corresponding to the number of partitions to be replaced at each step. The partition sampling procedure in HierBatching could be seen as implementing a specific COMET policy with I 1= c. We argue that it is not a limitation of HierBatching. The value of / actually has influence on the overall 10 traffic in the dispersed mode, since all partitions are loaded once in an epoch. Instead, smaller / would lead to less data randomness in the mega-batch and could affect the model accuracy. Although MariusGNN does not have analysis of how to choose for node prediction tasks, as a side note, MaN suggests make I large as possible for link prediction tasks (Section 4).
15

---

Under review as a conference paper at ICLR 2023
Compared to our work, the main concern with MariusGNN is that employs techniques make up for the lost neighbors during the mega-batch construction. This has not been an big issue because the datasets used in MariusGNN are "easier" in sense: e.g. for rgbn-papers 100M if we only keep edges connected by training nodes for training and discard the remaining 99 edges, the model could still achieve test accuracy of 62.95%, accuracy drop of merely 2% from training with the full graph. To reveal the risk of accuracy degradation in MariusGNN, we construct a new dataset by changing the data splits of ogbn-arxiv: 10% of nodes are chosen randomly as the training nodes and the rest as validation nodes. We compare the validation F1 scores of different approaches (we use the same set of sypee-parameters as our paper):
NS (training with full graph): 69.61+.07
HB (Na/N, = 1/16,r,, = 0.01): 69.64+.08
MariusGNN (sequential mode, c/p 1/8): 67.08t.14
MariusGNN (dispersed mode, c/p 1/8): 67.29
With this "harder" dataset, MariusGNN suffers from more significant accuracy losses, while HB still retains the model accuracy with NS. Therefore, we believe that HierBatching is more robust out-of-core training solution than MariusGNN.
16


Reviews:
[{"review_id": "r1LIwQJZKi", "reviewer": "Reviewer_bDQL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors describe a hierarchical strategy for storing large batches of GNN training data in multiple levels of memory in a single system. By partitioning the storage of GNN training data between the extremely large out-of-core disk, smaller but faster CPU DRAM main memory, and much more limited but fastest GPU DRAM memory they are able to train GNNs on graphs that are far too large to fit into either GPU or CPU DRAM memory much faster than naive strategies. To achieve this the authors compare and contrast the training accuracy vs performance tradeoff of their approach vs the traditional neighbor sampling strategy used by default in DGL. A detailed strategy for detailing the high variability in the degree of nodes in a given graph is also given and the authors propose a decomposition of the cache into dynamic and static components to keep the highest utilized nodes throughout the training process in fast memory. An ablation study shows the utility of their approach and the impact on both training accuracy and speed.", "summary_of_the_review": "Overall the paper addresses an important issue regarding the training of large graphs on machines with limited memory. The authors present a strategy to mitigate the limitations associated with training large GNNs and yield a training procedure that effectively utilizes the hierarchy of multiple memory systems of different capacities and performance characteristics. Though the authors mention the need to minimize the graph cut metric in Section 3.1, was Metis the easiest choice or the best? Also, in Section 3.1 the authors mention an out-of-core partitioner was used when the graph exceeded the memory capacity, please add a reference. It may be worth considering a simpler way to motivate the utility of the static cache size in terms of the hit rate over an epoch or similar metric of typical interest for studying the utility of caches. More information regarding the graph partitioning hyperparameters is provided in the Appendix, Section C.3, were the number of partitions chosen based only on memory considerations? It would be useful if the comment in section 3.1 regarding partitions that are too large or small could be supported by data.", "strength_and_weaknesses": "Strengths\n-------------------\n- The experiments support the author's motivation to provide a static cache for a small number of highly connected nodes and re-using nodes within a mega-batch while loading additional nodes from disk during training.\n- Ablation studies provide extensive data regarding the tradeoffs between the accuracy and performance of the different approaches.\n- As the graphs of interest for GNN training continue to increase in size it will be of imperative importance to make effective use of the memory hierarchy of the entire system. As demonstrated in Section 4.2 the authors are able to train extremely large graphs using a fraction of the DRAM memory and incurring a moderate amount of degradation in performance.\n\nWeaknesses\n-------------------\n- The major weakness is the lack of theoretical motivation to support the training scenario the authors describe in section 3.3. However, the authors acknowledge this weakness openly in the paper and pose it as an interesting area for future work.\n- Though the ablation studies were beneficial to support the author's claims regarding the use of a static cache to store the nodes with the largest degrees it may have been more straightforward to use a typical metric for cache effectiveness, such as hit-rate per minibatch.\n- The proposed scheme introduces yet another set of hyperparameters that much be tuned per input graph to yield the best results in terms of performance and accuracy, as illustrated in Figure 5.\n- The costs and impact of different graph partitioning strategies are not provided (ie Metis partitions may be of low quality depending on a number of factors, would that have any notable impact on the accuracy of the results?).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "W6r83KwTyiR", "reviewer": "Reviewer_wEnk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In order to train GNN efficiently on large graphs with a single machine and external storage, this paper proposes a locality-aware training scheme to reduce the data movement time. First, it partitions the graph using METIS. The main idea is to save a mega-batch, which is randomly sampled from partitions in the main memory, and construct mini-batches from the mega-batch. To alleviate the performance from insufficient neighbors in mega-batch, it permanently saves nodes with the highest degree. Reusing each mega-batch several times and pipelining further reduces the total training time.", "summary_of_the_review": "Reducing the data movement of GNN training on CPU-GPU nodes has been extensively studied recently. The paper proposes a straightforward technique.  However, it is unclear whether the technique can be applied to more general GNN tasks. ", "strength_and_weaknesses": "## Strength:  \nThe experiments show up to 20 times speedup than in-memory DGL on several large graphs. The analysis of hyper-parameters is in detail.\n\n## Weakness:\n1. My main concern is the convergence of the training because both static cache and reuse of mega-batch can change the sampling distribution of nodes. \n2. I guess the performance including speedup and accuracy is also highly dependent on the parameters, such as mega-batch size and reuse times. Do you need to tune these parameters?\n\n## Questions:\n1. Table 5 provides the partitions (N_d) in mega-batch for each dataset, but I’m not sure how the authors decide it. I think there is a trade-off between accuracy and data loading time when using different N_d.\n2. How many mega-batches are in the main memory? I assume the number is two so that the main memory can read the next mega-batch from external memory and construct minibatches at the same time. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Rg6IRq6yeUH", "reviewer": "Reviewer_Hx4Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes HierBatching, a framework that conducts out-of-core training for GNNs on giant data on small main memory. HierBatching organizes the graph into closely connected partitions and loads some partitions to main memory to conduct training for locality. The nodes with the largest degrees are cached in main memory as they are accessed frequently. Pipelining is used to overlap disk read and computation. Experiment results show that HierBatching runs significantly faster than a naïve solution that directly reads disk.", "summary_of_the_review": "I like that the paper tackles an important problem and conducts solid engineering. However, the utilized techniques are well-know and have limited novelty. ", "strength_and_weaknesses": "Strengths\n\n1. Training GNNs on giant data is important, and out-of-core training is interesting as it makes training more accessible for practitioners.\n2. The paper is well-written with excellent clarity and logic flow.\n3. The codes are open-source\n\n\nWeakness\n1. The novelties of the proposed techniques are limited. Partitioning a graph into strongly connected clusters is a standard method to achieve spatial locality in graph processing, DistDGL also uses it for the distributed training of GNNs. Caching hot nodes in has been used by [a, b] to handle limited GPU memory. Moreover, overlapping computation and IO is a common technique in system design.\n\n2. HierBatching incurs accuracy loss, which may not be acceptable for some critical scenarios (e.g., recommendation, where marginal accuracy improvement translates into large revenue). \n\n3. The experiments can be improved. Figure 4 shows that HierBatching uses over 50% of the time for disk IO, which makes me wonder whether training with HierBatching is cheaper than using distributed in-memory solutions such as DistDGL. Note that DistDGL already conducts locality-aware graph partitioning, which reduces cross-machine communication. By using less time for IO, DistDGL may be cheaper than HierBatching is we purchase instances from AWS. Another interesting experiment is to show how the accuracy and training time of HierBatching changes with the amount of main memory. \n\n[a] https://arxiv.org/pdf/2111.05894.pdf\n[b] https://dl.acm.org/do/10.5281/zenodo.6347456/full/\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OR3MkbwKjDV", "reviewer": "Reviewer_p8K8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Proposes an out-of-core training approach for message-passing GNNs on very large graphs. Key idea is to partition the nodes + their features on disk, load a few partitions into memory, and then build batches on the subgraph induced by the currently loaded nodes as well as the most frequent nodes, and repeat. Also reports on a small experimental study.\n", "summary_of_the_review": "Potentially useful approach, but falls short on novelty, comparison to related work, analysis, and quality of results. I recommend to reject this paper.\n", "strength_and_weaknesses": "Strengths:\n\nS1. Can handle large graphs\n\nS2. I/O mostly sequential and interleaved with communication\n\nS3. Seems to provide reasonable results in study\n\nWeaknesses:\n\nW1. Novelty unclear; related work cited but otherwise ignored\n\nW2. Simplistic & purely heuristic, no analysis\n\nW3. Results far from SOTA\n\nW4. Experimental study setup shaky\n\nDetails:\n\nOn W1. The most relevant related work to this work is MariusGNN (cited here as Marius++). There is no discussion of how this work relates to MariusGNN, both technically and empirically. This is not acceptable. In fact, MariusGNN seems to use a more refined approach and perform experiments on (partly) larger graphs, smaller machines, with faster speed ups. (I coincidentally found a very short paragraph on Marius++ in the appendix after writing this review. I consider this discussion insufficient.)\n\nOn W2. The method proposed here is rather simplistic; e.g., is does not consider to exchange loaded partitions individually, but only all at once. More generally, the entire approach is driven by heuristics, but there is no analysis that justifies the approach. There is also no discussion of what could go wrong.\n\nOn W3. The test accuracies reported in Tab. 2 seem to be far away from SOTA. E.g., for ogbn-papers100M, this paper gives a test accuracy of 0.65 with SAGE. The OGB leaderboard lists an accuracy of .78 with GraphSAGE and goes up to >.85 in all of the top-10 approaches.\n\nOn W4. The experimental setup uses machines with more memory than used by the proposed methods. For evaluating out-of-core methods, this is not good: this memory may be used as a disk cache by the OS, for example.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject