Hierarchical Graph Capsule Network

Jinyu Yang, P. Zhao, Yu Rong, Chao-chao Yan, Chunyuan Li, Hehuan Ma, Junzhou Huang

Abstract

Graph Neural Networks (GNNs) draw their strength from explicitly modeling the topological information of structured data. However, existing GNNs suffer from limited capability in capturing the hierarchical graph representation which plays an important role in graph classification. In this paper, we innovatively propose hierarchical graph capsule network (HGCN) that can jointly learn node embeddings and extract graph hierarchies. Specifically, disentangled graph capsules are established by identifying heterogeneous factors underlying each node, such that their instantiation parameters represent different properties of the same entity. To learn the hierarchical representation, HGCN characterizes the part-whole relationship between lower-level capsules (part) and higher-level capsules (whole) by explicitly considering the structure information among the parts. Experimental studies demonstrate the effectiveness of HGCN and the contribution of each component. Code: https://github.com/uta-smile/HGCN

Benchmark Results

Tested on 5 datasets 1 baseline value 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
41	HGCN Hyb ★ proposed	0.9316 ±0.0610	This paper
51	PSCN GNN baseline actual #51 vs paper #279 228 places worse	0.9263 ±0.0421 best reported	actual #51 vs paper #279 228 places worse paper 0.8895 ±0.0437 best at pub: Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017) best today: Quaternion Graph Neural Networks (2020) Difference within reported uncertainty; not counted as underperformance. paper 0.8895 ±0.0437 Δ at pub 0.0368 Δ today 0.0368
63	GCN GNN baseline actual #63 vs paper #379 316 places worse	0.8720 ±0.0511	actual #63 vs paper #379 316 places worse paper 0.8720 ±0.0511 prev best: Graph Neural Networks With Convolutional ARMA Filters (2019) Improvement within reported uncertainty; not highlighted. paper 0.8720 ±0.0511 Δ at pub 0.0150
159	WL Trad baseline actual #159 vs paper #563 404 places worse	0.9040 ±0.0570 best reported	actual #159 vs paper #563 404 places worse paper 0.8205 ±0.0036 best at pub: Understanding Isomorphism Bias in Graph Data Sets (2019) best today: How Powerful are $K$-hop Message Passing Graph Neural Networks (NeurIPS 2022) paper 0.8205 ±0.0036 Δ at pub 0.0415 Δ today 0.0835
365	DGK SVM baseline	0.8744 ±0.0272	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
634	EigenPooling GNN baseline	0.7950	This paper
671	HaarPool GNN baseline	0.7760 ±0.0894	This paper

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 baseline actual #3 vs paper #47 44 places worse	0.8365 ±0.0169	actual #3 vs paper #47 44 places worse paper 0.8365 ±0.0169 prev best: Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels (NeurIPS 2019) best today: 1-WL Expressiveness Is (Almost) All You Need (2022) paper 0.8365 ±0.0169 Δ at pub 0.0345 Δ today 0.1362
24	CapsNets Hyb ★ proposed	0.8487 ±0.0168	This paper
88	GFN GNN baseline	0.8277 ±0.0149	This paper
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
218	HaarPool GNN baseline	0.8017 ±0.0229	This paper
302	CapsGNN GNN baseline actual #302 vs paper #303 1 place worse	0.7840 ±0.0160 best reported	actual #302 vs paper #303 1 place worse paper 0.7835 ±0.0155 best today: Molecular Representation Learning via Heterogeneous Motif Graph Neural Networks (ICML 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7835 ±0.0155 Δ today 0.0005
357	EigenPooling GNN baseline	0.7700	This paper
519	GK SVM baseline actual #519 vs paper #541 22 places worse	0.6600 ±0.0010 best reported	actual #519 vs paper #541 22 places worse paper 0.6249 ±0.0027 best at pub: Implicit Graph Neural Networks (NeurIPS 2020) best today: GPS: graph contrastive learning via multi-scale augmented views from adversarial pooling (2024) paper 0.6249 ±0.0027 Δ at pub 0.0001 Δ today 0.0351

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 …
101	EigenPooling GNN baseline	0.7660	This paper
148	GCN GNN baseline actual #148 vs paper #179 31 places worse	0.7565 ±0.0324	actual #148 vs paper #179 31 places worse paper 0.7565 ±0.0324 prev best: Graph Convolutional Networks with EigenPooling (KDD 2019) Improvement within reported uncertainty; not highlighted. paper 0.7565 ±0.0324 Δ at pub 0.0165
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
178	DGK SVM baseline	0.7568 ±0.0054	This paper
355	HaarPool GNN baseline	0.7323 ±0.0251	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
16	GFN GNN baseline	0.7017 ±0.0558	This paper
17	GatedGCN code ↗ GNN global	0.7000 ±0.0494	GNNBenchmark code ↗
26	GraphSAGE code ↗ GNN global	0.6817 ±0.0545	GNNBenchmark code ↗
36	GCN GNN baseline actual #36 vs paper #36	0.6650 ±0.0691	actual #36 vs paper #36 paper 0.6650 ±0.0691 prev best: GraphCrop: Subgraph Cropping for Graph Classification (2020) Improvement within reported uncertainty; not highlighted. paper 0.6650 ±0.0691 Δ at pub 0.0740
54	EigenPooling GNN baseline	0.6450	This paper
124	MLP code ↗ Trad global	0.5583 ±0.0352	GNNBenchmark code ↗
127	CapsGNN GNN baseline actual #127 vs paper #136 9 places worse	0.5531 ±0.0423 best reported	actual #127 vs paper #136 9 places worse paper 0.5467 ±0.0567 best at pub: Wasserstein Embedding for Graph Learning (ICLR 2020) best today: Contrastive Graph Few-Shot Learning (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.5467 ±0.0567 Δ at pub 0.0003 Δ today 0.0064

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
43	GCN GNN baseline actual #43 vs paper #43	0.7912 ±0.0307	actual #43 vs paper #43 paper 0.7912 ±0.0307 prev best: Graph Convolutional Networks with EigenPooling (KDD 2019) Improvement within reported uncertainty; not highlighted. paper 0.7912 ±0.0307 Δ at pub 0.0322
52	GFN GNN baseline	0.7878 ±0.0349	This paper
85	GCAPS-CNN GNN baseline	0.7762 ±0.0499	This paper
97	CliquePool GNN baseline	0.7733	This paper
101	PSCN GNN baseline actual #101 vs paper #113 12 places worse	0.7712 ±0.0241 best reported	actual #101 vs paper #113 12 places worse paper 0.7627 ±0.0264 best at pub: Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017) best today: Semi-Supervised Hierarchical Graph Classification (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7627 ±0.0264 Δ at pub 0.0085 Δ today 0.0085
132	CapsGNN GNN baseline	0.7538 ±0.0417	This paper
164	AWE Walk baseline	0.7151 ±0.0402	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) Improved at pub — later paper surpassed this result Best today — OK at publication; today's leaderboard best is elsewhere