BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing

• Data I/O and preprocessing are often bottlenecks in sampling-based GNN training, where cross-partition sampling and feature retrieval create high network traffic.The paper reports around 10% GPU utilization in a typical DGL job on a large graph, with around 90% of GPU cycles wasted.Source: §1 · p. 1
• BGL co-designs a dynamic cache policy with node sampling order; proximity-aware ordering improves FIFO cache hit ratios while keeping overhead acceptable.Nearby mini-batches sample nearby nodes to exploit temporal locality; static caching has low hit ratios when only a small fraction of a large graph can be cached.Source: §1 · p. 2
• BGL's partition algorithm preserves multi-hop connectivity within partitions while balancing load and scaling to giant graphs, reducing cross-partition sampling communication.It is tailored to typical GNN sampling algorithms that request multi-hop neighbors.Source: §1 · p. 2
• BGL profiles preprocessing operations' resource demands and isolates CPU cores, addressing contention among operations that may not scale well with more resources.Source: §1 · p. 2
• Geometric-mean speedups were 2.14x over PaGraph, 3.02x over PyG, 7.04x over DGL, and 20.68x over Euler.With the same GPU backend as DGL, BGL also reaches 99% V100 utilization when graphs are stored remotely and distributedly.Source: §1 · p. 2

2.1 Sampling-based GNN Training

• Mini-batch training samples a subgraph, retrieves its node features, then computes gradients and updates model parameters.The paper calls the first two stages data I/O and preprocessing.Source: §2.1 · pp. 2–3

2.2 Data I/O and Preprocessing Bottlenecks

• 99% of Euler and 83% of DGL training time went to data I/O and preprocessing, while maximum GPU utilization was 15% for DGL and 5% for Euler.The experiment trained GraphSAGE with one GPU worker on Ogbn-products partitioned across two servers.Source: §2.2 · p. 3
• With Ogbn-products, a three-hop batch of 1,000 nodes requires 5 MB of subgraph structure and 195 MB of node features; even a saturated 100 Gbps link could pull only 60 batches per second.Other preprocessing stages can reduce preparation to a few batches per second.Source: §2.2 · p. 3

2.3 Challenges in Removing the Bottlenecks

• Static caching can yield below 40% cache hits when only 10% of a giant graph’s nodes fit, while LRU and LFU updates incur near 80-millisecond overhead.The cited work describes this as a memory-capacity constraint for giant graphs.Source: §2.3 · p. 3
• Partitioning must scale to giant graphs while limiting cross-partition multi-hop sampling traffic and balancing training nodes, which may be only 10% of all nodes.Existing algorithms may focus on one-hop connectivity or balance all nodes rather than training nodes.Source: §2.3 · p. 4
• Uncoordinated preprocessing processes compete for CPU, memory, PCIe, and network resources, and existing frameworks leave resource allocation to naive or GNN-agnostic scheduling.BGL’s proposed response is a carefully designed resource isolation scheme.Source: §2.3 · p. 4

3.1 Overview

• BGL partitions the graph once, saves the partition results in distributed storage, and loads each partition into a graph-store server’s memory for sampling.The graph partition module can load graph data from a distributed storage system such as HDFS.Source: §3.1 · p. 4
• BGL co-designs FIFO caching with proximity-aware node ordering to improve feature-cache hits while keeping dynamic cache overhead low.The ordering uses BFS to improve temporal locality and introduces randomness to preserve model accuracy.Source: §3.1 · p. 5
• BGL merges nodes into blocks using multi-source BFS to preserve multi-hop connectivity, then assigns blocks to partitions while balancing training workload.Source: §3.1 · p. 5
• BGL formulates resource allocation as an optimization problem and isolates resources for pipeline stages to minimize their processing time under resource constraints.Source: §3.1 · p. 5

3.2.1 Dynamic Cache Policy

• FIFO cache updates take less than 20 ms per batch, meeting the roughly 20 ms computation time of a typical GNN iteration, whereas LRU and LFU have intolerable overhead.The reported overhead is amortized across cache lookup and updates on misses in an asynchronous pipeline.Source: §3.2.1 · p. 5

3.2.2 Proximity-Aware Ordering

