Graph Neural Networks with Non-Recursive Message Passing

Graph neural networks (GNNs) have become the de-facto standard for learning on graphs. GNNs involve a recursive message passing mechanism to recursively aggregate messages from adjacent nodes. It is in line with the topological structures and has dominated the implementation of existing GNN models. However, it causes a critical issue, i.e., messages from high-order neighbors must be transmitted layer by layer. Important high-order neighbors of a node could be trivial to its low-order neighbors, which corrupts long-range messages. In this paper, we propose a simple but effective non-recursive message passing model (nrecGNN) to enable each node to access its multiple-hop neighbors directly. nrecGNN considers neighbors with the same order as a hop set and combines messages within each set to obtain hop-level representations. The final embedding representation of a node is explicitly obtained by aggregating all hop representations in a non-recursive manner. We theoretically prove that nrecGNN has the same expression capacity as its recursive counterpart. Experiments on multiple benchmark datasets of various scales and types demonstrate the superiority of nrecGNN against the state-of-the-art GNNs.