RelWire: Metric Based Rewiring

Oversquashing is a major hurdle to the application of geometric deep learning and graph neural networks to real world applications. Recent work has found connections between oversquashing and commute times, effective resistance, and the eigengap (or spectral gap) of the underlying graph. Graph rewiring is the most promising technique to alleviate this issue. Some prior work adds edges locally to highly negatively curved subgraphs. These local changes, however, have a small effect on global statistics such as commute times and the eigengap. Other prior work uses the spectrum of the graph Laplacian to target rewiring to increase the eigengap. These approaches, however, make large structural and topological changes to the underlying graph. We use ideas from geometric group theory to present \textsc{RelWire}, a rewiring technique based on the geometry of the graph. We explore topological properties of different rewiring techniques and show that \textsc{RelWire} is Pareto optimal: it has the best balance between improvement in eigengap and commute times and minimizing changes in the topology of the underlying graph, while performing comparably well on downstream tasks.