• FIFO alone has an unimpressive hit ratio because it evicts hot and cold node features equally, but FIFO combined with proximity-aware ordering achieves the highest hit ratio among the candidate policies.Source: §3.2.2 · p. 5, §3.2.1 · p. 5
• BFS-based proximity-aware ordering places connected training nodes in consecutive batches to improve temporal locality, unlike random ordering.The example ordering {0,1,2,7,9} improves locality over {0,9,1,7,2} for batch size 1.Source: §3.2.2 · p. 6
• Proximity-aware ordering balances locality against convergence: traversal order can distort batch label distributions, while random ordering preserves state-of-the-art accuracy at the cost of poorer locality.Source: §3.2.2 · p. 6
• The ordering uses multiple BFS sequences from random roots in round-robin batches, then randomly shifts each sequence to vary late-batch label distributions while preserving consecutive-node order.Source: §3.2.2 · p. 6
• BGL selects the minimum number of BFS sequences that satisfies its convergence requirement, estimating shuffling error from label distributions and per-batch label frequencies.The implementation increases the sequence count until the error is below the requirement.Source: §3.2.2 · p. 6

3.2.3 Maximizing Cache Size

• BGL combines per-GPU caches with a CPU cache, assigning disjoint node IDs to GPU maps to avoid duplicate entries across GPU buffers.A GPU can fetch features from another GPU by point-to-point copy; the CPU cache further increases capacity and reduces graph-store traffic.Source: §3.2.3 · p. 6
• Queueing all operations for each GPU cache through one processing thread avoids races without locks and reduces overhead by 8x compared with locks.Source: §3.2.3 · p. 7

3.3 Graph Partition Module

• The partition algorithm is designed to combine billion-node scalability, multi-hop connectivity within partitions, and balanced training nodes.The paper notes that existing algorithms do not provide all three properties simultaneously.Source: §3.3 · p. 7

3.3.1 Partition Workflow

• Multi-source BFS forms connected blocks, which are coarsened into a graph for partitioning before assignments are mapped back to original nodes.The workflow further merges small blocks, then assigns blocks greedily for multi-hop locality and training-node balance.Source: §3.3.1 · pp. 7–8
• With multi-level coarsening, assignment complexity is O(|E2|j), versus O(|E|j) for the cited state-of-the-art approach, where |E2| ≪ |E|.Total partitioning complexity is O(|E|+|E1|+|E2|j).Source: §3.3.1 · p. 8

3.3.2 Assignment Heuristics

• The assignment heuristic trades off placing blocks near their multi-hop neighbors against balancing partition capacity and training-node load.It uses multi-hop block-neighbor locality, node count, and training-node count in selecting a partition.Source: §3.3.2 · p. 8

3.4 Resource Isolation For Contending Stages

• BGL divides training into eight asynchronous stages, whose work can contend for CPU, network, and PCIe resources.Examples include sampling and subgraph construction competing for server CPUs, and moving subgraphs and features competing for PCIe bandwidth.Source: §3.4 · p. 8
• Unrestricted resource sharing can hurt performance; cache processing may plateau beyond 40 CPU cores or degrade above 64.The paper attributes this behavior to memory-bandwidth limits and OpenMP synchronization and scheduling overhead.Source: §3.4 · p. 8
• Profiling-based allocation minimizes the maximum completion time across stages under CPU and PCIe capacity constraints.The decision variables include CPU cores for stages 1–4 and PCIe bandwidth for stages I–II; caching time uses a fitted function of its CPU allocation.Source: §3.4 · p. 8
• Brute-force search finds the resource allocation, with the paper reporting an average search time below 20 ms.Integer assumptions on bandwidth variables reduce the search space.Source: §3.4 · p. 9

4 Implementation

• BGL reuses DGL’s graph store and GPU backend and GMiner’s graph processing module for partitioning.The authors state that the design can be applied to other GNN frameworks with little change.Source: §4 · p. 9
• The cache engine queues GPU cache operations on a dedicated CUDA stream and uses pinned CPU buffers and CUDA callbacks to notify workers when queries finish.It also enables GPU peer-to-peer communication on cache-processing threads.Source: §4 · p. 9
• BGL uses concurrent OpenMP threads and an atomic tail to insert or evict cache entries in a circular GPU cache buffer.Because node features remain unchanged during training, inserting new features implicitly evicts old ones.Source: §4 · p. 9
• Separate sampling, feature-retrieving, and GNN-computation processes use Linux shared memory and CUDA IPC to avoid unnecessary memory copies.Source: §4 · p. 9

