🤖 machine learning

Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

本文证明，Weisfeiler-Leman 层级及其相关的图神经网络在区分非同构的单谱图方面本质上是不完备的，并引入了 PRiSM，这是一种可证明完备的规范化解法，能够解决这一局限性并实现对此类图上的通用近似。

原作者： Snir Hordan, Nadav Dym, Tim Seppelt

发布于 2026-05-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Snir Hordan, Nadav Dym, Tim Seppelt

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

以下是用简单语言和创造性类比对这篇论文的解读。

全局概览：“图侦探”问题

想象你是一名侦探，正在破解一个谜团：这两幅由相连点（图）构成的图画，是否实际上是同一幅图，只是点的名字被重新命名了？

在计算机科学的世界里，这些图画代表了从化学分子到社交网络的一切。为了解决这个问题，计算机使用一套称为韦斯费勒 - 莱曼（WL）测试的规则。你可以把 WL 测试想象成一名侦探，他观察一幅图画，根据点的邻居给点着色，然后检查颜色模式是否匹配。

长期以来，科学家们认为，如果你让侦探变得更聪明、更强大（通过增加 k-WL 中的"k"），他们最终就能发现两幅图画之间的任何差异。

意外：侦探有盲区

这篇论文证明了一个令人震惊的事实：即使是最聪明的 WL 侦探，也存在永久的盲区。

作者发现了一种特定类型的图画，称为**“简单谱图”**。你可以把这些图画想象成每个点都拥有完全独特的“氛围”或频率，这使得它们在理论上很容易通过数学方法识别（就像在干草堆里找针一样）。

然而，论文证明，无论 WL 侦探变得多么强大，他们总是无法区分某些特定图画对。 这就像有一对穿着完全相同衣服的孪生兄弟；无论侦探多么仔细地观察他们的局部环境，都无法将他们区分开来。

这为什么重要？
大多数现代图人工智能模型（图神经网络）的工作原理完全就像这名 WL 侦探。如果侦探无法区分，人工智能也无法区分。这意味着，在处理这些特定类型的图时，当前的人工智能模型存在根本性的局限。

解决方案：PRiSM（新的排序算法）

既然侦探陷入了困境，作者就构建了一个名为PRiSM的新工具（代表Partition 分区、Refine 细化、Solve 求解、Match 匹配）。

把这个问题想象成一副被洗乱的扑克牌。

问题所在：牌（图的数学特征）是正确的，但它们可能被翻面了（符号歧义）或者顺序错了（排列歧义）。以前的方法试图对它们进行排序，但经常陷入僵局或犯错。
PRiSM 的修复：PRiSM 是一个严格、循序渐进的排序机器，它保证无论牌最初是如何被洗乱或翻面的，这副牌总能被排列成完全相同的方式。
- 分区（Partition）：它将看起来相似的牌分组。
- 细化（Refine）：它深入观察，看看这些组是否实际上不同。
- 求解（Solve）：它确定每张牌正确的“翻转”方向（正或负）。
- 匹配（Match）：它将它们按完美的标准顺序排列。

由于 PRiSM 为这些图创建了完美且独特的“指纹”，它使得人工智能模型最终能够看到旧侦探所遗漏的差异。

结果：它有效吗？

作者在真实世界数据上测试了 PRiSM，具体包括：

分子：预测化学化合物的性质（如溶解度或毒性）。
基准测试：旨在评估人工智能在发现图之间差异方面能力的标准测试。

结果：
PRiSM 的表现与现有方法相当或更优。它成功区分了其他方法无法区分的图对。当与强大的人工智能模型（如 Transformer）结合使用时，它使人工智能能够更有效地学习，证明解决“排序”问题有助于整个系统更好地工作。

主张总结（论文实际所说的内容）

局限性：标准的"WL"图测试层级是不完备的。无论测试多么复杂，它都无法区分所有具有“简单谱”的非相同图。
后果：这意味着所有依赖这些测试的当前图神经网络（GNN）对于这些特定图也是不完备的。
创新：作者创建了PRiSM，这是第一种可证明完备的方法，用于对简单谱图的数学“指纹”（特征分解）进行排序。
证明：他们从数学上证明，将 PRiSM 与标准人工智能模型（如 DeepSets 或 Transformer）结合，可以使人工智能在这些图上近似任何函数（通用近似）。
证据：在实验中，PRiSM 在分子数据集和表达力基准测试中优于以前的方法，表明它能够区分其他方法遗漏的图对。

论文未声称的内容：

它不声称能直接治愈疾病或发现新药（尽管更好的分子建模未来可能有所帮助）。
它不声称能完美适用于每一种类型的图（具体来说，它承认对具有重复特征值的图存在局限性，尽管它们为这些情况提供了一种启发式修复方法）。
它不声称该方法是“连续”的（平滑的）；事实上，他们承认该方法是“不连续”的，这是为了获得完美精度而不得不做出的数学权衡。

技术摘要：Weisfeiler–Leman 在简单谱图上是不完备的，因此需对其进行规范化

问题陈述

图神经网络（GNN）广泛用于图结构数据的学习，但其表达能力通常受限于 Weisfeiler–Leman（WL）层级。已知结果是， $k$ 维 WL 测试（ $k$ -WL）无法区分所有非同构图。然而，特定的一类图——即具有简单谱的图（其邻接矩阵具有互异特征值）——允许在立方时间内进行同构性测试。尽管存在这种理论上的可解性，WL 层级（作为许多 GNN 表达能力的上界）是否能够区分所有简单谱图，仍是一个未解之谜。

