Tackling Graph Oversquashing by Global and Local Non-Dissipativity
<|reference_start|>Tackling Graph Oversquashing by Global and Local Non-Dissipativity: 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 properties of global and local non-dissipativity, that enable the maintenance of a constant information flow rate. Namely, we present SWAN, a uniquely parameterized model GNN with antisymmetry both in space and weight domains, as a means to obtain non-dissipativity. Our theoretical analysis asserts that by achieving 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.<|reference_end|>
@article{gravina2024tackling,
    title={Tackling Graph Oversquashing by Global and Local Non-Dissipativity},
    author={Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu,
  Carola-Bibiane Sch"onlieb},
    journal={arXiv preprint arXiv:2405.01009},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01009},
    primaryClass={cs.LG}
}