🤖 machine learning

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

本文介绍了一种基于图对齐问题的、针对图神经网络的新型自监督基准测试框架，证明了任务难度可以有效地对模型架构进行排序，并且由此学习到的位置编码能显著提升下游图任务的性能。

原作者： Adrien Lagesse, Marc Lelarge

发布于 2026-06-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Adrien Lagesse, Marc Lelarge

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

核心理念：为 AI 打造一个全新的“健身房”

想象一下，你想测试一名新晋举重选手的力量。你不会只是让他们去搬一个随机的箱子；你会把他们放在一台特定的、可调节重量的举重机上，这样你就能精确控制重量的大小。

这篇论文为图神经网络 (Graph Neural Networks, GNNs) 提出了一种新的“举重机”。GNNs 是一种旨在理解呈现为“连接图谱”形式的数据（如社交网络、化学分子或道路地图）的 AI。

作者认为，目前测试这些 AI 的方法存在缺陷，因为它们混淆了地图的“形状”与地图上的“标签”（如颜色或名称）。他们想要测试的是 AI 理解纯粹形状的能力。为此，他们基于一个被称为图对齐 (Graph Alignment) 的谜题创建了一个基准测试。

核心谜题：“幽灵地图”游戏

你可以这样理解图对齐问题：

想象你拥有一张详细的城市地图（图 A）。
现在，想象一个相同城市的“幽灵版本”（图 B）。它拥有完全相同的街道和交叉路口，但街道名称被打乱了，而且一些街道被随机移除或新增了一些街道。
挑战： 你的 AI 必须观察这张“幽灵地图”，并搞清楚幽灵地图上的哪个交叉路口对应于原始地图上的哪个交叉路口。

如果 AI 能成功匹配这两张地图，就证明它真正理解了城市的结构，而不仅仅是路牌上的名字。

他们是如何构建测试的

研究人员并没有只使用一张地图。他们构建了一个拥有不同地形类型的完整“健身房”：

合成地图： 计算机生成的随机城市。
现实世界地图： 来自社交网络（如 Twitter）、化学分子和科学论文的真实数据。

他们还添加了一个“难度滑块”（称为噪声）。

低噪声： 幽灵地图与原始地图几乎完全一致。谜题很简单。
高噪声： 幽灵地图非常混乱，有很多缺失或虚假的街道。谜题非常难。

发现： 他们发现，如果谜题太简单或太难，所有的 AI 表现看起来都一样（要么全都做对，要么全都失败）。但在一个**“金发姑娘原则”下的适中难度水平**（即难度刚刚好），最聪明和最笨的 AI 之间的差异会变得非常明显。这使得研究人员能够准确地对模型进行排名。

测试结果：谁赢得了健身房？

当他们运行测试时，发现了一些关于不同 AI 架构运作方式的有趣现象：

各向同性 (Isotropic) vs. 各向异性 (Anisotropic)： 把“各向同性”模型想象成对待所有方向都一视同仁的人（就像一个人在绕圈走）。“各向异性”模型则像是那些会关注自己所面向的具体方向的人。
获胜者： “具备方向感”（各向异性）的模型始终击败了“盲目方向”（各向同性）的模型。这表明，关注连接的具体方向有助于 AI 更好地理解地图。

额外收获：学习如何“阅读”地图

这篇论文最令人兴奋的部分是 AI 解决谜题之后发生的事情。

当 AI 学习对齐这些地图时，它会为地图上的每一个点创建一个特殊的“身份证”（称为嵌入/Embedding）。这些“身份证”包含了该点在整体结构中所处位置的深度理解。

作者展示了这些“身份证”是如此强大，以至于可以将它们用作另一种 AI 类型——Transformer（驱动聊天机器人和图像生成器的同类 AI）的位置编码 (Positional Encodings)。

类比： 通常，Transformer 就像是能读懂书本但不知道单词在页面上具体位置的人。这些“身份证”就像是单词的 GPS，告诉 Transformer 每一部分数据在结构中的确切位置。
结果： 当他们使用这些由 AI 生成的“身份证”时，Transformer 在预测化学性质（例如药物的溶解度）方面变得极其出色，甚至能以 98% 的准确率从头开始重新绘制整张地图。

总结

简而言之，这篇论文指出：

我们需要一种更好的方法来测试图 AI 是否真的理解形状，而不只是标签。
我们创建了一个“幽灵地图”谜题（图对齐），通过调节难度来观察哪种 AI 才是真正的智者。
我们发现，关注方向的 AI 表现最好。
这些 AI 从谜题中学到的“教训”非常强大，可以用作教学工具，让其他 AI 理解复杂的结构，从而在科学和化学领域实现更好的预测。

作者还发布了一个免费工具包，任何人都可以利用它构建这些“幽灵地图”谜题并测试自己的 AI 模型。

技术摘要：用于图神经网络基准测试与位置编码学习的图对齐任务

问题陈述

图神经网络（GNNs）广泛应用于化学、材料科学和社会网络等领域。然而，评估其结构理解能力仍然具有挑战性。现有的基准测试往往将结构能力与特征学习混为一谈，或者依赖于与特定问题拓扑或合成模型（如随机块模型 SBM）紧密相关的组合优化任务（如 SAT、TSP），这限制了它们的泛化能力。此外，现有方法难以提供一种细粒度的指标，用以比较同一表达类（例如 1-Weisfeiler-Lehman 类）中的模型，也难以量化在现实应用中各种多样化图拓扑上的结构表达能力。

作者提出通过引入基于图对齐问题（也称为图匹配）的基准测试方法来解决这一差距。该任务涉及对齐两个无标签图，以最大化重叠边数，这是一个推广了图同构的组合优化问题。

