1 Introduction↩︎

Message passing neural networks (MPNNs) are a popular class of neural networks on graphs where each vertex keeps a feature vector and updates it by propagating messages over neighbors [1]. [2]–[4] MPNNs have achieved success, with one reason being their respect for the natural symmetries of graph problems (i.e., invariance to graph isomorphism) [5]. On the other hand, MPNNs in their basic form can be viewed as implementing color updates of the Weisfeiler-Lehman (1-WL) graph isomorphism test, and thus their expressive power is not stronger [6]. [7] Also, their inner workings are often tied to the topology of the input graph, which is related to over-smoothing, over-squashing, and under-reaching of features under mixing [8].

In this work, we revisit an alternative direction for learning on graphs, where a random walk on a graph produces a machine-readable record, and this record is processed by a deep neural network that directly makes 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 [9] and node2vec [10], which use skip-gram on walks, AWE [11], which uses embeddings of anonymized walks [12], and CRaWl [13], which uses 1D 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 [13], [14].

Despite the potential, unlike MPNNs, we have not yet reached a good principled understanding of RWNNs. First, from the viewpoint of geometric deep learning, it is unclear how we can systematically incorporate the symmetries of graph problems into RWNNs, as their neural networks are 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.

max width=0.87

1.0.0.1 Contributions

We aim to establish a principled understanding of RWNNs with a focus on the previously stated questions. Our starting point is a new formalization of RWNNs which decouples random walks, their records, and neural networks that process them. This abstracts a wide range of design choices including those of prior methods, as in Table ¿tbl:table:prior95work?. Our key idea for the analysis is then to understand RWNNs through a combination of two recent perspectives in geometric deep learning: probabilistic notions of invariance and expressive power [15], [16], and invariant projection of non-invariant neural networks [17], [18].

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 [12] and our novel extension of it 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 1).

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 on designing random walks to minimize or bound the cover times. From this we motivate a novel adaptation of minimum degree local rule (MDLR) walks [19] for RWNNs, and introduce restarts when working on a large and possibly infinite graph. We also provide a justification for the widespread use of non-backtracking [13].

