Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
This addresses performance issues in graph neural networks for applications like heterophilic data analysis, though it appears incremental as it builds on existing spectral gap methods.
The paper tackles the problems of over-squashing and over-smoothing in Message Passing Graph Neural Networks by proposing a spectral gap optimization framework that deletes edges, showing effectiveness on large heterophilic datasets.
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.