Invariant-Stratified Propagation for Expressive Graph Neural Networks

Asela Hevapathige; Ahad N. Zehmakan; Asiri Wijesinghe; Saman Halgamuge

cs.LGMar 2, 2026

Invariant-Stratified Propagation for Expressive Graph Neural Networks

Authors: Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe, Saman Halgamuge

Organizations: Department of Mechanical Engineering, University of Melbourne, Melbourne, Australia · School of Computing, Australian National University, Canberra, Australia · Data61, CSIRO, Canberra, Australia

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.

Figures & tables

Figure 1. ISP-GNN architecture overview. (a) Input graph. (b) ISP coloring based on invariant values. (c) Layered propagation with WL and ISP aggregation at each layer. Triangle detail shows gap encoding for nodes with higher-layer neighbors. (d) Output embeddings for downstream tasks.

Figure 2. Mechanisms by which ISP-WL distinguishes graphs that 1-WL cannot: (A) Triangle Aggregation:

G_{1}

and

G_{2}

have identical degree sequences but different triangle structures. (B) Invariant Stratification: Triangle-free graphs

H_{1}

and

H_{2}

differ in structural properties captured by invariants (e.g., local girth). (C) Hierarchical Gap Encoding:

I_{1}

and

I_{2}

have identical triangle patterns but different invariant hierarchies (e.g., betweenness centrality).

Method	MUTAG	PTC_MR	BZR	DHFR	COX2	PROTEINS	D&D	IMDB-BINARY	IMDB-MULTI
GIN (2018)	92.8±5.9	65.6±6.5	91.1±3.4	84.9±4.0	88.9±2.3	78.8±4.1	82.2±3.7	78.1±3.5	54.6±3.0
ID-GNN (2021)	97.8±3.7	74.4±4.2	93.3±4.8	86.1±3.8	87.8±3.1	78.1±3.9	81.9±3.8	79.3±2.9	55.4±2.8
DropGIN (2021)	92.5±4.9	67.1±8.7	86.6±5.0	67.6±4.8	82.9±3.7	77.4±2.9	79.2±4.3	78.2±3.4	54.3±2.9
GSN (2022)	93.1±4.1	70.6±5.3	93.1±4.3	85.7±4.3	88.1±3.7	78.2±2.8	83.9±2.3	79.6±3.2	54.6±2.5
GraphSNN (2022)	94.7±1.9	70.6±3.1	91.1±3.0	85.7±3.8	86.3±3.3	78.4±2.7	81.8±3.7	78.5±2.3	55.3±3.0
GIN-AK+ (2022)	95.0±6.1	74.1±5.9	92.8±4.6	85.3±4.2	88.2±3.6	78.9±5.4	OOM	79.4±3.3	55.2±2.8

Table 1. Graph classification performance comparison across different datasets and methods. Results are reported as accuracy±standard deviation%. Best , second best , and third best results are highlighted. OOM indicates the out-of-memory error.

Method	Jazz			Cora-ML			Network Science			Power Grid
Method	IC	LT	SIS	IC	LT	SIS	IC	LT	SIS	IC	LT	SIS
GCN (2017)	0.233 ±.010	0.199 ±.006	0.344 ±.023	0.277 ±.007	0.255 ±.008	0.365 ±.065	0.270 ±.019	0.190 ±.012	0.180 ±.007	0.313 ±.024	0.335 ±.023	0.207 ±.001
GraphSAGE (2017)	0.201 ±.028	0.120 ±.004	0.301 ±.018	0.255 ±.010	0.203 ±.019	0.222 ±.051	0.241 ±.010	0.112 ±.005	0.102 ±.005	0.313 ±.024	0.341 ±.018	0.133 ±.001
GIN (2018)	0.148 ±.012	0.174 ±.029	0.344 ±.013	0.247 ±.001	0.305 ±.008	0.225 ±.019	0.277 ±.005	0.265 ±.006	0.140 ±.007	0.276 ±.001	0.471 ±.002	0.184 ±.029
GAT (2018)	0.342 ±.005	0.156 ±.100	0.288 ±.017	0.352 ±.004	0.192 ±.010	0.208 ±.008	0.274 ±.002	0.114 ±.008	0.123 ±.013	0.331 ±.002	0.280 ±.015	0.133 ±.001
APPNP (2018)	0.200 ±.006	0.124 ±.003	0.357 ±.059	0.265 ±.022	0.220 ±.031	0.321 ±.042	0.248 ±.006	0.084 ±.006	0.100 ±.012	0.290 ±.006	0.189 ±.011	0.132 ±.001

Table 2. Influence estimation performance comparison across different datasets and methods. Results are reported as MAE

