Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing

Diaaeldin Taha, James Chapman, Marzieh Eidi, Karel Devriendt, Guido Montúfar

Main figure for Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing

Abstract

Topological deep learning (TDL) has emerged as a powerful tool for modeling higher-order interactions in relational data. However, phenomena such as oversquashing in topological message-passing remain understudied and lack theoretical analysis. We propose a unifying axiomatic framework that bridges graph and topological message-passing by viewing simplicial and cellular complexes and their message-passing schemes through the lens of relational structures. This approach extends graph-theoretic results and algorithms to higher-order structures, facilitating the analysis and mitigation of oversquashing in topological message-passing networks. Through theoretical analysis and empirical studies on simplicial networks, we demonstrate the potential of this framework to advance TDL.

Benchmark Results

Tested on 8 datasets 6 baseline values reported too low

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

Classic

Cora

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GraphSAGE+CNA code ↗ GNN global	0.9418 ±0.0033	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
2	GCN+CNA code ↗ GNN global	0.9366 ±0.0048	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
3	TransformerConv code ↗ GNN global	0.9350 ±0.0058	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
21	GCN GNN global	0.9004	Understanding Heterophily for Graph Neural Networks
166	RGIN (Clique, None, None) GNN baseline	0.8660 ±0.0060	This paper
263	GIN (None, Prune, None) GNN baseline	0.8440 ±0.0080	This paper
559	SIN (None, Prune, None) GNN baseline	0.8170 ±0.0080	This paper
681	CIN++ (Clique, None, None) GNN baseline	0.7940 ±0.0070	This paper
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks

CiteSeer

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	CNA code ↗ GNN global	0.9575 ±0.0058	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
2	IS-GIB code ↗ Hyb global	0.9390 ±0.0187	Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization code ↗
3	EERM code ↗ GNN global	0.9112 ±0.0145	Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization code ↗
44	GCN GNN global	0.8033 ±0.0088	NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification
287	RGIN Clique FoSR baseline	0.7340 ±0.0100	This paper
308	RGIN None FoSR baseline	0.7320 ±0.0060	This paper
350	MLP code ↗ Trad global	0.7289 ±0.0010	Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax code ↗
441	RGIN None None baseline	0.7220 ±0.0100	This paper
452	RGIN Clique None baseline	0.7210 ±0.0090	This paper
629	GIN None None baseline	0.6990 ±0.0080	This paper
643	GIN None FoSR baseline	0.6930 ±0.0080	This paper
652	GIN Clique None baseline	0.6900 ±0.0080	This paper
670	GIN Clique FoSR baseline	0.6860 ±0.0080	This paper
725	SIN None None baseline	0.6690 ±0.0080	This paper
788	CIN++ (Clique, FoSR) GNN baseline	0.6440 ±0.0100	This paper
804	SIN Clique None baseline	0.6320 ±0.0080	This paper
805	CIN++ (Clique, None) GNN baseline	0.6320 ±0.0090	This paper
829	SIN Clique FoSR baseline	0.6020 ±0.0120	This paper
857	SIN None FoSR baseline	0.5430 ±0.0110	This paper
879	CIN++ None FoSR GNN baseline	0.4490 ±0.0110	This paper
881	CIN++ None None GNN baseline	0.4470 ±0.0170	This paper

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
39	GIN GNN global	0.9330 ±0.0290	ProtGNN: Towards Self-Explaining Graph Neural Networks
307	SIN GNN baseline	0.8850 ±0.0300	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗

