摘要

图神经网络（Graph Neural Networks, GNNs）近年来已成为处理图结构数据学习任务的标准方法。先前的研究揭示了GNN的潜力，同时也指出了其局限性。遗憾的是，已有研究表明，标准GNN在表达能力上存在瓶颈：其区分非同构图的能力不超过一维Weisfeiler-Leman（1-WL）算法。本文提出了一种新型模型——路径神经网络（Path Neural Networks, PathNNs），该模型通过聚合从节点出发的路径来更新节点表示。我们推导出三种不同的PathNN变体：分别聚合单条最短路径、所有最短路径以及长度不超过K的所有简单路径。我们证明，其中两种变体在区分图结构的能力上严格强于1-WL算法，并通过实验验证了理论结果。实验表明，PathNN能够区分1-WL无法区分的非同构图对，而最具表达力的PathNN变体甚至可区分3-WL也无法区分的图。此外，我们在图分类与图回归数据集上对不同PathNN变体进行了评估，结果表明，在大多数情况下，其性能优于现有基线方法。