方法论

1. 图对齐任务

核心任务定义为寻找两个具有 $N$ 个顶点的图 $G$ 和 $\tilde{G}$ 之间的置换 $\pi^*$ ，以最大化其邻接矩阵的重叠：
$\pi^* \in \arg \max_{\pi \in S_N} \sum_{i,j} A_{i,j} \tilde{A}_{\pi(i),\pi(j)}$
这被框架化为一个自监督学习任务。作者采用了孪生架构（Siamese architecture），通过一个 GNN 处理两张图以生成节点嵌入 $X$ 和 $\tilde{X}$ 。随后计算相似度矩阵 $\Sigma = X\tilde{X}^T$ 。

训练： 模型最小化预测相似度矩阵与地面真值对齐（植入置换）之间的二元交叉熵损失。
评估： 使用匈牙利算法在 $\Sigma$ 上求解线性分配问题，以提取预测的置换。性能通过正确映射节点的百分比来衡量。

2. 数据集构建

为了克服以往合成数据集（例如仅限于 Erdős-Rényi 图）的局限性，作者提出了一种从任何现有图数据集（基础数据集）生成图对齐数据集的方法。

相关图生成： 对于基础图 $G$ ，通过基于噪声水平 $\eta$ 随机添加和删除边来生成相关图 $\tilde{G}$ 。
植入解（Planted Solution）： 由于最优对齐是已知的（即在噪声之前的恒等置换或已知置换），因此可以获得地面真值，而无需求解 NP 难问题。
可扩展性： 对于大型图（如 OGBN-Arxiv），使用广度优先搜索（BFS）采样算法提取保留局部拓扑的小型子图，使其能够与消息传递神经网络（MPNNs）兼容。
难度控制： 通过改变噪声水平 $\eta$ （从 4% 到 30%），作者创建了一个具有可控难度的系列数据集，从而实现细致的评估。

3. 位置编码学习 (GAPE)

作者利用从图对齐任务中学习到的节点嵌入作为图对齐位置编码（GAPE）。这些嵌入旨在作为 Transformer 架构的结构输入，因为 Transformer 本身缺乏对图结构的固有访问能力。

核心贡献

新型基准测试任务： 引入图对齐问题作为 GNN 的基准测试，它推广了 Weisfeiler-Lehman 测试，并允许在不修改底层图结构的情况下，在多种拓扑（分子、社交、随机）上进行评估。
数据集生成框架： 一种从合成及真实世界基础数据集中生成图对齐数据集的全面方法，能够创建不同难度水平的数据集。
架构经验排名： 对广泛使用的 MPNNs（GCN、GIN、GatedGCN、GAT、GATv2）进行了系统性的基准测试，结果表明各向异性模型（anisotropic models）在结构分析方面始终优于各向同性模型（isotropic models）（如 GCN 和 GIN），即使是在同质图中也是如此。
最优难度水平： 发现存在一个“最优噪声水平”，在该水平下模型之间的性能差距达到最大，从而提供了对超参数选择和随机种子具有鲁棒性的统计显著排名。
位置编码 (GAPE)： 证明通过图对齐学习的嵌入可以作为有效的 Transformer 位置编码，其表现优于或等同于基于谱理论和随机游走的编码，并在分子回归任务中表现出色。
图重建： 证据表明 GAPE 嵌入有效地压缩了图结构，使得使用简单的解码器即可实现约 98% 的全邻接矩阵重建准确率。
开源工具： 提供了一个用于生成这些数据集并基准测试新架构的 Python 包。

结果

模型性能： 在五个基础数据集（Erdős-Rényi, AQSOL, PCQM4Mv2, CoraFull, OGBN-Arxiv）的实验中，各向异性架构（GatedGCN, GAT, GATv2）比各向同性架构（GCN, GIN）实现了更高的对齐准确率。
噪声敏感性： 在极低或极高噪声水平下，模型间的性能差距微乎其微。差距在最优噪声水平（例如分子图的 $\eta \approx 15\%$ ）处达到峰值，此时统计显著性最高。
下游任务： 当作为 Transformer 的位置编码用于分子回归（AQSOL, PCQM4Mv2, ZINC）时，GAPE 达到了与拉普拉斯、随机游走及其他谱编码相比具有竞争力的或最先进的平均绝对误差（MAE）。具体而言，GAPE+RWPE 在 AQSOL 和 PCQM4Mv2 上取得了最佳结果。
重建： 一个使用冻结 GAPE 编码器的自动编码器实现了 98% 以上的邻接矩阵重建准确率，证实了这些嵌入捕捉到了完整的图拓扑。
相关性： 在图对齐准确率与下游分子属性预测误差之间观察到强负相关性（ $r < -0.90$ ），这表明结构对齐能力是这些任务的主要瓶颈。

意义与主张

本文声称提供了一个稳健且细粒度的框架，用于评估 GNN 的结构表达能力，且该评估独立于特定的节点或边特征。通过隔离结构理解，该基准测试揭示了各向异性模型比此前确立的各向同性模型提供了更丰富的图拓扑表示。

此外，作者认为图对齐任务不仅仅是一个“谜题”，而是一个基本的预训练目标。由于学习到的嵌入可以用于高精度的图重建，并能显著提升下游 Transformer 的性能，这表明该任务迫使模型学习高保真度的图结构压缩。这验证了该基准测试在对比架构以及为化学和材料科学领域的实际应用生成有用表示方面的实用价值。

该工作总结道，图对齐基准测试提供了一种灵活、与领域无关的方法来进行 GNN 评估，能够适应任何目标应用领域的特定拓扑特征。