NCI1

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9954	1-WL Expressiveness Is (Almost) All You Need
2	GIN GNN baseline actual #2 vs paper #268 266 places worse	0.9934 best reported	actual #2 vs paper #268 266 places worse paper 0.7890 ±0.0060 best at pub: 1-WL Expressiveness Is (Almost) All You Need (2022) paper 0.7890 ±0.0060 Δ at pub 0.2044
3	GCN GNN baseline actual #3 vs paper #581 578 places worse	0.9727 best reported	actual #3 vs paper #581 578 places worse paper 0.4960 ±0.0060 best at pub: 1-WL Expressiveness Is (Almost) All You Need (2022) paper 0.4960 ±0.0060 Δ at pub 0.4767
19	CIN GNN baseline actual #19 vs paper #367 348 places worse	0.8530 ±0.0120 best reported	actual #19 vs paper #367 348 places worse paper 0.7680 ±0.0040 best at pub: CIN++: Enhancing Topological Message Passing (2023) best today: Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2023) paper 0.7680 ±0.0040 Δ at pub 0.0850 Δ today 0.0850
82	SIN GNN baseline actual #82 vs paper #223 141 places worse	0.8280 ±0.0220 best reported	actual #82 vs paper #223 141 places worse paper 0.8000 ±0.0080 best at pub: Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (ICML 2021) paper 0.8000 ±0.0080 Δ at pub 0.0280
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
234	RGIN GNN baseline	0.7980 ±0.0070	This paper
413	RGCN GNN baseline	0.7500 ±0.0090	This paper
566	SGC GNN baseline	0.5680 ±0.0080	This paper

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 #412 400 places worse	0.8050 ±0.0390 best reported	actual #12 vs paper #412 400 places worse paper 0.7190 ±0.0100 best at pub: CIN++: Enhancing Topological Message Passing (2023) best today: Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2023) paper 0.7190 ±0.0100 Δ at pub 0.0860 Δ today 0.0860
32	GIN GNN baseline actual #32 vs paper #372 340 places worse	0.7880 ±0.0410 best reported	actual #32 vs paper #372 340 places worse paper 0.7280 ±0.0120 best at pub: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7280 ±0.0120 Δ at pub 0.0600
67	SAGE GNN global	0.7726 ±0.0228	Semi-Supervised Hierarchical Graph Classification
118	SIN GNN baseline actual #118 vs paper #356 238 places worse	0.7640 ±0.0330 best reported	actual #118 vs paper #356 238 places worse paper 0.7320 ±0.0150 best at pub: Weisfeiler and Lehman Go Cellular: CW Networks (NeurIPS 2021) best today: Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7320 ±0.0150 Δ at pub 0.0320 Δ today 0.0320
148	GCN GNN baseline actual #148 vs paper #163 15 places worse	0.7600 ±0.0320 best reported	actual #148 vs paper #163 15 places worse paper 0.7580 ±0.0170 best at pub: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) best today: Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7580 ±0.0170 Δ at pub 0.0020 Δ today 0.0020
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
185	RGCN GNN baseline	0.7560 ±0.0120	This paper
392	RGIN GNN baseline	0.7240 ±0.0140	This paper
484	SGC GNN baseline	0.6500 ±0.0150	This paper

ENZYMES

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GMN code ↗ Hyb global	0.7866	Memory-Based Graph Networks code ↗
2	MemGNN code ↗ Hyb global	0.7550	Memory-Based Graph Networks code ↗
3	TFGW SP Hyb global	0.7510 ±0.0500	Template based Graph Neural Network with Optimal Transport Distances
17	GatedGCN code ↗ GNN global	0.7000 ±0.0494	GNNBenchmark code ↗
26	GraphSAGE code ↗ GNN global	0.6817 ±0.0545	GNNBenchmark code ↗
32	GIN GNN baseline actual #32 vs paper #159 127 places worse	0.6767 ±0.0583 best reported	actual #32 vs paper #159 127 places worse paper 0.5000 ±0.0270 best at pub: GNNBenchmark (JMLR 2023) paper 0.5000 ±0.0270 Δ at pub 0.1767
124	MLP code ↗ Trad global	0.5583 ±0.0352	GNNBenchmark code ↗
284	SGC GNN baseline	0.2150 ±0.0160	This paper

Heterophilic Graphs

Cornell

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	P^2GNN Hyb global	0.9541 ±0.0272	$P^2$GNN: Two Prototype Sets to boost GNN Performance
2	ACM-GCN code ↗ GNN global	0.9480 ±0.0380	Heterophily-informed Message Passing code ↗
3	RF-GCN GNN global	0.9429	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
24	MLP Trad global	0.9136 ±0.0070	Node-oriented Spectral Filtering for Graph Neural Networks
138	SAGE GNN global	0.8269	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
379	RGIN (None, None) GNN baseline	0.5950 ±0.0500	This paper
436	CIN++ (Ring, None) GNN baseline	0.5420 ±0.0420	This paper
510	GIN (Ring, Prune) GNN baseline	0.4740 ±0.0410	This paper
529	SIN (None, Prune) GNN baseline	0.4470 ±0.0420	This paper

Wisconsin

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DMD++ Hyb global	0.9190 ±0.0260	When Graph Neural Networks Meet Dynamic Mode Decomposition
2	F-GREAD-BS code ↗ GNN global	0.9059 ±0.0380	Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND code ↗
3	APPNP GNN global	0.9010 ±0.0350	When Graph Neural Networks Meet Dynamic Mode Decomposition
37	MLP code ↗ Trad global	0.8629 ±0.0450	Is Homophily a Necessity for Graph Neural Networks? code ↗
63	GCN code ↗ GNN global	0.8310 ±0.0320	Restructuring Graphs for Higher Homophily via Adaptive Spectral Clustering code ↗
106	RGIN (Ring, Prune, Prune) GNN baseline	0.7460 ±0.0250	This paper
143	CIN++ (Clique, None, None) GNN baseline	0.6620 ±0.0280	This paper
164	SIN (Ring, None, None) GNN baseline	0.6120 ±0.0350	This paper
182	GIN (Clique, FoSR, FoSR) GNN baseline	0.5650 ±0.0260	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)