RADE: Random Add-Drop Edge as a Regularizer

Danial Saber, Amirali Salehi-Abari · 2026

Read RADE: Random Add-Drop Edge as a Regularizer by Danial Saber, Amirali Salehi-Abari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00757.txt.

Introduction

Saber and Salehi-Abari add a training trick for graph neural networks in this 2026 paper. These networks learn from data on linked nodes, but they overfit with ease. They also squash news from far nodes into too small a space. Random edge cuts can curb overfit, yet they can skew what training shows versus real use. Rewiring helps far nodes talk, but it is not built to regularize.

Their method, RADE, both drops and adds edges at random during training. The design keeps training and real use in line, so the random changes add no shift. Added edges also open long-range paths at run time. A small extra algorithm tunes the drop and add rates by gradient norms as training runs. That makes the method near free of hand-set knobs. On node and graph tests, the authors report, RADE curbs overfit and eases over-squashing at once.

Catalog record

CREATORDanial Saber, Amirali Salehi-Abari
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00757

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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. 1 Introduction Graph Neural Networks (GNNs) ( 23 ; 38 ; 46 ) are neural networks designed for relational data (e.g., social networks, protein-protein networks, etc.), with diverse applications such as recommender systems ( 58 ) , knowledge graph completion ( 5 ) , and molecular property prediction ( 30 ) . The dominant paradigm of GNNs is Message-Passing Neural Networks (MPNNs) ( 22 ) , in which each node iteratively aggregates and transforms messages from its neighbors. Despite GNNs’ success, their generalizability faces several challenges, including limited expressiveness ( 7 ) , over-smoothing ( 34 ) , over-squashing ( 3 ) , and overfitting. We focus on two problems of overfitting , a widespread challenge in machine learning, and over-squashing , a distinctive challenge for MPNNs. Over-squashing occurs when the set of nodes that influence a node’s representation through message passing expands rapidly as the number of layers increases, forcing a lot of information to be compressed into a fixed-size embedding ( 3 ) . This limits the ability to capture higher-order and long-range dependencies in graphs. Prior work addresses overfitting and over-squashing largely in separation. To reduce overfitting in GNNs, common approaches include penalty-based regularization (e.g., weight decay), architectural regularization (e.g., Dropout ( 50 ) ), and stochastic graph augmentation as an implicit regularizer—mostly in the form of deletion-based perturbations (e.g., DropEdge ( 43 ) ). Of special interest for GNNs is graph augmentation, but it is often tuning-sensitive: weak perturbations have little effect, while strong ones remove useful graph signal. Also, training on perturbed views can create train-inference misalignment unless an explicit correction is applied. To mitigate over-squashing, existing methods typically increase connectivity through rewiring or shortcut edges ( 1 ; 4 ; 29 ; 3 ) . These methods can improve long-range information flow, but the extent of rewiring must still be tuned, and simple random edge addition is less emphasized than more structured surgical rewiring. Looking across these two bodies of work, stochastic augmentations regularize training without improving long-range communication, whereas rewiring methods—viewed as a form of augmentation—improve connectivity without regularizing. This gap calls for a unified augmentation framework that regularizes training and, when needed, improves long-range connectivity against over-squashing. Since random edge addition has the potential to be a stochastic regularizer and to facilitate long-range connectivity, a natural question arises: can random edge addition be combined with edge deletion so that the same augmentation both regularizes training and, when useful, improves long-range communication? The main difficulty is train-inference alignment, since training on randomly perturbed graphs but inferring on a fixed graph can induce misalignment or distribution shift. A second practical challenge is controlling the deletion and addition rates without dataset-specific tuning. We propose Random Add-Drop Edge (RADE) , a stochastic topology augmentation that randomly drops existing edges and adds non-edges during training, with corrections for train-inference alignment. We introduce two variants of RADE. RADE-OF solely targets overfitting: it corrects both deletion and addition effects, so that training-time message aggregation, in expectation, matches the aggregation of the input graph at inference. Thus, the random perturbations act as training-time regularization without systematically shifting the inference rule. RADE-OFS targets both overfitting and over-squashing: it corrects the deletion effect but keeps the expected contribution of added edges at inference, thus preserving the regularization benefit of stochastic perturbations while creating additional communication paths for long-range information flow. For both variants, we further show that the regularization effects of random deletion and addition are generally not interchangeable. We also introduce a mini-batch gradient-norm balancing rule that adapts the drop/add rates during training, thereby making RADE practically hyperparameter-free. Our extensive evaluation across diverse node- and graph-level datasets and various backbone models (e.g., GCN, GIN, and GAT) confirms RADE’s potential for both implicit regularization and over-squashing mitigation. RADE-OF consistently outperforms competitive regularizers while RADE-OFS is the most effective when long-range communication is important: it yields the largest gains on over-squashing-prone graph classification benchmarks ( 45 ) and datasets requiring long-range interactions (e.g., peptides-func) ( 16 ) . Ablations further verify the benefit of our train-inference alignment rules (i.e., removing alignment rules downgrades performance), the performance gains of our adaptive rate selection (i.e., adaptively selected drop/add rates outperform fixed, hyperparameter-tuned choices), and the complementary effects of random drop and addition (i.e., RADE outperforms the drop-only or add-only variants). Overall, RADE appears to be a simple and effective augmentation framework for regularizing against overfitting and mitigating over-squashing. 2 Related Work Data augmentation for GNNs perturbs the input graph through its topology (edges/nodes) or attributes (node/edge features). Many augmentations are stochastic regularizers against overfitting, while others address structural limitations of MPNNs (e.g., over-squashing). We review prior work through two lenses: overfitting and over-squashing. Overfitting. Stochastic augmentations act as implicit regularizers against overfitting. Examples include random edge deletion ( 43 ) , feature/representation noise injection ( 54 ; 19 ; 60 ) , feature/message masking ( 51 ; 18 ; 62 ) , and node dropping to generate alternative views ( 20 ; 44 ; 63 ; 36 ) . These perturbations can also mitigate over-smoothing in deep GNNs by weakening or randomizing propagation pathways ( 43 ; 51 ; 18 ) . Over-squashing. To improve long-range information flow, many methods add or rewire connectivity to alleviate bottlenecks ( 3 ) . This includes virtual nodes ( 12 ; 49 ) , higher-order structures ( 8 ; 9 ) , last-layer full connectivity ( 3 ) , diffusion/multi-hop rewiring ( 1 ; 2 ; 55 ; 40 ; 21 ; 11 ; 6 ; 24 ) , fully-connected attention in graph transformers ( 61 ; 32 ; 42 ) , and targeted edge addition around bottlenecks ( 52 ; 29 ) . Other objectives. Augmentations have also been used to improve expressiveness by ensembling diverse substructure views ( 41 ; 7 ) , to support robustness/denoising under structural noise or adversaries ( 57 ; 65 ; 17 ) , and to enable scalable stochastic training via sampled neighborhoods ( 25 ; 13 ; 14 ; 27 ; 64 ; 35 ) . Our work. Our work bridges two separate uses of graph augmentation—regularization against overfitting and connectivity enrichment against over-squashing—through random edge addition. Existing regularizers mostly drop

Read the complete text