Revisiting Random Walks for Learning on Graphs

## Abstract

Abstract We revisit a simple idea for machine learning on graphs, where a random walk on a graph produces a machine-readable record, and this record is processed by a deep neural network to directly make vertex-level or graph-level predictions.
We refer to these stochastic machines as random walk neural networks , and show that we can design them to be isomorphism invariant while capable of universal approximation of graph functions in probability.
A useful finding is that almost any kind of record of random walk guarantees probabilistic invariance as long as the vertices are anonymized.
This enables us to record random walks in plain text and adopt a language model to read these text records to solve graph tasks.
We further establish a parallelism to message passing neural networks using tools from Markov chain theory, and show that over-smoothing in message passing is alleviated by construction in random walk neural networks, while over-squashing manifests as probabilistic under-reaching.
We show that random walk neural networks based on pre-trained language models can solve several hard problems on graphs, such as separating strongly regular graphs where the 3-WL test fails, counting substructures, and transductive classification on arXiv citation network without training.
Code is available at https://github.com/jw9730/random-walk .

## 1 Introduction

The most widely used class of neural networks on graphs are message passing neural networks where each vertex keeps a feature vector and updates it by propagating and aggregating messages over neighbors [, , ].
These networks benefit in efficiency by respecting the natural symmetries of graph functions, namely invariance to graph isomorphism [].
On the other hand, message passing can be viewed as implementing color refinement iterations of the one-dimensional Weisfeiler-Lehman (1-WL) graph isomorphism test, and consequently their expressive power is not stronger [, ].
Also, the inner working of these networks is tied to the topology of the input graph, which is related to over-smoothing, over-squashing, and under-reaching of features under mixing [, , ].

In this work, we (re)visit a simple alternative idea for learning on graphs, where a random walk on a graph produces a machine-readable record, and this record is processed by a deep neural network that directly makes vertex-level or graph-level predictions.
We call these stochastic machines random walk neural networks.
Using random walks for graph learning has received practical interest due to their scalability and compatibility with sequence learning methods.
This has led to empirically successful algorithms such as DeepWalk [] and node2vec [] which use skip-gram models on random walks and CRaWl [] which uses convolutions on random walks.
However, principled understanding and design of random walk neural networks have been studied relatively less.

We study the fundamental properties of random walk neural networks, and show that they can be designed from principle to be isomorphism invariant while capable of universal approximation of graph functions in probability.
Specifically, we find that (1) almost any kind of record of random walks guarantees invariance as long as the vertices are anonymized, and there is no constraint on the choice of the neural network that processes the records, and (2) universal approximation is achieved if the neural network that reads the records is powerful enough, and the random walk covers the whole graph of interest with a high probability.
The findings motivate us to record random walks in plain text and adopt a pre-trained transformer language model to read these records to solve graph tasks.
They also give us principled guidance on how to design the random walk algorithm to minimize or bound the cover times, such as using restarts when working on a large and possibly infinite graph.

We further analyze random walk neural networks using tools from Markov chain theory and establish a parallelism to a simple model of message passing neural networks.
From this, we show that over-smoothing phenomenon in message passing is inherently avoided in random walk neural networks, while over-squashing manifests as probabilistic under-reaching.
This eliminates the typical trade-off between over-smoothing and over-squashing in message passing and allows our method to focus on overcoming under-reaching using rapidly mixing random walks such as non-backtracking walks.

We test random walk neural networks based on pre-trained language models on several hard problems on graphs.
Our model based on DeBERTa [] learns and performs separation of strongly regular graphs with perfect accuracy whereas the 3-WL test fails, and it also successfully learns challenging tasks of counting 8-cycles at graph-level and vertex-level.
We further show that our approach can turn transductive classification problem on a large graph into an in-context learning problem by recording labeled vertices during random walks.
To demonstrate this, we apply frozen Llama 3 [] directly on transductive classification on arXiv citation network with 170k vertices, and show that it outperforms message passing networks as well as zero- and few-shot baselines even without training.
This verifies that our approach allows a pure language model to understand and leverage graph structures.

## 2 Random Walk Neural Networks

Figure: Figure 1: A random walk neural network that reads text record using a language model.
Refer to caption: x1.png

We define a random walk neural network as a randomized function $X_{\theta}(\cdot)$ that takes a graph $G$ as input and outputs a random variable $X_{\theta}(G)$ on the output space $\mathbb{R}^{d}$.(^1^11While any output type such as text is possible (Figure 1), we explain with vector output for simplicity.)
It can be optionally queried with an input vertex $v$ which gives a random variable $X_{\theta}(G,v)$.
It consists of the following:

- 1.
Random walk algorithm that produces $l$ steps of vertex transitions $v_{0}\to\cdots\to v_{l}$ on the input graph $G$. If an input vertex $v$ is given, we fix the starting vertex by $v_{0}=v$.
- 2.
Recording function $q:(v_{0}\to\cdots\to v_{l},G)\mapsto\mathbf{z}$ that produces a machine-readable record $\mathbf{z}$ of the random walk.
It may access the graph $G$ to record auxiliary information such as attributes.
- 3.
Reader neural network $f_{\theta}:\mathbf{z}\mapsto\hat{\mathbf{y}}$ that processes record $\mathbf{z}$ and outputs a prediction $\hat{\mathbf{y}}$ in $\mathbb{R}^{d}$.
It is the only trainable component and is not restricted to specific architectures.

To perform graph-level tasks, we sample a prediction $\hat{\mathbf{y}}\sim X_{\theta}(G)$ by running a random walk on $G$ and processing its record using the reader neural network.
For vertex-level predictions $\hat{\mathbf{y}}\sim X_{\theta}(G,v)$, we query the input vertex $v$ by simply starting the random walk from it.

In the sections below, we discuss the design of each component for graph-level tasks on finite graphs and then vertex-level tasks on possibly infinite graphs.
The latter simulates learning problems on large graphs, such as transductive classification, and forces the model to operate independently of the size of the whole graph $G$ [].
Pseudocode and proofs can be found in Appendix A.2 and A.4.

### 2.1 Graph-Level Tasks

Let $\mathbb{G}$ be the class of undirected, connected, and simple graphs(^2^22We assume this for simplicity but extending to directed or attributed graphs is possible.).
Let $n\geq 1$ and $\mathbb{G}_{n}$ be the collection of graphs in $\mathbb{G}$ with at most $n$ vertices.
We would like to model a graph-level function $\phi:\mathbb{G}_{n}\to\mathbb{R}^{d}$ using a random walk neural network $X_{\theta}(\cdot)$.

Since $\phi$ is a function on graphs, it is reasonable to assume that it is isomorphism invariant:

$$ $\displaystyle\phi(G)=\phi(H),\quad\forall G\simeq H.$ (1) $$

Incorporating the invariance structure to our model class would offer generalization benefit [, ].
Since $X_{\theta}(\cdot)$ is a randomized function, we accept the probabilistic notion of invariance [, , , ]:

$$ $\displaystyle X_{\theta}(G)\overset{d}{=}X_{\theta}(H),\quad\forall G\simeq H.$ (2) $$

We now claim that we can achieve probabilistic invariance by properly choosing the random walk algorithm and recording function while not imposing any constraint on the reader neural network.

###### Theorem 2.1 .

$X_{\theta}(\cdot)$ is invariant if its random walk algorithm and recording function are invariant.

Below, we describe the choice of random walk algorithm, recording function, and neural networks that comprise random walk neural networks as in Theorem 2.1.
Pseudocode is given in Appendix A.2.

###### Theorem 2.1 .

##### Random walk algorithm

A random walk algorithm is invariant if it satisfies the following:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{l})\overset{d}{=}u_{0}\to\cdots\to u _{l},\quad\forall G\overset{\pi}{\simeq}H,$ (3) $$

where $v_{[\cdot]}$ is a random walk on $G$, $u_{[\cdot]}$ is a random walk on $H$, and $\pi:V(G)\to V(H)$ specifies the isomorphism from $G$ to $H$.
It turns out that many random walk algorithms in literature are already invariant.
To see this, let us write the probability of walking from a vertex $u$ to its neighbor $x\in N(u)$:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x|v_{t-1}=u]\coloneq\frac{c_{G}(u,x)}{\sum_{y \in N(u)}c_{G}(u,y)},$ (4) $$

where the function $c_{G}:E(G)\to\mathbb{R}_{+}$ assigns positive weights called conductance to edges.
If we use constant conductance $c_{G}(\cdot)=1$, we have unbiased random walk used in DeepWalk [].
We show:

###### Theorem 2.2 .

The random walk in Equation (4) is invariant if its conductance $c_{[\cdot]}(\cdot)$ is invariant:

$$ $\displaystyle c_{G}(u,v)=c_{H}(\pi(u),\pi(v)),\quad\forall G\overset{\pi}{ \simeq}H.$ (5) $$

It includes constant conductance, and any choice that only uses degrees of endpoints $\mathrm{deg}(u)$, $\mathrm{deg}(v)$.

We favor using the degree information since it is cheap while potentially improving the behaviors of walks.
Among many instantiations, we find that the following conductance function called the minimum degree local rule [, ] is particularly useful:

$$ $\displaystyle c_{G}(u,v)\coloneq\frac{1}{\min[\mathrm{deg}(u),\mathrm{deg}(v)]}.$ (6) $$

This conductance is special because it achieves $O(n^{2})$ cover time, i.e. the expected time of visiting all $n$ vertices of a graph, optimal among random walks in Equation (4) that use degrees of endpoints [].

In practice, we find that adding non-backtracking property that enforces $v_{t+1}\neq v_{t-1}$ is helpful while not adding much cost.
Formally, we can extend Equation (4) and Theorem 2.2 to second-order random walks that include non-backtracking and node2vec walks [].
We leave this in Appendix A.1.

###### Theorem 2.2 .

##### Recording function

A recording function $q:(v_{0}\to\cdots\to v_{l},G)\mapsto\mathbf{z}$ takes a random walk and produces a machine-readable record $\mathbf{z}$.
We let $q(\cdot,G)$ have access to the graph $G$ the walk is taking place.
This allows recording auxiliary information such as vertex or edge attributes.
A recording function is invariant if it satisfies the following for any given random walk $v_{[\cdot]}$ on $G$:

$$ $\displaystyle q(v_{0}\to\cdots\to v_{l},G)=q(\pi(v_{0})\to\cdots\to\pi(v_{l}), H),\quad\forall G\overset{\pi}{\simeq}H.$ (7) $$

Invariance requires that $q(\cdot,G)$ produces the same record $\mathbf{z}$ regardless of re-indexing of vertices of $G$ into $H$.
For this, we have to be careful in how we represent each vertex in a walk $v_{0}\to\cdots\to v_{l}$ as a machine-readable value, and which auxiliary information we record from $G$.
We make two choices:

- •
Anonymization.
We name each vertex in a walk with a unique integer, starting from $v_{0}\mapsto 1$ and incrementing it based on their order of discovery.
For instance, a random walk $a\to b\to c\to a$ translates to a sequence $1\to 2\to 3\to 1$.
- •
Anonymization + named neighborhoods.
While applying anonymization for each vertex $v$ in a walk, we record its neighbors $u\in N(v)$ if they are already named but the edge $v\to u$ has not been recorded yet.
For instance, a walk $a\to b\to c\to d$ on a fully-connected graph translates to a sequence $1\to 2\to 3\langle 1\rangle\to 4\langle 1,2\rangle$, where $\langle\cdot\rangle$ represents the named neighborhoods.

The pseudocode of both algorithms can be found in Appendix A.2.
We now show the following:

###### Theorem 2.3 .

A recording function $q:(v_{0}\to\cdots\to v_{l},G)\mapsto\mathbf{z}$ that uses anonymization, optionally with named neighborhoods, is invariant.

Our choice of anonymizing a walk is inspired by the observation model of Micali and Zhu (2015) [].
While initially motivated by privacy concerns [, ], we find it useful for invariance.
Recording named neighborhoods is inspired by sublinear algorithms that probe previously discovered neighbors during a walk [, , ].
In our context, it is useful because whenever a walk visits a set of vertices $S\subseteq V(G)$ it automatically records the entire induced subgraph $G[S]$.
As a result, to record all edges of a graph, a walk only has to visit all vertices.
It is then possible to choose a random walk algorithm that takes only $O(n^{2})$ time to visit all $n$ vertices [, ], while traversing all edges, i.e. edge cover time, is $O(n^{3})$ in general [, ].
The degree-biasing in Equation (6) precisely achieves this.

###### Theorem 2.3 .

##### Reader neural network

A reader neural network $f_{\theta}:\mathbf{z}\mapsto\hat{\mathbf{y}}$ processes the record $\mathbf{z}$ of the random walk and outputs a prediction $\hat{\mathbf{y}}$ in $\mathbb{R}^{d}$.
As in Theorem 2.1, there is no invariance constraint imposed on $f_{\theta}$, and any neural network that accepts the recorded walks and has a sufficient expressive power can be used.
This is in contrast to message passing where invariance is hard-coded in feature mixing operations.
Furthermore, our record $\mathbf{z}$ can take any format, such as a matrix, byte sequence, or plain text, as long as $f_{\theta}$ accepts it.
It is appealing in this regard to choose the record to be plain text, such as "1-2-3-1", and choose $f_{\theta}$ to be a pre-trained transformer language model.
This offers expressive power [] as well as transferable representation from language domain [, ].
In our experiments, we test both "encoder-only" DeBERTa [] and "decoder-only" Llama [] language models as $f_{\theta}$.

### 2.2 Vertex-Level Tasks

We now consider vertex-level tasks.
In case of finite graphs, we may simply frame a vertex-level task $(G,v)\mapsto\mathbf{y}$ as a graph-level task $G^{\prime}\mapsto\mathbf{y}$ where $G^{\prime}$ is $G$ with its vertex $v$ marked.
Then, we can solve $G^{\prime}\mapsto\mathbf{y}$ by querying a random walk neural network $X_{\theta}(G,v)$ to start its walk at $v_{0}=v$.

A more interesting case is when $G$ is an infinite graph that is only locally finite, i.e., has finite degrees.
This simulates learning problems on a large graph such as transductive classification.
In this case, it is reasonable to assume that our target function depends on finite local structures [, ].

Let $r\geq 1$, and $\mathbb{B}_{r}\coloneq\{B_{r}(v)\}$ be the collection of local balls in $G$ of radius $r$ centered at $v\in V(G)$.
We would like to model a vertex-level function $\phi:\mathbb{B}_{r}\to\mathbb{R}^{d}$ on $G$ using a random walk neural network $X_{\theta}(\cdot)$ by querying the vertex of interest, $X_{\theta}(G,v)$.
We assume $\phi$ is isomorphism invariant:

$$ $\displaystyle\phi(B_{r}(v))=\phi(B_{r}(u)),\quad\forall B_{r}(v)\simeq B_{r}(u).$ (8) $$

The invariance of $X_{\theta}(\cdot)$ in probability is defined as following:

$$ $\displaystyle X_{\theta}(G,v)\overset{d}{=}X_{\theta}(G,u),\quad\forall B_{r}( v)\simeq B_{r}(u).$ (9) $$

We may achieve invariance by choosing the random walk algorithm and recording function similar to the graph-level case(^3^33This is assuming that the random walks are localized in $B_{r}(v)$ and $B_{r}(u)$, e.g. with restarts.).
As a modification, we query $X_{\theta}(G,v)$ with the starting vertex $v_{0}=v$ of the random walk.
Anonymization informs $v$ to the reader neural network by always naming it as $1$.

