Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability

Zehao Dong, Muhan Zhang, Qihang Zhao, Philip R. O. Payne, Michael Province, Carlos Cruchaga, Tianyu Zhao, Yixin Chen, Fuhai Li

Abstract

The expressivity of Graph Neural Networks (GNNs) has been studied broadly in recent years to reveal the design principles for more powerful GNNs. Graph canonization is known as a typical approach to distinguish non-isomorphic graphs, yet rarely adopted when developing expressive GNNs. This paper proposes to maximize the expressivity of GNNs by graph canonization, then the power of such GNNs is studies from the perspective of model stability. A stable GNN will map similar graphs to close graph representations in the vectorial space, and the stability of GNNs is critical to generalize their performance to unseen graphs. We theoretically reveal the trade-off of expressivity and stability in graph-canonization-enhanced GNNs. Then we introduce a notion of universal graph canonization as the general solution to address the trade-off and characterize a widely applicable sufficient condition to solve the universal graph canonization. A comprehensive set of experiments demonstrates the effectiveness of the proposed method. In many popular graph benchmark datasets, graph canonization successfully enhances GNNs and provides highly competitive performance, indicating the capability and great potential of proposed method in general graph representation learning. In graph datasets where the sufficient condition holds, GNNs enhanced by universal graph canonization consistently outperform GNN baselines and successfully improve the SOTA performance up to $31\

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

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
22	GIN-AK+ GNN baseline actual #22 vs paper #306 284 places worse	0.9500 ±0.0610 best reported	actual #22 vs paper #306 284 places worse paper 0.8850 ±0.0860 best at pub: Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries (NeurIPS 2022) best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.8850 ±0.0860 Δ at pub 0.0280 Δ today 0.0650
24	GraphSNN GNN baseline actual #24 vs paper #343 319 places worse	0.9470 ±0.0190 best reported	actual #24 vs paper #343 319 places worse paper 0.8780 ±0.0760 best at pub: The Expressive Power of Graph Neural Networks: A Survey (2023) best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.8780 ±0.0760 Δ at pub 0.0690 Δ today 0.0690
39	GIN GNN global	0.9330 ±0.0290	ProtGNN: Towards Self-Explaining Graph Neural Networks
73	ESAN GNN baseline actual #73 vs paper #111 38 places worse	0.9200 ±0.0500 best reported	actual #73 vs paper #111 38 places worse paper 0.9100 ±0.0480 best at pub: Asynchronous Neural Networks for Learning in Graphs (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.9100 ±0.0480 Δ at pub 0.0100
171	GNN-RNI GNN baseline	0.9040 ±0.0740	This paper
166	DropGNN GNN baseline	0.9040 ±0.0700	This paper
255	GC-GNN (GCN) GNN ★ proposed	0.8940 ±0.0880	This paper
322	SignNet GNN baseline	0.8830 ±0.0920	This paper
339	Nested GIN Hyb baseline	0.8790 ±0.0820	This paper
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
468	GIN (backbone) GNN ★ proposed	0.8450 ±0.0890	This paper
496	Nested GraphSAGE Hyb baseline	0.8390 ±0.1070	This paper
530	Nested GCN Hyb baseline	0.8290 ±0.1110	This paper
572	Nested GAT Hyb baseline	0.8190 ±0.1020	This paper
726	GraphSAGE (backbone) GNN baseline	0.7400 ±0.0880	This paper
732	GAT (backbone) GNN baseline	0.7390 ±0.1070	This paper
739	GCN (backbone) GNN baseline	0.7340 ±0.1080	This paper

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 ↗
30	GIN-AK+ GNN baseline actual #30 vs paper #224 194 places worse	0.7890 ±0.0540 best reported	actual #30 vs paper #224 194 places worse paper 0.7520 ±0.0470 best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7520 ±0.0470 Δ today 0.0370
32	GIN GNN global	0.7880 ±0.0410	Permutation-Invariant graph partitioning: How graph neural networks capture structural …
39	GraphSNN GNN baseline actual #39 vs paper #275 236 places worse	0.7842 ±0.0270 best reported	actual #39 vs paper #275 236 places worse paper 0.7470 ±0.0390 best at pub: The Expressive Power of Graph Neural Networks: A Survey (2023) best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7470 ±0.0390 Δ at pub 0.0370 Δ today 0.0372
78	ESAN GNN baseline actual #78 vs paper #163 85 places worse	0.7710 ±0.0460 best reported	actual #78 vs paper #163 85 places worse paper 0.7580 ±0.0450 best at pub: The Expressive Power of Graph Neural Networks: A Survey (2023) best today: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7580 ±0.0450 Δ at pub 0.0010 Δ today 0.0130
96	GC-GNN (GCN) GNN ★ proposed	0.7670 ±0.0510	This paper
130	DropGNN GNN baseline	0.7630 ±0.0610	This paper
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
186	SignNet GNN baseline	0.7560 ±0.0410	This paper
308	Nested GraphSAGE Hyb baseline	0.7420 ±0.0370	This paper
322	Nested GIN Hyb baseline	0.7390 ±0.0510	This paper
333	Nested GAT Hyb baseline	0.7370 ±0.0480	This paper
345	GNN-RNI GNN baseline	0.7350 ±0.0450	This paper
354	Nested GCN Hyb baseline	0.7330 ±0.0400	This paper
410	GAT (backbone) GNN baseline	0.7200 ±0.0330	This paper
422	GCN (backbone) GNN baseline	0.7170 ±0.0470	This paper
437	GraphSAGE (backbone) GNN baseline	0.7120 ±0.0520	This paper
448	GIN (backbone) GNN ★ proposed	0.7060 ±0.0430	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 ↗
26	GraphSAGE code ↗ GNN global	0.6817 ±0.0545	GNNBenchmark code ↗
31	GraphSNN GNN baseline actual #31 vs paper #205 174 places worse	0.6767 ±0.0374 best reported	actual #31 vs paper #205 174 places worse paper 0.3680 ±0.0510 best at pub: Union Subgraph Neural Networks (AAAI 2023) paper 0.3680 ±0.0510 Δ at pub 0.3087
124	MLP code ↗ Trad global	0.5583 ±0.0352	GNNBenchmark code ↗
194	GIN-AK+ GNN baseline	0.3850 ±0.0630	This paper
195	GIN (backbone) GNN ★ proposed	0.3830 ±0.0640	This paper
196	DropGNN GNN baseline	0.3830 ±0.0710	This paper
198	ESAN GNN baseline	0.3790 ±0.0630	This paper
199	GC-GNN (GCN) GNN ★ proposed	0.3770 ±0.0690	This paper
202	SignNet GNN baseline	0.3750 ±0.0640	This paper
225	Nested GCN Hyb baseline	0.3120 ±0.0670	This paper
227	GraphSAGE (backbone) GNN baseline	0.3070 ±0.0630	This paper
228	Nested GraphSAGE Hyb baseline	0.3070 ±0.0630	This paper
229	GNN-RNI GNN baseline	0.3070 ±0.0560	This paper
231	GAT (backbone) GNN baseline	0.3020 ±0.0420	This paper
235	Nested GAT Hyb baseline	0.2950 ±0.0570	This paper
236	Nested GIN Hyb baseline	0.2900 ±0.0800	This paper
245	GCN (backbone) GNN baseline	0.2730 ±0.0550	This paper

