Towards Dynamic Message Passing on Graphs
This work addresses a key bottleneck in GNNs for researchers and practitioners in graph learning, offering a more efficient and flexible approach to message passing.
The paper tackles the problem of over-reliance on input topology in graph neural networks (GNNs), which limits message passing efficacy, by proposing a dynamic message-passing mechanism that projects nodes and learnable pseudo nodes into a common space to enable flexible pathways with linear complexity. The resulting GNN model, N^2, demonstrates superior performance on eighteen benchmarks, scales to large-scale datasets, and requires significantly fewer parameters for graph classification.
Message passing plays a vital role in graph neural networks (GNNs) for effective feature learning. However, the over-reliance on input topology diminishes the efficacy of message passing and restricts the ability of GNNs. Despite efforts to mitigate the reliance, existing study encounters message-passing bottlenecks or high computational expense problems, which invokes the demands for flexible message passing with low complexity. In this paper, we propose a novel dynamic message-passing mechanism for GNNs. It projects graph nodes and learnable pseudo nodes into a common space with measurable spatial relations between them. With nodes moving in the space, their evolving relations facilitate flexible pathway construction for a dynamic message-passing process. Associating pseudo nodes to input graphs with their measured relations, graph nodes can communicate with each other intermediately through pseudo nodes under linear complexity. We further develop a GNN model named $\mathtt{\mathbf{N^2}}$ based on our dynamic message-passing mechanism. $\mathtt{\mathbf{N^2}}$ employs a single recurrent layer to recursively generate the displacements of nodes and construct optimal dynamic pathways. Evaluation on eighteen benchmarks demonstrates the superior performance of $\mathtt{\mathbf{N^2}}$ over popular GNNs. $\mathtt{\mathbf{N^2}}$ successfully scales to large-scale benchmarks and requires significantly fewer parameters for graph classification with the shared recurrent layer.