摘要

图神经网络（GNN）在图分类任务中的成功与Weisfeiler-Lehman（1-WL）算法密切相关。通过迭代地将邻近节点的特征聚合到中心节点，1-WL和GNN都能获得一个编码了以该中心节点为根的子树的节点表示。这些以节点为根的子树表示随后被池化成一个单一的表示，用于描述整个图。然而，以节点为根的子树在表示非树形图时表达能力有限。为了解决这一问题，我们提出了嵌套图神经网络（NGNN）。NGNN使用以节点为根的子图而非子树来表示图，因此两个共享许多相同子图（而非子树）的图往往具有相似的表示。关键在于使每个节点表示不仅编码其周围的子树，还能编码其周围的子图。为了实现这一点，NGNN提取每个节点周围的局部子图，并应用基础GNN来学习每个子图的表示。然后通过对这些子图表示进行池化操作来获得整个图的表示。我们提供了严格的理论分析，证明了NGNN比1-WL算法更强大。特别是，我们证明了NGNN几乎可以区分所有的r-正则图（r-regular graphs），而1-WL总是失败。此外，与其他更强大的GNN不同，NGNN仅引入了相对于标准GNN常数级别的更高时间复杂度。NGNN是一个即插即用框架，可以与各种基础GNN结合使用。我们在多个基准数据集上测试了不同基础GNN与NGNN结合的效果。结果表明，NGNN统一提升了它们的性能，并在所有数据集上表现出高度竞争力。