摘要
尽管图神经网络（Graph Neural Networks, GNNs）在图学习任务中取得了显著成果，但传统GNNs由于其信息传播机制与一阶Weisfeiler-Leman图同构测试算法（1-WL）具有一致性，难以突破1-WL的表达能力上限。基于子图相较于原图更易于区分这一观察，我们提出了一种新型神经网络框架——子结构感知图神经网络（Substructure Aware Graph Neural Networks, SAGNN），以解决上述问题。我们首先引入一种称为“Cut子图”的结构，该子图可通过在原图上连续且有选择性地移除边而获得。随后，我们将随机游走编码范式拓展至根节点在子图上的返回概率，用以捕捉图的结构信息，并将其作为节点特征输入，从而显著提升GNN的表达能力。理论上，我们证明了所提出的框架在表达能力上超越了1-WL，且在结构感知方面具有显著优势。大量实验结果验证了该框架的有效性：在多个经过充分验证的图学习任务中，SAGNN均取得了当前最优性能；即使在传统GNN在三阶Weisfeiler-Leman测试（3-WL）中失效的图结构上，本框架仍表现出卓越的性能。具体而言，与基础模型相比，本框架最高可实现83%的性能提升；相较于此前的最先进方法，性能提升亦达32%。