Scalable and Adaptive Parallel Training of Graph Transformer on Large Graphs Conference: 63rd ACM/IEEE Design Automation Conference; July 26–29, 2026; Long Beach, CA, USA 63rd ACM/IEEE Design Automation Conference (DAC ’26), July 26–29, 2026, Long Beach, CA, USA DOI: 10.1145/3770743.3804417 ISBN: 979-8-4007-2254-7/2026/07

Jun-Liang Lin, Kamesh Madduri, Mahmut Taylan Kandemir · 2026

Read Scalable and Adaptive Parallel Training of Graph Transformer on Large Graphs Conference: 63rd ACM/IEEE Design Automation Conference; July 26–29, 2026; Long Beach, CA, USA 63rd ACM/IEEE Design Automation Conference (DAC ’26), July 26–29, 2026, Long Beach, CA, USA DOI: 10.1145/3770743.3804417 ISBN: 979-8-4007-2254-7/2026/07 by Jun-Liang Lin, Kamesh Madduri, Mahmut Taylan Kandemir (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16715.txt.

Introduction

Lin and colleagues introduce a training framework for graph transformers, adapting parallelization to graph structure and hardware. Graph foundation models adapt well, but implementations run on single GPUs, causing long training or memory exhaustion. Full-graph training is hard, since efficiency hinges on graph structure, bandwidth and memory capacity. With distributed sparse operations, it accelerates sparse graph attention three point eight times and cuts memory use by 78 percent. On large benchmarks, it reaches 6 times speedup while scaling to 8 GPUs. The work brings graph transformers closer to practical foundation models.

Catalog record

CREATORJun-Liang Lin, Kamesh Madduri, Mahmut Taylan Kandemir
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29971
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.16715

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable and Adaptive Parallel Training of Graph Transformer on Large Graphs Conference: 63rd ACM/IEEE Design Automation Conference; July 26–29, 2026; Long Beach, CA, USA 63rd ACM/IEEE Design Automation Conference (DAC ’26), July 26–29, 2026, Long Beach, CA, USA DOI: 10.1145/3770743.3804417 ISBN: 979-8-4007-2254-7/2026/07 Jun-Liang Lin, Kamesh Madduri, Mahmut Taylan Kandemir Abstract . Graph foundation models have demonstrated remarkable adaptability across diverse downstream tasks through large-scale pretraining on graphs. However, existing implementations of the backbone model, graph transformers, are typically limited to single-GPU systems, leading to long training times or out-of-memory issues on large graphs. Moreover, parallelizing graph transformer training over the full graph is challenging, as efficiency depends heavily on both the graph structure and system characteristics, such as bandwidth and memory capacity. In this work, we introduce a distributed training framework for graph transformers, which automatically selects and optimizes parallelization strategies based on the graph structure and hardware configuration. With our implementation of distributed sparse operations, we accelerate sparse graph attention by up to 3.8x and reduce memory consumption by 78% compared to state-of-the-art frameworks. On large graph benchmarks, our proposed framework achieves up to 6x speedup with system scaling up to 8 GPUs. These results demonstrate that the proposed framework improves the scalability of graph transformers, bringing them closer to serving as practical graph foundation models. † † cc-license: by 1. Introduction With the rapid development of transformer models, research has shown that scaling up both the size of the model and the pretraining data leads to stronger performance ( 10 ) . Larger pretrained models exhibit remarkable adaptability across a wide range of downstream tasks, demonstrating strong transferability and generalization ( 1 ; 5 ; 4 ) . These pretrained models are commonly referred to as “foundation models” because they serve as a universal base (foundation) on which diverse applications can be built, allowing performance improvements by leveraging the rich knowledge encoded within them. Extending this paradigm to graph-structured data, graph foundation models aim to learn universal representations through large-scale self-supervised pretraining, enabling broad applicability to downstream tasks via finetuning or prompt tuning ( 8 ; 24 ; 12 ) . Among candidate architectures, “graph transformers” have emerged as a promising backbone due to their ability to capture both structural and semantic patterns in graphs ( 6 ; 22 ; 20 ; 23 ; 32 ) . Recent studies have explored their effectiveness in multiple domains and various pretraining strategies have been proposed to further enhance their generalization and transferability ( 8 ; 33 ) . Scaling graph transformers to larger graphs is crucial for advancing graph foundation models ( 13 ) . However, recent graph transformer designs mainly target single-GPU training ( 6 ; 22 ; 20 ; 23 ) , and therefore fail to scale algorithms and models to large graphs. In contrast, modern graph neural network (GNN) training frameworks, such as DistDGL ( 30 ) and BGL ( 14 ) , do support distributed multi-GPU training, but they are mostly designed for mini-batch training, where subgraphs are sampled and processed in each iteration. This paradigm is not applicable to general graph transformers, which rely on full-graph information to capture long-range dependencies. Although some distributed training frameworks support full-graph GNN workloads, they are largely optimized for simple GCN models ( 25 ; 26 ; 7 ) . None of these frameworks support graph transformers, which involve substantially more complex computation and communication patterns. Several recent approaches, such as SGFormer ( 28 ) and TorchGT ( 29 ) , attempt to scale graph transformers through graph clustering or partitioning, but they inevitably sacrifice parts of the graph structure, losing the ability to fully exploit global information. In other words, no existing framework provides an efficient solution for distributed graph transformer training with full graphs. These limitations motivate a critical question: How can we enable distributed training of graph transformer models on full graphs while ensuring scalability on multi-GPU systems? Following the transformer design used in large language models (LLMs), general graph transformers incorporate query, key, and value projections along with a self-attention mechanism. However, a key distinction is that instead of computing full attention on all pairs of nodes, graph transformers restrict attention to neighboring nodes, resulting in a sparse attention mask ( 6 ; 20 ; 23 ; 22 ) . This mask corresponds to the adjacency matrix of the graph and can be represented in sparse formats such as Coordinate (COO) or Compressed Sparse Row (CSR) ( 21 ) . Consequently, attention computation is performed through a series of sparse operations, including sparse matrix–matrix multiplication (SpMM) and sampled dense–dense matrix multiplication (SDDMM) ( 16 ; 19 ) . To achieve scalable training of graph transformers, it is crucial to distribute these sparse operations efficiently across multiple devices. Unlike LLMs, where model parameters dominate memory consumption, training graph transformers is often constrained by the size of the graph data itself. As a result, traditional parallelization strategies used in LLM training, such as data parallelism and model parallelism ( 15 ) , are not effective for scaling graph transformer training on large graphs. Therefore, we focus on “graph parallelism”, referring to exploiting parallelism based on the graph structure and its features. In this direction, there exist multiple strategies, each with different computation costs, communication overhead, and memory footprints ( 2 ) . Determining the optimal strategy is challenging due to the diversity of graph structures and the variability in system configurations. In this paper, we address these challenges by introducing a “distributed training framework” to enable training of the graph transformer on full large graphs. The main contributions of this work are as follows: \bullet We propose two parallelization strategies, Graph Parallelism with All-Gather (GP-AG) and Graph Parallelism with All-to-All (GP-A2A), to enhance training efficiency through the use of sparse operators and reduce memory consumption significantly. \bullet We introduce an algorithm, Automatic Graph Parallelism (AGP), which automatically applies the optimal parallelization strategy to training of sparse graph transformers on large graphs, based on the target graph structure and system configurations. \bullet We present a detailed experimental evaluation of our algorithm. This evaluation demonstrates strong scalability (achieving up to a 6x speedup on 8 GPUs) for full-graph training on large graphs, along with substantial improvements in training efficiency over prior approaches (up to a 3.8x speedup and a 78% reduction in memory usage). 2. Graph Transformers with Sparse Graph Attention 2.1. Definition of Sparse Graph Transformer A typical graph transformer design follows the definition in the early work UniMP ( 22 ) , which can be represented as follows: (1) \mathbf{x}^{\prime}_{i}=\mathbf{W}_{o}\mathbf{x}_{i}+\sum_{j\in\mathcal{N}(i)}\alpha_{i,j}\mathbf{W}_{V}\mathbf{x}_{j}, (2) \alpha_{i,j}=\textrm{softmax}\left(\frac{(\mathbf{W}_{Q}\mathbf{x}_{i})^{\top}(\mathbf{W}_{K}\mathbf{x}_{j})}{\sqrt{d}}\right), where \mathbf{x}_{i} and \mathbf{x}^{\prime}_{i} are the input and output features of node i , \mathbf{W} s are the weight matrices, and \mathcal{N}(i) is the set of neighbors of node i . Note that we can rewrite and extend it into the matrix form. Given a graph G with N nodes and feature dimension d , along with a dense feature matrix \textbf{X}\in\mathbb{R}^{N\times d} and a sparse adjacency matrix \textbf{A}\in\{0,1\}^{N\times N} , the general form of the “Sparse Graph Attention” (SGA) can be calculated as follows: (3) \textbf{Q}=\textbf{X}\textbf{W}_{Q},\textbf{K}=\textbf{X}\textbf{W}_{K},\textbf{V}=\textbf{X}\textbf{W}_{V}, (4) \textbf{Z}=(\textbf{Q}\textbf{K}^{\top})\odot\textbf{A},\textbf{U}=\text{Softmax}(\frac{\textbf{Z}}{\sqrt{d}}), (5) \textbf{Y}=\textbf{U}\textbf{V},\textbf{X'}=\textbf{X}\textbf{W}_{o}+\textbf{Y}, where \textbf{W}_{Q} , \textbf{W}_{K} , and \textbf{W}_{V} are the weight matrices of size d\times

Read the complete text