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:
- 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.
- 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.
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,
PROXYDELETEnaturally tends to remove edges between nodes of different classes, preserving unique features.
- 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,
PROXYDELETEachieved a Mean Absolute Error (MAE) of 0.2470, outperforming strong baselines like FoSR and DRew. - Heterophilic Boost: On the Roman-Empire dataset, adding
PROXYDELETEto a standard GCN boosted accuracy from ~70% to ~78%. - Efficiency:
PROXYDELETEis significantly faster than curvature-based rewiring methods (like SDRF). For example, on the Squirrel dataset, SDRF took ~155 seconds whilePROXYDELETEtook 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