Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes
Authors: Cai Zhou
Xiyuan Wang
Muhan Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: random walk on simplicials
Hodge Laplacian
graph neural networks
edge-level positional encoding
TL;DR: Systematic analysis on how random walk on different orders of simplicial complexes facilitates graph neural networks.

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 spatial domain, we directly make use of edge level random walk to construct EdgeRWSE. Based on 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.

Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes
Cai Zhou Tsinghua University zhouc200mails. tsinghua. edu. en
Xiyuan Wang Peking University vangxiyuan@pku edu, cn
Muhan Zhang Peking University muhan0pku. edu. en
Abstract
Node-level random walk has been widely used to improve Graph Neural Networks. However, there is limited attention to random walk edges and, more gener- ally, on k-simplices. This paper systematically analyzes how random walk on different orders of simplicial complexes (SC) facilitates GNNs in their theoreti- cal expressivity. First, on O-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 construct EdgeRWSE. Based on the spectral analysis of Hodge I-Laplcians, we propose Hodgel
permutation equivariant and expressive edge-level positional encoding. Third, we generalize our theory random walk on higher-ordet simplices and propose the general principle to design PE on simplices based on random walk and Hodge Laplacians. Inter-level random walk also introduced to unify a wide range of simplicial networks. Extensive experiments verify the effectiveness of our random walk-based methods.
Introduction
Graph neural networks (GNNs) have recently achieved great success in tasks with graph-structured data, benefiting many theoretical application areas, including combinatorial optimization, bio- informatics, social-network analysis, etc. [1]
29 16]. Two important aspects to evaluate GNN models are their theoretical expressivity in distinguishing nom-isomoiphic graphs, and their perfor- mance 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, 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 [3I], 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 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 many works on simplices and simplicial complexes [8] ( 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 central
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

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 EdgeRWSE and Hodgel EdgeRWSE uses an edge-level random walk directly to capture structure information, while Hodge Lap 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 Sate--OfThhe -ae---OfTThhhee The-Art or highly competitive performance on several Walk
datasets and benchmarks. Code is available at
2 Related work
Theoretical expressivity and Weisfeiler-..hhann 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 2 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 2
Symmetry in graph and simplicial learning. Symmetry is 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-forrm 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 = [V] and m = |E] to represent the number of nodes and edges in the graph G(V, A). In an undirected graph, for any u, e E V. we have (u, v) E <> (v, u) E E. Let NV,, G) {u E Vl(u, v) E E} denote the set of neighbors d; is the degree of node Vi.
node in graph G. Let diagonal matrix D = diag (d, ..., dn), where
The transition matrix of typical random walk node level is P D-'A, which indicates that in each step the walk moves from the current node v to one of its neighboring nodes u E [N G) with equal probabilities. Consequently, a t step of the aforementioned random walk corresponds to transition matrix Pt.
Discrete Hodge Laplacian of abstract simplicial complex. An abstract simplicial complex IC on finite set V is collection of subsets of V that is closed under inclusion. In our paper, V will be
vertex set [m] = { [1, 2, .... n) without special statement. An element of cardinality + 1 is called a k-face or k-simplex of K., For instance, O-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 K. as S& (KC). The dimension of a k-face is k and the dimension of a complex K. is defined as the maximum dimension of the faces in K..
The definition of neighbors of simplices is crucial in this paper. Two k + 1-simplices sharing collective f-cace are called k-down neighbors, and two k-simplices sharing a collective + 1-simplex called A + 1-up neighbors. Generally, face F is chosen an ordering on its vertices and is said
2

---

to be oriented, denoted by [F]. For any permutation element a E Gk+1 where GK+1 is the symmetric group of permutations on {0, ..., k). two orders of vertices transformed by a are said to determine the same orientation if a is an even permutation and opposite if 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 1-th simplices as Bx+1 E R [St [S5/x|58 ||| B [[.]] || = if the i-th s-simplex and j-th k 1-simplex are adjacent and share the same direction, Bx+1 [i, - if
adjacent with opposite directions, and O if they are not adjacent. For example, B, is the node-to-edge
incidence matrix.
In discrete Hodge-deRham theory, the k-th order Hodge Laplacian is defined as
Lg B + B
(1)
where B = B the adjoint of B₁ and is equívalent to the transpose of B₁ in Hilbert space. A special case is that when k- = 0, B, is not defined and Ln = B D - 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 L rather than previously used Lo alone.
The kernel space of L called the k-th cohomology group: H. (K, := :er (er(Bijjj) 1/imm//BBBB. = ker(B
k++ n ker(kB, = ker(Ls). We will write H (K,, IR) simply as H² 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 Lg, or the dimension of null space of Hodge k-Laplacian ker ker(Le)) ). called the k-th Betti number 3x [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 K... For example, zero eigenvalues and their eigenvectors of Lo 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 L are associated with cycles (in the usual sense), and those of L2 correspond to cavities. We refer readers to App2ndix(C.2.22 for 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.
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 the node level of the graph, obtaining P. P? .??..., P Then the method only takes into account each node's return probabilities to itself, i.e. the diagonal elements of Ph k = 1, 2, ..., K. For each node v. the RWSE feature is h RaW SE [P.., P Pi,,... .... p. ..J. 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- 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 P.
RWSE.
Theorem 4.1. RWSE is strictly less powerful than 2-FWI, i.e. RWSE - 2-FWL.
The above expressivity bound holds because 2-FWL can simulate the multiplication and injective transformations of a matrix, including the adjacency matrix A. Therefore, 2-FWL is capable of obtaining P k E N. Specifically, block of PPGN 34 can simulate one time of matrix multiplication. Moreover, RWSE is strictly less expressive than 2-FWL, since loses much structure information when taking the diagonal elements of Pd only. In other words, RWSE is summary of full random walk transition probabilities (on spatial domain), which accelerates calculation at the cost of losing expressivity.
3

---

Resistance distance and random walk. In addition to RWSE, there are number of positional encoding methods closely related the node-level random walk. A.K. et al. (2). Zhang et al. [5T] 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) 3 are both upper-hounded by 2-FWL. in expressive power.
Positive definite kernels based on graph Laplacian spectrum. Graph Laplacian, or Hodge O- Laplacian as we refer to later, is closely connected with random walk on graph. The definition of graph Laplacian Lo = - = 60 = Do. Through the spectrum of Lo. we are able to define family of positive definite kernels on graphs [42] by applying a regularization function r to the spectrum of Lo: K, -i=1 r(A, r(A,)u,,u. where Lo = E; Au is the eigenvalue decomposition.
For example, the heat kernel or the diffusion kernel 20 can be incorporated if r(),) = e - Other PE [30]. These results imply that spectral analysis of graph
methods directly use eigenvectors Laplacians can also inspire more powerful PE and SE, and we will generalize graph Laplacian Lo to
arbitrary order of Hodge & 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 Laplacian L1, 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 EdgeRWSE, more theoretically powerful PE for edges. Furthermore, systematically analyze the spectra of L, and propose novel HodgelLar PE, the first sign and basis invariant edge-level positional encoding that make use of the spectra of L instead of the previously adopted Lo only.
5.1 Normalized Hodge-1 Laplacian and edge-level random walk
Theoretical analysis of edge-level random walk. The standard Hodge k-Laplacian is L B; + B B and there are a number of normalized Hodge Laplacian because the normaliza- tion is rather flexible. Schaub et al. [4]] propose a normalized form for Hodge 1-Laplacian L with clear interpretation of a random walk in the lifted edge space. Concretely,
L D, B, B,D,B,D,*'
(2)
where D2 is the diagonal matrix with adjusted degrees of each edge D2 = max BB 11. 7). D, is the diagonal matrix of weighted degree of nodes D2 = 2 diag((B, ID21), and D3 I.
To interpret this normalized Hodge I-Laplacian É, Schaub et al. 41 introduce a lifted space of edges, where the original m = |S|| directed edges are lifted to 2m directed edges. For example, (i,j) E S1, then we add (j. to the lifted space. Consequently, the edge flow E C³ expands to a larger space D where there are two orientations for each edge, |D'| 2/ The matrix
representation for this lifting procedure is V = [[+m -Im] E 2mmxm Then the probability transition matrix for this lifted random walk corresponding to L, is - = v"P. In practice, we also perform simpler row-wise normalization over L1 to obtain another form of probability transition matrix.
Using P. can construct edge-level random walk- 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.
EdgeRWSE. Similar to node-level random walk, well-defined edge-level random walk contains some structure information and can be used to facilitate edge data, namely edge-level positional encoding. While nove-level positional encodings have been widely studied, the edge-level positional encoding is a nearly blank field.
Inspired by (node-level) RWSE, EdgeRWSE is based on edge-level random walk. A full version of EdgeRWSE is based on the full edge-level random walk as we have stated above and [41] For undirected graphs, two edges with opposite directions (i. and (j, are again merged by summing

---

the two probabilities, that is, the lifted space D' is mapped back to C². Generally speaking, PE can be based on any injection functions v in P and its powers.
E) (P(P)) -= 1,2,
(3)
where K the maximum steps we consider. One possible example is to encode the return probability
of each edge, which written EdgeRWSEnee (P); = (PP)). k = 1, ... If t/ 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 Pº and concatenate them with the original edge features. Then any standard GNN is applicable for downstream tasks. 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 L-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, í.e. we only consider the 1-down neighbors that share a O-simplices (node). In this way, P becomes P down. This simplification will lead to a theoretically weaker expressivity than using full P, which will be bounded by 2-FWL. However, this simplification appropriate and beneficial for real-world data that contain 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 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, with probabilities proportional their degrees minus one (since we want 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 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,..., 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.
5.2 Sign and basis invariant edge-level positional encoding
Theoretical analysis of Hodge I-Laplacian spectrum. Recall that the unnormalized Hodge 1- Laplacian is L, B,B, + BB L 1,domm. + Lup- Here, analyze the theoretical properties of Hodge I-Laplacian including its spectrum, which provides solid insights into our following designs.
Note that previous simplicial networks 12 equivariant; thus, they can only be applied to simplicial complexes where all edges are directed. This frustrating if we want boost general learning graphs rather than simplicial complexes alone. However, the spectral analysis of Hodge I-Laplacian is applicable to undirected graphs. An important property of Hodge Laplacians is that their eigenvalues are invariant 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 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)
47
g 7 are orientation equivariant and permutation
We can show that the nonzero eigenvalues of L Li,down are the same as Lo,up and hence Lp. This implics that if there no 2-simplicials (triangles), Hodge 1-Laplacian has the same nonzero
5

---

eigenvalues as Hodge 0- O-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 I-Laplacian L1 is not less than the number of non-zero eigenvalues of Hodge O-Laplacian Lo-
One direct conclusion is that graph isomorphism based on Hodge I-Laplacian isospectra is strictly more powerful than Hodge O-Laplacian. Here we draw conclusion on the theoretical expressivity of the L1 isospectra:
Theorem 5.3. 111 isospectra is incomparable with 1-FWL and 2-FWI..
show that the Lp isospectra is strictly bounded by 2-FWL. The L₁ isospectra, through the introduction of 2-simplices (triangles), can distinguish some non-isomorphic graph pairs that are indistinguishable by 2-FWI.. See Appendix C for detailed examples.
Rattan and Seppelt [3]
The zero eigenvalues of L have some more important properties. Its multiplicity is the 1-th Betti number 81. which is exactly the number of cycles (except triangles) in the graph. We further consider the eigenvectors of L1, each eigenvector u, of the eigenvalues X has a length m, and each element Uj in it reflects the weight of the corresponding edge e, at this frequency A 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 HodgelLap, a novel edge-level positional encoding method based on the spectral analysis of Hodge I-Laplacian. To the best of our knowledge, this is the first sign and basis invariant edge-level PE based on Hodge 1-Laplacian L1.
Recall the geometric meaning of the Hodge 1 1-Laplacian spectra in Section 5.2 Zero eigenvalues
and cigenvectors reflect the cycles in the graph. These insights of Hodge 1- 1-Laplacian spectra shed light on our design for edge-level positional encoding. Denote the eigenvalues X; with multiplicity
m(i) as (=( ) Ai(m:). respectively. The corresponding eigenvectors are u1;1): :.(1)...... U1(m=)) but note that these eigenvectors are: (i) not sign invariant, since if [y,;()) = 0, = 1, ..., m,, then Li ()())))) = 0; (ii) not basis invariant if m, 1, since any m; linearly independent basis of the kernel space are also eigenvectors, and the subspace they span is identical to the kernel space. This analogous to the Lo eigenvectors: they are not sign and basis invariant, which makes difficult for us to design sign and basis invariant positional encodings. Therefore, we propose a novel projection- based method to build HodgelLap a sign and basis invariant edge-level positional encoding.
Formally, HodgelLap processes the eigenvalues X; with multiplicity m; and relevant eigenvectors as follows. Recall the projection matrix
mig
P Pproj,t UU
where the subscript proy is used to distinguish the projection matrix from probability transition matrix P. and U [u.(1)--..,, [m:]]] For any vector E R.m. Peroj..V projects it into the subspace spanned by the eigenvectors ] == 1,..., m. It is straightforward to verify that the projection in the subspace is independent of the choice of basis (ay long they are linearly independent and hence is both sign and basis invariant. As long as the preimage v is well defined (c.g., permutation equivariant to edge index), the projection can satisfy permutation equivariance as well as sign and basis invariance. In Hodgel Lap, we propose to use two different forms of preimages: a unit vector E R with each element e, - and the original edge feature X X(E) R The first variant ym
considers puer structure information, while the second variant jointly encodes structure and feature information. Taking the first variant an example, Hodgel implemented by projection can be formulated as
HodgelLapproj
(E)= Σ de (P)ro...))
where di are injective functions and can be replaced by MI.P layers, and the summation performed over the interested eigen-subspaces.

---

