{"ID":2922115,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-02T14:42:14.75819314Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.00757","arxiv_id":"2606.00757","title":"RADE: Random Add-Drop Edge as a Regularizer","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.","short_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 connecti...","url_abs":"https://arxiv.org/abs/2606.00757","url_pdf":"https://arxiv.org/pdf/2606.00757v1","authors":"[\"Danial Saber\",\"Amirali Salehi-Abari\"]","published":"2026-05-30T14:47:04Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[\"Graph Neural Network\"]","has_code":false}