Natural Graph Networks

P. D. Haan, Taco Cohen, Max Welling

Abstract

A key requirement for graph neural networks is that they must process a graph in a way that does not depend on how the graph is described. Traditionally this has been taken to mean that a graph network must be equivariant to node permutations. Here we show that instead of equivariance, the more general concept of naturality is sufficient for a graph network to be well-defined, opening up a larger class of graph networks. We define global and local natural graph networks, the latter of which are as scalable as conventional message passing graph neural networks while being more flexible. We give one practical instantiation of a natural network on graphs which uses an equivariant message network parameterization, yielding good performance on several benchmarks.

Benchmark Results

Tested on 3 datasets

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
39	GIN GNN global	0.9330 ±0.0290	ProtGNN: Towards Self-Explaining Graph Neural Networks
145	PPGN v1 GNN baseline	0.9055 ±0.0870	This paper
256	GCN^2 GNN baseline	0.8939 ±0.0160	This paper
290	PPGN v2 GNN baseline	0.8888 ±0.0740	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 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
70	PPGN v1 GNN baseline	0.8319 ±0.0111	This paper
90	GCN^2 GNN baseline	0.8274 ±0.0135	This paper
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
169	PPGN v2 GNN baseline	0.8121 ±0.0214	This paper

COLLAB

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9792	1-WL Expressiveness Is (Almost) All You Need
2	MSH-GNN GNN global	0.9640 ±0.0070	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
3	CoCN code ↗ GNN global	0.8722 ±0.0013	Scalable Graph Compressed Convolutions code ↗
23	GCN code ↗ GNN global	0.8260 ±0.0220	Scalable Expressiveness through Preprocessed Graph Perturbations code ↗
65	PPGN v2 GNN baseline	0.8138 ±0.0142	This paper
118	PPGN v1 GNN baseline	0.8016 ±0.0111	This paper
151	MLP Trad global	0.7920 ±0.0240	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
172	Invariant Graph Networks GNN baseline	0.7836 ±0.0247	This paper
191	DGCNN GNN baseline actual #191 vs paper #269 78 places worse	0.7759 ±0.0224 best reported	actual #191 vs paper #269 78 places worse paper 0.7376 ±0.0050 best at pub: Graph U-Nets (2019) best today: Explainable Graph Representation Learning via Graph Pattern Analysis (IJCAI 2025) paper 0.7376 ±0.0050 Δ today 0.0383
274	DGK SVM baseline actual #274 vs paper #275 1 place worse	0.7310 ±0.0030 best reported	actual #274 vs paper #275 1 place worse paper 0.7309 ±0.0030 best at pub: Wasserstein Embedding for Graph Learning (ICLR 2020) best today: InfoGCL: Information-Aware Graph Contrastive Learning (NeurIPS 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.7309 ±0.0030 Δ at pub 0.0001 Δ today 0.0001
281	PSCN GNN baseline	0.7260 ±0.0220	This paper
344	DCNN Trad baseline	0.5211 ±0.0070	This paper

SOTA performance (not significantly different from the best) Baseline / comparison (this paper) Global context (other papers) Best today — OK at publication; today's leaderboard best is elsewhere