Topological Graph Neural Networks

Max Horn, E. Brouwer, Michael Moor, Y. Moreau, Bastian Alexander Rieck, Karsten M. Borgwardt

Abstract

Graph neural networks (GNNs) are a powerful architecture for tackling graph learning tasks, yet have been shown to be oblivious to eminent substructures such as cycles. We present TOGL, a novel layer that incorporates global topological information of a graph using persistent homology. TOGL can be easily integrated into any type of GNN and is strictly more expressive (in terms the Weisfeiler--Lehman graph isomorphism test) than message-passing GNNs. Augmenting GNNs with TOGL leads to improved predictive performance for graph and node classification tasks, both on synthetic data sets, which can be classified by humans using their topology but not by ordinary GNNs, and on real-world data.

Benchmark Results

Tested on 6 datasets 1 baseline value reported too low

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

TU Dortmund

NCI1

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9954	1-WL Expressiveness Is (Almost) All You Need
2	GIN GNN global	0.9934	1-WL Expressiveness Is (Almost) All You Need
3	GCN GNN global	0.9727	1-WL Expressiveness Is (Almost) All You Need
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
398	GCN-1-TOGL-1 Hyb ★ proposed	0.7580 ±0.0180	This paper
443	PersLay Hyb baseline	0.7350	This paper
469	GFL Trad baseline	0.7120 ±0.0210	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 ↗
18	WL Trad baseline actual #18 vs paper #137 119 places worse	0.6950 ±0.0320 best reported	actual #18 vs paper #137 119 places worse paper 0.5430 ±0.0090 best at pub: Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017) best today: Template based Graph Neural Network with Optimal Transport Distances (NeurIPS 2022) paper 0.5430 ±0.0090 Δ at pub 0.0475 Δ today 0.1520
26	GraphSAGE code ↗ GNN global	0.6817 ±0.0545	GNNBenchmark code ↗
43	GCN-4 GNN baseline	0.6580 ±0.0460	This paper
44	GATED-GCN-4 GNN baseline	0.6570 ±0.0490	This paper
98	WL-OA Trad baseline actual #98 vs paper #108 10 places worse	0.5990 ±0.0110 best reported	actual #98 vs paper #108 10 places worse paper 0.5890 ±0.0090 best at pub: On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016) Difference within reported uncertainty; not counted as underperformance. paper 0.5890 ±0.0090 Δ at pub 0.0100
124	MLP code ↗ Trad global	0.5583 ±0.0352	GNNBenchmark code ↗
146	GCN-3-TOGL-1 Hyb ★ proposed	0.5300 ±0.0920	This paper
153	GAT-3-TOGL-1 Hyb ★ proposed	0.5150 ±0.0730	This paper
160	GIN-4 GNN baseline	0.5000 ±0.1230	This paper
174	GIN-3-TOGL-1 Hyb ★ proposed	0.4380 ±0.0790	This paper
247	GAT-4 GNN baseline	0.2680 ±0.0410	This paper

IMDB-MULTI

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GraphSNN GNN global	0.7790 ±0.0360	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
2	SIN GNN global	0.7560 ±0.0320	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
3	CIN GNN global	0.7560 ±0.0370	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
5	GIN GNN global	0.7510 ±0.0510	Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
37	GCN-1-TOGL-1 Hyb ★ proposed	0.5200 ±0.0400	This paper
68	GFL Trad baseline	0.4970 ±0.0290	This paper
81	PersLay Hyb baseline	0.4880	This paper

GNNBenchmark

MNIST

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	Schrödinger GNN global	0.9913 ±0.0004	Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observables
2	CNN GNN global	0.9907 ±0.0007	Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observables
3	MPNN GNN global	0.9895 ±0.0006	Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observables
11	GatedGCN GNN global	0.9855 ±0.0002	RandAlign: A Parameter-Free Method for Regularizing Graph Convolutional Networks
32	GIN GNN global	0.9833 ±0.0011	Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observables
98	GATED-GCN-4 GNN baseline	0.9730 ±0.0010	This paper
115	GIN-3-TOGL-1 Hyb ★ proposed	0.9610 ±0.0010	This paper
114	GIN-4 GNN baseline	0.9610 ±0.0030	This paper
120	GAT-3-TOGL-1 Hyb ★ proposed	0.9590 ±0.0030	This paper
124	GCN-3-TOGL-1 Hyb ★ proposed	0.9550 ±0.0020	This paper
126	MLP code ↗ Trad global	0.9534 ±0.0014	GNNBenchmark code ↗
134	GAT-4 GNN baseline	0.9410 ±0.0030	This paper
142	GCN-4 GNN baseline	0.9000 ±0.0030	This paper

CLUSTER

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GRPE-Small Hyb 489.0M global	0.8159 ±0.0019	GRPE: Relative Positional Encoding for Graph Transformer
2	TANGO-GPS Hyb global	0.8011 ±0.0014	TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows
3	GRIT GNN global	0.8003 ±0.0028	GCCM: Enhancing Generative Graph Prediction via Contrastive Consistency Model
54	GatedGCN GNN 505.0M global	0.7608 ±0.0020	GRPE: Relative Positional Encoding for Graph Transformer
70	GCN code ↗ GNN global	0.6903 ±0.0137	Recurrent Distance Filtering for Graph Representation Learning code ↗
86	GCN-3-TOGL-1 Hyb ★ proposed	0.6040 ±0.2000	This paper
92	GCN-4 GNN baseline	0.5700 ±0.9000	This paper
114	MLP code ↗ Trad global	0.2097 ±0.0000	GNNBenchmark code ↗

PATTERN

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DeepGraph (48) code ↗ Hyb global	0.9066 ±0.0006	Are More Layers Beneficial to Graph Transformers? code ↗
2	GRIT (our run) GT global	0.9041 ±0.0023	Enhancing Graph Neural Networks with Quantum Computed Encodings
3	GRIT 2-QiQRW Hyb global	0.9016 ±0.0045	Enhancing Graph Neural Networks with Quantum Computed Encodings
45	GIN-3-TOGL-1 Hyb ★ proposed	0.8670 ±0.0010	This paper
56	GCN-3-TOGL-1 Hyb ★ proposed	0.8660 ±0.0010	This paper
66	GatedGCN code ↗ GNN 0.5M global	0.8651 ±0.0008	IJCAI--23 Formatting Instructions code ↗
88	GCN code ↗ GNN global	0.8561 ±0.0003	Recurrent Distance Filtering for Graph Representation Learning code ↗
92	GCN-4 GNN baseline	0.8550 ±0.0040	This paper
97	GIN-4 GNN baseline	0.8480	This paper
116	GAT-4 GNN baseline	0.7310 ±0.0190	This paper
120	GAT-3-TOGL-1 Hyb ★ proposed	0.5960 ±0.0330	This paper
123	MLP code ↗ Trad global	0.5052	GNNBenchmark code ↗

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