On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912251140636672 |
|---|---|
| author | Gravina, Alessio Eliasof, Moshe Gallicchio, Claudio Bacciu, Davide Schönlieb, Carola-Bibiane |
| author_facet | Gravina, Alessio Eliasof, Moshe Gallicchio, Claudio Bacciu, Davide Schönlieb, Carola-Bibiane |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01009 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems Gravina, Alessio Eliasof, Moshe Gallicchio, Claudio Bacciu, Davide Schönlieb, Carola-Bibiane Machine Learning 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. |
| title | On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2405.01009 |