
消息传递神经网络(Message Passing Neural Networks, MPNNs)是图神经网络(Graph Neural Networks, GNNs)中的一种常见类型,其核心机制是通过递归地聚合节点直接邻居的信息(即“消息”)来更新每个节点的表示,这一过程在结构上类似于星型模式。MPNNs 因其高效性和可扩展性而受到广泛关注,但其表达能力受限于一阶 Weisfeiler-Lehman 同构检验(1-WL),存在理论上的表达上限。为突破这一限制,已有研究提出了一些表达能力更强的模型,但往往以牺牲可扩展性甚至泛化性能为代价。本文介于上述两种范式之间:我们提出一个通用框架,能够在几乎不增加可扩展性开销的前提下,显著提升任意 MPNN 的表达能力,并大幅改善其实际性能。这一目标的实现依赖于对 MPNN 中局部聚合机制的扩展——从传统的星型邻居结构推广至更一般的子图结构(例如 k-egonets)。在本框架中,每个节点的表示不再仅基于其直接邻居的编码,而是基于其周围诱导子图的完整编码,从而捕获更丰富的局部拓扑信息。为兼顾效率与表达能力,我们选择使用 GNN(主要为 MPNN)作为子图编码器,构建了一个通用的、可作为“包装器”(wrapper)集成于任意 GNN 之上的框架。该方法被命名为 GNN-AK(GNN As Kernel),因其架构类似于卷积神经网络,但将传统卷积核替换为 GNN 模块,从而实现对局部结构的深度建模。理论上,我们证明了所提框架严格强于 1-WL 与 2-WL,且表达能力不低于 3-WL,表明其具备更强的图同构判别能力。此外,我们设计了高效的子图采样策略,在显著降低内存占用并提升计算速度的同时,保持了优异的性能表现。在多个经典的图机器学习任务上,本方法取得了显著的性能突破,大幅刷新了现有最先进水平:在 ZINC 数据集上达到 0.08 的平均绝对误差(MAE);在 CIFAR10 图分类任务上取得 74.79% 的准确率;在 PATTERN 数据集上达到 86.887% 的准确率,展现出卓越的实用性与泛化能力。