cs.LGJun 19, 2026

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

Authors: Hugo AttaliRachid El Jouhri

Organizations: Université Sorbonne Paris Nord, CNRS, LIPN, France

Abstract

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.

Explore similar work

CardsList
  1. Schreier-Coset Graph Rewiring

    Jul 29, 2026Aryan Mishra, Randy Martinez, Lizhen LinGraph Neural NetworksGraph Theory

  2. RAwR: Role-Aware Rewiring via Approximate Equitable Partition

    May 10, 2026Riccardo Porcedda, Giuseppe Squillace, Bastian Epping +4Graph Neural NetworksPartitioning