Continuing the link to Markov chain theory, we further analyze RWNNs and establish a parallelism to a linearized model of MPNNs. From this, we show that over-smoothing in MPNNs is 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 [8], [20], and allows an RWNN to focus on overcoming under-reaching by scaling the walk length or using rapidly-mixing random walks such as non-backtracking 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-smoothing, and over-squashing. Then, we demonstrate adapting a language model (DeBERTa [21] 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 on a large graph into an in-context learning problem by recording labeled vertices during random walks. To demonstrate this, we apply Llama 3 [22] model on transductive classification on 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.

2 Random Walk Neural Networks↩︎

We start our discussion by formalizing random walk neural networks (RWNNs). We define an RWNN as a randomized function \(X_\theta(\cdot)\) that takes a graph \(G\) as input and outputs a random variable \(X_\theta(G)\) on the output space \(\mathbb{R}^d\).⁴ In the case of vertex-level tasks, it is additionally queried with an input vertex \(v\) which gives a random variable \(X_\theta(G, v)\). An RWNN consists of the following components:

1. Random walk algorithm that produces \(l\) steps of vertex transitions \(v_0\to\cdots\to v_l\) on the input graph \(G\). If an input vertex \(v\) is given, we fix the starting vertex by \(v_0=v\).

2. Recording function \(q: (v_0\to\cdots\to v_l, G)\mapsto\mathbf{z}\) that produces a machine-readable record \(\mathbf{z}\) of the random walk. It may access the graph \(G\) to record auxiliary information such as attributes.

3. Reader neural network \(f_\theta:\mathbf{z}\mapsto\hat{\mathbf{y}}\) that processes record \(\mathbf{z}\) and outputs a prediction \(\hat{\mathbf{y}}\) in \(\mathbb{R}^d\). It is the only trainable component and is not restricted to specific architectures.

For graph-level prediction, we sample \(\hat{\mathbf{y}}\sim X_\theta(G)\) by running a random walk on \(G\) and processing its record using the reader NN \(f_\theta\). For vertex-level prediction \(\hat{\mathbf{y}}\sim X_\theta(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 \((\cdot)\mapsto\mathbb{E}[X_\theta(\cdot)]\).

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 as in transductive classification. As our definition captures many known designs (Table ¿tbl:table:prior95work?), we discuss them as well. We leave the pseudocode in Appendix 7.2 and notations and proofs in Appendix 7.9.

2.1 Graph-Level Tasks↩︎

Let \(\mathbb{G}\) be the class of undirected, connected, and simple graphs⁵. Let \(n\geq 1\) and \(\mathbb{G}_n\) be the collection of graphs in \(\mathbb{G}\) with at most \(n\) vertices. Our goal is to model a graph-level function \(\phi:\mathbb{G}_n\to\mathbb{R}^d\) using an RWNN \(X_\theta(\cdot)\). Since \(\phi\) is a graph function, it is reasonable to assume isomorphism invariance: \[\begin{align} \label{eq:graph95level95invariance} \phi(G) = \phi(H),\quad\forall G\simeq H, \end{align}\tag{1}\] Incorporating the invariance structure to our model class \(X_\theta(\cdot)\) would offer generalization benefit. As \(X_\theta(\cdot)\) is randomized, we accept the probabilistic notion of invariance [15]: \[\begin{align} \label{eq:graph95level95probabilistic95invariance} X_\theta(G)\overset{d}{=}X_\theta(H),\quad\forall G\simeq H. \end{align}\tag{2}\] An intuitive justification is that, if \(X_\theta(\cdot)\) is invariant in probability, its mean predictor \((\cdot)\mapsto\mathbb{E}[X_\theta(\cdot)]\) would be an invariant function (we leave further discussion in Section 4). We now claim that we can achieve probabilistic invariance of \(X_\theta(\cdot)\) by properly choosing the random walk algorithm and recording function while not imposing any constraint on the reader NN \(f_\theta\).

In other words, even if \(f_\theta\) lacks symmetry, invariant random walk and recording function provably converts it into an invariant random variable \(X_\theta(\cdot)\). This is an extension of invariant projection operators on functions [17], [18] to a more general and probabilistic setup.

2.1.0.1 Random walk algorithm

A random walk algorithm is invariant in probability if it satisfies: \[\begin{align} \label{eq:random95walk95invariance} \pi(v_0)\to\cdots\to\pi(v_l)\overset{d}{=}u_0\to\cdots\to u_l,\quad\forall G\overset{\pi}{\simeq}H, \end{align}\tag{3}\] where \(v_{[\cdot]}\) is a random walk on \(G\), \(u_{[\cdot]}\) is a random walk on \(H\), and \(\pi:V(G)\to V(H)\) specifies the isomorphism from \(G\) to \(H\). It turns out that many random walk algorithms in literature are already invariant. To see this, let us write the probability of walking from a vertex \(u\) to its neighbor \(x\in N(u)\): \[\begin{align} \label{eq:first95order95random95walk} \mathrm{Prob}[v_t=x|v_{t-1}=u] \coloneq \frac{c_G(u, x)}{\sum_{y\in N(u)}c_G(u, y)}, \end{align}\tag{4}\] where the function \(c_{G}: E(G)\to\mathbb{R}_+\) assigns positive weights (conductances) to edges. If we set \(c_G(\cdot)=1\), we recover uniform random walk used in DeepWalk [9]. We show:

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) [19], [23] is particularly useful: \[\begin{align} \label{eq:minimum95degree95local95rule} c_G(u, v) \coloneq \frac{1}{\min[\mathrm{deg}(u), \mathrm{deg}(v)]}. \end{align}\tag{5}\] MDLR is special as its vertex cover time, i.e., the expected time of visiting all \(n\) vertices of a graph, is \(O(n^2)\), optimal among first-order random walks (Equation 4 ) that use degrees of endpoints.

A common practice is to add non-backtracking property that enforces \(v_{t+1}\neq v_{t-1}\) [13], and we also find this beneficial. In Appendix 7.1 we extend Equation 3 and Proposition 2 to second-order walks that include non-backtracking and node2vec walks [10].

2.1.0.2 Recording function

A recording function \(q: (v_0\to\cdots\to v_l, G)\mapsto\mathbf{z}\) takes a random walk and produces a machine-readable record \(\mathbf{z}\). We let \(q(\cdot, G)\) have access to the graph \(G\) the walk is taking place. This allows recording auxiliary information such as vertex or edge attributes. A recording function is invariant if it satisfies the following for any given random walk \(v_{[\cdot]}\) on \(G\): \[\begin{align} \label{eq:recording95invariance} q(v_0\to\cdots\to v_l, G) = q(\pi(v_0)\to\cdots\to\pi(v_l), H),\quad\forall G\overset{\pi}{\simeq}H. \end{align}\tag{6}\] Invariance requires that \(q(\cdot, G)\) produces the same record \(\mathbf{z}\) regardless of re-indexing of vertices of \(G\) into \(H\). For this, we have to be careful in how we represent each vertex in a walk \(v_0\to\cdots\to v_l\) as a machine-readable value, and which auxiliary information we record from \(G\). For example, identity recording used in DeepWalk [9] and node2vec [10] are not invariant as the result is sensitive to vertex re-indexing. We highlight two choices which are invariant:

• Anonymization. We name each vertex in a walk with a unique integer, starting from \(v_0\mapsto1\) and incrementing it based on their order of discovery. For instance, a random walk \(a\to b\to c\to a\) translates to a sequence \(1\to2\to3\to1\).

• Anonymization + named neighbors. While applying anonymization for each vertex \(v\) in a walk, we record its neighbors \(u\in N(v)\) if they are already named but the edge \(v\to u\) has not been recorded yet. For instance, a walk \(a\to b\to c\to d\) on a fully-connected graph translates to a sequence \(1\to2\to3\langle1\rangle\to4\langle1, 2\rangle\), where \(\langle\cdot\rangle\) represents the named neighbors.

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

While anonymization was originally motivated by privacy concerns in [12] (see also Appendix 7.10), Proposition 3 offers a 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 [24]. In our context, it is useful since whenever a walk visits a set of vertices \(S\subseteq V(G)\) it automatically records the entire induced subgraph \(G[S]\). As a result, to record all edges of a graph, a walk only has to visit all vertices. While traversing all edges, i.e. edge cover time, is \(O(n^3)\) [25] in general, it is possible to choose a walk algorithm that takes only \(O(n^2)\) time to visit all \(n\) vertices. MDLR in Equation 5 exactly achieves this.

2.1.0.3 Reader neural network

A reader neural network \(f_\theta:\mathbf{z}\mapsto\hat{\mathbf{y}}\) processes the record \(\mathbf{z}\) of the random walk and outputs a prediction \(\hat{\mathbf{y}}\) in \(\mathbb{R}^d\). As in Proposition 1, there is no invariance constraint imposed on \(f_\theta\), and any neural network that accepts the recorded walks and has a sufficient expressive power can be used (we will make this precise in Section 3.1). This is in contrast to MPNNs where invariance is hard-coded in feature mixing operations. Also, our record \(\mathbf{z}\) can take any format, such as a matrix, byte sequence, or plain text, as long as \(f_\theta\) accepts it. Thus, it is possible (while not required) to choose the record to be plain text, such as "1-2-3-1", and choose \(f_\theta\) to be a pre-trained language model. This offers expressive power [26] and has a potential benefit of knowledge transfer from the language domain [27], [28].

2.2 Vertex-Level Tasks↩︎

We now consider vertex-level tasks. In case of finite (small) graphs, we may simply frame a vertex-level task \((G, v)\mapsto\mathbf{y}\) as a graph-level task \(G'\mapsto\mathbf{y}\) where \(G'\) is \(G\) with its vertex \(v\) marked. Then, we can solve \(G'\mapsto\mathbf{y}\) by querying an RWNN \(X_\theta(G, v)\) to start its walk at \(v_0=v\).

A more interesting case is when \(G\) is an infinite graph that is only locally finite, i.e. has finite degrees. This simulates problems on a large graph such as transductive classification. In this case, we may assume that our target function depends on finite local structures [29].

Let \(r\geq 1\), and \(\mathbb{B}_r\coloneq\{B_r(v)\}\) be the collection of local balls in \(G\) of radius \(r\) centered at \(v\in V(G)\). We would like to model a vertex-level function \(\phi:\mathbb{B}_r\to\mathbb{R}^d\) on \(G\) using an RWNN \(X_\theta(\cdot)\) by querying the vertex of interest, \(X_\theta(G, v)\). We assume that \(\phi\) is isomorphism invariant: \[\begin{align} \phi(B_r(v))=\phi(B_r(u)),\quad\forall B_r(v)\simeq B_r(u). \end{align}\] The probabilistic invariance of \(X_\theta(\cdot)\) is defined as follows: \[\begin{align} X_\theta(G, v)\overset{d}{=}X_\theta(G, u),\quad\forall B_r(v)\simeq B_r(u). \end{align}\] We can achieve probabilistic invariance by choosing the walk algorithm and recording function similar to the graph-level case⁶. As a modification, we query \(X_\theta(G, v)\) with the starting vertex \(v_0=v\) of the random walk. Anonymization informs \(v\) to the reader 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 \(v_0\) either with a probability \(\alpha\in(0, 1)\) at each step or periodically every \(k\) steps. Restarting walks tend to stay more around starting vertex \(v_0\), and were used to implement locality bias in personalized PageRank algorithm for search [30]. This localizing effect is crucial in our context since a walk can drift away from \(B_r(v_0)\) before recording all necessary information, which may take an infinite time to return as \(G\) is infinite [31]. Restarts make the return to \(v_0\) mandatory, ensuring that \(B_r(v_0)\) can be recorded in a finite expected time. We show:

3 Analysis↩︎

In Section 2, we have described the design of RWNNs, primarily relying on the principle of (probabilistic) 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↩︎

[32] Intuitively, if the records of random walks contain enough information such that the structures of interest, e.g., graph \(G\) or local ball \(B_r(v)\), can be fully recovered, a powerful reader NN such as an MLP [33] or a transformer [26] on these records would be able to approximate any function of interest. Our analysis formalizes this intuition.

We first consider using an RWNN \(X_\theta(\cdot)\) to universally approximate graph-level functions \(\phi(\cdot)\) in probability, as defined in [16].

We show that, if the random walk is long enough and the reader NN \(f_\theta\) is universal, an RWNN \(X_\theta(\cdot)\) is capable of graph-level universal approximation. The length of the walk \(l\) controls the confidence \(>1-\delta\), with edge cover time \(C_E(G)\) or vertex cover time \(C_V(G)\) playing a central role.

While both cover times are \(O(n^3)\) for uniform random walks [25], [34], we can use MDLR in Equation 5 to achieve an \(O(n^2)\) vertex cover time, in conjunction with named neighbors recording. While universality can be in principle achieved with uniform random walks, our design reduces the worst-case length \(l\) required for the desired reliability \(>1-\delta\).

We now show an analogous result for the universal approximation of vertex-level functions.

Accordingly, using local vertex cover time \(C_V(B_r(v))\) and edge cover time \(C_E(B_r(v))\), we show:

Since restarts are required to 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-reaching↩︎

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 a range of prior work has shown how this relates to the well-known issues of over-smoothing, 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-bipartite graph with row-normalized adjacency matrix \(P\). We consider a linearized MPNN, where the vertex features \(\mathbf{h}^{(0)}\) are initialized as some probability vector \(\mathbf{x}\), and updated by \(\mathbf{h}^{(t+1)}=\mathbf{h}^{(t)}P\). This simplification is often useful in understanding the aforementioned issues [8], [35]. Specifically, in this model:

• Over-smoothing happens as the features exponentially converge to a stationary vector \(\mathbf{h}^{(l)}\to\boldsymbol{\pi}\) as \(l\to\infty\), smoothing out the input \(\mathbf{x}\) [8].

• Over-squashing and under-reaching occur when a feature \(\mathbf{h}_u^{(l)}\) becomes insensitive to distant input \(\mathbf{x}_v\). While under-reaching refers to insufficient depth \(l<\mathrm{diam}(G)\) [36], over-squashing refers to features getting overly compressed at bottlenecks of \(G\), even with sufficient depth \(l\). The latter is described by the Jacobian \(|\partial \mathbf{h}_u^{(l)}/\partial \mathbf{x}_v|\leq [\sum_{t=0}^lP^t]_{uv}\),⁷ as the bound often decays exponentially with \(l\) [37], [38].

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

We consider a simple RWNN that runs a uniform random walk \(v_0\to\cdots\to v_l\), reads the record \(\mathbf{x}_{v_0}\to\cdots\to\mathbf{x}_{v_l}\) by averaging, and outputs it as \(\mathbf{h}^{(l)}\). Like linear MPNN, the model involves \(l\) steps 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 as in simple MPNNs⁸:

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

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

The equation shows that the feature Jacobians are bounded by the sum of powers of \(P\), same as 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 [38], in RWNNs it is related to exponentially decaying probability of reaching a distant vertex \(v\), i.e., probabilistic under-reaching.

In many MPNNs, it is understood that the topology of the input graph inevitably induces a trade-off between over-smoothing and over-squashing [8], [20]. 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 5 ) and non-backtracking [39] can be understood as achieving this.

4 Related Work↩︎

We briefly review the related work. An extended discussion can be found in Appendix 7.10.

4.0.0.1 Random walks for learning on graphs

In graph learning, random walks have received interest due to their compatibility with sequence learning methods (Table ¿tbl:table:prior95work?). DeepWalk [9] and node2vec [10] used skip-gram models on walks. CRaWl [13] used 1D CNN on sliding window-based walk records, with expressive power bounded by the window size. We discuss the relation between CRaWl and our approach in depth in Appendix 7.10. AgentNet [14] learns agents that walk on a 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 [40] proposed a fine-tuning method for language models on 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 [41] has arrived at a similar use of anonymization combined with RNNs.

4.0.0.2 Probabilistic invariant neural networks

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

5 Experiments↩︎

[54]–[58] We perform a set of experiments to demonstrate RWNNs. We implement random walks in C++ based on [59], which produces good throughput (\(<\)​0.1 seconds for 10k steps) without using GPUs as in [13]; pseudocode is in Appendix 7.2. We implement training and inference pipelines in PyTorch with NVIDIA GPUs and Intel Gaudi 2 compatibility. Supplementary experiments and analysis can be found in the Appendix, from 7.4 to 7.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 (Equation 5 ), non-backtracking, and named neighbor recording. We measure the edge cover times \(C_E(G)\) and vertex cover times \(C_V(G)\) on varying sizes of lollipop graphs \(G\) [60] which are commonly used to establish the upper bounds of cover times. While the strict definition 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 a 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 6).

max width=0.65

Then, we verify our claims in Section 3.2 using Clique and Barbell datasets of [61] that explicitly test for over-smoothing and over-squashing, respectively. Our RWNN uses MDLR walks with non-backtracking, 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 \(l\). 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-squashing manifests as probabilistic under-reaching (and is therefore mitigated by sufficiently long walks). With \(l = 1000\), our model in Table [tbl:table:smoothing] achieves the best performance among the considered methods. More details on the experiment and additional baseline comparisons can be found in Appendix 7.4.

5.2 Graph Isomorphism Learning↩︎

max width=0.55

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 WL test fails.

The Circular Skip Links (CSL) graphs dataset [51] contains 10 non-isomorphic regular graphs with 41 vertices of degree 4. Distinguishing these graphs requires computing lengths of skip links, and 1-WL and 2-WL tests fail. The \(4\times 4\) rook’s and Shrikhande graphs [62], which we call SR16, are a pair of strongly regular graphs with 16 vertices of degree 6. Distinguishing the pair requires detecting 4-cliques, and 3-WL test fails. The SR25 dataset [63] 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 7.2.

Our RWNN uses MDLR walks with non-backtracking, and recording function with anonymization and named neighbors that produces plain text (Algorithm 6). We use pre-trained DeBERTa-base language model as the reader NN to leverage its capacity (see Appendix 7.5 regarding pre-training), and fine-tune it with cross-entropy loss for \(\leq\)​100k steps using AdamW optimizer with 2e-5 learning rate and 0.01 weight decay following [52]. We truncate the input to 512 tokens due to memory constraints. We use batch size 256, and accumulate gradients for 8 steps for SR25, which we found sufficient to stabilize the training. At test time, we ensemble 4 predictions by averaging logits. [64]

The results are in Table [tbl:table:graph95separation]. MPNNs that align with certain WL tests fail when asked to solve harder problems, e.g., GIN aligns with 1-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 [62]. Alternative approaches based on stochastic symmetry-breaking, e.g., random node identification, often fail on CSL although universal approximation is possible in theory [16], possibly due to learning difficulties. For algorithms based on walks, AgentNet and CRaWl solve CSL and SR16, while failing on SR25. This is because learning a policy to walk in AgentNet can be challenging in complex tasks especially at the early stage of training, and the expressiveness of CRaWl is limited by the receptive field of the 1D CNN. Our approach based on DeBERTa language model overcomes the problems, demonstrating as the first RWNN that solves SR25.

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

5.3 Real-World Transductive Classification↩︎

[65], [66]

max width=0.33

Previous results considered undirected, unattributed, and relatively small graphs. We now show that RWNN based on Llama 3 [22] language models can solve real-world problem on a large graph with directed edges and textual attributes. We use ogbn-arxiv [67], a citation network of 169,343 arXiv papers with title and abstract. The task is transductive classification into 40 areas such as "cs.AI" using a set of labeled vertices. Additional results are in Appendix 7.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 as language model embeddings and trains an MPNN, at the risk of over-compressing the text. To take the best of both worlds, we design the recording function so that, not only it does basic operations such as anonymization, it records a complete information of the local subgraph including title and abstract, edge directions, and notably, labels in case of labeled vertices (Appendix 7.2) [68]. The resulting record naturally includes a number of input-label pairs of the classification task at hand, implying that we can frame transductive classification problem as a simple in-context learning problem [69]. This allows training-free application of Llama 3 [22] language model for transductive classification. We choose restart rate \(\alpha=0.7\) (Section 2.2) by hyperparameter search on a 100-sample subset of the validation data.

The results are in Table [tbl:table:arxiv]. 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 as 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 to quickly learn the task in-context compared to randomly chosen shots. In Appendix 7.3, we visualize the attention weights, verifying that the model makes use of the graph structure recorded by random walks to make predictions.

As a final note, our approach is related to label propagation algorithms [70]–[72] 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 [tbl:table:arxiv], 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 information propagation, showing that we can design RWNNs to be invariant and universal without constraining its neural network. Experiments support the utility of our approach.

Acknowledgments↩︎

This work was in part supported by the National Research Foundation of Korea (RS-2024-00351212 and RS-2024-00436165), the Institute of Information & communications Technology Planning & Evaluation (IITP) (RS-2022-II220926, RS-2024-00509279, RS-2021-II212068, RS-2022-II220959, and RS-2019-II190075) funded by the Korea government (MSIT), Artificial intelligence industrial convergence cluster development project funded by the Korea government (MSIT) & Gwangju Metropolitan City, and NAVER-Intel Co-Lab. We would like to thank Zeyuan Allen-Zhu for helpful discussion regarding anonymous random walks.

7 Appendix↩︎

7.1 Second-Order Random Walks (Section 2)↩︎

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

A non-backtracking random walk is defined upon a first-order random walk algorithm, e.g. one in Equation 4 , by enforcing \(v_{t+1}\neq v_{t-1}\): \[\begin{align} \label{eq:non95backtracking95random95walk} \mathrm{Prob}[v_{t+1}=x|v_t=j,v_{t-1}=i] \coloneq \begin{dcases*} \frac{\mathrm{Prob}[v_{t+1}=x|v_t=j]}{\sum_{y\in N(j)\setminus\{i\}}\mathrm{Prob}[v_{t+1}=y|v_t=j]} & for x\neq i, \\ 0\vphantom{\frac{0}{0}} & for x=i, \end{dcases*} \end{align}\tag{7}\] where \(\mathrm{Prob}[v_{t+1}=x|v_t=j]\) is the probability of walking \(j\to x\) given by the underlying first-order random walk. Notice that the probabilities are renormalized over \(N(j)\setminus\{i\}\). This is ill-defined in the case the walk traverses \(i\to j\) and reaches a dangling vertex \(j\) which has \(i\) as its only neighbor, since \(N(j)\setminus\{i\}=\emptyset\). In such cases, we allow the random walk to "begrudgingly" backtrack [74], \(i\to j\) and then \(j\to i\), given that it is the only possible choice due to the dangling of \(j\).

In case of node2vec random walk [10], a weighting term \(\alpha(v_{t-1}, v_{t+1})\) with two (hyper)parameters, return \(p\) and in-out \(q\), is introduced to modify the behavior of a first-order random walk: \[\begin{align} \label{eq:node2vec95random95walk} \mathrm{Prob}[v_{t+1}=x|v_t=j,v_{t-1}=i] \coloneq \frac{\alpha(i, x)\,\mathrm{Prob}[v_{t+1}=x|v_t=j]}{\sum_{y\in N(j)}\alpha(i, y)\,\mathrm{Prob}[v_{t+1}=y|v_t=j]}, \end{align}\tag{8}\] where the probability \(\mathrm{Prob}[v_{t+1}=x|v_t=j]\) is given by the underlying first-order random walk and \(\alpha(v_{t-1}, v_{t+1})\) is defined as follows using the shortest path distance \(d(v_{t-1}, v_{t+1})\): \[\begin{align} \label{eq:node2vec95weighting} \alpha(v_{t-1}, v_{t+1}) \coloneq \begin{dcases*} 1/p & for d(v_{t-1}, v_{t+1}) = 0, \\ 1 & for d(v_{t-1}, v_{t+1}) = 1, \\ 1/q & for d(v_{t-1}, v_{t+1}) = 2. \\ \end{dcases*} \end{align}\tag{9}\] Choosing a large return parameter \(p\) reduces backtracking since it decreases the probability of walking from \(v_t\) to \(v_{t-1}\). Choosing a small in-out parameter \(q\) has a similar effect of avoiding \(v_{t-1}\), with a slight difference that it avoids the neighbors of \(v_{t-1}\) as well.

We now show an extension of Proposition 2 to the above second-order random walks:

7.2 Main Algorithm↩︎

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

Based on the algorithms, in Figures 8, 9, and 10 we illustrate the task formats used for graph separation experiments in Section 5.2 by providing examples of input graphs, text records of random walks on them, and prediction targets for the language model that processes the records. Likewise, in Figures 11, 12, and 13 we show task formats for transductive classification on arXiv citation network in Section 5.3.

7.3 Attention Visualizations↩︎

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

In Figures 15, 16, and 17, 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 \(v_{t+1}\) where the walk has traversed \(v_t\to v_{t+1}\), we regard it as an attention on the edge \((v_t, v_{t+1})\) in the input graph. We ignore [CLS] and [SEP] tokens since they do not appear on the input graph. We observe that the models often focus on sparse, connected substructures, which presumably provide discriminative information on the isomorphism types. In particular, for CSL graphs (Figure 15) 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.

7.4 Supplementary Materials for Synthetic Experiments (Section 5.1)↩︎

max width=0.65

We provide experimental details and additional baseline comparisons for the Clique and Barbell experiments in Section 5.1 we could not include in the main text due to space constraints.

7.4.0.1 Dataset

In Clique and Barbell [61], each vertex of a graph \(G\) is given a 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 a 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 to form \(G\) and one clique is given positive values and the other is given negative values.

7.4.0.2 Models

Our RWNN uses MDLR walks with non-backtracking, and since the task is vertex-level, for each \(v\) we fix the starting vertex as \(v_0=v\). The recording function \(q:(v_0\to\cdots\to v_l, G)\mapsto\mathbf{z}\) takes a walk and produces a record \(\mathbf{z}\mathrel{\vcenter{:}}=(\mathrm{id}(v_0), \mathbf{x}_{v_0}, \mathbf{x}_{v_0})\to\cdots\to(\mathrm{id}(v_l), \mathbf{x}_{v_l}, \mathbf{x}_{v_0})\), where \(\mathrm{id}(v)\) is the anonymization of \(v\) and \(\mathbf{x}_v\) is the scalar value of \(v\). We find that recording \(\mathbf{x}_{v_0}\) at each step improves training. The reader NN is a 1-layer transformer encoder, with 128 feature dimensions, sinusoidal positional embedding, and average pooling readout. To map the recording at each step \((\mathrm{id}(v_t), \mathbf{x}_{v_t}, \mathbf{x}_{v_0})\) to a 128-dimensional feature, we use a learnable vocabulary for \(\mathrm{id}(v_t)\), a learnable linear layer for \(\mathbf{x}_{v_t}\), and a 3-layer MLP with 32 hidden dimensions and tanh activation for \(\mathbf{x}_{v_0}\).

We test additional baselines that use random walks. We test CRaWl [13] using the official code, and only remove batch normalization since it led to severe overfitting for Clique and Barbell. Since CRaWl uses vertex-level average pooling, while RWNN-transformer uses walk-level, we also test a variant that uses walk-level pooling and denote it by CRaWl*. We also test RWNN-MLP, which uses an MLP on the concatenated walk features instead of a transformer. The MLP has 3 layers with 128 hidden dimensions and ReLU activation. We also test an adaptation of WalkLM [40]. 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 \(\mathrm{id}(v_t)\) from the walk record, and denote the model by WalkLM-transformer.

We train all models with Adam optimizer with batch size 1 and learning rate 1e-4 for 500 epochs, closely following [61] 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 8 predictions per vertex during training, and average 32 predictions per vertex at test-time.

7.4.0.3 Results

The results are in Table [tbl:table:apdx95smoothing]. All random walk based methods consistently perform better than GCN, SAGE, and GAT, and RWNN-transformer 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, CRaWl and CRaWl* are limited by their window size of information processing (see Appendix 7.10), and RWNN-MLP is bottlenecked by the fixed-sized hidden feature. While WalkLM-transformer performs on par with RWNN-transformer on Clique, its error is higher than RWNN-MLP on Barbell, showing the benefits of our design of walks and their records.

7.5 Supplementary Materials for Graph Isomorphism Learning (Section 5.2)↩︎

max width=0.6

max width=

7.5.0.1 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 7.2 and 7.3). To test if language pre-training is useful, we additionally trained RWNN-DeBERTa on CSL and SR16 datasets using the same configurations to our reported models but from random initialization. The training curves are shown in Figure 18. 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.

