mlsanityData to 14 Oct 2026

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

arXiv 2609.34420 ↗First posted 28 Sep 2026cs.LGcited by 0

Not on the map. Why?

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.

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

20 of 21 references.

References · 20

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  7. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  8. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 545
  9. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 541
  10. 2023Ring Attention with Blockwise Transformers for Near-Infinite Contextcited by 457
  11. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
  12. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 210
8 more
  1. 2022Hierarchical Graph Transformer with Adaptive Node Samplingcited by 72
  2. 2021BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessingcited by 50
  3. 2022DGRec: Graph Neural Network for Recommendation with Diversified Embedding Generationcited by 33
  4. 2023Bridged-GNN: Knowledge Bridge Learning for Effective Knowledge Transfercited by 10
  5. 2023Efficient Link Prediction via GNN Layers Induced by Negative Samplingcited by 6
  6. 2024TorchGT: A Holistic System for Large-scale Graph Transformer Trainingcited by 5
  7. 2024GNNavigator: Towards Adaptive Training of Graph Neural Networks via Automatic Guideline Explorationcited by 2
  8. 2025Towards Affordable, Adaptive and Automatic GNN Training on CPU-GPU Heterogeneous Platformscited by 1

Built on by

Not cited yet.