\pm

standard deviation. Lower values indicate better performance. Best , second best , and third best results are highlighted.

Method	Cora ML	Citeseer	Pubmed	DBLP	Film	Cornell	Wisconsin	Texas
GraphSAGE (2017)	86.52 ± 1.32	76.04 ± 1.30	88.45 ± 0.50	86.16 ± 0.50	34.23 ± 0.99	75.95 ± 5.01	81.18 ± 5.56	82.43 ± 6.14
ISP-GraphSAGE †	87.23 ± 1.78	77.91 ± 0.92	88.51 ± 0.58	83.93 ± 0.60	35.89 ± 1.18	78.51 ± 5.98	87.38 ± 5.05	83.61 ± 6.96
$\Delta$ (%)	+0.98	+2.89	+0.07	-2.10	+6.31	+6.45	+7.64	+7.39
GCN (2018)	87.07 ± 1.21	76.68 ± 1.64	86.74 ± 0.47	83.93 ± 0.34	30.26 ± 0.79	55.14 ± 8.46	61.60 ± 7.00	60.00 ± 6.45
ISP-GCN †	87.29 ± 1.20	78.05 ± 1.70	89.01 ± 0.42	84.13 ± 0.53	35.10 ± 1.03	64.47 ± 8.94	66.75 ± 6.35	79.67 ± 3.53
$\Delta$ (%)	+0.25	+1.89	+2.62	+0.82	+15.99	+22.71	+8.36	+32.78

Table 3. Node classification performance comparison across different datasets and methods. Results are reported as accuracy ± standard deviation (%).

\Delta

represents the maximum percentage improvement of ISP variants over their respective baseline.

Panel of Figure 3 — Figure 3. Oversmoothing comparison

Figure 4. Runtime and performance on ogbg-molpcba dataset. (a) Per epoch time in seconds. (b) Average precision score. Results show ISP-GNN with different structural invariants.

(a) Overall Performance Method Accuracy (%) Time (ms) 1-WL 0.0 2.58 SPD-WL 20.8 7.08 ISP-WL

{}_{\text{Deg}}

23.3 4.35 ISP-WL

{}_{\text{BC}}

30.5 7.59 ISP-WL

{}_{\text{ANC}}

44.5 15.25 3-WL 67.5 101.42

(b) Regular Graph Performance

Table 5. Expressivity evaluation on BREC benchmark

ISP-WL Component	ISP-GNN Component
Hash-based color refinement	Neural aggregation + MLP
Multiset $\{\!\!\{c(u):u\in N(v)\}\!\!\}$	$\text{AGG}\{h_{u}:u\in N(v)\}$
Gap encoding $\delta(v,u,w)$	Gap features $d_{vuw}$
Layer assignment at $\phi(v)$	Gating $\gamma^{(k)}_{v}=\mathbb{I}[\phi(v)=k]$
Color space $\mathcal{C}^{(k)}$	Embedding space $\mathbb{R}^{d}$

Table 6. Correspondence between ISP-WL algorithm and ISP-GNN neural implementation.

Panel of Figure 5 — Figure 5. Gap encoding components capture complementary structural properties using degree as invariant. (a) $\delta_{1}$ differentiates hub vs. peripheral roles. (b) $\delta_{2}$ captures structural proximity to the closest neighbour. (c) $\delta_{3}$ measures neighbor similarity.

Invariant	Complexity	Description
Degree	$O(\|V\|)$	Number of neighbors
K-Core ( Malliaros et al., 2020 )	$O(\|V\|+\|E\|)$	Maximal core membership
Onion ( Hébert-Dufresne et al., 2016 )	$O(\|V\|+\|E\|)$	Hierarchical k-core layers
Clustering Coefficient ( Li et al., 2017 )	$O(d\|E\|)$	Local triangle density ratio
Average Neighborhood Clustering ( Wilson and Din, 2018 )	$O(d^{2}\|E\|)$	Mean clustering coefficient of neighbors
K-Truss ( Wu et al., 2018 )	$O(\|E\|^{1.5})$	Triangle-support decomposition

Table 7. Graph invariants used in our experiments and their computational complexities on sparse graphs with bounded degeneracy.

Figure 6. Graphs $G_{1}$ and $G_{2}$ with identical degree sequences but different triangle structures.

Dataset	# Nodes	# Edges	# Features	# Classes
Cora ML	2,995	8,416	2,879	7
Citeseer	3,327	4,732	3,703	6
Pubmed	19,717	44,338	500	3
DBLP	17,716	105,734	1,639	4
Film	7,600	33,544	932	5
Amazon Photo	7,650	119,081	745	8

