GSplit: Scaling Graph Neural Network Training on Large Graphs via Split-Parallelism

Sandeep Polisetty, Juelin Liu, Kobi Falus, Yi Ren Fung, Seung-Hwan Lim, Hui Guan, Marco Serafini

Abstract

Graph neural networks (GNNs), an emerging class of machine learning models for graphs, have gained popularity for their superior performance in various graph analytical tasks. Mini-batch training is commonly used to train GNNs on large graphs, and data parallelism is the standard approach to scale mini-batch training across multiple GPUs. One of the major performance costs in GNN training is the loading of input features, which prevents GPUs from being fully utilized. In this paper, we argue that this problem is exacerbated by redundancies that are inherent to the data parallel approach. To address this issue, we introduce a hybrid parallel mini-batch training paradigm called split parallelism. Split parallelism avoids redundant data loads and splits the sampling and training of each mini-batch across multiple GPUs online, at each iteration, using a lightweight splitting algorithm. We implement split parallelism in GSplit and show that it outperforms state-of-the-art mini-batch training systems like DGL, Quiver, and $P^3$.

Introduction: The Redundancy Problem in GNN Scaling

Training Graph Neural Networks (GNNs) on massive graphs typically requires mini-batching across multiple GPUs. The industry standard is data parallelism, where each GPU independently samples and processes its own "micro-batch."

However, graphs are inherently interconnected. If two GPUs sample different target nodes, their $k$-hop neighborhoods often overlap significantly. This leads to massive redundant work: the same nodes and edges are sampled, loaded from memory, and computed multiple times across different GPUs.

Redundancy in GNN mini-batch sampling where target nodes share k-hop neighbors.

The authors found that data parallelism can result in up to 2.5x more feature loading and 1.2x more computation than a single-batch approach. Existing solutions like caching help with loading but don't solve the computation redundancy, while hybrid approaches like $P^3$ often introduce communication overheads that outweigh their savings.

Methodology: Introducing Split-Parallelism

The authors propose GSplit, which implements a technique called split-parallelism. Instead of each GPU having its own micro-batch, the system samples one large mini-batch for all GPUs and divides it into non-overlapping "splits."

Comparison of Data, Push-pull ($P^3$), and Split parallelism paradigms.

The Probabilistic Splitting Algorithm

The core challenge is partitioning these mini-batches on-the-fly without creating a bottleneck. GSplit uses a two-phase approach:

  1. Offline (Pre-sampling): The system runs a few "mock" sampling epochs to assign weights to vertices and edges based on access frequency. It then uses a standard partitioner (like METIS) to create a global mapping of every vertex in the graph to a specific GPU.
  2. Online (Constant-time Splitting): During training, when a mini-batch is sampled, GSplit uses the pre-computed global map to instantly assign nodes to their "owner" GPUs.

This ensures balanced load, minimized communication (low "cross-edges"), and consistent cache usage. GSplit also provides a layer-centric API that abstracts away the complexity of these shuffles, allowing researchers to use optimized single-GPU kernels for the actual GNN layers.

Evaluation and Results

GSplit was evaluated on three massive datasets: Orkut (3.1M nodes), Papers100M (111M nodes), and Friendster (65M nodes).

Key Insights

  • Redundancy as a Hidden Tax: In GNN scaling, data parallelism wastes PCIe bandwidth and GPU cycles. Split-parallelism trades minor communication (shuffles) for a massive reduction in redundant work.
  • Static Mapping for Dynamic Batches: A global partition based on expected access patterns is sufficient to provide probabilistic guarantees for any individual stochastic mini-batch.

Performance Benchmarks

GSplit consistently outperformed state-of-the-art baselines across models like GraphSAGE and GAT:

  • Vs. DGL: Up to 4.4x speedup (2.5x average).
  • Vs. Quiver: Up to 1.9x speedup (1.4x average).
  • Vs. $P^3$: Up to 4.1x speedup (2.4x average).
  • Scalability: GSplit showed superior scaling as GPU counts increased, capitalizing on more opportunities to eliminate redundancy.
  • Accuracy: The system maintains identical convergence and accuracy to standard training.

Limitations and Future Work

GSplit requires an offline pre-sampling and partitioning step (taking a few minutes for the largest graphs), which may be a hurdle for frequently changing graph structures. Additionally, the benefits are most pronounced when redundant computation costs are high; for very simple models, shuffle overhead might diminish returns. Future work includes extending the probabilistic splitting algorithm to handle dynamic, evolving graphs.

This summary is based on the paper "GSplit: Scaling Graph Neural Network Training on Large Graphs via Split-Parallelism".

Summary updated

Abstract

Graph neural networks (GNNs), an emerging class of machine learning models for graphs, have gained popularity for their superior performance in various graph analytical tasks. Mini-batch training is commonly used to train GNNs on large graphs, and data parallelism is the standard approach to scale mini-batch training across multiple GPUs. One of the major performance costs in GNN training is the loading of input features, which prevents GPUs from being fully utilized. In this paper, we argue that this problem is exacerbated by redundancies that are inherent to the data parallel approach. To address this issue, we introduce a hybrid parallel mini-batch training paradigm called split parallelism. Split parallelism avoids redundant data loads and splits the sampling and training of each mini-batch across multiple GPUs online, at each iteration, using a lightweight splitting algorithm. We implement split parallelism in GSplit and show that it outperforms state-of-the-art mini-batch training systems like DGL, Quiver, and $P^3$.
BibTeX
@misc{polisetty2023gsplit,
  author = {Sandeep Polisetty and Juelin Liu and Kobi Falus and Yi Ren Fung and Seung-Hwan Lim and Hui Guan and Marco Serafini},
  title = {{GSplit: Scaling Graph Neural Network Training on Large Graphs via Split-Parallelism}},
  year = {2023},
  eprint = {2303.13775},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.13775},
}

Loading related content...

Figure