Then, we make an important choice of localizing random walks with restarts.
That is, we reset a walk to the starting vertex $v_{0}$ either with a probability $\alpha\in(0,1)$ at each step or periodically every $k$ steps.
A restarting random walk tends to stay more around its starting vertex $v_{0}$, and was used to implement locality bias in personalized PageRank algorithm for search [, ].
This localizing effect is crucial in our context since a walk may drift away from $B_{r}(v_{0})$ before recording all necessary information, which will then take an infinite time to return since $G$ is infinite [, , , ].
Restarts make the return to $v_{0}$ mandatory, ensuring that $B_{r}(v_{0})$ can be recorded within a finite expected time.
We show:

###### Theorem 2.4 .

For a uniform random walk on an infinite graph $G$ starting at $v$, the cover time and edge cover time of the finite local ball $B_{r}(v)$ are not always finitely bounded.

###### Theorem 2.5 .

In Theorem 2.4, if the random walk restarts at $v$ with any nonzero probability $\alpha$ or any period $k\geq r+1$, the cover time and edge cover time of $B_{r}(v)$ are always finite.

###### Theorem 2.4 .

###### Theorem 2.5 .

## 3 Analysis

In Section 2, we have described the design of random walk neural networks, primarily relying on the principle of invariance.
In this section we provide in-depth analysis on their expressive power and relations to issues in message passing such as over-smoothing, over-squashing, and under-reaching.

### 3.1 Expressive Power

Intuitively, if the records of random walks contain enough information such that the structures of interest, e.g. graph $G$ or local ball $B_{r}(v)$, can be fully recovered, a powerful reader neural network such as a multi-layer perceptron [, ] or a transformer [] on these records would be able to approximate any function of interest.
Our following analysis shows this.

We first consider using random walk neural network $X_{\theta}(\cdot)$ to universally approximate graph-level functions $\phi(\cdot)$ in probability, as defined in Abboud et al. (2021) [].
While we consider scalar-valued functions as often done in universality proofs, extension to vector-valued functions can be done easily.

###### Definition 3.1 .

$X_{\theta}(\cdot)$ is a universal approximator of graph-level functions in probability if, for all invariant functions $\phi:\mathbb{G}_{n}\to\mathbb{R}$ for a given $n\geq 1$, and $\forall\epsilon,\delta>0$, there exist choices of length $l$ of the random walk and network parameters $\theta$ such that the following holds:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-X_{\theta}(G)|<\epsilon]>1-\delta,\quad \forall G\in\mathbb{G}_{n}.$ (10) $$

We show that, if the random walk is long enough and the reader neural network $f_{\theta}$ is powerful enough, a random walk neural network $X_{\theta}(\cdot)$ is capable of graph-level universal approximation in probability.
In particular, we show that the length of the random walk $l$ controls the confidence $1-\delta$ of the approximation, with cover time $C_{V}(G)$ or edge cover time $C_{E}(G)$ playing a central role.

###### Theorem 3.2 .

A random walk neural network $X_{\theta}(\cdot)$ with a sufficiently powerful $f_{\theta}$ is a universal approximator of graph-level functions in probability (Definition 3.1) if it satisfies either of the below:

- •
It uses anonymization to record random walks of lengths $l>C_{E}(G)/\delta$.
- •
It uses anonymization and named neighborhoods to record walks of lengths $l>C_{V}(G)/\delta$.

We remark that, while the cover time and edge cover time are $O(n^{3})$ for uniform random walks [, , , , , , , ], we make use of minimum degree local rule in Equation (6) to achieve a cover time of $O(n^{2})$ [, ], in conjunction with named neighborhood recording.
While universal approximation can be in principle achieved with simple uniform random walk, our design reduces the length $l$ required for the desired reliability $>1-\delta$, and hence improves learning and inference.

We now show an analogous result for universal approximation of vertex-level functions.
Since our target function $\phi$ is on a collection $\mathbb{B}_{r}$ of finite graphs, the proof is similar to the graph-level case.

###### Definition 3.3 .

$X_{\theta}(\cdot)$ is a universal approximator of vertex-level functions in probability if, for all invariant functions $\phi:\mathbb{B}_{r}\to\mathbb{R}$ for a given $r\geq 1$, and $\forall\epsilon,\delta>0$, there exist choices of length $l$ and restart probability $\alpha$ or period $k$ of the random walk and network parameters $\theta$ such that:

$$ $\displaystyle\mathrm{Prob}[|\phi(B_{r}(v))-X_{\theta}(G,v)|<\epsilon]>1-\delta ,\quad\forall B_{r}(v)\in\mathbb{B}_{r}.$ (11) $$

We show the following, which relates to local cover time $C_{V}(B_{r}(v))$ and edge cover time $C_{E}(B_{r}(v))$:

###### Theorem 3.4 .

A random walk neural network $X_{\theta}(\cdot)$ with a sufficiently powerful $f_{\theta}$ and any nonzero restart probability $\alpha$ or restart period $k\geq r+1$ is a universal approximator of vertex-level functions in probability (Definition 3.3) if it satisfies either of the below for all $B_{r}(v)\in\mathbb{B}_{r}$:

- •
It uses anonymization to record random walks of lengths $l>C_{E}(B_{r}(v))/\delta$.
- •
It uses anonymization and named neighborhoods to record walks of lengths $l>C_{V}(B_{r}(v))/\delta$.

We remark that restarts are necessary to finitely bound the local cover times of a random walk on an infinite graph.
From this fact and Theorem 3.4 we can see that non-restarting walks of finite length cannot provide vertex-level universal approximation in probability, and our design is obligatory.

###### Definition 3.1 .

###### Theorem 3.2 .

###### Definition 3.3 .

###### Theorem 3.4 .

### 3.2 Over-smoothing, Over-squashing, and Under-reaching

In message passing neural networks, the model operates by passing features over edges and mixing them, and thus their operation is tied to the topology of the input graph.
It is now understood how this relates to the issues of over-smoothing, over-squashing, and under-reaching [, , , , , ].
We connect these theories and random walk neural networks to verify if similar issues may take place.

Let $G$ be a connected non-bipartite graph with row-normalized adjacency matrix $P$.
We consider a simplified message passing model, where the vertex features $\mathbf{h}^{(0)}$ are initialized as some probability vector $\mathbf{x}$, and updated by $\mathbf{h}^{(t+1)}=\mathbf{h}^{(t)}P$.
This simple model is often used as a proxy to study the aforementioned issues [, ].
For example, over-smoothing happens as the features exponentially converge to a stationary vector $\mathbf{h}^{(l)}\to\boldsymbol{\pi}$ as $l\to\infty$, smoothing out the input $\mathbf{x}$ [].
Over-squashing and under-reaching occur when a feature $\mathbf{h}_{u}^{(l)}$ becomes insensitive to distant input $\mathbf{x}_{v}$.
While under-reaching refers to insufficient depth $l<\mathrm{diam}(G)$ [, ], over-squashing refers to features getting overly compressed at bottlenecks of $G$, even with sufficient depth $l$.
The latter is described by the Jacobian $|\partial\mathbf{h}_{u}^{(l)}/\partial\mathbf{x}_{v}|\leq[\sum_{t=0}^{l}P^{t}]
_{uv}$,(^4^44This bound is obtained by applying Lemma 3.2 of Black et al. (2023) [] to our simplified message passing.), as the bound often decays exponentially with $l$ [, ].

What do these results tell us about random walk neural networks?
We can see that, while $P$ drives feature mixing in the message passing schema, it can be also interpreted as the transition probability matrix of uniform random walk where $P_{uv}$ is the probability of walking from $u$ to $v$.
This parallelism motivates us to design an analogous, simplified random walk neural network and study its behavior.

We consider a simple random walk neural network that runs a uniform random walk $v_{0}\to\cdots\to v_{l}$, reads the record $\mathbf{x}_{v_{0}}\to\cdots\to\mathbf{x}_{v_{l}}$ by averaging, and outputs it as $\mathbf{h}^{(l)}$.
Like simple message passing, the model involves $l$ steps of time evolution through $P$.
However, while message passing uses $P$ to process features, this model uses $P$ only to obtain a record of input, with feature processing decoupled.
We show that in this model, over-smoothing does not occur as in simple message passing(^5^55While we show not forgetting $\mathbf{x}$ for brevity, we may extend to initial vertex $v_{0}$ using its anonymization as $1$.):

###### Theorem 3.5 .

The simple random walk neural network outputs $\mathbf{h}^{(l)}\to\mathbf{x}^{\top}\boldsymbol{\pi}$ as $l\to\infty$.

Even if the time evolution through $P$ happens fast (i.e. $P$ is rapidly mixing) or with many steps $l$, the model is resistant to over-smoothing as the input $\mathbf{x}$ always affects the output.
In fact, if $P$ is rapidly mixing, we may expect improved behaviors based on Section 3.1 as the cover times could reduce.

On the other hand, we show that over-squashing manifests as probabilistic under-reaching:

###### Theorem 3.6 .

Let $\mathbf{h}_{u}^{(l)}$ be output of the simple random walk neural network queried with $u$.
Then:

$$ $\displaystyle\mathbb{E}\left[\left|\frac{\partial\mathbf{h}_{u}^{(l)}}{ \partial\mathbf{x}_{v}}\right|\right]=\frac{1}{l+1}\left[\sum_{t=0}^{l}P^{t} \right]_{uv}\to\boldsymbol{\pi}_{v}\quad\text{as}\quad l\to\infty.$ (12) $$

The equation shows that the feature Jacobians are bounded by the sum of powers of $P$, same as in simple message passing.
Both models are subject to over-squashing phenomenon that is similarly formalized, but manifests through different mechanisms.
While in message passing the term is related to over-compression of features at bottlenecks [], in random walk neural networks it is related to exponentially decaying probability of reaching a distant vertex $v$, i.e., probabilistic under-reaching.

In message passing, it is understood that the topology of the input graph inevitably induces a trade-off between over-smoothing and over-squashing [, ].
Our results suggest that random walk neural networks avoid the trade-off, and we can focus on overcoming under-reaching e.g. by accelerating the walk, while not worrying much about over-smoothing.
Our design choices such as degree-biasing (Equation (6)) and non-backtracking [] can be understood as achieving this.

###### Theorem 3.5 .

###### Theorem 3.6 .

## 4 Related Work

##### Random walks on graphs

Our work builds upon theory of random walks on graphs, i.e. Markov chains on discrete spaces.
Their statistical properties such as hitting and mixing times have been well-studied [, , , , , ], and our method (Section 2) is related to cover time [, , , ], edge cover time [, , , ], and improving them, using local degree information [, , ], non-backtracking [, , , ], or restarts in case of infinite graphs [, , ].
Random walks and their statistical properties are closely related to structural properties of graphs, such as effective resistance [, ], Laplacian eigen-spectrum [, ], and discrete Ricci curvatures [, ].
This has motivated our analysis in Section 3.2, where we transfer the prior results on over-smoothing and over-squashing of message passing based on these properties [, , , , , , ] into the results on our approach.
Our work is also inspired by graph algorithms based on random walks, such as anonymous observation [], sublinear algorithms [, , ], and personalized PageRank for search [].
While we adopt their techniques to make our walks and their records well-behaved, the difference is that we use a deep neural network to process the records and directly make predictions.

##### Random walks and graph learning

In graph learning, random walks have received interest due to their scalability and compatibility to sequence learning methods.
DeepWalk [] and node2vec [] use shallow skip-gram models on random walks to learn vertex embeddings.
While CRaWl [] is the most relevant to our work, it uses convolutions on walks recorded in a different way from ours.
Hence, its expressive power is controlled by the kernel size and does not always support universality.
AgentNet [] learns agents that walk on a graph while recurrently updating their features.
While optimizing the walk strategy, this method may trade off efficiency as training requires recurrent roll-out of the entire network.
Our method allows pairing simple and fast walkers with parallelizable networks such as transformers, which suffices for universality.
WalkLM [] proposed a fine-tuning method for language models on random walks on text-attributed graphs.
While in a similar spirit, our result provides more principles as well as extending to purely topological graphs and training-free setups.
Our method is also related to label propagation algorithms [, , ] that perform transductive learning on graphs based on random walks, which we further discuss in Section 5.3.

##### Probabilistic invariant neural networks

Whenever a learning problem is compatible with symmetry, incorporating the associated invariance structure to the hypothesis class often leads to generalization benefit [, , ].
This is also the case for probabilistic invariant neural networks [, ], which includes our approach.
Probabilistic invariant networks have recently gained interest due to their potential of achieving higher expressive powers compared to deterministic counterparts [, ].
In graph learning, this is often achieved with stochastic symmetry breaking between vertices using randomized features [, , , ], vertex orderings [, ], or dropout [].
Our approach can be understood as using random walk as a symmetry-breaking mechanism for probabilistic invariance, which provides an additional benefit of natural compatibility with sequence learning methods.

##### Language models on graphs

While not based on random walks, there have been prior attempts on applying language models for problems on graphs [, , , , ], often focusing on prompting methods on problems involving simulations of graph algorithms.
We take a more principle-oriented approach based on invariance and expressive power, and thus demonstrate our approach mainly on the related tasks, e.g. graph separation.
We believe extending our work to simulating graph algorithms requires a careful treatment [, , , ] and plan to investigate it as future work.

## 5 Experiments

We perform a series of experiments to demonstrate random walk neural networks.
We implement random walk algorithms in C++ based on Chenebaux (2020) [], which produces good throughput even without GPU acceleration [].
Likewise, we implement recording functions in C++ which perform anonymization with named neighborhoods and produce plain text.
Pseudocode of our implementation is given in Appendix A.2.
We choose reader neural networks as pre-trained language models, with a prioritization on long inputs in accordance to Section 3.1.
For fine-tuning experiments, we use DeBERTa-base [] that supports up to 12,276 tokens, and for training-free experiments, we use instruction-tuned Llama 3 [] that support up to 8,192 tokens.
We implement our pipelines in PyTorch [] with libraries [, , , ] that support multi-GPU training and inference.

### 5.1 Graph Separation

**Table 1: Graph separation results. We report accuracy of classifying training data rounded to the first decimal point. *, ${\dagger}$, ${\ddagger}$, $\mathsection$, and ^⋄ are from [], [], [], [], and [], respectively. We trained AgentNet and CRaWl on SR25 with their reported best configurations on SR16 and CSL, respectively.**
|  |  |  |  |
| --- | --- | --- | --- |
|  | CSL | SR16 | SR25 |
| Method | 1, 2-WL fails | 3-WL fails | 3-WL fails |
|  |  |  |  |
| GIN [] | 10.0%${\dagger}$ | 50.0%$\mathsection$ | 6.7%${\ddagger}$ |
| PPGN [] | 100.0%$\mathsection$ | 50.0%$\mathsection$ | 6.7%${\ddagger}$ |
|  |  |  |  |
| GIN-AK+ [] | - | - | 6.7%${\ddagger}$ |
| PPGN-AK+ [] | - | - | 100.0%${\ddagger}$ |
| GIN+ELENE [] | - | - | 6.7%^⋄ |
| GIN+ELENE-L (ED) [] | - | - | 100.0%^⋄ |
|  |  |  |  |
| GIN-RNI [, ] | 16.0%* | - | - |
| GIN-RP [] | 37.6%${\dagger}$ | - | - |
| GIN-Dropout [] | 82.0%* | - | - |
|  |  |  |  |
| Random Walk AgentNet [] | 100.0%$\mathsection$ | 50.5%$\mathsection$ | - |
| AgentNet [] | 100.0%$\mathsection$ | 100.0%$\mathsection$ | 6.7% |
| CRaWl [] | 100.0%$\mathsection$ | 100.0%$\mathsection$ | 46.6% |
| DeBERTa-walk (Ours) | 100.0% | 100.0% | 100.0% |
|  |  |  |  |

