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.

基于 k 维 Weisfeiler-Leman（k-WL）层次结构的图学习架构在理论上具有良好的表达能力。然而，这样的架构通常在实际任务中无法提供可靠的预测性能，限制了它们的实际影响。相比之下，基于全局注意力的图变换器等架构在实践中表现出强大的性能，但是与 k-WL 层次结构的表达能力进行比较仍具有挑战性，特别是因为这些架构依赖于位置或结构编码来实现其表达能力和预测性能。为了解决这个问题，我们展示了最近提出的边界变换器（Edge Transformer），一种基于节点对而不是节点操作的全局注意力模型，具有至少 3-WL 的表达能力。在实证上，我们证明了边界变换器相对于其他理论上对齐的架构在预测性能方面的优势，同时不依赖于位置或结构编码。