Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions?

Asela Hevapathige, Qing Wang

Abstract

Graph Neural Networks (GNNs) have paved the way for being a cornerstone in graph-related learning tasks. Yet, the ability of GNNs to capture structural interactions within graphs remains under-explored. In this work, we address this gap by drawing on the insight that permutation invariant graph partitioning enables a powerful way of exploring structural interactions. We establish theoretical connections between permutation invariant graph partitioning and graph isomorphism, and then propose Graph Partitioning Neural Networks (GPNNs), a novel architecture that efficiently enhances the expressive power of GNNs in learning structural interactions. We analyze how partitioning schemes and structural interactions contribute to GNN expressivity and their trade-offs with complexity. Empirically, we demonstrate that GPNNs outperform existing GNN models in capturing structural interactions across diverse graph benchmark tasks.

Benchmark Results

Tested on 5 datasets 4 baseline values reported too low

Tables show presented results in global context (best 3 papers + GCN + MLP).

TU Dortmund

MUTAG

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9910 ±0.0030	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	ID-GNN+BEC Hyb global	0.9830 ±0.0360	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
3	SupCosine Hyb global	0.9830 ±0.0250	Supervised Contrastive Learning with Structure Inference for Graph Classification
18	KP-GIN GNN baseline	0.9560 ±0.0440	This paper
22	GIN-AK+ GNN baseline actual #22 vs paper #22	0.9500 ±0.0610	actual #22 vs paper #22 paper 0.9500 ±0.0610 prev best: Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries (NeurIPS 2022) Improvement within reported uncertainty; not highlighted. paper 0.9500 ±0.0610 Δ at pub 0.0370
24	GraphSNN GNN baseline	0.9470 ±0.0190	This paper
26	CIN GNN baseline actual #26 vs paper #48 22 places worse	0.9440 ±0.0370 best reported	actual #26 vs paper #48 22 places worse paper 0.9270 ±0.0610 best at pub: CIN++: Enhancing Topological Message Passing (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.9270 ±0.0610 Δ at pub 0.0170
39	GIN GNN baseline actual #39 vs paper #47 8 places worse	0.9330 ±0.0290 best reported	actual #39 vs paper #47 8 places worse paper 0.9280 ±0.0590 best at pub: ProtGNN: Towards Self-Explaining Graph Neural Networks (AAAI 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.9280 ±0.0590 Δ at pub 0.0050
63	GCN GNN global	0.9220 ±0.0440	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
73	ESAN GNN baseline actual #73 vs paper #111 38 places worse	0.9200 ±0.0500 best reported	actual #73 vs paper #111 38 places worse paper 0.9100 ±0.0710 best at pub: Asynchronous Neural Networks for Learning in Graphs (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.9100 ±0.0710 Δ at pub 0.0100
140	PPGN GNN baseline actual #140 vs paper #142 2 places worse	0.9060 ±0.0870 best reported	actual #140 vs paper #142 2 places worse paper 0.9055 ±0.0870 best at pub: DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks (NeurIPS 2021) best today: The Expressive Power of Graph Neural Networks: A Survey (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.9055 ±0.0870 Δ at pub 0.0005 Δ today 0.0005
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗

PROTEINS

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9410 ±0.0330	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	GRDL GNN global	0.8260 ±0.0120	Graph Classification via Reference Distribution Learning: Theory and Practice
3	GMN code ↗ Hyb global	0.8225	Memory-Based Graph Networks code ↗
12	CIN GNN baseline actual #12 vs paper #83 71 places worse	0.8050 ±0.0390 best reported	actual #12 vs paper #83 71 places worse paper 0.7700 ±0.0430 best at pub: CIN++: Enhancing Topological Message Passing (2023) best today: Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7700 ±0.0430 Δ at pub 0.0350 Δ today 0.0350
23	KP-GIN GNN baseline	0.7950 ±0.0440	This paper
30	GIN-AK+ GNN baseline actual #30 vs paper #30	0.7890 ±0.0540	actual #30 vs paper #30 paper 0.7890 ±0.0540 prev best: Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability (2023) Improvement within reported uncertainty; not highlighted. paper 0.7890 ±0.0540 Δ at pub 0.0370
32	GIN GNN baseline actual #32 vs paper #32	0.7880 ±0.0410	actual #32 vs paper #32 paper 0.7880 ±0.0410 prev best: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) Improvement within reported uncertainty; not highlighted. paper 0.7880 ±0.0410 Δ at pub 0.0180
39	GraphSNN GNN baseline actual #39 vs paper #39	0.7842 ±0.0270	actual #39 vs paper #39 paper 0.7842 ±0.0270 prev best: The Expressive Power of Graph Neural Networks: A Survey (2023) Improvement within reported uncertainty; not highlighted. paper 0.7842 ±0.0270 Δ at pub 0.0002
67	SAGE GNN global	0.7726 ±0.0228	Semi-Supervised Hierarchical Graph Classification
73	PPGN GNN baseline	0.7720 ±0.0470	This paper
78	ESAN GNN baseline actual #78 vs paper #78	0.7710 ±0.0460	actual #78 vs paper #78 paper 0.7710 ±0.0460 prev best: The Expressive Power of Graph Neural Networks: A Survey (2023) Improvement within reported uncertainty; not highlighted. paper 0.7710 ±0.0460 Δ at pub 0.0120
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors

OGB

ogbg-molhiv

Global leaderboard →

