Facilitating Graph Neural Networks with Random Walk on Simplicial
  Complexes
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.
Cai Zhou, Xiyuan Wang, Muhan Zhang
# Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes

###### Abstract

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 EdgeRMSE. 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.

## 1 Introduction

Graph neural networks (GNNs) have recently achieved great success in tasks with graph-structured data, benefiting many theoretical application areas, including combinatorial optimization, bioinformatics, social-network analysis, etc. [11; 29; 16]. Two important aspects to evaluate GNN models are their theoretical expressivity in distinguishing non-isomorphic graphs, and their performance on real-world tasks. Positional encoding (PE) and structure encoding (SE) are widely adopted methods to enhance both theoretical expressivity and real-world performance of GNNs. Generally, PE encodes the information of the nodes' local or global positions, while SE provides information about local or global structures in the graph. For example, Kreuzer et al. [30] uses eigenvectors of the graph Laplacian, Dwivedi et al. [18] proposes to use diagonal elements of the \(t\)-step random walk matrix, and Bouritsas et al. [9] manually count some predefined structures. There are also some methods based on pair-wise node distances, such as the shortest path distance [31], the heat kernel [20], and the graph geodesic [35]. Although some work theoretically analyzes some of these methods [51], there are still some left-out methods, and people lack a unified perspective to view all these PE and SE designs. Moreover, most existing methods focus only on node data, while PE and SE on edge data as well as some higher-order topological structures are waited to be studied.

In addition to PE and SE, geometric deep learning has recently become a central topic. Researchers are inspired by concepts of differential geometry and algebraic topology, which resulted in many works on simplices and simplicial complexes [8; 7; 47]. Despite their capability to deal with higher-order structures, these simplicial networks should follow orientation symmetry, which brings difficulties in their applications in undirected graphs. This work connects these two separate areas via a central
concept: random walk on simplicial complexes. On the one hand, by introducing concepts of higher-order simplicial complexes, we can design more PE and SE methods that are both theoretically and practically powerful. On the other hand, PE and SE greatly facilitate simplicial data and benefit graph learning.

