理解图神经网络的截断位置编码

论文信息

标题: Understanding Truncated Positional Encodings for Graph Neural Networks

作者: James Flora, Mitchell Black, Weng-Keen Wong, et al.

发布日期: 2026-06-11

PDF 链接: 下载 PDF

研究背景与核心动机

图神经网络（GNN）在处理图结构数据方面取得了显著成功，但消息传递神经网络（MPNN）在捕获全局结构信息方面存在根本性局限——其表达能力被证明不超过 1-WL 测试。位置编码（Positional Encodings, PEs）的引入为解决这一问题提供了有效途径，它们通过注入图拓扑信息来增强模型的表达能力。

目前最流行的两类位置编码是谱编码和游走编码。谱编码利用图拉普拉斯矩阵的特征值和特征向量，游走编码则基于邻接矩阵的幂次。理论上，这两类编码的完整版本具有等价的表达能力，都介于 1-WL 与 3-WL 测试之间。然而，完整版本需要 $O(n^3)$ 的时间和空间复杂度，在实践中难以应用。

因此，研究者通常采用截断版本——例如仅使用前 $k$ 个特征空间或前 $k$ 次幂——以降低计算开销。但是，这些截断变体的理论性质始终未被充分研究。本文开创性地填补了这一空白，揭示了截断位置编码在表达能力上的根本差异。

核心方法与技术框架

理论基础：WL 测试家族

为分析位置编码的表达能力，论文建立在一系列 WL 测试变体的基础上。经典的 1-WL 测试通过迭代更新节点颜色来判断图同构性。GD-WL 测试将相对位置编码 $\psi$ 纳入考虑，为使用该编码的图 Transformer 提供表达能力上界：

\chi_{\psi}^{(t)}(v) = \{\{(\chi_{\psi}^{(t-1)}(u), \psi(u,v)) : u \in V_G\}\}

对于消息传递网络中的边编码，论文引入了稀疏版本的 Sparse- $\psi$ -WL 测试，将边特征聚合到节点颜色更新中。

三种位置编码族系

特征空间投影编码（EP-WL） 将拉普拉斯矩阵分解为特征值和特征空间投影矩阵： $\mathcal{P}(u,v) = \{(\lambda_i, \Pi_i(u,v)) : 1 \leq i \leq l\}$ 。截断版本 $k$ -EP-WL 仅保留前 $k$ 个最小特征值对应的投影。

游走编码（Walk-WL） 拼接邻接矩阵的前 $k$ 次幂 $(A, A^2, \ldots, A^k)$ ，反映节点间不同长度的游走数量。