We conjecture that certain representations or computational circuits acquired in language pre-training are useful for processing text records of walks to recognize graphs. For example, some circuits specialized in 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 as image recognition [27], [28].

7.6 Supplementary Materials for Transductive Classification (Section 5.3)↩︎

7.6.0.1 Fine-tuning

In Section 5.3, our RWNNs are training-free. We demonstrate fine-tuning the Llama 3 8b reader NN using the training labels with quantized low-rank adaptation (QLoRA) [75], [76]. The result is in Table [tbl:table:arxiv95lora], showing a promising performance.

7.6.0.2 Additional real-world transductive classification

We provide additional experiments on real-world transductive classification datasets Cora, Citeseer, and Amazon Ratings. Our RWNNs are designed similarly to the ones used for arXiv. We compile the baseline scores from [68], [77]–[81], which includes MPNNs and language models on graphs. The results are in Table [tbl:table:real95world]. Llama 3 based RWNN is competitive among training-free methods, and performs reasonably well when fine-tuned with QLoRA. Especially, on Amazon Ratings which is heterophilic [81], our fine-tuned RWNN-Llama3-8b achieves the highest accuracy (55.76%). This supports our results in Section 3.2 that RWNNs avoid over-smoothing, as avoiding it is known to be important for handling heterophily [82].

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

