Rethinking Random Walk in Graph Representation Learning

Abstract

With the help of deep learning, Graph Neural Networks (GNNs) have achieved remarkable progress in various fields. However, due to the limitation of the message passing mechanism of GNNs, there exists an upper limit on its expressiveness. Some high-order GNNs have achieved good results in expressiveness, but they also have shortcomings in complexity and real-world performance. In this paper, we attempt to provide a graph neural network architecture that simultaneously addresses expressiveness, complexity and real-world performance. To this end, we propose Spatially constrained Random walk diffusion structural Encoding (SRE) to encode structural information and can be used for any GNN under our architecture. Our extensive and diverse experiments on datasets of different types and sizes demonstrate the superior expressiveness and state-of-the-art performance of our architecture on real-world tasks.