We first verify the claims on expressive power in Section 3.1 using three synthetic datasets where the task is recognizing the isomorphism type of an input graph.
This is framed as fitting an $N$-way classification problem on $N$ non-isomorphic graphs.
The graphs are chosen such that a certain WL graph isomorphism test fails, and so does their related family of message passing neural networks.

The Circular Skip Links (CSL) graphs dataset [] contains 10 non-isomorphic regular graphs with 41 vertices of degree 4.
Distinguishing these graphs requires computing lengths of skip links [, ], and 1-WL and 2-WL tests fail.
The $4\times 4$ rook’s and Shrikhande graphs [], which we call SR16, are a pair of strongly regular graphs with 16 vertices of degree 6.
Distinguishing the pair requires detecting 4-cliques [], and 3-WL test fails [].
The SR25 dataset [] contains 15 strongly regular graphs with 25 vertices of degree 12, on which 3-WL test fails [].
SR25 is challenging and has only been solved by a handful of carefully designed subgraph-based message passing algorithms [, , ].
Examples of the considered graphs and random walks on them can be found in Appendix A.2.

Our random walk neural network uses the minimum degree local rule from Equation (6) with non-backtracking (Algorithm 1), and recording function with anonymization and named neighborhoods that produces plain text (Algorithm 3).
We use pre-trained DeBERTa-base language model as the reader neural network, and fine-tune it with cross-entropy loss for at most 100k steps using AdamW optimizer [] with 2e-5 learning rate and 0.01 weight decay on on 8$\times$ RTX 3090 GPUs.
While the model supports 12,276 tokens in maximum, we use 512 tokens which is the maximum allowed by memory constraint.
We use batch size 256, and accumulate gradients for 8 steps for SR25.
At test time, we ensemble 4 stochastic predictions of the network by averaging classification logits.

The results are in Table LABEL:table:graph_separation.
Message passing neural networks that align with certain WL test fail when asked to solve harder problems, e.g. GIN aligns with 1-WL and fails in CSL.
Recent algorithms that use subgraphs and structural features show improved performance, with state-of-the-art such as ELENE-L (ED) solving SR25.
Alternative approaches based on stochastic symmetry-breaking e.g. random node identification, often fail on CSL although universal approximation is possible in theory [], possibly due to learning difficulties.
For algorithms based on walks, AgentNet and CRaWl solve CSL and SR16, while failing on SR25.
This is because learning a policy to walk in AgentNet can be challenging in complex tasks especially at the early stage of training, and the expressiveness of CRaWl is limited by the receptive field of convolution layers.
Our approach based on DeBERTa language model overcomes the problems, being the first walk-based algorithm that solves SR25.

In Appendix A.3, we further provide visualizations of learned attentions by mapping attention weights on text records of walks to input graphs.
We find that the models often focus on sparse, connected substructures, which presumably provide discriminative information on the isomorphism types.

### 5.2 Substructure Counting

**Table 2: Substructure (8-cycle) counting results. We report normalized mean absolute error (MAE) on test set at best validation. We trained MP, Subgraph GNN, Local 2-GNN, and Local 2-FGNN using configurations in [], and trained MP-RNI, MP-Dropout, AgentNet, and CRaWl as in Table LABEL:table:graph_separation.**
|  |  |  |
| --- | --- | --- |
| Method | Graph-level | Vertex-level |
|  |  |  |
| MP [] | .0917 | .1156 |
| Subgraph GNN [] | .0515 | .0715 |
| Local 2-GNN [] | .0433 | .0478 |
| Local 2-FGNN [] | .0422 | .0438 |
| Local 2-FGNN (large) | .0932 | .1121 |
|  |  |  |
| MP-RNI [, ] | .3610 | .3650 |
| MP-Dropout [] | .1359 | .1393 |
|  |  |  |
| AgentNet [] | .1107 | N/A |
| CRaWl [] | .0526 | .0725 |
| DeBERTa-walk (Ours) | .0459 | .0465 |
|  |  |  |

We test our model on more challenging tasks that require both expressive power and generalization to unseen graphs.
We use a synthetic dataset of 5,000 random regular graphs from Chen et al. (2020) [], and consider the task of counting substructures.
We choose 8-cycles since they are known to require a particularly high expressive power [].
We experiment with both graph-level and vertex-level counting i.e. counting 8-cycles containing the queried vertex, following Zhang et al. (2024) [].
We use the data splits from the previous works [, , ], while excluding disconnected graphs following our modeling assumption in Section 2.1.
Our random walk neural network uses the same design to Section 5.1, and we train them with L1 loss for at most 250k steps using batch size of 128 graphs for graph-level counting and 8 graphs for vertex-level.
At test-time, we ensemble 64 and 32 stochastic predictions by averaging for graph- and vertex-level tasks, respectively.

The results are in Table LABEL:table:counting, and overall in line with Section 5.1.
While simple message passing shows a low performance, variants with higher expressive powers such as local 2-GNN and local 2-FGNN achieve high performances.
This is consistent with the observation of [].
On the other hand, message passing with stochastic symmetry-breaking often show learning difficulties and does not achieve good performance.
AgentNet was not directly applicable for vertex-level counting since its vertex encoding depends on which vertices the agent visits, and a learning difficulty was observed for graph-level counting.
Our approach based on DeBERTa demonstrates competitive performance, outperforming random walk baselines and approaching performances of local 2-GNN and 2-FGNN.

### 5.3 In-Context Transductive Classification

**Table 3: Transductive classification test accuracy on ogbn-arxiv. ${\dagger}$ denotes using validation labels for in-context learning or label propagation, as done in []. For Llama 3, we use instruction-tuned models, and ensemble 5 predictions by voting for both one-shot learning and our algorithm.**
|  |  |
| --- | --- |
| Method | Accuracy |
|  |  |
| MLP [] | 55.50% |
| node2vec [] | 70.07% |
| GCN [] | 71.74% |
| GAT [] | 73.91% |
| RevGAT [] | 74.26% |
| Label propagation [] | 68.50% |
| C&S [] | 72.62% |
| C&S${\dagger}$ [] | 74.02% |
| Llama2-13b zero-shot [] | 44.23% |
| GPT-3.5 zero-shot [] | 73.50% |
| DeBERTa, fine-tuned [] | 74.13% |
| Llama3-8b zero-shot | 50.20% |
| Llama3-8b one-shot | 52.49% |
| Llama3-8b one-shot${\dagger}$ | 52.54% |
| Llama3-8b-walk (Ours) | 71.10% |
| Llama3-8b-walk (Ours)${\dagger}$ | 73.11% |
| Llama3-70b zero-shot | 65.33% |
| Llama3-70b one-shot${\dagger}$ | 67.57% |
| Llama3-70b-walk (Ours)${\dagger}$ | 74.75% |
|  |  |

Previous results considered synthetic tasks on undirected, unattributed, and relatively small graphs.
We now show that our approach based on frozen Llama 3 [] language models can solve real-world problem on a large graph with directed edges and textual attributes, without any training.
We use ogbn-arxiv [], a citation network of 169,343 arXiv papers with title and abstract attributes.
The task is transductive classification into 40 areas such as "cs.AI" using a subset of labeled vertices.

We consider two representative types of baselines.
The first reads title and abstract of each vertex using a language model and solves vertex-wise classification problem, ignoring graph structure.
The second initializes vertex features as language model embeddings and trains a graph neural network, at the risk of over-compressing the text.
Our algorithm allows taking the best of both worlds.
We design the recording function so that, not only it does basic operations such as anonymization, it records a complete information of the local subgraph including title and abstract, edge directions, and notably, labels in case of labeled vertices (Appendix A.2) [].
The resulting record naturally includes a number of input-label pairs of the classification task at hand, implying that we can frame transductive classification problem as a simple in-context learning problem [].
This allows us to use a frozen Llama 3 [] language model directly on transductive classification without any training.

The results are in Table LABEL:table:arxiv.
Notably, our model based on frozen Llama 3 is able to outperform graph neural networks on text embeddings, as well as language models that perform vertex-wise predictions ignoring graph structures such as GPT-3.5 and fine-tuned DeBERTa.
We especially note that our model largely outperforms one-shot baselines, which are given 40 randomly chosen labeled examples (one per class).
This is surprising as our model observes fewer vertices, 29.17 in average, due to other recorded information.
This is presumably since the record produced by our algorithm faithfully encodes graph structure, providing more useful input for the language model to quickly learn the task in-context compared to randomly chosen shots.
Overall, the results show that our approach allows a pure language model to understand and leverage graph structures even without training.
In Appendix A.3, we provide a visualization of the internal attention weights, verifying that the model makes use of the graph structure recorded by the random walk to make predictions.

As a final note, our approach is related to label propagation algorithms [, , ] for transductive classification, which makes predictions by running random walks and probing the distribution of visited labeled vertices.
The difference is that, in our approach, the reader neural network i.e. language model can appropriately use other information such as attributes, as well as do meaningful non-linear processing rather than simply probing the input.
As shown in Table LABEL:table:arxiv, our approach outperforms label propagation, verifying our intuition.
This result also supports the proposal of Sato (2024) [] of using labels as features for training-free neural networks for transductive classification on graphs.

## 6 Conclusion

We presented random walk neural networks, stochastic machines that process a graph as a machine-readable record of random walk.
By choosing a proper random walk algorithm and recording function, the proposed method can achieve isomorphism invariance and universal approximation of graph functions in probability using unconstrained neural networks.
Equipped with a powerful language model, the proposed method demonstrated promising results on a number of hard graph learning problems and even in-context learning capability on large-scale transductive classification tasks.

##### Limitations and future work

Our current main limitation is the cost of performing training and inference with language models, especially on long walks.
We believe efficient fine-tuning with e.g. low-rank adaptation [, ] may help overcome the issue.
A question for future work is whether we can train a language model on a large pseudocorpus of random walks [, ] to build a foundation model for graphs which is language-compatible.
We plan to investigate this direction in the future.

##### Acknowledgements

This work was supported in part by the National Research Foundation of Korea (RS-2024-00351212) and the IITP grant (2022-0-00926 and RS-2022-II220959) funded by the Korean government (MSIT).

## Appendix A Appendix

### A.1 Second-Order Random Walks (Section 2.1 )

In second-order random walks, the probability of choosing $v_{t+1}$ depends not only on $v_{t}$ but also on $v_{t-1}$.
We consider non-backtracking [, ] and node2vec [] random walks as representatives.

A non-backtracking random walk is defined upon a first-order random walk algorithm, e.g. one in Equation (4), by enforcing $v_{t+1}\neq v_{t-1}$:

$$ $\displaystyle\mathrm{Prob}[v_{t+1}=x|v_{t}=j,v_{t-1}=i]\coloneq\begin{dcases*} \frac{\mathrm{Prob}[v_{t+1}=x|v_{t}=j]}{\sum_{y\in N(j)\setminus\{i\}}\mathrm{ Prob}[v_{t+1}=y|v_{t}=j]}&for $x\neq i$,\\ 0\vphantom{\frac{0}{0}}&for $x=i$,\end{dcases*}$ (13) $$

where $\mathrm{Prob}[v_{t+1}=x|v_{t}=j]$ is the probability of walking $j\to x$ given by the underlying first-order random walk.
Notice that the probabilities are renormalized over $N(j)\setminus\{i\}$.
This is ill-defined in the case the walk traverses $i\to j$ and reaches a dangling vertex $j$ which has $i$ as its only neighbor, since $N(j)\setminus\{i\}=\emptyset$.
In such cases, we allow the random walk to "begrudgingly" backtrack [], $i\to j$ and then $j\to i$, given that it is the only possible choice due to the dangling of $j$.

In case of node2vec random walk [], a weighting term $\alpha(v_{t-1},v_{t+1})$ with two (hyper)parameters, return $p$ and in-out $q$, is introduced to modify the behavior of a first-order random walk:

$$ $\displaystyle\mathrm{Prob}[v_{t+1}=x|v_{t}=j,v_{t-1}=i]\coloneq\frac{\alpha(i, x)\,\mathrm{Prob}[v_{t+1}=x|v_{t}=j]}{\sum_{y\in N(j)}\alpha(i,y)\,\mathrm{ Prob}[v_{t+1}=y|v_{t}=j]},$ (14) $$

where the probability $\mathrm{Prob}[v_{t+1}=x|v_{t}=j]$ is given by the underlying first-order random walk and $\alpha(v_{t-1},v_{t+1})$ is defined as follows using the shortest path distance $d(v_{t-1},v_{t+1})$:

$$ $\displaystyle\alpha(v_{t-1},v_{t+1})\coloneq\begin{dcases*}1/p&for $d(v_{t-1}, v_{t+1})=0$,\\ 1&for $d(v_{t-1},v_{t+1})=1$,\\ 1/q&for $d(v_{t-1},v_{t+1})=2$.\\ \end{dcases*}$ (15) $$

Choosing a large return parameter $p$ reduces backtracking since it decreases the probability of walking from $v_{t}$ to $v_{t-1}$.
Choosing a small in-out parameter $q$ has a similar effect of avoiding $v_{t-1}$, with a slight difference that it avoids the neighbors of $v_{t-1}$ as well.

We now show an extension of Theorem 2.2 to the above second-order random walks:

###### Theorem A.1 .

The non-backtracking random walk in Equation (13) and the node2vec random walk in Equation (14) are invariant if their underlying first-order random walk algorithm is invariant.

###### Proof.

The proof is given in Appendix A.4.3.
∎

###### Theorem A.1 .

###### Proof.

### A.2 Main Algorithm

We outline the main algorithms for the random walk and the recording function described in Section 2 and used in Section 5.
Algorithm 1 shows the random walk algorithm, and Algorithms 2, 3, and 4 show the recording functions.
For the random walk algorithm, we use non-backtracking described in Appendix A.1 and the minimum degree local rule conductance $c_{G}(\cdot)$ given in Equation (6) by default.

Based on the algorithms, in Figures 2, 3, and 4 we illustrate the task formats used for graph separation experiments in Section 5.1 by providing examples of input graphs, text records of random walks on them, and prediction targets for the language model that processes the records.
Likewise, in Figures 5, 6, and 7 we show task formats for transductive classification on arXiv citation network in Section 5.3.

Figure: Algorithm 1 Random walk algorithm

Figure: Algorithm 2 Recording function, using anonymization

Figure: Algorithm 3 Recording function, using anonymization and named neighborhoods

Figure: Algorithm 4 Recording function for transductive classification on arXiv network (Section 5.3)

Figure: Figure 2: Two CSL graphs and text records of random walks from Algorithms 1 and 3. Task is graph classification into 10 isomorphism types $\mathrm{csl}(41,s)$ for skip length $s\in\{2,3,4,5,6,9,11,12,13,16\}$. In random walks, we label vertices by anonymization and color edges by their time of discovery.
Refer to caption: x2.png

