为鼓励人工智能和机器学习领域具有突出贡献和创新性的研究，2024年5月7日， 机器学习国际顶级会议ICLR官方公布了杰出论文奖（Outstanding Paper Award）。在所投稿的7262篇论文中，来自北京大学智能学院王立威、贺笛教授团队的科研成果“Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness”经层层选拔最终荣获杰出论文奖提名，成为11篇荣获杰出论文奖提名的论文之一。该论文的共同第一作者是2019级智能学院博士研究生张博航与2021级数学学院本科生盖景初，指导老师为王立威教授和贺笛助理教授。

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

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

目前研究者们已经提出了大量的工作来理解和增强图神经网络的表达能力。一类代表性的工作基于图同构判定来分析不同图神经网络的强弱，并以判定图同构问题的能力为标准，设计改进图神经网络的具体模块。然而，由于图同构测试本身的困难性以及与实际问题的脱节，该方法的缺陷日趋明显。另一类代表性工作则聚焦实用场景下的图神经网络表达能力，如子图计数，通过将子图计数信息引入图神经网络的节点特征中来增强模型在实际中的表现。然而，子图计数并不能全面的衡量图神经网络的表达能力，且相应的模型架构没有理论上的表达能力保证。

与之相比，该研究团队提出了一种新颖的框架来研究GNN的表达能力。具体来说，文章提出了一种定量的表达能力指标，称为同态表达能力，它衡量了GNN对子结构进行同态计数的能力。同态是图论中的基础性概念，与图上的染色、匹配、计数等问题具有密切联系。通过研究GNN对哪些子结构能够同态计数，同态表达能力可被定义为包含所有能够被同态计数的子结构的集合。那么，不同图神经网络的表达能力便可以由集合之间的包含关系和集合差来简单的定量比较。

文章证明了对于四大类图神经网络，如消息传递GNN、子图GNN、局域GNN和Folklore GNN，同态表达能力是完整的，即同态信息能够完全决定GNN所输出的图表示。文章进一步通过嵌套耳分解的概念对各类GNN的同态表达能力给出了优雅的描述。

嵌套耳分解示意图以及不同耳之间所诱导的关系树。

接下来，文章通过三种不同的角度说明了这些理论结果的重要意义。首先，同态表达能力提供了一种极为简单的方法来定量比较不同网络架构的表达能力差异，这回答了先前工作所遗留的一系列开放性问题。第二，同态表达能力能够完全决定图神经网络的子图计数能力，从而理解其在实际应用中的能力，如分子图中苯环的计数。第三，同态表达能力与图神经网络计算图上多项式的能力具有密切联系。这些结果为之前的一系列工作提供了新颖的见解，在不同子领域之间建立了桥梁，并解决了一些开放性的问题。文章最后通过实验表明，GNN 模型的实际性能与所提出的指标非常吻合。

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