Ramanujan Graph Rewiring with Non Negative Resistance Curvature
For GNN practitioners, this provides a principled rewiring method to improve long-range dependency learning by mitigating over-squashing.
Ramanujan Propagation rewires graphs to have Ramanujan properties, which guarantee non-negative resistance curvature and alleviate over-squashing in GNNs. It outperforms nine state-of-the-art rewiring techniques on benchmark tasks.
Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.