RADE: Random Add-Drop Edge as a Regularizer

Danial Saber, Amirali Salehi-Abari

Abstract

Graph Neural Networks (GNNs) suffer from overfitting and over-squashing of long-range information. Stochastic graph augmentations (e.g., edge deletion) regularize training against overfitting but can introduce train-inference misalignment and do not improve over-squashing. In contrast, rewiring methods improve connectivity to mitigate over-squashing, but are not designed to regularize training. We propose Random Add-Drop Edge (RADE), a stochastic graph augmentation method that jointly drops and adds edges to address both overfitting and over-squashing simultaneously. RADE is provably designed to align training and inference so that random augmentations regularize training without distribution shift, while supporting long-range communication at inference. We further propose and study a mini-batch gradient-norm balancing algorithm that adapts deletion and addition rates during training, rendering RADE hyperparameter-free in practice. Experiments on node- and graph-classification benchmarks show that RADE is a strong regularizer and mitigates over-squashing. Ablations support the roles of train-inference alignment, adaptive rate selection, and the complementary effects of random edge deletion and edge addition.

Benchmark Results

Tested on 8 datasets 22 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 #654 633 places worse	0.9004 best reported	actual #21 vs paper #654 633 places worse paper 0.8010 ±0.0064 best at pub: Understanding Heterophily for Graph Neural Networks (ICML 2024) paper 0.8010 ±0.0064 Δ at pub 0.0994
39	SAGE GNN global	0.8911 ±0.0012	Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment
43	DropEdge Trad baseline actual #43 vs paper #647 604 places worse	0.8900 best reported	actual #43 vs paper #647 604 places worse paper 0.8028 ±0.0034 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) paper 0.8028 ±0.0034 Δ at pub 0.0872
44	GAT GNN baseline actual #44 vs paper #730 686 places worse	0.8897 ±0.0014 best reported	actual #44 vs paper #730 686 places worse paper 0.7744 ±0.0103 best at pub: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7744 ±0.0103 Δ at pub 0.1153
165	GIN GNN baseline actual #165 vs paper #716 551 places worse	0.8660 ±0.0091 best reported	actual #165 vs paper #716 551 places worse paper 0.7796 ±0.0266 best at pub: Large Language Model Meets Graph Neural Network in Knowledge Distillation (AAAI 2024) paper 0.7796 ±0.0266 Δ at pub 0.0864
605	RADE-OF GNN ★ proposed	0.8108 ±0.0106	This paper
617	RADE-OFS GNN ★ proposed	0.8082 ±0.0124	This paper
619	DropNode Trad baseline actual #619 vs paper #619	0.8080 ±0.0055	actual #619 vs paper #619 paper 0.8080 ±0.0055 prev best: xAI-Drop: Don't Use What You Cannot Explain (LoG 2024) paper 0.8080 ±0.0055 Δ at pub 0.0080
623	Dropout Trad baseline	0.8076 ±0.0085	This paper
627	DropMessage Trad baseline	0.8065 ±0.0101	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 ↗
24	DropEdge Trad baseline actual #24 vs paper #639 615 places worse	0.8130 best reported	actual #24 vs paper #639 615 places worse paper 0.6942 ±0.0116 best at pub: Tackling Over-Smoothing for General Graph Convolutional Networks (2020) paper 0.6942 ±0.0116 Δ at pub 0.1188
35	GAT GNN baseline actual #35 vs paper #769 734 places worse	0.8080 ±0.0026 best reported	actual #35 vs paper #769 734 places worse paper 0.6512 ±0.0080 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) paper 0.6512 ±0.0080 Δ at pub 0.1568
44	GCN GNN baseline actual #44 vs paper #648 604 places worse	0.8033 ±0.0088 best reported	actual #44 vs paper #648 604 places worse paper 0.6912 ±0.0110 best at pub: NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification (2024) paper 0.6912 ±0.0110 Δ at pub 0.1121
61	GraphSAGE GNN global	0.7923 ±0.0053	Gophormer: Ego-Graph Transformer for Node Classification
350	MLP code ↗ Trad global	0.7289 ±0.0010	Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax code ↗
389	GIN GNN baseline actual #389 vs paper #792 403 places worse	0.7250 ±0.0080 best reported	actual #389 vs paper #792 403 places worse paper 0.6404 ±0.0264 best at pub: Towards Self-Explainable Graph Neural Network (2021) paper 0.6404 ±0.0264 Δ at pub 0.0846
613	RADE-OF GNN ★ proposed	0.7020 ±0.0131	This paper
616	RADE-OFS GNN ★ proposed	0.7012 ±0.0225	This paper
621	Dropout Trad baseline	0.7004 ±0.0058	This paper
672	DropNode Trad baseline	0.6842 ±0.0143	This paper
688	DropMessage Trad baseline	0.6794 ±0.0182	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 ↗
18	GCN GNN baseline actual #18 vs paper #715 697 places worse	0.9296 ±0.0015 best reported	actual #18 vs paper #715 697 places worse paper 0.7749 ±0.0042 best at pub: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7749 ±0.0042 Δ at pub 0.1547
20	GAT GNN baseline actual #20 vs paper #813 793 places worse	0.9233 ±0.0018 best reported	actual #20 vs paper #813 793 places worse paper 0.7346 ±0.0096 best at pub: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models (2025) paper 0.7346 ±0.0096 Δ at pub 0.1887
43	DropEdge Trad baseline actual #43 vs paper #694 651 places worse	0.9090 best reported	actual #43 vs paper #694 651 places worse paper 0.7780 ±0.0038 best at pub: Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping (2021) paper 0.7780 ±0.0038 Δ at pub 0.1310
116	SAGE GNN global	0.8881 ±0.0015	Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment
157	GIN GNN baseline actual #157 vs paper #775 618 places worse	0.8810 best reported	actual #157 vs paper #775 618 places worse paper 0.7588 ±0.0019 best at pub: UGSL: A Unified Framework for Benchmarking Graph Structure Learning (2023) paper 0.7588 ±0.0019 Δ at pub 0.1222
210	MLP code ↗ Trad global	0.8690 ±0.0074	On the Equivalence of Graph Convolution and Mixup code ↗
558	DropMessage Trad baseline actual #558 vs paper #709 151 places worse	0.7920 best reported	actual #558 vs paper #709 151 places worse paper 0.7757 ±0.0040 best at pub: Oversmoothing alleviation in graph neural networks: a survey and unified view (2024) paper 0.7757 ±0.0040 Δ at pub 0.0163
661	RADE-OFS GNN ★ proposed	0.7824 ±0.0085	This paper
675	RADE-OF GNN ★ proposed	0.7804 ±0.0080	This paper
702	Dropout Trad baseline	0.7770 ±0.0072	This paper
705	DropNode Trad baseline	0.7768 ±0.0064	This paper

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 baseline actual #39 vs paper #479 440 places worse	0.9330 ±0.0290 best reported	actual #39 vs paper #479 440 places worse paper 0.8422 ±0.0612 best at pub: ProtGNN: Towards Self-Explaining Graph Neural Networks (AAAI 2021) Difference within reported uncertainty; not counted as underperformance. paper 0.8422 ±0.0612 Δ at pub 0.0908
63	GCN GNN baseline actual #63 vs paper #484 421 places worse	0.9220 ±0.0440 best reported	actual #63 vs paper #484 421 places worse paper 0.8400 ±0.0800 best at pub: Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature (KDD 2025) paper 0.8400 ±0.0800 Δ at pub 0.0820
116	DropEdge Trad baseline actual #116 vs paper #437 321 places worse	0.9100 ±0.0570 best reported	actual #116 vs paper #437 321 places worse paper 0.8555 ±0.0607 best at pub: Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8555 ±0.0607 Δ at pub 0.0545
158	GraphSAGE code ↗ GNN global	0.9040 ±0.0780	Asynchronous Neural Networks for Learning in Graphs code ↗
183	GAT GNN baseline actual #183 vs paper #510 327 places worse	0.9010 ±0.0580 best reported	actual #183 vs paper #510 327 places worse paper 0.8345 ±0.0571 best at pub: Breaking the Limits of Message Passing Graph Neural Networks (ICML 2021) best today: The Expressive Power of Graph Neural Networks: A Survey (2023) paper 0.8345 ±0.0571 Δ at pub 0.0665 Δ today 0.0665
363	DropNode Trad baseline actual #363 vs paper #447 84 places worse	0.8750 best reported	actual #363 vs paper #447 84 places worse paper 0.8502 ±0.0599 best at pub: SoftEdge: Regularizing Graph Classification with Random Soft Edges (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8502 ±0.0599 Δ at pub 0.0248
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
411	RADE-OFS GNN ★ proposed	0.8624 ±0.0679	This paper
415	RADE-OF GNN ★ proposed	0.8616 ±0.0562	This paper
421	DropMessage Trad baseline	0.8608 ±0.0739	This paper
473	Dropout Trad baseline	0.8441 ±0.0894	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 ↗
32	GIN GNN baseline actual #32 vs paper #229 197 places worse	0.7880 ±0.0410 best reported	actual #32 vs paper #229 197 places worse paper 0.7519 ±0.0527 best at pub: Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions? (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7519 ±0.0527 Δ at pub 0.0361
49	GAT GNN baseline actual #49 vs paper #180 131 places worse	0.7800 ±0.0300 best reported	actual #49 vs paper #180 131 places worse paper 0.7564 ±0.0512 best at pub: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7564 ±0.0512 Δ at pub 0.0236
67	SAGE GNN global	0.7726 ±0.0228	Semi-Supervised Hierarchical Graph Classification
148	GCN GNN baseline actual #148 vs paper #208 60 places worse	0.7600 ±0.0320 best reported	actual #148 vs paper #208 60 places worse paper 0.7537 ±0.0015 best at pub: CI-GNN: A Granger Causality-Inspired Graph Neural Network for Interpretable Brain Network-Based Psychiatric Diagnosis (2023) best today: Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors (2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7537 ±0.0015 Δ at pub 0.0063 Δ today 0.0063
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
163	RADE-OFS GNN ★ proposed	0.7584 ±0.0344	This paper
182	RADE-OF GNN ★ proposed	0.7562 ±0.0186	This paper
193	DropEdge Trad baseline actual #193 vs paper #219 26 places worse	0.7550 ±0.0020 best reported	actual #193 vs paper #219 26 places worse paper 0.7529 ±0.0274 best at pub: SoftEdge: Regularizing Graph Classification with Random Soft Edges (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7529 ±0.0274 Δ at pub 0.0021
198	DropMessage Trad baseline	0.7545 ±0.0380	This paper
204	Dropout Trad baseline	0.7540 ±0.0441	This paper
234	DropNode Trad baseline actual #234 vs paper #245 11 places worse	0.7511 ±0.0300 best reported	actual #234 vs paper #245 11 places worse paper 0.7501 ±0.0429 best at pub: Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications (NeurIPS 2023) Difference within reported uncertainty; not counted as underperformance. paper 0.7501 ±0.0429 Δ at pub 0.0010

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 #261 152 places worse	0.7780 ±0.0182 best reported	actual #109 vs paper #261 152 places worse paper 0.7384 ±0.0125 best at pub: GRPE: Relative Positional Encoding for Graph Transformer (2022) paper 0.7384 ±0.0125 Δ at pub 0.0396
140	GAT GNN baseline actual #140 vs paper #294 154 places worse	0.7717 ±0.0137 best reported	actual #140 vs paper #294 154 places worse paper 0.6841 ±0.0143 best at pub: Do We Need Anisotropic Graph Neural Networks? (ICLR 2021) paper 0.6841 ±0.0143 Δ at pub 0.0876
160	GraphSAGE code ↗ GNN global	0.7690 ±0.0136	SoGCN: Second-Order Graph Convolutional Networks code ↗
184	GCN GNN baseline actual #184 vs paper #234 50 places worse	0.7630 ±0.0030 best reported	actual #184 vs paper #234 50 places worse paper 0.7521 ±0.0124 best at pub: Motif-based Graph Representation Learning with Application to Chemical Molecules (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7521 ±0.0124 Δ at pub 0.0109
185	RADE-OFS GNN ★ proposed	0.7628 ±0.0141	This paper
188	DropEdge Trad baseline actual #188 vs paper #201 13 places worse	0.7620 ±0.0100 best reported	actual #188 vs paper #201 13 places worse paper 0.7601 ±0.0054 best at pub: Automated Data Augmentations for Graph Classification (ICLR 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.7601 ±0.0054 Δ at pub 0.0019
196	RADE-OF GNN ★ proposed	0.7609 ±0.0124	This paper
200	DropNode Trad baseline actual #200 vs paper #200	0.7604 ±0.0100	actual #200 vs paper #200 paper 0.7604 ±0.0100 prev best: Graph Mixup with Soft Alignments (ICML 2023) Improvement within reported uncertainty; not highlighted. paper 0.7604 ±0.0100 Δ at pub 0.0108
255	DropMessage Trad baseline	0.7421 ±0.0107	This paper
260	Dropout Trad baseline	0.7400 ±0.0094	This paper

