Graph Capsule Convolutional Neural Networks

Saurabh Verma, Zhi-Li Zhang

Abstract

Graph Convolutional Neural Networks (GCNNs) are the most recent exciting advancement in deep learning field and their applications are quickly spreading in multi-cross-domains including bioinformatics, chemoinformatics, social networks, natural language processing and computer vision. In this paper, we expose and tackle some of the basic weaknesses of a GCNN model with a capsule idea presented in and propose our Graph Capsule Network (GCAPS-CNN) model. In addition, we design our GCAPS-CNN model to solve especially graph classification problem which current GCNN models find challenging. Through extensive experiments, we show that our proposed Graph Capsule Network can significantly outperforms both the existing state-of-art deep learning methods and graph kernels on graph classification benchmark datasets.

Benchmark Results

Tested on 7 datasets 6 baseline values 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
12	WL Trad baseline actual #12 vs paper #122 110 places worse	0.8590 ±0.0010 best reported	actual #12 vs paper #122 110 places worse paper 0.8219 ±0.0018 best at pub: Propagation Kernels (2014) paper 0.8219 ±0.0018 Δ at pub 0.0371
91	GCAPS-CNN GNN ★ proposed	0.8272 ±0.0238	This paper
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
145	MLG SVM baseline	0.8175 ±0.0024	This paper
210	DGK SVM baseline	0.8031 ±0.0046	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.0024 best at pub: On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016) paper 0.7300 ±0.0024 Δ at pub 0.0150
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 at pub: Learning Convolutional Neural Networks for Graphs (ICML 2016) best today: GPS: graph contrastive learning via multi-scale augmented views from adversarial pooling (2024) paper 0.6228 ±0.0029 Δ today 0.0372
540	DCNN Trad baseline actual #540 vs paper #566 26 places worse	0.6261 best reported	actual #540 vs paper #566 26 places worse paper 0.5661 ±0.0104 best at pub: Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017) best today: Deep Learning on Attributed Graphs: A Journey from Graphs to Their Embeddings and Back (2018) paper 0.5661 ±0.0104 Δ at pub 0.0600 Δ today 0.0600

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 ↗
32	GIN GNN global	0.7880 ±0.0410	Permutation-Invariant graph partitioning: How graph neural networks capture structural …
123	GCAPS-CNN GNN ★ proposed	0.7640 ±0.0417	This paper
125	MLG SVM baseline	0.7634 ±0.0072	This paper
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
164	SP Trad baseline actual #164 vs paper #239 75 places worse	0.7580 ±0.0050 best reported	actual #164 vs paper #239 75 places worse paper 0.7507 ±0.0054 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.7507 ±0.0054 Δ at pub 0.0073
178	DGK SVM baseline	0.7568 ±0.0054	This paper
190	WL Trad baseline actual #190 vs paper #277 87 places worse	0.7560 ±0.0040 best reported	actual #190 vs paper #277 87 places worse paper 0.7468 ±0.0049 best at pub: On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016) paper 0.7468 ±0.0049 Δ at pub 0.0092
302	RW SVM baseline	0.7422 ±0.0130	This paper
425	GK SVM baseline	0.7167 ±0.0055	This paper
501	DCNN Trad baseline actual #501 vs paper #501	0.6130 ±0.0160 best reported	actual #501 vs paper #501 paper 0.6129 ±0.0160 best today: Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.6129 ±0.0160 Δ today 0.0001

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 ↗
151	MLP Trad global	0.7920 ±0.0240	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
187	GCAPS-CNN GNN baseline	0.7771 ±0.0251	This paper
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.0025 best today: InfoGCL: Information-Aware Graph Contrastive Learning (NeurIPS 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.7309 ±0.0025 Δ today 0.0001
277	GK SVM baseline	0.7284 ±0.0028	This paper
344	DCNN Trad baseline	0.5211 ±0.0071	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 #150 132 places worse	0.6950 ±0.0320 best reported	actual #18 vs paper #150 132 places worse paper 0.5222 ±0.0126 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.5222 ±0.0126 Δ at pub 0.0683 Δ today 0.1728
26	GraphSAGE code ↗ GNN global	0.6817 ±0.0545	GNNBenchmark code ↗
75	GCAPS-CNN GNN ★ proposed	0.6183 ±0.0539	This paper
76	MLG SVM baseline	0.6181 ±0.0099	This paper
124	MLP code ↗ Trad global	0.5583 ±0.0352	GNNBenchmark code ↗
145	DGK SVM baseline	0.5343 ±0.0091	This paper
179	SP Trad baseline actual #179 vs paper #186 7 places worse	0.4260 ±0.0160 best reported	actual #179 vs paper #186 7 places worse paper 0.4010 ±0.0150 best at pub: On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016) paper 0.4010 ±0.0150 Δ at pub 0.0250
181	DCNN Trad baseline actual #181 vs paper #181	0.4244 ±0.0176	actual #181 vs paper #181 paper 0.4244 ±0.0176 prev best: Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017) paper 0.4244 ±0.0176 Δ at pub 0.2434
218	GK SVM baseline actual #218 vs paper #249 31 places worse	0.3270 ±0.0120 best reported	actual #218 vs paper #249 31 places worse paper 0.2661 ±0.0099 best today: Anonymous Walk Embeddings (ICML 2018) paper 0.2661 ±0.0099 Δ today 0.0609
257	RW SVM baseline	0.2416 ±0.0164	This paper

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	0.7978 ±0.0036	This paper
63	GK SVM baseline	0.7845 ±0.0111	This paper
72	MLG SVM baseline	0.7818 ±0.0256	This paper
85	GCAPS-CNN GNN baseline	0.7762 ±0.0499	This paper
155	DGK SVM baseline	0.7350 ±0.0101	This paper
193	DCNN Trad baseline	0.5809 ±0.0053	This paper

IMDB-BINARY

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	ID-GNN+BEC Hyb global	0.8150 ±0.0240	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
2	GIN+BEC Hyb global	0.8080 ±0.0330	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
3	GCN+BEC Hyb global	0.7990 ±0.0340	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
4	GCN GNN global	0.7980 ±0.0230	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
114	GCAPS-CNN GNN baseline	0.7169 ±0.0340	This paper
140	DGK SVM baseline actual #140 vs paper #140	0.6700 ±0.0060 best reported	actual #140 vs paper #140 paper 0.6696 ±0.0056 best today: Contrastive Multi-View Representation Learning on Graphs (ICML 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.6696 ±0.0056 Δ today 0.0004
142	GK SVM baseline actual #142 vs paper #142	0.6590 ±0.0100 best reported	actual #142 vs paper #142 paper 0.6587 ±0.0098 best today: Contrastive Multi-View Representation Learning on Graphs (ICML 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.6587 ±0.0098 Δ today 0.0003
158	DCNN Trad baseline	0.4906 ±0.0137	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
87	GCAPS-CNN GNN baseline	0.4850 ±0.0410	This paper
109	DGK SVM baseline actual #109 vs paper #109	0.4460 ±0.0050 best reported	actual #109 vs paper #109 paper 0.4455 ±0.0052 best today: Contrastive Multi-View Representation Learning on Graphs (ICML 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.4455 ±0.0052 Δ today 0.0005
110	GK SVM baseline actual #110 vs paper #110	0.4390 ±0.0040 best reported	actual #110 vs paper #110 paper 0.4389 ±0.0038 best today: Contrastive Multi-View Representation Learning on Graphs (ICML 2020) Difference within reported uncertainty; not counted as underperformance. paper 0.4389 ±0.0038 Δ today 0.0001
117	DCNN Trad baseline	0.3349 ±0.0142	This paper

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) Best at pub — reported value improved over the best known when published Best today — OK at publication; today's leaderboard best is elsewhere