摘要

图神经网络（GNNs）是一种有效的图表示学习框架。GNNs 采用邻域聚合方案，通过递归地聚合和转换节点的邻域节点表示向量来计算该节点的表示向量。许多 GNN 变体已被提出，并在节点分类和图分类任务中取得了最先进的结果。然而，尽管 GNNs 在图表示学习领域带来了革命性的变化，但对其表示性质和局限性的理解仍然有限。本文提出了一种理论框架，用于分析 GNNs 捕捉不同图结构的表达能力。我们的研究结果表征了流行的 GNN 变体（如图卷积网络和 GraphSAGE）的判别能力，并表明它们无法学会区分某些简单的图结构。随后，我们开发了一种简单架构，该架构在 GNN 类中具有最高的表达能力，并且其威力等同于 Weisfeiler-Lehman 图同构测试。我们在多个图分类基准数据集上对我们的理论发现进行了实证验证，并展示了我们的模型达到了最先进的性能。