Table 8. Dataset statistics for node classification.

Dataset	# Nodes	# Edges
Jazz	198	2,742
Cora-ML	2,810	7,981
Network Science	1,565	13,532
Power Grid	4,941	6,594

Table 9. Dataset statistics for influence estimation.

Dataset	Domain	# Graphs	Avg # Nodes	Avg # Edges	# Classes
MUTAG	Molecular	188	17.93	19.79	2
PTC_MR	Molecular	344	14.29	14.69	2
BZR	Molecular	405	35.75	38.36	2
DHFR	Molecular	467	42.43	44.54	2
COX2	Molecular	467	41.22	43.45	2
PROTEINS	Bioinformatics	1,113	39.06	72.82	2

Table 10. Dataset statistics for graph classification.

Method	Node Classification		Graph Classification
Method	Amazon Photo	Amazon-Ratings	ogbg-moltox21	Reddit-Binary
Baseline	89.30 $\pm$ 0.82	37.99 $\pm$ 0.61	74.9 $\pm$ 0.5	92.2 $\pm$ 2.3
Degree	93.12 $\pm$ 0.46	47.5 $\pm$ 1.03	75.1 $\pm$ 0.6	92.8 $\pm$ 2.2
K-core	93.97 $\pm$ 0.46	48.43 $\pm$ 1.21	75.1 $\pm$ 0.8	92.5 $\pm$ 2.1
Onion	93.93 $\pm$ 0.35	44.95 $\pm$ 0.54	75.6 $\pm$ 0.7	92.4 $\pm$ 2.7
Clustering Coefficient	93.23 $\pm$ 0.31	46.27 $\pm$ 0.78	74.8 $\pm$ 0.6	93.0 $\pm$ 2.7

Table 11. Node and graph classification performance with different structural invariants. Values show accuracy (%) with standard deviation. Best results are highlighted in bold .

Figure 7. Structural metrics comparison across datasets.

Hyperparameter	Search Space
Number of layers	$\{2,3,4,5,6\}$
Temperature ( $\beta$ )	$\{0.5,1.0,1.5,2.0\}$
Number of Strata ( $S$ )	$\{4,6,8\}$
Dropout rate	$\{0.0,0.1,0.2,0.5,0.6,0.9\}$
Learning rate	$\{0.005,0.009,0.01,0.1\}$
Batch size	$\{32,64,100\}$

Table 12. Hyperparameter search space for ISP-GNN variants

Package	Version
Python	3.11.5
PyTorch	2.3.1
PyTorch Geometric	2.7.0
torch-cluster	1.6.3
torch-scatter	2.0.9
torch-sparse	0.6.18

Table 13. Software environment specifications

Figure 8. Structural metrics comparison across datasets.

Panel of Figure 9 — Figure 9. t-SNE visualization of ISP-GNN embeddings on Cora-ML. The learnable invariant produces the most compact and well-separated clusters (silhouette: 0.631), outperforming predefined invariants (silhouette: 0.558–0.619). This demonstrates that learnable stratification automatically discovers task-adaptive structural patterns aligned with semantic categories.

Figure 10. Ablation study on hierarchical gap encoding components for graph classification. Results demonstrate the complementary nature of $\delta_{1}$ , $\delta_{2}$ , and $\delta_{3}$ . Progressive performance improvements from individual components through pairs to full encoding validate the necessity of all three gap features.

Motif Type	MUTAG	PTC_MR	IMDB-MULTI
GIN (Baseline)	$92.8\pm 5.9$	$65.6\pm 6.5$	$54.6\pm 3.0$
4-clique	$95.2\pm 4.4$	$72.7\pm 5.6$	$55.2\pm 2.8$
4-cycle	$94.7\pm 4.0$	$71.0\pm 7.5$	$55.0\pm 3.2$
Diamond	$94.6\pm 4.1$	$73.4\pm 7.7$	$55.4\pm 2.9$
5-clique	$95.3\pm 5.5$	$72.2\pm 7.7$	$55.3\pm 3.0$
6-cycle	$94.7\pm 5.0$	$74.3\pm 6.6$	$54.9\pm 3.1$

Table 14. Ablation study on motif types. Results show mean accuracy

\pm

standard deviation (%) for graph classification. Best results are highlighted in bold . Note that the degree is used as the invariant.

Panel of Figure 11 — Figure 11. t-SNE visualization of ISP-GNN embeddings on Cora-ML. The learnable invariant produces the most compact and well-separated clusters (silhouette: 0.631), outperforming predefined invariants (silhouette: 0.558–0.619). This demonstrates that learnable stratification automatically discovers task-adaptive structural patterns aligned with semantic categories.

