Invariant-Stratified Propagation for Expressive Graph Neural Networks

• URL: http://arxiv.org/abs/2603.01388v1
• Date: Mon, 02 Mar 2026 02:34:40 GMT
• Title: Invariant-Stratified Propagation for Expressive Graph Neural Networks
• Abstract summary: Graph Neural Networks (GNNs) face fundamental limitations in expressivity and capturing structural heterogeneity.<n>We introduce Invariant-Stratified Propagation (ISP), a framework comprising both a novel WL variant (ISP-WL) and its efficient neural network implementation (ISPGNN)<n>ISP stratifies nodes according to graph invariants, processing them in hierarchical strata that reveal structural distinctions invisible to 1-WL.<n>ISP quantifies differences in nodes' structural positions within higher-order patterns, distinguishing interactions where participants occupy different roles from those with uniform participation.
• Score: 9.192992900110983
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity [15.786915433105868]
  We show that a broad class of feedforward neural networks learn (have finite sample complexity) in the PAC model.<n>Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator.
  arXiv  Detail & Related papers  (2026-05-08T01:26:25Z)
• Layer Embedding Deep Fusion Graph Neural Network [25.30982656886312]
  Graph Neural Networks (GNNs) have demonstrated impressive performance in learning representations from graph-structured data.<n>We propose a novel framework named Layer Embedding Deep Fusion Graph Neural Network (LEDF-GNN)
  arXiv  Detail & Related papers  (2026-04-25T14:25:02Z)
• Graph Neural Networks with Similarity-Navigated Probabilistic Feature Copying [1.5229257192293202]
  We propose AxelGNN, a novel GNN architecture inspired by Axelrod's cultural dissemination model.<n>AxelGNN incorporates similarity-gated probabilistic interactions that adaptively promote convergence or divergence based on node similarity.<n>It consistently outperforms or matches state-of-the-art GNN methods across diverse graph structures with varying homophily-heterophily characteristics.
  arXiv  Detail & Related papers  (2025-09-23T14:39:09Z)
• Parameter-Free Structural-Diversity Message Passing for Graph Neural Networks [8.462209415744098]
  Graph Neural Networks (GNNs) have shown remarkable performance in structured data modeling tasks such as node classification.<n>This paper proposes a parameter-free graph neural network framework based on structural diversity.<n>The framework is inspired by structural diversity theory and designs a unified structural-diversity message passing mechanism.
  arXiv  Detail & Related papers  (2025-08-27T13:42:45Z)
• COMBINEX: A Unified Counterfactual Explainer for Graph Neural Networks via Node Feature and Structural Perturbations [6.894071825948456]
  We propose COMBINEX, a novel GNN explainer that generates counterfactual explanations for both node and graph classification tasks.<n>Unlike prior methods, which treat structural and feature-based changes independently, COMBINEX optimally balances modifications to edges and node features.<n>This unified approach ensures minimal yet effective changes required to flip a model's prediction, resulting in realistic and interpretable counterfactuals.
  arXiv  Detail & Related papers  (2025-02-14T12:17:24Z)
• Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation [66.40525136929398]
  Test-time adaptation (TTA) has attracted attention due to its ability to adapt a pre-trained model to a target domain, without re-accessing the source domain.<n>We propose Matcha, an innovative framework designed for effective and efficient adaptation to structure shifts in graphs.<n>We validate the effectiveness of Matcha on both synthetic and real-world datasets, demonstrating its robustness across various combinations of structure and attribute shifts.
  arXiv  Detail & Related papers  (2024-10-09T15:15:40Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Learning Invariant Representations of Graph Neural Networks via Cluster Generalization [58.68231635082891]
  Graph neural networks (GNNs) have become increasingly popular in modeling graph-structured data. In this paper, we experimentally find that the performance of GNNs drops significantly when the structure shift happens. We propose the Cluster Information Transfer (CIT) mechanism, which can learn invariant representations for GNNs.
  arXiv  Detail & Related papers  (2024-03-06T10:36:56Z)
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization [67.28453445927825]
  Graph Neural Networks (GNNs) are de facto solutions to structural data learning. Existing graph structure learning (GSL) frameworks still lack robustness and interpretability. This paper proposes a general GSL framework, SE-GSL, through structural entropy and the graph hierarchy abstracted in the encoding tree.
  arXiv  Detail & Related papers  (2023-03-17T05:20:24Z)
• ASGNN: Graph Neural Networks with Adaptive Structure [41.83813812538167]
  We propose a novel interpretable message passing scheme with adaptive structure (ASMP) to defend against adversarial attacks on graph structure. ASMP is adaptive in the sense that the message passing process in different layers is able to be carried out over dynamically adjusted graphs.
  arXiv  Detail & Related papers  (2022-10-03T15:10:40Z)
• Equivariant Subgraph Aggregation Networks [23.26140936226352]
  This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. While two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN. We provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture's expressive power.
  arXiv  Detail & Related papers  (2021-10-06T16:45:07Z)
• Dual-constrained Deep Semi-Supervised Coupled Factorization Network with Enriched Prior [80.5637175255349]
  We propose a new enriched prior based Dual-constrained Deep Semi-Supervised Coupled Factorization Network, called DS2CF-Net. To ex-tract hidden deep features, DS2CF-Net is modeled as a deep-structure and geometrical structure-constrained neural network. Our network can obtain state-of-the-art performance for representation learning and clustering.
  arXiv  Detail & Related papers  (2020-09-08T13:10:21Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.