Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint
24/2022

Oversquashing in GNNs through the lens of information contraction and graph expansion

Pradeep Kumar Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon and Guido Montúfar

Abstract

The quality of signal propagation in message-passing graph neural networks (GNNs) strongly influences their expressivity as has been observed in recent works. In particular, for prediction tasks relying on long-range interactions, recursive aggregation of node features can lead to an undesired phenomenon called``oversquashing''. We present a framework for analyzing oversquashing based on information contraction. Our analysis is guided by a model of reliable computation due to von Neumann that lends a new insight into oversquashing as signal quenching in noisy computation graphs. Building on this, we propose a graph rewiring algorithm aimed at alleviating oversquashing. Our algorithm employs a random local edge flip primitive motivated by an expander graph construction. We compare the spectral expansion properties of our algorithm with that of an existing curvature-based non-local rewiring strategy. Synthetic experiments show that while our algorithm in general has a slower rate of expansion, it is overall computationally cheaper, preserves the node degrees exactly and never disconnects the graph.

Received:
Aug 9, 2022
Published:
Aug 12, 2022
Keywords:
graph neural networks, oversquashing, expander graphs, Information Bottleneck, discrete curvature, SDPI

Related publications

inBook
2022 Repository Open Access
Pradeep Kumar Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon and Guido Montúfar

Oversquashing in GNNs through the lens of information contraction and graph expansion

In: 2022 58th Annual Allerton Conference on communication, control, and computing : 27-30 Sept. 2022
Piscataway, N.J. : IEEE, 2022. - p. 9929363