In summary, we first connect a number of existing PE and SE methods through the bridge of node-level random walk on \(0\)-simplices. Then, for \(1\)-simplices or edges, we design two novel sign and basis invariant edge-level PE and SE, namely EdgeRMSE and Hodge1Lap. EdgeRMSE uses an edge-level random walk directly to capture structure information, while Hodge1Lap is based on spectral analysis of Hodge 1 Laplacian, which is closely related to random walk on edges. We further generalize our theory to random walk on higher-order and inter-order simplices to facilitate graph and simplicial learning. Our methods achieve State-Of-The-Art or highly competitive performance on several datasets and benchmarks. Code is available at [https://github.com/zhouc20/HodgeRandomWalk](https://github.com/zhouc20/HodgeRandomWalk).

## 2 Related work

Theoretical expressivity and Weisfeiler-Lehman test.Weisfeiler-Lehman tests are a classical family of algorithms to distinguish non-isomorphic graphs. Previous work has built connections between the expressivity of GNNs and the WL hierarchy. Some classical conclusions include that for \(k\geq 2\), \(k+1\)-dimensional WL is more powerful than \(k\)-WL. [46] proves that traditional message-passing neural networks (MPNN) are not more powerful than \(1\)-WL. There is another variation of the WL test called the Folklore Weisfeiler-Lehman (FWL) test, and \(k\)-FWL is equivalent to \(k\)-WL in expressivity for \(k\geq 1\).

Symmetry in graph and simplicial learning.Symmetry is a central topic in graph and simplicial learning. In graph learning, node features and edge features need to be permutation (i.e., relabeling of nodes or edges) equivariant, while the graph features should be permutation invariant. In simplicial learning, one needs to further orientation symmetry [47] in an oriented simplicial complex (SC). The incidence relations and the simplicial adjacencies in an oriented SC are altered when the orientations are reversed. The \(k\)-form remains invariant to this transformation, while the features of \(k\)-simplices are equivariant in terms of the basis. [32] also state the standard that the graph-level functions (and in the context of SC, \(k\)-forms) should be invariant to both sign and basis (either of orientation or of space), which is a basic rule for our PE and SE designs.

## 3 Preliminary

Graphs.We denote a graph as \(G(V,E,A)\), where \(V,E\) is the set of nodes and the set of edges, respectively, and \(A\) is the adjacency matrix for the nodes. For convenience, we use \(n=|V|\) and \(m=|E|\) to represent the number of nodes and edges in the graph \(G(V,E,A)\). In an undirected graph, for any \(u,v\in V\), we have \((u,v)\in E\Leftrightarrow(v,u)\in E\). Let \(\mathcal{N}(v,G)=\{u\in V|(u,v)\in E\}\) denote the set of neighbors of node \(v\) in graph \(G\). Let diagonal matrix \(D=diag(d_{1},...,d_{n})\), where \(d_{i}\) is the degree of node \(v_{i}\).

The transition matrix of a typical random walk at node level is \(P=D^{-1}A\), which indicates that in each step the walk moves from the current node \(v\) to one of its neighboring nodes \(u\in\mathcal{N}(v,G)\) with equal probabilities. Consequently, a \(t\) step of the aforementioned random walk corresponds to a transition matrix \(P^{t}\).

Discrete Hodge Laplacian of abstract simplicial complex.An abstract simplicial complex \(\mathcal{K}\) on a finite set \(V\) is a collection of subsets of \(V\) that is closed under inclusion. In our paper, \(V\) will be a vertex set \([n]=\{1,2,...,n\}\) if without special statement. An element of cardinality \(k+1\) is called a \(k\)-face or \(k\)-simplex of \(\mathcal{K}\). For instance, \(0\)-faces are usually called vertices, \(1\)-faces are directed edges, and \(2\)-faces are 3-cliques (triangles) with an orientation. We denote the collection of all \(k\)-faces of \(\mathcal{K}\) as \(S_{k}(\mathcal{K})\). The dimension of a \(k\)-face is \(k\), and the dimension of a complex \(\mathcal{K}\) is defined as the maximum dimension of the faces in \(\mathcal{K}\).

The definition of neighbors of simplices is crucial in this paper. Two \(k+1\)-simplices sharing a collective \(k\)-face are called \(k\)-down neighbors, and two \(k\)-simplices sharing a collective \(k+1\)-simplex are called \(k+1\)-up neighbors. Generally, a face \(F\) is chosen as an ordering on its vertices and is said
to be oriented, denoted by \([F]\). For any permutation element \(\sigma\in\mathcal{G}_{k+1}\) where \(\mathcal{G}_{k+1}\) is the symmetric group of permutations on \(\{0,...,k\}\), two orders of vertices transformed by \(\sigma\) are said to determine the same orientation if \(\sigma\) is an even permutation and opposite if \(\sigma\) is odd.

In the Hilbert space, the matrix representations of boundary and coboundary operators are adjacency matrices of order \(k\) and \(k+1\) simplices. In order to keep coordinate with most existing literature, we write the adjacent matrix of \(k\)-th and \(k+1\)-th simplices as \(\mathbf{B}_{k+1}\in\mathbb{R}^{[S_{k}]\times[S_{k+1}]}\). \(\mathbf{B}_{k+1}[i,j]=1\) if the \(i\)-th \(k\)-simplex and \(j\)-th \(k+1\)-simplex are adjacent and share the same direction, \(\mathbf{B}_{k+1}[i,j]=-1\) if adjacent with opposite directions, and \(0\) if they are not adjacent. For example, \(\mathbf{B}_{1}\) is the node-to-edge incidence matrix.

In discrete Hodge-deRham theory, the \(k\)-th order Hodge Laplacian is defined as

\[\mathbf{L}_{k}=\mathbf{B}_{k}^{*}\mathbf{B}_{k}+\mathbf{B}_{k+1}\mathbf{B}_{k +1}^{*} \tag{1}\]

where \(\mathbf{B}_{k}^{*}=\mathbf{B}_{k}^{T}\) is the adjoint of \(\mathbf{B}_{k}\) and is equivalent to the transpose of \(\mathbf{B}_{k}\) in Hilbert space. A special case is that when \(k=0\), \(\mathbf{B}_{0}\) is not defined and \(\mathbf{L}_{0}=\mathbf{B}_{1}\mathbf{B}_{1}^{*}=\mathbf{D}-\mathbf{A}\) is exactly the graph Laplacian. We refer readers to Appendix C.2.2 for an illustrative calculation example of Hodge Laplacians. In our following texts, we will make use of higher-order Hodge Laplacians such as \(\mathbf{L}_{1}\) rather than previously used \(\mathbf{L}_{0}\) alone.

The kernel space of \(\mathbf{L}_{k}\) is called the \(k\)-th cohomology group: \(\tilde{\mathcal{H}}^{k}(\mathcal{K},\mathbb{R}):=\ker(\mathbf{B}_{k+1}^{*})/ \mathrm{im}(\mathbf{B}_{k}^{*})\cong\ker(\mathbf{B}_{k+1}^{*})\cap\ker( \mathbf{B}_{k})=\ker(\mathbf{L}_{k})\). We will write \(\tilde{\mathcal{H}}^{k}(\mathcal{K},\mathbb{R})\) simply as \(\tilde{\mathcal{H}}^{k}\) without causing confusion. The kernel spaces of Hodge Laplacians are closely associated with harmonic functions and will play an important role in our following analysis. Particularly, the multiplicity of zero eigenvalues of \(\mathbf{L}_{k}\), or the dimension of null space of Hodge \(k\)-Laplacian \(\ker(\mathbf{L}_{k})\), is called the \(k\)-th Betti number \(\beta_{k}\)[23]. This is exactly the number of cycles composed of \(k\)-simplicials that are not induced by a \(k\)-boundary, or intuitively, \(k\)-dimensional "holes" in the simplicial complex \(\mathcal{K}\). For example, zero eigenvalues and their eigenvectors of \(\mathbf{L}_{0}\) are associated with the \(0\)-th cohomology group of the graph, corresponding to the connected components of the graph. The zero eigenvalues and eigenvectors of \(\mathbf{L}_{1}\) are associated with cycles (in the usual sense), and those of \(\mathbf{L}_{2}\) correspond to cavities. We refer readers to Appendix C.2.2 for detailed explanations and illustrative examples of cohomology groups.

## 4 Random walk on 0-simplices

Random walk on \(0\)-simplices or at node level has been studied systematically. Previous work has established comprehensive analysis on the theoretical properties of node-level random walk, which provide theoretical insights into the design of random walk-based methods. However, there is still limited research on the theoretical expressivity of random walk-based positional encoding (PE) and structure encoding (SE) methods. In this section, we establish connections between several PE and SE with node-level random walk, and provide theoretical expressive power bounds for them.

Rwse.[52] and Dwivedi et al. [18] propose a structure encoding method based on node-level random walk, which we denote as RWSE. Concretely, RWSE considers \(K\) steps of random walk at the node level of the graph, obtaining \(\mathbf{P},\mathbf{P}^{2},...,\mathbf{P}^{K}\). Then the method only takes into account each node's return probabilities to itself, i.e. the diagonal elements of \(\mathbf{P}^{k},k=1,2,...,K\). For each node \(v_{i}\), the RWSE feature is \(h_{i}^{RWSE}=[\mathbf{P}_{ii},\mathbf{P}_{ii}^{2},...,\mathbf{P}_{ii}^{K}]\). Compared with encoding methods based on graph Laplacian eigenvalues and eigenvectors, this method is sign and basis invariant. It internally captures some structure information within \(K\)-hops and achieves impressive results in experiments [38]. However, there are limited investigations on the theoretical expressivity of RWSE and its extensions. Here, we provide a theoretical bound of positional and structure encoding methods based on random walk transition matrix \(\mathbf{P}\).

**Theorem 4.1**.: _RWSE is strictly less powerful than \(2\)-FWL, i.e. \(\text{RWSE}\prec 2\)-FWL._

The above expressivity bound holds because \(2\)-FWL can simulate the multiplication and injective transformations of a matrix, including the adjacency matrix \(\mathbf{A}\). Therefore, \(2\)-FWL is capable of obtaining \(\mathbf{P}^{k},k\in\mathbb{N}\). Specifically, a block of PPGN [34] can simulate one time of matrix multiplication. Moreover, RWSE is strictly less expressive than \(2\)-FWL, since it loses much structure information when taking the diagonal elements of \(\mathbf{P}^{k}\) only. In other words, RWSE is a summary of full random walk transition probabilities (on spatial domain), which accelerates calculation at the cost of losing expressivity.
Resistance distance and random walk.In addition to RWSE, there are a number of positional encoding methods closely related to the node-level random walk. A.K. et al. [2], Zhang et al. [51] connect commute time in random walks with resistance in electrical networks, which can be used as a PE method called resistance distance (RD). Zhang et al. [51] prove that RD and shortest path distance (SPD) [31] are both upper-bounded by 2-FWL in expressive power.

Positive definite kernels based on graph Laplacian spectrum.Graph Laplacian, or Hodge \(0\)-Laplacian as we refer to later, is closely connected with random walk on graph. The definition of graph Laplacian is \(\mathbf{L}_{0}=\mathbf{D}-\mathbf{A}=\delta_{0}^{*}\delta_{0}=\Delta_{0}\). Through the spectrum of \(\mathbf{L}_{0}\), we are able to define a family of positive definite kernels on graphs [42] by applying a regularization function \(r\) to the spectrum of \(\mathcal{L}_{0}\): \(K_{r}=\sum_{i=1}^{m}r(\lambda_{i})\mathbf{u}_{i}\mathbf{u}_{i}^{T}\), where \(\mathbf{L}_{0}=\sum_{i}\lambda_{i}\mathbf{u}_{i}\mathbf{u}_{i}^{T}\) is the eigenvalue decomposition. For example, the heat kernel or the diffusion kernel [20] can be incorporated if \(r(\lambda_{i})=e^{-\beta\lambda_{i}}\). Other methods directly use eigenvectors as PE [30]. These results imply that spectral analysis of graph Laplacians can also inspire more powerful PE and SE, and we will generalize graph Laplacian \(\mathbf{L}_{0}\) to arbitrary order of Hodge \(k\) Laplacians in the following section to facilitate graph learning.

## 5 Random walk on 1-simplices

While node-level random walk has been widely studied, edge-level random walk is still limited. In this section, we will first introduce Hodge \(1\) Laplacian \(\mathbf{L}_{1}\), as well as its connection with random walk on \(1\)-simplices (in the lifted space) and thus edges of undirected graph. Analogous to node-level RWSE, we introduce EdgeRMSE, a more theoretically powerful PE for edges. Furthermore, we systematically analyze the spectra of \(\mathbf{L}_{1}\) and propose a novel Hodge1Lap PE, the first sign and basis invariant edge-level positional encoding that make use of the spectra of \(\mathbf{L}_{1}\) instead of the previously adopted \(\mathbf{L}_{0}\) only.

### Normalized Hodge-1 Laplacian and edge-level random walk

Theoretical analysis of edge-level random walk.The standard Hodge \(k\)-Laplacian is \(\mathbf{L}_{k}=\mathbf{B}_{k}^{*}\mathbf{B}_{k}+\mathbf{B}_{k+1}\mathbf{B}_{k +1}^{*}\), and there are a number of normalized Hodge Laplacian because the normalization is rather flexible. Schaub et al. [41] propose a normalized form for Hodge \(1\)-Laplacian \(\mathbf{L}_{1}\) with a clear interpretation of a random walk in the lifted edge space. Concretely,

\[\mathbf{\tilde{L}_{1}}=\mathbf{D}_{2}\mathbf{B}_{1}^{*}\mathbf{D}_{1}^{-1} \mathbf{B}_{1}+\mathbf{B}_{2}\mathbf{D}_{3}\mathbf{B}_{2}^{*}\mathbf{D}_{2}^{ -1} \tag{2}\]

where \(\mathbf{D}_{2}\) is the diagonal matrix with adjusted degrees of each edge \(\mathbf{D}_{2}=\max(diag(|\mathbf{B}_{2}|\mathbf{1}),I)\), \(\mathbf{D}_{1}\) is the diagonal matrix of weighted degree of nodes \(\mathbf{D}_{1}=2\cdot diag(|\mathbf{B}_{1}|\mathbf{D}_{2}\mathbf{1})\), and \(\mathbf{D}_{3}=\frac{1}{3}\mathbf{I}\).

To interpret this normalized Hodge \(1\)-Laplacian \(\mathbf{\tilde{L}_{1}}\), Schaub et al. [41] introduce a lifted space of edges, where the original \(m=|S_{1}|\) directed edges are lifted to \(2m\) directed edges. For example, if \((i,j)\in S_{1}\), then we add \((j,i)\) to the lifted space. Consequently, the edge flow \(\mathbf{f}\in\mathcal{C}^{1}\) expands to a larger space \(\mathcal{D}^{1}\) where there are two orientations for each edge, \(|\mathcal{D}^{1}|=2|\mathcal{C}^{1}|\). The matrix representation for this lifting procedure is \(\mathbf{V}=[+\mathbf{I}_{m}\quad-\mathbf{I}_{m}]^{T}\in\mathbb{R}^{2m\times m}\). Then the probability transition matrix for this lifted random walk corresponding to \(\tilde{L}_{1}\) is \(\mathbf{\hat{P}}\):\(-\frac{1}{2}\mathbf{\tilde{L}_{1}}\mathbf{V}^{T}=\mathbf{V}^{T}\mathbf{ \hat{P}}\). In practice, we also perform a simpler row-wise normalization over \(\mathbf{L}_{1}\) to obtain another form of probability transition matrix.

Using \(\mathbf{\hat{P}}\), we can construct an edge-level random walk-based PE method to enrich edge data by encoding structure information, analogous to node-level RWSE. We will also discuss some variations and simplified versions of the aforementioned random walk on \(1\)-simplices and theoretically analyze their expressivity.

EdgeRMSE.Similar to node-level random walk, a well-defined edge-level random walk contains some structure information and can be used to facilitate edge data, namely edge-level positional encoding. While node-level positional encodings have been widely studied, the edge-level positional encoding is a nearly blank field.

Inspired by (node-level) RWSE, EdgeRMSE is based on edge-level random walk. A full version of EdgeRMSE is based on the full edge-level random walk as we have stated above and in [41]. For undirected graphs, two edges with opposite directions \((i,j)\) and \((j,i)\) are again merged by summing
the two probabilities, that is, the lifted space \(\mathcal{D}^{1}\) is mapped back to \(\mathcal{C}^{1}\). Generally speaking, PE can be based on any injection functions \(\psi\) in \(\hat{\mathbf{P}}\) and its powers.

\[\mathrm{EdgeRWSE}(\hat{\mathbf{P}})_{i}=\psi([\hat{\mathbf{P}}^{k}]),k=1,2,...K \tag{3}\]

where \(K\) is the maximum steps we consider. One possible example is to encode the return probability of each edge, which is written \(\mathrm{EdgeRWSE}_{\mathrm{ret}}(\hat{\mathbf{P}})_{i}=\psi([\hat{\mathbf{P}} ^{k}_{i\mid i}]),k=1,2,...K\). If \(\psi\) is well defined, the theoretical expressivity of the full EdgeRWSE above is able to break the \(2\)-FWL bottleneck of node-level RWSE. In practice, we can apply neural networks like MLP or Transformer to encode \(\hat{\mathbf{P}}^{k}\) and concatenate them with the original edge features. Then any standard GNN is applicable for downstream tasks. If the GNN is at least as powerful as \(1\)-FWL, then the GNN with EdgeRWSE is strictly more powerful than \(1\)-FWL and can distinguish some non-isomorphic graph pairs in which \(2\)-FWL fails.

In addition to the edge-level random walk in the lifted space of \(1\)-simplicials in [41], we further define two simplified versions of the edge-level random walk only through lower adjacency. We neglect the \(2\)-simplices or the triangles in our simplified version random walk, i.e. we only consider the \(1\)-down neighbors that share a \(0\)-simplices (node). In this way, \(\hat{\mathbf{P}}\) becomes \(\mathbf{P}_{down}\). This simplification will lead to a theoretically weaker expressivity than using full \(\hat{\mathbf{P}}\), which will be bounded by \(2\)-FWL. However, this simplification is appropriate and beneficial for real-world data that contain a small number of triangles. We illustrate these two variations temporarily on undirected connected graphs without multiple edges and self-loops for simplicity.

The two variations of edge-level random walk via down-neighbors differ in whether two lower adjacent nodes of the edge have the same status. Concretely, the first type of edge-level random walk based on \(\mathbf{P}_{down}\), which we define as _directed \(1\)-down random walk_ follows a two-stage procedure at every step. The walk first selects one of the two lower-adjacent nodes with equal probability \(0.5\) each, then moves towards the neighboring edges connected with the selected node with equal probabilities. If there are no other edges connected to the selected node, the walk returns to the original edge. On the other hand, the second type, which we denote as _undirected \(1\)-down random walk_, chooses the two nodes \(u,v\) with probabilities proportional to their degrees minus one (since we want to exclude the case of returning to \(e\) itself). Consequently, the walk transits to all \(1\)-down neighbors of the source edge with equal probabilities.

In a similar way as the full EdgeRWSE, we propose two simplified versions of EdgeRWSE based on directed \(1\)-down and undirected \(1\)-down random walk, both can be implemented in a rather flexible way. As a special case, the return probabilities of each edge after \(k=1,\ldots,K\) steps are encoded, but notice again that it is not the only implementation choice.

We conclude by summarizing the expressivity of EdgeRWSE.

**Theorem 5.1**.: _Full EdgeRWSE can distinguish some non-isomorphic graphs that are indistinguish by \(2\)-FWL. EdgeRWSE based on directed and undirected \(1\)-down random walk are not more powerful than \(2\)-FWL._

### Sign and basis invariant edge-level positional encoding

Theoretical analysis of Hodge 1-Laplacian spectrum.Recall that the unnormalized Hodge 1-Laplacian is \(\mathbf{L}_{1}=\mathbf{B}_{1}^{T}\mathbf{B}_{1}+\mathbf{B}_{2}\mathbf{B}_{2}^{ T}=\mathbf{L}_{1,down}+\mathbf{L}_{up}\). Here, we analyze the theoretical properties of Hodge 1-Laplacian including its spectrum, which provides solid insights into our following designs.

Note that previous simplicial networks [12; 47; 8; 7] are orientation equivariant and permutation equivariant; thus, they can only be applied to simplicial complexes where all edges are directed. This is frustrating if we want to boost general learning on graphs rather than simplicial complexes alone. However, the spectral analysis of Hodge \(1\)-Laplacian is applicable to undirected graphs. An important property of Hodge Laplacians is that their eigenvalues are invariant to permutation and orientation (if the simplices are oriented), thus they could be directly applied to analyze undirected graphs. Hence in this section, we temporarily omit discussion on permutation and orientation invariance since they naturally hold. Instead, we care more about the sign and basis invariance in the field of spectral analysis [32].

We can show that the nonzero eigenvalues of \(\mathbf{L}_{1,down}\) are the same as \(\mathbf{L}_{0,up}\) and hence \(\mathbf{L}_{0}\). This implies that if there are no \(2\)-simplicials (triangles), Hodge \(1\)-Laplacian has the same nonzero
eigenvalues as Hodge \(0\)-Laplacian. However, the corresponding eigenvectors still provide different information about the nodes and edges, respectively.

**Theorem 5.2**.: _The number of non-zero eigenvalues of Hodge \(1\)-Laplacian \(L_{1}\) is not less than the number of non-zero eigenvalues of Hodge \(0\)-Laplacian \(L_{0}\)._

One direct conclusion is that graph isomorphism based on Hodge 1-Laplacian isospectral is strictly more powerful than Hodge 0-Laplacian. Here we draw a conclusion on the theoretical expressivity of the \(L_{1}\) isospectra:

**Theorem 5.3**.: \(L_{1}\) _isospectral is incomparable with \(1\)-FWL and \(2\)-FWL._

Rattan and Seppelt [39] show that the \(L_{0}\) isospectra is strictly bounded by \(2\)-FWL. The \(L_{1}\) isospectra, through the introduction of \(2\)-simplices (triangles), can distinguish some non-isomorphic graph pairs that are indistinguishable by \(2\)-FWL. See Appendix C for detailed examples.

The zero eigenvalues of \(L_{1}\) have some more important properties. Its multiplicity is the \(1\)-th Betti number \(\beta_{1}\), which is exactly the number of cycles (except triangles) in the graph. We further consider the eigenvectors of \(L_{1}\), each eigenvector \(\mathbf{u}_{i}\) of the eigenvalues \(\lambda_{i}\) has a length \(m\), and each element \(\mathbf{u}_{ij}\) in it reflects the weight of the corresponding edge \(e_{j}\) at this frequency \(\lambda_{i}\). The absolute values of elements corresponding to the edges in cycles are non-zero, while the edges not in cycles have zero weights in the eigenvectors. In other words, the eigenvectors of zero eigenvalues can efficiently mark the edges that are in a cycle. More intuitive illustration and theoretical proof are given in Appendix C.2.2.

Hodge1Lap: sign and basis invariant edge PE.In this section, we propose Hodge1Lap, a novel edge-level positional encoding method based on the spectral analysis of Hodge 1-Laplacian. To the best of our knowledge, this is the first sign and basis invariant edge-level PE based on Hodge \(1\)-Laplacian \(L_{1}\).

Recall the geometric meaning of the Hodge \(1\)-Laplacian spectra in Section 5.2. Zero eigenvalues and eigenvectors reflect the cycles in the graph. These insights of Hodge \(1\)-Laplacian spectra shed light on our design for edge-level positional encoding. Denote the eigenvalues \(\lambda_{i}\) with multiplicity \(m(i)\) as \(\lambda_{i(1)},\lambda_{i(2)},\ldots,\lambda_{i(m_{i})}\), respectively. The corresponding eigenvectors are \(\mathbf{u}_{i(1)},\ldots,\mathbf{u}_{i(m_{i})}\), but note that these eigenvectors are: (i) not sign invariant, since if \(L_{1}\mathbf{u}_{i(j)}=0,j=1,...,m_{i}\), then \(L_{1}(-\mathbf{u}_{i(j)})=0\); (ii) not basis invariant if \(m_{i}>1\), since any \(m_{i}\) linearly independent basis of the kernel space are also eigenvectors, and the subspace they span is identical to the kernel space. This is analogous to the \(L_{0}\) eigenvectors: they are not sign and basis invariant, which makes it difficult for us to design sign and basis invariant positional encodings. Therefore, we propose a novel projection-based method to build Hodge1Lap, a sign and basis invariant edge-level positional encoding.

Formally, Hodge1Lap processes the eigenvalues \(\lambda_{i}\) with multiplicity \(m_{i}\) and relevant eigenvectors as follows. Recall the projection matrix

\[P_{proj,i}=\mathbf{U}\mathbf{U}^{T}=\sum_{j=1}^{m_{i}}\mathbf{u}_{i(j)} \mathbf{u}_{i(j)}^{T} \tag{4}\]

where the subscript \({}_{proj}\) is used to distinguish the projection matrix from probability transition matrix \(P\), and \(\mathbf{U}=[\mathbf{u}_{i(1)},\ldots,\mathbf{u}_{i(m_{i})}]\). For any vector \(\mathbf{v}\in\mathbb{R}^{m}\), \(P_{proj,i}\mathbf{v}\) projects it into the subspace spanned by the eigenvectors \(u_{i(j)},j=1,\ldots,m_{i}\). It is straightforward to verify that the projection in the subspace is independent of the choice of basis \(u_{i(j)}\) as long as they are linearly independent and hence is both sign and basis invariant. As long as the preimage \(\mathbf{v}\) is well defined (e.g., permutation equivariant to edge index), the projection can satisfy permutation equivariance as well as sign and basis invariance. In Hodge1Lap, we propose to use two different forms of preimages: a unit vector \(\mathbf{e}\in\mathbb{R}^{m}\) with each element \(\mathbf{e}_{j}=\frac{1}{\sqrt{m}}\), and the original edge feature \(\mathbf{X}(E)\in\mathbb{R}^{m\times d}\). The first variant considers pure structure information, while the second variant jointly encodes structure and feature information. Taking the first variant as an example, Hodge1Lap implemented by projection can be formulated as

\[\mathrm{Hodge1Lap_{proj}}(E)=\sum_{i}\phi_{i}(P_{proj,i}\mathbf{e}) \tag{5}\]

where \(\phi_{i}\) are injective functions and can be replaced by MLP layers, and the summation is performed over the interested eigen-subspaces.
In addition to the projection-based implementation of Hodge1Lap, we also implement other variants (analogously to the implementation of LapPE [30]): (i) We use a shared MLP \(\phi\) to directly embed the \(n_{eigen}\) eigenvectors corresponding to the smallest \(n_{eigen}\) eigenvalues, where \(n_{eigen}\) is a hyper-parameter shared for all graphs. We refer this implementation as \(\mathrm{Hodge1Lap_{sim}}(E)=\sum_{i=1}^{n_{eigen}}\phi(\mathbf{u}_{i})\). (ii) We take the absolute value of each element in eigenvectors before passing them to the MLP, which we denote as \(\mathrm{Hodge1Lap_{abs}}(E)=\sum_{i=1}^{n_{eigen}}\phi(|\mathbf{u}_{i}|)\), where \(|\cdot|\) means taking element-wise absolute value. It is remarkable that, while \(\mathrm{Hodge1Lap_{proj}}\) is sign-invariant and basis-invariant, \(\mathrm{Hodge1Lap_{sim}}\) is not invariant to both sign and basis, and \(\mathrm{Hodge1Lap_{abs}}\) is sign-invariant yet not basis-invariant. We also allow combination of the above implementations; see Appendix E for more implementation details.

Our Hodge1Lap has elegant geometric meanings thanks to the spectral properties of \(L_{1}\). For example, the kernel space of \(L_{1}\) related to the zero eigenvalues is fully capable of **detecting cycles and rings** in graphs [23], which can play a significant role in many domains. In molecular graphs, for example, cycle structures such as benzene rings have crucial effects on molecular properties. Hodge1Lap is able to extract such rings in a natural way rather than manually listing them, and \(\mathrm{Hodge1Lap_{abs}}\) is able to differentiate edges from distinct cycles. Intuitively, according to the Hodge decomposition theorem, any vector field defined on edges \(\mathcal{C}^{1}\) can be decomposed into three orthogonal components: a solenoidal component, a gradient component and a harmonic (both divergence-free and curl-free) component; see Appendix A. \(\ker(\mathbf{L}_{1})\) is the harmonic component, and since divergence-free and curl-free edge flows can only appear on cycles, the eigenvectors corresponding to \(\ker(\mathbf{L}_{1})\) therefore mark out the cycles in the graph; see Appendix C.2.2 for more technical details and illustrative examples. Moreover, taking into account more subspaces other than the kernel space of \(L_{1}\), Hodge1Lap contains other structure information since the eigenvectors are real and continuous vectors. Ideally, one can apply any sign and basis invariant functions to obtain a universal approximator [32] for functions on \(1\)-faces besides projections, see Section 6 for general conclusions.

## 6 Random walk on higher-order and inter-order simplices

In Section 4 and Section 5, we systematically analyze the random walk and Hodge Laplacian-based PE and SE on \(0\)-simplices (node level) and \(1\)-simplices (edge level), respectively. As we have shown, introducing higher-order simplices into random walk benefits their theoretical expressivity. In this section, we formally introduce random walks on higher-order simplices and analyze their expressivity. We will also investigate the spectral analysis of Hodge \(k\) Laplacians, whose normalization forms are closely related to random walks on \(k\)-simplices. Besides random walk within same-order simplices, we define a novel inter-order random walk that is able to transmit within different orders of simplices. This random walk scheme incorporates and unifies a wide range of simplicial networks [12; 8; 14].

### Higher-order Hodge Laplacians and random walk

The \(k\)-th order Hodge Laplacian is defined as \(\mathbf{L}_{k}=\mathbf{B}_{k}^{*}\mathbf{B}_{k}+\mathbf{B}_{k+1}\mathbf{B}_{k +1}^{*}=\mathbf{L}_{k,down}+\mathbf{L}_{k,up}\). Analogous to \(\mathbf{L}_{1}\), a properly normalized Hodge \(k\) Laplacian \(\mathbf{\tilde{L}_{k}}\) corresponds to a \(k\)-th order random walk on \(k\)-simplices in the lifted space. The matrix representation for the lifting is \(\mathbf{V}_{k}=\left[+\mathbf{I}_{n_{k}}\quad-\mathbf{I}_{n_{k}}\right]^{T} \in\mathbb{R}^{2n_{k}\times n_{k}}\), where \(n_{k}=|S_{k}|\) is the number of \(k\)-simplices in the simplicial complex \(\mathcal{K}\). For undirected graphs, one only needs to sum over different orientations to get the cochain group \(\mathcal{C}^{k}\) from \(\mathcal{D}^{k}\), where \(|\mathcal{D}^{k}|=2|\mathcal{C}^{k}|\) is the cochain group in the lifted space. The transition matrix \(\hat{\mathbf{P}_{k}}\) for \(k\)-th order random walk is defined through \(-\frac{1}{2}\mathbf{\tilde{L}_{k}}\mathbf{V}_{k}^{T}=\mathbf{V}_{k}^{T}\hat{ \mathbf{P}_{k}}\).

Similarly to the edge-level random walk in the lifted space, the transition matrix \(\hat{\mathbf{P}_{k}}\) describes that each step of \(k\)-th order random walk move towards either \(k\)-down neighbors or \(k\)-up neighbors. When going through the upper adjacent \(k+1\) faces, the walk uniformly transits to an upper adjacent \(k\)-simplex with different orientation relative to the shared \(k+1\) face, unless it has no upper adjacent faces. If the step is taken towards a lower-adjacent \(k-1\) face, the walk transits along or against the original direction to one of its \(k\)-down neighbors.

Based on \(\hat{\mathbf{P}_{k}}\), we can design \(k\)-th order RWSE for \(k\)-simplicial data according to the \(k\)-th order random walk, \(k-\mathrm{RWSE}=\psi_{k}(\hat{\mathbf{P}_{k}})\), where \(\psi_{k}\) is an injective function that acts on either \(\hat{\mathbf{P}_{k}}\) or its polynomials. If we maintain all \(k\)-RWSE for \(k=0,1,\ldots,K\) in a simplicial complex \(\mathcal{K}\) with
dimension larger than \(K\), then we can get a more powerful algorithm by adding \(K+1\)-RWSE to the \(K+1\)-simplices in \(\mathcal{K}\).

In addition to directly making use of the random walk on the \(k\)-simplices, spectral analysis of \(\mathbf{L}_{k}\) also sheds light on PE designs for higher-order simplicial data. Based on the eigenvalues and eigenvectors of \(\mathbf{L}_{k}\), we can build permutation equivariant and basis invariant functions defined on \(\mathcal{K}_{k+1}\) that can simulate arbitrary \(k\)-cochain or \(k\)-form. Concretely, if we use the normalized version of \(k\)-th Hodge Laplacian \(\Delta_{k}\) as in [24], the eigenvalues of \(\Delta_{k}\) will be compact \(0\leq\lambda\leq k+2\). Then applying a permutation equivariant and basis-invariant function such as _Unconstrained BasisNet_[32] on the eigenvalues and eigenvectors, we are able to approximate any \(k\)-form which is basis-invariant. We refer interested readers to Appendix C.3 for more details.

### Inter-order random walk

The concept of random walk can be even generalized to a more universal version, which we denote as inter-order random walk. In each step, the inter-order random walk at a \(k\)-simplex can transit not only to the \(k\)-down neighbors and \(k\)-up neighbors (they are all \(k\)-simplices as well), but also to lower adjacent \(k-1\)-simplices and upper adjacent \(k+1\)-simplices. Here we denote the (unnormalized) adjacent matrix for the inter-order random walk on a \(K\)-order simplicial complex \(\mathcal{K}\) as \(\mathcal{A}_{K}(\mathcal{K})\), which is defined as

\[\mathcal{A}_{K}(\mathcal{K})=\begin{bmatrix}\mathbf{L}_{0}&\mathbf{B}_{1}&&\\ \mathbf{B}_{1}^{T}&\mathbf{L}_{1}&\mathbf{B}_{2}&&\\ &...&...&...&\\ &&...&...&...\\ &&&\mathbf{B}_{K-1}^{T}&\mathbf{L}_{K-1}&\mathbf{B}_{K}\\ &&\mathbf{B}_{K}^{T}&\mathbf{L}_{K}\end{bmatrix} \tag{6}\]

which is a block matrix with \(\mathbf{L}_{k}\) in the \(k\)-th diagonal block, \(\mathbf{B}_{k}^{T}\) and \(\mathbf{B}_{k+1}\) in the offset \(\pm 1\) diagonal blocks, while all other blocks are zeros. Although Chen et al. [14] also mentioned a similar block matrix, they do not pose a concrete form of the off-diagonal blocks. The inter-order adjacent matrix we define has a clear physical interpretation that one can only transform to simplices with different orders that are boundaries and co-boundaries of current simplex. A properly normalized version \(\tilde{\mathcal{A}}_{K}\) can describe the inter-order random walk with a certain rule. Here, we give a property of the power of \(\mathcal{A}_{K}\) which still holds in normalized versions.

\[\mathcal{A}_{K}^{r}=\begin{bmatrix}p_{r}(\mathbf{L}_{0})&q_{r-1}(\mathbf{L}_ {0,up})\mathbf{B}_{1}&&\\ q_{r-1}(\mathbf{L}_{1,down})\mathbf{B}_{1}^{T}&p_{r}(\mathbf{L}_{1})&q_{r-1}( \mathbf{L}_{1,up})\mathbf{B}_{2}&&\\ &...&...&...&\\ &&...&...&...\\ &&&q_{r-1}(\mathbf{L}_{K,down})\mathbf{B}_{K}^{T}&p_{r}(\mathbf{L}_{K})\end{bmatrix} \tag{7}\]

where \(p_{r}(\cdot)\) and \(q_{r}(\cdot)\) are polynomials with maximum order \(r\). The above equation states that simplices with differences of order larger than one cannot directly exchange information even after infinite rounds, but they can affect each other through the coefficients in \(p_{r}\) and \(q_{r-1}\) in the blocks on the offset \(\pm 1\)-diagonal blocks.

Several previous works such as [8] can be unified by \(\mathcal{A}_{K}\). Additionally, we can make use of \(\mathcal{A}_{K}^{r}\) to build random walk-based positional encoding for all simplices in the \(K\)-dimensional simplicial complex that contains rich information.

## 7 Experiments

In this section, we present a comprehensive ablation study on Zinc-12k to investigate the effectiveness of our proposed methods. We also verify the performance on graph-level OGB benchmarks. Due to the limited space, experiments on synthetic datasets and more real-world datasets as well as experimental details are presented in Appendix E.

**Ablation study on Zink-12k.** Zinc-12k [17] is a popular real-world dataset containing 12k molecules. The task is the graph-level molecular property (constrained solubility) regression. In our ablation study, we use GINE [25], GAT [45], PNA [15], SSWL+ [50], GPS [38] and GRIT [33] as our base models, where the first three are message-passing based GNNs, SSWL+ is an instance of subgraph GNN, while GPS and GRIT are recent SOTA graph transformers. Four different factors are studied: (1) the node-level PE or SE, where RWSE refers to [18], LapPE refers to [30] and
"-" suggests no node-level PE/SE; (2) EdgeRWSE, the edge-level SE based on spatial domain of \(1\)-down random walk, where "directed" and "undirected" are used to distinguish the two types of simplified version of \(1\)-down random walk; (3) Hodge1Lap, the edge-level PE based on spectra of \(\mathbf{L}_{1}\), where "abs" refers to the sign-invariant method (summing over absolute values of eigenvectors, or \(\mathrm{Hodge1Lap_{abs}}\)), and "project" refers to the sign and basis invariant method (project the unit vector into interested subspace, or \(\mathrm{Hodge1Lap_{proj}}\)); (4) RWMP, a novel Random Walk Message Passing scheme we propose, which performs message passing based on probability calculated by a distance metric; see Appendix D for details of RWMP.

\begin{table}
\begin{tabular}{l|c c c c|c} \hline \hline model & Node PE/SE & EdgeRWSE & Hodge1Lap & RWMP & Test MAE \\ \hline GIN [46] & - & - & - & - & \(0.526\pm 0.051\) \\ GSN [9] & - & - & - & - & \(0.101\pm 0.010\) \\ Graphmer [48] & - & - & - & - & \(0.122\pm 0.006\) \\ SAN [30] & - & - & - & - & \(0.139\pm 0.006\) \\ GIN-AK+ [53] & - & - & - & - & \(0.080\pm 0.001\) \\ CIN [7] & - & - & - & - & \(0.079\pm 0.006\) \\ Specformer [6] & - & - & - & - & \(0.066\pm 0.003\) \\ \hline GINE[25] & - & - & - & - & \(0.133\pm 0.002\) \\ GINE & - & directed & - & - & \(0.110\pm 0.003\) \\ GINE & - & undirected & - & - & \(0.104\pm 0.008\) \\ GINE & - & - & abs & - & \(0.102\pm 0.004\) \\ GINE & - & - & project & - & \(0.091\pm 0.004\) \\ GINE & LapPE & - & - & - & \(0.120\pm 0.005\) \\ GINE & RWSE & - & - & - & \(0.074\pm 0.003\) \\ GINE & RWSE & directed & - & - & \(0.070\pm 0.003\) \\ GINE & RWSE & undirected & - & - & \(0.069\pm 0.002\) \\ GINE & RWSE & - & abs & - & \(0.068\pm 0.003\) \\ GINE & RWSE & - & project & - & \(0.068\pm 0.004\) \\ GINE & RWSE & - & - & True & \(0.068\pm 0.003\) \\ GINE & RWSE & - & project & True & \(0.066\pm 0.003\) \\ \hline GINE & RWSE & Full-EdgeRWSE & - & - & \(0.069\pm 0.003\) \\ GINE & Inter-RWSE & Inter-RWSE & - & - & \(0.083\pm 0.006\) \\ GINE & RWSE & Cellular & - & - & \(0.068\pm 0.003\) \\ \hline GAT [45] & - & - & - & - & \(0.384\pm 0.007\) \\ GAT & - & undirected & - & - & \(0.163\pm 0.008\) \\ GAT & - & - & project & - & \(0.130\pm 0.005\) \\ \hline PNA [15] & - & - & - & - & \(0.188\pm 0.004\) \\ PNA & - & undirected & - & - & \(0.104\pm 0.004\) \\ PNA & - & - & project & - & \(0.074\pm 0.005\) \\ \hline SSWL+ [50] & - & - & - & - & \(0.070\pm 0.005\) \\ SSWL+ & - & undirected & - & - & \(0.067\pm 0.005\) \\ SSWL+ & - & - & project & - & \(0.066\pm 0.003\) \\ \hline GPS [38] & - & - & - & - & \(0.113\pm 0.005\) \\ GPS & RWSE & - & - & - & \(0.070\pm 0.004\) \\ GPS & RWSE & undirected & - & - & \(0.068\pm 0.004\) \\ GPS & RWSE & - & project & - & \(0.064\pm 0.003\) \\ \hline GRIT [33] & - & - & - & - & \(0.149\pm 0.008\) \\ GRIT & RWSE & - & - & - & \(0.081\pm 0.010\) \\ GRIT & SPDPE & - & - & - & \(0.067\pm 0.002\) \\ GRIT & RDPE & - & - & - & \(0.059\pm 0.003\) \\ GRIT & RRWP & - & - & - & \(0.059\pm 0.002\) \\ GRIT & - & undirected & - & - & \(0.103\pm 0.006\) \\ GRIT & - & - & project & - & \(0.086\pm 0.005\) \\ GRIT & RRWP & undirected & - & - & \(0.058\pm 0.002\) \\ GRIT & RRWP & - & project & - & \(0.057\pm 0.003\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Ablation on Zinc-12k dataset [17] (MAE \(\downarrow\)). Highlighted are the first, second results.
The full results of performance on the Zinc dataset are reported in Table 1. Note that all our base models are improved when augmented with our EdgeRWSE or Hodge1Lap: both GAT and PNA reduce by over \(50\%\) MAE. In particular, a simple GINE without using any transformer or subgraph GNN variations is able to surpass GPS with our PE/SE, verifying the impressive effectiveness of our proposed methods. Applying EdgeRWSE and Hodge1Lap to GRIT results in new **State-of-the-Art** performance. Regarding ablation, all variants of our EdgeRWSE and Hodge1Lap can improve performance of base models, see Appendix E for more implementation details of these variants. One may observe that RWSE is significantly beneficial in this task, and combining node-level RMSE and our edge-level PE/SE methods would lead to a further performance gain. In general, Hodge1Lap shows better performance than EdgeRWSE, indicating the effectiveness of embedding structures such as rings through spectral analysis. The effect of whether EdgeRWSE is directed or the implementation method in Hodge1Lap is rather small. We also observe that Full-EdgeRWSE, Inter-RWSE, and CellularRWSE are beneficial, see Appendix E for more details. Additionally, the RWMP mechanism is also capable of improving performance, which we will analyze in Appendix D.

Experiments on OGB benchmarks.We also verify the performance of EdgeRWSE and Hodge1Lap on graph-level OBG benchmarks, including the ogbg-molhiv and ogbg-molpcba datasets. The results are shown in Table 2. We apply our Hodge1Lap and EdgeRWSE to both GatedGCN and GPS(consists of GatedGCN and Transformer) and show that our methods can improve both architectures. In general, both two edge-level PE/SE are able to achieve comparable performance as the SOTA models, though EdgeRWSE suffers from overfitting on ogbg-molhiv. It should be noted that SOTA results on ogbg-molhiv typically involve manually crafted structures, including GSN [9] and CIN [7]. Natural methods and complex models usually suffer from overfitting and cannot generalize well in the test set.

## 8 Conclusions

In this paper, we propose to facilitate graph neural networks through the lens of random walk on simplicial complexes. The random walk on \(k\)-th order simplices is closely related to Hodge \(k\) Laplacian \(\mathbf{L}_{k}\), and we emphasize that both spatial analysis of random walk and spectra of \(\mathbf{L}_{k}\) can improve the theoretical expressive power and performance of GNNs. For \(0\)-simplices, we connect a number of existing PE and SE methods (such as RWSE) via node-level random walk, and further provide a theoretical expressivity bound. For \(1\)-simplices, we propose two novel edge-level PE and SE methods, namely EdgeRWSE and Hodge1Lap. EdgeRWSE directly encodes information based on edge-level random walk, while Hodge1Lap is the first sign and basis invariant edge-level PE based on Hodge-\(1\) Laplacian spectra. We also generalize our theory to arbitrary-order simplices, showing how \(k\)-order and inter-order random walk as well as spectral analysis of Hodge Laplacians can facilitate graph and simplicial learning. Besides analyzing theoretical expressive power and physical meanings of these random walk-based methods, we also verify the effectiveness of our methods, which achieve SOTA or highly competitive performance on several datasets.

\begin{table}
\begin{tabular}{l|c c} \hline \hline model & ogbg-molhiv (AUROC \(\uparrow\)) & ogbg-molpcba (Avg. Precision \(\uparrow\)) \\ \hline GIN+virtual node & \(0.7707\pm 0.0149\) & \(0.2703\pm 0.0023\) \\ GSN (directional) & \(0.8039\pm 0.0090\) & - \\ PNA & \(0.7905\pm 0.0132\) & \(0.2838\pm 0.0035\) \\ SAN & \(0.7785\pm 0.2470\) & \(0.2765\pm 0.0042\) \\ GIN-AK+ & \(0.7961\pm 0.0110\) & \(0.2930\pm 0.0044\) \\ CIN & \(0.8094\pm 0.0057\) & - \\ GPS & \(0.7880\pm 0.0101\) & \(0.2907\pm 0.0028\) \\ Specformer & \(0.7889\pm 0.0124\) & \(0.2972\pm 0.0023\) \\ \hline GPS+EdgeRWSE & \(0.7891\pm 0.0118\) & \(\mathbf{0.2934\pm 0.0025}\) \\ GPS+Hodge1Lap & \(\mathbf{0.8021\pm 0.0154}\) & \(0.2937\pm 0.0023\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Experiments on graph-level OGB benchmarks [26]. Highlighted are the first, second, **third** test results.
## Acknowledgments and Disclosure of Funding

Muhan Zhang is partially supported by the National Natural Science Foundation of China (62276003) and Alibaba Innovative Research Program.
