Towards Principled Graph Transformers
This work addresses the problem of bridging theory and practice in graph learning for researchers and practitioners, offering a method with strong theoretical guarantees and improved performance, though it is incremental in advancing graph transformer designs.
The paper tackles the gap between theoretically expressive graph learning architectures and practical performance by showing that the Edge Transformer, a global attention model operating on node pairs, has at least 3-WL expressive power and surpasses other theoretically aligned architectures in predictive performance without relying on positional or structural encodings.
Graph learning architectures based on the k-dimensional Weisfeiler-Leman (k-WL) hierarchy offer a theoretically well-understood expressive power. However, such architectures often fail to deliver solid predictive performance on real-world tasks, limiting their practical impact. In contrast, global attention-based models such as graph transformers demonstrate strong performance in practice, but comparing their expressive power with the k-WL hierarchy remains challenging, particularly since these architectures rely on positional or structural encodings for their expressivity and predictive performance. To address this, we show that the recently proposed Edge Transformer, a global attention model operating on node pairs instead of nodes, has at least 3-WL expressive power. Empirically, we demonstrate that the Edge Transformer surpasses other theoretically aligned architectures regarding predictive performance while not relying on positional or structural encodings. Our code is available at https://github.com/luis-mueller/towards-principled-gts