Physics-informed Graph Neural Networks have achieved remarkable performance in learning through graph-structured data by mitigating common GNN challenges such as over-smoothing, over-squashing, and heterophily adaption. Despite these advancements, the development of a simple yet effective paradigm that appropriately integrates previous methods for handling all these challenges is still underway. In this paper, we draw an analogy between the propagation of GNNs and particle systems in physics, proposing a model-agnostic enhancement framework. This framework enriches the graph structure by introducing additional nodes and rewiring connections with both positive and negative weights, guided by node labeling information. We theoretically verify that GNNs enhanced through our approach can effectively circumvent the over-smoothing issue and exhibit robustness against over-squashing. Moreover, we conduct a spectral analysis on the rewired graph to demonstrate that the corresponding GNNs can fit both homophilic and heterophilic graphs. Empirical validations on benchmarks for homophilic, heterophilic graphs, and long-term graph datasets show that GNNs enhanced by our method significantly outperform their original counterparts.

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.