# MegaGraph: Towards Efficient Training of Large-Scale Graph Transformers with Automated Hybrid Parallelism

arXiv: https://arxiv.org/abs/2609.34420 · HTML: https://mlsanity.com/paper/2609.34420/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 21 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Ring Attention with Blockwise Transformers for Near-Infinite Context](https://mlsanity.com/paper/2310.01889/) (2023)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [DGRec: Graph Neural Network for Recommendation with Diversified Embedding Generation](https://mlsanity.com/paper/2211.10486/) (2022)
- [Bridged-GNN: Knowledge Bridge Learning for Effective Knowledge Transfer](https://mlsanity.com/paper/2308.09499/) (2023)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [TorchGT: A Holistic System for Large-scale Graph Transformer Training](https://mlsanity.com/paper/2407.14106/) (2024)
- [GNNavigator: Towards Adaptive Training of Graph Neural Networks via Automatic Guideline Exploration](https://mlsanity.com/paper/2404.09544/) (2024)
- [Towards Affordable, Adaptive and Automatic GNN Training on CPU-GPU Heterogeneous Platforms](https://mlsanity.com/paper/2511.07421/) (2025)

## Abstract (arXiv)

Graph Transformers (GTs) offer superior representation capabilities by overcoming the depth limitations and over-smoothing issues of traditional Graph Neural Networks (GNNs). However, scaling GTs to large graphs poses critical bottlenecks. Specifically, the attention score matrix and its associated topology-aware bias matrix jointly incur significant per-layer memory overhead, and heavy graph embedding layers result in severe workload imbalances. These characteristics are unique to GT training and are not addressed by parallelism techniques designed for either conventional GNNs or Transformers, making a dedicated solution necessary. This paper introduces MegaGraph, the first automated hybrid parallelism framework designed for efficient GT training. MegaGraph designs three specialized strategies, namely graph-aware context parallelism, heterogeneous pipeline parallelism, and hybrid data parallelism, to support efficient training on large-scale graphs. However, coordinating these three parallelism strategies yields an exponentially large configuration space. To address this complexity, an automatic search engine leverages precise cost models via a Profile - Model - Search workflow to identify the optimal parallelism configuration. Evaluations demonstrate that MegaGraph enables training on large-scale graphs where state-of-the-art baselines fail due to out-of-memory (OOM) errors. The framework reduces per-device peak memory by up to 77.8% and achieves up to 4.51× training speedup while maintaining model accuracy.