RelWire: Metric Based Rewiring

Rishi Sonthalia, Anna Gilbert, Matthew DurhamNeurReps @ NeurIPS 2024 · OpenReview

TL;DR

This paper introduces RELWIRE, a novel graph rewiring technique inspired by geometric group theory, designed to combat "oversquashing" in Graph Neural Networks (GNNs). RELWIRE achieves a superior balance between improving key graph statistics (like eigengap and commute times) and preserving the graph's original topology, outperforming existing methods and showing promise on downstream tasks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data, but their performance is often hampered by a phenomenon called "oversquashing." Oversquashing occurs when nodes in a graph have limited influence on each other, making it difficult for GNNs to propagate information effectively. This limitation is linked to graph properties like commute times and the eigengap (or spectral gap) of the graph's Laplacian.

Graph rewiring, which involves adding edges to a graph, has emerged as a promising solution to alleviate oversquashing. However, existing rewiring methods often fall into two extremes: either they make local changes with limited global impact, or they drastically alter the graph's structure and topology, potentially losing valuable information. The authors aim to bridge this gap by developing a rewiring technique that effectively addresses oversquashing while minimally disturbing the graph's inherent structure.

Methods

The core of this paper is the RELWIRE (Rewiring based on Relations) technique. RELWIRE leverages concepts from geometric group theory to define two novel edge relations based on the graph's geometry: one that captures aspects of negative curvature and another that relates to flat curvature.

Instead of directly optimizing global graph statistics like eigengap or commute time, RELWIRE identifies pairs of edges that are "transverse," a notion related to negative curvature. By adding edges between nodes connected by highly transverse edge pairs, RELWIRE aims to reduce negative curvature in the graph. The selection of which edges to add is weighted by the distance between the nodes, encouraging global rewiring.

To quantify the impact of rewiring on graph structure, the authors introduce two new topological distance measures:

  • Betti Distance: This measure compares the Betti curves of the rewired graph and the original graph, derived from Vietoris-Rips filtrations. Betti curves capture the "birth" and "death" of topological features (like loops) across different scales.
  • Rank Distance: This measure quantifies the difference in the rank of the first homology group (which corresponds to the number of loops) between two graph filtrations.

These topological distances are crucial for evaluating how much a rewiring method alters the graph's underlying structure.

Datasets

The paper evaluates RELWIRE on several real-world datasets:

  • Molecular datasets: ZINC, ESOL, BACE, Lipo, Tox21, Mutag, Proteins, and ENZYMES. These datasets are used for graph regression and classification tasks.
  • WebKb datasets: Texas and Cornell. These are used for analyzing graph properties as edges are added.
  • Other datasets: IMDB, Reddit, Collab.

The authors also mention using a standard barbell graph (two complete graphs connected by a path) as a test case for comparing rewiring methods.

Key Insights and Ideas

  • Pareto Optimality: RELWIRE is shown to be Pareto optimal, meaning it offers the best trade-off between improving graph statistics (eigengap, commute times) and preserving graph topology, outperforming other methods that excel in one aspect but suffer in the other.
  • Topology Matters: The paper strongly suggests that preserving graph topology is crucial for downstream tasks, as methods that drastically alter structure don't always yield better performance. RELWIRE's ability to balance structural preservation with performance gains is a key takeaway.
  • Geometric Group Theory for Graphs: Applying concepts from geometric group theory, particularly notions of curvature and edge relations, provides a novel and effective way to guide graph rewiring.
  • New Topological Metrics: The introduction of Betti and Rank distances offers a principled way to quantify the topological changes induced by graph rewiring, enabling more nuanced comparisons between methods.

Key Results

  • Improved Graph Statistics: RELWIRE consistently improves eigengap and commute times across various datasets, often achieving the second-best results while maintaining low topological distortion.
  • Topology Preservation: RELWIRE exhibits significantly lower Betti distances compared to other methods like FOSR and GTR, indicating a much smaller impact on the graph's topology.
  • Downstream Task Performance: On graph classification tasks, RELWIRE achieves the best mean rank across different GNN architectures. While its performance on graph regression is less dominant, it still shows competitive results, especially with the GCN architecture.
  • Scalability: RELWIRE demonstrates good scalability, with its runtime increasing reasonably with graph size.

Limitations and Future Work

  • Downstream Task Dependence: The paper notes that the effectiveness of graph rewiring, including RELWIRE, can be highly dependent on the specific GNN architecture, the type of data, and the task itself. The authors suggest that more research is needed to understand these dependencies.
  • Hyperparameter Tuning: For practical applications, a hyperparameter search for the number of edges to add (k) is necessary.
  • Further Exploration of Geometric Concepts: The authors suggest that exploring other geometric concepts and their application to graph rewiring could yield further improvements.
  • Understanding "When" Rewiring Helps: While RELWIRE shows promise, the paper acknowledges that a deeper understanding of when graph rewiring is beneficial for specific tasks and data types is still an open area of research.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sonthalia2024relwire,
  author = {Rishi Sonthalia and Anna Gilbert and Matthew Durham},
  title = {{RelWire: Metric Based Rewiring}},
  booktitle = {NeurReps @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=cJUITTiPUT},
}
Figure