Figure: Figure 3: SR16 graphs and text records of random walks from Algorithms 1 and 3. The task is graph classification into two isomorphism types $\{4\times 4\text{ rook's graph},\text{Shrikhande graph}\}$. In random walks, we label vertices by anonymization and color edges by their time of discovery.
Refer to caption: x8.png

Figure: Figure 4: Two SR25 graphs and text records of random walks from Algorithms 1 and 3. The task is graph classification into 15 isomorphism types. In random walks, we label vertices by anonymization and color edges by their time of discovery.
Refer to caption: x14.png

Figure: Figure 5: Transductive classification on arXiv citation network using text record of random walk from Algorithms 1 and 4. Colors indicate task instruction, walk information, and label information.

Figure: Figure 6: Zero-shot format for vertex classification on arXiv citation network. Task instruction and label information are colored.

Figure: Figure 7: One-shot format for transductive classification on arXiv citation network. 40 labeled examples are given in form of multi-turn dialogue. Task instruction and label information are colored.

### A.3 Attention Visualizations

In Figure 8, we show an example of self-attention in the frozen Llama 3 8B model applied to arXiv transductive classification (Section 5.3).
We show attention weights on text record of random walk from the generated cs token as query, which is just before finishing the prediction e.g. cs.CV.
We color the strongest activation with orange, and do not color values below $1\%$ of it.
The model invests a nontrivial amount of attention on walk information such as Paper 1 cites 12, while also making use of titles and labels of labeled vertices.
This indicates the model is utilizing the graph structure recorded by the random walk in conjunction with other information to make predictions.

In Figures 9, 10, and 11, we provide examples of self-attention in DeBERTa models trained for graph separation (Section 5.1).
We first show attention weights on text record of random walk from the [CLS] query token.
Then, we further show an alternative visualization where the attention weights are mapped onto the original input graph.
For example, for each attention on $v_{t+1}$ where the walk has traversed $v_{t}\to v_{t+1}$, we regard it as an attention on the edge $(v_{t},v_{t+1})$ in the input graph.
We ignore [CLS] and [SEP] tokens since they do not appear on the input graph.
We observe that the models often focus on sparse, connected substructures, which presumably provide discriminative information on the isomorphism types.
In particular, for CSL graphs (Figure 9) we observe an interpretable pattern of approximate cycles composed of skip links.
This is presumably related to measuring the lengths of skip links, which provides sufficient information to infer isomorphism types of CSL graphs.

Figure: Figure 8: Example of attention in a frozen Llama 3 8B applied on arXiv transductive classification. Attention weights are averaged over all 30 heads.

Figure: Figure 9: Examples of attention from [CLS] token in a DeBERTa trained on CSL graph separation, forming approximate cycles using skip links. This is presumably related to measuring the lengths of skip links, which provides sufficient information to infer isomorphism types of CSL graphs.
Refer to caption: x20.png

Figure: Figure 10: Examples of attention from [CLS] token in a DeBERTa trained on SR16 graph separation. The model tend to focus on neighborhood records that form a sparse connected substructure, which we conjecture to provide discriminative information on the isomorphism type of SR16 graphs.
Refer to caption: x8.png

Figure: Figure 11: Examples of attention from [CLS] token in a DeBERTa trained on SR25 graph separation. The model tend to focus on neighborhood records that form a sparse connected substructure, which we conjecture to provide discriminative information on the isomorphism type of SR25 graphs.
Refer to caption: x14.png

### A.4 Proofs

We recall that an isomorphism between two graphs $G$ and $H$ is a bijection $\pi:V(G)\to V(H)$ such that any two vertices $u$ and $v$ are adjacent in $G$ if and only if $\pi(u)$ and $\pi(v)$ are adjacent in $H$.
If an isomorphism $\pi$ exists between $G$ and $H$, the graphs are isomorphic and written $G\simeq H$ or $G\overset{\pi}{\simeq}H$.

In the proofs, we write by $\mathrm{id}(\cdot)$ the namespace obtained by anonymization of a walk $v_{0}\to\cdots\to v_{l}$ (Section 2.1) that maps each vertex $v_{t}$ to its unique integer name $\mathrm{id}(v_{t})$ starting from $\mathrm{id}(v_{0})=1$.

Let us define some notations related to cover times.
These will be used from Appendix A.4.5.
We denote by $H(u,v)$ the expected number of steps a random walk starting from $u$ takes until reaching $v$.
This is called the hitting time between $u$ and $v$.
For a graph $G$, let $C_{V}(G,u)$ be the expected number of steps a random walk starting from $u$ takes until visiting every vertices of $G$.
The vertex cover time $C_{V}(G)$, or the cover time, is this quantity given by the worst possible $u$:

$$ $\displaystyle C_{V}(G)\coloneq\max_{u\in V(G)}C_{V}(G,u).$ (16) $$

Likewise, let $C_{E}(G,u)$ be the expected number of steps a random walk starting from $u$ takes until traversing every edge of $G$.
The edge cover time $C_{E}(G)$ is given by the worst possible $u$:

$$ $\displaystyle C_{E}(G)\coloneq\max_{u\in V(G)}C_{E}(G,u).$ (17) $$

For local balls $B_{r}(u)$, we always set the starting vertex of the random walk to $u$ (Section 2.2).
Thus, we define their cover times as follows:

$$ $\displaystyle C_{V}(B_{r}(u))\coloneq C_{V}(B_{r}(u),u),$ (18) $\displaystyle C_{E}(B_{r}(u))\coloneq C_{E}(B_{r}(u),u).$ (19) $$

#### A.4.1 Proof of Theorem 2.1 (Section 2.1 )

###### Theorem 2.1 .

$X_{\theta}(\cdot)$ is invariant if its random walk algorithm and recording function are invariant.

###### Proof.

We recall the invariance of a random walk algorithm in Equation (3):

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{l})\overset{d}{=}u_{0}\to\cdots\to u _{l},\quad\forall G\overset{\pi}{\simeq}H,$ (20) $$

where $v_{[\cdot]}$ is a random walk on $G$ and $u_{[\cdot]}$ is a random walk on $H$.
We further recall the invariance of a recording function $q:(v_{0}\to\cdots\to v_{l},G)\mapsto\mathbf{z}$ in Equation (7):

$$ $\displaystyle q(v_{0}\to\cdots\to v_{l},G)=q(\pi(v_{0})\to\cdots\to\pi(v_{l}), H),\quad\forall G\overset{\pi}{\simeq}H,$ (21) $$

for any given random walk $v_{[\cdot]}$ on $G$.
Combining Equation (20) and (21), we have the following:

$$ $\displaystyle q(v_{0}\to\cdots\to v_{l},G)\overset{d}{=}q(u_{0}\to\cdots\to u_ {l},H),\quad\forall G\simeq H.$ (22) $$

Then, since the reader neural network $f_{\theta}$ is a deterministic map, we have:

$$ $\displaystyle f_{\theta}(q(v_{0}\to\cdots\to v_{l},G))\overset{d}{=}f_{\theta} (q(u_{0}\to\cdots\to u_{l},H)),\quad\forall G\simeq H,$ (23) $$

which leads to:

$$ $\displaystyle X_{\theta}(G)\overset{d}{=}X_{\theta}(H),\quad\forall G\simeq H.$ (24) $$

This shows Equation (2) and completes the proof.
∎

###### Theorem 2.1 .

###### Proof.

#### A.4.2 Proof of Theorem 2.2 (Section 2.1 )

We first show a useful lemma.

###### Lemma A.2 .

The random walk in Equation (4) is invariant if the probability distributions of the starting vertex $v_{0}$ and each transition $v_{t-1}\to v_{t}$ are invariant.

###### Proof.

We prove by induction.
Let us write the invariance of the starting vertex $v_{0}$ as follows:

$$ $\displaystyle\pi(v_{0})\overset{d}{=}u_{0},\quad\forall G\overset{\pi}{\simeq}H,$ (25) $$

and the invariance of each transition $v_{t-1}\to v_{t}$ as follows, by fixing $v_{t-1}$ and $u_{t-1}$:

$$ $\displaystyle\pi(v_{t-1})\to\pi(v_{t})\overset{d}{=}u_{t-1}\to u_{t},\quad \forall G\overset{\pi}{\simeq}H,v_{t-1}\in V(G),u_{t-1}\coloneq\pi(v_{t-1}).$ (26) $$

Let us assume the following for some $t\geq 1$:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{t-1})\overset{d}{=}u_{0}\to\cdots\to u _{t-1},\quad G\overset{\pi}{\simeq}H.$ (27) $$

Then, from the chain rule of joint distributions, the first-order Markov property of random walk in Equation (4), and the invariance in Equation (26), we obtain the following:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{t})\overset{d}{=}u_{0}\to\cdots\to u _{t},\quad G\overset{\pi}{\simeq}H.$ (28) $$

By induction from the initial condition $\pi(v_{0})\overset{d}{=}u_{0}$ in Equation (25), the following holds $\forall l>0$:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{l})\overset{d}{=}u_{0}\to\cdots\to u _{l},\quad\forall G\overset{\pi}{\simeq}H.$ (29) $$

This shows Equation (3) and completes the proof.
∎

We now prove Theorem 2.2.

###### Theorem 2.2 .

The random walk in Equation (4) is invariant if its conductance $c_{[\cdot]}(\cdot)$ is invariant:

$$ $\displaystyle c_{G}(u,v)=c_{H}(\pi(u),\pi(v)),\quad\forall G\overset{\pi}{ \simeq}H.$ (30) $$

It includes constant conductance, and any choice that only uses degrees of endpoints $\mathrm{deg}(u)$, $\mathrm{deg}(v)$.

###### Proof.

We recall Equation (4) for a given conductance function $c_{G}:E(G)\to\mathbb{R}_{+}$:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x|v_{t-1}=u]\coloneq\frac{c_{G}(u,x)}{\sum_{y \in N(u)}c_{G}(u,y)}.$ (31) $$

From Lemma A.2, it is sufficient to show the invariance of each transition $v_{t-1}\to v_{t}$ as we sample $v_{0}$ from the invariant distribution $\mathrm{Uniform}(V(G))$ (Algorithm 1).
We rewrite Equation (26) as follows:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x|v_{t-1}=u]=\mathrm{Prob}[u_{t}=\pi(x)|u_{t- 1}=\pi(u)],\quad\forall G\overset{\pi}{\simeq}H.$ (32) $$

If the conductance function $c_{[\cdot]}(\cdot)$ is invariant (Equation (30)), we can show Equation (32) by:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x|v_{t-1}=u]$ $\displaystyle\coloneq\frac{c_{G}(u,x)}{\sum_{y\in N(u)}c_{G}(u,y)},$ $\displaystyle=\frac{c_{H}(\pi(u),\pi(x))}{\sum_{y\in N(u)}c_{H}(\pi(u),\pi(y))},$ $\displaystyle=\frac{c_{H}(\pi(u),\pi(x))}{\sum_{\pi(y)\in N(\pi(u))}c_{H}(\pi( u),\pi(y))},$ $\displaystyle=\mathrm{Prob}[u_{t}=\pi(x)|u_{t-1}=\pi(u)],\quad\forall G \overset{\pi}{\simeq}H.$ (33) $$

In the third equality, we used the fact that isomorphism $\pi(\cdot)$ preserves adjacency.
It is clear that any conductance function $c_{[\cdot]}(\cdot)$ with a constant conductance such as $c_{G}(\cdot)=1$ is invariant.
Furthermore, any conductance function that only uses degrees of endpoints $\mathrm{deg}(u)$, $\mathrm{deg}(v)$ is invariant as isomorphism $\pi(\cdot)$ preserves the degree of each vertex.
This completes the proof.
∎

###### Lemma A.2 .

###### Proof.

###### Theorem 2.2 .

###### Proof.

#### A.4.3 Proof of Theorem A.1 (Appendix A.1 )

We extend the proof of Theorem 2.2 given in Appendix A.4.2 to second-order random walks discussed in Appendix A.1.
We first show a useful lemma:

###### Lemma A.3 .

A second-order random walk algorithm is invariant if the probability distributions of the starting vertex $v_{0}$, the first transition $v_{0}\to v_{1}$, and each transition $(v_{t-2},v_{t-1})\to v_{t}$ for $t>1$ are invariant.

###### Proof.

We prove by induction.
The invariance of starting vertex $v_{0}$ and first transition $v_{0}\to v_{1}$ are:

$$ $\displaystyle\pi(v_{0})$ $\displaystyle\overset{d}{=}u_{0},\quad\forall G\overset{\pi}{\simeq}H,$ (34) $\displaystyle\pi(v_{0})\to\pi(v_{1})$ $\displaystyle\overset{d}{=}u_{0}\to u_{1},\quad\forall G\overset{\pi}{\simeq}H ,v_{0}\in V(G),u_{0}\coloneq\pi(v_{0}),$ (35) $$

and the invariance of each transition $(v_{t-2},v_{t-1})\to v_{t}$ for $t>1$ can be written as follows by fixing $(v_{t-2},v_{t-1})$ and $(u_{t-2},u_{t-1})$:

$$ $\displaystyle\pi(v_{t-2})\to\pi(v_{t-1})\to\pi(v_{t})\overset{d}{=}u_{t-2}\to u _{t-1}\to u_{t},\quad$ $\displaystyle\forall G\overset{\pi}{\simeq}H,$ $\displaystyle(v_{t-2},v_{t-1})\in E(G),$ $\displaystyle(u_{t-2},u_{t-1})\coloneq(\pi(v_{t-2}),\pi(v_{t-1})).$ (36) $$

Let us assume the following for some $t\geq 2$:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{t-2})\to\pi(v_{t-1})\overset{d}{=}u_ {0}\to\cdots\to u_{t-2}\to u_{t-1},\quad G\overset{\pi}{\simeq}H.$ (37) $$

Then, from the chain rule of joint distributions, the second-order Markov property of second-order random walks, and the invariance in Equation (A.4.3), we obtain the following:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{t-1})\to\pi(v_{t})\overset{d}{=}u_{0 }\to\cdots\to u_{t-1}\to u_{t},\quad G\overset{\pi}{\simeq}H.$ (38) $$

By induction from the initial condition $\pi(v_{0})\to\pi(v_{1})\overset{d}{=}u_{0}\to u_{1}$ given from Equations (34) and (35), the following holds $\forall l>0$:

$$ $\displaystyle\pi(v_{0})\to\cdots\to\pi(v_{l})\overset{d}{=}u_{0}\to\cdots\to u _{l},\quad\forall G\overset{\pi}{\simeq}H.$ (39) $$

This shows Equation (3) and completes the proof.
∎

We now prove Theorem A.1.

###### Theorem A.1 .

The non-backtracking random walk in Equation (13) and the node2vec random walk in Equation (14) are invariant if their underlying first-order random walk algorithm is invariant.

###### Proof.

We assume that the first transition $v_{0}\to v_{1}$ is given by the underlying first-order random walk algorithm.
This is true for non-backtracking since there is no $v_{t-2}$ to avoid, and true for the official implementation of node2vec [].
Then from Lemma A.3, it is sufficient to show the invariance of each transition $(v_{t-2},v_{t-1})\to v_{t}$ for $t>1$ as we sample $v_{0}$ from the invariant distribution $\mathrm{Uniform}(V(G))$ (Algorithm 1) and the first transition $v_{0}\to v_{1}$ is given by the first-order random walk which is assumed to be invariant.
We rewrite Equation (A.4.3) as follows:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x|v_{t-1}=j,v_{t-2}=i]=\mathrm{Prob}[u_{t}= \pi(x)|u_{t-1}=\pi(j),u_{t-2}=\pi(i)],\quad\forall G\overset{\pi}{\simeq}H.$ (40) $$

