The distinguishing power of graph transformers is closely tied to the choice
of positional encoding: features used to augment the base transformer with
information about the graph. There are two primary types of positional
encoding: absolute positional encodings (APEs) and relative positional
encodings (RPEs). APEs assign features to each node and are given as input to
the transformer. RPEs instead assign a feature to each pair of nodes, e.g.,
graph distance, and are used to augment the attention block. A priori, it is
unclear which method is better for maximizing the power of the resulting graph
transformer. In this paper, we aim to understand the relationship between these
different types of positional encodings. Interestingly, we show that graph
transformers using APEs and RPEs are equivalent in terms of distinguishing
power. In particular, we demonstrate how to interchange APEs and RPEs while
maintaining their distinguishing power in terms of graph transformers. Based on
our theoretical results, we provide a study on several APEs and RPEs (including
the resistance distance and the recently introduced stable and expressive
positional encoding (SPE)) and compare their distinguishing power in terms of
transformers. We believe our work will help navigate the huge number of choices
of positional encoding and will provide guidance on the future design of
positional encodings for graph transformers.

图转换器的区分能力与位置编码的选择紧密相关，本文旨在理解绝对位置编码和相对位置编码之间的关系，并展示了在图转换器中如何交换这两种类型的位置编码而保持它们的区分能力。基于理论结果，我们对几种位置编码进行了研究并比较了它们在转换器中的区分能力，从而为位置编码的未来设计提供指导。

通过位置编码比较图变换器

Comparing Graph Transformers via Positional Encodings

We revisit the classical result of Morris et al.~(AAAI'19) that
message-passing graphs neural networks (MPNNs) are equal in their
distinguishing power to the Weisfeiler--Leman (WL) isomorphism test.
Morris et al.~show their simulation result with ReLU activation function and
$O(n)$-dimensional feature vectors, where $n$ is the number of nodes of the
graph. Recently, by introducing randomness into the architecture, Aamand et
al.~(NeurIPS'22) were able to improve this bound to $O(\log n)$-dimensional
feature vectors, although at the expense of guaranteeing perfect simulation
only with high probability.
In all these constructions, to guarantee equivalence to the WL test, the
dimension of feature vectors in the MPNN has to increase with the size of the
graphs. However, architectures used in practice have feature vectors of
constant dimension. Thus, there is a gap between the guarantees provided by
these results and the actual characteristics of architectures used in practice.
In this paper we close this gap by showing that, for \emph{any} non-polynomial
analytic (like the sigmoid) activation function, to guarantee that MPNNs are
equivalent to the WL test, feature vectors of dimension $d=1$ is all we need,
independently of the size of the graphs.
Our main technical insight is that for simulating multi-sets in the WL-test,
it is enough to use linear independence of feature vectors over rationals
instead of reals. Countability of the set of rationals together with nice
properties of analytic functions allow us to carry out the simulation invariant
over the iterations of the WL test without increasing the dimension of the
feature vectors.

通过引入随机性来优化 MPNN (WL) isomorphism 测试的结果，本研究证实，对于任何非多项式解析 (如 sigmoid) 的激活函数，只需特征向量的维度 d=1，独立于图的大小，即可保证 MPNN 等价于 WL 测试。

关于 MPNN 中的特征向量维度性

On dimensionality of feature vectors in MPNNs

Various recent proposals increase the distinguishing power of Graph Neural
Networks GNNs by propagating features between $k$-tuples of vertices. The
distinguishing power of these "higher-order'' GNNs is known to be bounded by
the $k$-dimensional Weisfeiler-Leman (WL) test, yet their $\mathcal O(n^k)$
memory requirements limit their applicability. Other proposals infuse GNNs with
local higher-order graph structural information from the start, hereby
inheriting the desirable $\mathcal O(n)$ memory requirement from GNNs at the
cost of a one-time, possibly non-linear, preprocessing step. We propose local
graph parameter enabled GNNs as a framework for studying the latter kind of
approaches and precisely characterize their distinguishing power, in terms of a
variant of the WL test, and in terms of the graph structural properties that
they can take into account. Local graph parameters can be added to any GNN
architecture, and are cheap to compute. In terms of expressive power, our
proposal lies in the middle of GNNs and their higher-order counterparts.
Further, we propose several techniques to aide in choosing the right local
graph parameters. Our results connect GNNs with deep results in finite model
theory and finite variable logics. Our experimental evaluation shows that
adding local graph parameters often has a positive effect for a variety of
GNNs, datasets and graph learning tasks.

我们在研究中提出了一种基于本地图参数的 GNN 架构，该架构处于 GNN 和其高阶对应物之间的表现力水平，并提出了可帮助选择正确本地图参数的技术。 我们的结果将 GNN 与有限模型理论和有限变量逻辑的深度结果联系起来，实验评估表明添加本地图参数对各种 GNN，数据集和图形学习任务通常有积极影响。