Rethink convolution-based graph neural networks (GNN) -- they characteristically suffer from limited expressiveness, over-smoothing, and over-squashing, and require specialized sparse kernels for efficient computation. Here, we design a simple graph learning module entirely free of convolution operators, coined random walk with unifying memory (RUM) neural network, where an RNN merges the topological and semantic graph features along the random walks terminating at each node. Relating the rich literature on RNN behavior and graph topology, we theoretically show and experimentally verify that RUM attenuates the aforementioned symptoms and is more expressive than the Weisfeiler-Lehman (WL) isomorphism test. On a variety of node- and graph-level classification and regression tasks, RUM not only achieves competitive performance, but is also robust, memory-efficient, scalable, and faster than the simplest convolutional GNNs.

本研究解决了基于卷积的图神经网络（GNN）在表现力、过度平滑和过度挤压等方面的局限性。我们提出了一种完全不使用卷积运算的图学习模块——统一记忆随机游走（RUM）神经网络，该网络结合了节点的拓扑和语义特征。研究结果表明，RUM在多种节点和图级分类及回归任务中表现出色，且在效率、鲁棒性以及速度上均优于传统卷积GNN。

非卷积图神经网络