mlsanityData to 7 Oct 2026

Invariant-Stratified Propagation for Expressive Graph Neural Networks

arXiv 2603.01388 ↗First posted 2 Mar 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 42 of its 85 references that are in the map. First posted on arXiv 2 Mar 2026.

Builds on

42 of 85 references.

References · 42

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  9. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  12. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
30 more
  1. 2019Graph U-Netscited by 489
  2. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  3. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
  4. 2019Position-aware Graph Neural Networkscited by 203
  5. 2021Identity-aware Graph Neural Networkscited by 197
  6. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  7. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  8. 2022A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodalcited by 106
  9. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  10. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  11. 2021Knowledge Graph Reasoning with Relational Digraphcited by 91
  12. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  13. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 88
  14. 2021Reconstruction for Powerful Graph Representationscited by 65
  15. 2022Ordered Subgraph Aggregation Networkscited by 57
  16. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  17. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  18. 2023Deep Graph Representation Learning and Optimization for Influence Maximizationcited by 27
  19. 2023Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphscited by 25
  20. 2022A Practical, Progressively-Expressive GNNcited by 20
  21. 2020GraphReach: Position-Aware Graph Neural Network using Reachability Estimationscited by 14
  22. 2022Graph Ordering Attention Networkscited by 8
  23. 2025Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvaturecited by 8
  24. 2023Union Subgraph Neural Networkscited by 6
  25. 2015Multi-scale structure and topological anomaly detection via a new network statistic: The onion decompositioncited by 4
  26. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  27. 2024DeepSN: A Sheaf Neural Framework for Influence Maximizationcited by 4
  28. 2025UniGO: A Unified Graph Neural Network for Modeling Opinion Dynamics on Graphscited by 3
  29. 2025Understanding and Improving Laplacian Positional Encodings For Temporal GNNscited by 3
  30. 2014Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphscited by 2

Built on by

Not cited yet.