[Papers Review] Summaries of Papers Focusing on Graph Rewiring to Address Over-Squashing

Note that all summaries here are for personal purpose to better understand mathematical details of essential Theorems and Lemmas for each rewiring approach and thus may not be appropriate for others who want to get the general glimpse or overview of the papers.

Graph Rewiring Strategies

1. GDC

• Paper : Diffusion Improves Graph Learning, Gasteiger et al, 2019

• Summary Note : 2019, Gasteiger et al, GDC (DIGL)

• Description :

  • Shows direct correspondence between graph diffusion based message passing scheme and spectral graph covolution with the particular choices of diffusion coefficients equivalent to a polynomial filter.

  • Suggest a model GDC (Graph Diffusion Convolution), which is a spectral graph diffusion that combines the strengths of both spatial (message passing) and spectral methods.

2. BLEND

• Paper : Beltrami Flow and Neural Diffusion on Graphs, Chamberlain et al, 2021

• Summary Note : 2021, chamberlain, BLEND

• Description :

  • Adopt the concept of discretised Beltrami flow on graphs to model a non-Euclidean graph diffusion PDE that evolves the graph embeddings in joint space (feature and positional coordinates).

3. FoSR

• Paper : FoSR: First-order spectral rewiring for addressing oversquashing in GNNs, Karhadkar et al, 2022

• Summary Note : 2023, Karhadkar, FoSR

• Description :

  • Base architecture is relational GIN that uses separate aggregation functions for original graph and rewired one to preserve graph topology while easing the information flow across the graph.

  • Use spectral gap (first non-zero eigenvalue of graph laplacian) as a measure of graph connectivity (the ease of graph flow) and add an edge that minimizes the change in spectral gap of normalized adjacency matrix ($\large L \, = \, I - A$).

4. GTR

• Paper : Understanding Oversquashing in GNNs through the Lens of Effective Resistance, Black et al, 2022

• Summary Note : 2023, black, ER

• Description :

  • Define total effective resistance by summing up the local effective resistances, which captures local bottleneck between two nodes and use it as an approximation of the total amount of oversquashing in a graph. (greedily add edges that maximize the change in R)

  • Provides the connection (upper bound) between the Jacobian of the graph embeddings with arbitrary size of receptive field and the total effective resistance.

• First two papers are focusing on local (spatial) properties (positional encoding defined on nodes) as an optimization target for graph rewiring algorithms. (not included here, but curvature based rewiring (SDRF, Topping et al, 2022) also is a spatial rewiring as the curvature is locally defined on each edge)

• On the other hand, last two papers (FoSR and GTR) gives more attention to spectral rewiring (spectral gap and total effective resistance) that can capture more global and comprehensive characteristics of graphs.

• Slides