Spectral Graph Pruning Against Over-Squashing and Over-Smoothing

Adarsh Jamadandi, Celia Rubio-Madrigal, Rebekka Burkholz

In the world of Graph Neural Networks (GNNs), researchers have long struggled with two pesky problems: over-squashing and over-smoothing. For years, these were treated like a zero-sum game—fixing one usually made the other worse. However, a new paper presented at NeurIPS 2024 by Jamadandi et al. suggests a counter-intuitive solution: if your graph is performing poorly, try deleting some edges.

TL;DR

Contrary to the belief that over-squashing and over-smoothing are diametrically opposed, this paper proves they can be mitigated simultaneously by strategically pruning edges. By leveraging the "Braess Paradox"—the idea that removing a path can actually improve flow—the authors introduce PROXYDELETE, a computationally efficient algorithm that maximizes the graph's spectral gap to improve both long-range communication and feature distinction.

The Twin Bottlenecks of GNNs

Standard GNNs rely on "message passing," where nodes aggregate information from their neighbors. This leads to two major failure modes:

  1. Over-squashing: When a graph has structural bottlenecks (like a narrow bridge connecting two large clusters), information from distant nodes gets "squashed" into a fixed-size vector, losing critical detail. The standard fix is "rewiring"—adding edges to bypass bottlenecks.
  2. Over-smoothing: As you add more layers (or edges) to fix over-squashing, nodes start to look identical because they all eventually aggregate the same global information. This is especially lethal in heterophilic graphs, where neighbors often belong to different classes.

The "gap" in the literature was the assumption that you must trade one for the other. Adding edges reduces over-squashing but accelerates over-smoothing. The authors asked: Can we find a way to increase the efficiency of information flow (spectral gap) while actually slowing down the rate at which features wash out?

Methods: Spectral Graph Theory and the Braess Paradox

The authors turn to spectral graph theory, specifically the spectral gap ($\lambda_1$) of the normalized Laplacian. A larger spectral gap generally means a better-connected graph with fewer bottlenecks.

Inspired by a phenomenon in traffic engineering where closing a road can actually reduce congestion, the authors prove that deleting specific edges can increase the spectral gap. This allows for better information flow (less over-squashing) without the "feature-mixing" baggage that comes with adding new edges.

A toy graph demonstrating the Braess phenomenon where edge deletion (G-) increases the spectral gap compared to the original graph (G).

Algorithms: PROXYDELETE and PROXYADD

Calculating eigenvalues exactly is computationally expensive ($O(n^3)$). To make this practical for real-world graphs, the authors developed:

  • PROXYDELETE: A greedy algorithm that uses Matrix Perturbation Theory to estimate how much the spectral gap will change if a specific edge is removed. This reduces the complexity to a much more manageable level.
  • Eldan’s Criterion: A more theoretically rigorous (but slower) method used as a baseline to provide guarantees on when pruning will definitely help.

Key Insights and Ideas

  • The Myth of the Trade-off: The paper provides a minimal example showing that an edge deletion can increase the spectral gap (fixing over-squashing) while simultaneously making node representations more informative (fixing over-smoothing).
  • Pruning as a Feature: Pruning isn't just about making models smaller or faster (the "Lottery Ticket Hypothesis"); it's a structural regularizer. In heterophilic settings, PROXYDELETE naturally tends to remove edges between nodes of different classes, preserving unique features.
Smoothing tests on toy graphs and the Texas dataset showing that edge deletion delays over-smoothing (maintaining lower MSE at higher smoothing orders).
  • Initialization Matters: They show that you can prune the graph at initialization based purely on topology, without looking at labels or features, and still find "winning subgraphs" that outperform the original dense graph.

Key Results

The researchers tested their approach across a wide variety of benchmarks, including the Long Range Graph Benchmark (LRGB), heterophilic datasets (Roman-Empire, Amazon-Ratings), and homophilic datasets (Cora, Citeseer).

  • State-of-the-Art Performance: On the LRGB Peptides-struct task, PROXYDELETE achieved a Mean Absolute Error (MAE) of 0.2470, outperforming strong baselines like FoSR and DRew.
  • Heterophilic Boost: On the Roman-Empire dataset, adding PROXYDELETE to a standard GCN boosted accuracy from ~70% to ~78%.
  • Efficiency: PROXYDELETE is significantly faster than curvature-based rewiring methods (like SDRF). For example, on the Squirrel dataset, SDRF took ~155 seconds while PROXYDELETE took only ~7 seconds for 50 edge modifications.
  • Dirichlet Energy: Qualitative analysis showed that their pruning method slows down the decay of Dirichlet energy, confirming that it effectively combats over-smoothing in deep networks.

Limitations and Future Work

While highly effective, the approach has a few limitations. The current proxy method can struggle when a graph has multiple identical eigenvalues (multiplicity), as the algorithm must choose one eigenvector to follow. Additionally, while the authors argue that spectral pruning works without labels, a purely topological approach might occasionally remove an edge that was actually useful for a specific downstream task. Finally, while much faster than $O(n^3)$ methods, the greedy nature of the algorithm still requires iterative updates, suggesting future work could explore batch-pruning techniques to scale to massive graphs.

By proving that "less is more," this paper opens up a new frontier for graph preprocessing: one where we don't just ask what information to add, but what noise we should remove.

Summary updated

Abstract

Message Passing Graph Neural Networks are known to suffer from two problems that are sometimes believed to be diametrically opposed: over-squashing and over-smoothing. The former results from topological bottlenecks that hamper the information flow from distant nodes and are mitigated by spectral gap maximization, primarily, by means of edge additions. However, such additions often promote over-smoothing that renders nodes of different classes less distinguishable. Inspired by the Braess phenomenon, we argue that deleting edges can address over-squashing and over-smoothing simultaneously. This insight explains how edge deletions can improve generalization, thus connecting spectral gap optimization to a seemingly disconnected objective of reducing computational resources by pruning graphs for lottery tickets. To this end, we propose a computationally effective spectral gap optimization framework to add or delete edges and demonstrate its effectiveness on the long range graph benchmark and on larger heterophilous datasets.
BibTeX
@inproceedings{jamadandi2024spectral,
  author = {Adarsh Jamadandi and Celia Rubio-Madrigal and Rebekka Burkholz},
  title = {{Spectral Graph Pruning Against Over-Squashing and Over-Smoothing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=EMkrwJY2de},
}
Figure