为鼓励人工智能和机器学习领域具有突出贡献和创新性的研究，2022年3月22日， 机器学习国际顶级会议ICLR官方公布了杰出论文奖（Outstanding Paper Award）。在所投稿的4966篇论文中，来自北京大学智能学院贺笛、王立威教授团队的科研成果“Rethinking the Expressive Power of GNNs via Graph Biconnectivity”成为仅有的四篇入选论文之一。

该论文的作者均为北京大学智能学院贺笛、王立威教授研究团队成员：第一作者是2019级博士研究生张博航，共同第一作者为2022级博士研究生罗胜杰，指导老师为贺笛助理教授和王立威教授。

图神经网络（GNN）是近年来兴起的一种机器学习算法，由于其巨大的普适性，已经在各种图数据任务上（如分子性质预测、社交网络分析等）取得了广泛的应用。由于图数据结构上的复杂性，如何设计具有强大表达能力的图神经网络是图机器学习领域的一个核心话题。然而，不同于传统神经网络结构（如多层感知机、卷积神经网络等），主流的图神经网络表达能力非常受限，甚至无法区分一些结构上完全不同的简单图。

主流的图神经网络无法区分上面两张完全不同的图

为了进一步增强图神经网络的表达能力，目前主流的方法是基于图同构判定来分析不同图神经网络的强弱，并以判定图同构问题的能力为标准，设计改进图神经网络的具体模块。然而，由于图同构测试本身的困难性以及与实际问题的脱节，该方法的缺陷日趋明显，人们不清楚这些新设计的神经网络是否有在实际场景下、解决实际问题中的能力。

割点、割边和双连通分量给出了关于图结构信息的骨架描述

 与之相比，该研究团队采用了一种从根本上不同于图同构的全新视角来重新审视GNN的表达能力。具体来说，文章创造性地从图双连通性这一图论中的重要性质出发，引入了一系列度量图神经网络表达能力的新颖指标，如割点、割边、双连通分量等。以割点和割边作为纽带，图的双连通性给出了关于图结构信息的一种优雅的描述，这些信息在理论和实际问题中都有着广泛的应用。例如，图的双连通性与最小生成树、网络流、图匹配和平面图等许多领域有密切联系。在化学反应中，分子化学键的断裂和重组对应双连通性的割边；在社交网络中，割点则起到了连接不同用户群体的桥梁作用。更重要的是，由于双连通性可以使用具有线性计算开销的简单算法来计算，因此人们自然而然地期望图神经网络能够轻松学到图中的双连通性信息，从而提升真实任务中的表现。

绝大多数图神经网络无法区别上面的4组图中双连通性的差异

然而，该研究团队在对过去所有提出的图神经网络架构进行系统分析后发现，它们中的绝大多数对这些指标都不具有表达能力，这意味着主流的图神经网络在实际任务中的表达能力存在重大缺陷。进一步地，文章深入研究了先前方法不能解决双连通性问题的本质原因：传统图神经网络无法编码距离信息。为此，文章提出了一种非常简单高效的方法，即将广义距离直接编码到图神经网络的设计中，并证明了所得到了图神经网络能够解决所有双连通性问题。在实践中，文章基于Transformer结构给出了可以判定双连通性的神经网络实现，它能够保持表达能力并享有完全的并行性。相应的方法在合成数据集和真实数据集上的一系列实验中均超越了先前的网络架构。

论文地址：https://openreview.net/forum?id=r9hNv76KoT3