#	Model	ROC-AUC ↑	Paper
1	Multi-RF Fusion with Multi-GNN Blending global	0.8476 ±0.0002	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
2	HyperFusion global	0.8475 ±0.0003	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
3	PAS+FPs global	0.8420 ±0.0015	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
8	CIN GNN baseline	0.8094 ±0.0060	This paper
9	GatedGCN GNN 2.8M global	0.8090 ±0.0160	Deep Prompt Tuning for Graph Transformers
38	GIN-AK+ GNN baseline	0.7961 ±0.0110	This paper
80	GraphSNN GNN baseline actual #80 vs paper #80	0.7851 ±0.0170	actual #80 vs paper #80 paper 0.7851 ±0.0170 prev best: Union Subgraph Neural Networks (AAAI 2023) paper 0.7851 ±0.0170 Δ at pub 0.0546
101	ESAN GNN baseline actual #101 vs paper #180 79 places worse	0.7800 ±0.0142 best reported	actual #101 vs paper #180 79 places worse paper 0.7643 ±0.0210 best at pub: Agent-based Graph Neural Networks (ICLR 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7643 ±0.0210 Δ at pub 0.0157
109	GIN GNN baseline actual #109 vs paper #221 112 places worse	0.7780 ±0.0182 best reported	actual #109 vs paper #221 112 places worse paper 0.7558 ±0.0140 best at pub: GRPE: Relative Positional Encoding for Graph Transformer (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7558 ±0.0140 Δ at pub 0.0222
160	GraphSAGE code ↗ GNN global	0.7690 ±0.0136	SoGCN: Second-Order Graph Convolutional Networks code ↗

Heterophilic Graphs

Texas

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	P^2GNN Hyb global	0.9672 ±0.0147	$P^2$GNN: Two Prototype Sets to boost GNN Performance
2	DoG code ↗ ext data GNN global	0.9660 ±0.0210	Diffusion on Graph: Augmentation of Graph Structure for Node Classification code ↗
3	GPF-plus code ↗ ext data GNN global	0.9583 ±0.0419	ProG: A Graph Prompt Learning Benchmark code ↗
34	MLP Trad global	0.9230 ±0.0070	Design your own universe: a physics-informed agnostic method for enhancing graph neural networks
53	GraphSAGE GNN baseline actual #53 vs paper #212 159 places worse	0.9000 ±0.0365 best reported	actual #53 vs paper #212 159 places worse paper 0.8160 ±0.0230 best at pub: A Quasi-Wasserstein Loss for Learning Graph Neural Networks (WWW 2023) best today: Graph Neural Networks Need Cluster-Normalize-Activate Modules (NeurIPS 2024) paper 0.8160 ±0.0230 Δ at pub 0.0840 Δ today 0.0840
189	SAGE GNN global	0.8269	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
211	GAT GNN baseline actual #211 vs paper #478 267 places worse	0.8162 ±0.0645 best reported	actual #211 vs paper #478 267 places worse paper 0.6200 ±0.0220 best at pub: A Quasi-Wasserstein Loss for Learning Graph Neural Networks (WWW 2023) best today: Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (2025) paper 0.6200 ±0.0220 Δ at pub 0.1800 Δ today 0.1962
257	GCN GNN baseline actual #257 vs paper #575 318 places worse	0.7933 ±0.0447 best reported	actual #257 vs paper #575 318 places worse paper 0.5310 ±0.2160 best at pub: Restructuring Graphs for Higher Homophily via Adaptive Spectral Clustering (AAAI 2022) best today: Graph Wave Networks (WWW 2025) Difference within reported uncertainty; not counted as underperformance. paper 0.5310 ±0.2160 Δ at pub 0.2530 Δ today 0.2623
326	GIN GNN baseline actual #326 vs paper #480 154 places worse	0.7460 ±0.0080 best reported	actual #326 vs paper #480 154 places worse paper 0.6160 ±0.0110 best at pub: Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond (2023) best today: Design your own universe: a physics-informed agnostic method for enhancing graph neural networks (2024) paper 0.6160 ±0.0110 Δ at pub 0.1300 Δ today 0.1300

MoleculeNet

Tox21

Global leaderboard →

Default metric is ROC-AUC. The paper reports 6 values on ROC-AUC and 3 values on ROC .

#	Model	ROC-AUC ↑ default	ROC ↑	Paper
1	HIMP Hyb global	0.8740 ± 0.0050	—	ROC — Graph convolutions that can finally model local structure
2	GINE w/ VN GNN global	0.8720 ± 0.0030	—	ROC — Graph convolutions that can finally model local structure
3	NaiveGINe+ K=3 w/ VN GNN global	0.8700 ± 0.0040	—	ROC — Graph convolutions that can finally model local structure
14	GCN GNN global	0.8400 ± 0.0040	—	ROC — Graph convolutions that can finally model local structure
24	GIN GNN baseline	0.8290 ±0.0069 best reported	0.7491 ± 0.0050	ROC 0.7491 ± 0.0050 paper 0.6341 ±0.0070 best at pub: Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling (2019) paper 0.6341 ±0.0070 Δ at pub 0.1949
207	GraphSNN GNN baseline	—	0.7545 ± 0.0110	ROC 0.7545 ± 0.0110 This paper
228	ESAN GNN baseline	—	0.7512 ± 0.0050	ROC 0.7512 ± 0.0050 This paper
319	λ_degree-GPNN GNN baseline	0.6528 ± 0.0050	—	ROC — This paper
323	λ_core-degree-GPNN GNN baseline	0.6470 ± 0.0040	—	ROC — This paper
326	λ_core-GPNN GNN baseline	0.6399 ± 0.0040	—	ROC — This paper
327	λ_triangle-GPNN GNN baseline	0.6399 ± 0.0040	—	ROC — This paper
330	λ_core-onion-GPNN GNN baseline	0.6291 ± 0.0080	—	ROC — This paper

SOTA performance (not significantly different from the best) Baseline / comparison (this paper) Global context (other papers) Best at pub — reported result worse than the best known when published (best reported in green) Best at pub — reported value improved over the best known when published