Size-Transferability of Graph Transformers with Convolutional Positional Encodings

Attention-based architectures have achieved remarkable success across data modalities, motivating the rise of Graph Transformers (GTs). GTs typically encode structural information via positional encodings (PEs), which may be either embedding vectors added to the input or modifications to the attention kernel. Given the challenges of learning from large graphs, a crucial question is whether GTs are _size-transferable_, that is, whether they can generalize to larger graphs than those seen during training. In this work, we study GTs through the lens of manifold limit models and establish that GTs can _inherit_ the transferability properties of their PEs. In particular, if the PEs are transferable, the GT is also transferable. We derive bounds showing that GTs with Graph Neural Network (GNN)-based PEs are transferable. Furthermore, our results show that their transferability is more stable than that of eigenvector-based GTs. We complement our theory with extensive experiments on standard graph benchmarks, where we confirm that GTs with GNN-based PEs exhibit superior transferability compared to those eigenvector-based PEs. We showcase a real-world application of a computationally efficient GT in a shortest-path distance estimation task over terrain manifolds. Our results provide new insights into GTs and suggest practical directions for efficient training in large-scale settings.