For non-backtracking, we first handle the case where $i\to j$ reaches a dangling vertex $j$ which has $i$ as its only neighbor.
In this case the walk begrudgingly backtracks $i\to j\to i$ (Appendix A.1).
Since isomorphism $\pi(\cdot)$ preserves adjacency, $\pi(i)\to\pi(j)$ also reaches a dangling vertex $\pi(j)$ and must begrudgingly backtrack $\pi(i)\to\pi(j)\to\pi(i)$.
By interpreting the distributions on $v_{t}$ and $u_{t}$ as one-hot at $i$ and $\pi(i)$, respectively, we can see that Equation (40) holds.
If $i\to j$ does not reach a dangling vertex, the walk $j\to x$ follows the invariant probability of the underlying first-order random walk $\mathrm{Prob}[v_{t+1}=x|v_{t}=j]$ renormalized over $N(j)\setminus\{i\}$.
Then we can show Equation (40) by:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x$ $\displaystyle|v_{t-1}=j,v_{t-2}=i]$ $\displaystyle\coloneq\begin{dcases*}\frac{\mathrm{Prob}[v_{t}=x|v_{t-1}=j]}{ \sum_{y\in N(j)\setminus\{i\}}\mathrm{Prob}[v_{t}=y|v_{t-1}=j]}&for $x\neq i$, \\ 0\vphantom{\frac{0}{0}}&for $x=i$,\end{dcases*}$ $\displaystyle=\begin{dcases*}\frac{\mathrm{Prob}[u_{t}=\pi(x)|u_{t-1}=\pi(j)]} {\sum_{\pi(y)\in N(\pi(j))\setminus\{\pi(i)\}}\mathrm{Prob}[u_{t}=\pi(y)|u_{t- 1}=\pi(j)]}&for $\pi(x)\neq\pi(i)$,\\ 0\vphantom{\frac{0}{0}}&for $\pi(x)=\pi(i)$,\end{dcases*}$ $\displaystyle=\mathrm{Prob}[u_{t}=\pi(x)|u_{t-1}=\pi(j),u_{t-2}=\pi(i)],\quad \forall G\overset{\pi}{\simeq}H.$ (41) $$

In the second equality, we have used the fact that isomorphism $\pi(\cdot)$ is a bijection and preserves adjacency, and the assumption that the first-order random walk algorithm is invariant.
For node2vec random walk, we first show the invariance of the weighting term $\alpha(i,x)$ in Equation (15) using the fact that isomorphism preserves shortest path distances between vertices $d(i,x)=d(\pi(i),\pi(x))$:

$$ $\displaystyle\alpha(i,x)$ $\displaystyle\coloneq\begin{dcases*}1/p&for $d(i,x)=0$,\\ 1&for $d(i,x)=1$,\\ 1/q&for $d(i,x)=2$.\\ \end{dcases*}$ $\displaystyle=\begin{dcases*}1/p&for $d(\pi(i),\pi(x))=0$,\\ 1&for $d(\pi(i),\pi(x))=1$,\\ 1/q&for $d(\pi(i),\pi(x))=2$.\\ \end{dcases*}$ $\displaystyle=\alpha(\pi(i),\pi(x)).$ (42) $$

Then we can show Equation (40) by:

$$ $\displaystyle\mathrm{Prob}[v_{t}=x|v_{t-1}=j,v_{t-2}=i]$ $\displaystyle\coloneq\frac{\alpha(i,x)\,\mathrm{Prob}[v_{t}=x|v_{t-1}=j]}{\sum _{y\in N(j)}\alpha(i,y)\,\mathrm{Prob}[v_{t}=y|v_{t-1}=j]},$ $\displaystyle=\frac{\alpha(\pi(i),\pi(x))\,\mathrm{Prob}[u_{t}=\pi(x)|u_{t-1}= \pi(j)]}{\sum_{\pi(y)\in N(\pi(j))}\alpha(\pi(i),\pi(y))\,\mathrm{Prob}[u_{t}= \pi(y)|u_{t-1}=\pi(j)]},$ $\displaystyle=\mathrm{Prob}[u_{t}=\pi(x)|u_{t-1}=\pi(j),u_{t-2}=\pi(i)],\quad \forall G\overset{\pi}{\simeq}H.$ (43) $$

In the second equality, we have used the fact that isomorphism $\pi(\cdot)$ preserves adjacency, and the assumption that the first-order random walk algorithm is invariant.
This completes the proof.
∎

###### Lemma A.3 .

###### Proof.

###### Theorem A.1 .

###### Proof.

#### A.4.4 Proof of Theorem 2.3 (Section 2.1 )

###### Theorem 2.3 .

A recording function $q:(v_{0}\to\cdots\to v_{l},G)\mapsto\mathbf{z}$ that uses anonymization, optionally with named neighborhoods, is invariant.

###### Proof.

Given a walk $v_{0}\to\cdots\to v_{l}$ on $G$, we can write the anonymized namespace $\mathrm{id}(\cdot)$ as follows:

$$ $\displaystyle\mathrm{id}(v_{t})=1+\operatorname*{arg\,min}_{i}[v_{i}=v_{t}].$ (44) $$

Consider any walk $\pi(v_{0})\to\cdots\to\pi(v_{l})$ on some $H$ which is isomorphic to $G$ via $\pi$.
Let us denote the anonymization of this walk as $\mathrm{id}^{\prime}(\cdot)$.
Then we have:

$$ $\displaystyle\mathrm{id}^{\prime}(\pi(v_{t}))$ $\displaystyle=1+\operatorname*{arg\,min}_{i}[\pi(v_{i})=\pi(v_{t})],$ $\displaystyle=1+\operatorname*{arg\,min}_{i}[v_{i}=v_{t}],$ $\displaystyle=\mathrm{id}(v_{t}),\quad\forall G\overset{\pi}{\simeq}H.$ (45) $$

The second equality is due to the fact that $\pi$ is a bijection.
This completes the proof for anonymization.
For the named neighborhoods, we prove by induction.
Let us fix some $t\geq 1$ and assume:

$$ $\displaystyle q(v_{0}\to\cdots\to v_{t-1},G)=q(\pi(v_{0})\to\cdots\to\pi(v_{t- 1}),H),\quad\forall G\overset{\pi}{\simeq}H.$ (46) $$

Let $T\subseteq E(G)$ be the set of edges recorded by $\mathbf{z}\coloneq q(v_{0}\to\cdots\to v_{t-1},G)$, and $T^{\prime}\subseteq E(H)$ be the set of edges recorded by $\mathbf{z}^{\prime}\coloneq q(\pi(v_{0})\to\cdots\to\pi(v_{t-1}),H)$.
Then, $T$ and $T^{\prime}$ are isomorphic via $\pi$:

$$ $\displaystyle T^{\prime}=\{(\pi(u),\pi(v))\forall(u,v)\in T\}.$ (47) $$

The equality is shown as follows.
$(\supseteq)$ Any $(u,v)\in T$ is recorded in $\mathbf{z}$ as $(\mathrm{id}(u),\mathrm{id}(v))$.
From Equations (46) and (A.4.4), we have $\mathbf{z}=\mathbf{z}^{\prime}$ and $(\mathrm{id}(u),\mathrm{id}(v))=(\mathrm{id}(\pi(u)),\mathrm{id}(\pi(v)))$.
Thus, $(\pi(u),\pi(v))$ is recorded in $\mathbf{z}^{\prime}$ as $(\mathrm{id}(\pi(u)),\mathrm{id}(\pi(v)))$, i.e. $(\pi(u),\pi(v))\in T^{\prime}$.
$(\subseteq)$ This follows from symmetry.
Now, we choose some $v_{t}\in N(v_{t-1})$ and consider the set $F\subseteq E(G)$ of all unrecorded edges from $v_{t}$:

$$ $\displaystyle F\coloneq\{(v_{t},u):u\in N(v_{t})\}\setminus T.$ (48) $$

Then, the set $D$ of unrecorded neighbors of $v_{t}$ is given as:

$$ $\displaystyle D\coloneq\{u:(v_{t},u)\in F\}.$ (49) $$

Since $\pi(\cdot)$ preserves adjacency, the set $F^{\prime}\subseteq E(H)$ of all unrecorded edges from $\pi(v_{t})$ is given by:

$$ $\displaystyle F^{\prime}$ $\displaystyle\coloneq\{(\pi(v_{t}),\pi(u)):\pi(u)\in N(\pi(v_{t}))\}\setminus T ^{\prime},$ $\displaystyle=\{(\pi(v_{t}),\pi(u)):u\in N(v_{t})\}\setminus\{(\pi(u^{\prime}) ,\pi(v^{\prime}))\forall(u^{\prime},v^{\prime})\in T\},$ $\displaystyle=\{(\pi(v_{t}),\pi(u)):u\in N(v_{t}),(v_{t},u)\notin T\},$ $\displaystyle=\{(\pi(v_{t}),\pi(u)):(v_{t},u)\in F\},$ (50) $$

and consequently:

$$ $\displaystyle D^{\prime}$ $\displaystyle\coloneq\{\pi(u):(\pi(v_{t}),\pi(u))\in F^{\prime}\},$ $\displaystyle=\{\pi(u):u\in D\}.$ (51) $$

While $D$ and $D^{\prime}$ may contain vertices not yet visited by the walks and hence not named by $\mathrm{id}(\cdot)$, what we record are named neighbors.
Let $S$ be the set of all named vertices in $G$.
It is clear that the set $S^{\prime}$ of named vertices in $H$ is given by $S^{\prime}=\{\pi(v):v\in S\}$.
Then, the named neighbors in $G$ to be newly recorded for $v_{t-1}\to v_{t}$ is given by $U=D\cap S$, and for $\pi(v_{t-1})\to\pi(v_{t})$ in $H$ the set is given by $U^{\prime}=D^{\prime}\cap S^{\prime}$.
Since $\pi(\cdot)$ is a bijection, we can see that $U^{\prime}=\{\pi(u):u\in U\}$.
From the invariance of anonymization in Equation (A.4.4), $U$ and $U^{\prime}$ are named identically $\{\mathrm{id}(u):u\in U\}=\{\mathrm{id}(\pi(u)):\pi(u)\in U^{\prime}\}$, and therefore will be recorded identically.
As a result, the information to be added to the records at time $t$ are identical, and we have:

$$ $\displaystyle q(v_{0}\to\cdots\to v_{t},G)=q(\pi(v_{0})\to\cdots\to\pi(v_{t}), H),\quad\forall G\overset{\pi}{\simeq}H.$ (52) $$

Then, by induction from the initial condition:

$$ $\displaystyle q(v_{0},G)=q(\pi(v_{0}),H)=\mathrm{id}(v_{0})=\mathrm{id}(\pi(v_ {0}))=1,$ (53) $$

the recording function using anonymization and named neighborhoods is invariant.
∎

###### Theorem 2.3 .

###### Proof.

#### A.4.5 Proof of Theorem 2.4 (Section 2.2 )

###### Theorem 2.4 .

For a uniform random walk on an infinite graph $G$ starting at $v$, the cover time and edge cover time of the finite local ball $B_{r}(v)$ are not always finitely bounded.

###### Proof.

We revisit the known fact that hitting times on the infinite line $\mathbb{Z}$ is infinite [, , , ].
Consider a local ball $B_{1}(0)$ of radius $1$ from the origin 0 0 such that $V(B_{1}(0))=\{-1,0,1\}$.
Let us assume that the expected number of steps for a random walk starting at 0 0 to visit $1$ for the first time is finite, and denote it by $T$.
In the first step of the walk, we have to go either to $-1$ or $1$.
If we go to $-1$, we have to get back to 0 0 and then to $1$ which would take $2T$ in expectation (by translation symmetry).
This leads to $T=1/2\cdot 1+1/2\cdot(1+2T)=1+T$, which is a contradiction.
Since visiting all vertices or traversing all edges in in $B_{1}(0)$ clearly involves visiting $1$, the cover time and edge cover time cannot be finitely bounded.
∎

###### Theorem 2.4 .

###### Proof.

#### A.4.6 Proof of Theorem 2.5 (Section 2.2 )

Let us recall that our graph $G$ is locally finite (Section 2.2), and denote its maximum degree as $\Delta$.
We further denote by $d(u,v)$ the shortest path distance between $u$ and $v$.
We show some useful lemmas.
We first show that $H(u,x)$, the expected number of steps of a random walk starting at $u$ takes until reaching $x$, is finite for any $u$, $x$ in $B_{r}(v)$ for any nonzero restart probability $\alpha$ or restart period $k\geq r$.

###### Lemma A.4 .

For any $u$ and $x$ in $B_{r}(v)$, $H(u,x)$ is bounded by the following:

$$ $\displaystyle H(u,x)\leq\frac{1}{\alpha}+\frac{1}{\alpha}\left(\frac{\Delta}{1 -\alpha}\right)^{r}+\frac{1}{\alpha}\left(\frac{1}{\alpha}-1\right)\left(\frac {\Delta}{1-\alpha}\right)^{2r},$ (54) $$

if the random walk restarts at $v$ with any probability $\alpha\in(0,1)$, and:

$$ $\displaystyle H(u,x)\leq k+k\Delta^{r},$ (55) $$

if the random walk restarts at $v$ with any period $k\geq r$.

###### Proof.

We first prove for random restarts.
The proof is inspired by Theorem 1.1 of McNew (2013) [] and Lemma 2 of Zuckerman (1991) [].
We clarify some measure-theoretic details.
Let $W$ be the set of all (infinite) random walks on $G$.
We denote by $P$ the probability measure defined on the space $W$, equipped with its cylinder $\sigma$-algebra, by the random walk restarting at $v$ with probability $\alpha\in(0,1)$.
For a vertex $x$ in $G$, we define the hitting time function $|\cdot|_{x}:W\to\mathbb{N}\cup\{\infty\}$ as follows:

$$ $\displaystyle|w|_{x}\coloneq\operatorname*{arg\,min}_{i}[(w)_{i}=x],\quad \forall w\in W.$ (56) $$

Let $W(a)$ be the set of all random walks that start at $a$, $W(a,b)$ be the set of random walks that start at $a$ and visit $b$, and $W(a,b^{-})$ be the set of random walks that start at $a$ and do not visit $b$.
Then, the measurability of $|\cdot|_{x}$ follows from the measurability of the sets $W(a)$, $W(a,b)$, and $W(a,b^{-})$, which we show as follows.
$\forall a,b\in V(G)$, $W(a)$ is clearly measurable, $W(a,b)$ is measurable as it equals $\bigcup_{n\in\mathbb{N}}\{w\in W|(w)_{1}=a,(w)_{n}=b\}$, and $W(a,b^{-})$ is measurable as it is $W(a)\setminus W(a,b)$.

Consider $W(u,x^{-})$, the set of random walks that start at $u$ and never visit $x$.
We start by showing that this set is of measure zero:

$$ $\displaystyle P(W(u,x^{-}))=0.$ (57) $$

For this, we use the fact that $W(u,x^{-})=W(u,v^{-},x^{-})\cup W(u,v,x^{-})$, where $W(u,v^{-},x^{-})$ is the set of random walks starting at $u$ that do not visit $v$ nor $x$, and $W(u,v,x^{-})$ is the set of walks starting at $u$ that visit $v$ and do not visit $x$.
We have the following:

