Search papers, labs, and topics across Lattice.
This paper analyzes Graph Transformers (GTs) with Graph Neural Network (GNN)-based positional encodings through the lens of manifold limit models, establishing a theoretical connection to Manifold Neural Networks (MNNs). It leverages transferability results for GNNs under manifold convergence to demonstrate that GTs inherit size transferability guarantees from their positional encodings, enabling generalization from small to large graphs. Empirical validation on graph benchmarks and shortest path distance estimation tasks confirms the scalable behavior of GTs, aligning with theoretical predictions.
Graph Transformers can be effectively trained on small graphs and then transferred to larger graphs, thanks to their GNN-based positional encodings, offering a path to scalable graph learning.
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.
