图神经网络的表达能力，究竟有多强大？ _神经网络

文章插图
作者 | Mr Bear
编辑 | 丛末
近年来，随着图神经网络在各个领域的火热应用，越来越多的学者试图从图论的角度对图神经网络的表达能力进行理论分析，并基于这些理论分析开发出了性能强大的模型。然而，在实际应用中，这些在理论上非常强大的模型的性能往往会受到计算复杂度等因素的限制。
本文作者 Michael Bronstein 是一名来自帝国理工学院的教授，同时也是 Twitter 图机器学习项目组的负责人。在本文中，他深入浅出地介绍了近年来分析图神经网络表达能力的工作，并介绍了他们对于该领域未来发展方向的思考。

1图神经网络和 WL 图同构测试之间的关系

文章插图
众所周知，传统的前馈神经网络（多层感知机）是一种通用函数近似器：它们能够以任意的准确率逼近任意的平滑函数。对于近期兴起的图神经网络来说，其表征性质还不太为人所知。在实验中，我们经常可以看到图神经网络在某些数据集上性能优异，但同时又在另一些数据集上表现令人失望。
为了探究造成这种现象的根本原因，我们不得不思考一个问题：图神经网络究竟有多强大？
在探究这一问题的过程中，我们所面临的一个挑战是：实际应用场景下使用的图往往是连续结构和离散结构（节点、边特征、连通性）的组合。因此，该问题可以被表述为不同的形式。一种可能的形式化定义是：图神经网络是否能够区分不同类型的图结构。在图论中，这是一种被称为「图同构问题」的经典问题，旨在判断两个图在拓扑意义上是否等价。两个同构的图拥有相同的连通性，其差别仅仅可能是节点的排列不同。
稍令人惊讶的是，我们尚不知晓精确的图同构问题的复杂度级别。该问题在多项式时间内不可解，它也不是一个 NP 完全（NPC）问题。有时，我们将其复杂度称为一种特殊的「GI 级」（GI class）。
1、Weisfeiler-Lehman 测试
【图神经网络的表达能力，究竟有多强大？】Boris Weisfeiler 和 Andrey Lehman 于 1968 年发表的具有开创性意义的论文「The reduction of a graph to canonical form and the algebra which Appears therein 」），提出了一种高效的启发式算法，我们现在将其称为「WL 测试」。
最初，人们认为 WL 测试可以在多项式时间内求解图同构问题。但一年之后，人们就举出了一个反例。然而，从概率意义上说，似乎 WL 测试对于几乎所有的图都有效。

文章插图
图 1：在两个同构图上执行 WL 测试的示例。包含弧线的 hash 圆括号代表多重集。在着色情况不再变化后算法会终止，并给出输出结果（颜色直方图）。若将两图输入给该算法得到的输出相同，则说明两图可能同构。
WL 测试是建立在迭代式的图重着色（图论中的「着色」指的是一种离散的节点标签）基础上的，在初始状态下，每个节点的颜色均不相同。在每一步迭代中，算法会聚合节点及其邻居节点的颜色，并将它们表征为多重集，然后将聚合得到的颜色多重集通过 Hash 函数映射到某种唯一的新颜色上。当达到稳定的着色状态（各节点着色状态不再变化）后，算法终止。当算法终止后，若两图的着色情况不同，则我们认为它们「非同构」。如果两图着色情况相同，它们可能（但并不一定）是同构的。换句话说， WL 测试是图同构的必要非充分条件。有一些非同构的图在接受 WL 测试后得到的着色情况也是相同的，而在这种情况下 WL 测试就失效了，因此我们只能认为它们「可能同构」。下图展示了其中的一种可能性：