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

Invariant-Based Weight Sharing for Message Passing
May 25, 2026Florian SeiffarthGraph Neural Networks GNN Expressivity
University of Bonn, Bonn, Germany · Lamarr Institute for Machine Learning and Artificial Intelligence, Bonn, Germany
Full-Spectrum Graph Neural Networks: Expressive and Scalable
May 7, 2026Xiaohan Wang, Deyu Bo, Longlong Li +1Graph Neural Networks GNN Expressivity
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.
Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning
Feb 18, 2026Chuqin Geng, Li Zhang, Haolin Ye +5Graph Representation Learning GNN Explainability
School of Computer Science, McGill University, Montreal, Canada · Department of Computer Science, University of Toronto, Toronto, Canada

May 25, 2026J/K move · Enter open · S save

Invariant-Based Weight Sharing for Message Passing

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Invariant-Based Weight Sharing for Message Passing

Full-Spectrum Graph Neural Networks: Expressive and Scalable

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