ogbn-arxiv

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GIANT-XRT code ↗ Hyb global	0.7612 ±0.0016	Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction code ↗
2	GEGCN Hyb global	0.7576 ±0.0064	Geometric Evolution Graph Convolutional Networks: Enhancing Graph Representation Learning via …
3	AGDN GNN global	0.7522 ±0.0007	Geometric Evolution Graph Convolutional Networks: Enhancing Graph Representation Learning via …
15	GAT GNN baseline actual #15 vs paper #87 72 places worse	0.7365 ±0.0011 best reported	actual #15 vs paper #87 72 places worse paper 0.6951 ±0.0042 best at pub: Fully-inductive Node Classification on Arbitrary Graphs (ICLR 2024) paper 0.6951 ±0.0042 Δ at pub 0.0414
23	GCN GNN baseline actual #23 vs paper #80 57 places worse	0.7300 ±0.0017 best reported	actual #23 vs paper #80 57 places worse paper 0.7051 ±0.0014 best at pub: Geometric Evolution Graph Convolutional Networks: Enhancing Graph Representation Learning via Ricci Flow (2026) paper 0.7051 ±0.0014 Δ at pub 0.0249
25	GraphSAGE GNN global	0.7277 ±0.0016	Geometric Evolution Graph Convolutional Networks: Enhancing Graph Representation Learning via …
50	RADE-OF GNN ★ proposed	0.7185 ±0.0032	This paper
59	DropMessage Trad baseline	0.7155 ±0.0020	This paper
62	DropNode Trad baseline	0.7149 ±0.0024	This paper
76	RADE-OFS GNN ★ proposed	0.7095 ±0.0019	This paper
77	Dropout Trad baseline	0.7077 ±0.0042	This paper
81	GIN GNN baseline actual #81 vs paper #81	0.7046 ±0.0019	actual #81 vs paper #81 paper 0.7046 ±0.0019 prev best: FedBook: A Unified Federated Graph Foundation Codebook with Intra-domain and Inter-domain Knowledge Modeling (2025) paper 0.7046 ±0.0019 Δ at pub 0.0153
82	DropEdge Trad baseline	0.7038 ±0.0027	This paper
107	MLP Trad global	0.5765 ±0.0012	Geometric Evolution Graph Convolutional Networks: Enhancing Graph Representation Learning via …

