Exposition on Over-squashing Problem of GNNs: Current Methods, Benchmarks and Challenges

Graph-based message-passing neural networks (MPNNs) have achieved remarkable success in both node and graph-level tasks. However, several identified problems, including over-smoothing (OSM), limited expressive power, and oversquashing (OSQ), still restrain the performance of MPNNs. In particular, the latest identified problem, OSQ, reveals that MPNNs generally fail to maintain their learning accuracy with tasks that require long-range dependencies between node pairs. In this work, we present an exposition of the OSQ problem by summarizing its various formulations in the current literature and categorizing existing solutions into three different types. In addition, we also discuss the alignment between OSQ and expressive power plus the trade-off between OSQ and OSM. Furthermore, we summarize the empirical methods proposed by existing works to verify the efficiency of OSQ mitigation approaches, together with illustrations of their computational complexities. Lastly, we identify some open questions that are of interest for further exploration of the OSQ problem.