🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

本文研究了在图神经网络中使用截断位置编码（truncated positional encodings）的理论与实证影响，揭示了这种截断从根本上改变了不同编码族的表达能力——使得谱变体（spectral variants）并不比 1-WL 测试更强——并证明了在现实世界的数据集上，结合多种截断编码的效果优于使用任何单一家族。

原作者： James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

发布于 2026-06-12

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图教一个机器人理解一座城市的布局。这个机器人是一个图神经网络 (GNN)，而这座城市是一个由图 (graph) 构成的，其中交汇点是节点 (nodes)，街道是边 (edges)。

为了做好这份工作，机器人需要的不仅仅是一份关于哪些街道连接在一起的清单。它需要位置编码 (Positional Encodings, PEs)。把 PEs 想象成一张“地图”或一个“指南针”，它告诉机器人每个交汇点相对于其他交汇点的位置。如果没有这张地图，机器人就像一个闭着眼睛在城市里行走的人，只知道谁站在自己身边，却完全不知道自己是在市中心还是被困在了死胡同里。

问题所在：“完美”地图太重了

有两种主要方法可以创建这张完美的地图：

谱图 (The Spectral Map)： 它利用复杂的数学（特征值和特征向量）来观察城市的“振动”或全局形状。
行走图 (The Walk Map)： 它计算从一点走到另一点，经过 1 步、2 步、3 步……等等有多少种方式。

从数学上讲，如果你使用完整的地图（所有的步骤、所有的振动），这两种方法具有同等的威力。它们可以区分几乎任何两个不同的城市布局。

然而，有一个陷阱： 为一座大型城市创建这种“完整”的地图需要巨大的计算能力和内存（具体来说，随着城市规模的增长，难度呈指数级增加）。这就像是试图在背包里背着一整座图书馆，里面装满了世界上每一种可能的地图。这在现实生活中是无法使用的。

因此，工程师们使用截断式位置编码 (Truncated Positional Encodings)。与其携带整个图书馆，不如只取前几章。

截断谱图 (Truncated Spectral)： 只取前几种“振动”（特征向量）。
截断行走图 (Truncated Walk)： 只取前几步行走（邻接矩阵的幂）。

大的问题在于：如果我们把这些地图的结尾切掉，它们是否还能以同样的方式工作？

重大发现：“切割”改变了一切

作者发现了一个令人惊讶的答案：不，它们不再以同样的方式工作了。

当你拥有完整的地图时，谱图法和行走图法是双胞胎。但当你进行截断（切割）时，它们就变成了各具特色、优缺点各异的兄弟。

“截断谱图”的陷阱： 有时，仅仅使用前几种“振动”实际上会让机器人比没有任何地图时表现得更差！在某些情况下，一个截断谱图是如此微弱，以至于它甚至无法区分两个连简单的“邻居检查”测试（称为 1-WL 测试）都能轻易识别出的不同城市。
“截断行走图”的陷阱： 相反，有些城市布局，一个截断行走图（仅计算几步）会完全忽略，但截断谱图却能立即捕捉到。

类比： 想象你在识别一个人。

完整的谱图 就像是了解他们的整个 DNA 和生平历史。
截断谱图 就像是只知道他们的身高。
截断行走图 就像是只知道从他们家走到杂货店需要走多少步。

如果你只知道身高（截断谱图），你可能会把两个身高相同的人搞混。如果你只知道步行距离（截断行走图），你可能会把住在相同距离商店的人搞混。但如果你同时使用两者，你就能得到更清晰的轮廓。

新英雄：“调和距离 (Harmonic Distances)”

论文引入了一类新的地图，称为 k-调和距离 (k-harmonic distances)。

可以把有效电阻 (Effective Resistance)（一种 1-调和距离）想象成测量两点之间的“连通性”，就像电流在它们之间如何流动一样。
论文表明，双调和距离 (Biharmonic distance)（2-调和）测量的是不同的东西：它衡量一条街道对于整个城市而言有多“中心”或多重要。

