Anti-Symmetric DGN: a stable architecture for Deep Graph Networks
This addresses a key bottleneck in graph learning for researchers and practitioners by providing a stable architecture that enhances long-range information preservation, though it is an incremental improvement over existing DGN methods.
The paper tackles the problem of over-squashing in Deep Graph Networks (DGNs), which limits long-term dependency propagation, by proposing Anti-Symmetric Deep Graph Networks (A-DGNs) that theoretically ensure stability and non-dissipation, leading to improved performance on graph benchmarks and enabling effective learning with dozens of layers.
Deep Graph Networks (DGNs) currently dominate the research landscape of learning from graphs, due to their efficiency and ability to implement an adaptive message-passing scheme between the nodes. However, DGNs are typically limited in their ability to propagate and preserve long-term dependencies between nodes, i.e., they suffer from the over-squashing phenomena. This reduces their effectiveness, since predictive problems may require to capture interactions at different, and possibly large, radii in order to be effectively solved. In this work, we present Anti-Symmetric Deep Graph Networks (A-DGNs), a framework for stable and non-dissipative DGN design, conceived through the lens of ordinary differential equations. We give theoretical proof that our method is stable and non-dissipative, leading to two key results: long-range information between nodes is preserved, and no gradient vanishing or explosion occurs in training. We empirically validate the proposed approach on several graph benchmarks, showing that A-DGN yields to improved performance and enables to learn effectively even when dozens of layers are used.