Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

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