作者证明了虽然这些新地图很强大，但它们也有局限性。如果你只使用“电阻”地图，你可能会错过“双调和”地图能捕捉到的细节，反之亦然。然而，如果你使用足够多的这些调和地图，你就可以重现那些沉重的完整地图的威力。

实践建议：“混合搭配”

由于没有任何一种单一的“切割”地图是完美的，作者为工程师们提出了一个简单的经验法则：不要只依赖一种类型的截断地图。

相反，将它们混合在一起。

结合几步“行走”图。
结合几种“谱图”的“振动”。
加入一个或两个“调和”距离。

实验：
作者在真实世界的数据集（如预测分子的化学性质）上测试了这一点。

仅使用一种类型的截断地图效果尚可。
使用不同类型截断地图的混合体则显著更好。

这就像在城市中导航：同时拥有指南针（谱图）、计步器（行走图）和交通流量测量仪（调和距离）比只依赖其中之一要好得多。

总结

完整地图太重了，难以在现实中使用，所以我们使用“截断”（切掉一部分）的版本。
切割打破了等价性： 截断谱图和截断行走图不再相等；它们各有盲点。
有些切割甚至比没有地图还差： 在某些情况下，截断谱图甚至比一个非常基础的测试还要弱。
解决方案： 不要只选一种。混合使用不同类型的截断地图，可以在不产生沉重计算成本的前提下获得最佳性能。

技术摘要：理解图神经网络中的截断位置编码

问题陈述

图神经网络（GNN），特别是消息传递神经网络（MPNN），在捕捉全局结构信息方面存在根本性的局限性，这一约束通过其与 1-Weisfeiler-Lehman (1-WL) 测试的等价性得到了形式化。为了克服这一限制，图 Transformer（GT）和增强型 GNN 利用位置编码（PE）来注入结构信息。两类主流的 PE 分别是谱编码（源自拉普拉斯特征空间）和基于游走的编码（源自邻接矩阵的幂）。

从理论上讲，完整的编码版本（使用 $\Omega(n)$ 个特征向量或矩阵幂）在表达能力上是等价的，均处于 1-WL 和 3-WL 测试之间。然而，计算这些完整的编码需要 $O(n^3)$ 的时间和空间复杂度，这在实际应用中是难以承受的。因此，从业者依赖于截断变体（例如前 $k$ 个特征向量或前 $k$ 次邻接矩阵幂）。截断 PE 的理论特性、表达能力以及比较优势在很大程度上仍未得到充分探索，这造成了理论保证与实际实现之间的鸿沟。

研究方法

作者通过理论分析和实证验证，对截断 PE 进行了系统性研究。

理论框架

本文利用 WL 层级及其变体来表征不同 PE 的表达能力：

$\psi$ -WL 测试： 一种 WL 测试的变体，其中节点颜色使用相对位置编码（RPE） $\psi$ 进行更新。
Sparse- $\psi$ -WL 测试： 一种针对 MPNN 的扩展，其中 $\psi$ 被用作边特征。
分析的关键族类：
1. 截断特征空间投影 ( $k$ -EP-WL)： 使用拉普拉斯矩阵的前 $k$ 个特征空间投影。
2. 截含游走编码 ( $k$ -Walk-WL)： 使用邻接矩阵的前 $k$ 次幂。
3. 有效电阻 (Resistance-WL)： 一种特定的谱距离（1-调和距离）。
4. $k$ -调和距离： 一种有效电阻的泛化，定义为 $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ 。

作者构建了特定的图对（例如，路径图与完全图的乘积，或循环图与不连通循环图的并集），以证明在不同截断 PE 和 WL 测试下的可分性或不可区分性。

实证评估

实验在三个基准数据集上进行：

BREC： 一个旨在通过测试 GNN 区分从 1-WL 到 4-WL 不可区分的非同构图的能力，来衡量“实现表达能力”的数据集。
ZINC-12k： 一个用于分子溶解度预测的图回归基准，用于测试混合截断 PE 是否能提高性能的假设。
ogbg-molhiv： 一个用于 HIV 抑制分类的二分类基准。

