Understanding Truncated Positional Encodings for Graph Neural Networks¶

会议: ICML 2026
arXiv: 2606.13671
代码: 待确认
领域: 图学习 / 图神经网络表达力
关键词: 位置编码, 截断, 谱编码, k-调和距离, WL 测试

一句话总结¶

这篇论文从理论上证明：谱编码与游走编码在"完整"形式下表达力等价，但实践中大家用的"截断"版本表达力却天差地别——截断谱编码甚至不再强于 1-WL 测试，因此作者建议"既然要截断，就混用来自不同家族的位置编码"，并在真实数据集上验证了这条经验法则。

研究背景与动机¶

领域现状：消息传递图神经网络（MPNN）的表达力被证明上界为 1-WL 测试，无法捕捉全局结构。图 Transformer（GT）通过位置编码（Positional Encoding, PE）把全局结构信息注入网络来突破这一上界。两大主流 PE 家族是谱编码（拉普拉斯特征空间投影、有效电阻等）和游走编码（邻接矩阵的幂）。已有理论证明：当游走编码用到 \(\Omega(n)\) 阶邻接幂时，二者表达力等价，且都落在 1-WL 与 3-WL 之间。

现有痛点：上述等价性建立在使用"完整"PE 的前提上，而完整谱/游走 PE 需要 \(O(n^3)\) 的时间和空间复杂度——对每张训练图都要做一次特征分解，这在真实任务里代价过高。于是实践者普遍只用截断版本：取拉普拉斯最小的前 \(k\) 个特征空间，或前 \(k\) 阶邻接幂。但这些截断 PE 的理论性质完全没人研究过。

核心矛盾：人们默认"截断 = 完整版的近似"，所以隐含假设截断谱编码和截断游走编码也应该差不多。但这个假设从未被验证。如果截断破坏了等价性，那么"用哪种截断 PE"就不再是无所谓的工程细节，而是会实质改变模型能感知到的结构信号。

本文目标：（1）刻画截断谱编码、截断游走编码、有效电阻三者在表达力上到底差多少；（2）找一个能在谱与游走之间架桥、且可平滑截断的 PE 家族；（3）给实践者一条可操作的选 PE 建议。

切入角度：作者用 WL 测试层级（以及针对 PE 的变体 EP-WL、Walk-WL、GD-WL）作为"结构敏感度"的代理，去比较不同截断 PE 能区分哪些非同构图。这个角度的好处是：表达力结果直接对应"哪些结构性质（中心性、motif 计数、长程依赖）能被模型计算出来"。

核心 idea：截断不是无害近似——它会让原本等价的 PE 家族携带完全不同的信息，因此"混用不同家族的截断 PE"能互补结构线索，而单用任何一个家族都不够。

方法详解¶

这是一篇以理论分析为主、实验验证为辅的论文，没有可画成流水线的"模型"，核心是一串关于截断 PE 表达力的定理。下面先用文字搭好分析框架，再把关键定理按"截断打破等价性 → 有效电阻的弱化 → k-调和距离架桥"的逻辑链讲清。

整体框架¶

论文研究的是相对位置编码（RPE）：给每一对节点 \((u,v)\) 关联一个向量，要求在图同构下保持不变。三类被分析的截断 PE 是：

\(k\)-EP-WL：特征空间投影编码。对拉普拉斯 \(L=D-A\) 的每个特征值 \(\lambda_i\) 取其特征空间投影矩阵 \(\Pi_i=\sum_j z_{i,j}z_{i,j}^T\)，编码为 \(\mathcal{P}^k(u,v)=\{(\lambda_i,\Pi_i(u,v)):1\le i\le k\}\)，即只保留最小的 \(k\) 个特征值。空间复杂度从完整的 \(O(n^3)\) 降到 \(O(kn^2)\)。
\(k\)-Walk-WL：取前 \(k\) 阶邻接幂，\((A^k)_{uv}\) 数的是 \(u,v\) 间长度为 \(k\) 的游走数。
有效电阻 / \(k\)-调和距离：\(R(u,v)=(1_u-1_v)^T L^+ (1_u-1_v)\) 衡量两点的"连通好坏"，其中 \(L^+\) 是拉普拉斯伪逆。

为了刻画"某个 PE 让 GT 有多强"，论文用 GD-WL（对 RPE \(\psi\) 的着色测试 \(\psi\)-WL）作为上界：Graphormer-GD 用 \(\psi\) 当 RPE 时，区分图的能力恰好等于 \(\psi\)-WL（Theorem 3.2）。判断"截断 PE 强不强"，就化归为"\(\psi\)-WL 在 WL 层级里的位置"。

整篇分析得到的鸟瞰结论是：完整谱/游走 PE 都卡在 1-WL 与 3-WL 之间且互相等价，但一旦截断，它们各自只捕获图结构的某一侧面，谁都不严格更强，甚至可能弱于 1-WL。这直接推出实验部分的主张——混用不同家族。