D&D

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GC-GNN (GCN) GNN ★ proposed	0.9210 ±0.0810	This paper
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
20	GIN-AK+ GNN baseline	0.8030 ±0.0310	This paper
27	ESAN GNN baseline	0.7970 ±0.0380	This paper
30	GraphSNN GNN baseline	0.7960 ±0.0290	This paper
60	DropGNN GNN baseline	0.7850 ±0.0600	This paper
71	SignNet GNN baseline	0.7820 ±0.0410	This paper
82	Nested GIN Hyb baseline	0.7780 ±0.0390	This paper
95	Nested GraphSAGE Hyb baseline	0.7740 ±0.0420	This paper
113	Nested GCN Hyb baseline	0.7630 ±0.0380	This paper
118	Nested GAT Hyb baseline	0.7600 ±0.0440	This paper
123	GNN-RNI GNN baseline	0.7580 ±0.0300	This paper
162	GCN (backbone) GNN baseline	0.7160 ±0.0280	This paper
163	GraphSAGE (backbone) GNN baseline	0.7160 ±0.0300	This paper
167	GAT (backbone) GNN baseline	0.7100 ±0.0440	This paper
168	GIN (backbone) GNN ★ proposed	0.7050 ±0.0360	This paper

OGB

ogbg-molhiv

Global leaderboard →

#	Model	ROC-AUC ↑	Paper
1	Multi-RF Fusion with Multi-GNN Blending global	0.8476 ±0.0002	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
2	HyperFusion global	0.8475 ±0.0003	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
3	PAS+FPs global	0.8420 ±0.0015	Multi-RF Fusion with Multi-GNN Blending for Molecular Property Prediction
9	GatedGCN GNN 2.8M global	0.8090 ±0.0160	Deep Prompt Tuning for Graph Transformers
98	ESAN (GIN + ED) Trad baseline	0.7803 ±0.0170	This paper
109	GIN GNN 510.0M global	0.7780 ±0.0182	GRPE: Relative Positional Encoding for Graph Transformer
125	GIN (backbone) GNN ★ proposed	0.7744 ±0.0098	This paper
153	GN-GIN Hyb baseline	0.7705 ±0.0195	This paper
195	GN-GCN Hyb baseline	0.7609 ±0.0158	This paper
239	GCN (backbone) GNN baseline	0.7501 ±0.0140	This paper

ogbg-molpcba

Global leaderboard →

#	Model	AP ↑	Paper
1	GRPE-Large GT global	0.3150 ±0.0010	GRPE: Relative Positional Encoding for Graph Transformer
2	Graphormer code ↗ GT global	0.3140	Unified 2D and 3D Pre-Training of Molecular Representations code ↗
3	Graphormer-FLAG GT 47.0M global	0.3139 ±0.0032	GRPE: Relative Positional Encoding for Graph Transformer
31	GIN GNN 510.0M global	0.2902 ±0.0017	GRPE: Relative Positional Encoding for Graph Transformer
45	ESAN (GIN + ED) Trad baseline	0.2782 ±0.0036	This paper
46	GN-GIN Hyb baseline	0.2781 ±0.0043	This paper
54	GIN (backbone) GNN ★ proposed	0.2703 ±0.0023	This paper
76	GN-GCN Hyb baseline	0.2510 ±0.0047	This paper
82	GCN (backbone) GNN baseline	0.2422 ±0.0034	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)