Spectral Graph Pruning Against Over-Squashing and Over-Smoothing

arXiv:2404.04612v1 Announce Type: new
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 …

abstract arxiv bottlenecks cs.lg eess.sp flow gap graph graph neural networks information networks neural networks nodes pruning results stat.ml the information type