  Graph neural networks (GNNs) are able to leverage the structure of graph data
by passing messages along the edges of the graph. While this allows GNNs to
learn features depending on the graph structure, for certain graph topologies
it leads to inefficient information propagation and a problem known as
oversquashing. This has recently been linked with the curvature and spectral
gap of the graph. On the other hand, adding edges to the message-passing graph
can lead to increasingly similar node representations and a problem known as
oversmoothing. We propose a computationally efficient algorithm that prevents
oversquashing by systematically adding edges to the graph based on spectral
expansion. We combine this with a relational architecture, which lets the GNN
preserve the original graph structure and provably prevents oversmoothing. We
find experimentally that our algorithm outperforms existing graph rewiring
methods in several graph classification tasks.
