mlsanityData to 14 Oct 2026

RADE: Random Add-Drop Edge as a Regularizer

arXiv 2606.00757 ↗First posted 30 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 51 of its 64 references that are in the map. First posted on arXiv 30 May 2026.

Builds on

51 of 64 references.

References · 51

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2021Convex optimizationcited by 2,515
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  8. 2019Simplifying Graph Convolutional Networkscited by 1,477
  9. 2020Graph Contrastive Learning with Augmentationscited by 1,208
  10. 2018Deep Graph Infomaxcited by 1,106
  11. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  12. 2017GradNorm: Gradient Normalization for Adaptive Loss Balancing in Deep Multitask Networkscited by 834
38 more
  1. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  2. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  3. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  4. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  5. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  6. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 584
  7. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  8. 2020Graph Neural Networks in Recommender Systems: A Surveycited by 494
  9. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  10. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  11. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  12. 2019Diffusion Improves Graph Learningcited by 414
  13. 2021Graph Contrastive Learning Automatedcited by 287
  14. 2022Long Range Graph Benchmarkcited by 263
  15. 2016Molecular Graph Convolutions: Moving Beyond Fingerprintscited by 238
  16. 2020Graph Random Neural Network for Semi-Supervised Learning on Graphscited by 213
  17. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  18. 2021Large-Scale Representation Learning on Graphs via Bootstrappingcited by 186
  19. 2021Equivariant Subgraph Aggregation Networkscited by 154
  20. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  21. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  22. 2019Graph Adversarial Training: Dynamically Regularizing Based on Graph Structurecited by 93
  23. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 85
  24. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  25. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  26. 2023On the Connection Between MPNN and Graph Transformercited by 61
  27. 2019k-hop Graph Neural Networkscited by 57
  28. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  29. 2020Multi-hop Attention Graph Neural Networkcited by 53
  30. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  31. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 36
  32. 2023GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentationcited by 31
  33. 2022DropMessage: Unifying Random Dropping for Graph Neural Networkscited by 29
  34. 2020A Survey on Graph Neural Networks for Knowledge Graph Completioncited by 26
  35. 2022Sampling Enclosing Subgraphs for Link Predictioncited by 9
  36. 2023Simplifying Subgraph Representation Learning for Scalable Link Predictioncited by 7
  37. 2023Stochastic Subgraph Neighborhood Pooling for Subgraph Classificationcited by 3
  38. 2025Aggregation Buffer: Revisiting DropEdge with a New Parameter Blockcited by 3

50 most cited of 51 All 51 (JSON)

Built on by

Not cited yet.