$$ $\displaystyle P(W(u,x^{-}))$ $\displaystyle=P(W(u,v^{-},x^{-}))+P(W(u,v,x^{-})),$ $\displaystyle\leq P(W(u,v^{-}))+P(W(u,v,x^{-})).$ (58) $$

We show Equation (57) by showing $P(W(u,v^{-}))=0$ and $P(W(u,v,x^{-}))=0$ in Equation (A.4.6).

- 1.
$(P(W(u,v^{-}))=0)$
Consider $W(u,v^{-})$, the set of all random walks that start at $u$ and never visit $v$.
Since restart sends a walk to $v$, every walk in this set never restarts.
The probability of a walk not restarting until step $t$ is $(1-\alpha)^{t}$.
Denote this probability by $p_{t}$, and let $p$ be the probability of a random walk to never restart.
Then $p_{t}\downarrow p=0$ and $P(W(u,v^{-}))\leq p=0$.
- 2.
$(P(W(u,v,x^{-}))=0)$
Assume $P(W(u,v,x^{-}))>0$.
Then $P(W(v,x^{-}))>0$ since each walk step is independent.
Let $W_{N}(v,x^{-})$ be the set of walks that start at $v$ and do not reach $x$ within $N$ restarts.
Then we have $W_{N}(v,x^{-})\downarrow W(v,x^{-})$.
If a walk restarts at $v$, the probability of reaching $x$ before the next restart is at least the probability of exactly walking the shortest path from $v$ to $x$, which is $\geq(\frac{1-\alpha}{\Delta})^{d(v,x)}\in(0,1)$.
Then $P(W_{N}(v,x^{-}))\leq(1-(\frac{1-\alpha}{\Delta})^{d(v,x)})^{N}\downarrow 0$, leading to $P(W(v,x^{-}))=0$.
This is a contradiction, so we have $P(W(u,v,x^{-}))=0$.

We are now ready to bound $H(u,x)$.
Using the hitting time function $|\cdot|_{x}$ in Equation (56), we have:

$$ $\displaystyle H(u,x)=\mathbb{E}\left[|w|_{x}|w\in W(u)\right].$ (59) $$

Since $W(u)=W(u,x)\cup W(u,x^{-})$, and $P(W(u,x^{-}))=0$ from Equation (57), we have:

$$ $\displaystyle H(u,x)$ $\displaystyle=\mathbb{E}[|w|_{x}|w\in W(u,x)],$ $\displaystyle=\int_{W(u,x)}|w|_{x}\,dP(w|w\in W(u,x)).$ (60) $$

Each walk in $W(u,x)$ starts at $u$ and, when it reaches $x$, it either has or has not visited $v$.
We treat the two cases separately.
Let $W(a,b,c)$ be the set of walks that start at $a$ and reach $c$ after $b$, and let $W(a,b^{-},c)$ be the set of walks that start at $a$ and reach $c$ before $b$.
Then we have:

$$ $\displaystyle H(u,x)$ $\displaystyle=\int_{W(u,v,x)\cup W(u,v^{-},x)}|w|_{x}\,dP(w|W(u,x)),$ $\displaystyle=\int_{W(u,v,x)}|w|_{x}\,dP(w|W(u,x))+\int_{W(u,v^{-},x)}|w|_{x} \,dP(w|W(u,x)).$ (61) $$

Let $\hat{H}(a,b,c)$ (or $\hat{H}(a,b^{-},c)$) be the expected number of steps for a walk starting at $a$ to reach $c$ after reaching $b$ (or before $b$), given that it is in $W(a,b,c)$ (or in $W(a,b^{-},c)$).
If a walk from $u$ reaches $v$ before $x$, the expected steps is given by $\hat{H}(u,x^{-},v)+H(v,x)$.
If the walk reaches $x$ before $v$, the expected steps is $\hat{H}(u,v^{-},x)$.
Then, if $W(u,v^{-},x)\neq\emptyset$, we can write $H(u,x)$ as follows:

$$ $\displaystyle H(u,x)$ $\displaystyle=\left[\hat{H}(u,x^{-},v)+H(v,x)\right]P(W(u,v,x)|W(u,x))$ $\displaystyle\quad+\hat{H}(u,v^{-},x)\,P(W(u,v^{-},x)|W(u,x)).$ (62) $$

On the other hand, if $W(u,v^{-},x)=\emptyset$, we simply have:

$$ $\displaystyle H(u,x)=\hat{H}(u,x^{-},v)+H(v,x).$ (63) $$

We first consider $\hat{H}(u,x^{-},v)$, the expected number of steps from $u$ to reach $v$ before $x$.
We show:

$$ $\displaystyle\hat{H}(u,x^{-},v)\leq\frac{1}{\alpha}.$ (64) $$

To see this, note that $\hat{H}(u,x^{-},v)$ is equivalent to the expectation $\mathbb{E}[T]$ of the number of steps $T$ to reach $v$ from $u$, on the graph $G$ with the vertex $x$ deleted and transition probabilities renormalized.
If $u$ is isolated on this modified graph, the only walk in $W(u,x^{-},v)$ is the one that immediately restarts at $v$, giving $\mathbb{E}[T]=1$.
Otherwise, we have $\mathbb{E}[T]\leq 1/\alpha$ due to the following.
Let $T^{\prime}$ be the number of steps until the first restart at $v$.
Since restart can be treated as a Bernoulli trial with probability of success $\alpha$, $T^{\prime}$ follows geometric distribution with expectation $1/\alpha$.
Since it is possible for the walk to reach $v$ before the first restart, we have $\mathbb{E}[T]\leq\mathbb{E}[T^{\prime}]=1/\alpha$, which gives Equation (64).

We now consider $H(v,x)$, the expectation $\mathbb{E}[T]$ of the number of steps $T$ to reach $x$ from $v$.
Let $T^{\prime}$ be the steps until the walk restarts at $v$, then exactly walks the shortest path from $v$ to $x$ for the first time, and then restarts at $v$.
Since $T^{\prime}$ walks until restart after walking the shortest path to $x$, and it is possible for a walk to reach $x$ before walking the shortest path to it, we have $\mathbb{E}[T]\leq\mathbb{E}[T^{\prime}]$.
Then, we split the walk of length $T^{\prime}$ into $N$ trials, where each trial consists of restarting at $v$ and walking until the next restart.
A trial is successful if it immediately walks the shortest path from $v$ to $x$.
Then $N$ is the number of trials until we succeed, and it follows geometric distribution with probability of success at least $(\frac{1-\alpha}{\Delta})^{d(v,x)}$ due to bounded degrees.
Its expectation is then bounded as:

$$ $\displaystyle\mathbb{E}[N]\leq\left(\frac{\Delta}{1-\alpha}\right)^{d(v,x)}.$ (65) $$

Let $S_{i}$ be the length of the $i$-th trial.
Since each $S_{i}$ is i.i.d. with finite mean $\mathbb{E}[S_{i}]=1/\alpha$, and $N$ is stopping time, we can apply Wald’s identity [] to compute the expectation of $T^{\prime}$:

$$ $\displaystyle\mathbb{E}[T^{\prime}]$ $\displaystyle=\mathbb{E}[S_{1}+\cdots+S_{N}],$ $\displaystyle=\mathbb{E}[N]\mathbb{E}[S_{1}],$ $\displaystyle\leq\frac{1}{\alpha}\left(\frac{\Delta}{1-\alpha}\right)^{d(v,x)}.$ (66) $$

We remark that $H(v,x)\leq\mathbb{E}[T^{\prime}]$.
Combining this result with Equation (64), we have:

$$ $\displaystyle\hat{H}(u,x^{-},v)+H(v,x)\leq\frac{1}{\alpha}+\frac{1}{\alpha} \left(\frac{\Delta}{1-\alpha}\right)^{d(v,x)}.$ (67) $$

If $W(u,v^{-},x)=\emptyset$, we have $H(u,x)=\hat{H}(u,x^{-},v)+H(v,x)$ from Equation (63) and it is finitely bounded for any $\alpha\in(0,1)$ by the above.
If $W(u,v^{-},x)\neq\emptyset$, Equations (A.4.6) and (67) lead to:

$$ $\displaystyle H(u,x)$ $\displaystyle\leq\hat{H}(u,x^{-},v)+H(v,x)+\hat{H}(u,v^{-},x)\,P(W(u,v^{-},x)| W(u,x)),$ $\displaystyle\leq\frac{1}{\alpha}+\frac{1}{\alpha}\left(\frac{\Delta}{1-\alpha }\right)^{d(v,x)}+\hat{H}(u,v^{-},x)\,P(W(u,v^{-},x)|W(u,x)),$ (68) $$

and it suffices to bound $\hat{H}(u,v^{-},x)\,P(W(u,v^{-},x)|W(u,x))$.
We show the following:

$$ $\displaystyle\hat{H}(u,v^{-},x)$ $\displaystyle=\int_{W(u,v^{-},x)}|w|_{x}\,dP(w|W(u,v^{-},x)),$ $\displaystyle=\sum_{k=1}^{\infty}\int_{\{w\in W(u,v^{-},x)\wedge|w|_{x}=k\}}|w |_{x}\,dP(w|W(u,v^{-},x)),$ $\displaystyle=\sum_{k=1}^{\infty}k\int_{\{w\in W(u,v^{-},x)\wedge|w|_{x}=k\}} dP(w|W(u,v^{-},x)),$ $\displaystyle=\sum_{k=1}^{\infty}k\,P(\{w\in W(u,v^{-},x)\wedge|w|_{x}=k\}|W(u ,v^{-},x)),$ $\displaystyle\leq\sum_{k=1}^{\infty}k\,P(\{w:|w|_{x}=k\}|W(u,v^{-},x)),$ $\displaystyle=\sum_{k=1}^{\infty}k\,\frac{P(\{w:|w|_{x}=k\wedge w\in W(u,v^{-} ,x)\})}{P(W(u,v^{-},x))},$ $\displaystyle\leq\sum_{k=1}^{\infty}k(1-\alpha)^{k}\frac{1}{P(W(u,v^{-},x))},$ $\displaystyle=\frac{1}{\alpha}\left(\frac{1}{\alpha}-1\right)\frac{1}{P(W(u,v^ {-},x))}.$ (69) $$

We have used Fubini’s theorem for the second equality.
Then we have:

$$ $\displaystyle\hat{H}(u,v^{-},x)\,P(W(u,v^{-},x)|W(u,x))$ $\displaystyle\leq\frac{1}{\alpha}\left(\frac{1}{\alpha}-1\right)\frac{P(W(u,v^ {-},x)|W(u,x))}{P(W(u,v^{-},x))},$ $\displaystyle=\frac{1}{\alpha}\left(\frac{1}{\alpha}-1\right)\frac{1}{P(W(u,x) )}.$ (70) $$

$P(W(u,x))$ is at least the probability of precisely walking the shortest path from $u$ to $x$, which has length $d(u,x)\leq 2r$ since $u$ and $x$ are both in $B_{r}(v)$.
This gives us the following:

$$ $\displaystyle P(W(u,x))$ $\displaystyle\geq\left(\frac{1-\alpha}{\Delta}\right)^{d(u,x)},$ $\displaystyle\geq\left(\frac{1-\alpha}{\Delta}\right)^{2r}.$ (71) $$

Combining this with Equation (A.4.6), we have:

$$ $\displaystyle\hat{H}(u,v^{-},x)\,P(W(u,v^{-},x)|W(u,x))\leq\frac{1}{\alpha} \left(\frac{1}{\alpha}-1\right)\left(\frac{\Delta}{1-\alpha}\right)^{2r}.$ (72) $$

Combining with Equations (A.4.6) and (67), we have:

$$ $\displaystyle H(u,x)\leq\frac{1}{\alpha}+\frac{1}{\alpha}\left(\frac{\Delta}{1 -\alpha}\right)^{d(v,x)}+\frac{1}{\alpha}\left(\frac{1}{\alpha}-1\right)\left( \frac{\Delta}{1-\alpha}\right)^{2r},$ (73) $$

for any $\alpha\in(0,1)$.
Notice that, while this bound is for the case $W(u,v^{-},x)\neq\emptyset$, it subsumes the bound for the case $W(u,v^{-},x)=\emptyset$ (Equation (67)).
Then, using $d(v,x)\leq r$, we get Equation (54).
This completes the proof for random restarts.

We now prove for periodic restarts.
If the walk starting at $u$ reaches $x$ before restarting at $v$, the steps taken is clearly less than $k$.
If the walk starting at $u$ restarts at $v$ at step $k$ before reaching $x$, it now needs to reach $x$ from $v$, while restarting at $v$ at every $k$ steps.
Let $T$ be the steps taken to reach $x$ from $v$.
Let $T^{\prime}$ be the number of steps until the walk restarts at $v$, then exactly follows the shortest path from $v$ to $x$ for the first time, and then restarts at $v$.
It is clear that $\mathbb{E}[T]\leq\mathbb{E}[T^{\prime}]$.
Then, we split the walk of length $T^{\prime}$ into $N$ trials, where each trial consists of restarting at $v$ and walking $k$ steps until the next restart.
A trial is successful if it immediately walks the shortest path from $v$ to $x$.
Then $N$ is the number of trials until we get a success, and it follows geometric distribution with probability of success at least $(1/\Delta)^{d(v,x)}$ only for $k\geq d(v,x)$, and zero for $k<d(v,x)$ since the walk cannot reach $x$ before restart.
Hence, its expectation is at most $\Delta^{d(v,x)}$ for $k\geq d(v,x)$, and we have $\mathbb{E}[T]\leq\mathbb{E}[T^{\prime}]=k\mathbb{E}[N]\leq k\Delta^{d(v,x)}$.
Adding the $k$ steps until the first restart at $v$, we have:

$$ $\displaystyle H(u,x)\leq k+k\Delta^{d(v,x)},$ (74) $$

for any $k\geq d(v,x)$.
Using $d(v,x)\leq r$, we get Equation (55).
This completes the proof.
∎

We now extend Lemma A.4 to edges.
Let $H(u,(x,y))$ be the expected number of steps of a random walk starting at $u$ takes until traversing an edge $(x,y)$ by $x\to y$.
We show that $H(u,(x,y))$ is finite for any $u$ and adjacent $x$, $y$ in $B_{r}(v)$ for any nonzero restart probability $\alpha$ or restart period $k\geq r+1$.

###### Lemma A.5 .

For any $u$ and adjacent $x$, $y$ in $B_{r}(v)$, $H(u,(x,y))$ is bounded by the following:

$$ $\displaystyle H(u,(x,y))$ $\displaystyle\leq\frac{1}{\alpha}+\frac{1}{\alpha}\left(\frac{\Delta}{1-\alpha }\right)^{r+1}+\frac{1}{\alpha}\left(\frac{1}{\alpha}-1\right)\left(\frac{ \Delta}{1-\alpha}\right)^{2r+1},$ (75) $$

if the random walk restarts at $v$ with any probability $\alpha\in(0,1)$, and:

$$ $\displaystyle H(u,(x,y))$ $\displaystyle\leq k+k\Delta^{r+1},$ (76) $$

if the random walk restarts at $v$ with any period $k\geq r+1$.

###### Proof.