Figure 12. Hyperparameter sensitivity analysis. (a) Effect of number of strata $S$ (b) Effect of temperature $\beta$ .

Figure 13. ISP-WL computational overhead on synthetic BA graphs. (a) Time per iteration scales linearly with graph size for all variants. (b) Overhead ratios stabilize at large graphs, with preprocessing costs becoming better amortized at scale.

Figure 14. Preprocessing cost analysis (log scale). (a) Invariant computation time shows Degree ( $O(|V|)$ ) is nearly instantaneous, K-Core/Onion ( $O(|E|)$ ) remain efficient, while K-Truss ( $O(|E|^{1.5})$ ) is expensive but amortizes well at scale. (b) Amortized cost per iteration shows preprocessing contribution decreases relative to the iteration cost as the graphs grow.

Figure 15. Triangle enumeration scalability on BA graphs. (a) Sublinear triangle growth confirms bounded degeneracy typical of real-world networks. (b) Linear enumeration time validates the complexity $T=O(d|E|)$ . (c) Quadratic explosion at high degrees demonstrates why bounded degeneracy is critical.

Figure 16. Coloring refinement comparison of 1-WL and ISP-WL. ISP-WL with different invariants achieves 17-27% more colours than standard 1-WL, providing higher discriminative power.

Figure 17. Pairwise complementarity between invariants measured as percentage of nodes receiving different final colors. High values (red) indicate orthogonal structural information, validating that different invariants capture distinct graph properties.

Figure 18. Iterative color refinement across variants. K-Truss converges fastest, while other finer-grained invariants, such as degree and onion, require more iterations.

Explore similar work

May 25, 2026

Invariant-Based Weight Sharing for Message Passing

Message-passing neural networks (MPNNs) are a powerful framework for learning representations of graph-structured domains. However, weights in MPNNs act on features only, limiting their ability to capture structural patterns. We introduce a novel structure-aware weight sharing principle that explicitly incorporates information inherent to the graph structure. Weights are indexed directly by user-chosen graph invariants, i.e., functions preserved under node permutations, enabling systematic reuse across structurally equivalent subgraphs. We present ShareGNNs, which instantiate this principle within a simple encoder-decoder architecture, resulting in an MPNN with learnable adjacency and transformer-like connectivity. We show that their expressivity is at least as strong as the discriminative power of the chosen invariants, providing explicit control over the model complexity. Experiments on synthetic and real-world data, as well as subgraph counting tasks, demonstrate consistent improvements over standard MPNNs, competitive expressivity beyond the 1-WL test, and scalability to large datasets.

Florian Seiffarth

University of Bonn, Bonn, Germany · Lamarr Institute for Machine Learning and Artificial Intelligence, Bonn, Germany

Graph Neural Networks GNN Expressivity Message Passing Neural Networks

Ask PDF

May 7, 2026

Full-Spectrum Graph Neural Networks: Expressive and Scalable

It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNNs (FSpecGNNs), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering from two perspectives: (1) it lifts signals from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNNs, and prove that FSpecGNNs can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.

Xiaohan Wang, Deyu Bo, Longlong Li +1

Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.

Graph Neural Networks GNN Expressivity Spectral Methods Spectral Graph Convolution

Ask PDF

Feb 18, 2026

Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning

Graph Neural Networks (GNNs) have become essential in high-stakes domains such as drug discovery, yet their black-box nature remains a significant barrier to trustworthiness. While self-explainable GNNs attempt to bridge this gap, they often rely on standard message-passing backbones that inherit fundamental limitations, including the 1-Weisfeiler-Lehman (1-WL) expressivity barrier and a lack of fine-grained interpretability. To address these challenges, we propose SymGraph, a symbolic framework designed to transcend these constraints. By replacing continuous message passing with discrete structural hashing and topological role-based aggregation, our architecture theoretically surpasses the 1-WL barrier, achieving superior expressiveness without the overhead of differentiable optimization. Extensive empirical evaluations demonstrate that SymGraph achieves state-of-the-art performance, outperforming existing self-explainable GNNs. Notably, SymGraph delivers 10x to 100x speedups in training time using only CPU execution. Furthermore, SymGraph generates rules with superior semantic granularity compared to existing rule-based methods, offering great potential for scientific discovery and explainable AI.

Chuqin Geng, Li Zhang, Haolin Ye +5

School of Computer Science, McGill University, Montreal, Canada · Department of Computer Science, University of Toronto, Toronto, Canada

Graph Representation Learning GNN Explainability GNN Expressivity

Ask PDF