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
School of Computation, Information and Technology, Technical University of Munich · Graduate School of Information Science and Technology, The University of Tokyo