Title: RADE: Random Add-Drop Edge as a Regularizer

Abstract:

Graph Neural Networks (GNNs) are frequently hindered by the dual challenges of overfitting and the inability to effectively capture long-range dependencies, a phenomenon known as over-squashing. While stochastic graph augmentations, such as edge deletion, serve to regularize training and combat overfitting, they often create a misalignment between training and inference phases and fail to alleviate over-squashing issues. Conversely, rewiring techniques enhance connectivity to reduce over-squashing but lack specific design mechanisms for training regularization. To address these limitations, we introduce Random Add-Drop Edge (RADE), a novel stochastic augmentation strategy that simultaneously removes and introduces edges to tackle both overfitting and over-squashing in tandem. RADE is theoretically grounded to ensure alignment between training and inference, allowing random augmentations to regularize the model without inducing distribution shifts, while still facilitating long-range communication during the inference stage. Additionally, we develop and analyze a mini-batch gradient-norm balancing algorithm that dynamically adjusts the rates of edge deletion and addition throughout training, effectively making RADE hyperparameter-free in practical applications. Empirical evaluations on node and graph classification benchmarks demonstrate that RADE functions as a robust regularizer and successfully mitigates over-squashing. Further ablation studies confirm the effectiveness of train-inference alignment, adaptive rate selection, and the synergistic benefits of combining random edge deletion with edge addition.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC