Rethinking Graph Regularization for Graph Neural Networks

Han Yang, Kaili Ma, James Cheng

Abstract

The graph Laplacian regularization term is usually used in semi-supervised representation learning to provide graph structure information for a model $f(X)$. However, with the recent popularity of graph neural networks (GNNs), directly encoding graph structure $A$ into a model, i.e., $f(A, X)$, has become the more common approach. While we show that graph Laplacian regularization brings little-to-no benefit to existing GNNs, and propose a simple but non-trivial variant of graph Laplacian regularization, called Propagation-regularization (P-reg), to boost the performance of existing GNN models. We provide formal analyses to show that P-reg not only infuses extra information (that is not captured by the traditional graph Laplacian regularization) into GNNs, but also has the capacity equivalent to an infinite-depth graph convolutional network. We demonstrate that P-reg can effectively boost the performance of existing GNN models on both node-level and graph-level tasks across many different datasets.

Benchmark Results

Tested on 5 datasets 12 baseline values reported too low

Tables show presented results in global context (best 3 papers + GCN + MLP).

Classic

Cora

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GraphSAGE+CNA code ↗ GNN global	0.9418 ±0.0033	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
2	GCN+CNA code ↗ GNN global	0.9366 ±0.0048	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
3	TransformerConv code ↗ GNN global	0.9350 ±0.0058	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
21	GCN GNN baseline actual #21 vs paper #568 547 places worse	0.9004 best reported	actual #21 vs paper #568 547 places worse paper 0.8167 ±0.0060 best at pub: SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels (2017) best today: Understanding Heterophily for Graph Neural Networks (ICML 2024) paper 0.8167 ±0.0060 Δ at pub 0.0550 Δ today 0.0837
39	SAGE GNN global	0.8911 ±0.0012	Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment
44	GAT GNN baseline actual #44 vs paper #401 357 places worse	0.8897 ±0.0014 best reported	actual #44 vs paper #401 357 places worse paper 0.8320 ±0.0072 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.8320 ±0.0072 Δ at pub 0.0420 Δ today 0.0577
108	APPNP GNN baseline actual #108 vs paper #414 306 places worse	0.8787 best reported	actual #108 vs paper #414 306 places worse paper 0.8312 ±0.0044 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Feature Transportation Improves Graph Neural Networks (AAAI 2023) paper 0.8312 ±0.0044 Δ at pub 0.0458 Δ today 0.0475
307	GraphMix GNN baseline actual #307 vs paper #360 53 places worse	0.8394 ±0.0057 best reported	actual #307 vs paper #360 53 places worse paper 0.8354 ±0.0072 best at pub: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) Difference within reported uncertainty; not counted as underperformance. paper 0.8354 ±0.0072 Δ at pub 0.0040
312	GAT+P-reg GNN ★ proposed	0.8389 ±0.0031	This paper
323	DeepAPPNP GNN baseline	0.8378 ±0.0033	This paper
327	GMNN GNN baseline actual #327 vs paper #413 86 places worse	0.8370 best reported	actual #327 vs paper #413 86 places worse paper 0.8318 ±0.0085 best at pub: Graph Convolutional Neural Networks with Node Transition Probability-based Message Passing and DropNode Regularization (2020) Difference within reported uncertainty; not counted as underperformance. paper 0.8318 ±0.0085 Δ at pub 0.0052
342	BVAT GNN baseline actual #342 vs paper #389 47 places worse	0.8360 ±0.0050 best reported	actual #342 vs paper #389 47 places worse paper 0.8337 ±0.0101 best at pub: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) best today: Metropolis-Hastings Data Augmentation for Graph Neural Networks (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8337 ±0.0101 Δ at pub 0.0023 Δ today 0.0023
389	GCN+P-reg GNN ★ proposed	0.8338 ±0.0086	This paper
466	GraphAT GNN baseline actual #466 vs paper #471 5 places worse	0.8250 best reported	actual #466 vs paper #471 5 places worse paper 0.8246 ±0.0060 best at pub: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) Difference within reported uncertainty; not counted as underperformance. paper 0.8246 ±0.0060 Δ at pub 0.0004
501	GAM GNN baseline	0.8228 ±0.0048	This paper
583	Graph U-Nets GNN baseline	0.8131 ±0.0147	This paper
724	MLP Trad global	0.7768	Understanding Heterophily for Graph Neural Networks

