通过子图同构计数提升图神经网络的表达能力

尽管图神经网络（Graph Neural Networks, GNNs）在诸多应用中取得了显著成果，但近期研究揭示了其在捕捉底层图结构方面存在重要缺陷。已有研究表明，标准GNN的表达能力受限于Weisfeiler-Leman（WL）图同构测试，因而继承了其固有的局限性，例如无法检测或计数图中的子结构。然而，在网络科学与生物信息学等领域的大量实证研究表明，图的子结构往往与下游任务密切相关。为此，我们提出了“图子结构网络”（Graph Substructure Networks, GSN），一种基于子结构编码的拓扑感知消息传递机制。我们从理论上分析了该架构的表达能力，证明其严格超越WL测试，并给出了实现通用性的充分条件。尤为重要的是，我们的方法并不遵循WL层次结构，从而在保持标准GNN所具备的局部性与线性网络复杂度等优良特性的同时，仍能有效区分复杂的图同构实例。我们在图分类与回归任务上进行了广泛的实验评估，在包括分子图和社会网络在内的多种真实世界场景中均取得了当前最优性能。相关代码已公开发布于：https://github.com/gbouritsas/graph-substructure-networks。