Improving Message-Passing GNNs by Asynchronous Aggregation

Message passing (MP) is a popular paradigm for designing graph neural networks (GNNs), which iteratively aggregates neighbor information and updates node embeddings. However, this paradigm suffers from several issues: First, long-range information struggles to be fully utilized, known as over-squashing. Second, excessive MP layers lead to indistinguishable representations, referred to as over-smoothing. Finally, vanilla MPNNs fail to meet the ability of training in heterophilic graphs. In this paper, we provide a unified insight into these defects: node embeddings are sent to neighbors at a constant "pace" and are aggregated immediately. Such synchronicity causes embeddings closer to the output to be more important, i.e. local priority, manifesting the aforementioned issues. Based on this, Asyn-MPNN, an asynchronous framework that customizes the speed of information aggregation, is proposed, which can unify many popular GNNs. We further propose the automated asynchronous (a Asyn) layer, which achieves effects similar to Asyn-MPNN but without introducing extra hyperparameters and can be integrated into any GNN. aAsyn-MPNN validates its performance through extensive experiments on both graph-level and node-level tasks and achieves leading results on tasks from long-range graph benchmark.