CiteSeer

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	CNA code ↗ GNN global	0.9575 ±0.0058	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
2	IS-GIB code ↗ Hyb global	0.9390 ±0.0187	Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization code ↗
3	EERM code ↗ GNN global	0.9112 ±0.0145	Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization code ↗
20	APPNP GNN baseline actual #20 vs paper #457 437 places worse	0.8142 ±0.0026 best reported	actual #20 vs paper #457 437 places worse paper 0.7200 ±0.0048 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.7200 ±0.0048 Δ at pub 0.0850 Δ today 0.0942
35	GAT GNN baseline actual #35 vs paper #533 498 places worse	0.8080 ±0.0026 best reported	actual #35 vs paper #533 498 places worse paper 0.7129 ±0.0084 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.7129 ±0.0084 Δ at pub 0.0731 Δ today 0.0951
44	GCN GNN baseline actual #44 vs paper #503 459 places worse	0.8033 ±0.0088 best reported	actual #44 vs paper #503 459 places worse paper 0.7157 ±0.0046 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification (2024) paper 0.7157 ±0.0046 Δ at pub 0.0523 Δ today 0.0876
61	GraphSAGE GNN global	0.7923 ±0.0053	Gophormer: Ego-Graph Transformer for Node Classification
185	GCN+P-reg GNN ★ proposed	0.7483 ±0.0017	This paper
191	GraphMix GNN baseline actual #191 vs paper #239 48 places worse	0.7470 ±0.0059 best reported	actual #191 vs paper #239 48 places worse paper 0.7381 ±0.0085 best today: Metropolis-Hastings Data Augmentation for Graph Neural Networks (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7381 ±0.0085 Δ today 0.0089
230	BVAT GNN baseline actual #230 vs paper #238 8 places worse	0.7400 ±0.0060 best reported	actual #230 vs paper #238 8 places worse paper 0.7383 ±0.0054 best at pub: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) Difference within reported uncertainty; not counted as underperformance. paper 0.7383 ±0.0054 Δ at pub 0.0017
279	GraphAT GNN baseline actual #279 vs paper #279	0.7349 ±0.0038	actual #279 vs paper #279 paper 0.7349 ±0.0038 prev best: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) Improvement within reported uncertainty; not highlighted. paper 0.7349 ±0.0038 Δ at pub 0.0009
339	GMNN GNN baseline actual #339 vs paper #358 19 places worse	0.7290 best reported	actual #339 vs paper #358 19 places worse paper 0.7277 ±0.0143 best at pub: Graph Convolutional Neural Networks with Node Transition Probability-based Message Passing and DropNode Regularization (2020) Difference within reported uncertainty; not counted as underperformance. paper 0.7277 ±0.0143 Δ at pub 0.0013
350	MLP code ↗ Trad global	0.7289 ±0.0010	Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax code ↗
352	GAT+P-reg GNN ★ proposed	0.7286 ±0.0065	This paper
361	GAM GNN baseline	0.7274 ±0.0062	This paper
526	DeepAPPNP GNN baseline	0.7137 ±0.0066	This paper
696	Graph U-Nets GNN baseline	0.6774 ±0.0148	This paper

