Non-local Exchange: Introduce Non-locality via Graph Re-wiring to Graph Neural Networks

Graph is an effective data structure to characterize ubiquitous connections as well as evolving behaviors that emerge from the inter-wined system. Limited by the stereotype of node-to-node connections, learning node representations is often confined in a graph diffusion process where local information has been excessively aggregated as the random walk of graph neural networks (GNN) explores far-reaching neighborhoods layer-by-layer. In this regard, tremendous efforts have been made to alleviate feature over-smoothing issues such that current backbones can lend themselves in a deep network architecture. However, not as popular as designing a new GNN, less attention has been paid to underlying topology by graph re-wiring, which is not only mitigating flaws of the random walk but also the over-smoothing risk by reducing unnecessary diffusion in deep layers. Inspired by the human cognition of non-locality, we propose a non-local information exchange mechanism by establishing an express connection to the distant node, instead of propagating information along the (possibly very long) original pathway node-after-node. Since the seek of express connections throughout the graph could be computationally expensive in real-world applications, we propose a re-wiring framework (coined \textit{express messenger} wrapper) to progressively incorporate express links in a non-local manner, which allows us to capture multi-scale feature without using a deep model, thus free of the over-smoothing challenge. We have integrated our \textit{express messenger} wrapper with existing GNN backbones (either using graph convolution or tokenized transformer) and achieved a new record on the Roman-empire dataset along with SOTA performance on both homophilous and heterophilous datasets.