  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.
