摘要

最近，Weisfeiler-Lehman (WL) 图同构测试被用于衡量图神经网络 (GNN) 的表达能力。研究表明，流行的基于消息传递的 GNN 无法区分通过 1-WL 测试也无法区分的图（Morris 等，2018；Xu 等，2019）。不幸的是，许多简单的图实例都无法通过 1-WL 测试进行区分。为了寻找更具表达力的图学习模型，我们基于近期提出的 k 阶不变性和等变图神经网络（Maron 等，2019a,b），并提出了两个结果：首先，我们证明了这种 k 阶网络在区分非同构图方面的能力与 k-WL 测试相当，而后者对于 k>2 的情况已被证明比 1-WL 测试更强。这使得这些模型严格优于基于消息传递的模型。然而，这些模型更高的表达能力也带来了处理高阶张量的计算成本。其次，我们的目标是构建一个具有更强表达能力、简单且可扩展的模型。我们证明了一个仅包含缩放恒等算子的简化 2 阶网络，在加入单个二次操作（矩阵乘法）后，可以达到 3-WL 的表达能力。换句话说，我们建议了一种简单的模型，该模型交替应用标准多层感知机 (MLP) 对特征维度进行处理和矩阵乘法操作。我们通过在流行的图分类和回归任务上展示最先进的结果来验证这一模型。据我们所知，这是第一个具有保证的 3-WL 表达能力且严格优于基于消息传递模型的实际不变性/等变性模型。