关键设计¶

1. 截断打破等价性：截断谱与游走 PE 表达力根本不同

完整形式下谱编码与游走编码等价，直觉上让人以为"截断版也差不多"。论文用两个对偶的反例定理推翻了它。Theorem 4.1 构造了一对图 \(G,H\)，它们能被 1-WL 区分，却无法被任何 \(k\in\Omega(n)\) 的 \(k\)-EP-WL 区分——也就是说，即便保留线性多个特征空间，截断谱编码也可能比最基本的 1-WL 还弱，因此截断 EP-WL 与 WL 层级不可比（既有时强、有时弱）。Theorem 4.2 给出反方向：存在一对图被 \(\Omega(n)\)-Walk-WL 判不出来，却能被仅 \(k=1\) 的 1-EP-WL 区分。两个定理合起来说明，常数尺寸的一种截断 PE 能区分线性尺寸另一种截断 PE 区分不了的图。

这个结果对"造更强的图 Transformer"有直接含义：截断特征向量是最常用的 PE，但单用它不保证比 MPNN 更强。补救办法是在特征向量编码之外，再加入某种邻接信息（邻接 PE、最短路距离）或消息传递层，让谱与游走的互补信息同时进入网络。

2. 有效电阻的弱化：它连邻接信息都没编全

有效电阻是 GT/MPNN 里极常用的 PE，凭直觉它应该很强（正比于两点间的通勤时间）。但论文证明它其实相当弱。Theorem 4.3 在加权图上构造了一对图，有效电阻分不开，但邻接-WL 分得开；由于 \(A\) 可被 EP-WL 恢复，立刻得到 Corollary 4.1：有效电阻分不开的图，EP-WL 能分开，即有效电阻严格弱于特征空间投影。更进一步，这推翻了 Zhang 等人此前的猜想（有效电阻-WL 强于最短路-WL，且编码了整张图的谱）：既然有效电阻连邻接信息都没保全，它显然没有编码完整谱。作者据此猜想在无权图上有效电阻-WL 也不强于 1-WL。一句话：把有效电阻当成"很强的谱 PE"是一种误解，它只是 \(k\)-调和距离家族里最弱的那个特例（\(k=1\) 的平方）。

3. \(k\)-调和距离架桥：从有效电阻到完整谱的一族可截断 PE

既然有效电阻太弱，作者转向它的推广——\(k\)-调和距离 \(H^k(u,v)=\sqrt{(1_u-1_v)^T (L^+)^k (1_u-1_v)}\)（\(k=1\) 平方即有效电阻）。它的妙处在于用单维通道就能携带不同层级的谱信息，是谱编码与游走编码之间的天然桥梁。三个定理刻画了它的能力边界：Theorem 4.6 证明拼接 \([2n]=\{1,\dots,2n\}\) 个 \(k\)-调和距离与 EP-WL 等价，说明谱编码和游走编码只是"众多等价 PE"中的两个，给替代 PE 打开了大门；Theorem 4.4/4.5 给出经典夹逼——稀疏-\(k\)-调和-WL 严格强于 1-WL（因为它用了边信息），又被 3-WL 严格压住。

家族内部也有有趣的张力。Theorem 4.7 说，在树上稀疏-双调和（biharmonic, \(k=2\)）-WL 一次迭代就能区分某些图对，而稀疏-有效电阻-WL 需要 \(\omega(n)\) 次迭代都做不到——因为树上任意两点的有效电阻恒等于最短路（恒为 1，毫无信息，Lemma 4.1），而双调和距离编码的是"边对全图有多中心"，能提供额外拓扑信息。但 Theorem 4.8 又从另一面给出"普遍一致性"：如果某个 \(k\)-调和距离能区分一对图，那么除了至多 \(O(n^5)\) 个 \(k'\) 取值外，绝大多数 \(k'\)-调和距离也能区分它们——所以不同 \(k\) 之间虽有差距，但整体高度相关。

一个完整示例¶

以树为例最能看清"截断 PE 各自盲在哪"。给定一对非同构的树 \(G,H\)：

用有效电阻当 PE：树上任意两点的有效电阻 = 它们的最短路距离，而所有边的有效电阻恒为 1。于是有效电阻给所有边贴上相同标签，等于没提供任何超出 1-WL 的信息——稀疏-有效电阻-WL 在树上退化得和 1-WL 一样强（Lemma 4.1），\(o(n)\) 次迭代都分不开。
换成双调和距离（\(k=2\)）：每条边 \((s,t)\) 的双调和距离完全由这条边两侧的节点数决定，于是不同形状的树会得到不同的边标签，稀疏-双调和-WL 一次迭代就能把这对图分开（Theorem 4.7）。

