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.

图神经网络中广泛使用了节点级随机游走以提高性能，但对于边缘和更一般地，k-单形的随机游走关注有限。本文系统地分析了不同阶数单形复合物（SC）上的随机游走如何在理论表达能力方面促进GNN。首先，在0-单形或节点级上，我们通过随机游走的桥梁建立了现有位置编码（PE）和结构编码（SE）方法之间的联系。其次，在1-单形或边缘级上，我们通过边级随机游走和Hodge 1-Laplacians建立了联系，并分别设计了相应的边界PE。在空间域中，我们直接利用边界级随机游走构建了EdgeRWSE。基于Hodge 1-Laplacians的谱分析，我们提出了Hodge1Lap，一种置换等价并具有表达能力的边界位置编码。第三，在高阶单形上推广了我们的理论，并提出了基于随机游走和Hodge Laplacians设计单形PE的一般原则。还引入了跨层次的随机游走来统一广泛范围的单形网络。大量实验证实了我们基于随机游走的方法的有效性。

利用简化复形上的随机游走促进图神经网络