max width=0.45

7.7.0.1 Real-world graph classification

We conduct a preliminary demonstration of RWNN on real-world graph classification, using the Peptides-func dataset [83] used in [13]. Our model is a pre-trained DeBERTa-base (identical to Section 5.2) fine-tuned on text records of non-backtracking MDLR walks with anonymization and named neighbor recording. The recording function is 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 19.

In Table [tbl:table:peptides95func], 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 CRaWl, are from [13], [84]. We see that RWNN-DeBERTa, which has been successful in graph isomorphism 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 a fine-tuned language model.

max width=0.5

7.7.0.2 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 a synthetic dataset of 5,000 random regular graphs from [85] and consider the task of counting substructures. We choose 8-cycles since they require a particularly high expressive power [86]. We test both graph- and vertex-level counting (i.e., counting 8-cycles containing the queried vertex) following [86]. We use the data splits from [85]–[87], 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 \(\leq\)​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 [tbl:table:counting], and overall in line with Section 5.2. While MPNNs show a low performance, variants with higher expressive powers such as local 2-GNN and local 2-FGNN achieve high performances. This is consistent with the observation of [86]. On the other hand, MPNNs with stochastic symmetry-breaking often show learning difficulties and does not achieve good performance. AgentNet was not directly applicable for vertex-level counting since its vertex encoding depends on which vertices the agent visits, and a learning difficulty was observed for graph-level counting. Our approach based on DeBERTa demonstrates competitive performance, outperforming random walk baselines and approaching performances of local 2-GNN and 2-FGNN.

