Revisiting Random Walks for Learning on Graphs
Authors: Jinwoo Kim
Olga Zaghen
Ayhan Suleymanzade
Youngmin Ryou
Seunghoon Hong
Venue: ICLR 2025 Spotlight (2025)
Keywords: Graph machine learning
random walk
invariance
universal approximation
markov chain
Primary area: learning on graphs and other geometries & topologies
TL;DR: From the perspectives of invariance and universality, we revisit a simple idea where a random walk on a graph produces a machine-readable record which is processed by a deep neural network to directly make vertex-level or graph-level predictions.

Abstract: We revisit a simple model class 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 call these stochastic machines random walk neural networks (RWNNs), and through principled analysis, 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 walks guarantees probabilistic invariance as long as the vertices are anonymized. This enables us, for example, 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 RWNNs, while over-squashing manifests as probabilistic under-reaching. We empirically demonstrate RWNNs on a range of problems, verifying our theoretical analysis and demonstrating the use of language models for separating strongly regular graphs where 3-WL test fails, and transductive classification on arXiv citation network. Code is available at https://github.com/jw9730/random-walk.

Published as a conference paper at ICLR 2025
REVISITING RANDOM WALKS FOR LEARNING ON GRAPHS
Jinwoo Kim!
Olga Zaghen Ayhan Suleymanzade
Youngmin Ryou' Seunghoon Hong
KAIST University of Amsterdam
ABSTRACT
We revisit a simple model class for machine learning on graphs, where a random walk graph produces machine-readable record, and this record is processed by a deep neural network to directly make vertex-level or graph-level predictions. We call these stochastic machines random walk neural networks (RWNNs), and through principled analysis, 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 walks guarantees probabilistic invariance as long as the vertices are anonymized. This enables us, for example, record random walks in plain text and adopt 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 RW NNs, while over-squashing manifests demonstrate RWNNs on a range of problems, verifying our theoretical analysis and demonstrating the use of language models for separating strongly regular graphs where 3- 3-WL test fails, and transductive classification on arXiv citation network[]
probabilistic under-reaching. We empirically
INTRODUCTION
Message passing neural networks (MPNNs) are a popular class of neural networks on graphs where each vertex keeps feature vector and updates it by propagating messages over neighbors (Battaglia jet al.) 2018). MPNNs have achieved success, with one reason being their respect for the natural symmetries of graph problems (i.e., invariance graph isomorphism) (Chen et al., 2019). On the other hand, MPNNs in their basic form can be viewed as implementing color updates of the Weisfeiler- Lehman (1-WI. graph isomorphism test, and thus their expressive power is not stronger (Xu et al.) 2019). Also, their inner workings are often tied to the topology of the input graph. which is related to over-smoothing, over-squahhin, and under-reaching of features under mixing (Giraldo et al. (023).
In this work, we revisit an alternative direction for learning on graphs, where a random walk on graph produces a machine-readade record, and this record processed by a deep neural network that directly makes graph-level or vertex-level predictions. We refer to these stochastic machines as random walk neural networks (RWNNs). Pioneering works were done in this direction, often motivated by the compatibility of random walks with sequence learning methods. Examples include DeepWalk (Perozzi et al. 2014) and node2vee (Grover & Leskovec| (2166), which use skip-gram on walks, AWE [Ivanov & Burnaev 2018). which uses embeddings of anonymized walks (Micali & Zhu 2016), and CRaWI (Tönhooff et al. 2023), which uses ID CNNs on sliding window descriptions of walks. These methods were proven powerful in various contexts, such as graph isomorphism learning that requires expressive powers surpassing 1-WL test (Tönshoff et al. 2023
Martinkus et al. (023).
Despite the potential, unlike MPNNs, have not yet reached good principled understanding of RWNNs. First, from the viewpoint of geometric deep learning, it is unclear how we can system- atically incorporate the symmetries of graph problems into RWNNs, as their neural networks not necessarily isomorphism invariant. Second, the upper bound of their expressive power, along with the requirements on each component to reach it, is not clearly known. Third, whether and how the over-smoothing and over-squashing problems may occur in RWNNs is not well understood. Addressing these questions would improve our understanding of the existing methods and potentially allow us to design enhanced RWNNs by short-circuiting the search in their large design space.
'These authors contributed equally.
I Work done during an internship at School of Computing, KAIST.
Code is available at at/httss: i thub. com wtt.c/ow//www//oooooo / www.://wanddddaaamaaamm

---

Published as a conference paper at ICLR 2025
Table I: An overview of prior methods in the context of RWNNS and new components originating from our analysis. NB is non-backtracking; MDLR is minimum degree local rule (Section
Method
Random walk
Recording function y
Reader NN fo
DeepWalk
Uniform
Identity
Skip-gram
node2vec
Second-order conerr pq-walk
Identity
Skip-gram
AWE
Uniform
Anonymization
Embedding table
CRaWl
Uniform NB
Sliding window
ID CNN
KW-AgentNet
Uniform
Neighborhoods
RNN
WalkLM
Uniform
Text attributes
Language model
MDLR (+ NB) (
Anonymization 2.1
Ours
3
restarts) 2.2
named neighbors) 2.1
Any universal ( 3.1
"1-2-3-1-4-2"
"a chordal 4 4-cycle"
Figure I: An RWNN that reads text record using a language model.
Contributions We aim to establish principled understanding of RWNNs with focus on the previously stated questions. Our starting point a new formalization of RWNNs which decouples random walks, their records, and neural networks that process them. This abstracts wide range of design choices including those of prior methods, as in Table Our key idea for the analysis is then understand RWNNs through combination of two recent perspectives in geometric deep learning: probabilistic notions of invariance and expressive power (Bloem-Reddy & Tch 2020 Abboud et al.
2021), and invariant projection of non-invariant neural networks (Puny al. 2022 Dym et al. 2024).
This idea allows us to impose probabilistic invariance on RWNNs even if their neural networks lack symmetry, by instead requiring (probabilistic) invariance conditions on random walks and their records. This provides a justification for the anonymized recording of walks (Micali & Zhu 2016) and our novel extension of using named neighbors. As long as probabilistic invariance holds, this also enables recording walks in plain text and adopting a language model to process them (Figure I
We then upper-bound the expressive power of RWNNs as universal approximation in probability which surpasses the WL hierarchy of MPNNs, under the condition that random walk records the graph of interest with a high probability. This establishes a useful link to cover times of Markov chains, providing guidance
designing random walks to minimize or bound the cover times. From this we motivate a novel adaptation of minimum degree local rule (MDLR) walks (David & Feige 2018) for RWNNs, and introduce restarts when working a large and possibly infinite graph. We also provide a justification for the widespread use of non-backtracking (Tönshoff et al. 2023).
Continuing the link Markov chain theory, we further analyze RWNNs and establish parallelism to a linearized model of MPNNs. From this, we show that over-smoothing in MPNNs inherently avoided in RWNNs, while over-squashing manifests as probabilistic under-reaching. This eliminates the typical trade-off' between over-smoothing and over-squashing in MPNNs (Giraldo et al. 2023 Nguyen et al. 2023), and allows an RWNN focus on overcoming under-reaching by scaling the walk length or using rapidly-mixine random walks such as non- backtrakkkck walks.
We empirically demonstrate RWNNs on several graph problems. On synthetic setups, optionally with a small 1-layer transformer, we verify our claims on cover times, over-smoo,,ing, and over- squashing. Then, we demonstrate adapting language model (DeBERTa (He et al.. (02T)) to solve the challenging task of isomorphism learning of strongly regular graphs with perfect accuracy whereas the 3-WL test fails, improving over the previously known best result of RWNNs. We further suggest that our approach can turn transductive classification problem learning problem by recording labeled vertices during random walks. To demonstrate this, we apply Llama 3 (Dubey et al. (2024) model transductive classification arXiv citation network with 170k vertices, and show that it can outperform a range of MPNNs as well as zero- and few-shot baselines. Our experiments show the utility of our approach in the analysis and development of RWNNs.
large graph into in-context
2

---

Published as a conference paper at ICLR 2025
2 RANDOM WALK NEURAL NETWORKS
We start our discussion by formalizing random walk neural networks (RWNNs). We define an RWNN as randomized function (-)-) that takes graph G as input and outputs random variable (G) on the output space IR In the case of vertex-level tasks, it is additionally queried with an input vertex which gives random variable Xo(G, v). An RWNN consists of the following components:
ey on the input 1. Random walk algorithm that produces I steps of vertex transitions Up - graph G. If an input vertex v is given, we fix the starting vertex by v.
2. Recording function q (VD + ... - 2/, G) + z that produces a muchine-readablle record z of the random walk. It may access the graph G to record auxiliary information such as attributes.
3. Reader neural network fo 1 2 + ý that processes record z and outputs a prediction y in Rd is the only trainable component and is not restricted to specific architectures.
For graph-level prediction, we sample ý ~ (G) by running a random walk on G and processing its record using the reader NN fe. For vertex-level prediction y ~ Xo (G( v), we query the input vertex v by simply starting the walk from it. In practice, we ensemble several sampled predictions e.g. by averaging, which can be understood as Monte Carlo estimation of the mean predictor (+) + (()
We now analyze each component for graph-level tasks on finite graphs, and then vertex-level tasks on possibly infinite graphs. The latter simulates the problem of scaling to large graphs such in transductive classification. As our definition captures many known designs (Table []. we discuss them as well. We leave the pseudocode in Appendix A.2 and notations and proofs in Appendix A.9
2.1 GRAPH-LEVEL TASKS
Let G be the class of undirected, connected, and simple graph Let n 2 1 and C, be the collection of graphs in G with most n vertices. Our goal is model a graph-level function Φ Cn + Rd using an RWNN Xo(-). Since o is graph function, it is reasonable to assume isomorphism invariance:
((G) = (HH), YG H,
Incorporating the invariance structure to our model class Xe(() would offer generalization benefit. As X-(-) is randomized, we accept the probabilistic notion of invariance (Bloem- Reoeem-Redyy & Teh 2020
(G) d Xo(H), VG H.
An intuitive justification is that, if X-()) is invariant in probability, its mean predictor (-) + E[Xo(-) would be an invariant function (we leave further discussion in Section 4 We now claim that we can achieve probabilistic invariance of Xo(-) by properly choosing the random walk algorithm and recording function while not imposing any constraint on the reader NN fe.
Proposition 2.1. Xo(.) is invariant in probability, if its random walk algorithm is invariant in probability and its recording function is invariant.
In other words, even if fo lacks symmetry, invariant random walk and recording function provably converts into an invariant random variable Xo(.). This is an extension of invariant projection operators functions (Puny et al. 2022 Dym et al. 2024) to more general and probabilistie setup.
Random walk algorithm
random walk algorithm invariant in probability if it satisfies:
<(v)) +
7 (vr) 4 un + ut; VG & H,
where 2I is random walk on G, ut] is random walk on H, and V(G) - VHH specifies the isomorphism from G to H. It turns out that many random walk algorithms literature are already invariant. To see this, let us write the probability of walking from vertex to its neighbor x E NN)):
CG ca(u, x))
Prob/u, = x u] = EnEN(w) (a cc(u,y)
(4)
where the function co : EEG) - R assigns positive weights (conductances) to edges. If we set (.)+ = 1, we recover uniform random walk used in DeepWalk (Perozzi et al. 2014). We show:
'hile any output type such as text is possible (Figure we explain with vector output for simplicity. We assume this for simplicity but extending directed attributed graphs possible.
3

---

Published as a conference paper at ICLR 2025
Proposition 2.2. The random walk in Equation 4 is invariant in probability if its conductance cn)(t) is invariant:
calu, v) ch (T((1) (()), VG - H.
(5)
includes constant conductance, and any choice that only uses degrees of endpoints deg(u), deg(w).
We favor using degrees since it is cheap while potentially improving the behaviors of walks. Among many possible choices, we find that the following conductance function called the minimum degree local rule (MDLR) (Abdullah et al. 2015 David & Feige 2018) is particularly useful:
co(u,) v) min (dig(())()) deg(v)]
(6)
MDLR special its vertex cover time, i.e. the expected time of visiting all vertices of a graph. is (n²), optimal among first-order random walks (Equation that use degrees of endpoints.
common practice is to add bonbbacktracking property that enforces 1t++1 * 14-1 (Tönshoff et al. 2023), and we also find this beneficial. In Appendix A.. we extend Equation 3 and Proposition 2.2 to
second-order walks that include non-backtracking and node2vec walks (Grover & Leskovec, 2016).
Recording function A recording function q (Do + .... 02 G) + takes random walk and produces a machine-readable record z. We let q(,,(((GGG G) have access to the graph the walk 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 VI-] on G:
q(vo +
0y G) q + ..... II,, VG & H.
(7)
Invariance requires that q(., G) produces the same record regardless of re-indexing of vertices of G into H. For this, we have be careful in how we represent each vertex in a walk vo - + Ut as a muchine-readablle value, and which auxiliary information we record from G. For example, identity recording used in WeepWalk (Perozzi et al.] 2014) and node2vec (Grover & Leskovee! (2016) are not invariant as the result is sensitive to vertex re- re-indexing. We highlight two choices which are invariant:
Anonymization. We name each vertex in walk with unique integer, starting from U H 1 and incrementing it based on their order of discovery. For instance, a random walk a + > c + a translates to a sequence 1 + 2->3 3 1.
Anonymization + named neighbors. While applying anonymization for each vertex v in walk, we record its neighbors u N (v) if they are already named but the edge - has not been recorded yet. For instance, a walk + b + - d on a fully-connected graph translates to a sequence 1 1+22 - 3(1 - 4(1, 2), where (-) represents the named neighbors.
The pseudocode of both algorithms can be found in Appendix A.2
We now show the following:
Proposition 2.3. A recording function g (Uo -
Uz G)
+ z that uses anonymization,
optionally with named neighbors, invariant.
While anonymization was originally motivated by privacy concerns in Micali & Zhu (011)) (see also Appendix AA. Proposition 2.3 offers new justification based on invariance. Our design of recording named neighbors is novel, and is inspired by sublinear algorithms that probe previously discovered neighbors in a walk (Dasgupta al. 2014). In our context, it is useful since whenever walk visits a set of vertices S C V(G) it automatically records the entire induced subgraph G[S]. As a result, to record all edges of graph, walk only has to visit all vertices. While traversing all edges, i.e. edge cover time, is Onn²) (Zuckerman 1991) in general, it is possible to choose a walk algorithm that takes only O(n²) time to visit all n vertices. MDLR in Equation exactly achieves this.
Reader neural network A reader neural network fo z + ÿ processes the record z of the random walk and outputs a prediction ý in Rdd. As in Proposition 2.1 there no invariance constraint imposed on fo, and any neural network that accepts the recorded walks and has a sufficient expressive power can be used (we will make this precise in Section This is in contrast to MPNNs where invariance is hard-coded in feature mixing operations. Also, our record z can take any format, such as matrix, byte sequence, or plain text, as long as fo accepts it. Thus, is possible (while not required) to choose the record to be plain text, such " "1-2-3-1" ", and choose fe to be pre-trained language model. This offers expressive power (Yun et al. 2020) and has a potential benefit of knowledge transfer from the language domain (Lu et al. 2022 Rothermel et al. 2021
4

---

Published as a conference paper at ICLR 2025
2.2 VERTEX-LEVER TASKS
We now consider vertex-level tasks. In case of finite (small) graphs, we may simply frame a vertex- level task (G,v) + y as graph-level task G' + y where G' is G with its vertex v marked. Then, we can solve G' + y by querying an RWNN Xo(G,t) v) to start its walk at up =
more interesting case is when G is an infinite graph that is only locally finite, i.c. has finite degrees. This simulates problems on a large graph such as transductive classification. In this case, we may assume that our target function depends on finite local structures (Tahmasebi et al. 2023).
Let r 2 1, and B, == [b) be the collection of local balls in G of radius r centered at & E V(G). We would like to model vereex-level function á : B, + Rd on G using an RWNN Xx(:) by querying the vertex of interest, Xo(G, ((G.,)) v). We assume that ø is isomorphism invariant:
(v), ((),, VB,(u) ~ (u).
(8)
The probabilistic invariance of Xx (-) is defined as follows:
Xo(G, (o. (B, ~ (u).
(9)
We can achieve probabilistic invariance by choosing the walk algorithm and recording function similar to the graph-level case") As a modification, we query Xo(G, v) with the starting vertex vo of the random walk. Anonymization informs to the reader NN by always naming it as 1.
Then, we make a key choice of localizing random walks with restarts. That is, we reset a walk to its starting vertex uo either with probability (0, 1) at each step or periodically every & steps. Restarting walks tend to stay more around starting vertex oo and were used to implement locality bias in personalized PageRank algorithm for search (Page et al. 1999). This localizing effect is crucial in our context since a walk can drift away from B, (0o) before recording all necessary information, which may take an infinite time to return as G' is infinite (Janson & Peres 2012). Restarts make the return to do mandatory, ensuring that B, (vo) can be recorded in a finite expected time. We show:
Theorem 2.4. For a uniform random walk on an infinite graph G starting at v, the vertex and edge cover times of the finite local ball (v) are not always finitely bounded.
Theorem 2.5. In Theorem 2.4 if the random walk restarts at with any nonzero probability a or any period k 2 r 1, the vertex and edge cover times of (x(r)) are always finite.
3 ANALYSIS
In Section 2 we have described the design of RWNNs, primarily relying on the principle of (prob- abilistic) invariance. In this section, we provide in-depth analysis on their expressive power and relations to the issues in MPNNs such as over-smoothing, over-squashing, and under-reaching.
3.1 EXPRESSIVE POWER
Intuitively, the records of random walks contain enough information such that the structures of interest, c.g., graph G or local ball (v), can be fully recovered, powerful reader NN such as an MLP (Hornik et al. 1989) or a transformer (Yun et al. (0200) on these records would be able to approximate any function of interest. Our analysis formalizes this intuition.
We first consider using an RWNN Xo(.) to universally approximate graph-level functions <(-) in probability, defined in Abboud et al. (2021).
(-) is universal approximator of graph-level functions invariant functions Φ : Gn R for given n 2 and Ō there exist choices of length of the random walk and network parameters 0 such that the following holds:
Definition 3.1. X-(-)
functioos in probability if. for all
Prob]lo(G) Xo(G)) <e] > 1-8, 8, VG E G..
(10)
We show that, if the random walk is long enough and the reader NN fo is universal, RWNN Xx(+) is capable graph-level universal approximation. The length of the walk I controls the confidence 8, with edge cover time (G( or vertex cover time (v)) playing central role.
TThis is assuming that the random walks are localized in B,(x) and B, (u), e.g. with restarts.
5

---

Published as a conference paper at ICLR 2025
Theorem 3.2. An RWNN X with sufficiently powerful fo is universal approximator of functionn in probability (Definition 3.1 if it satisfies either of the below:
graph-level functions
It uses anonymization to record random walks of lengths 1 Cg(G)/8.
It uses anonymization + namedd neighbors to record walks of lengths Cv(G)/ō.
While both cover times are ( for uniform random walks (Aleliunas al. 1979. Zuckerman 1991), we can use MDLR in Equation 6 to achieve an O(n²) vertex cover time, in conjunction with named neighbors recording. While universality can be principle achieved with uniform random walks, our design reduces the worst-case length / required for the desired reliability >> 1 5.
We now show an analogous result for the universal approximation of vertex-level functions.
Definition 3.3. X-(.) is universal approximator of vertex-level functions in probability if. for all functions Φ B, - TR. for a given r 2 1, and Ve, 5 > O, there exist choices of length and restart probability a or period l of the random walk and network parameters O such that:
invariant functions
Probllo(B.(u)) - Xo(G, v) < VBr(v) Br.
(11)
Accordingly, using local vertex cover time (B,( and edge cover time CE(B,(U)), we show: Theorem 3.4. An RWNN Xx(.) with a sufficiently powerful fe and any nonzero restart probability restart period k 2 r + 1 is universal approximator vertex-level functions in probability (Definition 3.3) if it satisfies either of the below for all B, (u) E By:
It uses anonymization to record random walks of lengths 1 CB(BB
It uses anonymization + named neighbors to record walks of lengths (B,()()))
Since restarts are required finitely bound the local cover times on an infinite graph (Section 2.2). non-restarting walks cannot support vertex-level universality in general, and our design is obligatory.
3.2 OVER-SMOOTHING OVER-SQUASHING AND UNDER-REACHEE
Often, in MPNNs, each layer operates by passing features over edges and mixing them using weights deduced from e.g., adjacency matrix. This ties them to the topology of the input graph, and range of prior work has shown how this relates to the well-known issues of over soothing,, over-squashing and under-reaching. We connect RWNNs to these results to verify if similar issues may take place.
Let G be a connected non- bipartiie graph with row-normalized adjacency matrix P. We consider a linearized MPNN, where the vertex features (0) are initialized as some probability vector x, and updated by (++1) h(t) P. This simplification often useful in understanding the aforementioned
issues (Graldo et al. 2023 Zhao & Akoglu 2019). Specifically, in this model:
Over-smoothing happens as the features exponentially converge to stationary vector h() as / + oo, smoothing out the input x (Giraldo et al. 2023)
Over-squashing and under-reaching oceur when feature h becomes insensitive distant input x.. While under-reaching refers to insufficient depth < diam(G) (Barceló et al. 2020 over-squashing refers features getting overly compressed at bottlenecks G, even with
sufficient depth The latter is described by the Jacobian (bh /0x, <
as the
bound often decays exponentially with 7 (Topping et al. 2022 Black al. 2023
What do these results tell about RWNNs? We can see that, while P drives feature mixing in the message passing schema, can be also interpreted as the transition probability matrix of uniform random walk where P... is the probability of walking from to v. This parallelism motivates to design an analogous, simplified RWNN and study its behavior.
We consider simple RWNN that runs uniform random walk + + U/ reads the record Xop
X by averaging, and outputs it as (!) Like linear MPNN, the model involves / steps
"This hound obtained by applying Lemma 3.2 Black et al. 2023) linearized MPNN.

---

Published as a conference paper at ICLR 2025
of time evolution through P. However, while MPNN 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 in simple ]
Theorem 3.5. The simple RWNN outputs h - x π as as
Even if the time evolution through P happens fast (i.e. Pis rapidly mixing) or with many steps 4, the model is resistant to seothiggg as the input x always affects the output. In fact, if P is rapidly mixing, we may expect improved behaviors based on Section a. as the cover times could reduce.
On the other hand, we show that over werrshiu manifests as probabilistic under-reaching:
Theorem 3.6. Let ha be output of the simple RWNN queried with u. Then:
Th
E
pt
as
1- oc.
(12)
xx1
1+1
L==
22
The equation shows that the feature Jacobians are bounded by the sum of powers of P. same in simple MPNN. 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 (Topping et al. 2022). in RWNNs it is related to exponentially decaying probability of reaching a distant vertex v, i.c., probabilistic under-reaching.
In many MPNNs, it is understood that the topology of the input graph inevitably induces a trade-off between over- sooothit and verrsquushing (Nguyen et af. 2023 Giraldo et al., (023). Our results suggest that RWNNs avoid the trade-off, and we can focus on overcoming under-reaching e.g., with long or rapidly-mixing walks, while not worrying much about over-smoothing. Design choices such as MDLR (Equation 6 and non-backtracking (Alon et al.) (007) can be understood as achieving this.
RELATED WORK
We briefly review the related work. An extended discussion can be found in Appendix A.10
Random walks for learning on graphs In graph learning, random walks have received interest due to their compatibility with sequence learning methods [T. DeepWalk (Perozzi et al. 2014) and node2vee (Grover& & Leskovec| 2016) used skip-gram models on walks. CRaWi (Tönshoff et al.)
2023) used 1D CNN on sliding window-base walk records, with expressive power bounded by the window size. We discuss the relation between CRaWI and our approach in depth in Appendix [A. 10 AgentNet (Martinkus al. 2023) learns agents that walk on graph while recurrently updating their features. While optimizing the walk strategy, this may trade off speed as training requires recurrent roll-out of the network. Our method allows pairing simple and fast walkers, such as MDLR, with parallelizable NNs such as transformers. WalkLM (Tan et al. (2023) proposed a fine-tuning method for language models walks on text-attributed graphs. By utilizing anonymization, our approach is able to process graphs even if no text attribute is given. Lastly, a concurrent work (Wang & Cho 2024 has arrived at similar use of anonymization combined with RNNs.
Probabilistic invariant neural networks Whenever a learning problem is compatible with sym- metry, incorporating the associated invariance structure to the hypothesis class often leads to general- ization benefit (Bronstein et al. 2021 Elesedy [022] 2023). This is also the case for probabilistic invariant NNs (Lyle et al. 2020 Bloem-Redds & Tch 2020), which includes our approach. Prob- abilistic invariant NNs have recently gained interest due their potential of achieving higher expressive powers compared to deterministic counterparts (Cotta et al.) 2023 Cornish 2024). In graph learning, this is often achieved with stochastic symmetry breaking between vertices using randomized features (Loukas 2020; Puny et al. 2020 Abboud et al. 2021 Kim et al. 2022), vertex orderings (Murphy et al.) 2019) Kim et al.) (023). or dropout (Papp et al. 202T). Our approach can be understood using random walk as symmetry-breaking mechanism for probabilistic invariance, which provides an additional benefit of natural compatibility with sequence learning methods.
'While we show not forgetting x for brevity, we may extend to initial vertex to using its anonymization 1.
7

---

Published as a conference paper at ICLR 2025
Edge cover time C_E(G)
Vertex cover time C_ C_V(G)
Uniform
1200
Uniform
5000
Unifor +
Unioor NB
nove2vec
1000
node2vec
we stepp
4000
MOUR
MOUR (Durs)
MOLR
MOLR (Ours)
3000
600
2000
400
1000
3.4
16
verticas
Figure 2: Cover times of random walks on varying sizes of lollipop graphs. NB is non-backtracking.
Clique (over-smoothiin)
Barbell (oversquashing)
SAGE
SAGE
NSD
RWNN (Ours)
RIMNN (Curs)
6.10
0.10
200
400
600
8B0
1000
2.00
400
800
800
1000
Walk length
Walk length
Figure 3: Over-smoothing and over-squashing (MSE () for various walk lengths
Table 2: Over-smoothing and over-squashing results in comparison to baselines from Bamberger et al.
(024).. We report test mean squared error (MSE \) aggregated for 4 randomized runs.
Method
Clique (over-smootthnng)
Barell (over-squashing)
Baseline
30.94 0.42
30.97 = 0.42
Baseline
0199 0.08
1.00 0.07
MLP
1.10 0.08
1.08 0.07
GCN
29.65 0.34
1.05 + 0.08
SAGE
01.6 + 0.10
0,90 + 0.29
GAT
20.97
1.07
0.08 =
1.09 = 0.15
BuNN
0.03 a: 0.01
0.01 a: 0.07
RWNN- twaN--trnsformer (Ours)
0.023 0.006
0.007 0.001
EXPERIMENTS
We perform a set of experiments to demonstrate RWNNs. We implement random walks in C++ based on Chenebaux (2020), which produces good throughput (<0.1 seconds for 10k steps) without using GPUs as in Tonshoff et al. (2023); pseudocode is in Appendix A.2] We implement training and inference pipelines in Torch with NVIDIA GPUs and Intel Gaudi 2 compatibility. Supplementary
experiments and analysis can be found in the Appendix, from A.4 to A.8
5.1 SYNTHETIC EXPERIMENTS
On synthetic setups, we first verify our claims on cover times in Section 2.1 focusing on the utility of MDLR (Fquation 6), non-backtracking, and named neighbor recording.
measure the edge cover
times Ce(G)) and vertex cover times Cv (G) on varying sizes of lollipop graphs G (Feige 1995) which are commonly used to establish the upper bounds of cover times. While the strict detinition of edge cover requires traversing each edge in both directions, our measurements only require traversing
one direction, which suffices for the universality of RWNNs. The results are in Figure 2 We find that (1) MDLR achieves significant speed-up compared to uniform and node2vec walks, (2) adding non-backtracking significantly improves all first-order walks, and (3) edge cover times are often much larger than vertex cover times, strongly justifying the use of named neighbor recording (Theorem 3.2
8

---

Published as a conference paper at ICLR 2025
Table 3: Isomorphism learning results. We report accuracy of classifying training data rounded to the first decimal point. 8, t. I. S. and are from Papp et al. (2021), Murphy et al. (2019). Zhao et al. (2022)), Martinkus et al. (2023) and
et al. at. (2024). respectively.
CSL 1. 2-WL fails
SRI6
SR25 3-WL fails
Method
3-WL fails
GIN
10.0%1 100.096
50.0%S
6.7%
PPGN
50.09E$
6.7%
GIN-AK+
6. 6.7%
PPGN-AK+
100.0%
GIN
6.7%.
GIN+ELENE-L (ED)
100.0%
GIN-RNI
16.0%
GIN-KT
37.6%
GIN-Dropout
82.0%
RW-AgenNett
100.0%6
50.5%
AgeniNet
100.09-
100.0%-5
6,7%
RRww
100.0%6
100.0%8
46.6%
SWNN-DcBERTa (Ours)
100.0%
100.0%
100,0%
Then, we verify our claims in Section 3.2 using Clique and Barbell datasets of Bamberger al. (2024) that explicitly test for over-smoothing and over- wver-squashing respectively. Our RWNN uses MDLR walks with non- barkkrakkackkig and the reader NN is a 1-layer transformer encoder with width 128, matching the baselines. Figure 3 shows the results for varying walk lengths 1. The model performs well on Clique overall, while Barbell requires scaling the walk length. This agrees with our claims in Section 3.2 that RWNNs in general avoid over-smoothing, but over uver-squashing manifests as probabilistic under-reaching (and is therefore mitigated by sufficiently long walks). With / = 1000, model in Jchieves the best performance among the considered methods. More details on the experiment and additional baseline comparisons can be found in Appendix A..4
5.2 GRAPH ISOMORPHISM LEARNING
We now verify the claims on expressive power in Section 3.1 using three challenging datasets where the task is recognizing the isomorphism type of input graph where certain WI. test fails.
The Circular Skip Links (CSL) graphs dataset (Murphy et al. 2019) contains 10 non -soomorphi regular graphs with 41 vertices of degree 4. Distinguishing these graphs requires computing lengths of skip links, and 1-WL and 2- 2L tests fail. The 4 4 rook's and Shrikhande graphs (Alvarez- [Alvarez-Gonzaler et al. 2024), which we call SR16, are 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 (Balcilar)
et al. 2021) contains 15 strongly regular graphs with 25 vertices of degree 12, on which 3-WL test fails. Examples of the graphs and random walks on them can be found in Appendix A.2
Our RWNN uses MDLR walks with non-backtracking, and recording function with anonymization and named neighbors that produces plain text (Algorithm 3). We use pre-trained DeBERTa- base language model as the reader NN to leverage its capacity (see Appendix regardiin pre- me--raining), and fine-tune it with cross-entropy loss for < 100k steps using Adam optimizer with 2e-5 learning rate and 0.01 weight decay following Kim et al. (2023). We truncate the input 512 tokens due to memory constraints. We use batch size 256, and accumulate gradients for 8 steps for SR25, which we found sufficient stabilize the training. At test time, we ensemble 4 predictions by averaging logits.
The results are in Table 3, MPNNs that align with certain WL tests fail when asked to solve harder problems, e.g., GIN aligns with I-WL and fails in CSL. A limited set of the state-of-the art NNs solve SR25, but at the cost of introducing specialized structural features (Alvarez-Gonzalez et al. 2024). Alternative approaches based on stochastic symmetry-breaking. e.g., random node identification, often fail on CSL although universal approximation is possible in theory (Abboud et al. 2021). possibly due to learning difficulties. For algorithms based on walks, AgentNet and CRaWi 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 CRaWI is limited by the receptive field of the 1D CNN. Our approach based on DeBERTa language model overcomes the problems, demonstrating as the first RWNN that solves SR25.
In Appendix A.33 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 the isomorphism types.

---

Published as a conference paper at ICLR 2025
Table 4: Test accuracy on ogbn-arxiv. f denotes using validation labels for label propagation or
in-context learning following Huang al. 2020 For Llama 3, ensemble predictions by voting.
Method
Accuracy
MLP
55,50%
BuMe vec
70.07%
GCN
71.74%
SAGE
71.49%
73.91%
ReVGAT
74.26%
1 Lahe pmopaaaion
68.50%
C2S
72.62%
CCS
74.02%
1 Llama2- 2-32 zero-shot
44.23%
GP 1-333 zcro-saot
73,50%
line-Tune
74.13%
Llama3-88 3-b zero-shot
51.31%
Llama3 8b ooneshoo
52.81%
Llama3-Sb one-shoti
52.82%
Llama3 70t zero shot
65.30%
Llama3 70b one-shotf
67.65%
RWNN-LJama3-80 (Ours)
71.06%
RWNN-Llama3-80 (Ours)f
73.17%
RWNN-LLama3-700 (Ouns)
74.85 %
5.3 REAL-WORLD TRANSDUCTIVE CLASSIFICATION
Previous results considered undirected, unattributed, and relatively small graphs. We now show that RWNN based on Llama 3 (Dubey al.) (024) language models can solve real-world problem large graph with directed edges and textual attributes. We use ogbn-arxiv (Hu et al. 2220),, a citation network of 169,343 arXiv papers with title and abstract. The task is transductive classification into 40 areas such as ccs. AI" using a set of labeled vertices. Additional results are in Appendix [A.6]
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 language model embeddings and trains MPNN, the risk of over- compressing the text. To take the best of both worlds, we design the recording function so that, not only 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 ( (Sato 2024). The resulting record naturally includes number of input- frame transductive classification problem
pairs of the classification task at hand, implying that as a simple in-context learning problem (Brown et al., 2020). This allows training-free application of Llama 3 (Dubey al. 2024) language model for transductive classification. We choose restart rate = 0.7 (Section 2.2) by hyperparameter search on a 100-sample subset the validation data.
The results are in Table 4 Our models based on frozen Llama 3 perform competitively against a range of previous MPNNs on text embeddings, as well as outperforming language models that perform vertex-wise predictions ignoring graph structures such GPT-3.5 and fine-tuned DeBERTa. Especially, 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, 31.13 in average, due to other recorded information. This is presumably since the record produced by our algorithm informs useful graph structure to the language model quickly learn the task in-context compared to randomly chosen shots. In Appendix A..3 we visualize the attention weights, verifying that the model makes use of the graph structure recorded by random walks make predictions.
As final note, our approach is related to label propagation algorithms (Zhu & Ghahramani 2002 Zhu (2055] Grady 2006) 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 NN i.e. the 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 4 our approach outperforms label propagation, verifying our intuition.
6 CONCLUSION
We contributed a principled understanding of RWNNs, where random walks on graphs are recorded and processed by NNs to make predictions. We analyzed invariance, expressive power, and in- formation propagation, showing that we can design RWNNs to invariant and universal without constraining its neural network. Experiments support the utility of approach.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was in part supported by the National Research Foundation of Korea (RS-2024-00351222 and Evaluation (IITP)
the Institute of Information & communications Technology Planning & 10--022--1122200 1228, RS-2022-11220955 and ESS-2019-I11 11119990775) funded by the Korea government (MSIT), Artificial intelligence industrial convergence cluster development project funded by the Korea government (MSIT) & Gwangju Metropolitan City, and NAVER-Indr Co-Lab. We would like to thank Zeyuan Allen-Zhr for helpful discussion regarding anonymous random walks.
DS-2024-00509277,
REFERENCES
Ralph Abboud, Ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. IJCAI, 2021. (pages
Mohammed Abdullah. The cover time of random walks on graphs. arXiv, 2012. (page 50
Mohammed Amin Abdullah, Colin Cooper, and Moez Draief. Speeding up cover time of sparse graphs using local knowledge. In IWOCA, 2015. (pages 4 50)
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Annual Symposium
on Foundations of Computer Science, 1979. (pages 6 45 50
Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 2007. (pages T8 50)
Nurudin Alvarez- Grnzzz-Gonzzaez. Andreas Kaltenbrunner, and Vicenç Gómez. Improving subgraph-GNI via edge-level ego- geg-ore encodings. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. (page 9
Francesca Arrigo, Desmond J. Higham, and Vanni Noferini. Non-backtracking pagerank. J. Sci. Comput., 2019. (page (50)
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In ICMI, 2021. (page
Jacob Bamberger, Federico Barbero, Xiaowen Dong, and Michael Bronstein. Bundle neural networks for message diffusion graphs. arXiv, 2024. (pages 8 9 31)
Pablo Barceló, Egor Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva.
The logical expressiveness of graph neural networks. In ICLR, 2020. (pages 6 50
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Gonzalzz Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülççhhee, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew M. Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv, 2018. (page)
Anna Ben- Ham-H, Roberto I. Oliveira, and Yuval Peres. Estimating graph parameters via random walks with restarts. In Annual ACM-SIAM Symposium on Discrete Algorithms, 2018. (pages 50
51
Itai Benjamini, Gady Kozma, Laszlo Lovasz, Dan Romik, and Gabor Tardos. Waiting for a bat to fly by (in polynomial time). Combinatorics, Probability and Computing, 2006. (page
Suman Bera and C Seshadhri. How to count triangles, without seeing the whole graph. In KDD, 2020. (pages 50 51)
Mitchell Black, Zhengehao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In ICMI., 2023. (pages 50
11

---

Published as a conference paper at ICLR 2025
Benjamin Gloem-Reddye and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. Mach. Learn. Res., 2020. (pages
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. arXiv, 2021. (page
Bradley C. A. Brown, Jordan Juravsky, Ryan Saul Ehrlich, Ronald Clark, Quoe V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv, 2024. (page 35
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herhert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In NeurIPS, 2020. (page
10
Eric Richard Bussian. Bounding the edge cover time of random walks on graphs. Georgia Institute of Technology, 1996. (page 50)
Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. (page 34
carnage. Expected hitting time for simple random walk from origin point (x.y) in 2d-integer- grid. MathOverflow, 2012. URL httpps://///. /Rt htwp:///wwwww.eeeettee/eeeiioooe
net
[Online:] https: http:://mmaahheetteeeee
(page
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times. Comput. Complex., 1997. (page 50)
Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. arXiv, 2024a. (pages 32 33)
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NeurIPS, 2019. (page D
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In NeurlPS, 2020. (page 34)
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, and Jiliang Tang. Exploring the potential of large language models (Ilms)in learning on graphs. SIGKDD Explor. 2023. (page 51
Zhikai Chen, Haitao Mao, Jingzhe Liu, Yu Song, Bingheng Li, Wei Jin, Bahare Fatemi, Anton Tsitsulin, Bryan Perozzi, Hui Liu, and Jiliang Tang. Text-space graph foundation models: Compre- hensive benchmarks and new insights. arXiv, 2024b. (pages 32 33)
Maixent Chenebaux, graph- Fastest random walks generator on networkx graphs. https www.aaw...oo.kkiigaaaaaaa hawprrrihhhhaagaaaaaaaaeeeee 2020. (page 8
Flavio Chiericetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi, and Tamás Sarlós. On sampling nodes in a network. In WWW, 2016. (page 50)
Don Coppersmith, Uriel Feige, and James B. Shearer. Random walks on regular and irregular graphs. SIAM J. Discret. Math., 1996. (5)
Rob Cornish. Stochastic neural network symmetrisation in markov categories. arXiv, 2024. (page 7
Leonardo Cotta, Gal Yehuda, Assaf Schuster, and Chris J. Maddison. Probabilistic invariant learning with randomized linear classifiers. In NeurlPS, 2023. (pages ((55)
George Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control. Signals Syst. 1989.
12

---

Published as a conference paper at ICLR 2025
Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. On estimating the average degree. In wwW, 2014. (pages 50))
Roee David and Uriel Feige. Random walks with the minimum degree local rule have o(n2) cover time. SIAM J. Comput., 2018. (pages 2 50)
Artur Back de Luca and Kimon Fountoulakis. Simulation of graph algorithms with looped transform- ers. arXiv, 2024. (page 51)
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. In ICLR, 2023. (page[5]]
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms. In NeurlPS, 2023. (page 33)
Karel Devriendt and Renaud Lambiotte. Discrete curvature graphs from the effective resistance. Journal of Physics: Complexity, 2022. (page 50)
Jian Ding, James R Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. In
Annual ACM symposium Theory of computing, 2011. (page 50
Peter G Doyle and J Laurie Snell. Random walks and electric networks. American Mathematical Soc., 1984. (page (5)
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurélien Rodriguez, Austen Gregerson. Ava Spataru, Baptiste Rozière, Bethany Biron, Binh Tang, Bobbie Chern, and et al. The llama 3 herd models. arXiv, abs/2407.21783, 2024. (pages 10
Ioana Dumitriu, Prasad Tetali, and Peter Winkler. On playing golf with two balls. SIAM J. Discret. Math., 2003. (pages 41 50)
Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In NewrIPS, 2022. (page 33
Nadav Dym, Hannah Lawrence, and Jonathan W. Siegel. Equivariant frames and the impossibility of continuous canonicalization. In ICML, 2024. (pages
Bryn Elesedy. Group symmetry in pac learning. In ICLR workshop on geometrical and topological representation learning, 2022. (page
Bryn Elesedy. Symmetry and Generalisation in Machine Learning. PhD thesis, University of Oxford, 2023. (page 7
Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, and Francesco Alesiani. Adaptive message passing: A general framework mitigate oversmoothing, oversquashing, and underreaching. arXiv, 2023. (page(50)
William Falcon. Pytorch lightning. 2019.
Dario Fasino, Arianna Tonetto, and Francesco Tudisco. Hitting times for non-backtracking random walks. arXiv, 2021. (page 50)
Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv, 2023. (1)
Uriel Feige. A tight upper bound on the cover time for random walks on graphs. Random Struct. Algorithms, 1995. (pages
50
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
13

---

Published as a conference paper at ICLR 2025
Robert Fitzner and Remco van der Hofstad. Non-backtracking random walk. Journal of Statistical Physics, 2013. (pagel (8)
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019. (page
Agelos Georgakopoulos and Peter Winkler. New bounds for edge-cover by random walk. Comb. Probab. Comput., 2014. (page 50
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Francesco Di Giovanni, T. Konstantin Rusch, Michael M. Bronstein, Andreea Deac, Marc Lackenby, Siddhartha Mishra, and Petar Velickovic. How does over-squashing affect the power of gnns? arXiv, 2023. (page 50)
Jhony Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos Malliaros. On the trade-off between over wvorshno and over-squashing in deep graph neural networks. In CIKM, 2023. (pages
50
Leo J. Grady, Random walks for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 2006.
(pages 10 50)
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, 2016. (pages
18 39
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: decoding-enhancel bert with disentangled attention. In ICLR, 2021. (page 2
Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. Harness- ing explanations: Lim-to-Im interpreter for enhanced eext-attributed graph representation learning. In ICLR, 2023.
Jeffery Hein. Wald's identity. (page 43)
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 1989. (page 5)
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang. and Weizhu Chen. Lora: Low-rank adaptation of large language models. In ICLR, 2022. (page 33
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020. (page 10)
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out out-performs graph neural networks. arXiv. 2020. (page I0)
Satoshi Ikeda, Izumi Kubo, and Masafumi Yamashita. The hitting and cover times of random walks on finite graphs using local degree information. Theor. Comput. Sci., 2009. (page
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In ICML, 2018. (page)
Svante Janson and Yuval Peres. Hitting times for random walks with restarts. SIAM J. Discret. Math., 2012. (pages
50
Jeff D Kahn, Nathan Linial, Noam Nisan, and Michael E Saks, On the cover time of random walks on graphs. Journal of Theoretical Probability, 1989. (page (5))
Mark Kempton. Non-backtracking random walks and a weighted ihara's 's theorem. arXiv, 2016. (page
50
14

---

Published as a conference paper at ICLR 2025
Jinwoo Kim, Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. In NeurlPS, 2022. (pagel
Jinwoo Kim, Dat Nguyen, Ayhan Suleymanzade, Hyeokjun An, and Seunghoon Hong. Learning probabilistic symmetrization for architecture agnostic equivariance. In NeurIPS, 2023. (pages 7
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017. 2017.
Filip Klubicka, Alfredo Maldonado, Abhijit Mahalunkar, and John D. Kelleher. Synthetic, yet natural: Properties of wordnet random walk corpora and the impact of rare words on embedding performance. In GWC, 2019. (page ST
Filip Klubicka, Alfredo Maldonado, Abhijit Mahalunkar, and John D. Kelleher. English wordnet random walk pseudo-corpora. In IRECC, 2020. (page 51)
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Hao Liu, Jiarui Feng. Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training graph model for all classification tasks. In ICLR, 2024. (pages
33
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICLR, 2019.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In ICLR, 2020. (page
László Lovász. Random walks graphs. Combinatorics,, Paul erdos is eighty, 1993. (page 50)
Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. Frozen pretrained transformers. as universal computation engines. In AAAI, 2022. (pages
32)
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. arXiv, 2020. (page 7
Karolis Martinkus, Pál András Papp. Benedikt Schesch, and Roger Wattenhofer. Agent-based graph neural networks. In ICLR, 2023. (pages) 7
Nathan McNew. Random walks with restarts, 3 examples, 2013. (pages
50
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discret. Appl. Math., 2016. (pages] 2
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Ryan I.. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. Relational pooling for graph representations. In ICML, 2019. (pages 7
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley J. Osher, and Tan Minh
Nguyen. Revisiting over-smoo and over-squashing using ollivier-ricei curvature. In ICMI., 2023. (pages 2 50)
Roberto Oliveira. Mixing and hitting times for finite markov chains, 2012. (page 50
Yann Ollivier. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis, 2009. 50)
Lawrence Page. Sergey Brin, Rajeev Motwani, Terry Winograd, et al. The pagerank citation ranking: Bringing order to the web, 1999. (pages 5 50)
Athina Panotopoulou. Bounds for edge-cover by random walks, 2013. (page 50
15

---

Published as a conference paper at ICLR 2025
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. NeurIPS, 2021. (pages 7
Seonghyun Park, Narae Ryu, Gahee Kim, Dongyeop Woo, Se- Yo-Young Yun, and Sungsoo Ahn. Non- backtracking graph neural networks. In NeurIPS Workshop: New Frontiers Graph Learning, 2023. (page 50
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. NeurlPS, 2019.
Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. Journal of Theoretical Probability, 2015. (page 50)
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In KDD, 2014. (pages
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characterizing graph datasets for node classification: Homophily--heterophiy dichotomy and beyond. In NeurIPS, 2023a. (page 35)
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv, 2023b. (pages 32 33)
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks general- ization. arXiv, 2020. (page 7
Omri Puny, Matan Atzmon, Edward J. Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In ICLR, 2022. (pages
Brian Rappaport, Anuththari Gamage, and Shuchin Aeron. Faster clustering via con-backtracking random walks. arXiv, 2017. (pagel
Danielle Rothermel, Margaret Li, Tim Rocktäschel, and Jakob Foerster. Don't sweep your learning rate under the rug: A closer look at cross-modal transfer of pretrained transformers. arXiv, 2021.
(pages 32)
Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv, 2024. (page 51)
Ryoma Sato. Training-fres free graph neural networks and the power of labels as features. arXiv, 2024.
(pages 10 32 33
Yuval Sieradzki, Nitzan Hodos, Gal Yehuda, and Assaf Schuster. Coin flipping neural networks, In ICML, 2022. (page 35)
Daniel Spielman. Spectral and algebraic graph theory. Yale lecture notes, draft of December, 2019. (page 50
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The power of recursion in graph neural networks for counting substructures. In AISTATS, 2023. (page 5)
Yanchao Tan, Zihao Zhou, Hang Lv, Weiming Liu, and Carl Yang. Walklm: A uniform language model fine-tuning framework for attributed graph embedding. In NeurIPS, 2023. (pages 7 731
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions on Machine Learning Research, 2023. (pages
50
16

---

Published as a conference paper at ICLR 2025
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassessing the long-range graph benchmark. Trans. Mach. Learn. Res., 2024, 2024. (page 33
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. In ICLR, 2022.
(pages
50
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In Neur/PS, 2023. (page
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, al. Deep graph library: : A graph-centric, nighly-performant package for graph neural networks. arXiv,, 2019. (page 51)
Yuanqing Wang and Kyunghyun Cho. Non-convolutional graph neural networks. arXiv, 2024. (page
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Marina Meila and Tong Zhang (eds.), ICML, 2021. (page
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi,
Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's transformers: State-of-the-art natural language processing. arXiv, 2019.
Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention- based graph neural networks. In NeurlPS, 2023. (pages 50 51)
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019. (page
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), 2022. (page 33)
Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Language is all graph needs. In Findings of EACL, 2024. (page 51)
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-seegee to-seuuenc functions? In ICLR, 2020. (pages
5)
Bohang Zhang, Jingehu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for gnn expressiveness. arXiv, 2024. (page
Jianan Zhao, Meng Qu, Chaozhuo Li, Hao Yan, Qian Liu, Rui Li, Xing Xie, and Jian Tang. Learning on large-scale text-attributed graphs via variational inference. arXiv, 2022a.
Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael M. Bronstein, Zhaocheng Zhu, and
Jian Tang. Graphtext: Graph reasoning in text space. arXiv, 2023. (pages 33 51)
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv, 2019. (page
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In ICLR, 2022b. (pages
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propaga- tion. ProQuest number: information to all users, 2002. (pages T0 50)
Xiaojin Jerry Zhu. Semi-supervised learning literature survey, 2005. (pages 10
50
Yun Zhu, Yaoke Wang, Haizhou Shi, and Siliang Tang. Efficient tuning and inference for large language models on textual graphs. In IJCAI, 2024. (page 51
David Zuckerman. On the time to traverse all edges a graph. Inf. Process. Lett., 1991. (pages
42
46 50
17

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 SECOND-ORDER RANDOM WALKS (SECTION 2
In second-order random walks, the probability of choosing Ut+1 depends not only on 8; but also on 14-1- We consider non-backtracking (Alon et al. 2007 Fitzner & van der Hofstad 2013) and node2vec (Grover & Leskovee 2016) random walks as representatives.
A non- non-backtracking random walk is defined upon first-order random walk algorithm, e.g. one in Equation by enforcing u/+1 o 14-1:
Probfet41 2/v; = EvENOr Prob|uc+1 = =y/uz = =
for +
Prob|ut+1 = 0/ = J. 1-- =
(13)
for = i,
where Prob|us41 = z/v; .] is the probability of walking j - given by the underlying first-order random walk. Notice that the probabilities are renormalized over N(2) \ {d). This is ill-defined the case the walk traverses i + j and reaches dangling vertex j which has i as its only neighbor, since N( (1) 0. In such cases, we allow the random walk "begrudgingly" backtrack (Rappaport et al. 2017 i - j and then + i, given that it is the only possible choice due to the dangling of
In case of node2vec random walk (Grover Leskovee 2016). a weighting term a(4-1,, (t+1) with two parametees,,, return and in-out introduced to modify the behavior of first-order random walk:
ali, x) Problec+1 = x/ue = j]
Prob/ue4 = W//ee = 1, = = ΣVENG) a(i,v) Prob|ut+1 1/ 5
(14)
where the probability Prob xr/e = 5] is given by the underlying first-order random walk and a(%-1, ((+1) is defined as follows using the shortest path distance d(#)-1, P++1):
1/p for d(v,-1, P(41) 0,
a(1-1, P(41) =
for d(w4-1, 0(41) 1,
(15)
1/9 for d(v;-1, P(41) 2.
Choosing a large return parameter p reduces backtracking since decreases the probability of walking from v. 1--1- Choosing small in-out parameter has similar effect of avoiding 0z-1, with slight difference that it avoids the neighbors of 0t-1 as well.
We now show extension of Proposition 2.2 the above second-order random walks:
Proposition A.1. The non-bacctracking 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 given Appendix A.9.3
18

---

Published as a conference paper at ICLR 2025
A.2 MAIN ALGORITHM
We outline the main algorithms for the random walk and the recording function described in Section shows and used in Section Algorithm shoows the random walk algorithm, and Algorithms 2 and show the recording functions. For the random walk algorithm, we use non-backtrackknn described in Appendix A.1 and the minimum degree local rule conductance cc(-) given in Equation by default.
Based on the algorithms, in F and und6owe illustrate the task formats used for graph separation experiments in Section 5.2 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 7 and 9
we show task formats for transductive classification on arXiv citation network in Section 5.3
Algorithm 1: Random walk algorithm
Data: Input graph G, optional input vertex v, conductance function cg : E(G) + I2,, walk
length 1, optional restart probability E (0, 1) or period k >
Result: Random walk up - .... U,, restart flags T1, F1
/* transition probabilities p EG) R. x/
for (u, x)) E (G) do
L p(u, + co(u,))/ /at,d)//vennn EvEN(a) cu(u,))
// Rquat
1+ starting vertex
if v is given then
/* query starting vertex x/
to +
else
/+ sample starting vertex +/
0o Uni)orm(V(G))
/a random walk +... vr, restart flags f1, +/ N(v))))
01 (ategorical((p(oo
+- 0
for t < to do
/a restart flag */
10
P: <-
if a is given then
/+ it restarted at 1 1-1, not restart +/
12
if r = 0 then
13
Pt Bernoulli(a)
14
else & given then
if = 0 (mod k) then r
16
/+ random walk 14 +/
if rr: 0 then
< (v,-1) ( (v-2)
18
if S then
/. non-backtracking //
()te
E /ogpriilelppptttt////ssssssooous S})
// Equation
21
else
/+ begrudgingly backtracking +/
21-2
else
/+ restart +/
19

---

Published as a conference paper at ICLR 2025
Algorithm 2: Recording function, using anonymization
Data: Random walk vo U, restart flags "1
Result: Text record
/* named vertices S, nanespace id(.)
S t- {2
id(v)) +1
/a text record */
2 4 id(w))
for t -- 1
/* anonymizatien e id(w) */
if o & S then
S }0a}
id(v:) + |S|
/* text record 2 x/
if 0 then
/. record walk 14-1 - 1i +/
2 - 2 n-" id(v))
10
else
/. record restart vn
2. - 2+ "; id()))
11
Algorithm 3: Recording function, using amonymization and named neighbors
Data: Random walk to - fi restart flags T1:".,',, input graph G
Result: Text record
/x named vertices 8, namespace id(-), recorded edges T x/
IS+ S [vp}
id(vo) +
+00
/a text record
2 + id(up)
for 1
/a anonymization e + id(m)) x/
if & S then
Su
id(v:) +
(a text record 2 */
r. = then
/+ record walk 1-- + +/
10
z 2 n_ id(())
T + (U Ur), (1e, 1111)}
11
/* named neighbors x/
U + n
13
if + then
sort in ascending order id(un) ... < id(upi) */
< SorUByKey(U,id)
for un to dpj do
/x record named nei in - +/
if (v, u) T then
z - z " + id(u)
T - TU u(v,,,,,(,, (u,
19
else
/+ record restart == vo +/ z 4- 2 ";" + id(v))
20
20

---

Published as a conference paper at ICLR 2025
Algorithm 4: Recording function for transductive classification arXiv network (Section 5.3
Data: Directed input graph G, random walk vo - ... + and restart flags Ti, Tt on the undirected copy of G, paper titles (EViG) and abstracts (EV()) target category labels {y=) for labeled vertices T C V(G)
Result: Text record
/+ named vert ces S, nanespace id(-), recorded edges T
S + {
id(vo) +1
T PtD 0
/A text record x +/
/a record starting vertex x/
2 + "Paper
Title: (tmp )" Abstract: (ang)
fort + /o
/+ anonymization idii) +/
ef & S then
Su (
id(m)) - SS
(+ text record 2 +/
if 0 then
/+ record walk 8-11 + v with direction
if (m-11, U2) E E(G) then
11
2 - z + Paper (id(e;-1)) cites Paper (id(v)))"
else
13
2 - z z Paper (id(0:11) is cited by Paper (id(v)))"
T TU T (vr, v-1)]
14
/+ record title to, abstract a., and label Yv if is labeled */
15
id: = S ||| then (t,)"
2 2 2+
17
if L then
L z z+", Category: (yv)"
z 2 2 , Abstract: (a,)"
20
else
21
2 "."
/* named neighbors U x/
+ ns
22
i / 0 then
/x sort in ascending order id(u1) .... < id((pp)) */
Mi...., url < SUrtByKcy(U,id)
for u 4- to U|yl do
/8 record named neighbors 1N + with directions
if (u,, u) & T then
if (v;, u) E(G then
z + z + Paper (id(),) cites Paper (id(u))."
else
z - z z+" Paper (id())) is cited by Paper (id(x))
T TU (1,
32
else
/+ record restart +/
33
z z+ Restart Paper 1."
21

---

Published as a conference paper at ICLR 2025
5-0
Szeph
Random Walk
[CLS]
10 11111111111111111111111110111111
2421423-2-22
41-34-35-280
11-30-35-19-41-5--22---
23-32-29-22--1-33
(41,
45
510
Groph
Randem
Record
[CL8]1-2-3
21-22-2234-22222--222222
15-25-28-27-4
[SEF]
csl (41, 16)
Figure Two CSL graphs and text records random walks from Algorithms and 3 Task graph classification into 10 isomorphism types csl(41, s) for skip length {2, 3, 4, 5, 9. 11. 12, 13, 16). In random walks, we label vertices by anonymization and color edges by their time discovery.
22

---

Published as a conference paper at ICLR 2025
Graph
Random Walk
Record
8 7: 93
12 12-1-11--12-144422-133
gzaph
010
Graph
Random
Record
[CLS]]-
14#:4248412-
11-4-12-77119----------------31-
--1--10-6-11-11------------
1-10-6-13-9-8-9-1111
11-12-1--1-
Anawer
Shrikhande
graph
Figure 5: SR16 graphs and text records of random walks from Algorithms and classification into two isomorphism types {4 rook's graph, Shrikhande graph}. In random walks, we label vertices by anonymization and color edges by their time of discovery.
The task is graph
23

---

Published as a conference paper at ICLR 2025
Graph
Random Walk
Record
39647
1741466
F#10F114:3411-11
2
16-27-10-11-1
Gcaph
000
Groph
Record
[CLS]1-
8-134749r12-18
4
20-2--2--1--
[SEP]
Anawer
Graph
Figure 6: Two SR25 graphs and text records of random walks from Algorithms | and 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.
24

---

Published as a conference paper at ICLR 2025
8ystem
A walk on the arXiv citation network will be given. Predict the a:Xiv cs sup cat follewings Numerical Analysis (cs.NA), Maltimedic (G5.XM), Logic in Computer Science [cs. (cs.DK).
egory Paper belongs to. it
Discrete Mathemst in
Only respond with the answer, do not say eay word or explain,
Record
A walk on acXiv oitation network is as [ollowai
Paper litle: Safety guided deep reinforcement learning
online gaussian process estimation, Abstract: An important facet of reinforcement learning (rl) has to do with how the agent gees about exploring the enviroament. traditional exploration strategies typically focus efficiency and ignore safety, however, for practical applications ensering aafety of the agent during exploration is performing
action reaching unaafe state could result in iszeversible damage to the agent. the main challenge of safe exploration Paper g sa cited by Learning to walk in the real world with minimal human effort, Abstract: Reliable and stable locomotion has been one of the most fundementel challenges for legged robcts. deep reinforsament learning (deop =1) emerged Restart at 1. Pa Deep learning fzom demonstratione, Calegory: Artificial gence (ct, Abstract: Deep zeinforcemeat learning (=1) has achieved several high profile successes difficult desision-meking problems. however, these al algorithms typfcally require huge amount of data before they reach... Restart Constrained policy optimization, Calegory: Machine learn IG), Abstract: For many applications of reinforcement learning it be more convenient to apecify both reward function and constraints, rather reward Function. for example, ger is cited by 2. Paper a is cited by 5 Artificial inzelligence values and
crucial
that charactesizing
unsafe states and actions... Restart
as a promi aing not for developing auch control policies...
Giles
Papez cites
than trying to design behavior through
alignnent, Abstract: This paper locks philosophical quasticna that arise the context of at alignment. it defenda three propositions. first, normative and technical aspects of the si eligament problem are interreiated, ... Paper safety l'terature review, Eategory: Arrificla Intelliqance (CS,AI) Abstract; The development of artificial general intelligence (agi) promises to
g
majer event. along with its many petential benefits, also raises serious safety conceras (bostrom, 2014). the intention of... Paper & is eited by 1 Modeling agi safety frameworks
causal influence diagrama, Abstract: Proposals for safe agl systema are typically made at the level of frameworks, specifying how the components of the proposed system should be trained interact
this paper, per 1 cites 8 Safe learaing of zegions of attracticn for uncerssin nonlinear Control (cs.St), Abstract:
systems gaussian processes, Category: Systems
Control theory can provids useful insights into the properties of contralled, dynamio systems. one important property of nonlinear aystems the region Control
attraction (ros), safe aubset of the state... Paper is elled theory zeets ponáps a hybrid systems 45proach, Abstract: Partislly observabie markov decision processes (ponáps) provide modeling [ramework for variely sequentiel decisioa making under uncertainty scenarics in artificial intelligence (ai). since the... Restart
which arxiv CS sub-category does Paper belong to? Only respond with the ansker, Say any explain.
Anawer
Machine Tearning (cs.toy
Figure 7: Transductive classification on arXiv citation network using text record of random walk from Algorithms
I and Colors indicate task instruction, walk information, and label information.
25

---

Published as a conference paper at ICLR 2025
System
ritle and abstract of arxiv paper will
Predics the axxiv sub-cate
gory the paper balonga to. It la ane of the *olloxings Numarical Ana lyais [os.NA), (Cs.MM), Logic Computer Science (M). Only respend with the anewez, do not
... Discsele Mathematics word or explain.
Context
Title: Safety guided deep reinforcement learning via online gaussian process ostimation
Abatract:
do with how the agent goes about explering the environment. traditionsl exploration strategies typically
important
reinforcement learning
ignore safety. however, for practical applicaticns, encuring safety of the agent during exploration is crucial since performing an unsafe sction or resching an unsafe state could result irreversible damage the agent. the main challenge safe exploration is that characteri the unsafe states and actiona...
efficiency
arXiv
calegory this pape: belong
Answez
Machine Learning
(cs.
Figure 8: Zero-shot format for vertex classification on arXiv citation network. Task instruction and label information are colored.
System
Tiele and abstract of an arxiv paper T1 be given. Predios the arXiv CS aub-oate gory the paper belongs tc. It is one of the folloxings Numerical Anslysis (Cs.NA), imadiaadia (cs.MMy, bog'
10), Disc Matae
(ca. (Ca.DMI)
Context
Title:
Deeptrack learning discrininative feature represencations online For robust visual tracking
Abstract: Deep neural networks, albeit their great in varlous computer vision taaka, are usually cons considered aa impractica.. for online
feature learning
tracking, because they zequice very long... Cazegory: cs.eV
Title:
Perceived audiovisual quality model ing based on dect trees ge programming and neural networks....
Abstract: objective la to but ld machine learning based models that prediet audioviaual quality directly from set of corzelated parametera that are extracted from target quality dateset. Cazegory: c5.8K
the...
Title: Safety guided deep reinforcement learning online gaussian process estination
Abstract: important
reinforcement learning (xl) to do with haw tha zgent goes about explcring the environment. tredicional exploration strategies typicallyy focus efficiency and ignore safety. hovever, for practical applicatiens, cruatal since per an unsafe act' on or reaching an unsafe state could irreversible damage
safety of the agent during exploration is
main challenge sale exploratien is that cheracterizing the unsafe states and acticns... Shich arXiv sub-casegery this papes belong to?
agent,
Answer
E5.LE
Figure 9; One-shot format for transductive classification on arXiv citation network. 40 labeled examples are given form of multi-turn dialogue. Task instruction and label information are colored.
26

---

Published as a conference paper at ICLR 2025
[...] walk arxiv citation network follows?
Paper - Title: Inaupervised and "nte"pretable scene discavery with diacrete atterd infer present discrete attend infer repeat (clacrete-air)) recurrent auto encoder with structured Latent Histributions containing discrete categori distributions, consinusus attribute distributions, while inspired by the original six mode: andretaining air model'a capability in identify ing objects in an image, discrete-air provides direct interpretabillty of the latent codes, show that for multi-mnies and mult-plofejjests varsion of daprites... Restart (oo) Restart at 1. Paper 1 cites 12 Attend Infer repeat fast scene underatanding with
repeaty
factorised spatisl attertion.
generative models, Category: Computer Viaion and Patterr Recognicton, (ea.CV), Abstract: Ne present a framework for efficient inference in structured image modela that explicitly rea about cbjects. achieve this by performing probsbilistic inference using recusrent neural network that..: Paper 12 cites 3. Paper 12 citas 7, Paper 12 is cited by 9, Paper ted by Paper]
Restart at Paper 1 cites 12. Paper 12 is cited by 13 An architecture for deep hierarchical generativa mod ela, Category: Machina Tearning (ca.16), Abstract: present architectuve which lats us train deep, directed genera: ive modela with many layera of latenz variablea. we include de terministic paths between all latent varisbles and the generated outpat,... Pape: 13 cites [...]
Restart
Paper eltea
3. Kestart
Attencion (Layer 23/301
Answer 05.CV
Prediction
09.0V
Figure 10: Example of attention a frozen Llama 8B applied on arXiv transductive classification. Attention weights are averaged over all 30 heads.
A.3 ATTENTION VISUALIZATIONS
In Figure TO we show an example of self-attention 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 make predictions.
In Figures II and 13 we show examples of self-attention in DeBERTa models trained for graph separation (Section 5.2). We first show attention weights on text record of random walk from the [CLS] query token. Then, we show an alternative visualization where the attention weights are mapped onto the original input graph. For example, for each attention on 2/41 where the walk has traversed 0 - U1+1, we regard it as attention on the edge (Vt, Ut+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 sparse, connected substructures, which presumably provide discriminative information on the isomorphism types. In particular, for CSL graphs (Figure ITI 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 of isomorphism types of CSL graphs.
27

---

Published as a conference paper at ICLR 2025
2
8-
14-23-22-21-221110---11
31 30 29 41418435438 21
5 15
Atteation (Bead 12/12, Layez 12/12)
Graph
Attention Kapped onto Graph
1-2-3-4-5-
1748 18416 19415
22 2343
29421426 24 10 30420022 314
-8429-28-28221-229
15 111---1117711------------------1
19-1166-111------
39-18-22-22-2---------
15
Atcention (Bead 5/12, Layer 12/12)
Graph
Actant lon Mapped ont
Graph
Figure 11: Examples of attention from [CLS] token in a DeBERTa trained on CSL graph separation, forming approximate cycles using skip links. This presumably related to measuring the lengths of skip links, which provides sufficient information to infer isomorphism types of CSL graphs.
28

---

Published as a conference paper at ICLR 2025
1-2-3-18-5----7111------------
2
2-1-8-9--1-2-3-14-19-111
13-14-6-5-7-8-9-111 12
13 9 15 1-
12 10
Attention (Bead 11/12, Laye: 10/12)
Craph
Actention Mapped onto Graph
2244122-8
5
13
10 11 10
16
5-8
2-3-9-15
5-6-7-12-1
(Read 11/12, Layer 7/12)
Graph
Astention Mapped
Graph
Figure 12: Examples of attention from [CLS] ] token in DeBERTa trained SR16 graph separation.
The model tend to focus on named neighbor records that form a sparse connected substructure, which we conjecture provide discriminative information on the isomorphism type of SR16 graphs.
29

---

Published as a conference paper at ICLR 2025
2--3F--
5888991 -
164 6617119220222 17
22
25
21
24
17
10
23
18
Attension (Read 4/12, Layez 9/121
Craph
Actention Mapped onto Graph
1-2-
11
18 18424345478
# 0112-
25-20- 7- -tt.::/9--....11111-----------13
(Head 10/12,
Layer 8/12)
Graph
Actention Mapped
Graph
Figure 13: Examples of attention from [CLS] ] token in DeBERTa trained SR25 graph separation.
The model tend to focus on named neighbor records that form a sparse connected substructure, which we conjecture provide discriminative information on the isomorphism type of SR25 graphs.
30

---

Published as a conference paper at ICLR 2025
Table 5: Over-smoothing and over-squashing results, extending Table (Section 5.1 MSE aggregated for 4 randomized runs, except for CRaWI which took >3 days per run.
We report test
Method
Clique (over-smoothing))
Barbell (over- -quassing))
GCN
29.65 0.34
1.05 0.08
SAGE
01.86 + O. 10
0.90 + 01299
GAT
20.97 = 0,40
1.07 +
NSD BuNN
0.08 + 0.02
1.09 + 0.15
0.03 0.01
0.01 0.07
1= 100
RWNN-MLP
0.082 +: 0,018
0.326 4: 0,035 0.388 0.048
WalkLM WarkLM-rrnsfoomrr
0.096 0.018
RWKN RWAN-Fannstorm Transformer (Ours)
0.049 + 0.0077
0.297 + 0.050
1000
CRaWl
0,103 1: N/A
0.289 = N/A
CRawi
0,121 = N/A
0,103 = N/A
RWKN-MPP
0.028 0.026
0.015 0.005
MalkLM transformer
0.023 1 0.003
0.087 1 0.009
RWKN KWNN Transformer (Ours)
0.023 + 0.006
0.007 + 0.001
A.4 SUPPLEMENTARY MATERIALS FOR SYNTHETIC EXPERIMENTS (SECTION 5.1
We provide experimental details and additional baseline comparisons for the Clique and Barbell experiments in Section 5.I could not include in the main text due to space constraints.
Dataset In Clique and Barbell [Bamberger et al. 2024), each vertex of graph G' is given random scalar value. The task at each vertex v is to regress the mean of all vertices with an opposite sign. In Clique, G is 20-clique, and its vertices are randomly partitioned into two sets of size 10, and one set is given positive values and the other is given negative values. In Barbell, two 10-cliques are linked form G and one clique is given positive values and the other is given negative values.
Models Our RWNN uses MDLR walks with non-backtracking, and since the task is vertex-level, for each we fix the starting vertex as oo = v. The recording function (wo + ... + ur, G) H takes a walk and produces a record z (id(vo), : - .... (id(e)). , where id(v) is the anonymization of e and x, is the scalar value of v. We find that recording X at each step improves training. The reader NN a 1-layer transformer encoder, with 128 feature dimensions, sinusoidal positional embedding, and average pooling readout. To map the recording at each step (id())), xu:: Xxo) a 128 228-dimensional feature, we use learnable vocabulary for id(")). a learnable linear layer for X.,, and 3-layer MLP with 32 hidden dimensions and tanh activation for X...
We test additional baselines that use random walks. We test CRaWI (Tönshoff et al. 2023) using the official code, and only remove batch normalization since it led to severe overfitting for Clique and Barbell. Since CRaWl uses vertex-leve average pooling, while RWNN-transformer uses walk-level, we also test variant that uses walk- pooling and denote it by CRaW1 We also test RWNN-MLL which uses an MIP on the concatenated walk features instead of a transformer. The MLP has layers with 1 128 hidden dimensions and ReLU activation. We also test an adaptation of WalkLM (Tan) et al. 2023). While the work entails two ideas, representation of walks and fine-tuning by masked auto-encoding, we focus on testing its choice of walks and their representation since the fine-tuning method is orthogonal to our work. We do this by modifying RWNN-transformer to use uniform walks and omit anonymization id (v,) from the walk record, and denote the model by -trrsssorrrrr.
We train all models with Adam optimizer with batch size I and learning rate 1c-4 for 500 epochs, closely following Bamberger et al. (2024) except for the lower learning rate which we found necessary for stabilizing training due to the stochasticity of walk based methods. For all RWNN variants, we perform predictions per vertex during training, and average predictions per vertex at test-time.
Bambererg
The results are in Table All random walk based methods consistently perform better than GCN, SAGE, and GAT, and trans-rranformmr achieves the lowest test MSE. This supports our hypothesis that RWNNs can, in general, be resistant to over-smoothing and over-squashing (for the latter, if the walk is long). but also shows that proper design choices are important to obtain the best performance. For example, CRaWI and C are limited by their window size of information processing (see Appendix AA and RWNN- is bottlenecked by the fixed-sized hidden feature. While MalkkM-trrnssfoo performs on par with than RWNN-MIPP Barbell, showing the benefits of our design of walks and their records.
Results
on Clique, its error is higher
31

---

Published as a conference paper at ICLR 2025
CSL training loss
SR16 training loss
Pretrained (Ours)
1.4
Pretrained (Our)
Scratch
Scratch
2.0
1.2
1.0
1.5
Taaninn
0.8
0.4
0.2
0.0
0.0
20000 40000 60000 80000
100000
20000
40000
60000
80000
100000
Figure 14: The impact of language pre-training on graph isomorphism learning (Section 5.2
Table 6: Fine-tuning for arXiv, extending Table 4 (Section 5.3
uses validation labels in Table
Method
Training-free?
Accuracy
Llama3-8k 8b zero-shot
51.31% %6
Llama3 8b one-shot
52.81% %
Llama3-8b one-shotf
O
52.82%
LJama3- 70h zero-shot
O
65.30%
LJama3- 70b one-shot
O
67 11.55%
RWNN-LJaama-8i (Ours)
71 71.06%
RWNN-Llama3-88 (Ours)f
73. 13.1%%
RWNN-Llama3-700 (Ours)
74.85%
RWNN-Llama3-8i (Ours), fine-tuned
74.95 %
Table 7: Transductive classification test accuracy on homophilic (Cora, Citeseer) and heterophilic
(Amazon Ratings) datasets. The baselines scores are from Sato (2024); Zhao (2023): Liu et al. (2024): Chen et al. 2024a b): Platonov et al. (2023)). i denotes using validation labels as in Table
Method
Training-free? Cora 20-shot
Cora
Citeseer
Amazon Ratings
Training-fiee free GNN
60.00%
GCN
81.40%
89.13%
74.92%
48%70%
GAT
80.80%
89.68%
75.39%
49.09%
Graph Text
O
68.30%
67.77%
68.98%
LLaGA
O
59.59%
Graph Text
87.1 %
74.77%
LLaGIA
X
88.86%
28.20%
OIA
X 75.90%
51.44%
RWNN-LJama3-S8 (Ours)
O
72.29%
85.42%
79.62%
42.71%
RWNN-LJama3-83 (Ours)t
O
79.84%
87 00.%
80.41 %
38.66%
RWNN-LJama3-8t -h (Ours), fine-tuned
79.45%
86.72%
80.72%
55.76%
A.5 SUPPLEMENTARY MATERIALS FOR GRAPH ISOMORPIISM LEARNING (SECTION 5.2
The impact of language pre-training In Section 5.2 we have used language pre-trained DeBERTa for graph isomorphism learning, even though the records of random walks do not resemble natural language (Appendix A.2 and A.3). To test if language pre- pre-trainin tr-irrnning is useful, we additionally trained RWNN-DeBERTa CSL and SR16 datasets using the same configurations our reported models but from random initialization. The training curves are shown in Figure 14] We find that language pre-training has significant benefits over random initialization for isomorphism learning tasks, as randomly initialized models converge very slowly for CSL, and fails to converge for SR16.
conjecture that certain representations or computational circuits acquired in language pre-training useful for processing text records of walks to recognize graphs. For example, some circuits specialized recognizing certain syntactic structures in natural language could be repurposed during fine-tuning to detect skip links of CSL graphs from text records of walks. Our results are also consistent with prior observations on cross-model transfer of pre-trained language models to different domains such image recognition (Lu et al. 2022
Rothermel al. 2021).
32

---

Published as a conference paper at ICLR 2025
Table 8: Peptides-fune graph classification. The baseline scores are from
Tönshoff et al. 2024
Method
Test AP
GCN
0.6860
GINE
0.6621
GatedGCN
0.6765
Transformer
0.6326
SAN
0.6439
CRaWi
0.7074
(Ours)
0.7123 + 0.0016
n5 #ag
Record
r13[0, I71C, wttp://eaaaiiaaro.../..:/:122111 21 bbd.ddasppilccccccre00sea33a3343 m22 x24 222"=22||22222220113333550101413 "=a_a_acc_aaaaaaa.aaaaa333332221
#22=
33 |rg_a//._.aa.a20.000000000101111
38 cw,
r "2g. 40-m39=m188 [0, ap000=p22))3333 300---33-------3333-- 38-33-3-----3-mm-33333333333333 -0-0
Figure 15: An example text record for Peptides-fume graph classification.
A.6 SUPPLEMENTARY MATERIALS FOR TRANSDUCTIVE CLASSIFICATION (SECTION 5.3
Fine-tuning In Section 5.3] our RWNNs are training-free. We demonstrate fine-tuning the Llama 8b reader NN using the training labels with quantized low-rank adaptation (QLoRA) (Hu et al. 2022 Dettmers et al. 2023). The result is in Table 6 showing a promising performance.
Additional real-world transductive classification We provide additional experiments real- world transductive classification datasets Cora, Citeseer, and Amazon Ratings. Our RWNNs are designed similarly the ones used for arXiv. We compile the baseline scores from (ato (2024): Zhao iet al. (2023): Liu et al. (2024): Chen et al. (2024a b): Platonov et al. (2023b), which includes MPNNs and language models on graphs. The results are Table 7 Llama based RWNN is competitive among training- frreeingffree methods, and performs reasonably well when fune-tuned with QLoRA. Especially, on Amazon Ratings which is heterophilic (Platonov et al. (0236), our fine-tuned
achieves the highest accuracy (55.76%) This supports our results in Section 3.2 that RWNNs avoid over-smoothing, as avoiding known to important for handling heterophily (Yan et al. 2022).
A.7 SUPPLEMENTARY TASKS
We provide supplementary experimental results on real-world graph classification, substructure counting, and link prediction tasks we could not include in the main text due to space constraints.
Real-world graph classification We conduct a preliminary demonstration of RWNN on real-world graph classification, using the Peptides-fune dataset (Dwivedi et al., 2022) used in Tönshoff et al. (2023). Our model is pre-trained DeBERTa-bars (identical to Section 5.2) fine-tuned on text records of non-backtracking MDLR walks with anonymization and named neighbor recording. The recording function designed to properly incorporate the vertex and edge attributes provided in the dataset, including the atom and bond types. An example text is provided in Figure 15
In Table g we report the test average precision (AP) at best validation accuracy, with 40 random predicted logits averaged at test time. We report the mean and standard deviation for five repeated tests. The baseline scores, including CRaWI, are from Tönshoff et al. (023): Tönshoff et al. (2024). We that RWNN-DeBB DeBERTa, which has been successful in graph isomrrphism learning (Section (5.2). also shows a promising result in real-world protein graph classification, despite its simplicity of recording random walks in plain text and processing them with fine-tuned language model.
33

---

Method Published as a conference paper at ICLR 2025
Table 9: Substructure (8-cycle) counting. We report normalized test mean absolute error (MAE) best validation. We trained MP, Subgraph GNN, Local 2-GNN, and Local 2-FGNN using configurations in Zhang et (2024). and trained MP-RNI, Dropout, AgentNet, and CRaWI in Table
Method
Graph-level
Vertex-level
MP
0.0917
0.1156
Suhgraph GNN
0.0515
0.0715
Z-GNN
0.0433
0.0478
2-FGNNN
0.0422
0,0438
2-FGNN (large)
0.0932
0.1121
MP-RNI
0,3610
0,3650
MP-Dropout
0,1359
0.1393
AgentNet
0.1107
N/A
CRawI
0.0526
0.0725
WWNN-DDBERTA (Ours)
0.0459
0.0465
Table 10: Real-world link prediction. The baseline scores from Table of Cai al. (2021) and reproduced LGLP using the official code. We report the aggregated test AP for randomized runs.
YST
KHN
ADV
Katz
81.63
83.04 = 0.38
91.76
PR
82.08 = 0.46
87.18 0.26 0.26
02.43:0.11
SR
76.02 :
75.87
83.22
node2vec
76.61 0.94
80.60 0.74
76.70 0.82
SEAL
86.45
90.37
93.52
LGLP
88.54 0.77
90.80 0.33
93.51 0.32
RWNN- -trrnntttorrr (Ours)
88.13 0.45
90,90 = 0.35 93.70 # 0.21
Substructure counting To supplement Section 5.2
we demonstrate RWNNs on challenging tasks that require both expressive power and generalization to unseen graphs. We use synthetic dataset of 5,000 random regular graphs from [Cen al. (2020) and consider the task counting substructures. We choose 8-cycles since they require a particularly high expressive power (Zhang al. 2024).
We test both graph- and vertex-level counting (i.c., counting 8-cycles containing the queried vertex) following Zhang al. (2024). We use the data splits from Chen et al. (220)) Zhao al. (022b): Zhang et al. (2024), while excluding disconnected graphs following our assumption in Section 2.1 Our RWNN uses the same design to Section 5.2] and we train them with L1 loss for =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 predictions by averaging for graph- and vertex-level tasks, respectively.
The results are in Table 9 and overall in line with Section 5.2
While MPNNs show a low perfor- mance, variants with higher expressive powers such as local 2-GNN and local 2-FGNN achieve high performances. This is consistent with the observation of Zhang et al. (2024). On the other hand, MPNNs with stochastic symmetry-breaking 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.
often show learning difficulties and does not achieve
Link prediction We demonstrate an application of RWNNs to real-world link prediction, based on on et al. (2021) where link prediction is cast vertex classification on line graphs. We follow the experimental setup Cai et al.) (2021) and only change their 3-layer 32-dim DGCNN with an RWNN that uses 3-layer 32-dim transformer encoder. As the task is vertex-level, we use periodic restarts with & = 5. The results in Table TO shows that RWNN performs reasonably well.
A.8 SUPPLEMENTARY ANALYSIS (SECTION 5 AND APPENDIX A.7
We provide supplementary analysis and discussion on the impact of cover times, test-time ensembling. and the effective walk lengths, which we could not include in the main text due space constraints.
34

---

Published as a conference paper at ICLR 2025
Table 11:
The performance of RWNN-DeBERTa on SR16 graph separation (Table different required cover times controlled by the use of named neighbor recording.
3 Section 5.2 for
Test accuracy
Cover time
w/o named neighbor recording w/ named neighbor recording
50%
Ce 490.00
100 %
Cv 48.25
Table 12:
The performance of RWAN-LLama33700b on arXiv transductive classification (Table Section 5.3 for different local cover times controlled by the restart probability a of the random walk.
Test accuracy
Cover time Cv(B...(o))
Unique vertices observed per walk
0.3
74.40%
161.2
45,28
0.7
74.85 %
96.84
31.13
The impact of cover times of walks In Section 2 we use cover times as a key tool for the analysis and comparison of different random walk algorithms. In the analysis, cover times provide the worst-case upper bounds of walk length required to achieve universality, which is in line with the literature on the cover times Markov chains (Feige) 1995). To demonstrate how the differences in cover times may translate to different model behaviors, we provide two examples where performing interventions that change cover times leads to substantial differences in task performances.
First, in $R16 graph separation (Section 5.2) we test the use of named neighbor recording, which changes the required cover time from vertex cover time (G) (when used) to edge cover time Ce(G) (when not used). The result is in Table 11 We can see that not using named neighbor recording has a drastic effect on the required cover time (vertex cover time 48.25 + edge cover time 490.00), and the test performance deteriorates from perfect to random accuracy (100% - 50%).
Second, arXiv transductive classification (Section 5.3), due to the high homophily (Platonov et al., 2023a) we can assume that the cover time of the local neighborhoods, i..., (v) for small r, has an important influence on performance. Thus, we set r = 1 and check if the walk strategy that lowers the cover time of (v) leads better performance. To test different local cover times, two choices of the restart probability a = 0.3 and 0.7. Since we use named neighbor recording, we measure vertex cover times. Due the large size of G. we estimate the cover times by fixing random set of 100 test vertices and running 100 walks from each of them. The result is in Table I2 Increasing the restart probability (0.3 + 0.7) simultaneously results in lower cover time (161.2 96.84) and a higher test accuracy (74.40% + 74.85%). even though the average number of observed vertices decreases (45.28 + 31.13). This implies that lower cover time is correlated with better performance, while the number of observed vertices itself is not directly correlated with better performance.
While the above shows cases where interventions in cover times lead to different task performances, in general, there are factors that make it not always trivial to equate task performances and cover times. This because a substantial amount of useful information in practice could be recovered from possibly non-covering walks. We discuss this aspect in depth in Appendix A.
The impact of test-time ensembling For each test input to an RWNN Xo. we often sample several randomized predictions y ~ Xx(-) and ensemble them by averaging (or voting, for Llama models where we cannot directly obtain continuous logits). As discussed in Section 2 this can be viewed as MC estimation of the underlying invariant mean predictor (.) + E[Xo (+)] (or the invariant limiting classifier in the case of voting (Cotta et al. (023)). ). From another perspective,
also interpret this as a type of test-time scaling with repeated sampling, which has been shown beneficial in language models (Brown al. 2024) and randomized algorithms (called amplification (Cotta et al. 2023, Sieradzki et al.] (022)) To see if similar perspectives can be held for RWNNs, we measure the model performances with increased numbers of samples for averaging or voting. The results are in We see that increasing sample size consistently leads to better performances and reduced variances overall. The point of plateau seems differ per application and model architecture, and we leave obtaining better understanding of the scaling behavior for future work.
Table 13
while the strict definition of edge cover requires traversing each edge in both directions, measurements only require traversing one direction, which suffices for the universality of RWNNs.
As in Section 5.1
35

---

Published as a conference paper at ICLR 2025
Table 13: Test performances RWNN-Llama3-70h (Table 4 Section 5.3 and RWNN-DeBERG
(Table [ Appendix A.7) for different numbers of randomized predictions for ensembling by voting
and averaging, respectively. For we were unable to rum repeated experiments due to sampling costs.
# samples
Peptides- func test AP
1
0.5300 = 0.0092
# samples
arXiv test accuracy
10
0.6937 = 0.0039
74.45 0.049%
20
0.7056 = 0.0026
74.75 = 0.035%
40
0.7123 = 0.0016
5
74.83 = 0.028%
60
0.7145 = 0.0015
7
74.86% = N/A*
80
0.7155 = 0.0014
10
74.87% # N/A*
100
0.7161 = 0.0009
0.7176 = 0.0013
320
0,7177 = N/A*
Table 14: Effective random walk lengths for the experiments in Sections 5.2 and 5.3
Dataset
Length
CSL (Section 5.2
214.03 + 2.48
SRI6 (Section S
222.00 + 0.00
SR25 (Section
129.54 # 2.26
arXiv (Section
194.52 10.59
Effective walk lengths For Sections 5.2 and 5.3 the effective lengths of walks affected by the language model tokenizers since text records exceeding the maximum number of tokens are truncated. The maximum number of tokens a hyperparameter which we determine from memory constraints; for the DeBERTa tokenizer used in Section 5.2 we set it to 512, and for the Llama tokenizer used in Section 5.3
we set it to 4,096. The effective lengths of random walks for each dataset are measured and provided in Table 14 The effective length is shorter (129.54 on average) for SR25 graphs compared to CSL and SR16 221.03 and 222.00 on average, respectively) although using the same tokenizer configurations which is because the higher average degrees of SR25 graphs (Figure 6) compared to CSL and SR16 graphs (Figures 4 and [ respectively) has led to higher number of text characters invested in recording named neighbors ("+" symbols in the figures).
36

---

Published as a conference paper at ICLR 2025
A.9 PROOFS
We recall that an isomorphism between two graphs G and H is a bijection т: V(G) + V(H) such that any two vertices and adjacent in G if and only if r(u) and T(r) are adjacent in H. an isomorphism π exists between G and H, the graphs are isomorphic and written = H or G 2 H. By X we denote the equality of two random variables X and Y in distributions.
In the proofs, we write by id(-) the namespace obtained by anonymization of walk (Section 2 that maps each vertex v, to its unique integer name (e,) starting from id(vp)
Let us define some notations related to cover times. These will be used from Appendix A..9. 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 and v. For a graph G, let Cy (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 Cv()), or the cover time, is this quantity given by the worst possible
Cv( = max Cv Cv,
(16)
GEV(G)
Likewise, let Cg(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 Cg (G) is given by the worst possible u:
CE(G)
max wEV(G)
CE(G,u).
(17)
For local balls B, (u), we always set the starting vertex of the random walk to (Section 2.2 Thus, we define their cover times as follows:
(B Cv (B), CE(B, = (B),
(18)
(19)
A.9.1 PROOF PROPOSITION 2.1 (SECTION
Xo(-) is invariant in probability, if its random walk algorithm invariant in probability and its recording function is invariant.
Proposition 2.1,
Proof. We recall the probabilistic invariance of random walk algorithm in Equation 3
<(vo) - क (w) un . un YG & H,
(20)
where f4.) random walk on and un is random walk on H. We further recall the invariance of recording function q (un .... my G) in Equation
q(vo + + v,. G) (())) + ... + (()), H), VG H,
(21)
for any given random walk ft on G. Combining Equation 20 and equation 21 we have the following:
q(uu + ... + Un G) ( + ... 24, H). VG ~ H. Then, since the reader neural network fe a deterministic map, we have:
(22)
fola(vo .... uz. G)) fola(uo + .... -n H)), VG H,
(23)
which leads to:
Xa(G) d Xx(I)), VG ~ H.
(24)
This shows Equation and completes the proof.
0
A.9.2 PROOF OF PROPOSITION 2.2 (SECTION
We first show useful lemma.
Lemma A.2. The random walk in Equation is invariant in probability, if the probability distributions of the starting verfex vo and each transition et Ut are invariant.
37

---

Published as a conference paper at ICLR 2025
Proof. We prove by induction. Let write probabilistic invariance of the starting vertex vo as:
T(00)
_ uo. AG ~ H,
(25)
and probabilistic invariance of each transition 0t-1 et follows, by fixing 0t-1 and u4-1;
x ((=-1) - (w)) 4e-1 + AG H 4-11 = (1)-1).
(26)
Let us assume the following for some 2 1:
π (wo)
No 1t-1,
G H.
(27)
Then, from the chain rule of joint distributions, the first-order Markov property of random walk in Equation and probabilistic invariance in Equation 26 we obtain the following:
ग (vo) - π (w+) d
uo
Ut:
G H.
(28)
By induction from the initial condition x =vo)
d = un in Equation 25 the following holds >
x ((%)
क (vi)
d un
" AG E H.
(29)
This shows Equation 3 and completes the proof.
We now prove Proposition 2.2
Proposition 2.2
The random walk in Equation is invariant in probability if its conductance (1-)(-)
invariant:
ca(u, v) =
VG & H.
(30)
It includes constant conductance, and any choice that only uses degrees of endpoints deg(u), deg(v).
Proof. We recall Equation 4 for a given conductance function E(G)) - R,:
CG cG(u, x.)
Prob/ug x|U--1 u|]
(31)
EpEN(w) ca(u, (u,y)
From Lemma A.2 it sufficient to show the probabilistic invariance of each transition 0t-1 - 122 as
we sample vn from invariant distribution Uniform(V (G)) (Algorithm [). We rewrite Equation 26 as:
Prob(c; = x| = u] = Prob[u, = (())/u--1 = Tu)), VG H.
(32)
If the conductance function c-)(+) is invariant (Equation 30
show Equation 32 by:
ca(u,
Probfu; 2/11-1
EveN(u) ca ca(u,)) cH(T(U), (x))
Σ EveN(a) CH (T(U),
(
Em(w)N(() CH (=()
Prob|u, [()) = VG - H.
(33)
In the third equality, we used the fact that isomorphism 7(-) preserves adjacency. is clear that any conductance function (-) with a constant conductance such as ca(C) = is invariant. Further- more, any conductance function that only uses degrees of endpoints deg( (). deg(v) invariant as [
isomorphism x <(-) preserves the degree of each vertex. This completes the proof.
38

---

Published as a conference paper at ICLR 2025
A.9.3 PROOF OF PROPOSITION A.1 (APPENDIX A.1
We extend the proof of Proposition 2.2 given in Appendix [.9.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 in probability, if the probability distributions of the starting vertex vo, the first transition to - Ui, and each transition (Gr-2, Vt-1)
for 1. > 1 are invarianl.
Proof. We prove by induction. The probabilistic invariance of starting vertex up and first transition Vo 0n are:
π (vo) uo, YG E 11,
(34)
((v)) π (v)) uo U1 AG ~ H, V(G), un T(U)).
(35)
and probabilistic invariance of each transition (0-22 - u2 for can be written as follows
by fixing (V+-2, 11-1) and (u,-2, 1t-1):
(v)-2) - (1)-1) - x(w)) 2 > 14-1 - ut.
VG H,
(v vt-1) E E(G), (4 4-11 ( (36)
IT
Let us assume the following for some 2
(Un) + ....... (v)-2) + ( (v: 40 7
2 -4-1
G Z H.
(37)
Then, from the chain rule of joint distributions, the second-order Markov property of second-order random walks, and probabilistic invariance in Equation
36 we obtain the following:
т (vp) + ... (T) (1;)) $ un
1 - uhy
G
_ H.
(38)
By induction from the initial condition ((vo) क ((1)) the following holds vl > O:
un
un given from Equations 34 and
35
a(v))
π (21) $ uu up YG H.
(39)
This shows Equation 3 and completes the proof.
We now prove Proposition A.1
The non non-backtracking random walk in Equation 73 and the node2vec random walk Equation 14 are invariant in probability, if their underlying firstorderr random walk algorithm is invariant in probability.
Proposition A.1
Proof. We assume that the first transition Up - U1 is given by the underlying first-order random walk algorithm. This is true for non-backtracking since there is 0--2 to avoid, and true for the official implementation of node2vec (Grover & Leskovec 2016). Then from Lemma A.3 it is sufficient to show probabilistic invariance of each transition (U:-2, Ur-1) Ut for as sample vo from the invariant distribution Uniform( V (G)) (Algorithm D and the first transition Up - 22 is given by the first-order random walk which is assumed to be invariant in probability. Rewrite Equation 36 as:
Prob(u: 2|12-1 -. U1-2
Prob(u, π (x))u,- T(1), 4- T()). VG H. (40)
For non-backtracking, we first handle the case where i + reaches dangling vertex which has i as its only neighbor. In this case the walk begrudgingly backtracks } j - i (Appendix A. Since isomorphism T--) preserves adjacency, (() + (j) also reaches dangling vertex T()) and must begrudgingly backtrack rTi) + T(]) + (i). By interpreting the distributions on i, and u, one-hot at and (i), respectively,
that Equation 40 holds. If does not reach
39

---

Published as a conference paper at ICLR 2025
dangling vertex, the walk j + follows the invariant probability of the underlying first-order random walk Prob(et+1 = z/1; = j] renormalized over ((1) \ {i). Then we can show Equation 40 by:
Problu, x//411 3, 1 =
Problu: = = =
for + i,
VENONMO Problur 1/0011 5]
for i,
Problu, u( = x())
for [()) + T(),,
E [=(IEN(66)M11)0 Problu: = T1)) x())
for (σ) = л (i),
= Probfu- =
AG 2
(41)
In the second equality, have used the fact that isomorphism T(.) is a bijection and preserves adjacency, and the assumption that the first-order random walk algorithm is invariant in probability.
For node2vec walk, first show the invariance of the weighting term a(ti in Equation 15 using the fact that isomorphism preserves shortest path distances between vertices d(i, x) = (T)
1/p
for d(i,x) 0,
ali,z)
1
for d(i,x) 1,
1/4
for d(i,x)
1/p
for d(T(()())))))))))))( (i),, T (x)) 0,
1
for (((((())((())))))))))) = 1,
1/q for d(T(())) (z)) 2.
a
(42)
Then we can show Equation b0::
ali,
Prob(u: x//e-1 i, 4-
E ΣVENO) ali, Proble: = y = j]
a(*(1), (x)) Prob/u (<x) u4-1 = =(j)]
En(DENN())) a (T(()) n Prob/l = 1--1 T())''
Prob/u (()) xj), (1) x()), VG H.
(43)
In the second equality, we have used the fact that isomorphism x(.) preserves adjacency, and the assumption that the first-order walk algorithm is invariant in probability. This completes the proof. Li
A.9.4 PROOF OF PROPOSITION 2.3 (SECTION
Proposition 2.3 A recording function 9 (No optionally with named neighbors, invariant.
Ul G) H that uses anonymization,
Proof. Given a walk Uo
vn on G, we can write the anonymized namespace id(-) as follows:
id(r;) = 1 + arg min iu; = vz).
(44)
Consider any walk ((v)) + + (w)) on some H which is isomorphic to G via n. Let us denote the anonymization of this walk id' id)(.). Then we have:
id' (T(()) = + arg min (vx) = n (v:)),
+ arg min iy: = vt).
=id(u;, YG H.
(45)
40

---

Published as a conference paper at ICLR 2025
The second equality is due to the fact that π is a bijection. This completes the proof for anonymization. For the named neighbors, we prove by induction. Let us fix some t 2 and assume:
q(vo
ut-1 G) (()((1)))
11) H), AG ~ H.
(46)
Let T S E(G) be the set of edges recorded by z == ( + ... + 1 G), and T" C EHH) be the set of edges recorded by z' = (T(())) + (1--1), H). Then, T and T" are isomorphic via x:
T' (IF((
E TT)
(47)
The equality is shown as follows. (2) Any (u, v) E T is recorded in z as (id(u), id(())) From Equations 46 and 45 we have z = z and (id(u), id(v)) = (id(T(u)), id(x()))). Thus, (T(u), (T)) recorded in z' as (i((x())) iud( Now, choose some U2 E (((--1) and consider the set F C E() of all unrecorded edges from ey!
i.e., (I("), (v) E T (C) This follows from symmetry.
F = {11, u) :2 N(e))
(48)
Then, the set D of unrecorded neighbors of o given as:
D = {u: : (ot, E F).
(49)
Since T(-) preserves adjacency, the set F' C E(H) of all unrecorded edges from T(v)) is given by:
F' ((T(v:) : x()) e ((T(v:))) \T'
[(T(V)), (()) :ue N(e)) \ (( ET, ((T(M)), ue ((n). $ Th.
((T())) (v), e F),
(50)
and consequently:
D' = [T(U)) : (T(D)), a(u)) E F'}. = {T(u)= u D}.
(51)
While D and D' may contain vertices not yet visited by the walks and hence not named by i.(.).
what we record are named neighbors. Let S be the set of all named vertices in G. It is clear that the
set S' of named vertices in H is given by S' = {T(D)= v E S}. Then, the named neighbors in G to be newly recorded for f4-1 + U2 given by U D n S, and for x(1-1)) - T(v)) in H the set is given by U" = D' S'. Since x-) is bijection. we can see that U' = ( ( the invariance of anonymization in Equation 45) U and U are named identically {id(u) : u E U}-
U}. From
(id(m m (u))= π (w) E U"), and therefore will be recorded identically. As result, the information to be added to the records at time are identical, and we have:
q(v0 + ... + ur G) q(((vo) + .... T(v),, H), Then, by induction from the initial condition:
Z..
(52)
q G) = (())) H) = id(o)) id(T(vv)) 1,
(53)
the recording function using anonymization and named neighbors is invariant.
A.9.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 vertex and edge cover times of the finite local ball (v) are not always finitely bounded.
Proof. We revisit the known fact that hitting times on the infinite line E is infinite (Dumitriu et al. 2003 Janson& & Peres, 2012, carnage 2012 McNew 2013). Consider a local ball (0) of radius 1, 1]. Let us assume that the expected number of steps for a random walk starting at 0 to visit for the first time 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 -1, we have to get back to O and then to which would take 2T in expectation (by translation symmetry). This leads to T 1/2 1 + 1/2 (1 + 2T) 1 + T, which is contradiction. Since visiting all vertices or traversing all edges in in B, (0) clearly involves visiting 1, the vertex and edge cover times cannot be finitely bounded.
I from the origin 0 such that ((B
41

---

Published as a conference paper at ICLR 2025
A.9.6 PROOF OF THEOREM 2.5 (SECTION 2.2)
Let us recall that our graph is locally finite (Section 2.2 and denote its maximum degree as A. We further denote by d(u, 2) the shortest path distance between u and v. We show some useful lemmas. We first show that H [u, z),, the expected number of steps of random walk starting at takes until reaching v. is finite for any
in (v) for any nonzero restart probability a or restart period k 2 Lemma A.4. For any and x in (v), H(u, x)) is bounded by the following:
1 + H(u, x) S
(54)
a
1
if the random walk restarts at u with any probability E (0, 1), and:
H(,,)) S k + KA"
(55)
if the random walk restarts at e with any period k 2 r.
Proof. We first prove for random restarts. The proof is inspired by Theorem 1.1 of McNew (2013) and Lemma 2 of Zuckerman (199I). We clarify some measure-theoretic details. Let W be the set of all (infinite) random walks on G. We denote by / the probability measure defined on the space W, equipped with its cylinder oallgebra, by the random walk restarting at v with probability a E (0,1), 1). For vertex in G, we define the hitting time function I- la : W + NU foo} as follows:
w == arg migmii()),: = x]. Yu 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 and visit b. and W (a, b-) be the set of random walks that start at and do not visit 6. Then, the measurability of lz follows from the measurability of the sets W (a)), W (a, b). and W (aa, 6 ). which we show follows. Va, b (G),, W(a) is clearly measurable, W (a, b) is measurable it equals Unentur w E W[( = a, (w), = b), and W(a, b-) is measurable as it is W(a) 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:
P(W (u, x O.
(57)
For this, we use the fact that W(u, xx = W(u, (T,,,,,,")) WW, U, vT, W(, where W(u, e x is
the set of random walks starting at that do not visit nor x. and W (u, v, ) is the set of walks starting at u that visit v and do not visit œ. We have the following:
P(W x )) = P(W 07, ;²=)) + P(W(u, v,x)),,
S ((W(u, ()), )) + P(W (u, v,,")),
(58)
We show Equation 57 by showing P(W (u, e )) = 0 and P(W (n, x)) = 0 in Equation 58
1. (P(W(,, visit v. Since restart sends walk to v, every walk in this set never restarts. The probability of a walk not restarting until step t is (1 a)".. Denote this probability by Pt, and let p be the probability of a random walk to never restart. Then Pt 4 pp= = and P(W (u, v)) S p = O.
0) Consider W o²), the set of all random walks that start at u and never
2. (P(W (1, v, ))) = 0) Assume P(W (u, v. > 0. Then (w, (v,x=)) )) > O since each walk step is independent. Let Wy be the set of walks that start at and do not reach within N restarts. Then we have Wx WN(u, x W(v, =7). If walk restarts at v, the probability of reaching x before the next restart from x, which is > 2 )d(v,2) E (0, 1). Then (V,N(U, )) S (1- (- (==a)d(o.))) )d(e.)))a + O. leading P(W (v. x 0. This is contradiction, so we have P(W(u, v, v) =0. 0.
least the probability of exactly walking the shortest path
We are now ready to bound H (u,x). Using the hitting time function |. 1. in Equation 56
have:
H(u, x) E [1 | ww E W(u)).
(59)
42

---

Published as a conference paper at ICLR 2025
Since (uu) W(u, ((, and P(W(u, x -)) = 0 from Equation 57 H(u, x)) = [R[ w ww E (u,,
we have:
=f -w(a.s) |elr (ul( ((u,
(60)
Each walk in Wuu, x) starts at u and, when it reaches x, it either has or has not visited v. We treat the cases separately. Let (a, b, c) be the set of walks that start at a and reach after b, and let W (a, b c) be the set of walks that start at and reach c before b. Then we have:
H(,
ww/ (P (u,,))), www.rwwwu
-I (((ue,,))
1/ dP(wwW((uxz)) ((u,e7,z)
lwaa (P(w)W(u,x))
(61)
Let (a, b,, c) (or (a,.b, c)) be the expected number of steps for a walk starting at a to reach after reaching b (or before b), given that is in W W(a, b, c) (or in ((a, b", ,c)). If a walk from reaches before v, the expected steps is given by H (u, x u) + (t, I). If the walk reaches before c, the expected steps is (u, v .)). Then, if W (w, 07, , ,)) * 0, we can write H(,, x) as follows:
H(u, x)
[M, x .0) (v,,)) x P(W (u, v, x(,,))(
+ Au, v ;,,, P(W (u, v- , (w,
(62)
On the other hand, if NWW[,, - x) 0, we simply have:
H (u,,)) (u, x,,, ,0) + H(, z).
(63)
We first consider A(, x ,V), the expected number of steps from u to reach v before æ. We show:
1
(u, ,0)
(64)
a
To see this, note that (u, is equivalent to the expectation E(T) of the number of steps T to reach v from u, on the graph G with the vertex 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 v. giving E[T]-
Otherwise, we have E[T] S 1/a due the following. Let T' be the number of steps until the first restart at v. Since restart can be treated as Bernoulli trial with probability of success a, T follows geometric distribution with expectation 1/a. Since it possible for the walk to reach before the first restart, we have [[T] < B[T"] 1/xx, which gives Equation 64
We now consider (v,,), the expectation [T] of the number of steps T to reach x from V. Let T be the steps until the walk restarts at then exactly walks the shortest path from to for the first time, and then restarts at v. Since T" walks until restart after walking the shortest path to x, and is possible for walk to reach before walking the shortest path to it, we have [E[T] < B[T"). Then, we split the walk of length T" 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 to Then N is the number of trials until we succeed, and it follows geometric distribution with probability of success at least (ا= d((,,)) due to bounded degrees. Its expectation is then bounded as:
E|N < (
A 1
d(v.x)
(65)
Let S; be the length the i-th trial. Since each S; is i.i.d. with finite mean E[S.] = 1/a, and N is stopping time, we apply Wald's identity (Hein) to compute the expectation of
E E[S; + . + Sw], E[N]E[S)),
1
A
d(v.m)
(66)
a
43

---

Published as a conference paper at ICLR 2025
We remark that 2)) E[T Combining this result with Equation 64 we have:
Hu, v) + (v. 1 1
a a ( A 11
d(v,x)
(67)
If (w, , .)) = 0. we have x(, Hu, x,, ,)) + (U, x)) from Equation 63 and it is finitely bounded for any a E (0, 1) by the above. If W (u, 0- 2) + 0, Equations 62 and 67 lead to:
H(u,)) - (u, u, _ .) + (U, Hu, v, .z) P(W(u, 07 .2) W (u, x)), d(v,æ)
- +
+ + t. ,)) ((,(u, ,=)l
(68)
(u, and it suffices to bound H(u, o ,X) DW x)). We show the following:
Mu, U0 ,)) = | ((uur-,)) Iwea (u
(MEW(,,-=))AllL 1 (,,
[wEW(aor-WMMlL-. dP(w(W(u,v7,a))
xx) b
h P([w: - = ku)
P(ww: ww/ = kk W(,,v .2)1)
P(W(u,
< Σ 1:1 a)*
((W(,,),xx)
k=1
- (1-1)
(69)
P(W(u, ,2))
We have used Fubini's theorem for the second equality. Then we have:
1
(( (,,,,",))[[W (w,
(() xx)
< 1)
((W(u,T,xz)
1
(70)
x()(,, P(W(u,z)) is least the probability of precisely walking the shortest path from u to x, which has length d(u, x) S 2r since u and æ are both in (.).). This gives us the following:
d(u,x)
P(W(u,z)) 2
a
A
2r
(71)
A
Combining this with Equation 70 we have:
1) ( (1-a)
A
2r
Au, o x)) P(W x) (w, (1,
<
(72)
a
a
Combining with Equations 62 and 67
we have:
1
A
1 (
A
H(u,z)
-1
1-a)
(73)
a 1-a
a
a
44

---

Published as a conference paper at ICLR 2025
for any E (0, 1). Notice that, while this bound is for the case W(u, (0,, .x) o 0. it subsumes the bound for the case W (u, 0 2) = 9 (Equation 67 Then, using d(u, 2) I T, we get Equation 54 This completes the proof for random restarts.
We now prove for periodic restarts. If the walk starting at u reaches r before restarting at v, the steps taken is clearly less than k. If the walk starting needs to reach x from v, while restarting at v at every h steps. Let T be the steps taken to reach x from v. Let T" be the number of steps until the walk restarts at v, then exactly follows the shortest path from v to æ for the first time, and then restarts at U. It is clear that B[T] < E[T". Then, we split the walk of length T" into N trials, where each trial consists of restarting at v and walking steps until the next restart. A trial is successful if it immediately walks the shortest path from v to J. Then N' is the number of trials until we get success, and it follows geometric distribution with probability of success at least (d))(( only for k 2 d(v, x), and zero for k < d(v, x) since the walk cannot reach x before restart. Hence, its expectation
restarts at step l before reaching æ; it now
most A Ad(x,)) for 2 d(v, and
have E[T] < [T[ [N] s A d(v.x), Adding the k steps until the first restart at U, we have:
H(, x) S k KA d(o,a)
(74)
for any A: 2 d(), Using d(v, S r, we get Equation 55
This completes the proof.
L
We now extend Lemma A.4 to edges. Let Huu, (ar, v)) be the expected number of steps of a random
walk starting at u takes until traversing an edge (Ir, y) by x -> y. We show that (u, v)) is finite for any u and adjacent æ. y in (v) for any nonzero restart probability or restart period k: 2 r + 1.
Lemma A.5. For any u and adjacent x, y in (v), Hu, (I, y)) is bounded by the following:
(z. - a _ (1=))
+ a a (a-1) (1-a)
2c+1
(75)
if the random walk restarts at u with any probability (0,1), 1), and:
(u, (x. y)) S k + k1"+1 ++ if the random walk restarts at e with any period k 2 r + 1.
(76)
Proof. The proof is almost identical to Lemma A.4 except the target x of reaching is substituted by (ar, y) in the direction of x - y, and all arguments that use the shortest path from u or instead use the shortest path to r postfixed by x + V. 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 with any nonzero probability a or any period k 2 r + 1, the vertex and edge cover times of (,(v) are always finite.
Proof. The proof is inspired by the spanning tree argument of Alcliunas et al. (1979). Let us consider depth first scarch of (v) starting from v. We denote by T the resulting spanning tree with vertices V(T)= = V(B, vertex in the precise order visited by the depth first search by traversing each edge twice. It is clear that this upper-bounds the vertex cover time of Br (v) starting at v (Equation 18
We consider the expected time for a random walk starting at v to visit every
Cv,( S
Σ
[ v) + H(y.
(77)
(2.))E
Then, using the bounds from Lemma A.4
the property of spanning trees [E(T) (V(T)) 1, and from bounded degree, we obtain:
the fact that (V()) = (u))
< A
1 a
1 a
1)
2r
(v( 1)
(78)
a
a
the random walk restarts at v with any probability a E (0, 1), and:
(B,( 22(2- 1)(k kA"),
(79)
45

---

Published as a conference paper at ICLR 2025
if the random walk restarts with any period k This completes the proof for the vertex cover time. For the edge cover time, we consider the expected time for random walk starting at v to visit every edge in the precise order discovered" by the depth first search by traversing each edge twice. It clear that this upper-hounds the edge cover time of B, (v) starting at o (Equation 19).
Ce(B((v)) S
Σ
(H (I, + (V, (v, x)]]
(80)
B(,)EE(B,(O)
Then, using Lemma
A.4 and the fact that (E(, - A from bounded degree, we obtain:
Cr:(B(u)) s 2( 1) - a (Taa
r+
1
-1
1 a )
A 21+1
(81)
the random walk restarts at v with any probability a E (0, 1), and:
(E)) & 2(A 1) (A: + *
(82)
if the random walk restarts at v with any period & 2 r + 1. This completes the proof.
While our proof shows finite bounds for the cover times, it possible that they can be made tighter, for instance based on Zuckerman 1991). We leave improving the bounds as a future work.
A.9.7 PROOF OF THEOREM 3.2 (SECTION 3.1)
We recall universal approximation of graph-level functions in probability (Definition 3.1
We say (-)+) is universal approximator of graph-level functions in probability if. for all invariant functions & : G, + R. for a given n 2 1. and Ve, 5 > 0, there exist choices of length I of the random walk and network parameters 9 such that the following holds:
Definition 3.1
Probllø(G) Xo(G)) < 1- -, VG E G..
(83)
We remark that RWNN Xo(.) is composed of random walk algorithm, recording function q: (wo + .... v1, G) > z, and a reader neural network fo = y E TR.
Intuitively, if the record of the random walk always provides complete information of the input graph G, we may invoke universal approximation of fa to always obtain (Ø(G) - [z() < e, and thus lø(G) - Xx)
e. However, this is not always true the random walk may e.g. fail to visit some vertices of G, in which case the record z would be incomplete. As we show below, this uncertainty leads the probabilistic bound > 8 of the approximation.
Let us denote the collection of all possible random walk records as {z} == Range(q) (q), and consider a decoding function &o : {z} + Gn that takes the record walk f7.) and outputs the graph (z))) E G, composed of all recorded vertices V V(H) = fid(v.) Ve E {vo.... } and all recorded edges E(H) C (HH) x V(H). We show the following lemma:
q(v0 + .... - Ut, G') of given random
Lemma A.6. Let G2 be the subgraph of G whose vertices and edges are recorded by z. Then the graph (z)) decoded from the record z is isomorphic to G2 through the namespace id(-):
id
G₂
(z).
(84)
Furthermore, the decoded graph (2) reconstructs G up to isomorphism, that is,
id (z),
(85)
if the recording functtion q(-) and the random walk the satisfies either of the following:
q(-) uses anonymization, and fia has traversed all edges of G.
q(+) uses anonymization and named neighbors, and fin has visited all vertices of G.
We remark that depth first search discovers all edges of graph, while necessarily visiting all of them.
46

---

Published as a conference paper at ICLR 2025
Proof. Equation 84 straightforward from the fact that the namespace id(-) defines a bijection from V(G2) to Gl], and the recording function uses names id(e) to record vertices and edges. Equation 85 is satisfied when all vertices and edges of G' have been recorded, i.e., G2 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 neighbors 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:
E
Prob/T 2 a] -
(86)
We are now ready prove Theorem 3.2
Theorem 3.2. An RWNN x-(-) with sufficiently powerful fo is universal approximator of graph-llevel in probability (Definition } it satisfies either of the below:
It uses anonymization to record random walks of lengths 1 CB(G)/88.
It uses anonymization and named neighbors to record walks of lengths I Cv(
Proof. Instead of directly approximating the target function Φ G, - R. it is convenient to define proxy target function on random walk records @' {z] - R where {z} = Range(4) as follows:
o'
o v
(87)
where # : {z} -> Gn is the decoding function of walk records. Then, for a given z, we have:
C=dd())
(G) (2(2,,
(88)
which is because Φ is an invariant function, so (GG) = (z)(z)) ((v()) = 6 (z) o' (z). Then we have: Prob[G = (z)) S Prob|lo(G) o' o'(z)l 0].
(89)
We now invoke universality of So to approximate ø'. If Sa is universal approximator of functions on its domain {z) = Range(q), (4), for any >> there exists a choice of 0 such that the below holds:
(z(()) fa(z) <e,
Vz E Range(g).
(90)
Combining Equations 89 and 90, we have:
Prob[G (z)) S Prob[ld(G) o (2)) + So(2)] <c].
(91)
We remark triangle inequality of distances on R, for a given z:
(e(G) - fa(z)) S (dG (z))+ fo(2))
(92)
which implies. for given z:
(Ø(G) - 0' (z)) + (z() so(2)] <c
(Ø(G) fo(z)] <G
(93)
and hence:
Probllo(G) - 6zzz) + (z) - fo(z)) < d < Prob[lo(G) fo(z)] <c..
(94)
Combining Equations 91 and 94] we have:
Prob[lo(G) fo(2) < > ProbiG ~ ((2)),
(95)
which can be written follows:
Prob[lø(G) - Xe(G) (x(())))xGG) < < 2 Prob[G ~ {z))
(96)
We now consider the probability of the event G (z) based on Lemma We first consider the case where the recording function g(.) uses anonymization. In this case, G = (z) is achieved if the random walk of length has traversed all edges of G. Let TF(G, on) be the number of steps that a
random walk starting at vo takes until traversing all edges of G. Since the edge cover time (p(G) is its expectation taken at the worst possible starting vertex (Equation]) we have the following:
E E[Te(G, vo)] CE(G),
VoD V(G),
(97)
47

---

Published as a conference paper at ICLR 2025
which leads to the following from Markov's inequality (Equation 86):
Prob[TE(G, vo) 2 [[T
CE(G)
(98)
For given random walk to + - uy and record z, the following holds:
TE(G, ub) <1 = G G=v(z))
(99)
which implies the following:
Prob[Te(G, vo) <1 Prob = [/(z]]
(100)
Combining Equations 96
98
and 100 we have:
Prob[lø(G) Xx(G)) < CE(G)
(101)
Therefore, for any > 0, if we choose Cg(G)/8 we would have the following:
Prob]lø(G) Xo(G) < c) 1
(102)
This completes the proof for anonymization. The proof is identical for the recording function that uses anonymization and named neighbors, except that the edge cover time is changed to the vertex cover time Cv(G)) (Equation [6]. This is because named neighbor recording automatically records the induced subgraph of visited vertices, thus visiting all vertices implies recording all edges. G(V = G.
A.9.8 PROOF OF THEOREM 3.4 (SECTION 3.1
Theorem 3.4 An RWNN Xa(.) with sufficiently powerful So and any nonzero restart probubility or restarl period l 2 + + is universal upproximator of vertex-level functions in probability (Definition 3.3 if satisfies either of the below for all (v) By:
It uses anonymization to record random walks of lengths 1 C
Il uses anonymization and named neighbors record walks of lengths I (B,
Proof. The proof is almost identical to Theorem 3.2 except G E G, are substituted by B, (v) By, and the decoding function & (z] - TB, is defined to ignore all recorded vertices id(x) whose shortest path distance from the starting vertex id(v) id(vo)
exceeds The latter is necessary to restrict the range the decoding function v to B,. addition, any nonzero restart probability a restart period k 2 + is sufficient make the cover times CB(B,(v) (x))) and (v(B((r) finite (Theorem 2.3 thereby guaranteeing the existence of a finite choice
A.9.9
PROOF THEOREM 3.3 (SECTION 3.2)
Theorem 3.5
The simple RWNN outputs h + x as + oc.
Proof. Since is connected and non- bin-bipar the uniform random walk on it defines an ergodic Markov chain with unique stationary distribution æ. The limiting frequency of visits on each vertex is precisely the stationary probability n. Since the model reads X - - X by average pooling, the output is given by weighted mean Σ. x, which is x π.
A.9.10 PROOF OF THEOREM 3.6 (SECTION 3.2
Theorem 3.6 Let ha be output of the simple RWNN queried with u. Then:
(
ih
pt
+ n
as
1 1 oc.
(103)
xx,
[=
48

---

Published as a conference paper at ICLR 2025
+ Xx, by average pooling, the feature Jacobian jāhă ! /xx
Proof. Since the model reads X is given as number of visits to the vertex u in the random walk vp - ... - starting at vp u, divided by length + 1. Let us denote the expected number of these visits by [u, v, f). Let Le,=v be the indicator function that equals if Up and otherwise. Then we can write (u, v, () as:
Ju, 21 = E
Σ 1==
1 02
=
100
Σ
00 u].
(104)
We have used linearity expectations for the second equality. 1, = u] the probability of being at at step / given that the walk started at u. This probability is precisely [P*]ue Therefore:
J(,
Pd
p
(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 и.
The limiting frequency of visits on vertex is precisely the stationary probability T., which gives the convergence in Equation 103 This completes the proof.
L
49

---

Published as a conference paper at ICLR 2025
A. EXTENDED RELATED WORK (SECTION 4
Anonymized random walks (Micali & Zhu 2016) The initial work on anonymization by Micali & Zhu (2016) has stated an important result, that a sufficiently long anonymized walk starting from a vertex e encodes sufficient information to reconstruct the local subgraph (v) up to isomorphism. While the focus of Micali & Zhu (2016) was a probabilistic graph reconstruction algorithm that uses set of independent anonymized walks and accesses the oracle set of all possible anonymized walks, we adopt the idea in a neural processing context to acquire universality in probability (Section 3.1). In addition, the invariance property of anonymization has rarely been noticed formally in the literature, which is our key motivation for using it, on top of being able to recover the whole graph (Section 2
In-depth comparison with CRaWI Tonshoff et al. 2023) Our approach is related to CRaWI in two key aspects: (1) identity and connectivity encodings of CRaWI contains analogous information to anonymization and named neighbor recording, respectively, and (2) CRaWI uses 1D CNNs as the reader NN. A key technical difference lies in the first part. The identity and connectivity encodings of CRaWl are defined within a fixed window size (denoted 8 in (Tönshoff et al., 2023)), which puts a locality constraint on the recorded information. Precisely, the encodings at step can encode the information of the walk from step t - s to (precisely, its induced subgraph), referred to as walklet. The window size is a hyperparameter that controls the expressive power of CRa (I, and this dependency makes CRaWI non-universal (Section 3.2, (Tönshoff et al.) 2023). Our choice of anonymization and named neighbor recording are not under such a local constraint, and they encode the full information of a given walk globally. This property underlies our universality results in Section 3.1 which also naturally motivates our choice of universal reader NNs, e.g. a transformer language model, which were not explicitly considered in CRaWI.
Random walks on graphs Our work builds upon theory of random walks graphs, i.e., Markov
chains on discrete spaces. Their statistical properties such as hitting and mixing times have been well-
studied (Aleliunas et al. [979; Lovász
1993 Coppersmith et al.. 1996 Feige [995 Oliveira
2012
Peres & Sousi 2015), and our Section 2 is related to vertex cover time (Alelinnas et al. 1979
Kahn
al. 1989 Ding et al. 2011 Abdullah, (012), edge cover time (Zuckerann 1991| Bussian 1996
Panotopoulou 2013: Georgakopoulos & Winkler, 2014). and improving them, using local degree
information (Ikeda et al. Abdullahh et al. 2015 David & Feige 2018), non-backtracking (Alon
ct al. 2007 Kempton| [016] Arrgo et al. Fasio Fasino et al. (021). or restarts (Dumitriu et al. 2003
McNew] 2anson & Peres 2012). Our work is also inspired by graph algorithms based on random
walks, such as anonymous observation (Micali & Zhu 2016), sublinear algorithms (Dasgupta et al.
2014| Chiericett et al. 2016, BBen-Hamou et al. 2018 Bera & Seshadhri 2020)) and personalized
PageRank for search (Page et al. 1999) and message passing (Gasteiger et al. 2019). While we adopt their techniques to make our walks and their records well-behaved, the difference is that we use a non-linear deep neural network to process the records and directly make predictions. Our method is also related to label propagation algorithms (Zhu & Ghahramani] [002 Zhu 2005 Grady (006) that
perform transductive learning on graphs based on random walks, have discussed in Section 5.3
Over-smoothing and over-squashing Prior work on over-smoothing and over-squashing of
MPNNs (Barceló et al.] 2020; Topping et al., 2022] Giovanni et al.) 2023] Giraldo et al.) 2023
Black et al. [023] Nguyen et al.
20233] Park et al. 2023 Wu et al. (2023) often make use of structural
properties of graphs, such as effective resistance (Dyyle & Snell 1984 Chandra et al.) 1997). Lapla-
cian eigen-spectrum (Lovász) 1993) Spielman| 2019), and discrete Ricci curvatures Ollivier 2009)
Devriendt & Lambiotte| 2022 Interestingly, random walks and their statistical properties are often closely related to these properties, indicating some form of parallelism between MPNNs and RWNNs. This has motivated our analysis in Section 3.2 where we transfer the prior results on over-smoothing and over-squashing of MPNNs based on these properties into the results on our approach.
Unlike the MPNNs considered in the above prior work, AMP (Errica et al. 2023) mitigates over- smoothing and over-squashing by learning to prune messages at each step (among its other techniques). This brings it close to attention-based MPNNs, which can be understood as modifying the computation (P in Section 3.2) over topology. Indeed, our description of moothhng and squrshig in
MPNNs in Section 3.2 mainly applies to message passing using fixed weights, and attention falls
out of this framework, which is a shared limitation with prior work (Topping et al., 2022] Giraldo
et al.
2023
Black al. 2023
Nguyen et al. 2023). Formal propagation analysis for attention-based
50

---

Published as a conference paper at ICLR 2025
MPNNS is currently in its infancy (Wu et al. 2023). but we believe it is interesting since, based on parallelism between MPNNs and RWNNs, it may tell us about how to adapt the walk probabilities adaptively based on input data. We leave investigating this as future work.
Language models for learning on graphs While not based on random walks, there have been prior attempts on applying language models for problems on graphs (Wang al. 2023 Chen et 2023 Zhao et al. 2023) Fatemi et al.) [023] Ye et al. 2024), 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 the related tasks, e.g. graph separation. We believe extending our work to simulating graph algorithms requires careful treatment (Weiss al.) |021| Delétang al.] 2023 de Luca & Fountoulakis, 2024 Sanford ct al. 2024) and plan to investigate it as future work.
A.11 LIMITATIONS AND FUTURE WORK
Our current main limitation is the cost of performing training and inference using language models, especially on long walks, While random walk sampling and text recording can be done efficiently, the main computational bottleneck comes from the use of language models as the reader NN. For example, in Section 5.3 each test prediction of CWNN-LLama-3-7700 takes around 0.410 + 0.058 is faster, 0. + 0.064 seconds per prediction). The inference time of standard MPNNs are much shorter, e.g., a 3-layer GAT with 16 hidden dimensions takes around one second for all test vertices of ogbn-arxiv on a V100 GPU (Wang et al., 2019). Overcoming this issue is important future direction. We remark that, if language model embeddings are used and fine-tuned, the training cost of MPNNs can also be substantial, c.g., recent work has reported that prior methods for training MPNN jointly with language model embeddings on arXiv take 25-46 hours on a 6x RTX 3090 machine (Table 3 of Zhu et al. (024)).
seconds on a 4x H100 machine (RWNN-Llama-3)
On the theory side, focus pendix[A.8) which corresponds to the worst-case length bounds required for universal approximation. Yet, in practice, there is substantial amount of useful information that be already recovered from possibly non-covering walks. Examples include spectral properties (Benjamini et al., (206),006) number of edges and mixing time [Ben-Hamou et al.) 2018), and triangle counts (Bera & Seshadhri, 2020)). among others studied in the field of sublinear algorithms. These results suggest that shorter walks may suffice in practice for RWNNs, the task at hand requires properties that can be estimated without seeing the whole graph, and the reader NN can learn to recover them (e.g., leveraging universality). Understanding this aspect better is an important direction for future work.
times of random walks in analysis (Section 3.1 and Ap-
Another question for future work is whether we can train a language model on large pseudocorpus of random walks (Klubicka et al., 2019 2020) to build a foundation model for graphs which language-compatible We plan to investigate this direction in the future.
51


Reviews:
[{"review_id": "GXW8JyApyi", "reviewer": "Reviewer_R47c", "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. \n\nOn 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.", "questions": "Is there a simple intuitive reason why RWNN also outputs something based on the stationary vector in Thm 3.5?\n\nwould it be possible to include Crawl and WalkLM in Table2? As those seem to be the only two methods to compare to..\n\nI would be very interested in graph learning performance, especially since Crawl was surprisingly good there.\n\nWould 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.\n\nIs there anything to say about cases where walks do not cover the whole graph?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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).\n\nThe theoretical results seem sound too.", "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.\n\nThe 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. \n\nThere 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.\n\nCode 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).\n\nDetails: \n- Grammar/Structure in 87ff is off. especially: \"given that...\" and \"The result also...\"\n- Table 3/4: maybe just put the link to the reference on the method name to avoid the cluttered look of the table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VEeXbMnyYC", "reviewer": "Reviewer_8Hx8", "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.", "questions": "1. Can you include results on real-world graph-level datasets? I think only evaluating graph-level synthetic datasets is a bit restrictive.\n\n2. 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem is interesting, and using llms to process outputs from the recording function makes the results more practical and significant.", "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.\n\nGenerally 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.\n\n\nSrinivasan and Ribeiro, 2020. On the Equivalence between Positional Node Embeddings and Structural Graph Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JpszVkDvJo", "reviewer": "Reviewer_RBkC", "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.\n\nThe 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.\n\nAn 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.", "questions": "* What is the inference cost for RWNN-Llama in section 5.3? How does it compare to inductive GNN-based approaches?\n* 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? \n* What walk length and restart probabilities are used in sections 5.2 and 5.3?\n* 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 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.\n* 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.", "weaknesses": "While I think the theoretical contributions are significant, I think the experiment section lacks some details that would improve the paper:\n\n* 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.\n\n* 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.\n\n*  The main walk hyperparameters (length and restart probability) are not specified in Sections 5.2 and 5.3.\n\nThere are also some grammatical mistakes that would benefit from a spell checker.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7Lp6wm1ubb", "reviewer": "Reviewer_J6pj", "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).", "questions": "These are mostly related to typos and requests for modification\n  - 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\n  - Line 53: should it be “Addressing such questions is important”?\n  - 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\n  - 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?\n  - 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).\n  - Figure 3: what are colors and lines? The authors should improve the figure a bit by adding a legend.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "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. \n\nIntuitive 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.\n\nThe 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.\n\nThe authors also took care of efficiently implementing the core of their method so as to speed up the computation of random walks.", "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.\n\nI 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.\n\nAnother 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.\n\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)