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 more effective spectral gap optimization framework to add or delete edges and demonstrate its effectiveness on large heterophilic datasets.
Introduction
Message Passing Graph Neural Networks (MPNNs) are the standard for learning on graph-structured data. However, their performance is often capped by two structural pathologies: over-squashing and over-smoothing. Over-squashing occurs when information from a large number of distant nodes must be compressed into a fixed-size vector through a topological bottleneck, leading to information loss. Conversely, over-smoothing occurs when repeated message passing causes node features to converge to a uniform value, making them indistinguishable.
Historically, researchers have viewed these as opposing forces. To fix over-squashing, one typically adds edges to create "shortcuts" across the graph. However, these shortcuts often accelerate over-smoothing by increasing the connectivity of the graph. This paper introduces a counter-intuitive solution inspired by the Braess Paradox: deleting edges can actually mitigate both problems simultaneously.
The Braess Paradox and Spectral Rewiring
In traffic engineering, the Braess Paradox describes a situation where removing a road from a congested network can actually improve the overall flow of traffic. The authors apply this logic to graph topology. In spectral graph theory, the "spectral gap" (the first non-zero eigenvalue of the graph Laplacian, $\lambda_2$) is a measure of how well-connected a graph is. A larger spectral gap generally indicates fewer bottlenecks and reduced over-squashing.
While previous methods focused on adding edges to increase the spectral gap, this work demonstrates that strategic edge deletion can achieve the same goal. This is particularly beneficial in heterophilic graphs, where connected nodes often belong to different classes. In these cases, deleting inter-class edges not only increases the spectral gap but also prevents the "blurring" of features between different categories, thereby tackling over-smoothing.
Methodology: PROXYADD and PROXYDELETE
Calculating the change in the spectral gap for every possible edge modification is computationally prohibitive ($O(N^3)$). To address this, the authors propose a framework for Spectral Graph Rewiring using two efficient greedy algorithms:
- PROXYDELETE: Uses Matrix Perturbation Theory to estimate the change in the spectral gap resulting from an edge deletion. This allows the model to identify and prune edges that "clog" the network without full eigenvalue re-calculation.
- PROXYADD: A similar efficient estimation for identifying beneficial edge additions.
By using first-order approximations, the authors transform a complex optimization problem into a manageable preprocessing step that can be performed at initialization.
Key Insights
Pruning as a Structural Optimizer
Pruning is traditionally viewed as a method for model compression or memory saving. This research re-frames pruning as a structural regularizer. By removing "noisy" or bottleneck-inducing edges before training begins, the GNN can learn more robust representations. This connects spectral gap optimization to the Graph Lottery Ticket (GLT) hypothesis, showing that data-agnostic spectral pruning can find "winning subgraphs" that perform as well as dense networks.
Slowing Dirichlet Energy Decay
Over-smoothing can be measured by the decay of Dirichlet energy—a metric of feature distinctness across the graph. The authors demonstrate that their pruning method effectively slows the decay of this energy as the GNN depth increases. This allows for the design of deeper architectures that can capture long-range dependencies without the penalty of feature homogenization.
Experimental Results
The proposed framework was evaluated across several challenging benchmarks:
- Long Range Graph Benchmark (LRGB): On tasks like PascalVOC-SP and Peptides-func, PROXYADD and PROXYDELETE outperformed existing baselines such as DRew and FoSR, proving the efficacy of spectral optimization for handling bottlenecks.
- Heterophilic Datasets: On the Roman-Empire dataset, the method improved GCN accuracy from approximately 70% to 77% by pruning only 20 edges and adding 50. This highlights the "win-win" nature of the approach in non-assortative graphs.
- Efficiency: The spectral pruning method matched the performance of complex "train-prune-rewind" cycles (like Unified Graph Sparsification) while remaining entirely data-agnostic and significantly faster.
Conclusion and Future Work
This work provides a unified perspective on over-squashing and over-smoothing, showing that they are not necessarily a zero-sum trade-off. By leveraging the Braess Paradox and efficient spectral proxies, the authors demonstrate that deleting edges is a powerful tool for improving GNN generalization.
Future research directions include addressing the challenges of eigenvector multiplicity in symmetric graphs and exploring ways to batch edge modifications to scale the approach to even larger, web-scale graphs. Additionally, while the current method is task-agnostic, incorporating task-specific labels could potentially refine which edges are deemed "noisy" for specific downstream predictions.
Summary updated