Towards Principled Graph Transformers

The expressive power of graph learning architectures based on the $k$-dimensional Weisfeiler--Leman hierarchy is well understood. 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. However, comparing their expressivity with the hierarchy remains challenging, particularly since attention-based architectures rely on positional or structural encodings. To address this, we show that the recently proposed Edge Transformer, a global attention model operating on node pairs instead of nodes, has expressive power when provided with the right tokenization. Empirically, we demonstrate that the Edge Transformer surpasses other theoretically aligned architectures regarding predictive performance and is competitive with state-of-the-art models on algorithmic reasoning and molecular regression tasks while not relying on positional or structural encodings. Our code is available at.