In addition to the projection- basedd implementation of HodgelLap, we also implement other vari- ants (analogously to the implementation of LapPE [00: (i) We use a shared MLP & to directly embed the Neigen eigenvectors corresponding to the smallest Neigen eigenvalues, where Deigen is a hyper-parameter shared for all graphs. We refer this implementation as HodgelTapsim (F)
Ei ((,,). ). (ii) We take the absolute value of each element in eigenvectors before passing them to the MLP, which we denote as LodgelLapabb(C EE) Ei (([u:)), where means taking element-wise absolute value. is remarkable that, while HodgelLappros is sign-invariant and basis- invariant, Hodgel TordgelLapaen Lapsim is not invariant to both sign and basis, and Hodge is sign-invariant yet not basis-invariaa We also allow combination of the above implementations; see Appendix F for more implementation details.
Our Hodge Lap has elegant geometric meanings thanks to the spectral properties of L1. For example, the kernel space of L1 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. Hodge Lap is able to extract such rings in a natural way rather than manually listing them, and Hodge HadgelLapate is able to differentiate edges from distinct cycles. Intuitively. according to the Hodge decomposition theorem, any vector field defined on edges C² can be decomposed into three orthogonal components: solenoidal component, gradient component and a harmonic (both divergence- and curl-free) component; see Appendix A ker(L,) is the harmonic component, and since divergence-free and curl- free edge flows can only appear on cycles, the eigenvectors corresponding ker(L,) 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 L1. Hodge LLap 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 1-faces besides projections, see Section for general conclusions.
Random walk on higher-order and inter-order simplices
we systematically analyze the random walk and Hodge Laplacian-based PE and SE O-simplices (node level) and I-simplices (edge level), respectively. As have shown, introducing higher-orde ooderr simplices into random walk benefits their theoretical expressivity. In this section, we formally introduce random walks on oigher-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 wide range of simplicial networks 112 g
In Section 4 and Section 5
6.1 Higher-order Hodge Laplacians and random walk
The k-th order Hodge Laplacian is defined L BBB, + Bx+1B;+1 Lk,down Lkeup-
Analogous to L,, a properly normalized Hodge Laplacian L corresponds to a k-th order random walk on k-simplices in the lifted space. The matrix representation for the lifting is V₁ [+I -In,)' E 2m xns, where nı |S&| is the number of k-simplices the sim- plicial complex K.. For undirected graphs. one only needs to sum over different orientations to get the cochain group C from D* where |D* = 2 c is the cochain group in the lifted space. The transition matrix Ps for k-th order random walk is defined through - L VT V.P...
Similarly to the edge-level random walk in the lifted space, the transition matrix Ps 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 l: + 1 faces, the walk uniformly transits to upper adjacent k-simplex with different orientation relative to the shared + face, unless it has no upper adjacent faces. If the step is taken towards lower-adjacent & - face, the walk transits along against the original direction to one of its k-down neighbors.
Based on Pk. we can design k-th order RWSE for k-simplicial data according to the k-th order random walk, RWSF = 4/x (P&),, where 4h is an injective function that acts on either Ps or its polynomials, If we maintain all k-RWSE for k = 0, K in simplicial complex XC with
7

---

dimension larger than K, then we can get more powerful algorithm by adding K + 1-RWSE to the K 1-simplices in K.
In addition to directly making use of the random walk on the k-simplices, spectral analysis of Lg also sheds light PE designs for higher-order simplicial data, Based the eigenvalues and eigenvectors of Ls. we can build permutation equivariant and basis invariant functions defined on Kx++1 that can simulate arbitrary k-cochain or k-forr. Concretely, we use the normalized version of k-th Hodge Laplacian As as in 241 the eigenvalues of A will be compact 0 S X S k + 2. Then applying permutation equivariant and aasis-invariant function such Unconstrained BasisNer [32 on the eigenvalues and eigenvectors, we are able to approximate any k-form which is basis-invarian We refer interested readers to Appendix C.3 for more details.
6.2 Inter-order random walk
The concept random walk can be even generalized a more universal version, which we denote as inter-order random walk. 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 & - 1-simplices and upper adjacent k + 1-simplices. Here we denote the (unnormalized) adjacent matrix for the inter-order random walk on K-order simplicial complex IC Ax (K.) which is defined
Lo B
B1 L
B2
(x(
(6)
B
LK-1
Bg
B
LK_
which is block matrix with L3 in the k-th diagonal block, B and Ba+1 in the offset +1 diagonal blocks, while all other blocks are zeros. Although Chen et al. [14] also mentioned similar block matrix, they do not pose concrete form of the off-diagonal blocks. The inter-order adjacent matrix we define has clear physical interpretation that one can only transform to simplices with different orders that are boundaries and co-boundaries of current simplex. properly normalized version Ak can describe the inter-order random walk with a certain rule. Here, we give a property of the power of Ax which still holds in normalized versions.
(Lo)
9r-1 (T., B1 (LL]
9r-1 (L down B
Or- (L,,
Axx
(7)
(L donen B Pr (L())
where p-(-) and q-(-) polynomials with maximum order The above equation states that simplices with differences order larger than one cannot directly exchange information even after infinite rounds, but they affect each other through the coefficients in Pr and gr-1 in the blocks the offset = Iddiggonal blocks.
Several previous works such g to build random walk-based positional encoding for all simplices the K K-dimensional simplicial complex that contains rich information.
can be unified by Ax- Additionally, we can make use of A
7 Experiments
In this section, we present comprehensive ablation study on Zine- 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- 17 is 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 225) GAT [5), PNA [5). SSWL+ (50), GPS (38) and GRIT 33 as
our base models, where the first three are message-passine passing based GNNs, SSWL+ is an instance of subgraph GNN, while GPS and GRIT are recent SOTA graph transformers. Four different factors
studied: (1) the node-level PE SE, where RWSE refers to [18), LapPE refers to (30 and

---

Table 1: Ablation on Zinc-124 dataset 17
(MAE 4). Highlighted are the first, second results.
model
Node PE/SE
EdgeRWSE
HodgelLap
RWMP
Test MAE
GIN
146
0.526 0,051
GSN
9
0.101 0.010
Graphormer
48
0.122 = 0.006
SAN 30
0.139 = 0.006
GIN-AK+
0.080 = 0.001
CIN
0.079 = 0.006
Specformer
0.066 = 0.003
GINE
0.133 = 0.002
GINE
directed
0.110 = 0.003
GINE
undirected
0.104 = 0.008
GINE
abs
0.102 = O, 0.004
GINE
project
0.091 0.004
GINE
LapPE
0.120 0.005
GINE
RWSE
0.074 = 0.003
GINE
RWSE
directed undirected
0.070 = 0.003
GINE
RWSE
0.069 = 0.002
GINE
RWSE
abs
0.068 0.003
GINE
RWSE
project
0.068 = O, 0,004
GINE
RWSE
True
0.068 0.003
GINE
RWSE
project
True
0.066 0.003
GINE
RWSE
Full Edll--Ee Inter-RWSE
0.069 0.003
GINE
Inter-RWSE
0.083 0.006
GINE
RWSE
Cellular
0.068 = 003
GAT 45
0.384 0.007
GAT
undirected
0.163 0.008
GAT
project
0.130 = 0.005
PNA 15
0.188 0.004
PNA
undirected
0.104 = 0.004
PNA
project
0.074 = 0.005
SSWL+ 50
0.070 0.005
SSWL+
undirected
0.067 = 0.005
SSWL+
project
0.066 = 0.003
GPS 38
0.113 0.005
GPS
RWSE
0.070 = 0.004
GPS
RWSH
undirected
0.068 = 0.004
GPS
RWSE
pruject
0.064 = 0.003
GRIT 33
0.149 = 0.008
GRIT
RWSE
0.081 = 0.010
GRIT
SPDPE
0.067 = 0.002
GRIT
RDPE
0.059 0.003
GRIT
RRWP
0.059 0.002
GRIT
undirected
0.103 0.006
GRIT
project
0.086 = 0.005
GRIT
REWP
undirected
0.058 0.002
GRIT
RRWP
project
0.057 0.003
"_" 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) Lad, the edge-level PE based on spectra of L1, where "abs" refers to the iign-invariant method (summing over absolute values of eigenvectors, or Hodgel Lapabs), HodgelLapaas). and "project" refers to the sign and basis invariant method (project the unit vector into interested subspace, or Lapprij): (4) RWMP, a novel Random Walk Message Passing scheme we propose, which performs message passing based on probability calculated by a distance metrie; Appendix D D for details of RWMP.

---

Table 2: Experiments graph-level OGB benchmarks [26]
Highlighted are the first, second, third
test results.
model
oghg-molhiv (AUROC
oghg-molpcba (Avg. Precision 1)
+vituirl node
0.7707 +: 0.0149
0.2703 + 0.0023
GSN (directional)
0.8039 0.0090
PNA
0.7905 0.0132
0.2838 0.0035
SAN
0.7785 0.2470
0.2765 0.0042
GIN-AK+
0.7961 + 0.0110
0.2930 + 0.0044
CIN
0.8094 + 0.0057
GPS
0.7880 0.0101
0.2907 0.0028
Specformer
0.7889 0.0124
0.2972 0.0023
GPS+EdgeRWSE
0.7891 0.0118
0.2934 0.0025
GPS+HodgelLap
0.8021 0.0154
0.2937 + 0.0023
The full results of performance on the Zinc dataset reported in Table I Note that all our base models are improved when augmented with our EdgeRWSE or HodgelLap: both GAT and PNA reduce by over 50% MAE. In particular, a simple GINE without using any transformer subgraph GNN variations able to surpass GPS with our PE/SE, verifying the impressive effectiveness of our proposed methods. Applying EdgeRWSE and Hodge Lap GRIT results in new Sfate-of-the-Art performance. Regarding ablation, all variants of our EdgeRWSE and Hodge Lap 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 RWSE and our edge-level PE/SE methods would lead further performance gain. In general, Hodge Lap 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 Hodge Lap is rather small. We also observe that Full-EdgeRWSE, Inter-RWSE, and CellularRWSE are beneficial, see Appendix for more details. Additionally, the RWMP mechanism is also capable of improving performance, which we will analyze in Appendix
Experiments on OGB benchmarks. We also verify the performance of EdgeRWSE. and Hodge on graph-level OBG benchmarks, including the ogbg-molhiv and aogg-molpeee datasets. The results are shown in Table 2 We apply our Hodge 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 noted that SOTA results on ogbg-molhiv typically involve manually crafted structures, including GSN ( and CIN [7]. Natural methods and complex models usually suffer from overfitting and cannot generalize well in the test set.
ogbg- ggbg-molhiv. It should be
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 Hodge k Laplacian Lg, and we emphasize that both spatial analysis random walk and spectra of L can improve the theoretical expressive power and performance of GNNs. For O-simplices. we connect number of exsiting 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 HodgelLap. EdgeRWSE directly encodes information based on edge-level random walk, while Hodgellap is the first sign and basis invariant edge-level PE based on Hodge-1 Laplacian spectra. We also generalize our theory to arbitrary-ordee 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 highly competitive performance several datascts.
10

---

Acknowledgments and Disclosure of Funding
The work supported in part by the National Natural Science Foundation China (62276003), the National Key Research and Development Program of China (No. 2021ZD01 14702)), and Alibaba Innovative Research Program.
References
[1] Ralph Abboud, ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. CoRR, abs/2010.01 179, 2020.
BtLhtttp:: //app:////axxvv org/ a01/ 2010.0000..000 01119
[2] Chandra A.K., Raghavan P., Ruzzo W.I., and et al. The electrical resistance of graph captures its commute and cover times. Comput Complexity 6, 312-340, 1996.
[3] M. Balcilar, Pierre Héroux, Benoit Gaüzzèe, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference Machine Learning, 2021.
[4] D. Beaini, Saro Passaro, Vincent L' L'etourneau, William L. Hamilton, Gabriele Corso, and Pietro Lio'. Directional graph networks. In International Conference on Machine Learning, 2020.
[5] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai,
G. Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. ArXiv, abs/21 10.02910, 0, 2021.
[6] Deyu Bo, Chuan Shi, Lele Wang. and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. ArXiv, abs/2303.01028, 2023.
[7] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Lio', Guido Montúfar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: Cw networks. In Neural Information Processing Systems, 2021.
[8] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang. Nina Otter, Guido Montúfar, Pictro Lio', and Michael M. Bronstein. Weisfeiler and lchman go topological: Message passing simplicial networks. ArXiv, abs/2103.032112 2021.
[9] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-666, 2023. doi: 10.1109/TPAMI.2022.. 3154319.
[10] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. ArXiv, 2017.
[11] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. CoRR, abs/161 1.00977, 2016. URL httt://arxiv..rrt wwwpsiiivorr//baae www.oo////..........e.11.
[12] Eric Bunch, Qian You, Glenn Moo Fung, and Vikas Singh. Simplicial 2-complex convolutional neural nets. arXiv: Algebraic Topology, 2020.
[13] Jin- Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-415 1989.
[14] Yuzhou Chen, Yulia R. Gel, and H. Vincent Poor. Bscnets: Block simplicial complex neural networks. AAAI Conference on Artificial Intelligence, 2021.
[15] Gabriele Corso, Luca Cavalleri, D. Beaini, Pietro Lio', and Petar Velickovic. Principal neigh- bourhood aggregation for graph nets. ArXiv, abs/2004.05716 18, 2020.
[16] Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. CoRR, org/ Stg/abss/17e www.ab///1000000 01665
2017. URL. /ttt:://arxiii

---

[17] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. ArXiv, abs/2003.00982, 2020.
[18] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bres- son. Graph neural networks with learnable structural and positional representations. ArXiv, abs/2110.07875, 2021.
[19] Vijay Prakash Dwivedi, Ladislav Rampáek, Mikhail Galkin, Alipanah Parviz, Guy Wolf, Anh Tuan Luu, and D. Beaini. Long range graph benchmark. ArXiv, abs/2206.08166 2022.
[20] Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weisfeiler and leman go infinite: Spectral and combinatorial pre-colorings. ArXiv, abs/2201.13410, 2022.
[21] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang, How powerful are k-hop message passing graph neural networks. ArXiv, abs/2205. 13328, 2022.
[22] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. ArXiv, abs/2206.11140. 2022.
[23] Joel Friedman. Computing betti numbers via combinatorial laplacians. Algorithmica, 21: 331-346, 1996.
[24] Danijela Horak and Jürgen Jost. Spectra of combinatorial laplace operators on simplicial complexes. Advances in Mathematics, 244:303-336 2011.
[25] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv: Learning, 2019.
[26] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. ArXiv, hlss20005006887 2020.
[27] Md Shamim Hussain, Mohammed J. Zaki, and D. Subramanian. Global self-attention a replacement for graph convolution. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2021.
[28] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, abss/1609002900 2016.
[29] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. CoRR, abs/2003.03123, 2020. URL https:://arxiv.org//bbbb
03123
[30] Devin Kreuzer, D. Beaini, William L. Hamilton, Vincent L'etourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. ArXiv, abs/2106.0389, 2021.
[31] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding design provably more powerful graph neural networks for structural representation learning. ArXiv, abs/2009.00142. 2020.
[32] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. ArXiv, abs/2202. 13013, 2022.
[33] Liheng Ma, Chen Lin, Derek Lim, Adriana Comero-Soriana Puneet Kumar Dokania, Mark Coates, Philip H. S. Torr, and Ser Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, 2023. URL https
//api.semanticscholaar www.:ooroooooo..e....mmmm :5:999622855
[34] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. ArXiv, abs/1905.1 1136, 2019.
[35] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. ArXiv, 0bs/2100.05667, 2021.
12

---

[36] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In Advances Neural Information Processing Systems, 2020.
[37] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. In Neural Information Processing Systems, 2021.
[38] Ladislav Rampáek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and D. Beaini. Recipe for general, powerful, scalable graph transformer. ArXiv, abs/2205.
2022.
[39] Gaurav Rattan and Tim Seppelt. Weisfeiler-leman and graph spectra. In ACM-SIAM Symposium on Discrete Algorithmss, 2021.
[40] Yu Rong. Wen bing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2019.
[41] Michael T. Schaub, Austin R. Benson, Paul Horn, Gábor Lippner, and Ali Jadbabaic. Random walks on simplicial complexes and the normalized hodge laplacian. SIAM Rev., 62:353-391, 2018.
[42] Alex Smola and Risi Kondor. Kernels and regularization graphs. In Annual Conference Computational Learning Theory, 2003.
[43] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with Id convolutions on random walks. ArXiv, abs/2102.08786, 2021.
[44] Jan Tonshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. ArXiv, abs/2309.00367, 2023. URL https //api. "aapi.semanticscholar org/Corpus 261499904
[45] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio', and Yoshua Bengio. Graph attention networks. ArXiv, hts/1710.10903. 2017.
[46] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ArXiv, abs/ 18 1810188806, 2018.
[47] Maosheng Yang and Elvin Isufi. Convolutional learning on simplicial complexes. ArXiv, abs/2301. 1163, 2023.
[48] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform bad for graph representation? In Neural Information Processing Systems, 2021.
[49] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. ArXiv, abs/1907 .04931, 2019.
[50] Bohang Zhang. Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-Ichman tests. In International Confer- ence on Machine Learning, 2023. URL https:// semanticscholar. Brrg/CorpuIID.
256846546
[51] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. ArXiv, abs/2301.0955 2023.
[52] Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. Retgk: Graph kernels based return probabilities of random walks. In Neural Information Processing Systems, 2018.
[53] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. ArXiv, abs/2110.03753. 2021.
13

---

A Discrete Hodge-deRham theory of abstract simplicial complex
Inspired by differential geometry and algebraic topology, this work investigates how random walk on simplicial complexes can facilitate graph and simplicial learning. In our main text, we merely introduce the Hodge Laplacian (in Hilbert space) due to limited space. this section, we give complete background on discrete Hodge-deRham theory of abstract simplicial complexes to help readers better understand relevant concepts.
An abstract simplicial complex K. in a finite set V is collection of subsets of V that is closed under inclusion. In our paper, V will be vertex set [m] 21, n if without special statement. An element of cardinality & + is called k-face or k-simplex of K. For instance, O-faces are usually called vertices, 1-faces are directed edges and 2-faces are 3-cliques (triangles) with orientation. We denote the collection of all k-faces of K as Sy. (K). The dimension of a k-face is l and the dimension of complex K. is defined as the maximum dimension of faces in K.
The definition of neighbors of simplices is crucial this paper. Two & + 1-simplices sharing a collective f-face are called k-down neighbors, and two k-simplices sharing collective i 1-simplex are called + 1-up neighbors. Generally, a face F is chosen an ordering on its vertices and is said to be oriented, denoted by [F]. For any permutation element group of permutations on {0, ..., k), two orderings of vertices transformed by a are said to determine the same orientation if is an even permutation and opposite is odd. In addition, k-cochain or k-form is a function defined on K++1, f: x ... x V - R that satisfies the following.
Gk+1 where Gk+1 is the symmetric
((. (w)) = sgn(o))( (f...).). ik)
(8)
for all .i........ i&} E Kk+1 and all a E Gk+1- Specifically, fia......... is) = 0 f f Although they have the structure of vector spaces, the vector spaces usually called cochain groups Ch (XC, R). Chain groups (K,, R) are defined as duals of co-chain groups. addition, we define the simplicial coboundary maps 8; : Chi (K,, + ck+1 (X++1XX, RX:
.......... ix] KC++1-
R+1
(lv.)) 0411)
1)'
Uk+1))
j=0
where by suggests that the vertex v omitted. One can view 6y as the dual of the boundary map 0.41. which connects the cochain complex of IC' with coefficients in IR. Further, we can define the adjoint of coboundary operator: o Ck+1(KC, (K, + C* IK). Therefore, we have the following connection.
5x (KC,
5E-1 Ck-1 (KC
ck+ (KC, RR)
ch
(10)
b
After determining the inner products 5t : Ch+ (K, + Ch (K,R)
can define the adjoint of the coboundary operator
8gh,, f2 ><--1<< 81,5
(11)
where f (K, RR), fz CK+ R) are arbitrary. Specifically, in the Hilbert space I,2, the matrix representations of 5y and o% are adjoint matrix B and B&+1 as described in the main texts.
Define the Hodge k-Laplacian operator (also called combinatorial Laplace operator):
L Lk.down Lk.up 6x-18 + 8%
(12)
where we omit the notation for simplicity. is easy to verify by definition that all three operators Lg, Lggups Lg are self-adjoint, nonnegative and compact.
In the Hilbert space, the matrix representations for boundary and co-boundary operators are adjacent matrices of the & and & + order simplices. In order keep coordinate with most existing literature,
14

---

we write the matrix representation for o as Bx+1 E BISs/x/Se (one can view it as the adjacent matrix of k-th and 1-th simplices); therefore, have the definition in our main text:
L B + B
(13)
where = B is the adjoint of Bg and is equivalent to the transpose of B3 in the Hilbert space. =
remarkable that when l 0. Lo is exactly the graph Laplacian Lo = D A. In paper, make use of higher-order Hodge Laplacians such as L rather than previously used Lo alone.
Note that the following equation always holds:
òg0k-1 =0
(14)
This result is sometimes called the fundamental theorem of topology, which can be intuitively interpreted
"the coboundary of coboundary is zero".
The kernel space of LA is called k-th cohomology group:
H (1,, IR) == ker( /imm(xx1)) _ ker(ōx) n ko ker (Rx)
(15)
We will write HK,, R) simply H without causing confusion. The kernel space is closely associated with harmonic functions and will play an important role in our following analysis.
Proof. We already have 6 = O and thus 6-11%% 0% = 0. Then,
im (Lk, C ker [k, (Lx,p)) C ker (Ik,down)
(16)
Therefore,
(Lx = ker(ō)ōs) 16
(17)
ker(dx) ker(6)_1)
(18)
ker(5k) (im( (im(6x-1))
(19)
Hi
(20)
reveals an important conclusion: À > O is nonzero eigenvalue of Lg if and only a nonzero eigenvalue of Le,up and Lg.down. Let the sorted eigenvalues of operator A be s( s(A) (Ao....,Am.) Am), where the eigenvalues are in weakly increasing rearrangement. Denote
Equation 16
s(A) s(B) if the multisets of s( s(A) and s(B) have exactly the same nonzero eigenvalues (or they only differ in the multiplicities of zero). Then we have
( = u(L. U Us U
(21)
Further using s(AB) ((A),, we have an important property that bridges the up and down Hodge Laplacians of the adjacent dimension:
S( s(Lk,up) = 1(LL++1,.omm
(22)
Now we turn our attention to the zero eigenvalues and eigenvectors. The multiplicity of zero eigenvalues of L2, or the dimension of null space Hodge k-Laplacian ker(Læ), is called the k-th Betti number 3r. This is exactly the number of cycles composed of k-simplicials that are not induced by k-boundary, or intuitively, k-dimensional "holes" in the simplicial complex For example, zero eigenvalues and their eigenvectors of Lo associated with O-th homology group of the graph,
15

---

corresponding to the connected components in the graph. The zero eigenvalues and eigenvectors of L are associated with cycles (in the usual sense), and those of Lg correspond cavities.
Also note that the following relation always holds.
im() im( @ im(6k-1)
(23)
Finally, we present the central theorem of Hodge theory, known Hodge decomposition. It states that C can be decomposed into three orthogonal subspaces:
C*C, R) im(62)) @ ( @ im
(24)
(er(
For example, for vector field C2,, the above equation can interpreted as follows, Any edge flow can be decomposed into three orthogonal components: solenoidal (divergence-free) component, a harmonic (both divergence-
and curl-free) component, and a gradient (curl-free) component. In discrete graph, divergence of vertex (0-simplex) is defined as the excess of outgoing over incoming weights, while the curl in a directed triangle (2-simplex) defined as the edge sum around the triangle along the positive direction.
The Hodge decomposition theorem provides insight into our methods. For instance, the kernel space of L (which plays an important role in our Hodge Lap) is both divergence- and curl-free, thus only occurring along the cycles in the graph. Moreover, the Hodge decomposition holds for any order of cochains C* enriching the physical insights of our PE and SE based on Hodge k-Laplacians.
B Classical results of node-level random walk
Here are some classical conclusions about the random walk at node level.
Let X2 be the node we are at step k, and Sy. (2) be the number of times that the random walk visits x during first l steps, then have
Theorem B.1. lim E Se(r)
d(x)
Sa(r) tends to stationary probability a in probability as 2m
20.
Denote the mean hitting time of y from æ by ((,,, y). then clearly
H ( 9) = kP(X: = y. X 1 =
(25)
1=
Generally, H (ax y) is not symmetric. Specifically, Hxx, is the mean return time from to itself. We have
Hxx,)==1+ Po. d(x)
Σ H(z,z)
(26)
SEV
<EN(x)
terms of connected graph, we have following conclusion.
2m Theorem B.2. If the graph G is connected, then H(x, x))
d(x²)
A slight variation of the conclusion states,
Theorem B.3. [8g(ye)
ES)(y)
kd(g)
2m
Theorem B.4. G a connected graph, then simple random walk satisfies Evev(c) EyeN(,) H(x,
16

---

We have reformulation for the above result if we define the mean commute time as C( y) H (z. y) + (y,,)) 2), then
Σ
C(r,v)
(27)
2m
((C))
There is interesting and well-known connection between mean commute time and resistance between nodes Tays see 22 51.
Theorem B.5. C( v) = 2mTzy
In addition, the cover time is defined as == max{C, o Vj. where C. is the expected number of steps taken by a random walk that starts from to hit every vertex in the graph. A bound is obtained by Aleliunas et al. (1979),
Corollary B.6. The cover time C' is at most 2m(n - 1)
These classical conclusions in node-level random walk provide insights into the design of PE/SE methods such as resistance distance (RD). However, since they have been widely studied, we will not restate them.
C Theoretical analysis and proof
In this section, we provide proofs, details and examples for Section 4 Section 5 and Section 6 in the main text. Note that all the following results are novel and are of great significance in theoretically understanding methods.
C.1 Random walk on 0-simplices
C.1.1 Theoretical analysis of 0-RWSE
We start with proving the theoretical expressive power of PE/SE based on spatical domain of random walk on O-simplices. In order to distinguish RWSE for different orders of simplices, we denote the normal node-level RWSE as O-RWSE, our proposed EdgeRWSE 1-RWSE, and RWSE based on random walk on k-simplices as k-RWSE.
We first introduce 2-FWL, a powerful graph isomorphism test. It assigns colors all 2-tuples of nodes and iteratively updates them. The initial color (v, G') of tuple v E VG)² is determined by the isomorphism type of tuple 34
At the (-th iteration, the color updating scheme is
(v, G) = Hash (v,, G)
(w, G)lē [k)) V(G))). (28)
where (v, u) means replacing the i-th element with u. The color of is updated by its original color and the color of its high-order neighbors (1, u). The color of the whole graph is the multiset of all tuple colors,
(G) = Hash (v, G)l E V(G)))).
(29)
Given two function f.g. f can be expressed by means that there exists a function ó Φ o f which equivalent to given arbitrary input H, G. (HH) = [G) = g(H) = g(G). We use I - to denote that f can be expressed with y. If both f + y and + J. there exists a bijective mapping between the output of f to the output g. denoted as f ++> g-
Theorem C.1. (Thcorem 4.1. in main text.) O-RWSE is strictly less powerful than 2-FWL.
Proof. First, we will prove that 2-FWL can express (-RWSE. Specifically, we will prove that Yu E V, v, (ue, G) [(D-1 A) lk 1,2, ..., tJyt 1, 2, ..... We prove this by induction on
17

---

X
X
X
Y
Y
Y
X
Figure 1: pair of non non- isomorphii graphs that are distinguishable by 2-FWL but indistinguishable by O-RWSE in Theorem C.I The shaded sectors denote bicliques K1 i.. all six solid nodes in the shade are connected with the hollow node in the square trunk.
First, 2-FWL can capture degree information in one iteration.
1 (uv, G) (0) (ur, G)2 (((cl0) (uw, G), e00) (wvv G) V}
(30)
C2 (ur, G), (1e (uw, G) E GJ)
(0)
Auvi Duc
(31)
+ (D A)uv
(32)
Therefore, (1) (ue, G) (D-1A) A)
(8) 2. If C2 (ue, G) - [ A)) 1K 1,2, ..., t), at 1-th 2-FWL iteration.
(++1) 2 (uv, G) (1) (uc, G), (((((() (ww. G) el (wn, G)) E V)
(33)
[(D) A) s 1 1,2, .... 1), (1 11 A) f/u (D- (D-1A) / E V)
(34)
[(D- 1 A) k= 1,2, .... 1/ Σ (D- A) (D- A))
(35)
w
[(D-1A) k 1,2, ++
(36)
Next we prove the strictness, i.e. there exists some non-isomorphic graph pairs distinguishable by 2-FWL but not by RWSE. We will show that the graph pair in Figure satisfies this requirement. Both graphs consist of square backbone with nodes (hollow in the figure), and each backbone node connects with every node in either copy of X Y. The graph X consists of triangles, while the graph Y consists of six-ring. The difference of two graphs is that two backbone nodes connected with the same graph X Y are adjacent in (a), but are not adjacent in (b). These two graphs are non-isomorphic and can be distinguished by 2-FWL, but not by RWSE.
The conclusion of 2-FWL can distinguish graphs (a) and (b) in Figure be proved by the 3-pebble bijective game 13 on these two graphs, see (39 for details.
Then show that O-RWSE fails distinguish these two graphs step by step.
For the eight hollow nodes in the square backbones in (a) and (b), regardless of whether it is connected to a copy of X or Y, once we are at the other six nodes in the biclique K1,5 connected
with it, the probability of returning to the backbone node for the first time within & step is Pt. 1*' This can be easily verified since every solid node in X and Y has degree 3, therefore the steps it takes to return to the backbone a geometric distribution parameterized by
2. Consider random walks only within the 6 solid nodes in biclique K1.6 and not returning to the backbone. The probability distributions (or PMFs) for nodes in all copies X are the same (which we denote as px xxx),, x), and PMFs for all nodes in all copies of Y are the same (which we denote as p.y). The PMFs for nodes in X and Y are different (pxx * pyy). This also straightforwwar to verify, since nodes in X can only get to the other two solid nodes if they do not return to the
18

---

backbone, while nodes in Y can get to all nodes. Therefore, RWSE can distinguish subgraphs X and Y (not including the connection between these 6 nodes with backbone).
3. For any backhone node in two graphs, it will have probability 3 1 to walk toward the connected X or Y (but the walk cannot distinguish whether it is connected with X or Y according 1.), and probability & to walk towards another backbone connected with X or Y (again, either case is the same since the returning PMF backbone cannot distinguish X and Y). Combining and and using induction, we can conclude that the returns through biclique or backbone are the same in two graphs, and thus the return probabilities of all eight backbone nodes are the same, which we denote as PB-
4. For all nodes in any copies of X, in each step the return PMF to X will have probability depending on xxx, and probability 3/ depending on pa- Once the connected backbone node is reached, the walk returns to the backbone node according to pB. then returns to X with probability 3. Therefore, the final return probabilities of X are the same, depending on pxx and pg. Similarly, the return probabilities of y E Y are the same, depending on pyy and pB-
5. Finally, for both two graphs, all backbone nodes are assigned the same O-RWSE feature b, all J E X are assigned the same x, and all E Y are assigned y. Therefore, the two graphs have 4 b. 12 and 12 y, indicating that O-RWSE fails to distinguish these two graphs.
Corollary C.2. 1-FWL with O-RWSE initialization is strictly more powerful than O-RWSE, but not more powerful than 2-FWI.
Proof. Figure I provides pair of graphs that 1-FWL with O-RWSE can differentiate, while O-RWSE cannot. Therefore, 1-FWL with O-RWSE initialization strictly more powerful than O-RWSE. However, as shown in Theorem
C.1
31 > 0, cl9 (wn, G) - RW S S., Therefore,
(++)) (uv, G) - (0)
(un, G). (uw,
(uw, G), ()) (wv, G)) V
(37)
(wv, G), (0( (uw, G) E VJ, 10 (wv, G)|w v}
(38)
(0) (wv, G), (9) (wn, G), c G)
(39)
c0 (wv, G), RWW SEa, RW SE.
(40)
(0) (wv, GEWSE..
(41)
where GRWSE is the graph with the O-RWSE feature. In other words. 2-FWL can first capture RWSE with few iterations and then simulate 1-FWL on the graph with RWSE.
Despite its upper bound of 2-FWL, O-RWSE is capable of distinguishing some cases where 1-FWL fails. For example, the non-isomorphic graph pair shown in Tigure@is well-known case that 1-FWL does not distinguish. However, O-RWSE can easily distinguish them, since a O-random walk on graph (b) can only visit three nodes within the same triangle, thus having a larger return probability in the third step (and some subsequent steps) than on graph (a). O-RWSE can also greatly enhance the performance of GNNs in real-world tasks, as shown experiments.
For the same reason, we can prove that the newly proposed RRWP 33 than 2-FWL. RRWP is a natural extension of RWSE, which not only uses return probabilities P but also uses non-diagonal elements P as augmented edge features. However, is still based on node-level random walk and can be completely simulated by 2 2-FWL. Combining our new results and the results from PE/SEs:
SE also strictly less powerful
we provide the following summary for the expressive power of node-level
RWSE is strictly less powerful than 2-FWL.
SPDPE (shortest path distance) is strictly less powerful than 2-FWL.
RDPE (resistance distance) is strictly less powerful than 2-FWL, but more powerful than SPDPE in distinguishing non-isomorphic distanco-regular graphs.
RRWP is strictly less powerful than 2-FWL,, but it is strictly more powerful than SPDPE.
HK (heat kernel) is strictly less powerful than 2-FWI.
19

---

(a)
(b)
Figure 2: A pair of non-isomorphic graphs that are indistinguishable by 1-FWL. Graph (a) is six-cycle, while graph (b) consists of two 3-cycles. Both O-RWSE and Hodge-O isospectra are able to distinguish these two graphs.
(a)
(b)
Figure 3: A pair of non-isomorphic graphs that are indistinguishable by 2-FWI.. Graph (a) is the 4 x Rook's 's graph, graph (b) the Shrikhande's graph, both of them are strongly regular graphs parameterized by (16,6,2,2). Both O-RWSE and Hodge-O isospectra fail to distinguish these them, while full EdgeRWSE (1-RWSE) and Hodge-1 isospectra distinguish them.
C.1.2 Theoretical analysis of Hodge 0 spectra
As we will analyze Hodge I-Laplacians in the following text in detail, Hodge O-Laplacians that have been widely studied not main concentrations. In this section, briefly summarize the properties, aiming to compare with Hodge I-Laplacians.
Theorem C.3. Hodge O-isospectra is incomprable with 1-FWL and not more powerful than 2-FWL.
Proof. Rattan and Seppelt [39 has already proved that Hodge 0-isospectra upper-bounded by 2-FWL. Here we show that graphs in Figure 2 which are indistinguishable by 1-FWI can be distinguished by Hodge 0-isospeetra. The characteristic polynomial for L, of graph (a)
det AI Lo(()) (A 3))-3) 1)
(42)
The characteristic polynomial for L, of graph (b) is
det YV - Lo(()) (A- 81- - 4
(43)
Hence they are distinguishable by Hodge 0 cigenvalues.
However, the graph pair in Figure that can be distinguished by 1-FWL cannot be distinguished by Hodge eigenvalues, since the characteristic polynomial are both
del (YI Lo(a)) det [AI Lg Lb)(
- 3) 1)² 9x2 + 21A - 7) (44)
20

---

(a)
(b)
Figure 4: A pair of non-isomorphic graphs that have isospectral Hodge k- h-Laplacians for all k ...
0, 1, ..... thus they are indistinguishable via eigenvalues of all Hodge k-Laplacians. However, they are 1-FWL distinguishable.
Therefore, there exist some 1-FWL distinguishable graph pairs that cannot be distinguished by Hodge-0 isospectra and vice
C.2 Random walk on 1-simplices
C.2.1 Theoretical analysis of 1-RWSE
We start by proving the expressive power of 1-RWSE (Full EdgeRWSE and its variations).
Theorem C.4. (First part of Theorem 5.1 in the main text). Full EdgeRWSE can distinguish some non-isomorphic graphs that are indistinguishable by 2-FWL.
Proof. We will show that pair of strongly regular graphs parameterized by (16, 2, 2), 4 Rook's s graph and Shrikhande's graph (shown in Figure 3). are indistinguishable by 2-FWL but distinguishable by 1-RWSE. 2-FWL fails distinguish any pair of strongly regular graphs with same parameters, which is a classical result, hence we refer readers to [8] for a complete proof and skip here.
Now we show that the full 1-RWSE is able to distinguish these two graphs. Only the 1-up random walk (i.e. walk towards those 1-up neighbors via shared 2-faces) needs to be considered, since the 1-down random walks on two graphs are identical (see Theorem C.5). For 1-up random walk, note that all edges in the same graph share the same status, thus we only need analyze the random walk rooted at one arbitrary edge in two graphs, respectively. All edges in two graphs are contained in two different 2-simplices (triangles). However, the two 2-faces in (a) x 4 Rook's graph belong to the same 3-simplex or 4-clique, but there are no 4-cliques in (b) Shrikhande's 's graph. Note that all 2-simplices in graph (a) are only connected consequently, an 1-up random walk on graph can only visit 4 different 2-simplices (which are all faces of the 3-simplex 4-clique including the source itself. But the 2-simplices in graph (b) are all connected, so the 1-up random walk has the probability of visiting all triangles and edges the graph. Therefore, as time tends to infinity, the limit return probability of 1-up random walk on 4 x Rook's graph is
the 2-simplices that are in the same 3-simplex;
4-clique the source edge is in), and can only visit 6 different edges in the
1
R Pluu (1) b00
lim
(45)
6
The limit return probability of 1-up random walk on Shrikhande's graph is
1
lim (t) (-+00
(46)
48
21

---

Also, one can verify the difference on two walks via the return probabilities at the third step (or any other following steps, since the return probability on Rook's 's graph is always larger than that of Shrikhande's graph when 2 3):
1 8 Pl.up (3)
R Pl
(3)
(47)
16
Therefore, we have shown l-up random walk can distinguish these two graphs, so can 1-random walk. Therefore, 1-RWSE can distinguish this pair indistinguishable from 2-FWL.
Note that the 1-down RWSE is unable to distinguish 4 x 4 Rook's graph and Shrikhande's 's graph, since it does not consider any 2-simplicial faces. Similarly, O-RWSE is also unable to distinguish them, which is consistent with our previous results. Actually, both 1-down RWSE and O-RWSE upper bounded by 2-FWL, see below.
Theorem C.5. (Second part of Theorem 5.1 in the main text.) 1-down RWSE is not more powerful than 2-FWL.
Proof. When the graph has no triangle, the edge level random walk matrix is
P B Di Bı
(48)
while the node level random walk matrix is
Po = DT BT
(49)
Therefore, VI, Lr( (r(PPt) = tr(P)t), and thus we can determine the multiset of (Laeaall v] E E}.
Now we give more discussion on random walks on 1-simplices. We start by further interpretation of the normalized Hodge I-Laplacian and the edge-level random walk that corresponds. The transition matrix defined by - - VT = ' (see Section 5.1 in the main text) can be interpreted as follows:
P IPP down + P up. where P down and Pup are the transition matrices determined by a lower- adjacent and upper-adjacent random walk. Specifically, in each step with probability of 0.5 each, we take step toward either upper or lower adjacent edges. (1) If the step is taken towards the upper adjacent face (2-simplex or oriented triangle), there are two cases: (la) the edge has an upper adjacent face, then the edge uniformly transits to an upper adjacent edge with different orientation relative to the shared face. (2a) the edge does not have upper adjacent faces, then the walk will keep the same orientation of this edge or change the orientation with equal probability 0.5 each. (2) the step is taken toward the lower adjacent face (0-simplex or node), the walk transits along or against the edge direction to the lower adjacent nodes with each probability 0.5. Then from the selected node, the walk further transmits to the target edges connected with the node with probability proportional to the upper degrees or the weights of the target edges.
One can easily verify that the limit distribution of the directed 1-down random walk (case 1) is the uniform distribution all edges, independent of the starting position. In comparison, the limit distribution of the undirected 1 1-down random walk (case 2) is proportional to the number of 1-down neighbors of the edges (i.e., the number of edges that share one node with the interested edge), thus providing no information except the number of neighboring edges. However, the initial steps of both two types of edge-level I-down random walk are capable providing rich information on the graph structure.
Here we further explain why simplified 1-down EdgeRWSE variations are appropriate in the cases where the SCs contain few 2-simplices (triangles). Recall that the full edge-level 1-random walk will have probability 0.5 to go through the upper adjacent 2-faces, but stays at the same edge (with the same probabilities to keep or change direction) if the edge is not face of the 2-complex. In this case, the full edge-level random walk described by P will almost have probability 0.5 to stay on the same edge (or the edge with an inverse direction if the graph is directed). This results in the walk having larger probability to stay still, the walk becomes 'lazy' and provides less information about
22

---

a
5
1
b
2
4
3
c
3
4
d
d
(a)
(b)
Figure 5: Two simplicial complexes with order and respectively.
surrounding structures. In comparison, the simplified walk variations neglect the upper adjacent 2-faces, thus having greater probability moving out of the source edge and exploring more about structure information. By reducing P to downs the simplified walk has more probability moving away from the source, encouraging exploration of more information about the structure.
C.2.2 Theoretical analysis of HodgelLap
We start analyzing the spectral properties of Hodge I-Laplacians with proving the theorems in the main text. The following theorem discusses the relationship between spectra of Hodge O-Laplacian Lo and Hodge i-Laplacian L1.
Theorem C.6. (Theorem 5.2 in the main text.) The number of non-zero eigenvalues of Hodge I-Laplacian Lı is not less than the number of non-zero eigenvalues of Hodge O-Laplacian Lg-
Proof. This direct conclusion from Equation 21 and Equation
22 which have proved in
Appendix
direct conclusion is that graph isomorphism based on Hodge I- I-Laplacian isospectra (we only dis- cuss the multisets of cigenvalues) is strictly more powerful than Hodge O-Laplacian. The precondition here is that the two graphs have the same number of nodes and edges, or we can construct counter examples that two non-isomorphic graphs have the same Lj but have different numbers of nodes and different Lo (their Lo may have different dimensions and different multiplicities of zero eigenvalues two graphs only differ from some extra isolated nodes). Under this condition, Equation (2T) and Equation (22) state that if we can distinguish two graphs by their eigenvalues of Hodge O-Laplacians, we can also do so by eigenvalues of Hodge 1-Laplacians. For the strictness, the graph pair in Figure can be distinguished by Hodge isospectra but not by Hodge 0 isospectra, see below.
Theorem C.7. (Theorem 5.3 in main text.) isospectra is incomparable with 1-FWL and 2-FWL.
Proof. This theorem compares the expressive power of L, isospectra with the traditional FWL hierarchy. First, we show that there are some non non-isomorpphi graph pairs distinguishable by 1-FWL and 2-FWL cannot be distinguished by L, isospectra, see the example in Figure 4 1-FWL can distinguish them for the following reasons. The first iteration of 1-FWL (equivalently, 1-WL) can hash the nodes of different degrees into different colors. Then in the second iteration, in graph (b) there is one node with degree that owns two neighbors with degree However, there no such node in graph (a); thus, the two graphs have different multiscts of colors after 2 iterations of 1-WL.
23

---

Therefore, both 1-FWL and 2-FWL can distinguish them. However, we do not distinguish them by the multisets of eigenvalues of L1. Both of their characteristic polynomials of L are:
det det(AI- L1I-)( = det - [((()) = (A 3A- 9x² +21 - 7) (50)
Thus, they have identical multisets of eigenvalues L1.
On the other hand, we show that L, isospectra can distinguish strongly regular graphs in Figure B while 2-FWL and 1-FWL known fail them. The characteristic polynomial for Hodge Laplacian of x 4 Rook's graph (which we denote as L1 (R)) is
det (AI- L (A- 8) 4)
(51)
The characteristic polynomial of Shrikhande's Srrikhande'srrahh'sss Hodge I-Laplacian L, is
det - --
(52)
Obviously, their multisets of eigenvalues are different, hence Hodge 1-isospectra can distinguish some non-isomorphic graph pairs that even 2-FWL fail.
Now we turn our attention to the physical meanings and insights of the spectra of Hodge 1-Laplacians. Recall that zero eigenvalues and corresponding eigenvectors are associated with harmonic functions, and Hodgellay is able to figure out the cycles in the graph by projecting a unit vector into the subspace spanned by zero-eigenvalue eigenvectors (or equivalently, the kernel space of Lj). Furthermore, the near-zero eigenvalues and their cigenvectors are associated with near-harmonic functions. The eigenvectors of large eigenvalues are non-homology generators for local structures such as clusters, stars, chains, and so on.
The following theorems state the properties of the Hodge 1-Laplacian and its harmonic space.
Theorem C.8. In the Hilbert space, the Lı of a directed graph without multiple edges self-loops a m x m matrix, where m the number of directed edges. The elements of L satisfy: (1) the i-th diagonal element corresponding
the edge e, is 2 18 (e)),, where (ō1 (e:)l is the number of 2- 2-smpllices e; is in; (2) element [i]r.]] = if if and ej are 1-down adjacent (share one node but not in the same 2-simplex) and two edges have the directions starting from the shared node; (3) L, j] = 1 if and ej are 1-down adjacent but have different directions starting from the shared node; (4) L, [i. 0 6; and ej are 1-up adjacent (in the same 2 2-simplex).
Proof. This can be directly verified by the definition of L1 BBB, B B Bi+1
We take Figure
5 (a) as illustrative example of calculating L, This is a simplicial complex of order K = 2. When writing matrices, we follow the order a, b, d for O-simplices (nodes) and the order 1, 3, 4 for 1-simplices (directed edges). The node-to-edge incidence matrix
0
0
+1
+1
0
-1
B
(53)
-1
-1
0
+1
+1
Therefore the Hodge-O Laplcian is (recall that Bo is not defined and is omitted in calculating Lo)
+1
-1
0
0
+3
-1
Lo B,B
0
1
+2
-1
-D-A
(54)
-.
-1 +2
where D is the diagonal matrix with node degrees as diagonal elements, and A the adjacency matrix (in the normal sense). This is completely identical to the widely used graph Laplacian.
24

---

Now we come to compute L1. There is one 2-simplex in the simplicial complex, and we take the direction b - as the positive orientation of the 2-simplex, then
+1
B2
(55)
++
and we have the Hodge-1 Laplacian
+2
+1
0
0
0
0
+2
+1
0
17
+2
+1
0
+
1
11
+1
+3
0
0
L BiB, B2B;
+1
+2
+1
0
1
+1
-1
0
0
+3
0
-1 +1 +2
+1
+1
0
+3
(56)
which is identical to the description Theorem C.8 It can be seen that B;B, contributes to (1), (2),
(3) in Theorem C.8 ByB contributes to (I) and (4) in Theorem C.8 In some sense, if e; and Ej
both 1-down adjacent and l-up adjacent, the elements eij or eji B,B, and B2B; cancel out each other, resulting eij eja 0 if e; and ej belong to the same 2-simplex.
Next, we declare some properties about the kernel space of L1 (i.e., the 1-cohomology group). Note that the following cycles are that of length larger than 4 since directed triangles are considered as 2-simplices, and in the sense of the undirected graph induced by the directed graph (i.e., we do not care about the directions of edges in the cycle, since any changes of direction are equivalent multiplying 1 on the original basis).
Theorem C.9. For directed graph without multiple edges, self-loops or 2-simplices that contains e cycles, and there are no cycles that share edges, then a group of linearly independent and orthogonal basis of the kernel space of Ln is u, 1.....c, where elements u, corresponding to the edges on the i-th cycle is + 1 and O otherwise, where l(i) is the length of the i-th cycle.
Vi(e)
Proof. We have already stated that the direction of edges only affect the sign of corresponding element eigenvectors, WLOG, we suppose that all edges the i-th cycle follow the anticlockwise direction. Then all nonzero elements on the same basis u, have identical signs. We are going to prove this.
Obviously, u, I,.... e are linearly independent and orthogonal, since the cycles do not share edges, the nonzero elements in u, do not overlap consequently. Therefore, only need to prove that L, = 0. (1) For the j-th row where edge e(j) is not in the i-th cycle, there are two cases: (1a) e(j) connected with any edges in the i-th cycle, then obviously the inner product of j-th row of L and u; is zero, since all nonzero elements in the j-th row of L2 corresponds to zero elements u,; (Ib) e(i) is connected with some edges in the cycle, then the only situation is that e(j) connects with two edges e(ii), e(jz), where the shared node of these three edges is the source node of e(ii) and the target node of e(jz), and the j-th
of L, [j] will have -1 in element ji, +1 in element j2- Therefore, the inner product L, [ u, = 0 + 2 x 0 + (-1) X Vi(s) + X
Vi(a) = O. (2) If e
in the cycle i, then similar to (Ib), the non-zero index in both L D and u, is the index of two neighboring nodes of e(j), hence L [/ u, = 2
+ 2 X (-1)
O. Putting all
[(a)
the pieces together, we have proved L,u; u; 0.
Figure 5 (b) represents an example that satisfies the above conditions in the theorem. For illustration, we calculate its L
+2
1
-1
0
1
+2
0
+1
-1
L
1
0
+2
+1
0
(57)
0
+1
+1
+2
-1
-1
-1
+2
is straightforward to verify that the eigenvector corresponding to the zero eigenvalue is
ug = [1, 1
-1.0
(58)
25

---

The elements corresponding to edges in cycle (edge 2, 4) are non-zero, while other elements are strictly zero. Therefore, Hodgel capable of detecting eycles through the eigenvectors in ker(L,).
Corollary C.10. Suppose that the above conditions hold, denote U = [u uel. Then for vector e of length m and all elements 1, then projection JUT|e e has j-th element 1 if e(j) is in a
cycle and 0 otherwise.
indicates taking the absolute values element-wise.
Proof. This is direct conclusion of Theorem C.9 Note that [UT] has element UUT [i.5]
Rey) if both edges i and j are in the cycle Cij. and otherwise. Hence the projection of e in the kernel space has element if the corresponding edge is in a cycle and 0 otherwise, which means that this projection can efficiently mark out eycles. Note that the projection matrix is actually independent of the choice of basis; hence the above conclusion is universal. For the basis matrix V where the columns are independent but not orthogonal, the projection matrix should be calculated as VVV -VT.
Corollary C.11. Suppose that the above conditions hold, except that two cycles C1 Q2 share one edge e(j). Then in every eigenvector u in the kernel space of L1, u, = 71 72, where Ti 72 are the edge flow and are positive following the anticlockwise direction,
71. e(i) E
i + 5)1
72. e(i) E
(59)
0, e(i) $ (()) C2
Further, (UU?))) e); = O.
Proof. This is also straightforward to verify, since the basis in Theorem C.9 still holds for shared edges among cycles. However, the two edge flows in the cycle definitely have opposite directions in the same edge, as we assign anticlockwise as the positive direction for the flows. Consequently, the flow in e(j) is the difference of two edge flows. Moreover, for the projection without operation of taking element-wise absolute value in the projection matrix, the projection of two cycles in the j-th element of e will cancel out.
There are also some additional interesting conclusions, for example, if e(j) is in cycle e and in 2-simplex, then the edge flow in e(j) will be 57, where is the original edge flow in the cycle, and the edge flow in the other two edges of the 2-simplicial will be 7. Moreover, the eigenvalue 1 of L, will mark out the following substructure: node o, e are both only connected to b, while b is also connected to a fourth node d. All these interesting results can be verified through simple algebra, and we will not list all of them due to the limited space.
Finally, despite the satisfying theoretical properties of Hodge I Lap if we use the projection method (HodgelLapper) in the main text), we experimentally find that naive summation over the absolute values of eigenvectors (referred as HodgelLapats) works fine for a number of real-world tasks, although this method sign-invariant but not insis-invariant.
We also provide more discussion on the cycle detecting ability of HodgelLap As explained above, in Hodgel Lapproj: projecting the constant vector onto the kernel space of L, will result in the element j equal to if the edge j is in a cycle, and ( otherwise. However, is unable to distinguish different cycles or to indicate which cycle an edge belongs to. In comparison, ModgelLap.a can distinguish and detect different cycles, which we explain as follows. In the main text, this implementation described Σ; @(vv)), where || indicates taking element-wise absolute values, and v, refers to the interested eigenvectors (e.g. orthogonal basis of kernel space of L1, in case that we are discussing detecting cycles). Note that here v; is different from u, described in Theorem C..) instead, they are arbitrary random eigenvectors, and we aim to use randomness to distinguish different cycles. For simplicity, we first do not consider overlapping or 2-simplexes: then every eigenvector v; corresponding to zero eigenvalues has the following properties: (i) the elements corresponding to edges that are not in any cycles are zero; (ii) the elements corresponding to edges from the same cycles have identical absolute values, while those of edges from different cycles (almost surely) have
26

---

different absolute values. These properties can be easily verified, since any can be represented as linear combination u, described in Theorem C.9 Therefore, Σ; ML((vv) obtains different values for edges from different cycles, which is why we distinguish and detect them. In practical implementations, we further apply random projection technique to make Hodgell.ap more robust to the choice of basis v;: Σ; MT.P(( O'g vvl)), where 0ij ~ (0, 1) are random variables, and j = I.....JJ J where J is the maximum number of projections. Through this design, the model can explicitly learn different cycles and implicitly maintain the basis invariance.
C.3 Random walk on higher order and inter-order simplices
C.3.1 Properties of random walk on higher order and inter-order simplices
Analogously to O-simplices and 1-simplices, we can use random walk on any k-simplices to build expressive k-RWSE in order facilitate graph and simplicial learning. Meanwhile, Hodge k- Laplacians are closely connected with random walk of l order, whose spectra, including their cigenvalues and eigenvectors, are applicable in methods such as PE or spectral convolution learning.
Here we prove some crucial properties of Hodge Laplacians Li:- Lemma C.12.
L = (Lk + Li,down) Lg + koowwn
(60)
Proof. We prove this by induction. For 1, the equation obviously holds. Suppose L Luup + doown then for its r + 1-th power, we have
L r+1
(Tu + L ((,down)( + LL,down)
(61)
L. L
Lb,up Likdown + L down -Lk,ap
(62)
"k,down"
=L + k,down + (") 5 + (56-15%-1) 6660
(63)
(64)
kkdown
The last equation holds because 6д6R = and 02 _7_1 8 = 0 always hold for all l: 2 1.
Using the above property, we can prove that the power of the inter-order adjacent matrix (defined in Section 6.2 in the main text) satisfies the following property.
Theorem C.13. (Equation 7 in main text).
(Lo) G-- (Ln
Qr-1 (Lo.
(L,))
g. (Lr
Ak-
9r- (L dox.dow))0 pt (LK, don )
(65)
where (-(-) and (r(+) are polynomials with maximum order т, except the last row is incomplete
without LK Note that replace B2 in main text with coboundary operators 8y for universality.
Proof. We still prove by induction. For r = 1, the equation obviously holds with pı (x: = x, 40 Suppose the equation holds for r, then the r + power satisfies the following.
(I) The block at first row and first column concerning Lo. note that Lo = Lo,up = 8,00. we have
A 1, 1]
pr (Lo) + 9r-1 (Lo
(Lo) + g (Lo)
) Lo =
(66)
(2) The kth diagonal block (1 < < K):
Ax [k; k] = gr-1 (Lb 6x-10% + pr (L + gr-1 (Lr. (67)
(Ls()) gr- (Lx) Lx
(68)
= (1))1(Ln)
(69)
27

---

where we use 4r-1(1A + 9r-1 [ down) = (Ib) according to Lemma C.12 have (x) = (x) + q 1 (z) 2.
Further, we
(3) The block at k-th row and k: + 1-th column:
Ax [k; k 1] + pr LL 00% -r- (Ln 10 + 02+1 (x+1) +0
(70)
pr - 10% (5% 0000kk00 t Lkk
(71)
Pr (I,, ---11 L 0%
(72)
gr up
(73)
Hence we have (x) (x) + gr-1 (x) -2
Further, the block at l + 1-th and k-th column is the adjoint of that:
ARt + 1, = (LR.u)))) = 6g q, (6) = gr (IR+1down))
(74)
(4) The block at k-th and 1: + 2-th column:
K
k. k + 1] = 0 0 4r (Z =
(75)
Therefore, the block in 2-th row and k-th column is also 0.
(5) The other blocks are obviously zero.
Combining all these pieces together, we prove the theorem.
The above equation states that simplices with difference order larger than one cannot directly exchange information after infinite rounds, but they affect each other through the coefficients in p, and -r-1 in the blocks on the offset -1-diggonal blocks.
It's noticable that a number of previous works such [ can be reformatted and unified by Ak- Additionally, we can make use of A's to build random walk based positional encoding for all simplices in K K-dimensional simplicial complex that contains more information than random walks within the same order simplices.
In addition, analogously to 77 we can introduce any form of discrete topological structures, e.g., cellular complex, expanded complex cells. Our methods can also be naturally extended discrete domains without orientations, c.g. hypergraphs. In particular, we can define random walk on these discrete topological structures, which can greatly facilitate graph learning by incorporating structures of higher order other than simplicial complexes. Our methods can be easily generalized to these structures, for example, we provide the results of random walk on cellular complexes in Table [ which treats cycles as 2-cellular complexes and greatly improve the performance of the base model. More implementation details can be found Appendix E However, the theoretical analysis including expressive power in distinguishing non-isomorphic graphs of these new methods are nontrivial due to the flcxibility in definition of complex cells, which a future direction worth exploring.
C.3.2 Hodge Laplacians spectra and graph isomorphism
In the spectral domain, necessary but insufficient condition for two graphs to be isomorphic is that their Hodge k-Laplacians are isospectral (having the same cigenvalues) for all 2 O. As we have discussed before, the Hodge 0-isopectra is incomparable to 1-FWL and is not more powerful than 2- FWL. Hodge i-isospectra is incomparable with 1-FWL and 2-FWL. Note that Hodge k+ 1 1-isospectra is not necessarily more powerful than Hodge k-isospectra, except that for A 0 the conclusion holds since Lg.doun 0. However, we can always get a more powerful algorithm by increasing the highest order of Hodge Laplacians while maintaining all the Hodge Laplacians of lower orders.
In addition to making use of eigenvalues, we can build more powerful GNNs based on the spectra of Hodge k-1 k-Laapacia We address that we can universally approximate permutation equivariant and basis invariant functions (moreover, k-form) defined on k-simplicial complexes if we use Expressive- BasisNets [32). Universality is guaranteed by the following decomposition theorem.
28

---

Theorem C.14. (Theorem 4 in 132) Theorem 4 (Decomposition Theorem). Let Xi..... Xx be topological spaces and let G2 be a topological group that continuously acts on X, for each i. We assume that the mild topological conditions on X; and G2 hold. Assume that there is a topological embedding 4/s X//Gi -> IR of each quotient space into a Euclidean space Ra. for some dimension a4- Then, for any continuous function f X X1 x...X X X3 + RR Rodos that is invariant to the action of G G1 x ...... Gk, there exist continuous functions @; X, - R and a continuous function p: 2 C:ZCR' R - Rou,, where a Σi ag such that f(v1,.... 2k) = p(or(vi)................)..).)). . (vx)).
The proof of Theorem C.14 is completed in [32]. For mild topological conditions, we only need G; to be topological group that continuously acts on X; for each i, and to know that there exists topological embedding of each quotient space into some Euclidean space. As a matter of fact, the continuous group action is very mild assumption which holds for any finite compact matrix group. For a finite simplicial complex, the eigenvalues and eigenvectors of Hodge- Laplacins are finite; thus, the compactness naturally holds. Furthermore, using Hodge-Laplacians normalization in [4],, the maximum eigenvalue of L, satisfies Amaz I + 2. Finally, letting X: be the cochain Co in the above theorem,
that the permutation equivariant and basis-invariant function well as the k-form defined on the simplicial complex can be universally approximated, for instance, by Expressive-Basise Net.
Although we can recover the spectra of Lx, = O,...., K (or spectra convolution on simplicial complexes) via Expressive-BasiNNet it is actually impractically expensive. On the other hand, we can use spectral information, such as the eigenvalues and eigenvectors of L to facilitate learning via simple networks.
D Random walk message passing
In our main text, we mainly discuss how to facilitate graph and simplicial learning through designing PE and SE based on random walk on simplicial complexes. However, it is remarkable that random walk on simplicial complexes can give different insights and inspirations designing powerful GNNs and simplicial networks in addition to PE and SE. In this section, we propose novel random walk message passing (RWMP) mechanism, which introduces node distance metrics and simulates a weighted random walk at node level by dropping edges according to distances between neighboring nodes. As revealed in the experiments shown in the main text, RWMP is able to improve the performance of the base models and achieves SOTA performance in the Zinc dataset [17].
D.1 Connections between random walk, subgraph sampling and edge dropping
There have been a great number of relevant works on improving GNNs with subgraph sampling and edge dropping. Subgraph GNNs are a huge family of GNN variations that encode a set of subgraphs instead of the original graph. Some subgraph GNNs are more powerful than MPNN or 1-WL such as (5). while Frasca et al. (22) upper bound node-based subgraph GNNs by 3-WL. Despite the improvement in expressivity and performances, number of subgraph GNNs suffer from extensive computation complexity due to the exponential growth of the subgraph amount. Therefore, various subgraph sampling methods have been proposed improve the scalability of subgraph GNNs. For example, K- -hop GNN [1 extracts a K K-hop subgraph for each root node, and Zeng et al. Toenshoff et al. [43 propose to sample subgraphs via a random walk started from root node. Due to its internal association with the diffusion process, random walk is powerful tool to design subgraph sampling methods. Meanwhile, these subgraph GNNs based on sampling fashion can be interpreted as implicitly encoding structure information obtained by random walk via the following procedure: sampling subgraphs (sampling according to probability transition matrix), running GNN on the subgraphs (encoding structure captured by random walk), and aggregating information among subgraphs (taking expectation).
40
random walk
Dropping edge is another family of methods that introduce randomness into graph learning. DropE- dge [40] a widely adopted technique that randomly drops edges during training to improve the generalizability of GNNs. Unlike DropEdge, DropGNN [3]] randomly drops edges in both the train- ing and inference stages. DropGNN is able to partly improve expressive power, but it has to gather several rounds of inference results to obtain the final representation. In the context of representation learning for linear features, the representations obtained by randomly dropping edges layer-wise unbiased estimators of full message passing if we consider normalization. In comparison, the
29

---

representations obtained by subgraph sampling are biased estimators of full message passing. The layer-wise drop edge can be viewed as an intermediate product between full message passing and subgraph sampling GNNs, which (1) obtains representation in every forward pass like original message passing and does not have to run several forward passes on subgraphs in parallel; (2) has randomness like subgraph sampling methods and has the probability to encode subgraph structures. We leave further discussion and more theoretical analysis for future work.
D.2 Random walk message passing: weighted random walk based on node-level distance metric
As discussed above, both the subgraph sampling and edge-dropping methods can be associated with the simple node-level random walk on unweighted graphs. Through introducing randomness, they can better encode structure information and improve expressive power of GNNs. However, these methods use uniform sampling and uniform dropping strategies associated with unweighted random walk, and hence they are only able to learn pure structure information but no feature information.
To address this limitation, we propose the Random Walk Message Passing mechanism (RWMP). which can jointly learn feature and structure information by introducing distance metries of nodes (or node features). Briefly speaking, RWMP drops edges layerwise fashion, and the probability of dropping edge = (u, v) is function of the distance between nodes and v: Parop (e) = f(((u, (id(u.)), v)), where f is the designed function, and d(u, v) is the (feature) distance between u and in the defined metric. For example, if cosine similarity between node features the distance metric, possible drop probability is:
vl|
Parop (e) (1
(76)
where u and v denote the node feature vector of u and v. The above metric states that the probability of message passing between two nodes is linear with their cosine similarity in node features. The more they are different, the less likely they are to exchange information with each other. Intuitively, this can partly address the problem of oversmoothing, since it reserve heterogeneity by reducing message passing times within dissimilar nodes. RWMP also encourages message passing within similar nodes, which is beneficial for discovering local clusters (it is equivalent sample the subgraphs containing local structures of similar nodes with larger probabilities).
RWMP is novel framework that can jointly learn structure and feature information by simulating weighted random walk based on distance metric. Appropriate designs of distance metries are able to greatly improve the performance of RWMP, which is applicable any wessagg-passinng based GNN variations. RWMP can be regarded as an intermediate scheme between deterministic message passing variations like GAT RWMP is different from GAT the way that RWMP explicitly introduces randomness via dropping edges instead of taking expectation through the attention weights, and the stochastic process forces RWMP to explore more about local structures while relieving oversmoothing. On the other hand, RWMP greatly reduces the computation costs subgraph GNNs the latter often fail to run on large graph benchmarks, while preserving the ability to explore more on certain structures.
455 and subgraph sampling- -baed methods. However, on the one hand,
Combining RWMP with edge-level PE/SE, a GINE (25] model is able to achieve highly competitive performance in the Zine dataset. More experimental details are listed in Appendix E
E
Experiments
E.1 Datasets description
In Section 7 in the main text and Appendix E.2 we conduct extensive experiments on various datasets, confirming the effectiveness of our methods. Among these datasets, Zinc, MNIST, and CIFAR10 are from Benchmarking GNN [17. agbg-molhiv and ogbg-molpcha are from Open Graph Benchmark 26), while PCQM-Contact, Peptides-fune and Peptides-struct are from Long-range Graph Benfchmark [19].
30

---

Table 3: Experiments synthetic datasets (ACC 1). The backbone model is GINE, which is not more expressive than 1-WL.
PE/SE
EXP
SR25
None
50
6.67
Hodge Lapleigeevales
100
100
EdgeRWSE((ful)
100
100
Table 4: Experiments on two datasets from benchmarking GNN second, third test results.
Highlighted are the first,
model
MNIST (Accuracy 1)
CIFARIO (Accuracy 1)
GCN
90.705 1 0.218
55.710 + 0.381
GIN
46
96.485 1 0.252
55.255 + 1.527
GAT
45
95.535 = 0.205
64.223 = 0.455
GatedGCN
10
97.340 0.143
67.312 = 0.311
PNA [1]
97.94 + 0.12
70.35 = 0.63
DGN 4
72.838 + 0.417
CRaWi 4
97.944 + 0.050
69.013 + 0.259
GIN-AK+ 53
72.19 0.13
EGT 27
98.173 0.087
68.702 0.409
GPS 38
98.051 + 0.126
72.298 + 0.356
GrtdGGNNFEgcRWSS
98.069 + 0.115
70.260 = 0.341
GPS+EdgeRWSE
98.245 + 0.070
72.417 + 0.221
Zinc. Zinc-128 is a subset of 250k-250k, which consists of 12000 molecular graphs from the ZINC database of commercially available chemical compounds. The task is perform graph-level molecular property regression (on constrained solubility logP). These molecular graphs are between 9 and 37 nodes large. We follow the common predefined 10K/IK/IK train/validation/lest split.
MNIST and CIFARIO. These two datasets both contain directed graphs, and are derived from like-named image classification datasets. Both of them are 10-class classification tasks, and we follow the standard dataset splits as the original image classification datasets, i.c., 55K/5K/10K for MNIST and 45K/5K/10K for CIFARIO of train/validation/tes graphs, respectively.
oolg- and common node (atom) and edge (bond) featurization represent chemophysical properties. In detail, the prediction task of ogbg-molhit is binary classification of the fitness of molecule to inhibit HIV replication, which is measured by AUROC. The task of ogbg-molpcba is a 128-task binary classification, evaluated by average precision.
They are both molecular property prediction datasets, using
PCQM-Contact. It a dataset derived from PCQM4My2 and the corresponding 3D molecular structures. The task is binary link prediction which is evaluated by the Mean Reciprocal Rank (MRR).
Peptides-func and Peptides-struct. These two datasets both consist of atomic graphs of peptides. The task for Peptides-fund is multi-label graph classification into 10 nonexclusive peptide functional classes measured by average precision. The task for Peptides-struct graph regression of 11 3D- structural properties of the peptides measured by MAE.
E.2 Full experiment results
While SOTA and highly competitive results on Zine, ogbg-molhiv and ogbg-molpeba are shown in the main text, we further discuss the performance of our methods on other datasets here, including synthetic datasets and real-world datasets. For real-world datasets including BenchmarkingGNNN [17]
and Long Range Graph Benchmark (LRGB) [19], follow the experimental settings of
38 and
31

---

Table 5: Experiments three datasets from long-range graph benchmarks (LRGB) 19 Highlighted are the first, second, third test results.
model
Peptidex-func (AP
Peptides-struct (MAE
PCQM-Contact (MRR 1)
GCN
0.5930 = 0.0023
0.3496 + 0.0013
0.3234 + 0.0006
GINE
0.5498 = 0.0079
0.3547 1 0.0045
0.3180 + 0.0027
GatedGCN
0.5864 = 0.0077
0.3420 + 0.0013
0.3218 + 0.0011
Lransfomer+LappE
0.6326 0.0126
0.2529 + 0.0016
0.3174 = 0.0020
SAN LapPE
0.6384 = 0.0121
0.2683 + 0.0043
0.3350 = 0.0003
SAN+RWSE
0.6439 = 0.0075
0.2545 1 0.0012
0.3350 + 0.0003
GPS
0.6535 = 0.0041
0.2500 1 0.0005
0.3337 + 0.0006
GateGGCN+EdggRWSE
0.6002 = 0.0048
0.2679 + 0.0015
0.3342 = 0.0008
GatedGCN+HodgelLL.
0.5926 = 0.0059
0.2632 + 0.0008
0.3336 = 0.0004
GPS-EdgeRWSE
0.6625 0.0042
0.2501 + 0.0012
0.3408 + 0.0003
GPS+HodgelLaap
0.6584 0.0033
0.2505 + 0.0014
0.3407 + 0.0004
do not perform hyperparamettr search, since our main goal verify that our Hodgel and EdgeRWSE can benefit the arbitrary base model.
Experiments on synthetic datasets. To verify the theoretical expressive power of Hodgel and EdgeRWSE, we carried experiments
classical synthetic datasets: EXP and SR25. EXP 1 contains 600 pairs of non-isomorphic graphs that 1-WL. and 2-WL. fail to distinguish. SR25 [ contains 15 non-isomorphic strongly regular graphs (i.e., 105 non-isomorphie pairs) that 3-WI. fails to distinguish. An accuracy of 50% on EXP and 6.67% on SR25 suggests the model fails to distinguish any non-isomorphic graphs in the dataset. The results are shown in Table 3 The 1-WL equivalent GINE back-end model can fully distinguish EXP and SR25 when augmented by Hodge I Lap and Full- RSSe-Edg, indicating that both methods can distinguish non isommoppic graph pairs that 3- WL (and 2-FWL) fails, which is consistent with our theoretical analysis.
Experiments on MNIST and CIFAR1O. Since the graphs are all directed, only the directed version of EdgeRWSE is applicable since a random walk can only go along the edge, while Hodge Lap is also applicable if we follow the strict directions of edges and simplices. Here, we evaluate the effectiveness of EdgeRWSE acting GPS model (which consists of a GatedGCN and a Transformer in each layer) achieves the best on MNIST and second best on CIFARIO. It is remarkable that simple GatedGCN is greatly enhanced by EdgeRWSE, achieving highly competitive performance on both datasets. This verifies the effectiveness of EdgeRWSE: models involving edge features.
GatedGCN and GPS, see Table 4 With EdgeRWSE, the
The results are shown in Table 5 the baseline results are adopted from 38]. On both Peptides-func and PCQM-Contact, GPS model with EdgeRWSE (we use undirected version) and Hodge Lap (we use projection method) achieve the best and second best performance. respectively. On Peptides-struct, the improvement of edge-level PE/SE is not significant for GPS, but is obvious for the GatedGCN base model. Admittedly, as pointed out by [44) the baseline models need some reassessing including byper-parameter searching, and there are more SOTA results. However, we emphasize that our results are obtained without hyperparameter searching our main goal is to verify the enhancement brought by EdgeRWSE and Hodge Lap to the baseline models. SOTA methods can always facilitated with our PE/SE achieve better performance.
Experiments LRGB.
Trajectory prediction. Since our methods originate from simplicial complexes, we also verify the effectiveness of our Hodge Lap on simplicial data. We adopt the trajectory prediction task (edge flow classification) in [8]. The edge flows are represented as signals on oriented simplicial complexes. We use the same synthetic dataset of trajectories on the simplicial complex in (8). where each triangle is treated as 2-simplex. There are two holes the complex, and all trajectories pass one of the holes, thus giving rise to two different classes to be distinguished. Due to the presence of the two holes, the trajectories of the two classes approximately correspond to orthogonal directions in the space of harmonic cigenfunctions of the L₁ Hodge-Laplacian (T). The dataset contains
32

---

Table 6: Trajectory classification accuracy on synthetic flow dataset with simplicial networks.
model
Train accuracy
Test accuracy
MPSN
8
Lo-inv
88.2 + 5.1
85.3 + 5.8
MPSN 1d
88.0 + 3.1
82.6 + 3.0
MPSN
Tanh
97.9 + 0.7
95.2 + 1.8
MPSN Lo-inv HLd
98.4 +
99.8 0.4
MPSN Id Hodge
99.5 + 0.2
99.3 = 0.3
MPSN 'Tanh + Hodgel
100.0 + 0.0
99.9 = 0.1
1000 train trajectories and 200 test trajectories. Following 8 to make the task more challenging for non-orientation-invvaiann models, all training complexes use the same orientation for the edges, while the test trajectories use random orientations. We adopt orientation -invariiionnnvriiant message- passsng simplicial networks (MPSN) [8] with orientation equivariant layers as the base models.
Note that since we aim to distinguish two orthogonal directions in the harmonic kernel space of L Hodge-Laplacian, we do not use the projection implementation of Hodge instead, we use the simple implementation Hodgel Lapsimm (described in the main text) which embeds two eigenvectors respectively with a shared MLP. Theoretically, we can distinguish the two classes of flows with the help of eigenvectors since they correspond to two distinct cycles (i.e., two orthogonal directions in the kernel space). As shown in T all variants of MPSN achieve better performance (almost perfect test accuracy) when they are augmented with our Hodge Lap. This is consistent with our theory, which experimentally verified the capability of Hodge Lap to distinguish cycles.
E.3 Experiment details
Dataset split and repetitiveness. In all experiments, the datasets follow the common train/validation/tess split as we stated in datasets description. The results of the baseline mod- els are reported from (38]. For our results, we report the test results according to the best validation results. All experiments are run under 5 different random seeds, with mean and variance reported.
Hyperparameters. To verify that our methods are capable of improving the performance of the base models, all hyperparameters including training configuration and model hyperparameters set the same as [38]. For the edge PE/SE, we keep the embedding dimensions the same as the node PE/SE in GPS models. Hence, our experimental results strongly confirmed that our methods are beneficial for both naive and complex base models.
E.4 Implementation details
In this subsection, we provide more implementation details of our methods and more discussion on the corresponding variants. Our code is based on GPS [38. which enable to integrate our methods into a comprehensive graph learning framework.
EdgeRWSE. In real-world datasets, we use both directed 1-down RWSE and undirected 1-down RWSE in our experiments, except in MNIST and CIFARIO where only a directed walk is appropriate on the directed graphs. We also integrate variance of each row in the transition matrix corresponding to the target edge each step by an MLP. Generally, directed and undirected versions reveal similar performance, and report the performance of undirected EdgeRWSE if not specific.
For Full EdgeRWSE, we verify its theoretical expressive power through experiments on synthetic datasets; see Table 3 A GINE enhanced with Full EdgeRWSE achieves 100% performance on the synthetic datasets EXP and SR25. To fully distinguish EXP and SR25, the model needs to be more expressive than 1-WL and 2-FWL, respectively. This shows that Full-EdgeRWSE is (partly) more powerful than 2-FWL (3-WL), which consistent with our theory. In comparison, 1-down EdgeRWSE that does not consider 2-simplices fails (0%) to distinguish strongly regular graphs in SR25. However, we experimentally find that the performance of Full-EdgeRWSi on zine dataset similar to I-down EdgeRWSE with GINE base model. This is because 2-simplices (or triangles)
33

---

are actually rare in molecules, so Full-EdgeRWSE makes no significant difference than 1-down EdgeRWSE.
We also implement the interorder random walk among 0, 1, 2-simplices. The random walk probability AB (7 matrix is the normalized A2 in our main text. We compute , the diagonal elements for both node and edge features. The performance of GINE augmented with Inter-RWSE is significantly better than pure GINE but is slightly weaker than simultaneously applying NodeRWSE and EdgeRWSE (which are separately computed without inter-order communications) We attribute it to: (i) lack of tuning hyper-parae parameerrssterss such as T, and (ii) the return probabilities are much less in inter-order random walk, as there are totally + m possible targets, instead of n for O-random walk and m for 1 I-random walk. This makes harder for the model to learn meaningful structure information and may require larger T.
20 for Zine) and embed
The concept of CellularRWSE is explained in Appendix C.3 edges as 1-cells and extract all the rings (cycles) as 2-cells. In this CellularRWSE, a random walk is able to transit from one source edge to (i) another target edge sharing one node, or (ii) another target edge that is in the same 2-cell as the source edge. The performance is slightly better than EdgeRWSE (see Table which may be due to the ability to distinguish higher-order structures (rings and eycles).
CeltularRWSE
where we treat the
HadgelLap. We already include a detailed discussion in the main text and in Appendix C.2.2 on two different implementations: projection-baser methods and sign-invariant methods. As we have shown, the projection method HodgelLappred is both sign and basis invariant, and we consider the subspace spanned by eigenvectors of zero eigenvalues. The sign-invariant method Hodge LLapass simply takes absolute values of eigenvectors element-wise, and uses a MLP to encode eigenvectors and eigenvalues. We additionally apply MLP to learn eigenvalue- eigenveeeeeee pairs of Hodge-I I Laplacians in our Hodge Lap implementation. In practice, we adopt the combination of these two methods; if not specific, we report the results of the combined variant.
We the cosine similarities of the node features our distance metric. The drop probability follows Equation (76). In each layer, we use a normal GINE layer without RWMP and a GINE layer with RWMP and add their features the final representation of the layer. The GINE (25) model with Hodge and RWMP achieves highly competitive performance on Zine, outperforming and Specformer (6)
RWMP.
GPS 3
Other implementation details. below.
Some other implementation details and discussions are summarized
For SSWL+, add edge PE/SE features embedded by unique linear projection to the original edge features in every layer.
For GRIT, the PE is embedded by linear layer and then directly added to the edge features. For virtual edges, the PE values are padded as zeros.
Our method is can be applied to higher-order GNNs, including simplicial networks g and 2-8-FWL equivalent classes [36], while others (SPD, RD) cannot. Our method is also more sparse.
Our method can be applied to any base model without increasing much computation cost and can be applied together with other levels of PE/SE.
There are more than one way to integrate PE/SE into the models, while we choose the most simple ones: we treat PE/SE as initialization edge features by concatenating or adding them to the original edge features; they can also be used as in graphormer (as attetion biases), or any convolution/aatenniio computation in simplicial networks.
E.5 Complexity and applicability analysis
Theoretically, the complexity to generate Hodgel and EdgeRWSE are both O(m²), where m the number of edges. For small or sparse graphs, they share similar complexity with node-level PE such as LapPE and RWSE. For example, the average generation times on Zinc computed by RTX3090 are: RWSE (23s), Ed (32s), Hodgell.ay (28s). Even for extremely large graphs with millions of nodes, we can handle by sampling subgraphs are only interested in the local
34

---

structure information for some PE/SE. For example, for s-step EdgeRWSE,, we can sample K K-hop subgraph rooted at the target edge and continue to process, without having deal with large matrix multiplication. It is noticeable that we only have to preprocess once for every dataset, so the precompute time is negligible compared to experiment time.
For the computation complexity in the forward pass of models, since all our PE/SE are embedded by light-weight MLPs, the extra computation cost is completely ignorable compared with the whole model. In summary, our methods are able to significantly enhance model performance with extremely small additional computation cost.
Regarding applicability, on the base model side, our Hodge Lap and EdgeRWSE are universally applicable any base model long edge features are considered. Our methods orthogonal to other PE/SE and can be used together. SOTA methods can always be facilitated with our methods to achieve better performance. On the data type side, we have emphasized, our methods are applicable to (both directed and undirected) graphs, simplicial complexes, and other discrete topological data structures, e.g. cellular complexes.
35


Reviews:
[{"review_id": "07j3dzGBso", "reviewer": "Reviewer_Djvd", "summary": "Authors propose leveraging the random walk on different orders of the simplicial complex domain to enhance graph neural networks both in their performance and in the understanding of their theoretical expressivity. \n\n$\\textbf{Node level}$\n\nAuthors frame existing positional encoding (PE) and structure encoding (SE) methods in the context of random walk on 0-th order simplices and the traditional graph Hodge Laplacian $\\mathbf{L}_0$. Using this framework, they provide a theoretical expressivity bound for RWSE, a SE method, and provide an intuitive explanation of its nature. They summarize PE methods and their expressivity bounds from the literature.\n\n$\\textbf{Edge level}$\n\nAuthors introduce two novel edge-level PE and SE methods:\n- EdgeRWSE, which directly generalizes random walk on nodes to edges, with 3 variations: full (upper and lower adjacency), down adjacency directed, and down adjacency undirected. Authors test the directed/undirected down variations on graph regression (not competitive). Authors test a variation on graph-level classification (not competitive, overfits).\n- Hodge1Lap, the first sign / basis invariant edge-level PE, with 1 variation based on the spectra of the Hodge 1 Laplacian. Authors test sign invariant and sign / basis invariant Hodge1Lap on graph regression (SOTA). Authors test a variation on graph-level classification (competitive).\n- Random Walk Message Passing, a new random walk method based on a metric of node feature similarity. Authors test it on graph regression (SOTA) and show that it can improve the performance of Hodge1Lap (competitive).\n\n$\\textbf{k-level}$\n\nAuthors extend the theoretical framework of the random walk on simplicial complex arbitrary order $k$ by proposing:\n- a method that extends RWSE to $k$-order.\n- inter-order random walk, a method that utilizes the upper/lower boundary neighborhoods of a $k$-simplex.\n\nSupplementary materials provide mathematical proofs for expressive bounds, further theoretical analysis of proposed methods, explain RWMP and provide further experiments on MNIST, CIFAR10, and LRGB.", "questions": "- Could the proposed methods generalize to discrete domains without orientation, where the adjacency matrix is set-type (all positive) as in hypergraphs? And if so, how would their design/performance compare to previously introduced methods [1,2]?\n- Is there an intuitive explanation for the state-of-the-art (SOTA) results achieved in the long-range graph benchmark task, particularly in relation to the additional reach that random walk methods gain from neighborhood structures? From my perspective, these impressive results should have been included in the main text. It could be direct proof of the benefits of simplicial complex-based random walks.\n- What variations of EdgeRWSE and Hodge1Lap were used in the graph classification benchmark task? They are not specified in the table or in the text.\n1. Carletti, Timoteo, et al. \"Random walks on hypergraphs.\" Physical Review E 101.2 (2020): 022308.\n2. Chitra, Uthsav, and Benjamin Raphael. \"Random walks on hypergraphs with edge-dependent vertex weights.\" International conference on machine learning. PMLR, 2019.", "limitations": "- The authors highlight the overfitting behavior of EdgeRWSE in graph classification. It would have been interesting to see how different variations of EdgeRWSE compare in terms of overfitting when applied to datasets with higher-order features. Additionally, it would have been valuable to understand if this overfitting limitation is also at play in the non-competitive performance on Zinc 12k.\n- A significant limitation left unaddressed in the paper is the single topological domain. While the paper focuses on simplicial complexes, all of its proposed methods and Hodge Laplacian theory could fit into a larger framework of topological domains, including cellular complexes and hypergraphs. Each random walk could be generalized to such domains and tested on respective datasets. If any theoretical reasons prevent such an extension, the authors should clearly outline and explain the reasoning behind this limitation.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper presents a comprehensive and wholesome approach to higher-order random walk, addressing 0, 1, and higher orders in a systematic manner.\n- It offers a thorough and detailed background in preliminaries, providing a solid reference for the underlying concepts. The supplementary materials are additionally thorough.\n- Authors provide intuitive explanations for the theoretical bounds and the functioning of the PE/SE methods. Reframing pre-existing methods in a fresh, accessible way is a valuable contribution. In the same vein, observed performance increases are supported by a sound theoretical justification, lending credibility to the results obtained.\n- The regression experiments conducted on top of the GINE model are convincing, demonstrating the effectiveness of the proposed methods in graph regression tasks.\n- The introduction of the clever new method RWMP opens the door to a new and flexible class of random walks based on the concept of a \"feature distance\" metric. This could be the first such method of many, as new metrics are defined on different feature orders with different probabilities.", "weaknesses": "- Implementing the (appropriate) proposed methods on higher-order datasets would have been a significant contribution. Based on the increased performance of Hodge1Lap which benefits from upper adjacency schemes, I would have been very interested to see the full EdgeRWSE, and the inter-order random walk in action. Lifted benchmark datasets, including Zinc 12k [1] are common in topological deep learning research to allow for comprehensive testing of proposed methods. \n- While the paper introduces a valuable theoretical bound for a pre-existing method at the node level, this remains a case-by-case study of theoretical expressivity. This section would have been much more meaningful if it generalized this special case to a systematic method for bounding PE/SE methods from the random walk framework.\n- Authors make no mention of other discrete topological domains, cellular/cubical complexes being the most obvious, and how their proposed methods extend to datasets defined on these domains. This low-hanging fruit would be an important contribution to the cellular complex domain which only differs from the simplicial complex in the construction of higher-order features.\n- It would have been preferable to observe the proposed methods integrated with a wider range of neural network architectures, beyond just GINE, GPS, and GatedGCN. While the authors argue that the simplicity of these architectures showcases the power of their methods, I am still curious to see how these techniques impact the performance of more complex models like transformers and subgraph variations. Are there still significant improvements observed in these cases?\n- There are many syntax and grammatical errors in the text that could be easily caught with spell-checking software like Grammarly. Here are $\\textit{some}$ examples :\n    - line 106: \"there are still limited research\" should be \"there is still\"\n    - line 108: \"establish several connection\" should be \"establish several connections\"\n    - line 109: \"provide theoretically expressive bound\" should be \"provide a theoretically expressive bound\"\n    - line 129: \"resistance in electrical network\" should be \"resistance in an electrical network\"\n    - line 484 in supplementary materials: \"an function\" should be \"a function\"\n\n1. Bodnar, Cristian, et al. \"Weisfeiler and Lehman Go Cellular: Cw networks.\" Advances in Neural Information Processing Systems 34 (2021): 2625-2640.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable review and constructive points. We address them all as follows.\n\nWeakness\n\n1. Implementing higher-order and inter-order random walk: Thank you for your advice. We have newly implemented full EdgeRWSE and inter-order random walk in experiments, which we believe is huge contribution. (1) **Full-EdgeRWSE:** we implement Full-EdgeRWSE and show that a GINE augmented with it achieves $100\\%$ performance on synthetic datasets EXP and SR25. To fully distinguish EXP and SR25, the model need to be more expressive than $1$-WL and $2$-FWL, respectively. This show that Full-EdgeRWSE is (partly) more powerful than $2$-FWL ($3$-WL), which is consistent with our theory. In comparison, 1-down EdgeRWSE that does not consider 2-simplices fail ($0\\%$) to distinguish any strongly regular graphs in SR25. The performance of Full-EdgeRWSE on zinc dataset is similar to 1-down EdgeRWSE with a GINE base model. This is because 2-simplices (or triangles) are actually rare in molecules, so Full-EdgeRWSE makes no significant difference than 1-down EdgeRWSE. (2) **Inter-order random walk:** we implement the inter-order random walk among $0,1,2$-simplices. The random walk probability matrix is the normalized $\\mathcal A_2$ in our main text. We compute $\\mathcal A_2,\\dots, \\mathcal A_2^T$ ($T=20$ for Zinc) and embed the diagonal elements for both node and edge features. The performance of GINE augmented with Inter-RWSE is significantly better than pure GINE, but is slightly weaker than simultaneously applying NodeRWSE and EdgeRWSE (which are separately computed without inter-order communications). We attribute it to: (i) lack of tuning hyper-parameters such as $T$, and (ii) the return probabilities are much less in inter-order random walk, as there are totally $n+m$ possible targets, instead of $n$ for 0-random walk and $m$ for 1-random walk. This makes the model harder to learn meaningful structure information and may require larger $T$.\n\n2. Case by case analysis on node-level random walk: We provide the following conclusions for node-level PE/SEs:\n - RWSE is strictly less powerful than $2$-FWL.\n - SPDPE (shortest path distance) is strictly less powerful than $2$-FWL.\n - RDPE (resistance distance) is strictly less powerful than $2$-FWL, but more powerful than SPDPE in distinguishing non-isomorphic distance-regular graphs.\n - RRWP is strictly less powerful than $2$-FWL, but is strictly more powerful than SPDPE.\n - HK (heat kernel) is strictly less powerful than $2$-FWL.\n\nThe second and third conclusions are from [30]. RRWP is originally proposed in [5], and we newly bound it with $2$-FWL. We will provide full proof in the revision paper. The core idea of the proof is that 2-FWL can simulate the multiplication and injective\ntransformations of matrix (including adjacency matrix $\\mathbf A$), so that $2$-FWL is able to obtain all the information of these PE/SE (e.g. degree, triangles, 4-cycles). Although node-level random walk is not our main focus, we believe the above case-by-case analysis is valuable to understand the limitations of PE/SE based on node-level random walk.\n\n[30] Rethinking the expressive power of gnns via graph biconnectivity.\n\n[5] Graph Inductive Biases in Transformers without Message Passing.\n\n3. Other discrete topological structures: In line 399-402 of supplementary, we do mention other discrete topological structure such as cellular complex. We do not generalize our methods to these domain in the original version because of the limited space, and that our original contents are already fairly rich. It's also harder to theoretically analyze the expressive power of all possible cellular complexes case by case, since the definition of these topological structures are rather flexible. However, we do implement (the first-time ever) SE based on random walk on cellular complexes in our new experiments. As simple version, we treat edges as $1$-cells and extract all the rings as $2$-cells. In this CellularRWSE, one is able to transit from one source edge to (i) another target edge sharing one node, or (ii) another target edge that is in the same $2$-cell as the source edge. The performance is slightly better than EdgeRWSE (see Table 1), which may due to the capability to distinguish higher-order structures (rings).\n\n4. Applying methods to more architectures: In our new experiments, we apply our PE to: (a) GAT; (b) PNA; (c) SSWL+; (d) GPS; (e) GRIT, where SSWL+[3] is one subgraph GNN backbone and the latter two are graph transformers. We see significant improvements for all these kinds of base models, please refer to Table 1 and common comment for more details.\n\n[3] A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests.\n\n5. Sorry for the grammar mistakes, which we will correct in the final version.\n\nQuestions\n\n1. Generalization: Our methods indeed can be extended to discrete domains without orientations, which we also pointed out in our paper. In detail, for HodgeLap families, the Hodge Laplacians can be calculated whenever incidence matrix $\\mathbf B_k$ (or boundary operator) is defined, see equation (5-6) in supplementary. For spatial domain random walk families, we can perform undirected random walk on these structures without orientation (e.g. EdgeRWSE for undirected graph, as described in line 169-173 in main text). They can all be naturally applied to hyper-graphs.\n\n2. Long range information: Random walk methods are actually capable of capturing long-range information. For examples, a K-step node-level random walk is able to explore the K-hop subgraph around the root node. In our experiments, the number of steps are typically set as K=20, so it is able to capture long-range information and perform well on LRGB datasets.\n\n3. Variations: We primarily explain the variations of Hodge1Lap and EdgeRWSE in Section 5.3 (line 558-569) in supplementary. If not specific, we use undirected version of EdgeRWSE, and projection implementation of Hodge1Lap."}, {"review_id": "Z5rXZogFl7", "reviewer": "Reviewer_1k26", "summary": "Positional and structural encodings have been widely studied, especially in the context of graph transformer architectures where such encodings often make up for the lack of inductive bias provided by the original graph, due to dense connectivity in the attention mechanism. RWSE (random walk structural encodings) are common approach based on random walk probabilities of a node returning to itself after differing numbers of steps. The authors build on this work, drawing from theory of simplicial complexes and Hodge deRham theory, to propose a set of edge-level positional encodings. They provide theoretical analysis of the proposed technique and evaluate its effectiveness by incorporating the positional encodings into MPNNs and/or graph transformers on a number of datasets, including ZINC, as well as datasets from the OGB and LRGB collections.", "questions": "-The experiments on ZINC appear to use a standard MPNN (GINE) for the purposes of testing out the authors' random walk simplicial complex based approach. On the other hand, the experiments on OGB appear to be based on GPS framework which uses a combination of graph transformers and MPNNs. Is there a reason for this choice? Have you tried using the proposed random walk simplicial encodings with GPS/graph transformers on ZINC? This would be interesting, as positional and structural encodings are particularly critical for graph transformer architectures where the inductive bias provided by the original graph is lost due to dense connectivity.\n-Suggestion: It should be noted that for several of the LRGB datasets you consider in the appendix, there are improved results, so the results by the authors are not quite SOTA. For instance, the recent Exphormer [1] paper improves on GraphGPS numbers for most of the LRGB datasets. Please include this baseline..\n-It is not clear to me which results are new among the theorems (e.g., Thms. 5.2, 5.3 and the ones in the appendix) as opposed to previously known. It would be good for the authors to clarify this\n\n\n[1] Exphormer: Sparse Transformers for Graphs - Shirzad, Velingker, Venkatachalam, Sutherland, Sinop. ICML 2023.", "limitations": "I could not find a discussion about the limitations of the authors' proposed technique. However, it is possible that I have missed it. Societal impacts are not relevant to this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors consider an interesting question around positional and structural encodings, which have been widely studied. The authors introduce an interesting approach using Hodge Laplacians that build on previous work.", "weaknesses": "-The paper seems a bit rushed and has some typos. The paper can benefit from some careful proofreading.\n-Given that this work proposes GNNs based on techniques related to simplicial complexes, I would have liked to see experimental comparisons to some existing architectures based on simplicial complexes (e.g., [3], [4], [28] in the paper) or other topological baselines.\n-The experimentation on OGB benchmarks has very little explanation. I would like to see more details about the setup and design choices.\n\nI find the authors' approach interesting but think the experimental evaluation section could be stronger in general. I'd be willing to raise my score upon answers to the below questions and some actions to address the points stated above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. We address them all in the following.\n\nWeaknesses:\n\n(1) Typos: We will carefully proofread the paper, fix the typos and improve the writing. \n\n(2) Comparisons to existing architectures based on simplicial complexes (e.g., [3], [4], [28]): First, [3, 4, 28] are network architectures while our methods are PE/SE, so they are in some sense orthogonal to ours and cannot be directly compared. Nevertheless, [3] is actually just CIN, which is already compared in the tables of our paper. CIN is SOTA on ogbg-molhiv, but our methods generally perform better than CIN, for example on Zinc. Note that CIN is also heavily hand-crafted as it extracts cellular complexes, while our methods are more general and do not rely on prior/domain knowledge. [4] and [28] mainly conduct experiments on simplex datasets, which cannot be easily generalized to graph datasets; in comparison, our methods can be easily generalized to simplicial complexes. We test on synthetic dataset from [4], and show that MPSN(tanh) augmented with Hodge1Lap can achieve over $99.5\\pm 0.3$% test accuracy, exceeding SOTA baseline ($95.2\\pm1.8$%) in Table 1 of [4] (MPSN). This is consistent with the experimental analysis in [4], that the model needs to learn two approximately orthogonal components in kernel space of $\\mathbf L_1$, while Hodge1Lap can perfectly achieve this target (however not by projection as described in our main text, but learn two eigenvectors jointly through a linear layer; the invariance and equivariance are guaranteed by MPSN base model).\n\n(3) Explanation on OGB experimentation: The setup of experiments on OGB are the same as GPS for a fair comparison. However, the performance on ogbg-molhiv and ogbg-molpcba are less convincing to evaluate models: SOTA results on ogbg-molhiv typically involve manually crafted structures, including molecular fingerprints, GSN and CIN, while general methods and expressive models usually suffer from overfitting and cannot generalize well on the test set. We apply our Hodge1Lap and EdgeRWSE to both GatedGCN and GPS (consisting of GatedGCN and Transformer) and show that our methods can improve both architectures. However, the overfitting phenomenon still exists.\n\nQuestions:\n\n(1) Why choosing GINE (MPNN) as backbone: On Zinc dataset, GINE and GPS (with transformer) have similar performance according to the original GPS paper [23]. Therefore, to reveal that even a simple MPNN-like architecture can benefit from our proposed PE/SE, we choose GINE as the backbone model on Zinc. It's true that PEs are indeed more beneficial for graph transformers. In our new experiments (see Table 1 in the new pdf), we apply our methods to: (a) GAT; (b) PNA; (c) SSWL+; (d) GPS; (e) GRIT, whereas the latter two are recent state-of-the-art graph transformers. Our new experiments show that our methods are beneficial for a wide variety of architectures, including message-passing based and attention based models. By integrating Hodge1Lap, the test MAE on zinc decreases from $0.070$ to $0.064$ for GPS, from $0.059$ to $0.057$ for GRIT (which is SOTA performance on Zinc to the best of our knowledge). Similar improvements are also observed for EdgeRWSE, which verifies that our PE/SE are benificial for graph transformers. Remarkably, GPS and GRIT benefit from our edge-level PE in different ways. GPS adopts a standard transformer, so the only way to integrate edge features is through the local message-passing module (GINE in our experiments). In comparison, GRIT explicitly reserve the expanded edge features for every possible node pairs, which is able to process edge features without a local module. As for OGB benchmarks, we choose GPS as the backbone because it generally performs better than MPNN families.\n\n(2) Including the recent Exphormer: We have included this baseline. The performance of Exphormer with/without Hodge1Lap and EdgeRWSE are in Table 2 of the new pdf. However, we re-run the Exphormer experiments and find that the actual performance we obtained are weaker than the reported ones in their paper. We are still working on this point. \n\n(3) Which theoretical results are new: Section 1 and Section 2 in the appendix give the background information and summaries of previous results. We formally present our new conclusions and proof in **Section 4-6 of the main text** and **Section 3 of the appendix**. To the best of our knowledge, all these formally presented theorems in the main text (Theorem 4.1, 5.1 - 5.3) and Section 3 of the appendix (Theorem 3.1 - Theorem 3.13) are **newly proposed**. We make close connections of these mathematical properties with the Weisfeiler-Lehman expressive power hierarchy, and we also provide rigorous proofs for all these new theorems. Nevertheless, there may be cases where part of conclusions or proofs are borrowed from existing results, which have all been annotated in the statement or proofs in our original text."}, {"review_id": "OIsi73ZnAG", "reviewer": "Reviewer_r8fz", "summary": "The paper studies random walks over simplicial complexes to construct novel positional and structure encoding methods for improving graph neural networks.\nIn particular, the authors propose two strategies to construct edge embeddings, namely EdgeRWSE (via random walks on the edges) and Hodge1Lap (via spectral analysis of the Hodge 1 Laplacian).\nFinally, these constructions are theoretically generalized to higher order simplices for generic simplicial complexes.\n", "questions": "\nlines 248-249: the use of the terms sign-invariant and basis-invariant seems confusing since I don't see a group action. It seems more natural to describe this issue in terms of \"uniquess only up to a sign / change of basis\". I would at least mention this fact more explicitly to motivate the choice of words sign/basis-invariant.\n\n\n\nlines 268-272: while the kernel space of $L_1$ can count all cycles (as a vector space, it has a dimension per cycle), detecting individual cycles is - as far as I know - a more complex problem which boils down to finding particular sparse bases for the first (co)homology group (i.e. the kernel of $L_1$).\nThe projection of the constant vector $\\boldsymbol{e}$ in eq. 5 only spans a 1 dimensional subspace of the (co)homology group so it can not detect all cycles.\nFor this reason, I find the claim that Hodge1Lap can extract cycles in a natural way requires some further comments and clarification.\n\n\nline 289: could you provide some intuition about why the lifting is done this way? For example, why is the lifting done to a 2-times larger space rather than a $(k+1)!$ times larger one (one copy for every permutation of the nodes in a simplex)?\n\n", "limitations": "There is not explicit discussion of the limitations of the method.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper is clearly written.\nThe contributions are relevant and the ideas proposed seem novel.\nIn particular, I liked the idea of using the Hodge Laplacian's kernel to enrich the GNN with some information about the graph's cycles.\n", "weaknesses": "Section 6 generalises the method to higher order simplexes but it doesn't seem necessary in the main paper, which instead discusses only normal graphs.\nThis generalisation is not used in the experimental section either.\nI feel like Section 6 could be safely moved in the supplementary material to keep the paper more focused on the main applications and contributions, but I am open to discussions about this.\nThis could free some space to include the details about the RWMP method, which is currently missing from the main paper.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the review for acknowledging our work and the useful advice. In the new revision of our paper, we will introduce RWMP in the main text. However, we believe that Section 6 is a necessary part. This section generalize our theories, showing that our method can be extended to any higher-order structures. We have also implemented some higher-order and inter-order PE/SE instances in our new experiments to make it more contributive.\n\nNow we answer your questions as follows.\n\n1. Sign/basis invariance: To our knowledge, sign and basis invariant are actually widely considered in graph learning field, for example [19] gives a thorough discussion. Here sign and basis refer to the ones of eigenspaces instead of group action. However, it's indeed easier for common readers to understand if we describe it as \"invariant to the choice of sign and basis of eigenvectors\".\n\n[19] Sign and Basis Invariant Networks for Spectral Graph Representation Learning - Derek Lim and Joshua Robinson and Lingxiao Zhao and Tess E. Smidt and Suvrit Sra and Haggai Maron and Stefanie Jegelka.\n\n2. Ability to detect cycles: Besides counting cycles, the eigenvectors in the kernel space of $\\mathbf L_1$ can indeed **detect individual cycles**, i.e. the basis for first cohomology group. We describe in detail how the cycles are counted and detected in **Section 3.2.2 of supplementary (Theorem 3.9-3.11)**. It's remarkable that in eq. (5), $P_{proj,i}$ is the projection matrix to a subspace with dimension $m_i$ instead of one-dimension, see eq. (4). If we want to detect cycles, $\\lambda_i=0$, then $m_i$ is the multiplicity of zero eigenvalues, which is also the first-order Betti number $\\beta_1$ (also the number of cycles). Hence, this $m_i=\\beta_1$-dimensional subspace is able to detect all $m_i=\\beta_1$ cycles. Please inform if you need any further clarificaions.\n\n3. Explanation of lifting: This is because any higher-order k-simplex (k>0) only have 2 possible orientations instead of $(k+1)!$ (which is a fact that is often confused). Generally, the orientation is defined according ${\\rm sgn}(\\sigma)$ in eq. (1) of supplementary, where $\\sigma$ is the element in the symmetric group $\\mathcal G_{k+1}$. While there are $(k+1)!$ different permutations $\\sigma$, there are only two directions depending on ${\\rm sgn}(\\sigma)$, i.e. whether it is an even or odd permutation. All even permutations are equivalent in their direction, so do all odd permutations. For example, for a triangle $k=2$, there are obviously only two directions instead of $(k+1)!=6$. This applies to all higher-order simplices. Since the lifting is only for enumerating possible directions, 2-times larger space is enough rather than $(k+1)!$ times larger one."}, {"review_id": "ULwKkzEh1h", "reviewer": "Reviewer_kVcw", "summary": "A major issue with graphs is the absence of positional information on nodes, which decreases the representation power of GNNs to distinguish e.g., isomorphic nodes. An approach to tackle this issue is to introduce Positional Encoding (PE)  and Structural Encoding (SE) of nodes and inject it with node features. Most PE and SE techniques are based on node-level (0-simplices ) and edge-level (1-simplices ) random walk features. This paper analyzed the theoretical expressivity of node-level and edge-level random walks. The authors also introduce EdgeRWSE and Hodge1Lap,  new edge-level random walk-based features that make GNNs more powerful.  The authors analyzed theoretically the expressivity of these methods. They also introduced and generalized the study to random walks on higher-order simplices. The proposed approaches were tested empirically on many datasets and achieved competitive results with state-of-the-art methods.", "questions": "In the weaknesses part above, I have included most of my questions to the authors. One more question follows below.\n\n- From Tables 1, 2 in the main paper and Tables 1, 2 in the supplementary material,  I couldn't see a huge improvement in the performance when using EDGERWSE and Holde1LAp methods. Could you please further elaborate on this point?", "limitations": "Some of the limitations of the proposed methodology have been discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and organized. I appreciated sections about 0-simplices,1-simplices and high-order simplices.\n\n- It introduces a reasonable way to facilitate the expressivity of GNNs through positional and structural encodings.\n\n- The paper studied and analyzed the theoretical expressivity of node-level, edge-level random walks.\n\n- The paper generalized the random walks to high-order simplices and analyzed their expressivity.", "weaknesses": "The main weaknesses of the paper have to do with the empirical analysis. \n\n-   The combination of GNNs with EDGERWSE and HODGE1LAP has been tested only for GPS and GINE architectures. To validate the assumption that ‘EDGERWSE and Holde1LAp improve the performance of GNNs’, the combination should be tested for other GNN architectures as well, e.g., GIN, PNA, etc. Especially since the proposed positional and structural encoding is applicable to any standard GNN.\n\n- The experiments have been performed for graph-level tasks only (mainly graph classification and graph regression tasks). What is the performance of such approaches on node classification tasks?\n\n- The comparison with previous random walk-based PE and SE is missing, i.e., methods in papers [31,1,30,19]. EDGERWSE and Holde1LAp should be compared with the PE and SE baselines using the same GNN architecture. \n\n- The time complexity for generating EDGERWSE and Holde1LAp is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable reviews. We address the weakness and your questions as follows.\n\n1. Test on more GNN architectures: In our new experiments, we apply our Hodge1Lap and EdgeRWSE to a variety of different GNN models, see Table 1 and general response for more details. For all base models, we verify that our methods are capable of improving empirical performances.\n\n2. Node classification tasks: Generally, node classification tasks do not need so much structure information, and papers in the relevant field of GNN expressive power usually pay more attention to graph-level tasks. However, to show that our method is also beneficial for node-level tasks, we add experiments on Brazil-airports datasets [8]. We use GAT as our baseline model and evaluate the effectiveness of EdgeRWSE. Since the node classification is closely related to local structures, number of layers of GAT is set to 3 as in [8], and number of walk steps of EdgeRWSE is set to 10. We report mean test accuracy (with validation) over 20 seeds. By treating EdgeRWSE as additional edge features, the performance improves from $71.24\\pm 3.89$ to $75.83\\pm 2.61$, exceeding the best performance reported in [8] ($75.37\\pm 3.25$ for DEA-GNN-SPD). We are still working on more node-level tasks and will report the progress.\n\n[8] Distance Encoding: Design Provably More Powerful\nNeural Networks for Graph Representation Learning.\n\n3. Comparison with other random walk based PE/SE: Theoretically we have compared the expressive power of our methods and these random walk based PE/SE. Experimentally, we use GRIT as the common back-end model, and compare our methods with RWSE, SPDPE, RDPE and RRWP (reported in Table 1). We observe that Hodge1Lap and EdgeRWSE alone can improve the performance of backbone model, but slightly weaker than other PE/SE methods. However, we want to emphasize: (i) different models and tasks may benefit from different PE/SE, which is also observed in [4]; (ii) while SPDPE and RDPE are applied to $n\\times n$ node-pairs (only applicable to dense connectivity), our Hodge1Lap and EdgeRWSE only have values for real-edges, which is more sparse and more generalizable (directly applicable for real sparse edges, and applicable to dense connectivy via padding; (iii) our methods can be integrated with existing methods (e.g. node-level PEs), resulting highly competitive results.\n\n[4] Recipe for a general, powerful, scalable graph transformer.\n\n4. Computation complexity: Theoretically, the complexity for generating Hodge1Lap and EdgeRWSE are both $O(m^2)$, where $m$ is the number of edges. For small or sparse graphs, they share similar complexity with node-level PE such as LapPE and RWSE. For example, the average generation time on Zinc computed by RTX3090 are: RWSE ($23$s), EdgeRWSE ($32$s), Hodge1Lap ($28$s). Even for extremely large graphs with millions of nodes, we can handle by sampling subgraphs as we are only interested in the local structure information for some PE/SE. For example, for a $K$-step EdgeRWSE, we can sample a $K$-hop subgraph rooted at the target edge and continue to process, without having to deal with large matrix multiplication. It's noticeable that we only have to preprocess once for every dataset, so the pre-compute time is negligible compared with experiment time.\n\n5. Performance: We actually achieve several SOTA performance on Zinc and LRGB benchmarks. We also adopt some novel embedding methods (see general response for implementation details) and improve the performances. Again, we address that our methods are applicable to all kinds of GNN variations, but the performance gain depends on the base models and the tasks."}, {"review_id": "uYBQg9yRor", "reviewer": "Reviewer_j6x1", "summary": "The authors generalize node-level random walk positional and structural encoding to edge-level (1-simplex) and higher-order simplex random walks. They focus on the edge-level for both theoretical and empirical results. Their approach is motivated primarily through theory, and then expanded empirically to the algorithm level. In addition, the authors prove important results about their new algorithm, allowing their architecture to be strictly more expressive than 1-FWL. Empirically, their results outperform their selected baselines. ", "questions": "1. Are the new proposed approaches equivalent to RWSE and other approaches in terms of theoretical time complexity and practical compute time, memory, and parameters? \n2. Why were GINE, GPS, and GATEDGCN chosen as base models to augment?", "limitations": "The authors do not include many limitations in their work, but based on my understanding of the work, I believe that all limitations are implicitly addressed.\n\nI believe there are no potential negative societal impacts of their work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper's strengths lie in their novel approach to generalizing node-level random walks to edge-level and beyond. Although no empirical evidence is provided for the higher-levels, we see convincing empirical evidence that edge-level features contribute to the overall performance of the model. To the best of my knowledge, this is one of the first times that Hodge Laplacians have been used in GNN contexts, allowing the authors to apply their algorithms to practical examples. ", "weaknesses": "The paper's weaknesses lie in the lack of extremely convincing empirical results and the lack of clarity in the paper. \n\nEmpirically, the authors' new algorithms generally perform slightly better than their baselines; however, in around half the datasets provided, there exist other models which perform better than their algorithms. If possible, it would be more convincing to build their new algorithms on the current state-of-the-art models. Experiments on synthetic datasets that require models to be strictly more expressive than 1-FWL would also be helpful here (presumably, models with the proposed algorithms would perform drastically better).\n\nThe paper is unclear at times. Although the theory is interesting by itself, the importance of the results that were derived is not clear, and the algorithms are not explicitly defined anywhere. Explicit \"algorithm\" sections describing EdgeRWSE and Hodge1Lap would add much to the paper. Finally, the authors mention a \"novel Random Walk Message Passing scheme\" for the first time in the experiments section, with no prior explanation anywhere else in the paper. It seems a bit isolated from the rest of the paper; I would rather it be described in the body or in a separate manuscript entirely, instead of trying to fit into an already dense paper.\n\nThere also exist many grammar and syntactical mistakes scattered throughout the paper (examples: line 150 typo, 173 grammar, 263 typo).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review points. We address your questions as follows.\n\nWeakness\n\n1. Applying to SOTA baselines: We have applied our method to SOTA baselines, including GRIT[5] and Exphormer[6]. We also improve the performance by improving the implementation and hyper-paremeters of Hodge1Lap and EdgeRWSE. Please refer to general response for details.\n\n[5] Graph Inductive Biases in Transformers without Message Passing. ICML 2023.\n\n[6] Exphormer: Sparse Transformers for Graphs - Shirzad, Velingker, Venkatachalam, Sutherland, Sinop. ICML 2023.\n\n2. Experiments on synthetic datasets: We have conducted experiments on synthetic datasets, including EXP and SR25, two widely adopted synthetic datasets to measure theoretical expressivity. Both Hodge1Lap and Full-EdgeRWSE are able to achieve perfect performance on both two datasets, while other PE/SE fail. The results are consistent with our theoretical analysis that Hodge1Lap and Full-EdgeRWSE can distinguish some non-isomorphic graph pairs that $1$-WL and $3$-WL ($2$-FWL) fail. It's noticable that none of SPDPE, RDPE or RWSE can distinguish SR25 since they are strictly bounded by $2$-FWL in expressive power.\n\n3. Importance of our theories: We believe our theories are great contribution to both GNN theoretical expressive power and application communities. The results in Section 3 of supplementary (covering Section 4 - Section 6 in main text) are the first to reveal properties of PE and SE based on random walk on higher-order simplices as well as Hodge-$k$ Laplacians. We also make connections with existing $k$-WL hierarchies, showing that previous PE/SE are limited in their expressive power, while Hodge1Lap and EdgeRWSE can provably improve the expressivity of GNNs. Besides unifying existing methods including PE/SE and simplicial networks, we also propose novel Hodge1Lap/EdgeRWSE designs, along with a blue-print for designing higher-order and inter-order random walk based PE/SE methods. \n\n4. Writing and explicit algorithms: we do describe and discuss different possible implementation of Hodge1Lap and EdgeRWSE in our paper. We believe that equations (3) and (5) in main text is clear enough to express the design idea while enjoying great flexibility. There is no algorithm section in our original text, since our methods enjoy extremely flexible design space. For clarification, the general procedure is to compute positional/structure encoding statistics (e.g. eigenvalues and eigenvectors of $\\mathbf L_1$), and use some models (e.g. MLPs) to encode the statistics following certain rules (e.g. projection to the null space). However, we will improve writing add some paragraphs describing implementation details in the revision.\n\n5. RWMP: We do not mention RWMP in the main text due to limited space. However, this can be naturally integrated into any (weighted) random walk, as RWMP introduces a distance metric based on features. Therefore, it has close connections with the rest of our papers under the framework of random walk. The idea is also novel and explores a way to design more flexible GNN architectures. We will reorganize the paper in the final version and briefly mention it in main text.\n\nQuestions\n\n1. The computation depends on number of edges. Theoretically, the complexity for generating Hodge1Lap and EdgeRWSE are both $O(m^2)$, where $m$ is the number of edges. For common graphs, they basically share the same compute time and memories with node-level ones like RWSE. For example, the average generation time on Zinc computed by RTX3090 are: RWSE ($23$s), EdgeRWSE ($32$s), Hodge1Lap ($28$s). The number of parameters depends on detailed architectures, e.g. a linear layer or a 3-layer MLP as used in most of our experiments. Generally speaking, our method is extremely parameter-efficient but largely increase the performance.\n\n2. We generally follow GPS. GINE and GatedGCN are message-passing based GNN, while GPS integrates graph transformers. We show that our method can benefit both these types of graph machine learning models. GPS[4] also report that these architectures can be improved by PE/SE. Moreover, in our new experiments we apply our methods to over eight base models, verifying the universality of our methods.\n\n[4] Recipe for a general, powerful, scalable graph transformer."}]

Author rebuttal:
We sincerely thank all reviewers for their insightful and valuable review points. We add extensive experiments and report the results in the **pdf** attached to this common response. We answer some common questions in this response. Due to limited space, some experimental results and answers to the reviewers' questions are in individual replies.

**More backbone models**

In our new experiments (see **Table 1**), we apply our methods to: (a) GAT [1]; (b) PNA [2]; (c) SSWL+ [3]; (d) GPS [4]; (e) GRIT [5], where GAT and PNA are local (message-passing based) models, SSWL+ is a subgraph GNN, and the latter two are recent state-of-the-art graph transformers. We report the results over 5 different seeds for every setting. For both GAT and PNA that are relatively weak models, our Hodge1Lap and EdgeRWSE both decrease test MAE by around $50\%-70\%$. For the stronger backbone models SSWL+, GPS and GRIT, integrating Hodge1Lap and EdgeRWSE still improve their performances, resulting in highly competitive and even **new SOTA** results. For example, GRIT with Hodge1Lap achieves a **record-breaking** 0.057 MAE on Zinc-12k. All these results make it convincing that our Hodge1Lap and EdgeRWSE are capable of improving an extremely wide range of GNN models.

**Synthetic datasets**

To verify the theoretical expressive power of Hodge1Lap and EdgeRWSE, we conduct experiments on two synthetic datasets: EXP and SR25. EXP contains 600 pairs of non-isomorphic graphs that 1-WL and 2-WL fail to distinguish. SR25 contains 15 non-isomorphic strongly regular graphs (i.e., 105 non-isomorphic pairs) that 3-WL fails to distinguish. An accuracy of $50\%$ on EXP and $6.67\%$ on SR25 suggest the model fails to distinguish any non-isomorphic graphs in the dataset. From **Table 3** of the attached pdf, the $1$-WL equivalent GINE backend model can fully distinguish EXP and SR25 when augmented by Hodge1Lap and Full-EdgeRWSE, indicating that both methods can distinguish non-isomorphic graph pairs that $3$-WL (and $2$-FWL) fails, which is consistent with our theoretical analysis.

**Explanation on implementation details**
 - For SSWL+, we add edge PE/SE features embedded by a unique linear projection to the original edge features in every layer.
 - For GRIT, the PE is embedded by a linear layer and then directly added to the edge features. For virtual edges, the PE values are padded as zeros.
 - Our methods are applicable to higher-order GNNs, including simplicial networks and 2-$\delta$-FWL equivalent classes, while others (SPD, RD) cannot. Our methods are also more sparse.
 - Our methods can be applied to any base model without increasing much computation cost, and can be applied together with other types of PE/SE.

**Higher-order and inter-order implementation**

To make our theories for higher-order and inter-order random walk practical and more contributive, we implement Full-EdgeRWSE and $0-2$ inter-order random walk. Besides, we also generalize our random walk based theories to cellular complexes and implement Cellular-RWSE. We verify these new methods with the GINE backbone on the Zinc dataset. The results are presented in the **first block of Table 1** in the attached pdf. The implementation details are in our response to reviewer Djvd. The competitive results demonstrate the effectiveness of these new methods.

We make every effort during the rebuttal period to implement the new methods and supplement these new experimental results according to the reviewers' suggestions. We hope they can address your concerns and further strengthen our work.

[1] Graph attention networks.

[2] Principal neighbourhood aggregation for graph nets.

[3] A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests

[4] Recipe for a general, powerful, scalable graph transformer.

[5] Graph Inductive Biases in Transformers without Message Passing.

[6] Exphormer: Sparse Transformers for Graphs - Shirzad, Velingker, Venkatachalam, Sutherland, Sinop. ICML 2023.

Meta-review: This paper proposes random walks on different orders of simplicial complexes to enhance the expressive power of graph neural networks. The reviewers appreciated the novel idea, the nice presentation, and the theoretical analysis. Upon reading the paper myself, I also think the empirical results are quite strong for such a simple idea. I recommend acceptance for this work.
Decision: Accept (poster)