Organizations: Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA, USA · Halıcıoğlu Data Science Institute, University of California San Diego, La Jolla, CA, USA
Transformers have achieved remarkable success across domains, motivating the rise of Graph Transformers (GTs) as attention-based architectures for graph-structured data. A key design choice in GTs is the use of Graph Neural Network (GNN)-based positional encodings to incorporate structural information. In this work, we study GTs through the lens of manifold limit models for graph sequences and establish a theoretical connection between GTs with GNN positional encodings and Manifold Neural Networks (MNNs). Building on transferability results for GNNs under manifold convergence, we show that GTs inherit transferability guarantees from their positional encodings. In particular, GTs trained on small graphs provably generalize to larger graphs under mild assumptions. We complement our theory with extensive experiments on standard graph benchmarks, demonstrating that GTs exhibit scalable behavior on par with GNNs. To further show the efficiency in a real-world scenario, we implement GTs for shortest path distance estimation over terrains to better illustrate the efficiency of the transferable GTs. Our results provide new insights into the understanding of GTs and suggest practical directions for efficient training of GTs in large-scale settings.
Figures & tables
Figure 1: Transferability of GTs with RPEARL and Laplacian PEs measured by accuracy (higher is better ↑ ). The x -axis represents the train graph sizes as a proportion of the largest graph (α) , and the y -axis is the test accuracy at the full-sized graph. The top row shows dense GTs, and the bottom row shows sparse GTs. The GNN baseline appears in both rows for reference. Shaded regions show the standard deviation over 3 runs. The titles show dataset name and largest graph size.
Figure 2: Transferability heatmaps on SNAP-Patents. The x-axis is the ratio of testing graph size to the full graph size while y-axis is the ratio of training graph sizes. The color represents the accuracy.
Figure 3: Transferability on terrain graphs measured by normalized mean absolute error (NMAE), lower is better ↓ . The x -axis corresponds to the number of nodes for each training resolution, and the y -axis is the NMAE on the highest resolution test graph.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Nodes
Edges
Max Train/Test Nodes
Classes
Graphs
Feature Dim
Squirrel
5,201
216,933
2,081
5
1
2,089
ArXiv-year
169,343
1,166,243
76,205
5
1
128
OGBN-MAG
736,389
5,416,271
331,376
349
1
128
SNAP-Patents
2,923,922
13,975,788
1,315,765
5
1
269
Reddit-Binary
avg. 429.63
avg. 497.75
/
2
2000
1 ∗
Appendix
Table 1: Datasets used for transferability experiments. Edges are directed edges excluding self-loops; for OGBN-MAG we use the paper–paper citation subgraph. Max train/test nodes are the sizes of the full training and test graphs ( α=1 ), with 10%/45% of nodes held out for validation/test (20%/40% for Squirrel).
Model/Hyperparameters
Squirrel
ArXiv-year
OGBN-MAG
SNAP-Patents
Reddit-Binary
GNN
Learning rate
1×10−3
1×10−2
1×10−2
1×10−3
1×10−3
Dropout
0.5
0.5
0.25
0.25
0
Hidden channels
256
256
128
256
512
Number of hops
3
3
3
3
3
Number of layers
2
3
7
7
2
Appendix
Table 2: Hyperparameters for each architecture and dataset. PE: positional encoding; for RPEARL, “Random” feeds random node signals and “Data” the node features into the PE network.
Figure 4: Transferability plots for all datasets and architectures. For each dataset, the x axis represents the train graph sizes as a proportion of the largest graph (α) , and the y axis is the test accuracy at the full-sized graph. The titles show dataset name and largest graph size.
Figure 5: ERROR BARS
Figure 6: Transferability heatmaps on ArXiv-year. The x axis corresponds to train graph sizes as a proportion of the largest graph, and the y axis to test graph size fractions. The color corresponds to the test accuracy at each setting.
Figure 7: Transferability plot for Sparse GT on ArXiv-year for various values of the neighborhood parameter k .
Architecture
Accuracy
% vs. GT
GT (no PE)
31.33
–
GT + RPEARL
34.63
+10.53%
GT + Mask
39.69
+26.68%
GT + Mask + RPEARL
49.70
+58.63%
GT + Mask + RE
31.01
-1.02%
GT + Mask + RPEARL + RE
46.55
+48.58%
Appendix
Table 3: Test accuracy of GT trained with α=0.3 , with different components in SNAP-Patents (1.71M nodes).
Dataset
Model
6.10%
56.84%
100.00%
ArXiv-year
Dense GT
51.6
10.0
19.8
ArXiv-year
Sparse GT
8.8
1.4
2.0
OGBN-MAG
Dense GT
41.8
103.3
366.6
OGBN-MAG
Sparse GT
22.4
7.4
15.0
SNAP-Patents
Dense GT
223.3
945.7
2763.6
SNAP-Patents
Sparse GT
28.3
13.5
23.2
Appendix
Table 4: Runtimes in minutes for three subsample sizes of Sparse and Dense GT
Graph transformers are the state-of-the-art for learning from graph-structured data and are empirically known to avoid several pitfalls of message-passing architectures. However, there is limited theoretical analysis on why these models perform well in practice. In this work, we prove that attention-based architectures have structural benefits over graph convolutional networks in the context of node-level prediction tasks. Specifically, we study the neural network gaussian process limits of graph transformers (GAT, Graphormer, Specformer) with infinite width and infinite heads, and derive the node-level and edge-level kernels across the layers. Our results characterise how the node features and the graph structure propagate through the graph attention layers. As a specific example, we prove that graph transformers structurally preserve community information and maintain discriminative node representations even in deep layers, thereby preventing oversmoothing. We provide empirical evidence on synthetic and real-world graphs that validate our theoretical insights, such as integrating informative priors and positional encoding can improve performance of deep graph transformers.
Nil Ayday, Lingchu Yang, Debarghya Ghoshdastidar
School of Computation, Information and Technology, Technical University of Munich · Graduate School of Information Science and Technology, The University of Tokyo
Graph neural networks (GNNs) can operate on large graphs but become infrastructure-sensitive at the scale of millions of nodes and typically require scalable training techniques for even larger graphs. This raises a central question: when can a model trained on a smaller, scaled-down replica of a graph be deployed on the full-resolution graph without retraining? We introduce a zero-shot transfer protocol in which a GNN is trained on a graph coarse-grained by geometric renormalization (GR), and the resulting weights are transferred directly to the original network. Across synthetic and real-world networks, training on GR scaled-down replicas preserves much of the original-scale predictive performance while significantly reducing training cost. We further find that learned representations and predictive trajectories remain aligned across scales. These findings suggest that structural similarity may be more important than network size in determining GNN transferability, opening a path toward scale-equivariant graph architectures.
Robert Jankowski, Pedro Almagro-Blanco, Marián Boguñá +2
TU Delft · University of Seville · University of Barcelona +2
The success of large pretrained Transformers is closely tied to tokenizers, which convert raw input into discrete symbols. Extending these models to graph-structured data remains a significant challenge. In this work, we introduce a graph tokenization framework that generates sequential representations of graphs by combining reversible graph serialization, which preserves graph information, with Byte Pair Encoding (BPE), a widely adopted tokenizer in large language models (LLMs). To better capture structural information, the graph serialization process is guided by global statistics of graph substructures, ensuring that frequently occurring substructures appear more often in the sequence and can be merged by BPE into meaningful tokens. Empirical results demonstrate that the proposed tokenizer enables Transformers such as BERT to be directly applied to graph benchmarks without architectural modifications. The proposed approach achieves state-of-the-art results on 14 benchmark datasets and frequently outperforms both graph neural networks and specialized graph transformers. This work bridges the gap between graph-structured data and the ecosystem of sequence models. Our code is available at bluehere.
Zeyuan Guo, Enmao Diao, Cheng Yang +1
Beijing University of Posts and Telecom., Beijing 100876, China · DreamSoul