The proof is almost identical to Lemma A.4, except the target $x$ of reaching is substituted by $(x,y)$ in the direction of $x\to y$, and all arguments that use the shortest path from $u$ or $v$ to $x$ instead use the shortest path to $x$ postfixed by $x\to y$, which adds $+1$ to several terms in the bounds.
∎

We are now ready to prove Theorem 2.5.

###### Theorem 2.5 .

In Theorem 2.4, if the random walk restarts at $v$ with any nonzero probability $\alpha$ or any period $k\geq r+1$, the cover time and edge cover time of $B_{r}(v)$ are always finite.

###### Proof.

The proof is inspired by the spanning tree argument of Aleliunas et al. (1979) [].
Let us consider a depth first search of $B_{r}(v)$ starting from $v$.
We denote by $T$ the resulting spanning tree with vertices $V(T)=V(B_{r}(v))$.
We consider the expected time for a random walk starting at $v$ to visit every vertex in the precise order visited by the depth first search by traversing each edge twice.
It is clear that this upper-bounds the cover time of $B_{r}(v)$ starting at $v$ (Equation (18)):

$$ $\displaystyle C_{V}(B_{r}(v))\leq\sum_{(x,y)\in E(T)}[H(x,y)+H(y,x)].$ (77) $$

Then, using the bounds from Lemma A.4, the property of spanning trees $|E(T)|=|V(T)|-1$, and the fact that $|V(T)|=|V(B_{r}(v))|\leq\Delta^{r}$ from bounded degree, we obtain:

$$ $\displaystyle C_{V}(B_{r}(v))$ $\displaystyle\leq 2(\Delta^{r}-1)\left(\frac{1}{\alpha}+\frac{1}{\alpha}\left( \frac{\Delta}{1-\alpha}\right)^{r}+\frac{1}{\alpha}\left(\frac{1}{\alpha}-1 \right)\left(\frac{\Delta}{1-\alpha}\right)^{2r}\right),$ (78) $$

if the random walk restarts at $v$ with any probability $\alpha\in(0,1)$, and:

$$ $\displaystyle C_{V}(B_{r}(v))$ $\displaystyle\leq 2(\Delta^{r}-1)(k+k\Delta^{r}),$ (79) $$

if the random walk restarts at $v$ with any period $k\geq r$.
This completes the proof for the cover time.
For the edge cover time, we consider the expected time for a random walk starting at $v$ to visit every edge in the precise order discovered(^6^66We remark that depth first search discovers all edges of a graph, while not necessarily visiting all of them.) by the depth first search by traversing each edge twice.
It is clear that this upper-bounds the edge cover time of $B_{r}(v)$ starting at $v$ (Equation (19)):

$$ $\displaystyle C_{E}(B_{r}(v))\leq\sum_{(x,y)\in E(B_{r}(v))}[H(x,(x,y))+H(y,(y ,x))].$ (80) $$

Then, using Lemma A.4 and the fact that $|E(B_{r}(v))|\leq\Delta^{2r}-1$ from bounded degree, we obtain:

$$ $\displaystyle C_{E}(B_{r}(v))$ $\displaystyle\leq 2(\Delta^{2r}-1)\left(\frac{1}{\alpha}+\frac{1}{\alpha}\left (\frac{\Delta}{1-\alpha}\right)^{r+1}+\frac{1}{\alpha}\left(\frac{1}{\alpha}-1 \right)\left(\frac{\Delta}{1-\alpha}\right)^{2r+1}\right),$ (81) $$

if the random walk restarts at $v$ with any probability $\alpha\in(0,1)$, and:

$$ $\displaystyle C_{E}(B_{r}(v))$ $\displaystyle\leq 2(\Delta^{2r}-1)\cdot(k+k\Delta^{r+1}),$ (82) $$

if the random walk restarts at $v$ with any period $k\geq r+1$.
This completes the proof.
∎

While our proof shows finite bounds for the cover times, it is possible that they can be made tighter, for instance based on Zuckerman (1991) [].
We leave improving the bounds as a future work.

###### Lemma A.4 .

###### Proof.

###### Lemma A.5 .

###### Proof.

###### Theorem 2.5 .

###### Proof.

#### A.4.7 Proof of Theorem 3.2 (Section 3.1 )

We recall universal approximation of graph-level functions in probability (Definition 3.1):

###### Definition 3.1 .

We say $X_{\theta}(\cdot)$ is a universal approximator of graph-level functions in probability if, for all invariant functions $\phi:\mathbb{G}_{n}\to\mathbb{R}$ for a given $n\geq 1$, and $\forall\epsilon,\delta>0$, there exist choices of length $l$ of the random walk and network parameters $\theta$ such that the following holds:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-X_{\theta}(G)|<\epsilon]>1-\delta,\quad \forall G\in\mathbb{G}_{n}.$ (83) $$

We remark that a random walk neural network $X_{\theta}(\cdot)$ is composed of a random walk algorithm, a recording function $q:(v_{0}\to\cdots\to v_{l},G)\mapsto\mathbf{z}$, and a reader neural network $f_{\theta}:\mathbf{z}\mapsto\hat{\mathbf{y}}\in\mathbb{R}$.

Intuitively, if the record $\mathbf{z}$ of the random walk always provides complete information of the input graph $G$, we may invoke universal approximation of $f_{\theta}$ to always obtain $|\phi(G)-f_{\theta}(\mathbf{z})|<\epsilon$, and thus $|\phi(G)-X_{\theta}(G)|<\epsilon$.
However, this is not always true as the random walk may e.g. fail to visit some vertices of $G$, in which case the record $\mathbf{z}$ would be incomplete.
As we show below, this uncertainty leads to the probabilistic bound $>1-\delta$ of the approximation.

Let us denote the collection of all possible random walk records as $\{\mathbf{z}\}\coloneq\mathrm{Range}(q)$, and consider a decoding function $\psi:\{\mathbf{z}\}\to\mathbb{G}_{n}$ that takes the record $\mathbf{z}\coloneq q(v_{0}\to\cdots\to v_{l},G)$ of a given random walk $v_{[\cdot]}$ and outputs the graph $\psi(\mathbf{z})\in\mathbb{G}_{n}$ composed of all recorded vertices $V(H)\coloneq\{\mathrm{id}(v_{t}):v_{t}\in\{v_{0},...,v_{l}\}\}$ and all recorded edges $E(H)\subset V(H)\times V(H)$.
We show the following lemma:

###### Lemma A.6 .

Let $G_{\mathbf{z}}$ be the subgraph of $G$ whose vertices and edges are recorded by $\mathbf{z}$.
Then the graph $\psi(\mathbf{z})$ decoded from the record $\mathbf{z}$ is isomorphic to $G_{\mathbf{z}}$ through the namespace $\mathrm{id}(\cdot)$:

$$ $\displaystyle G_{\mathbf{z}}\overset{\mathrm{id}}{\simeq}\psi(\mathbf{z}).$ (84) $$

Furthermore, the decoded graph $\psi(\mathbf{z})$ reconstructs $G$ up to isomorphism, that is,

$$ $\displaystyle G\overset{\mathrm{id}}{\simeq}\psi(\mathbf{z}),$ (85) $$

if the recording function $q(\cdot)$ and the random walk $v_{[\cdot]}$ satisfies either of the following:

- •
$q(\cdot)$ uses anonymization, and $v_{[\cdot]}$ has traversed all edges of $G$.
- •
$q(\cdot)$ uses anonymization and named neighborhoods, and $v_{[\cdot]}$ has visited all vertices of $G$.

###### Proof.

Equation (84) is straightforward from the fact that the namespace $\mathrm{id}(\cdot)$ defines a bijection from $V(G_{\mathbf{z}})$ to $[|V(G_{\mathbf{z}})|]$, and the recording function uses names $\mathrm{id}(v_{t})$ to record vertices and edges.
Equation (85) is satisfied when all vertices and edges of $G$ have been recorded, i.e. $G_{\mathbf{z}}=G$, which is possible either when the random walk has traversed all edges of $G$, or when it has traversed all vertices of $G$ and named neighborhoods are used to record the induced subgraph $G[V(G)]=G$.
∎

We further remark Markov’s inequality for any nonnegative random variable $T$ and $a>0$:

$$ $\displaystyle\mathrm{Prob}[T\geq a]\leq\frac{\mathbb{E}[T]}{a}.$ (86) $$

We are now ready to prove Theorem 3.2.

###### Theorem 3.2 .

A random walk neural network $X_{\theta}(\cdot)$ with a sufficiently powerful $f_{\theta}$ is a universal approximator of graph-level functions in probability (Definition 3.1) if it satisfies either of the below:

- •
It uses anonymization to record random walks of lengths $l>C_{E}(G)/\delta$.
- •
It uses anonymization and named neighborhoods to record walks of lengths $l>C_{V}(G)/\delta$.

###### Proof.

Instead of directly approximating the target function $\phi:\mathbb{G}_{n}\to\mathbb{R}$, it is convenient to define a proxy target function on random walk records $\phi^{\prime}:\{\mathbf{z}\}\to\mathbb{R}$ where $\{\mathbf{z}\}\coloneq\mathrm{Range}(q)$ as follows:

$$ $\displaystyle\phi^{\prime}\coloneq\phi\circ\psi,$ (87) $$

where $\psi:\{\mathbf{z}\}\to\mathbb{G}_{n}$ is the decoding function of walk records.
Then, for a given $\mathbf{z}$, we have:

$$ $\displaystyle G\simeq\psi(\mathbf{z})\quad\Longrightarrow\quad\phi(G)=\phi^{ \prime}(\mathbf{z}),$ (88) $$

which is because $\phi$ is an invariant function, so $\phi(G)=\phi(\psi(\mathbf{z}))=\phi\circ\psi(\mathbf{z})=\phi^{\prime}(\mathbf
{z})$.
Then we have:

$$ $\displaystyle\mathrm{Prob}[G\simeq\psi(\mathbf{z})]\leq\mathrm{Prob}[|\phi(G)- \phi^{\prime}(\mathbf{z})|=0].$ (89) $$

We now invoke universality of $f_{\theta}$ to approximate $\phi^{\prime}$.
If $f_{\theta}$ is a universal approximator of functions on its domain $\{\mathbf{z}\}\coloneq\mathrm{Range}(q)$, for any $\epsilon>0$ there exists a choice of $\theta$ such that the below holds:

$$ $\displaystyle|\phi^{\prime}(\mathbf{z})-f_{\theta}(\mathbf{z})|<\epsilon,\quad \forall\mathbf{z}\in\mathrm{Range}(q).$ (90) $$

Combining Equations (89) and (90), we have:

$$ $\displaystyle\mathrm{Prob}[G\simeq\psi(\mathbf{z})]\leq\mathrm{Prob}[|\phi(G)- \phi^{\prime}(\mathbf{z})|+|\phi^{\prime}(\mathbf{z})-f_{\theta}(\mathbf{z})|< \epsilon].$ (91) $$

We remark triangle inequality of distances on $\mathbb{R}$, for a given $\mathbf{z}$:

$$ $\displaystyle|\phi(G)-f_{\theta}(\mathbf{z})|\leq|\phi(G)-\phi^{\prime}( \mathbf{z})|+|\phi^{\prime}(\mathbf{z})-f_{\theta}(\mathbf{z})|,$ (92) $$

which implies, for a given $\mathbf{z}$:

$$ $\displaystyle|\phi(G)-\phi^{\prime}(\mathbf{z})|+|\phi^{\prime}(\mathbf{z})-f_ {\theta}(\mathbf{z})|<\epsilon\quad\Longrightarrow\quad|\phi(G)-f_{\theta}( \mathbf{z})|<\epsilon,$ (93) $$

and hence:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-\phi^{\prime}(\mathbf{z})|+|\phi^{\prime}( \mathbf{z})-f_{\theta}(\mathbf{z})|<\epsilon]\leq\mathrm{Prob}[|\phi(G)-f_{ \theta}(\mathbf{z})|<\epsilon].$ (94) $$

Combining Equations (91) and (94), we have:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-f_{\theta}(\mathbf{z})|<\epsilon]\geq \mathrm{Prob}[G\simeq\psi(\mathbf{z})],$ (95) $$

which can be written as follows:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-X_{\theta}(G)|<\epsilon]\geq\mathrm{Prob}[ G\simeq\psi(\mathbf{z})].$ (96) $$

We now consider the probability of the event $G\simeq\psi(\mathbf{z})$ based on Lemma A.6.
We first consider the case where the recording function $q(\cdot)$ uses anonymization.
In this case, $G\simeq\psi(\mathbf{z})$ is achieved if the random walk of length $l$ has traversed all edges of $G$.
Let $T_{E}(G,v_{0})$ be the number of steps that a random walk starting at $v_{0}$ takes until traversing all edges of $G$.
Since the edge cover time $C_{E}(G)$ is its expectation taken at the worst possible starting vertex (Equation (17)), we have the following:

$$ $\displaystyle\mathbb{E}[T_{E}(G,v_{0})]\leq C_{E}(G),\quad\forall v_{0}\in V(G),$ (97) $$

which leads to the following from Markov’s inequality (Equation (86)):

$$ $\displaystyle\mathrm{Prob}[T_{E}(G,v_{0})<l]\geq 1-\frac{\mathbb{E}[T_{E}(G)]} {l}\geq 1-\frac{C_{E}(G)}{l}.$ (98) $$

For a given random walk $v_{0}\to\cdots\to v_{l}$ and its record $\mathbf{z}$, the following holds:

$$ $\displaystyle T_{E}(G,v_{0})<l\quad\Longrightarrow\quad G\simeq\psi(\mathbf{z}),$ (99) $$

which implies the following:

$$ $\displaystyle\mathrm{Prob}[T_{E}(G,v_{0})<l]\leq\mathrm{Prob}[G\simeq\psi( \mathbf{z})].$ (100) $$

Combining Equations (96), (98), and (100), we have:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-X_{\theta}(G)|<\epsilon]\geq 1-\frac{C_{E} (G)}{l}.$ (101) $$

Therefore, for any $\delta>0$, if we choose $l>C_{E}(G)/\delta$ we would have the following:

$$ $\displaystyle\mathrm{Prob}[|\phi(G)-X_{\theta}(G)|<\epsilon]>1-\delta.$ (102) $$

This completes the proof for anonymization.
The proof is identical for the recording function that uses anonymization and named neighborhoods, except that the edge cover time is changed to the cover time $C_{V}(G)$ (Equation (16)).
This is because neighborhood recording automatically records the induced subgraph of visited vertices, thus visiting all vertices implies recording all edges, $G[V(G)]=G$.
∎

###### Definition 3.1 .

###### Lemma A.6 .

###### Proof.

###### Theorem 3.2 .

###### Proof.

#### A.4.8 Proof of Theorem 3.4 (Section 3.1 )

###### Theorem 3.4 .

A random walk neural network $X_{\theta}(\cdot)$ with a sufficiently powerful $f_{\theta}$ and any nonzero restart probability $\alpha$ or restart period $k\geq r+1$ is a universal approximator of vertex-level functions in probability (Definition 3.3) if it satisfies either of the below for all $B_{r}(v)\in\mathbb{B}_{r}$:

- •
It uses anonymization to record random walks of lengths $l>C_{E}(B_{r}(v))/\delta$.
- •
It uses anonymization and named neighborhoods to record walks of lengths $l>C_{V}(B_{r}(v))/\delta$.

###### Proof.