此外，尽管谱位置编码（例如拉普拉斯特征向量）常被集成到 GNN 中以增强表达能力，但它们存在固有的模糊性：简单谱存在符号模糊性，而重特征值存在基模糊性。现有的解决这些模糊性的方法（如 SignNet、MAP 和 OAP）在简单谱图上被证明是不完备的，无法区分某些非同构图对。这种不完备性限制了谱 GNN 在此类图上实现通用逼近的能力。

方法论

1. WL 在简单谱上的不完备性证明

作者首先确立了整个 WL 层级在简单谱图上的不完备性。

构造：他们利用 Cai–Fürer–Immerman（CFI）构造，该构造生成无法被 $k$ -WL 区分的非同构图对。
编码：由于标准 CFI 图不具备简单谱，作者引入了一种新颖的整数编码机制。他们将 CFI 邻接模式映射到一个由整数条目组成的正交矩阵 $\tilde{X}$ 。
多重图形成：利用该正交矩阵和具有互异整数特征值的对角矩阵，他们构造了一对具有简单谱的对称多重图（ $A_{G,0}$ 和 $A_{G,1}$ ）。
结果：他们证明了这些构造出的简单谱多重图仍然无法被 $k$ -WL 测试区分，表明 WL 层级的任何层级都无法解决此类图的同构问题，尽管该问题可在立方时间内求解。

2. PRiSM：一种完备的规范化方法

为了解决现有谱方法的局限性，作者提出了PRiSM（Partition, Refine, Solve, Match，即划分、细化、求解、匹配），这是一种针对简单谱图特征值分解的、被证明完备的规范化过程。

输入：特征向量的列正交矩阵 $U$ 。
模糊群：该过程处理模糊群 $S_n \times \{-1, 1\}^k$ （置换和符号翻转）。
四个阶段：
1. 划分（Partition）：根据顶点的符号不变签名（特征向量条目的绝对值）对顶点进行分组。
2. 细化（Refine）：对划分应用 WL 颜色细化过程的谱变体。这利用由特征向量条目逐元素乘积（ $U_v \odot U_u$ ）定义的多重边特征，迭代地细化顶点类别，直到划分稳定。
3. 求解（Solve）：稳定的划分定义了一个在域 $\mathbb{Z}_2$ 上的线性方程组。该方程组强制每个划分类中至少包含一行具有非负条目。求解该方程组可确定特征向量的唯一规范符号（在图自同构意义下）。
4. 匹配（Match）：一旦符号固定，行按字典序排序以解决置换模糊性，从而生成唯一的规范矩阵。
扩展：对于具有重特征值的图（非简单谱），PRiSM 被启发式扩展。它对简单谱块（ $m=1$ ）应用基础过程，并利用 QR 分解和主元选择来解决高阶特征空间（ $m > 1$ ）。

3. 理论保证

完备性：PRiSM 被证明是一种有效的规范化方法，意味着它对同构图产生相同的输出，对非同构的简单谱图产生不同的输出。
通用逼近：通过将 PRiSM 与通用集网络（如 DeepSets 或 Transformer）组合，所得模型实现了对简单谱图上任何同构不变函数的通用逼近。这解决了谱 GNN 在此类图上实现完备性的未解问题。

主要结果

理论发现

定理 1：对于每个自然数 $k$ ，都存在具有 $\Theta(k)$ 个节点的非同构简单谱多重图，它们无法被 $k$ -WL 算法区分。这意味着所有 $k$ -WL 对齐的 GNN 族（包括 PPGN、 $k$ -GNN 和 Graph Transformers）在简单谱图上都是不完备的。
定理 2：PRiSM 为简单谱特征值分解提供了有效的规范化。
定理 3：由 PRiSM 和通用集网络组成的模型在简单谱图上实现了通用逼近。

实证性能

作者在三个基准测试中评估了 PRiSM：

BREC 表达能力基准：PRiSM 在区分非同构图对方面优于竞争性的规范化方法（MAP、OAP），特别是在 Regular 和 Extension 类别上。它正确区分了 212/360 对，而 MAP/OAP 为 199/360 对。
分子属性预测（ZINC, OGB-Mol）：在使用 GatedGCN 和 PNA 骨干网络时，PRiSM 在分子回归（ZINC）和分类（MOLTOX21, MOLPCBA）任务上达到了最先进（SOTA）或与最佳持平的性能。
Transformer 骨干网络（OGB, Alchemy）：当用作 Graph Transformer 的位置编码时，PRiSM 在所有四个数据集（MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY）上均优于所有基线（LPE, MAP, OAP）。作者将此归因于 PRiSM 除了提供校正符号的特征向量外，还提供了确定性的顶点排序，这对于 Transformer 注意力机制至关重要。

意义与主张

本文声称解决了 GNN 表达能力和谱方法理论理解中的一个根本性差距：

WL 的不完备性：它明确证明了 WL 层级尽管能力不断增强，仍无法区分所有简单谱图，而这类图的同构性在理论上是容易的。
首个完备规范化：PRiSM 被提出作为首个针对简单谱特征值分解的、被证明完备的符号规范化方法，克服了 MAP 和 OAP 等先前方法在此类图上不完备的局限性。
通用逼近：该工作确立了如果谱 GNN 与像 PRiSM 这样的完备规范化方法配对，则可以在简单谱图上实现通用逼近，从而证明了使用规范化拉普拉斯位置编码的合理性。
实用价值：实证表明，完全解决谱模糊性会带来下游任务的实质性改进，优于现有的符号不变和规范化方法。

作者指出了局限性，特别是完备性保证严格适用于简单谱图（或证明中构造的多重图），且规范化过程是不连续的，他们论证这是完备符号规范化在数学上不可避免的。他们还将不完备性证明扩展到简单组合图（无多重边）留作未来工作。