max width=0.65

7.7.0.3 Link prediction

We demonstrate an application of RWNNs to real-world link prediction, based on [88] where link prediction is cast as vertex classification on line graphs. We follow the experimental setup of [88] and only change their 3-layer 32-dim DGCNN with an RWNN that uses a 3-layer 32-dim transformer encoder. As the task is vertex-level, we use periodic restarts with \(k=5\). The results in Table [tbl:table:link95pred] shows that RWNN performs reasonably well.

7.8 Supplementary Analysis (Section 5 and Appendix 7.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 to space constraints.

7.8.0.1 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 of Markov chains [60]. 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 SR16 graph separation (Section 5.2), we test the use of named neighbor recording, which changes the required cover time from vertex cover time \(C_V(G)\) (when used) to edge cover time \(C_E(G)\) (when not used). The result is in Table 1. We can see that not using named neighbor recording has a drastic effect on the required cover time (vertex cover time 48.25 \(\to\) edge cover time⁹ 490.00), and the test performance deteriorates from perfect to random accuracy (100% \(\to\) 50%).

Second, in arXiv transductive classification (Section 5.3), due to the high homophily [89] we can assume that the cover time of the local neighborhoods, i.e., \(B_r(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 \(B_r(v)\) leads to a better performance. To test different local cover times, we use two choices of the restart probability \(\alpha=0.3\) and \(0.7\). Since we use named neighbor recording, we measure vertex cover times. Due to the large size of \(G\), we estimate the cover times by fixing a random set of 100 test vertices and running 100 walks from each of them. The result is in Table 2. Increasing the restart probability (0.3 \(\to\) 0.7) simultaneously results in a lower cover time (\(161.2 \to 96.84\)) and a higher test accuracy (74.40% \(\to\) 74.85%), even though the average number of observed vertices decreases (45.28 \(\to\) 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 is 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 7.11.

7.8.0.2 The impact of test-time ensembling

For each test input to an RWNN \(X_\theta\), we often sample several randomized predictions \(\hat{\mathbf{y}}\sim X_\theta(\cdot)\) and ensemble them by averaging (or voting, for Llama 3 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 \((\cdot)\mapsto\mathbb{E}[X_\theta(\cdot)]\) (or the invariant limiting classifier in the case of voting [46]). From another perspective, we can also interpret this as a type of test-time scaling with repeated sampling, which has been shown beneficial in language models [90] and randomized algorithms (called amplification [46], [91]). 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 Table ¿tbl:table:test95time95scaling?. We see that increasing sample size consistently leads to better performances and reduced variances overall. The point of plateau seems to differ per application and model architecture, and we leave obtaining a better understanding of the scaling behavior for future work.

7.8.0.3 Effective walk lengths

For Sections 5.2 and 5.3, the effective lengths of walks are affected by the language model tokenizers since text records exceeding the maximum number of tokens are truncated. The maximum number of tokens is 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 3 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 3. The effective length is shorter (129.54 on average) for SR25 graphs compared to CSL and SR16 (214.03 and 222.00 on average, respectively) although using the same tokenizer configurations, which is because the higher average degrees of SR25 graphs (Figure 10) compared to CSL and SR16 graphs (Figures 8 and 9, respectively) has led to a higher number of text characters invested in recording named neighbors ("#" symbols in the figures).

7.9 Proofs↩︎

We recall that an isomorphism between two graphs \(G\) and \(H\) is a bijection \(\pi:V(G)\to V(H)\) such that any two vertices \(u\) and \(v\) are adjacent in \(G\) if and only if \(\pi(u)\) and \(\pi(v)\) are adjacent in \(H\). If an isomorphism \(\pi\) exists between \(G\) and \(H\), the graphs are isomorphic and written \(G\simeq H\) or \(G\overset{\pi}{\simeq}H\). By \(X\overset{d}{=}Y\) we denote the equality of two random variables \(X\) and \(Y\) in distributions.

In the proofs, we write by \(\mathrm{id}(\cdot)\) the namespace obtained by anonymization of a walk \(v_0\to\cdots\to v_l\) (Section 2) that maps each vertex \(v_t\) to its unique integer name \(\mathrm{id}(v_t)\) starting from \(\mathrm{id}(v_0)=1\).

Let us define some notations related to cover times. These will be used from Appendix 7.9.5. We denote by \(H(u, v)\) the expected number of steps a random walk starting from \(u\) takes until reaching \(v\). This is called the hitting time between \(u\) and \(v\). For a graph \(G\), let \(C_V(G, u)\) be the expected number of steps a random walk starting from \(u\) takes until visiting every vertices of \(G\). The vertex cover time \(C_V(G)\), or the cover time, is this quantity given by the worst possible \(u\): \[\begin{align} \label{eq:cover95time} C_V(G)\coloneq \max_{u\in V(G)} C_V(G, u). \end{align}\tag{10}\] Likewise, let \(C_E(G, u)\) be the expected number of steps a random walk starting from \(u\) takes until traversing every edge of \(G\). The edge cover time \(C_E(G)\) is given by the worst possible \(u\): \[\begin{align} \label{eq:edge95cover95time} C_E(G)\coloneq \max_{u\in V(G)} C_E(G, u). \end{align}\tag{11}\] For local balls \(B_r(u)\), we always set the starting vertex of the random walk to \(u\) (Section 2.2). Thus, we define their cover times as follows: \[\begin{align} C_V(B_r(u))\coloneq C_V(B_r(u), u),\tag{12}\\ C_E(B_r(u))\coloneq C_E(B_r(u), u).\tag{13} \end{align}\]

7.9.1 Proof of Proposition 1 (Section 2)↩︎

7.9.2 Proof of Proposition 2 (Section 2)↩︎

We first show a useful lemma.

We now prove Proposition 2.

7.9.3 Proof of Proposition 10 (Appendix 7.1)↩︎

We extend the proof of Proposition 2 given in Appendix 7.9.2 to second-order random walks discussed in Appendix 7.1. We first show a useful lemma:

We now prove Proposition 10.

7.9.4 Proof of Proposition 3 (Section 2)↩︎

7.9.5 Proof of Theorem 4 (Section 2.2)↩︎

7.9.6 Proof of Theorem 5 (Section 2.2)↩︎

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

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

We are now ready to prove Theorem 5.

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

7.9.7 Proof of Theorem 6 (Section 3.1)↩︎

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

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

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

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

We further remark Markov’s inequality for any nonnegative random variable \(T\) and \(a>0\): \[\begin{align} \label{eq:markov} \mathrm{Prob}[T\geq a]\leq \frac{\mathbb{E}[T]}{a}. \end{align}\tag{38}\]

We are now ready to prove Theorem 6.

7.9.8 Proof of Theorem 7 (Section 3.1)↩︎

7.9.9 Proof of Theorem 8 (Section 3.2)↩︎

7.9.10 Proof of Theorem 9 (Section 3.2)↩︎

7.10 Extended Related Work (Section 4)↩︎

7.10.0.1 Anonymized random walks [12]

The initial work on anonymization by [12] has stated an important result, that a sufficiently long anonymized walk starting from a vertex \(v\) encodes sufficient information to reconstruct the local subgraph \(B_r(v)\) up to isomorphism. While the focus of [12] was a probabilistic graph reconstruction algorithm that uses a 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).

7.10.0.2 In-depth comparison with CRaWl [13]

Our approach is related to CRaWl in two key aspects: (1) identity and connectivity encodings of CRaWl contains analogous information to anonymization and named neighbor recording, respectively, and (2) CRaWl 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 \(s\) in [13]), which puts a locality constraint on the recorded information. Precisely, the encodings at step \(t\) can encode the information of the walk from step \(t - s\) to \(t\) (precisely, its induced subgraph), referred to as a walklet. The window size \(s\) is a hyperparameter that controls the expressive power of CRaWl, and this dependency makes CRaWl non-universal (Section 3.2, [13]). 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 CRaWl.

7.10.0.3 Random walks on graphs

Our work builds upon theory of random walks on graphs, i.e., Markov chains on discrete spaces. Their statistical properties such as hitting and mixing times have been well-studied [34], [60], [96]–[99], and our Section 2 is related to vertex cover time [34], [100]–[102], edge cover time [25], [103]–[105], and improving them, using local degree information [19], [23], [106], non-backtracking [39], [107]–[109], or restarts [31], [92], [94]. Our work is also inspired by graph algorithms based on random walks, such as anonymous observation [12], sublinear algorithms [24], [110]–[112], and personalized PageRank for search [30] and message passing [113]. 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 [70]–[72] that perform transductive learning on graphs based on random walks, as we have discussed in Section 5.3.

7.10.0.4 Over-smoothing and over-squashing

Prior work on over-smoothing and over-squashing of MPNNs [8], [20], [36]–[38], [114]–[116] often make use of structural properties of graphs, such as effective resistance [117], [118], Laplacian eigen-spectrum [96], [119], and discrete Ricci curvatures [120], [121]. 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 [122] 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 over-smoothing and over-squashing 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 [8], [20], [37], [38]. Formal propagation analysis for attention-based MPNNs is currently in its infancy [116], but we believe it is interesting since, based on our 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.

7.10.0.5 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 [77], [123]–[126], often focusing on prompting methods on problems involving simulations of graph algorithms. We take a more principle-oriented approach based on invariance and expressive power, and thus demonstrate our approach mainly on the related tasks, e.g. graph separation. We believe extending our work to simulating graph algorithms requires a careful treatment [127]–[130] and plan to investigate it as future work.

7.11 Limitations and Future Work↩︎

Our current main limitation is the cost of performing training and inference if 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 RWNN-Llama-3-70b takes around 0.410 ± 0.058 seconds on a 4\(\times\) H100 machine (RWNN-Llama-3-8b is faster, 0.116 ± 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 [131]. Overcoming this issue is an important future direction. We remark that, if language model embeddings are used and fine-tuned, the training cost of MPNNs can also be substantial, e.g., recent work has reported that prior methods for training an MPNN jointly with language model embeddings on arXiv take 25-46 hours on a 6\(\times\) RTX 3090 machine (Table 3 of [132]).

On the theory side, we focus on cover times of random walks in our analysis (Section 3.1 and Appendix 7.8), which corresponds to the worst-case length bounds required for universal approximation. Yet, in practice, there is a substantial amount of useful information that can be already recovered from possibly non-covering walks. Examples include spectral properties [133], number of edges and mixing time [111], and triangle counts [112], among others studied in the field of sublinear algorithms. These results suggest that shorter walks may suffice in practice for RWNNs, if 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.

Another question for future work is whether we can train a language model on a large pseudocorpus of random walks [134], [135] to build a foundation model for graphs which is language-compatible. We plan to investigate this direction in the future.

References↩︎

---

1. Code is available at https://github.com/jw9730/random-walk.↩︎

2. These authors contributed equally.↩︎

3. Work done during an internship at School of Computing, KAIST.↩︎

4. While any output type such as text is possible (Figure 1), we explain with vector output for simplicity.↩︎

5. We assume this for simplicity but extending to directed or attributed graphs is possible.↩︎

6. This is assuming that the random walks are localized in \(B_r(v)\) and \(B_r(u)\), e.g. with restarts.↩︎

7. This bound is obtained by applying Lemma 3.2 of [37] to our linearized MPNN.↩︎

8. While we show not forgetting \(\mathbf{x}\) for brevity, we may extend to initial vertex \(v_0\) using its anonymization as \(1\).↩︎

9. As in Section 5.1, while the strict definition of edge cover requires traversing each edge in both directions, our measurements only require traversing one direction, which suffices for the universality of RWNNs.↩︎

10. We remark that depth first search discovers all edges of a graph, while not necessarily visiting all of them.↩︎