Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey
It addresses critical bottlenecks for researchers and practitioners using GNNs, but is incremental as it surveys existing methods rather than introducing new ones.
This survey tackles the problems of oversquashing and oversmoothing in Graph Neural Networks (GNNs), which hinder information flow and reduce expressiveness, by reviewing graph rewiring techniques that modify graph topology to enhance performance.
Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, but their effectiveness is often constrained by two critical challenges: oversquashing, where the excessive compression of information from distant nodes results in significant information loss, and oversmoothing, where repeated message-passing iterations homogenize node representations, obscuring meaningful distinctions. These issues, intrinsically linked to the underlying graph structure, hinder information flow and constrain the expressiveness of GNNs. In this survey, we examine graph rewiring techniques, a class of methods designed to address these structural bottlenecks by modifying graph topology to enhance information diffusion. We provide a comprehensive review of state-of-the-art rewiring approaches, delving into their theoretical underpinnings, practical implementations, and performance trade-offs.