PubMed

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	LGTL GT global	0.9518 ±0.0011	Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models
2	MixHop (LO) code ↗ GNN global	0.9513 ±0.0038	LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework code ↗
3	GraphSAGE (LO) code ↗ GNN global	0.9511 ±0.0036	LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework code ↗
17	APPNP GNN baseline actual #17 vs paper #439 422 places worse	0.9355 ±0.0060 best reported	actual #17 vs paper #439 422 places worse paper 0.8010 ±0.0026 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework (2024) paper 0.8010 ±0.0026 Δ at pub 0.1040 Δ today 0.1345
18	GCN GNN baseline actual #18 vs paper #571 553 places worse	0.9296 ±0.0015 best reported	actual #18 vs paper #571 553 places worse paper 0.7917 ±0.0037 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7917 ±0.0037 Δ at pub 0.1053 Δ today 0.1379
20	GAT GNN baseline actual #20 vs paper #682 662 places worse	0.9233 ±0.0018 best reported	actual #20 vs paper #682 662 places worse paper 0.7799 ±0.0047 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) best today: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7799 ±0.0047 Δ at pub 0.1171 Δ today 0.1434
116	SAGE GNN global	0.8881 ±0.0015	Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment
210	MLP code ↗ Trad global	0.8690 ±0.0074	On the Equivalence of Graph Convolution and Mixup code ↗
340	GMNN GNN baseline actual #340 vs paper #340	0.8163 ±0.0036	actual #340 vs paper #340 paper 0.8163 ±0.0036 prev best: When Does Self-Supervision Help Graph Convolutional Networks? (ICML 2020) Improvement within reported uncertainty; not highlighted. paper 0.8163 ±0.0036 Δ at pub 0.0029
367	GraphMix GNN baseline actual #367 vs paper #391 24 places worse	0.8110 ±0.0078 best reported	actual #367 vs paper #391 24 places worse paper 0.8076 ±0.0084 best at pub: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) Difference within reported uncertainty; not counted as underperformance. paper 0.8076 ±0.0084 Δ at pub 0.0034
439	GCN+P-reg GNN ★ proposed	0.8011 ±0.0045	This paper
462	BVAT GNN baseline actual #462 vs paper #682 220 places worse	0.7990 ±0.0040 best reported	actual #462 vs paper #682 220 places worse paper 0.7797 ±0.0084 best at pub: GraphMix: Improved Training of GNNs for Semi-Supervised Learning (2019) paper 0.7797 ±0.0084 Δ at pub 0.0193
481	DeepAPPNP GNN baseline	0.7973 ±0.0022	This paper
497	GAM GNN baseline	0.7960 ±0.0063	This paper
581	GraphAT GNN baseline	0.7910 ±0.0020	This paper
652	GAT+P-reg GNN ★ proposed	0.7839 ±0.0027	This paper
699	Graph U-Nets GNN baseline	0.7776 ±0.0084	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
109	GIN GNN baseline actual #109 vs paper #225 116 places worse	0.7780 ±0.0182 best reported	actual #109 vs paper #225 116 places worse paper 0.7547 ±0.0122 best today: GRPE: Relative Positional Encoding for Graph Transformer (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7547 ±0.0122 Δ today 0.0233
145	GIN+Virtual+P-reg GNN ★ proposed	0.7712 ±0.0114	This paper
160	GraphSAGE code ↗ GNN global	0.7690 ±0.0136	SoGCN: Second-Order Graph Convolutional Networks code ↗
167	GIN+P-reg GNN ★ proposed	0.7677 ±0.0141	This paper
183	GIN+Virtual GNN baseline	0.7633 ±0.0152	This paper
184	GCN GNN baseline actual #184 vs paper #196 12 places worse	0.7608 ±0.0141	actual #184 vs paper #196 12 places worse paper 0.7608 ±0.0141 prev best: Wasserstein Embedding for Graph Learning (ICLR 2020) Improvement within reported uncertainty; not highlighted. paper 0.7608 ±0.0141 Δ at pub 0.0008
201	GCN+P-reg GNN ★ proposed	0.7603 ±0.0125	This paper
210	GCN+Virtual+P-reg GNN ★ proposed	0.7581 ±0.0161	This paper
217	GCN+Virtual GNN baseline	0.7567 ±0.0154	This paper

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 baseline actual #14 vs paper #239 225 places worse	0.8400 ±0.0040 best reported	actual #14 vs paper #239 225 places worse paper 0.7475 ±0.0055 best at pub: Memory-Based Graph Networks (ICLR 2020) best today: Graph convolutions that can finally model local structure (2020) paper 0.7475 ±0.0055 Δ at pub 0.0815 Δ today 0.0925
24	GIN GNN baseline actual #24 vs paper #237 213 places worse	0.8290 ±0.0069 best reported	actual #24 vs paper #237 213 places worse paper 0.7489 ±0.0066 best at pub: Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling (2019) paper 0.7489 ±0.0066 Δ at pub 0.0801
127	GCN+Virtual+P-reg GNN ★ proposed	0.7758 ±0.0039	This paper
130	GIN+Virtual+P-reg GNN ★ proposed	0.7751 ±0.0068	This paper
135	GraphSAGE code ↗ GNN global	0.7744 ±0.0038	Pre-training Graph Neural Networks on Molecules by Using Subgraph-Conditioned Graph Information … code ↗
137	GCN+Virtual GNN baseline	0.7742 ±0.0067	This paper
151	GIN+Virtual GNN baseline	0.7704 ±0.0083	This paper
189	GCN+P-reg GNN ★ proposed	0.7586 ±0.0075	This paper
237	GIN+P-reg GNN ★ proposed	0.7490 ±0.0059	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)