The proof is almost identical to Theorem 3.2, except $G\in\mathbb{G}_{n}$ are substituted by $B_{r}(v)\in\mathbb{B}_{r}$, and the decoding function $\psi:\{\mathbf{z}\}\to\mathbb{B}_{r}$ is defined to ignore all recorded vertices $\mathrm{id}(x)$ whose shortest path distance from the starting vertex $\mathrm{id}(v)=\mathrm{id}(v_{0})=1$ exceeds $r$.
The latter is necessary to restrict the range of the decoding function $\psi$ to $\mathbb{B}_{r}$.
In addition, any nonzero restart probability $\alpha$ or restart period $k\geq r+1$ is sufficient to make the cover times $C_{E}(B_{r}(v))$ and $C_{V}(B_{r}(v))$ finite (Theorem 2.5), thereby guaranteeing the existence of a finite choice of $l$.
∎

###### Theorem 3.4 .

###### Proof.

#### A.4.9 Proof of Theorem 3.5 (Section 3.2 )

###### Theorem 3.5 .

The simple random walk neural network outputs $\mathbf{h}^{(l)}\to\mathbf{x}^{\top}\boldsymbol{\pi}$ as $l\to\infty$.

###### Proof.

Since $G$ is connected and non-bipartite, the uniform random walk on it defines an ergodic Markov chain with a unique stationary distribution $\boldsymbol{\pi}$.
The limiting frequency of visits on each vertex $v$ is precisely the stationary probability $\boldsymbol{\pi}_{v}$.
Since the model reads $\mathbf{x}_{v_{0}}\to\cdots\to\mathbf{x}_{v_{l}}$ by average pooling, the output is given by weighted mean $\sum_{v}\boldsymbol{\pi}_{v}\mathbf{x}_{v}$ which is $\mathbf{x}^{\top}\boldsymbol{\pi}$.
∎

###### Theorem 3.5 .

###### Proof.

#### A.4.10 Proof of Theorem 3.6 (Section 3.2 )

###### Theorem 3.6 .

Let $\mathbf{h}_{u}^{(l)}$ be output of the simple random walk neural network queried with $u$.
Then:

$$ $\displaystyle\mathbb{E}\left[\left|\frac{\partial\mathbf{h}_{u}^{(l)}}{ \partial\mathbf{x}_{v}}\right|\right]=\frac{1}{l+1}\left[\sum_{t=0}^{l}P^{t} \right]_{uv}\to\boldsymbol{\pi}_{v}\quad\text{as}\quad l\to\infty.$ (103) $$

###### Proof.

Since the model reads $\mathbf{x}_{v_{0}}\to\cdots\to\mathbf{x}_{v_{l}}$ by average pooling, the feature Jacobian $|\partial\mathbf{h}_{u}^{(l)}/\partial\mathbf{x}_{v}|$ is given as number of visits to the vertex $v$ in the random walk $v_{0}\to\cdots\to v_{l}$ starting at $v_{0}=u$, divided by length $l+1$.
Let us denote the expected number of these visits by $J(u,v,l)$.
Let $\mathbbm{1}_{v_{t}=v}$ be the indicator function that equals $1$ if $v_{t}=v$ and 0 0 otherwise.
Then we can write $J(u,v,l)$ as:

$$ $\displaystyle J(u,v,l)$ $\displaystyle=\mathbb{E}\left[\sum_{t=0}^{l}\mathbbm{1}_{v_{t}=v}|v_{0}=u \right],$ $\displaystyle=\sum_{t=0}^{l}\mathbb{E}[\mathbbm{1}_{v_{t}=v}|v_{0}=u].$ (104) $$

We have used linearity of expectations for the second equality.
$\mathbb{E}[\mathbbm{1}_{v_{t}=v}|v_{0}=u]$ is the probability of being at $v$ at step $t$ given that the walk started at $u$.
This probability is precisely $[P^{t}]_{uv}$.
Therefore:

$$ $\displaystyle J(u,v,l)=\sum_{t=0}^{l}\left[P^{t}\right]_{uv}=\left[\sum_{t=0}^ {l}P^{t}\right]_{uv},$ (105) $$

which gives the equality in Equation (103).
Furthermore, since $G$ is connected and non-bipartite, the uniform random walk on it defines an ergodic Markov chain with a unique stationary distribution $\boldsymbol{\pi}$.
The limiting frequency of visits on vertex $v$ is precisely the stationary probability $\boldsymbol{\pi}_{v}$, which gives the convergence in Equation (103).
This completes the proof.
∎

###### Theorem 3.6 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Is there a simple intuitive reason why RWNN also outputs something based on the stationary vector in Thm 3.5?

would it be possible to include Crawl and WalkLM in Table2? As those seem to be the only two methods to compare to..

I would be very interested in graph learning performance, especially since Crawl was surprisingly good there.

Would it be possible to include SimTeG methods in Table 4? They also combine LLM and GNN, just in the opposite order. I also believe that using SimTeG features would further improve your results and make them actually SOTA. Currently the table is misleading.

Is there anything to say about cases where walks do not cover the whole graph?
soundness: 3
strengths: The whole part about random walk strategies and cover times is novel and interesting. The suggested method of compiling the walk information (including anonymization and neighborhood information) into a string to be fed into an LLM is also new, even though building upon exisitng work (this could be more explicit when describing the model).

The theoretical results seem sound too.
summary: The paper considers random-walk based techniques for graph learning. It introduces a framework splitting the random walk function, recording function (drawing features from the graph), and reader NN (actually processing those features). They then show that for invariance one needs to have it on the first two levels but not the third. In terms of expressiveness, everything that is sufficiently powerful suffices, which is again made formal. Also on the theoretical side, over-smoothing does not happen for RW-based methods. 

On the practical side, the paper combines efficient non-backtracking walks while always recording the neighborhood, outputting the result as a string which is then fed into an LLM. This architecture works very well for oversmoothing, over-squashing, isomorphism learning and node classification.
weaknesses: A lot of the theory has been implicitly used e.g. in CraWl, e.g. by using 1D CNNs as reader NN. Also the anonymization and neighborhood recording is already done there (with the difference that it outputs a matrix instead of a string). Also there is quite a bit of literature on anonymization and e.g. that anonymization alone is enough to recover the graph which I would have expected to be discussed in that context.

The expressive power section is quite lengthy while not saying much - by now we should all know that there are universal function approximators so if no information is lost during preprocessing (message passing or random walks), any such model is universal. While writing down the exact details on what it means to be universal/expressive, I consider most of section 3.1 entirely unsurprising and somewhat trivial. 

There should definitely be more experiments. Currently the experiments cover two types of toy datasets and one real-world one. Graph classification that the main competitor Crawl exclusively covers is left out in the real-world setting which is odd and I believe should be added. Also having more than one node-classification dataset would be nice.

Code is unavailable. This makes reproducing the results a lot harder (even though the description of walks and feature extraction is detailed, the exact use of the LLM and the finetuning procedures are not well-enough described to confidently repeat the experiments).

Details: 
- Grammar/Structure in 87ff is off. especially: "given that..." and "The result also..."
- Table 3/4: maybe just put the link to the reference on the method name to avoid the cluttered look of the table.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Can you include results on real-world graph-level datasets? I think only evaluating graph-level synthetic datasets is a bit restrictive.

2. What is the impact of voting in the node-level task? I think the fact that you need to average across multiple voters reflects the difference between invariance and probabilistic invariance.
soundness: 2
strengths: The problem is interesting, and using llms to process outputs from the recording function makes the results more practical and significant.
summary: The paper revisits the usage of random walks for learning on graphs. In particular, they consider the setting where the model consists of three components: a random walk algorithm, a recording function producing a machine-readable record of the random walk, and a reader neural network that processes the record and produces an output. The authors show that probabilistic invariance can be achieved by requiring invariance conditions on the random walk algorithm and the recording function. They also show connections with over-smoothing and over-squashing.
weaknesses: The readability of the paper can be improved. The paper is quite dense and has many theoretical results, while the experiments appear only at the end. Perhaps move the corresponding experiments closer to the relative sections would improve readability.

Generally speaking, I find it confusing that the authors emphasize the invariance of the random walk algorithm, while instead this is a probabilistic invariance, that is, an invariance of the distribution. While the authors discuss that they accept the probabilistic notion of invariance (eq. 2), they sometimes only refer to it as invariance (eq. 3). I think this point should be better clarified throughout the paper. Moreover, since it is well known that one can average over all random walks to obtain the invariance of permutations (Srinivasan and Ribeiro, 2020), I encourage the authors to connect the probabilistic invariance to the notion of invariance more commonly used in graph learning.


Srinivasan and Ribeiro, 2020. On the Equivalence between Positional Node Embeddings and Structural Graph Representations.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: * What is the inference cost for RWNN-Llama in section 5.3? How does it compare to inductive GNN-based approaches?
* How are the results in section 5.2 and 5.3 affected by the choice of random walks? Would uniform random walks with or without backtracking yield significant performance differences on the downstream tasks? 
* What walk length and restart probabilities are used in sections 5.2 and 5.3?
* Why is a DeBERTa model that was pretrained on natural language used in the experiments for isomorphism learning? The used walk records do not resemble written language and it is not clear which information learned during language pretaining is useful here. Is there a significant benefit to using this model as opposed to a randomly initialized one?
soundness: 3
strengths: * The work provides multiple novel theoretical insights on random-walk-based GNNs and a general framework for modeling and studying such approaches further.
* Applying pre-trained language models to text-based representations of random walks to perform in-context learning is a novel idea, and the presented results seem promising.
summary: The paper introduces RWNNs as a unified framework of graph learning approaches that sample random walks from an input graph and then process a suitable representation of those walks with a reader neural network. This general concept covers a range of recent approaches.

The work provides a theoretical analysis of sufficient conditions on the walks and walk records that ensure permutation invariance regardless of the choice of the reader architecture. The paper further proves that RWNNs are probabilistically universal if the random walks are sufficiently likely to cover a graph and that RWNNs inherently avoid the phenomenon of over-smoothing.

An empirical study further studies how RWNNs with transformer-based reader functions perform on various tasks. Here, a training-free approach that passes a text-based walk representation to a Llama model is explored to solve classification tasks in citation networks with in-context learning. The overall performance of this method is reported to be competitive.
weaknesses: While I think the theoretical contributions are significant, I think the experiment section lacks some details that would improve the paper:

* What is the runtime of the compared methods during inference? While the RWNN-Llama model requires no training, I would expect its computational cost during inference to be substantially larger than that of a standard GNN. This by itself is not a problem as LLMs are expected to be costly, and RWNN also allows for more efficient choices for the reader model. However, this tradeoff should be discussed more clearly, and providing some runtime measurements would be very helpful to the reader.

* The cover time of different walk distributions is examined in section 5.1. However, no further comparison of different walks on the predictive tasks of 5.2 or 5.3 is performed. It is therefore not clear whether or not the difference in cover time translates to a significant difference in downstream tasks in practice.

*  The main walk hyperparameters (length and restart probability) are not specified in Sections 5.2 and 5.3.

There are also some grammatical mistakes that would benefit from a spell checker.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: These are mostly related to typos and requests for modification
  - Line  34: the authors cannot make a general claim that all GNNs are less expressive than 1-WL. The statement should be probably massaged to consider this
  - Line 53: should it be “Addressing such questions is important”?
  - Table 1: the authors claim that in principle the Reader NN of RWNN can be any universal function. I believe this might be true for many other methods the authors listed in the table. In light of this, I would suggest that the authors maintain consistency and replace “Any universal” with “Language Model”, since they have not shown how to combine RW+Neighbor Information records with models different from language models
  - Theorems 2.1, 2.2, 2.3 formalize rather intuitive concepts, and the proofs are mostly about stating the definition of invariance. Maybe the authors could “downgrade” them to Propositions to inform the reader that some results have more relevance than others?
  - Lines 347-349: recent architectures such as [1] show that it is possible to modify the computation over the topology to control oversmoothing and oversquashing, and these two concepts are not as entangled to the original topology and related to each other anymore. Perhaps the authors would like to rephrase their statement in light of this? [1] Errica F., et al. "Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching." arXiv preprint arXiv:2312.16560 (2023).
  - Figure 3: what are colors and lines? The authors should improve the figure a bit by adding a legend.
soundness: 3
strengths: This is one, if not the most, beautiful papers I have reviewed, and as such it deserves one of the most positive reviews I have ever written. The scope is well defined, the presentation is excellent and overall it is a pleasure to read. Coming from the GNN field, I found the connection of RWs and oversmoothing etc problems extremely fascinating. 

Intuitive ideas have been well formalized into theorems (most of which seem ok, although I did not check all proofs carefully due to time shortage), some of which (Th. 3.2 and 3.4) are especially important to convince the GNN expressiveness community that it might be time to move beyond the WL-test arguments. The integration of GNNs and RWs seems a promising research direction in the future and this paper inspired me to think about it.

The empirical results support all theoretical findings (Figure 3 might be improved) and show some strong performance on discriminating regular graphs. The transformer architecture, and especially self-attention, seems to me a particularly adequate architecture for the tasks of Table 2, but it would be interesting to see how a simple MLP performs on top of the random walk features.

The authors also took care of efficiently implementing the core of their method so as to speed up the computation of random walks.
summary: The paper delivers a well-structured analysis, both theoretical and empirical, of the potential of random walk approaches as feature extractors for subsequent neural networks. The contribution is relevant both as a summary of previous random walk-based approaches and as a theoretical connection to the problems of oversmoothing, oversquashing, and underreaching. The paper first discusses the requirements for a random-walk feature extractor to be invariant to graph isomorphism, and later it shows that invariant random walks extractors can discriminate, in probability, any two graphs provided a sufficient length of the random walk is used. Random walks neural networks do not suffer from oversmoothing and the oversquashing is intimately related to probabilistic under-reaching (whereas in MPNNs one knows exactly how many steps are needed to reach a node).
weaknesses: These are mostly suggestions for improvement, as there are no particular concerns on this reviewer’s side. One suggestion for the authors is to discuss more explicitly the empirical tasks, such as the one of Table 2; what is the target to be predicted? It is not enough to mention the relevant paper in this case, and the reader might get lost. Also, more details about the empirical procedure, such as hyper-parameters tried and model-selection/risk-assessment procedures, might contribute to improve replicability of the experiments.

I would also suggest to define the meaning of the symbols =d (define precisely what  means equal in probability) and ~ (the isomorphism relation). The authors use them a lot in the paper and they should be properly defined.

Another point that would need clarification is to specify how one can deal with named neighborhoods outside of the textual representation of the record. The authors could clarify possible options and hopefully run a demonstrative example, with an MLP for instance, in place of a language model.

In terms of experiments, I believe the authors might be trying to position RWNN-Llama3 too positively with respect to the literature. It is well-known that GraphSAGE, one of the simplest GNNs, already achieves 77% test accuracy on the ogbn-arxiv leaderboard. A proper model-selection was enough to significantly improve the original scores of the paper. So, while the paper deserves acceptance, it would do a service to the community to highlight this fact.

Meta-review: The paper proposes a generic random walk-based framework for graph learning that combines random walks, a recording function, and a reader neural network (e.g., a pre-trained language model). The authors derive theoretical results on probabilistic invariance and universality, and show how their method can avoid oversmoothing and oversquashing under specific configurations. The discussion on cover times is interesting. The empirical results look promising, but the breath of the evaluation is limited (primarily synthetic and a few real-world datasets).

Decision: Accept (Spotlight)