Leave Graphs Alone: Addressing Over-Squashing without Rewiring
This offers a new approach for improving graph neural network performance on heterophilic tasks, addressing a known bottleneck without graph rewiring.
The paper tackles the over-squashing problem in graph neural networks by using Graph Echo State Networks (GESNs), achieving significantly better accuracy on six heterophilic node classification tasks without altering graph connectivity.
Recent works have investigated the role of graph bottlenecks in preventing long-range information propagation in message-passing graph neural networks, causing the so-called `over-squashing' phenomenon. As a remedy, graph rewiring mechanisms have been proposed as preprocessing steps. Graph Echo State Networks (GESNs) are a reservoir computing model for graphs, where node embeddings are recursively computed by an untrained message-passing function. In this paper, we show that GESNs can achieve a significantly better accuracy on six heterophilic node classification tasks without altering the graph connectivity, thus suggesting a different route for addressing the over-squashing problem.