作者评估了 Graphormer-GD 架构和 MPNN (GINE) 在使用各种组合的截断 PE（包括单一族类以及谱、游走和 $k$ -调和编码的混合）时的表现。

核心贡献与结果

1. 截断形式中表达能力的差异

本文证明了虽然完整的谱编码和游走编码是等价的，但它们的截断形式在本质上是不同的：

截断谱编码 vs. 1-WL： 作者表明，截断特征空间投影 ( $k$ -EP-WL) 可能比 1-WL 测试更弱。具体而言，存在某些图对，虽然可以被 1-WL 区分，但在 $k \in \Omega(n)$ 的情况下，对于 $k$ -EP-WL 是不可区分的（定理 4.1）。
截断游走编码 vs. 谱编码： 相反，存在某些图对，可以被单个特征空间投影 (1-EP-WL) 区分，但对于 $\Omega(n)$ 规模的游走编码是不可区分的（定理 4.2）。
启示： 没有哪一种单一的截断 PE 族是绝对优越的；它们捕捉了不同的结构方面，并且可能与标准的 WL 层级是不具可比性的。

2. 有效电阻的局限性

本文分析了有效电阻（1-调和距离），并发现它在加权图上的表现弱于完整的特征空间投影或游走编码。

定理 4.3： 存在某些加权图，在 Resistance-WL 下是不可区分的，但在 Adjacency-WL（以及无权图上的 1-WL）下是可区分的。
推论 4.1： Resistance-WL 并没有编码整个图的谱，从而反驳了之前的猜想。

3. $k$ -调和距离作为桥梁

作者引入了 $k$ -调和距离，将其作为谱编码与多项式编码之间的自然桥梁。

完备性： 拼接 $\Theta(n)$ 个 $k$ -调和距离可以产生一个在能力上等价于完整谱编码或游走编码的编码（定理 4.6）。
差异化能力： 即使在 $k$ -调和族内部，固定大小的编码也存在差异。例如，双调和距离（2-调和）可以在常数次迭代内区分某些树对，而有效电阻（1-调和）则需要 $O(n)$ 次迭代（定理 4.7）。
鲁棒性： 然而，如果一个 $k$ -调和距离能够区分一对图，那么大多数其他 $k$ -调和距离也会区分它们（定理 4.8）。

4. 实证发现：混合的力量

BREC 结果： $k$ -调和距离取得了与单通道、低开销编码竞争性的结果，通常能达到 1-WL 到 3-WL 之间图的理论上限。
ZINC 结果： 最显著的发现是，混合来自不同族类的 PE（例如，结合截断游走和 $k$ -调和）比任何单一族类都更有效。混合了截断游走和 $k$ -调和的组合在 ZINC-12k 上实现了最低的平均绝对误差 (MAE)，超越了单一族类的基准线。
效率： 本文指出， $k$ -调和距离可以使用快速拉普拉斯求解器和 Johnson-Lindenstrauss 投影在 $O(mk \cdot \text{poly}(\log n))$ 时间内进行近似，从而避免了精确计算所需的 $O(n^3)$ 成本。

重要性与主张

本文声称开启了对截断位置编码的理论研究，将视角从仅仅将其视为完整编码的近似，转向将其视为一个具有独特表达属性的独立设计空间。

理论洞察： 这项工作证明了截断从根本上改变了 PE 所捕捉的信息，使得它们在特定情况下与标准 WL 层级不可比。
实践指导： 作者提出了一个经验法则：在使用截断 PE 时，混合来自不同族类的 PE。这种方法可以在控制计算成本的同时，捕捉互补的结构线索。
研究范围： 作者承认，虽然图同构是一个原则性的代理指标，但现实世界的任务涉及下游信号（如中心性、模体），这些信号可能并不严格符合同构测试。因此，主要贡献在于建立一个理论基础和系统性实证研究的起点，而非声称找到了解决所有图学习任务的通用方案。