Graph neural network architectures aligned with the $k$-dimensional
Weisfeiler--Leman ($k$-WL) hierarchy offer theoretically well-understood
expressive power. However, these architectures often fail to deliver
state-of-the-art predictive performance on real-world graphs, limiting their
practical utility. While recent works aligning graph transformer architectures
with the $k$-WL hierarchy have shown promising empirical results, employing
transformers for higher orders of $k$ remains challenging due to a prohibitive
runtime and memory complexity of self-attention as well as impractical
architectural assumptions, such as an infeasible number of attention heads.
Here, we advance the alignment of transformers with the $k$-WL hierarchy,
showing stronger expressivity results for each $k$, making them more feasible
in practice. In addition, we develop a theoretical framework that allows the
study of established positional encodings such as Laplacian PEs and SPE. We
evaluate our transformers on the large-scale PCQM4Mv2 dataset, showing
competitive predictive performance with the state-of-the-art and demonstrating
strong downstream performance when fine-tuning them on small-scale molecular
datasets. Our code is available at
this https URL

图神经网络架构与 $k$ 维 Weisfeiler--Leman（$k$-WL）层次结构相吻合，其在理论上具有良好的表达能力。然而，这些架构在实际应用中往往无法提供最先进的预测性能，从而限制了它们的实用性。最近的一些研究将图变换器架构与 $k$-WL 层次结构相结合，展示了有希望的实证结果，但是将变换器用于更高阶的 $k$ 仍然存在挑战，因为自注意力的运行时间和内存复杂度过高，并且存在不切实际的架构假设，例如不可行的注意力头数。在这里，我们推进了将变换器与 $k$-WL 层次结构相结合的研究，展示了每个 $k$ 更强的表达能力结果，使得它们在实践中更可行。此外，我们发展了一个理论框架，可用于研究已建立的位置编码，如拉普拉斯位置编码和 SPE。我们在大规模 PCQM4Mv2 数据集上评估了我们的变换器，展示了与最先进方法的竞争性预测表现，并在小尺度分子数据集上进行微调时展示了强大的下游性能。我们的代码可在此 https URL 找到。