FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
This addresses inefficiencies in GNNs for certain graph topologies, which is an incremental improvement for machine learning practitioners working with graph data.
The paper tackles the problem of oversquashing in graph neural networks (GNNs) by proposing a computationally efficient algorithm that adds edges based on spectral expansion to improve information propagation, and it outperforms existing graph rewiring methods in graph classification tasks.
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.