LRGB

Peptides-func

Global leaderboard →

#	Model	AP ↑	Paper
1	S^2GCN code ↗ GNN global	0.7311 ±0.0066	Benchmarking Positional Encodings for GNNs and Graph Transformers code ↗
2	S4G Hyb global	0.7293 ±0.0004	Graph Mamba: Towards Learning on Graphs with State Space Models
3	BuNN code ↗ Hyb global	0.7276 ±0.0065	Bundle Neural Networks for message diffusion on graphs code ↗
4	GCN GNN baseline actual #4 vs paper #161 157 places worse	0.7261 ±0.0011 best reported	actual #4 vs paper #161 157 places worse paper 0.5514 ±0.0054 best at pub: From Message-Passing to Linearized Graph Sequence Models (2026) paper 0.5514 ±0.0054 Δ at pub 0.1747
26	GIN GNN baseline actual #26 vs paper #159 133 places worse	0.7059 ±0.0089 best reported	actual #26 vs paper #159 133 places worse paper 0.5563 ±0.0124 best at pub: From Message-Passing to Linearized Graph Sequence Models (2026) paper 0.5563 ±0.0124 Δ at pub 0.1496
145	RADE-OFS GNN ★ proposed	0.5912 ±0.0091	This paper
146	RADE-OF GNN ★ proposed	0.5882 ±0.0065	This paper
151	DropMessage Trad baseline	0.5848 ±0.0084	This paper
152	GAT GNN baseline actual #152 vs paper #168 16 places worse	0.5842 ±0.0046 best reported	actual #152 vs paper #168 16 places worse paper 0.5316 ±0.0314 best at pub: Graph Triple Attention Network: A Decoupled Perspective (2024) paper 0.5316 ±0.0314 Δ at pub 0.0526
155	DropEdge Trad baseline	0.5818 ±0.0068	This paper
163	Dropout Trad baseline	0.5484 ±0.0045	This paper
166	DropNode Trad baseline	0.5421 ±0.0076	This paper
181	MLP code ↗ Trad global	0.4060 ±0.0021	CIN++: Enhancing Topological Message Passing code ↗

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