arXiv:2603.01388cs.LGstat.ML2026-03KDD

提出ISP框架,让GNN更懂图中节点的结构角色差异。

Invariant-Stratified Propagation for Expressive Graph Neural Networks

  • 按图不变量分层处理节点,捕捉高阶结构差异
  • 理论证明超越1-WL表达能力,且抗过平滑
  • 适合需要精细结构理解的任务如节点分类

图神经网络(GNN)在表达能力和捕捉结构异质性方面存在根本局限。标准消息传递架构受限于1维魏斯费勒-莱曼测试(1-WL),无法区分超出度序列的图结构,且对邻居信息进行均匀聚合,难以捕捉节点在高阶模式中的不同结构位置。尽管已有方法提升表达能力,但计算成本过高,且缺乏统一框架灵活编码多样结构属性。为此,我们提出不变量分层传播(ISP)框架,包含新型魏斯费勒-莱曼变体(ISP-WL)及其高效神经网络实现(ISPGNN)。ISP根据图不变量对节点分层,在层次化结构中揭示1-WL无法察觉的结构差异。通过分层异质性编码,ISP量化了节点在高阶模式中结构位置的差异,能区分角色不同的交互与均质参与。我们提供形式化理论分析,证明其超越1-WL的表达能力、收敛性保证及固有的抗过平滑特性。在图分类、节点分类和影响力估计任务上的大量实验表明,该方法持续优于标准架构和最先进的表达性基线。

原文摘要 · Abstract (English)

Graph Neural Networks (GNNs) face fundamental limitations in expressivity and capturing structural heterogeneity. Standard message-passing architectures are constrained by the 1-dimensional Weisfeiler-Leman (1-WL) test, unable to distinguish graphs beyond degree sequences, and aggregate information uniformly from neighbors, failing to capture how nodes occupy different structural positions within higher-order patterns. While methods exist to achieve higher expressivity, they incur prohibitive computational costs and lack unified frameworks for flexibly encoding diverse structural properties. To address these limitations, we introduce Invariant-Stratified Propagation (ISP), a framework comprising both a novel WL variant (ISP-WL) and its efficient neural network implementation (ISPGNN). ISP stratifies nodes according to graph invariants, processing them in hierarchical strata that reveal structural distinctions invisible to 1-WL. Through hierarchical structural heterogeneity encoding, ISP quantifies differences in nodes' structural positions within higher-order patterns, distinguishing interactions where participants occupy different roles from those with uniform participation. We provide formal theoretical analysis establishing enhanced expressivity beyond 1-WL, convergence guarantees, and inherent resistance to oversmoothing. Extensive experiments across graph classification, node classification, and influence estimation demonstrate consistent improvements over standard architectures and state-of-the-art expressive baselines.

图神经网络结构表达节点分类

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。