On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems
Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schönlieb
Abstract
A common problem in Message-Passing Neural Networks is oversquashing -- the limited ability to facilitate effective information flow between distant nodes. Oversquashing is attributed to the exponential decay in information transmission as node distances increase. This paper introduces a novel perspective to address oversquashing, leveraging dynamical systems properties of global and local non-dissipativity, that enable the maintenance of a constant information flow rate. We present SWAN, a uniquely parameterized GNN model with antisymmetry both in space and weight domains, as a means to obtain non-dissipativity. Our theoretical analysis asserts that by implementing these properties, SWAN offers an enhanced ability to transmit information over extended distances. Empirical evaluations on synthetic and real-world benchmarks that emphasize long-range interactions validate the theoretical understanding of SWAN, and its ability to mitigate oversquashing.
BibTeX
@article{Gravina_Eliasof_Gallicchio_Bacciu_Schönlieb_2025, title={On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33858}, DOI={10.1609/aaai.v39i16.33858}, abstractNote={A common problem in Message-Passing Neural Networks is oversquashing -- the limited ability to facilitate effective information flow between distant nodes. Oversquashing is attributed to the exponential decay in information transmission as node distances increase. This paper introduces a novel perspective to address oversquashing, leveraging dynamical systems properties of global and local non-dissipativity, that enable the maintenance of a constant information flow rate. We present SWAN, a uniquely parameterized GNN model with antisymmetry both in space and weight domains, as a means to obtain non-dissipativity. Our theoretical analysis asserts that by implementing these properties, SWAN offers an enhanced ability to transmit information over extended distances. Empirical evaluations on synthetic and real-world benchmarks that emphasize long-range interactions validate the theoretical understanding of SWAN, and its ability to mitigate oversquashing.}, number={16}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Gravina, Alessio and Eliasof, Moshe and Gallicchio, Claudio and Bacciu, Davide and Schönlieb, Carola-Bibiane}, year={2025}, month={Apr.}, pages={16906-16914} }