同一对树，换一个 \(k\) 就从"完全分不开"变成"一步分开"，把"截断 PE 不是完整版的等价近似，而是各自只看见结构某一面"这件事讲得很具体。

实验关键数据¶

主实验¶

实验用 Graphormer-GD 架构，在 BREC（专门测真实表达力的数据集）与 ZINC-12k（分子性质回归）上验证理论。BREC 上单个 \(k\)-调和距离在 Basic/Regular/Extension 三类图上就逼近理论上界，且始终是单维编码，开销远低于多维的 EP 投影。

BREC 子类	双调和	4-调和	\(k\)=5 EP	\(k\)=7 EP	3-WL
Basic	46.6	86.7	91.6	100	100
Regular	27.1	32.1	30.7	35.7	35.7
Extension	59	83	92	100	100
Total(%)	32	46.5	48	—	60

可以看到有效电阻（最弱的 \(k\)-调和）全程 0 分，而双调和/4-调和已显著回血；EP 投影从 \(k=2\) 到 \(k=3\) 有一次锐增，之后收益递减。作为对比，堆 20 阶邻接幂的游走编码总分约 53.5%，与双调和距离相当，但它是多维编码。

消融实验（ZINC-12k，PE 组合对比，越低越好）¶

固定 PE 维度为 8，测各家族单用与混用的回归 MAE：

PE 组合	维度配比	Test MAE
Projections（仅特征投影）	8	\(0.117\pm0.005\)
\(k\)-Harmonics（仅调和）	8	\(0.076\pm0.006\)
Walks（仅游走）	8	\(0.082\pm0.003\)
Projections + Walks	4+4	\(0.075\pm0.005\)
Projections + \(k\)-Harmonics	4+4	\(0.078\pm0.002\)
Walks + \(k\)-Harmonics	4+4	\(\mathbf{0.064\pm0.002}\)

关键发现¶

混用 > 单用：游走 + \(k\)-调和的组合（0.064）显著优于任何单家族，验证了"截断就该混用不同家族"的核心主张。
冗余信号也会出现：特征投影 + \(k\)-调和这一对几乎没带来增益（0.078 对单用调和的 0.076），说明截断投影提供的归纳偏置在调和距离面前可能是冗余的——并非所有组合都有用，要混"信息互补"的家族。
单维通道的性价比：\(k\)-调和距离用一维就能逼近多维 EP/游走的效果，预处理与训练开销更低；还有近线性时间 \(O(mk\,\mathrm{poly}\log n)\) 的近似算法（基于快速拉普拉斯求解器 + Johnson-Lindenstrauss 投影），契合"截断本就是为省算力"的初衷。

亮点与洞察¶

"截断 ≠ 近似"这个观念翻转最有价值：长期以来截断 PE 被当作完整 PE 的廉价替身，本文证明它们其实是一个独立的设计空间，各自看见结构的不同侧面——这能解释为什么实践中换一种截断 PE 下游表现就变。
用 WL 层级当"结构敏感度代理"的论证很克制：作者明确承认图同构判定在真实数据上区分度有限，但坚持它是"哪些结构信号能被模型暴露"的有原则代理，避免了过度声称。
\(k\)-调和距离作为统一视角可迁移：把有效电阻看成 \(k=1\) 的特例、用单维通道扫不同 \(k\)，这套"在谱与游走之间连续插值"的思路，可迁移到设计新的轻量 PE，或给现有 GT 做 PE 选型的消融基线。
可操作的经验法则：结论落到"要截断就混不同家族"，且给了哪些组合互补（游走+调和）、哪些冗余（投影+调和），对调参有直接指导。

局限与展望¶

多为加权图上的反例：Theorem 4.3 等关键分离结果在加权图上构造，无权图上"有效电阻-WL 是否也不强于 1-WL"目前只是猜想（作者在附录讨论了推广的可能与障碍）。
表达力 ≠ 下游性能：本文的核心货币是图同构区分力，但作者自己强调真实任务不等于判同构；理论上更弱的 PE 在具体回归/分类任务上未必更差，ZINC 的提升幅度也较温和（0.082→0.064）。
实验规模有限：主要在 BREC 与 ZINC-12k 上验证，未覆盖大规模图、节点级长程任务等场景，"混用"在更广基准上的稳健性还需更系统的实证。
可改进方向：把 \(k\)-调和距离的连续谱视角与可学习的 PE 选择（让模型自己决定混哪些家族、各占多少维）结合，可能比固定等比混合更优。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统研究截断 PE 的表达力，并翻转"截断=近似"的固有认知
实验充分度: ⭐⭐⭐ 理论扎实，但实证仅 BREC + ZINC-12k，规模与任务覆盖偏窄
写作质量: ⭐⭐⭐⭐ 定理-反例-含义的逻辑链清晰，且对适用边界保持克制
价值: ⭐⭐⭐⭐ 把截断 PE 立为独立设计空间，并给出"混用不同家族"的可操作建议