Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes
This work addresses the limited attention to random walks on edges and higher-order structures in GNNs, offering theoretical insights and practical encodings for researchers in graph machine learning, though it appears incremental by building on existing positional encoding and simplicial network concepts.
The paper tackles the problem of enhancing Graph Neural Networks (GNNs) by systematically analyzing random walks on simplicial complexes, establishing connections between positional encoding methods and proposing new edge-level encodings like EdgeRWSE and Hodge1Lap, with extensive experiments verifying their effectiveness.
Node-level random walk has been widely used to improve Graph Neural Networks. However, there is limited attention to random walk on edge and, more generally, on $k$-simplices. This paper systematically analyzes how random walk on different orders of simplicial complexes (SC) facilitates GNNs in their theoretical expressivity. First, on $0$-simplices or node level, we establish a connection between existing positional encoding (PE) and structure encoding (SE) methods through the bridge of random walk. Second, on $1$-simplices or edge level, we bridge edge-level random walk and Hodge $1$-Laplacians and design corresponding edge PE respectively. In the spatial domain, we directly make use of edge level random walk to construct EdgeRWSE. Based on the spectral analysis of Hodge $1$-Laplcians, we propose Hodge1Lap, a permutation equivariant and expressive edge-level positional encoding. Third, we generalize our theory to random walk on higher-order simplices and propose the general principle to design PE on simplices based on random walk and Hodge Laplacians. Inter-level random walk is also introduced to unify a wide range of simplicial networks. Extensive experiments verify the effectiveness of our random walk-based methods.