Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges

Graph message passing neural networks (MPNNs) have achieved remarkable success in terms of both node and graph level classification tasks [80, 86, 81]. Despite these successes, there are several major problems such as over-smoothing (OSM) [51], limited expressive power [82], and over-squashing (OSQ) [70, 2] that restrict their performance. Established from the earlier days, OSM and limited expressive problems have been well studied and many solutions have been proposed to alleviate these problems [55, 82, 88]. However, the OSQ problem, identified recently in [70], is still a rather mysterious and perplexing topic in the machine learning community. Initially discovered from empirical observations in [2], the OSQ problem can be conceptually interpreted as a phenomenon of information distortion. In deep MPNNs, the rich information from long-range neighbouring nodes becomes overly compressed into a limited information pack due to the graph connectivity and MPNN architecture [70, 40]. This leads to the fact that nodes distant from each other fail to transmit their messages appropriately, causing MPNNs to perform poorly in tasks that require long-term interactions. Although it is seemingly straightforward to intuitively understand the notion of OSQ, quantifying the OSQ problem has become the foremost challenge for studies in this realm.