$k$ -调和距离 是本文重点探讨的谱编码族系，定义为 $H^k(u,v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ 。其中有效电阻（ $k=1$ ）已被广泛研究，双调和距离（ $k=2$ ）则度量边的中心性。

核心理论发现

截断 PE 的表达能力差异

论文最关键的发现是：截断后的谱编码与游走编码不再具有等价表达能力，它们捕获的是图结构的互补信息。

定理 4.1 证明了存在图对能被 1-WL 区分，但即使使用 $\Omega(n)$ 规模的截断 EP-WL 也无法区分。具体构造为 $P_n \times K_{10}$ 和 $P_n \times K_{5,5}$ 两类乘积图，它们的前 $n$ 个特征值和特征向量完全相同（因 $K_{10}$ 和 $K_{5,5}$ 的零特征值及全一特征向量相同），但节点度数不同。

定理 4.2 则展示了反向情况：存在图对能被 1-EP-WL 区分，却不能被 $\Omega(n)$ -Walk-WL 区分。例如长度为 $n$ 的环图与两个长度为 $n/2$ 环图的不交并，后者前 $n/4$ 步游走完全相同，但谱投影能立即发现连通性差异。

有效电阻的局限性

定理 4.3 证明了在加权图上，存在图对能被邻接矩阵 WL 区分，但不能被有效电阻 WL 区分。构造基于点集的平方欧几里得距离矩阵恰好形成两类图的电阻矩阵。这一发现反驳了先前关于电阻距离能编码完整图谱的猜想。

$k$ -调和距离的性质

论文建立了一系列关于 $k$ -调和距离表达能力的理论结果：

定理 4.4：任何 Sparse- $k$ -Harmonic-WL 都严格强于 1-WL，因为能区分标准 WL 无法区分的环图对
定理 4.5：所有 $k$ -调和距离的 WL 测试都弱于 3-WL
定理 4.6：拼接前 $[2n]$ 个调和距离可达到与完整 EP-WL 等价的能力
定理 4.7：双调和距离能在 1 轮迭代内区分有效电阻需要 $o(n)$ 轮才能区分的树对
定理 4.8：若某个 $k$ 调和距离能区分一对图，则除最多 $O(n^5)$ 个例外，其他 $k'$ 调和距离也能区分

这些理论结果表明，即使是同一族系内的不同截断版本，其表达能力也可能显著不同，但总体上具有相似的判别能力。

实验验证

BREC 数据集上的表达能力测试

BREC 数据集通过对比学习方式评估 GNN 的实际表达能力。实验采用了 Graphormer-GD 架构，关键发现包括：

单通道 $k$ -调和距离（如双调和距离或 4-调和距离）在基本、正则、扩展图类上就达到理论上限，总准确率约 47%，已超过多通道的 $k$ -EP-WL（ $k=5$ 时 48%）
$k$ -EP-WL 从 $k=2$ 到 $k=3$ 表现跳跃明显（46.5% 到 86.7%），后续增益递减
调和距离以单维度实现了与多维度 EP-WL 相竞争的结果，计算效率更高

ZINC-12k 分子回归基准

在固定总编码维度为 8 的设置下，论文验证了混合编码策略的有效性：

单独使用 $k$ -调和距离（8 维度）：测试 MAE 为 0.076
游走编码与调和距离各 4 维度的混合：达到最优 0.064 MAE
游走与投影混合（4+4 维）也取得 0.075 的优异表现
投影与调和距离混合改善有限（0.078），暗示这两类编码存在信息冗余

实验结果验证了核心假设：不同截断 PE 族系捕获互补的结构信息，混合使用能显著提升性能。

实践指导与技术启示

编码选择策略

基于理论与实验发现，论文提出以下实践建议：

混合编码优先：不应依赖单一截断 PE，应根据任务特点组合谱编码、游走编码、调和距离等多族系信息
维度预算分配：在计算资源约束下，合理分配各编码的维度预算，而非将全部资源投入单一族系
调和距离的优势： $k$ -调和距离（特别是 $k=2,4$ 等）以单通道提供丰富结构信息，性价比极高

计算效率考量

对于大规模图数据， $k$ -调和距离可通过快速拉普拉斯求解器和 Johnson-Lindenstrauss 投影在近似计算中达到线性时间复杂度 $O(mk \cdot \text{poly}\log n + n^2 \log n)$ ，这对于实际部署具有重要价值。

设计空间视角

论文强调应将截断位置编码视为独立的设计空间，而非完整编码的简单近似。不同截断方式对应不同的结构归纳偏置，应基于任务特性进行选择与组合。

总结与未来方向

本文首次对图神经网络截断位置编码进行了系统的理论分析，揭示了截断 EP-WL、Walk-WL 与 $k$ -调和距离-WL 三类方法在表达能力上的本质差异，推翻了它们在完整形式下的等价性在截断情形下的延续假设。实验证明了混合编码策略的实际有效性。

未来研究方向包括：在非加权图上验证有效电阻与 WL 的关系（本文仅证明了加权图情形）；探索更多截断编码组合对超大规模图的可扩展性；研究自适应截断策略，根据图结构动态选择最合适的编码维度和类型；以及开发针对特定下游任务（如分子性质预测、社交网络分析）的最优编码组合理论。

这项研究不仅为理解图 Transformer 中的位置编码提供了理论基础，更为模型设计者提供了清晰的工程指导：“混合使用，而非单一依赖” 应成为截断位置编码应用的基本法则。