Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization

Kaixuan Chen, Shunyu Liu, Tongtian Zhu, Ji Qiao, Yun Su, Yingjie Tian, Tongya Zheng, Haofei Zhang, Zunlei Feng, Jingwen Ye, Mingli Song

Abstract

Graph Neural Networks (GNNs) have emerged as a powerful category of learning architecture for handling graph-structured data. However, existing GNNs typically ignore crucial structural characteristics in node-induced subgraphs, which thus limits their expressiveness for various downstream tasks. In this paper, we strive to strengthen the representative capabilities of GNNs by devising a dedicated plug-and-play normalization scheme, termed as SUbgraph-sPEcific FactoR Embedded Normalization (SuperNorm), that explicitly considers the intra-connection information within each node-induced subgraph. To this end, we embed the subgraph-specific factor at the beginning and the end of the standard BatchNorm, as well as incorporate graph instance-specific statistics for improved distinguishable capabilities. In the meantime, we provide theoretical analysis to support that, with the elaborated SuperNorm, an arbitrary GNN is at least as powerful as the 1-WL test in distinguishing non-isomorphism graphs. Furthermore, the proposed SuperNorm scheme is also demonstrated to alleviate the over-smoothing phenomenon. Experimental results related to predictions of graph, node, and link properties on the eight popular datasets demonstrate the effectiveness of the proposed method. The code is available at.

Benchmark Results

Tested on 7 datasets 1 baseline value reported too low Non-standard metric on 1 dataset

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
136	MVGRL with SuperNorm ext data Hyb ★ proposed	0.9068 ±0.0671	This paper
173	InfoGraph with SuperNorm ext data Hyb ★ proposed	0.9037 ±0.0607	This paper
199	MVGRL GNN baseline actual #199 vs paper #199	0.8993 ±0.0616	actual #199 vs paper #199 paper 0.8993 ±0.0616 prev best: Graph Self-Supervised Learning: A Survey (2021) Improvement within reported uncertainty; not highlighted. paper 0.8993 ±0.0616 Δ at pub 0.0023
257	InfoGraph GNN baseline actual #257 vs paper #257	0.8930 ±0.0514	actual #257 vs paper #257 paper 0.8930 ±0.0514 prev best: Graph Contrastive Learning Automated (ICML 2021) Improvement within reported uncertainty; not highlighted. paper 0.8930 ±0.0514 Δ at pub 0.0029
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗

IMDB-BINARY

Global leaderboard →

Non-default metric. This paper reports ROC-AUC; the dataset default is Accuracy. Values below use ROC-AUC only.

Sorted by ROC-AUC. Highlighted rows are from other papers.

#	Model	ROC-AUC ↑	Paper
1	GraphSNN GNN baseline	0.7983 ±0.0075	This paper
2	GIN GNN baseline	0.7952 ±0.0043	This paper
3	GSN GNN baseline	0.7932 ±0.0072	This paper
4	GCN GNN baseline	0.7884 ±0.0091	This paper
5	GAT GNN baseline	0.7873 ±0.0080	This paper
6	MLP Trad baseline	0.7813 ±0.0045	This paper

OGB

ogbn-products

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	Jacobi GNN global	0.8968	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
2	GPR GNN global	0.8953	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
3	LEMP4HG ext data Hyb global	0.8939	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
4	SAGE GNN global	0.8933	Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
77	SIGN GNN baseline actual #77 vs paper #133 56 places worse	0.8310 ±0.0080 best reported	actual #77 vs paper #133 56 places worse paper 0.8063 ±0.0032 best at pub: PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm (WWW 2022) paper 0.8063 ±0.0032 Δ at pub 0.0247
119	SIGN with SuperNorm GNN ★ proposed	0.8120 ±0.0029	This paper
351	MLP Trad global	0.6605 ±0.0020	Latent Graph Inference using Product Manifolds

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
105	SuperNorm Hyb baseline	0.7786 ±0.0128	This paper
109	GIN GNN 510.0M global	0.7780 ±0.0182	GRPE: Relative Positional Encoding for Graph Transformer
162	BatchNorm GNN baseline	0.7687 ±0.0056	This paper
199	ExpreNorm GNN baseline	0.7605 ±0.0095	This paper
202	NoNorm GNN baseline	0.7601 ±0.0092	This paper
206	UnityNorm GNN baseline	0.7594 ±0.0093	This paper
221	GraphNorm GNN baseline	0.7559 ±0.0099	This paper

ogbl-collab

Global leaderboard →

#	Model	Hits@50 ↑	Paper
1	PROXI code ↗ Trad global	0.7650 ±0.0027	PROXI: Challenging the GNNs for Link Prediction code ↗
2	OGB Leader code ↗ global	0.7129 ±0.0018	PROXI: Challenging the GNNs for Link Prediction code ↗
3	GIDN GNN global	0.7096 ±0.0055	GIDN: A Lightweight Graph Inception Diffusion Network for High-efficient Link Prediction
9	GCN code ↗ GNN global	0.6621 ±0.0033	On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks code ↗
56	SuperNorm Hyb baseline	0.5198 ±0.0087	This paper
89	GroupNorm GNN baseline	0.4543 ±0.0187	This paper
94	MLP Trad global	0.4438 ±0.0347	Weak Models Can be Good Teachers: A Case Study on Link Prediction with MLPs
106	NoNorm GNN baseline	0.3538 ±0.0050	This paper

ogbn-mag

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	LMSPS+LP+MS ext data Hyb global	0.5784 ±0.0022	Long-range Meta-path Search on Large-scale Heterogeneous Graphs
2	SeHGNN+emb+ms code ↗ ext data Hyb global	0.5719 ±0.0012	Simple and Efficient Heterogeneous Graph Neural Network code ↗
3	SeHGNN+ms code ↗ Hyb global	0.5671 ±0.0014	Simple and Efficient Heterogeneous Graph Neural Network code ↗
25	LEGNN with SuperNorm GNN ★ proposed	0.5324 ±0.0013	This paper
27	SIGN GNN baseline actual #27 vs paper #27	0.5289 ±0.0011	actual #27 vs paper #27 paper 0.5289 ±0.0011 prev best: Scalable Graph Neural Networks for Heterogeneous Graphs (2020) paper 0.5289 ±0.0011 Δ at pub 0.0479
57	GraphSAGE code ↗ GNN global	0.4646 ±0.0060	Efficient Heterogeneous Graph Learning via Random Projection code ↗
76	MLP code ↗ Trad global	0.3243	Heterogeneous Graph Representation Learning with Relation Awareness code ↗

MoleculeNet

Tox21

Global leaderboard →

#	Model	ROC-AUC ↑	Paper
1	HIMP Hyb global	0.8740 ±0.0050	Graph convolutions that can finally model local structure
2	GINE w/ VN GNN global	0.8720 ±0.0030	Graph convolutions that can finally model local structure
3	NaiveGINe+ K=3 w/ VN GNN global	0.8700 ±0.0040	Graph convolutions that can finally model local structure
14	GCN GNN global	0.8400 ±0.0040	Graph convolutions that can finally model local structure
315	SuperNorm Hyb baseline	0.6712 ±0.0062	This paper
318	ExpreNorm GNN baseline	0.6598 ±0.0045	This paper
324	UnityNorm GNN baseline	0.6415 ±0.0086	This paper
328	BatchNorm GNN baseline	0.6372 ±0.0057	This paper
332	NoNorm GNN baseline	0.6261 ±0.0045	This paper
333	GraphNorm GNN baseline	0.6244 ±0.0091	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