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 找到。

将 Transformer 与 Weisfeiler-Leman 对齐

Aligning Transformers with Weisfeiler-Leman

Message-passing graph neural networks (MPNNs) emerged as powerful tools for
processing graph-structured input. However, they operate on a fixed input graph
structure, ignoring potential noise and missing information. Furthermore, their
local aggregation mechanism can lead to problems such as over-squashing and
limited expressive power in capturing relevant graph structures. Existing
solutions to these challenges have primarily relied on heuristic methods, often
disregarding the underlying data distribution. Hence, devising principled
approaches for learning to infer graph structures relevant to the given
prediction task remains an open challenge. In this work, leveraging recent
progress in exact and differentiable $k$-subset sampling, we devise
probabilistically rewired MPNNs (PR-MPNNs), which learn to add relevant edges
while omitting less beneficial ones. For the first time, our theoretical
analysis explores how PR-MPNNs enhance expressive power, and we identify
precise conditions under which they outperform purely randomized approaches.
Empirically, we demonstrate that our approach effectively mitigates issues like
over-squashing and under-reaching. In addition, on established real-world
datasets, our method exhibits competitive or superior predictive performance
compared to traditional MPNN models and recent graph transformer architectures.

利用最近在精确和可微分的 k 子集采样中的进展，我们设计了一种概率重连的消息传递图神经网络（PR-MPNNs），该网络学习在省略不太有益的边的同时添加相关边。首次，我们的理论分析探索了 PR-MPNNs 如何增强表达能力，并且我们确定了它们优于纯随机方法的精确条件。经验证实，我们的方法有效地缓解了如过度压缩和预测能力不足等问题。此外，根据现有的真实世界数据集，我们的方法在预测性能上与传统的 MPNN 模型和最近的图变压器架构相比表现出有竞争力或更好的性能。