5.1 Methodology

• The evaluation uses Neighbor Sampling with mini-batches of 1,000 subgraphs and compares BGL against four open-sourced frameworks.BGL’s evaluation also includes three datasets and three representative GNN models.Source: §5.1 · p. 9

5.2 Overall Performance

• BGL’s geometric-mean speedups are 2.14x over PaGraph, 3.02x over PyG, 7.04x over DGL, and 20.68x over Euler across the evaluated settings.The reported range is 1.14x–69x; Figures 11–13 show throughput for three models across Ogbn-products, Ogbn-papers, and User-Item.Source: §5.2 · p. 10, Figure 11 · p. 10, Figure 12 · p. 10
• BGL’s gains vary by model: up to 30x over DGL and PyG for GraphSAGE and GCN, versus 14% to 8x for GAT.The authors attribute the smaller GAT improvement to its computation-bound attention mechanism and lower communication intensity.Source: §5.2 · p. 11

5.3.1 Graph Partition

• BGL reduces graph sampling time by at least 20% over random partitioning and by 14% on Ogbn-products and 10% on Ogbn-papers versus GMiner.The prose attributes the gains to multi-hop locality and training-node balancing; Table 3 reports sampling time per epoch and up to a 25% reduction.Source: §5.3.1 · p. 11, Table 3 · p. 11
• BGL’s partition algorithm runs as fast as the well-optimized original GMiner, according to the reported comparison.Table 4 covers one-time partition time before training, which the paper says can be amortized across many training tasks.Source: §5.3.1 · p. 11, Table 4 · p. 11

5.3.2 Feature Cache Engine

• On one GPU worker, BGL reduces Ogbn-papers feature-retrieval time by 98% versus Euler, 88% versus DGL, and 57% versus PaGraph.Figure 14 compares per-mini-batch retrieval time across different GPUs.Source: §5.3.2 · p. 11, Figure 14 · p. 12

5.3.3 Resource Isolation

• With four GPUs, BGL achieves up to 2.7x throughput over BGL without resource isolation across the tested settings.Figure 15 shows GraphSAGE throughput; the authors report reduced contention and lower OpenMP parallel overhead with isolation.Source: §5.3.3 · p. 12, Figure 15 · p. 12

5.4 Model Accuracy

• BGL converges to almost the same test accuracy as DGL on GCN, GAT, and GraphSAGE across Ogbn-products and Ogbn-papers.The evaluation runs 100 epochs per task; Table 5 reports accuracy.Source: §5.4 · p. 12, Table 5 · p. 12

Graph Partition Algorithms

• Common distributed partitioners such as Random, Round-Robin, and Linear Deterministic Greedy have low overhead but do not ensure partition locality.NeuGraph uses Kernighan-Lin partitioning, while Cluster-GCN builds training batches with METIS and stochastic multi-clustering.Source: §6 · p. 12

GNN Training Frameworks

• Among GNN frameworks, NeuGraph is limited to small graphs on multi-GPUs in one machine, while AliGraph and AGL do not exploit GPU acceleration.AliGraph combines distributed graph storage, optimized sampling, and runtime; AGL is implemented on MapReduce.Source: §6 · p. 12

GNN Training Acceleration

• Full-batch systems GNNAdvisor and DGCL assume graphs are stored on a single machine.GNNAdvisor uses 2D workload management and specialized memory customization; DGCL plans communication with METIS partitioning.Source: §6 · p. 12
• For mini-batch training, PaGraph assumes a single-machine graph, while P3 incurs synchronization overhead, can suffer above hidden dimensions of 128, and overlooks sampling.P3's random-hashing partitioning in subgraph sampling leads to extensive cross-partition communication.Source: §6 · p. 12
• GPU sampling systems NextDoor and C-SAW are constrained by small GPU memory and are therefore unsuitable for giant graphs.Source: §6 · p. 12

7 Conclusion

• BGL targets data I/O and preprocessing bottlenecks with a dynamic feature cache engine using proximity-aware ordering.It also uses a sampling-tailored graph partition algorithm to reduce cross-partition communication and profiling-based resource isolation for preprocessing.Source: §7 · pp. 12–13
• 20.68x average improvement over existing GNN training systems.The authors plan to open-source BGL in the future.Source: §7 · p. 13
• The authors plan to open-source BGL and continue evolving it with the community.Source: §7 · p. 13