Learning Convolutional Neural Networks for Graphs

Mathias Niepert, Mohamed Ahmed, Konstantin Kutzkov

Abstract

Numerous important problems can be framed as learning from graph data. We propose a framework for learning convolutional neural networks for arbitrary graphs. These graphs may be undirected, directed, and with both discrete and continuous node and edge attributes. Analogous to image-based convolutional networks that operate on locally connected regions of the input, we present a general approach to extracting locally connected regions from graphs. Using established benchmark data sets, we demonstrate that the learned feature representations are competitive with state of the art graph kernels and that their computation is highly efficient.

Benchmark Results

Tested on 3 datasets 3 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
39	GIN GNN global	0.9330 ±0.0290	ProtGNN: Towards Self-Explaining Graph Neural Networks
52	PSCN k=10E GNN baseline	0.9263 ±0.0421	This paper
87	PSCN k=5 GNN baseline	0.9158 ±0.0586	This paper
159	WL Trad baseline actual #159 vs paper #596 437 places worse	0.9040 ±0.0570 best reported	actual #159 vs paper #596 437 places worse paper 0.8072 ±0.0300 best at pub: The Multiscale Laplacian Graph Kernel (NeurIPS 2016) best today: How Powerful are $K$-hop Message Passing Graph Neural Networks (NeurIPS 2022) paper 0.8072 ±0.0300 Δ at pub 0.0378 Δ today 0.0968
280	PSCN k=10 GNN baseline	0.8895 ±0.0437	This paper
370	PSLR k=10 Trad baseline	0.8737 ±0.0788	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
426	SP Trad baseline actual #426 vs paper #429 3 places worse	0.8580 ±0.0020 best reported	actual #426 vs paper #429 3 places worse paper 0.8579 ±0.0251 best at pub: Propagation Kernels (2014) Difference within reported uncertainty; not counted as underperformance. paper 0.8579 ±0.0251 Δ at pub 0.0001
501	RW SVM baseline actual #501 vs paper #504 3 places worse	0.8370 ±0.0150 best reported	actual #501 vs paper #504 3 places worse paper 0.8368 ±0.0166 best today: Learning Graph Representation by Aggregating Subgraphs via Mutual Information Maximization (2021) Difference within reported uncertainty; not counted as underperformance. paper 0.8368 ±0.0166 Δ today 0.0002
506	GK SVM baseline actual #506 vs paper #580 74 places worse	0.8350 ±0.0060 best reported	actual #506 vs paper #580 74 places worse paper 0.8158 ±0.0211 best today: Supervised Contrastive Learning with Structure Inference for Graph Classification (2022) paper 0.8158 ±0.0211 Δ today 0.0192

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
12	WL Trad baseline actual #12 vs paper #213 201 places worse	0.8590 ±0.0010 best reported	actual #12 vs paper #213 201 places worse paper 0.8022 ±0.0051 best at pub: Propagation Kernels (2014) paper 0.8022 ±0.0051 Δ at pub 0.0568
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
292	PSCN k=10E GNN baseline	0.7859 ±0.0189	This paper
382	PSCN k=10 GNN baseline	0.7634 ±0.0168	This paper
421	SP Trad baseline actual #421 vs paper #449 28 places worse	0.7450 ±0.0030 best reported	actual #421 vs paper #449 28 places worse paper 0.7300 ±0.0051 best at pub: Propagation Kernels (2014) best today: On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016) paper 0.7300 ±0.0051 Δ at pub 0.0140 Δ today 0.0150
455	PSCN k=5 GNN baseline	0.7280 ±0.0206	This paper
482	PSLR k=10 Trad baseline	0.7000 ±0.0198	This paper
519	GK SVM baseline actual #519 vs paper #542 23 places worse	0.6600 ±0.0010 best reported	actual #519 vs paper #542 23 places worse paper 0.6228 ±0.0029 best today: GPS: graph contrastive learning via multi-scale augmented views from adversarial pooling (2024) paper 0.6228 ±0.0029 Δ today 0.0372

D&D

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GC-GNN (GCN) GNN global	0.9210 ±0.0810	Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability
2	SUGAR code ↗ Hyb global	0.8403 ±0.0133	SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information … code ↗
3	Ortho-g-U-Nets global	0.8387	Orthogonal Graph Neural Networks
15	SAGE GNN global	0.8088 ±0.0233	Semi-Supervised Hierarchical Graph Classification
25	WL Trad baseline actual #25 vs paper #78 53 places worse	0.7978 ±0.0036 best reported	actual #25 vs paper #78 53 places worse paper 0.7795 ±0.0070 best today: Graph Learning with Distributional Edge Layouts (2024) paper 0.7795 ±0.0070 Δ today 0.0183
63	GK SVM baseline	0.7845 ±0.0026	This paper
102	PSCN k=10^E GNN baseline	0.7712 ±0.0241	This paper
115	PSCN k=10 GNN baseline	0.7627 ±0.0264	This paper
144	PSCN k=5 GNN baseline	0.7458 ±0.0285	This paper
173	PSLR k=10 Trad baseline	0.6839 ±0.0556	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 today — OK at publication; today's leaderboard best is elsewhere