  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
