通过关注双重连接性，显著提高图神经网络的性能
三个要点
✔️ 重点关注图双连通性的表现力，这在图神经网络（GNN）中尚未得到广泛关注
✔️ 发现现有的 GNN 对双连通性的表现力较差。
✔️ 提出了 Graphormer-GD，作为一种基于变换器的快速 GNN，对双重连接性具有充分的表达能力。
RETHINKING THE EXPRESSIVE POWER OF GNNS VIA GRAPH BICONNECTIVITY
written by Bohang Zhang, Shengjie Luo, Liwei Wang, Di He
(Submitted on Submitted on 23 Jan 2023 (v1), last revised 11 Feb 2024 (this version, v3))
Comments: Extended from ICLR 2023 Outstanding Paper; 60 pages, 12 figures. Fix typos in the previous version
Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)
code：
本文所使用的图片要么来自论文、介绍性幻灯片，要么是参考这些图片制作的。
介绍
图神经网络（GNN）由 Gori 和 Scarcelli 于 2005 年首次提出。图是一种关系，由顶点（节点）和连接顶点的边（边）表示。GNN 的目的是根据给定数据的图结构，学习汇总每个节点相邻节点特征的特征。
例如，根据学习到的特征，可以预测每个节点的标签；使用 GNN 的效果是，根据节点在图中的邻近程度，也更容易成功猜测节点的未知标签。
然而，根据给定数据的图结构，每个节点的邻居特征是如何聚合的，可能会学习到无法反映图结构差异的特征。
简而言之，当根据不同的图结构学习特征时，期望学习到的特征应该是不同的，但根据 GNN 的类型，有可能根据不同的图结构学习特征，但得到的特征是相同的。
Weisfeiler-Lehman 检验（WL 检验）经常被用来比较此类 GNN 图的表达能力。同构是指图的连接方式相同，只是图节点的排列方式不同。这意味着它们的不同之处仅在于编号方式，即识别图的节点。
WL 检验是 1968 年提出的一种经典方法，用于确定这些图形的同构性。该测试方法是，如果按照一定的规则给图的节点着色，则具有相同颜色直方图的图将被判定为同构。虽然它的缺点是节点数和度相同的图都被认为是同构的，但它被认为是一种快速而强大的判断方法。
虽然有很多关于 GNN 的研究都探讨了是否有可能通过学习特征来正确判断图的同构性，从而使其与 WL 测试一样好或更好，但目前还没有关于 GNN 的研究侧重于图的双重连通性。
与此相反，本文重点关注图双连接性。它研究了现有 GNN 方法在图对偶连通性方面的表现力，发现大多数方法在图对偶连通性方面缺乏表现力。
此外，Graphormer-GD 是一种基于变换器的高效计算 GNN，在图的双重连接性方面具有很强的表现力。这使得它在实际问题的基准测试中表现出了很高的性能。该论文被选为 2023 年 ICLR 优秀论文。
下文将介绍图形的双重连通性、WL 测试、GD-WL 和 Graphormer-GD 及其评估结果。
图形的双重连通性
我们解释说，本文介绍的重点是图的对偶连通性，但是图具有对偶连通性首先意味着什么？
图的双连通性指的是，如果从图中删除一个节点（或边），图的连通性（即所有节点都可以从图中的一个节点通过边追溯到所有节点）将保持不变。
如果即使节点被排除在外也能满足，则称为节点双重连通性；如果即使边缘被排除在外也能满足，则称为边缘连通性。
反之，如果移除图形中的一个节点会导致其失去连通性，则该节点被称为切割节点。如果删除一条边会使其失去连通性，那么这条边就被称为切割边。
切割节点和切割边的示例如图 1 所示。
图 1 (a) 显示了原始图形。图 1 (b) 中显示的红色边是一条切割边。删除这条剪切边会使图形失去连接性。图 1 (c) 中的橙色边节点是一个切割节点。移除该节点会导致图形失去连通性。
图的双连通性本身就是图论中长期备受关注的一个特性。在应用方面，以通信网络为例，如果通信网络上的某个设备发生故障，通信就会中断。因此，在创建通信网络时，必须确保不存在被切断的节点。从这个意义上说，它可以成为现实世界中的一个重要属性。
对于此类预测任务，图的双重连通性是一个重要特征，因此使用无法表示图的双重连通性的 GNN 预计会大大降低预测准确率。
WL 测试（色彩调整算法）
WL 测试有多种类型，本节将介绍最基本的一阶 WL 测试，并解释其难点在于不能很好地识别双连接性。
一阶 WL 测试
一阶 WL 检验也被称为色彩细化算法。
首先，如果节点没有颜色，则用明显的颜色对其进行初始化。例如，如果图是一个分子结构，那么初始化时，当原子被视为节点，原子之间的键被视为边时，不同的原子名称就会被赋予不同的颜色。
接下来，为每个节点创建一对自己的颜色和一个相邻节点颜色的多集合（这个集合可能包含多个相同元素）。对于每个节点的颜色对（自己的颜色、相邻节点颜色的多集合），给唯一的颜色对赋予不同于前一个颜色对的颜色，并进行一一对应。重复这一过程，直到调整前后的颜色不再相同。
对于两个图形，比较图形末端的颜色直方图，如果相同则判定为同构，否则判定为非同构。
通过一阶 WL 检验双连接的可识别性
在考虑 GNN 的表达能力时，关注双重连通性的一个原因是，在某些情况下，一阶 WL 检验无法识别双重连通性。
在一些例子中，一阶 WL 检验无法识别具有对偶连通性的图中的同构，如图 2 所示。
在图 2 中，第一行的图是具有双重连通性的图，其中红色边框的节点是剪切节点，红色线条是剪切边；第二行的图是不具有双重连通性的图，其中红色边框的节点是剪切节点，红色线条是剪切边。将(a)~(d)行中的图相互比较，它们的连接方式各不相同。换句话说，它们是非同构图形。然而，在 WL 检验中，由于颜色直方图（每种颜色出现的次数）相同，它们被误判为同构。
因此，简单的 WL 检验并不能充分代表双重连通性，所以我们需要一种能够代表具有双重连通性的图形的 WL 检验。
建议 GD-WL 的 WL 测试
本文通过数学方法证明，在WL 检验中，节点间的距离信息可以用来获得双连接的表现力。本文提出的新算法是一种使用节点间广义距离度量的颜色调整算法。
GD-WL 更新节点 v u∈[图节点集]的 "多对集"（（v,u）的距离，u 的颜色），为唯一的 "多对集 "赋予唯一的颜色。
在 GD-WL 中使用最短路径距离作为（v,u）距离的情况称为 SPD-WL。最短路径距离是从节点 v 到节点 u 所需的最短边通过数。SPD-WL 在本文中被证明对边对偶连通性具有完全判别性。但它对节点对偶连通性不具有完全判别能力，无法判别图 2(c) 列中的两个图。
另一方面，在边缘双重连通性方面，本文证明了当使用电阻距离（RD-WL）时，节点双重连通性具有完全的可判别性。电阻距离将图视为一个电路，将边缘视为电阻为 1 欧姆时，节点 v 到节点 u 的有效电阻为距离。
因此，可以通过改变距离指数来识别边的双重连通性和节点的双重连通性，所以在 GD-WL 中，SPD-WL 和 RD-WL 都可以用来完整识别双重连通性。
但是，有些图形即使同时使用 GD-WL 和 PD-WL 和 RD-WL 也无法确定其同构性。这些图形如图 3 所示。
图 3 (a) 显示了 SPD-WL 未能识别图形但 RD-WL 成功识别图形的示例，图 3 (b) 显示了 SPD-WL 和 RD-WL 均未能识别图形的示例。
拟议的 GNN Graphormer-GD
GD-WL 的实现可以通过将节点间距离信息纳入 Transformer 的多头注意力来完成，并且可以通过利用 Transformer 的并行处理来高效计算 GD-WL。因此，Graphormer-GD 被命名为 "Graphormer-GD"。
Graphormer-GD 评估结果。
本节介绍本文提出的 GNN Graphormer-GD 的评估结果。
切割节点和切割边缘检测任务
检测切割节点和切割节点任务的评估结果如表 1所示。
现有的图神经网络（GCN - Graphormer）的准确率低于 85%，而Graphormer-GD 的准确率则高达 100%。在双连接性方面，现有图神经网络的表现力不足可以得到证实。
还可以看到，根据理论，当去除电阻距离（w/o. Resistance Distance）时，拟议的Graphormer-GD 在检测节点双重连接性方面的准确性会降低。
实际问题基准评估。
作为现实世界问题的基准，准确性在一个名为 ZINC 的数据集上进行了评估，该数据集可根据分子图预测化学性质。
为了检验 Graphormer-GD 的可扩展性，表 2 列出了对 ZINC-Subset（12 000 个分子图）和 ZINC-Full（250 000 个分子图）的评估结果。
表 2 中的参数是 GNN 的模型参数数。为公平起见，建议的 Graphormere-GD 的模型参数大小与其他方法相当。
表 2 中的测试 MAE（平均绝对误差）越小，预测精度越高，但与表 2 中的现有方法相比，GD-WL 的预测精度最高。
GNN 的性能可以通过提高双重连接的可辨别性来改善，但这一问题一直没有得到关注。
表 2 中的时间是每个训练历元的训练时间，可以看出，GD-WL 与表 2 中的其他方法需要相同的处理时间。
由此可见，GD-WL 既精确又快速。
结论
本文介绍的论文表明，就 GNN 的表现力而言，可以通过提高图的双重连通性的表现力来提高 GNN 的性能，而这种连通性并不是人们关注的焦点。
WL 测试经常被讨论到 GNN 的表达能力，结果表明，在某些情况下，WL 测试无法识别图形的双重连通性，这表明 WL 测试需要改进。
GD-WL 作为一种使用节点间距离信息的 WL 测试被提出，并被证明能够识别双重连接性。
此外，研究还表明，GD-WL 可以通过学习现有的基于变换器的 GNN 方法来实现，并被提议为 Graphormer-GD。
Graphormer-GD 在检测双重连通性的任务中表现出了压倒性的性能，与现有方法相比，它在实际基准问题上达到了最佳的准确性。
这篇论文被选为国际人工智能大会（ICLR 2023）的优秀论文，是一篇理论与实践相结合的厚重论文。包括附录在内，论文长达 60 页。其中有许多证明、许多插图和许多现有方法的比较。论文详尽地探讨了各种建议的可能性、局限性和扩展性。这篇论文似乎是出于一种强烈的兴趣和好奇心。
这里介绍的是北京大学发表的一篇论文。近年来，我们听说被 NeurIPS 接收的论文中有 50% 是来自中国的研究人员。这充分说明了中国科研力量的强大。第一作者似乎来自资优生学校，虽然我没有详细研究，但从信中来看，可能是中国的天才们正在为人工智能研究而聚集。
与本文相关的类别
