Learning Long Range Dependencies on Graphs via Random Walks
Authors: Dexiong Chen
Till Hendrik Schulz
Karsten Borgwardt
Venue: ICLR 2025 Poster (2025)
Keywords: Graph neural networks
Graph transformers
Random walks
Long-range dependencies
Primary area: learning on graphs and other geometries & topologies
TL;DR: A novel random-walk based neural architecture for graph representation learning

Abstract: Message-passing graph neural networks (GNNs) excel at capturing local relationships but struggle with long-range dependencies in graphs. In contrast, graph transformers (GTs) enable global information exchange but often oversimplify the graph structure by representing graphs as sets of fixed-length vectors. This work introduces a novel architecture that overcomes the shortcomings of both approaches by combining the long-range information of random walks with local message passing. By treating random walks as sequences, our architecture leverages recent advances in sequence models to effectively capture long-range dependencies within these walks. Based on this concept, we propose a framework that offers (1) more expressive graph representations through random walk sequences, (2) the ability to utilize any sequence model for capturing long-range dependencies, and (3) the flexibility by integrating various GNN and GT architectures. Our experimental evaluations demonstrate that our approach achieves competitive performance on 19 graph and node benchmark datasets, notably outperforming existing methods by up to 13\% on the PascalVoc-SP and COCO-SP datasets.
Code: https://github.com/BorgwardtLab/NeuralWalker

Published as a conference paper at ICLR 2025
LEARNING LONG RANGE DEPENDENCIES ON GRAPHS VIA RANDOM WALKS
Dexiong Chen, Till Hendrik Schulz & Karsten Borgwardt
Max Planck Institute of Biochemistry, 82152 Martinsried, Germany (dchen, tschulz, z, borgwardt @bb ochem. wwg. de
ABSTRACT
cressage-passing graph neural networks (GNNs) excel capturing local relation- ships but struggle with long-range dependencies in graphs. In contrast, graph transformers (GTs) enable global information exchange but often oversimplify the graph structure by representing graphs sets of fixed-length vectors. This work introduces novel architecture that overcomes the shortcomings of both approaches by combining the long-range information of random walks with local message passing. By treating random walks as sequences, our architecture leverages recent advances in sequence models to effectively capture long-range dependencies within these walks. Based on this concept, we propose a framework that offers (1) more expressive graph representations through random walk sequences, (2) the ability to utilize any sequence model for capturing long-range dependencies, and (3) the flexibility by integrating various GNN and GT architectures. Our experimental evaluations demonstrate that our approach achieves competitive performance on graph and node benchmark datasets, notably outperforming existing methods by up to 13% on the PascalVoc-SP and COCO-SP datasets.
INTRODUCTION
Message-pasee passing graph neural networks (GNNs) (Gilmer et al., 2017) and graph transformers (GTs) (Ying et al., 2021). have emerged as powerful tools for learning on graphs. While GNNs are efficient in identifying local relationships, they often fail to capture distant interactions due to the local nature of message passing, leading to issues such as over-smoothing (Oono Suzuki, 2020) and over-squashing (Alon & Yahav, 2021). In contrast, GT's (Ying et al., 2021; Mialon et al., 2021; Chen et al., 2022a; Rampāšek et al., 2022: Shirzad et al., 2023) address these limitations by directly modeling long-range interactions through global attention mechanisms, enabling information exchange between all nodes. However, GTs typically preprocess the complex graph structure into fixed-length vectors for each node, using positional structural encodings (Rampášek et al., 2022). This approach essentially treats the graph as a set of nodes enriched with these vectors. Such vector representations of graph topologies inevitably result in loss of structural information, limiting expressivity even when GTss are combined with local message- message-passing techniques (Zhu et al., 2023). In this work, we address these limitations by introducing a novel architecture that captures long-range dependencies while preserving rich structural information, by leveraging the power of random walks.
Random walks offer flexible approach exploring graphs, surpassing the limitations of fixed-length vector representations. By traversing diverse paths across the graph, random walks can capture subgraphs with large diameters, such as cycles, which message passing often struggles to represent, due to its depth-first nature (Grover & Leskovec, 2016). More importantly, the complexity of sampling random walks is determined by their length and sample size rather than the overall size of the graph. This characteristic makes random walks scalable choice for representing large graphs, offering clear computational advantages compared to many computationally expensive encoding methods.
While several graph learning approaches have employed random walks, their full potential remains largely untapped. Most existing approaches either focus solely on short walks (Chen et al., 2020; Nikolentzos & Vazirgiannis, 2020) or walks primarily for structural encoding, neglecting the rich information they contain (Dwivedi et al., 2021; Mialon et al., 2021). more recent method, CRawL (Tönshoff et al., 2023b), takes novel approach by representing graph of random

---

Published as a conference paper at ICLR 2025
walks. While this approach shows promising results, it has two major practical limitations: 1) its reliance on convolutional layers to process random walks, particularly with small kernel sizes, constrains its abilitt to approximate arbitrary functions walks and fully capture long-range dependencies within each walk. 2) Due to the depth-first nature of random walks, it struggles to efficiently capture local relationships, such simple subtrees, illustrated in Figure 1.
Considering the limitations of existing random-walk -aak- based models, we propose an approach that leverages the strengths of two complementary graph exploration paradigms. Our method combines the local neighbor- hood information captured by the breadth-first nature of message passing with the long-range dependencies obtained through the depth-first nature of random walks. Unlike GTs that encode random walks into fixed-length vectors (Rampášek et al., 2022: Chen et al., 2022a), our approach preserves their sequential nature, thereby retaining richer structural information. Our proposed architecture, named Neura/Walker achieves this by processing sets of sampled random walks using powerful sequence models. We then employ local (and optionally global) message passing to capture complementary information. Multiple alternations of these two operations are stacked to form our model. A key innovation of our approach is the utilization of long sequence models, such as state space models, to learn from random walk sequences.
Message Passing
Random Walks
Figure 1: Message passing efficiently cap- tures locally sparse subgraphs, like k-star subgraphs, while random walks struggle, requiring a length of 2k.
Our contributions are summarized as follows. i) We propose a novel framework that leverages both random walks and message passing, leading to provably more expressive graph representation. ii) Our model exploits advances in sequence modeling (e.g, transformers and state space models) to capture long-range dependencies within the walks. iii) Our message-passing block can seamlessly integrate various GNN and GT architectures, allowing for customization based on specific tasks. iv) We conduct extensive ablation studies to offer practical insights for choosing the optimal sequence layer types and message- pasgggngaaningggggg strategics. Notably, the trade-off between model complexity and expressivity can be flexibly controlled by adjusting walk sampling rate and length, making model scalable to graphs with up to 1.6M nodes. v) Our model demonstrates remarkable performance improvements over existing methods comprehensive set of 19 benchmark datasets.
2 RELATED WORK
Local and global message passing. Message-passing neural networks (MPNNs) are a cornerstone of graph learning. They propagate information between nodes, categorized as either local or global methods based on the propagation range. Local MPNNs. also known GNNs (e.g, GCN (Kipf & Welling, 2016). GIN (Xu et al., 2019)), excel at capturing local relationships but struggle with distant interactions due limitations like over-smoothing (Oono & Suzuki, 2020) and over-squashing (Alon & Yahav, 2021). Global message passing offers a solution by modeling long-range dependencies through information exchange across all nodes. GTs (Ying al., 2021; Kreuzer al., 2021; Mialon et al., 2021; Chen et al., 2022a; Rampášek et al., 2022; Shirzad et al., 2023), using global attention mechanisms, are a prominent example. However, GTs achieve this by compressing the graph structure into fixed-length vectors, leading to a loss of rich structural information. Alternative techniques include the virtual node approach (Gilmer et al., 2017: Barceló et al., 2020). which enables information exchange between distant nodes by introducing an intermediary virtual node.
Random walks for graph learning. Random walks have a long history in graph learning, particu- larly within traditional graph kernels. Due to the computational intractability of subgraph or path kernels (Gärtner et al., 2003), walk kernels (Gärtner et al., 2003; Kashima et al., 2003; Borgwardt & Kriegel, 2005) were introduced to compare common walks or paths in two graphs efficiently. Non-backtracking walks have also been explored (Mahé et al., 2005) for molecular graphs. In deep graph learning, several approaches utilize walks or paths to enhance GNN expressivity. GCKN (Chen et al., 2020) pioneered short walk and path feature aggregation within graph convolution, further explored in Michel et al. (2023). RWGNN (Nikolentzos & Vazirgiannis, 2020) leverages differen- tiable walk kernels for subgraph comparison and parametrized anchor graphs. The closest work to ours is CRaWL (Tönshoff et al.. 2023b). However, it lacks message passing and relies on a convolutional layer, particularly with small kernel sizes, limiting its universality. Prior to CRaWI.,
2

---

Published as a conference paper at ICLR 2025
Lx Walkel Blocks
Random Walk Sampler
Walk Emnhedder
Walk Aggregator
Walk
2 Suaition Recodings
bostersting
Message Passing
Walk
Pueitio Recodings
Feabersting
Walk dner Block
Iterstive Neighbor Sampling
Walk Aggroguator
Stds
approgacion
Sequence Layer
Walk Embedder
Wale
Random Sampler
Figure 2: Overview of the NeuralWalker architecture. The random walk sampler samples m random walks independently without replacement; the walk embedder computes walk embeddings given the node/edge embeddings at the current layer; the walk aggregator aggregates walk features into the node features via pooling of the node features encountered in all the walks passing through the node.
Ivanov & Burnaev (2018); Wang et al. (2021); Yin al. (2022) used random walks with identity encodings, which served as inspiration for CRaWL. However, these approaches did not include adjacency encodings, which essential for capturing the full information of induced subgraphs. Additionally, random walks have been used as structural encoding in GTs such as RWPE (Dwivedi al., 2021) and relative positional encoding in self-attention (Mialon et al., 2021).
Sequence modeling. Sequence models. particularly transformers (Vaswaní et al., 2017) and state space models (SSMs) (Gu et al., 2021; ; Gu Dao, 2023), have become instrumental in natural lan- guage proesssig (NLP) and audio processing due to their ability capture long-range dependencies within sequential data. However, directly leveraging these models on graphs remains challenging due to the inherent structural differences. Existing approaches like GTs treat graphs as sets of nodes, hindering the application of transformer architectures to sequences within the graph. Similarly, recent work utilizing SSMs for graph modeling (Wang et al., 2024) relies on node orderings based on degrees, a suboptimal strategy that may introduce biases or artifacts when creating these artificial sequences that do not reflect the underlying graph topology. Behrouz Hashemi (2024) use SSMs on nested sequences of subgraphs induced by random walks of growing sizes and redundant encodings (e.g. Laplacian PEs and relative PE/SEs), introducing additional complexity and limiting walk lengths.
Our work addresses this limitation by explicitly treating random walks on graphs as sequences. This allows us to leverage the power state-of-the-art (SOTA) sequence models to capture rich structural information within these walks, ultimately leading to more universal graph representation. Furthermore, by integrating both message passing and random walks, our model is provably more expressive compared to existing MPNNs and random walk-based models, discussed in Section 4.
3 NEURAL WALKER
In this section, we present the architecture of our proposed Neural which processes sequences obtained from random walks to produce both node and graph representations. Its components consist of random walk sampler, described in Section 3.2, and stack of Neural blocks, discussed in Section 3.3. A visualization the architecture can be found in Figure
3.1 NOTATION AND RANDOM WALKS ON GRAPHS
We first introduce the necessary notation. graph is tuple G (V,E, where is the set of nodes, E is the set of edges, and æ V + Rd and z + gd denote the functions assigning attributes to node and edges, respectively. We denote by G and Gn the space of all graphs and the space of graphs up to size n, respectively. The neighborhood of a node is denoted by N(w) and its degree by d(v). A walk W of length e on graph G is sequence of nodes connected by edges, i.. W (Wp..... wy) E F++1 such that w; W; E E for all E [E]. We denote by W(G) and W2(G) the set of all walks and all walks of length e on G, respectively. W is called hon-backtracking if
3

---

Published as a conference paper at ICLR 2025
W;-1 # W4+11 for all i and denote the set of all such walks by Wi A random walk is Markov chain that starts with some distribution on nodes Po(u) and transitions correspond to moving to neighbor chosen uniformly random. For non- soubbcktracking random walks, neighbors are chosen uniformly from (wss) ( 11 We denote by P(W(G). Pa) the distribution of random walks with initial distribution Po. and by P(W(G)) the case where Po U(V) is the uniform distribution on V.
3.2 RANDOM WALK SAMPLER
The random walk sampler independently samples a subset of random walks on each graph through probability distribution all possible random walks. For any distribution on random walks P(W(G), Po), we denote by (m(G)) == (W.,... Wm realization of m i.i.d. samples W3 P(W(G) Po). Our model always operates on such realizations. Motivated by the success in Tönshoff et al. (2023b), we consider non-backtracking walks of fixed length. Specifically, we consider the uniform distribution of length-l random walks P(W(G), Po) == P(WT (G), U(V)..
.......
In practice, we restrict the number of samples m S n where = |V| for computation efficiency. We define the sampling rate of random walks as the ratio of random walks to nodes (7 == m/n). Note that random walks only need to be sampled once for each forward pass and that an efficient CPU implementation can be achieved through iterative neighbor sampling, with a complexity ((ry)), linear in the number and length of random walks. We remark that during inference, higher sampling rate than that used during training can be used to enhance performance. Therefore, we always fix it to 1.0 inference. In Section 5.3, empirically study the impact of y and & used at training on the performance, showing that once these hyperparameters exceed a certain threshold, their impact on performance saturates. We present below the positional encodings for random walks encoding full information of induced subgraphs along the walks, essential for establishing our theoretical results.
Positional encodings for random walks. Similar to Tönshoff et al. (2023b), we utilize additional encoding features that store connectivity information captured within random walks. In particular, we consider an identity encoding which encodes whether two nodes in a walk are identical within a window and adjacency encoding which includes information about subgraphs induced by nodes along the walk. Specifically, for a walk W = (Wo.... we) E We(G)) and window size s E N4. the identity encoding W, denoted idly, is the binary matrix in {0, (0,11, 1]((+1)x xs with id [ = 1 if wi W s.t. j 2 1, and otherwise for any 0 1 í < L and 0 S I s - 1. Similarly, the adjacency encoding adjt E {0, 1) ((+1)))x((s)) satisfies adjw [i.j]
1 if -o: i-j 2 1, and otherwise 0 for any 0 < i S l and 0 S 8 1. A visual example of such encodings given in Appendix B.1. Finally, the output of the random walk sampler is the concatenation all encodings into single matrix hipe E R (f+1))xd together with the sampled random walks.
E s.t.
3.3 MODEL ARCHITECTURE
In the following, we describe the architecture of NeuralWalke which conists of several walk encoder blocks where each block is comprised of three components: walk embedder, a sequence layer, and a walk aggregator that are presented in Sections 3.3.1, 3.3.2, and 3.3.3, respectively.
3.3.1 WALK EMBEDDER
The walk embedder generates walk embeddings given the sampled walks, and the node and edge embeddings at the current layer. It is defined as function femb : Wr(G) R((+1)xd, Specifically, for any walk W E P., (W),, the walk embedding hw := (emmmm(m R (e+1)xd is defined as
hwl1 == by (wi) + projeage (hg(wa::++)) + projpe (hppe [i)),
where by V + Rd and Ag E + ddw are node and edge embeddings the current block and projedge : R.day + Rd and projpe 4h -> Rd are some trainable projection functions. The resulting walk embeddings is then processed with sequence model as discussed below.
3.3.2 SEQUENCE LAYER ON WALK EMBEDDINGS
In principle, any sequence model can be used to process the walk embeddings obtained above. A sequence layer transforms sequence of feature vectors into a new sequence, i.e., it is a function Seq (e+11xxd (e+1)xd In the following, we discuss several choices for such function.
4

---

Published as a conference paper at ICLR 2025
ID CNNs are simple and fast models for processing sequences, also used in Tönshoff et al. (2023b). They are friendie and require relatively limited memory. However, the receptive field of a ID CNN is limited by its kernel size, which might fail to capture distant dependencies on long walks.
Transformers are widely used in modeling sequences and graphs due to their universality and strong performance. However, we found in experiments (see Table 6) that they suboptimal encoders for walk embeddings, even when equipped with the latest techniques like RoPE (Su et al., 2024).
SSMs more recent approach for modeling long sequences. In our experiments, two of the latest instances of SSMs, namely S4 (Gu et al., 2021) and Mamba (Gu & Dao, 2023). In addition to the original version, we consider the bidirectional version of Mamba (Zhu et al., 2024). We found that bidirectional Mamba consistently outperforms other options (Section 5.3). For more comprehensive background on SSMs, please refer to Appendix A.3.
employ
3.3.3 WALK AGGREGATOR
The walk aggregator aggregates walk features into node features such that the resulting node features encode context information from all walks passing through that node, defined as a function Jaez : (P (W,(())))))))) + ((1)xd)) + (V + ( and the resulting node feature mapping is given by h:50 := fagg Sey (Femb) P... (W.,())) where fl. denotes the function restriction. this work, we consider the average of all the node features encountered in the walks passing through given node. Specifically, the node feature mapping hig with an average pooling defined as
(v) = No (m..(()))))) (We wi W.WW w:=.
E
Σ
Sseg(h))(e
where (2 (Wr( represents the number of occurrences v in the union of walks in Pa (G)) One could also average the edge features in the walks passing through certain edge to update the edge features: 2, (c) == Ewep.. E EewehieWar at. wows-== Sseg (hw [{]]
up to a normalization factor. In practice, we also use skip connections to keep track of the node features from previous layers.
3.3.4 LOCAL AND GLOBAL MESSAGE PASSING
While random walks are efficient at identifying long-range dependencies due of their depth-first nature, they are less suited for capturing local substructure information, which often plays an essential role in many graph learning tasks. To address this limitation, we draw inspiration from classic node embedding methods (Perozzi et al., 2014; Grover Leskovee, 2016). We incorporate a message- passing layer into encoder block, leveraging its breadth-first characteristies complement the information obtained through random walks. Such a (local) message passing step is given by
h (v) == 1 (v) + MPNN(G, by (u)),
where MPNN denotes a GNN model, typically with one layer in each encoder block.
Following the local message passing layer, we optionally apply global message passing mechanism, allowing for a global information exchange, as done in GTs (Chen et al., 2022a). We particularly consider two global message passing techniques, namely virtual node (Gilmer et al., 2017; Tönshoff et al., 2023a) and transformer layer (Ying et al., 2021; Chen et al., 2022a; Rampášek et al., 2022). We provide more details on these techniques in Appendix B.2.
THEORETICAL RESULTS
In this section, we investigate the theoretical properties of NeuralWalke The proofs of the following results as well as more background can be found in Appendix C.
We first define walk feature vectors following Tönshoff al. (2023b):
Definition 4.1 (Walk feature vector). For any graph G = (V, 1,,222) and W E We(G), the walk feature vector Xw of W is defined by concatenating the node and edge feature vectors, along with the positional encodings of W with window size s = f. Formally,
X (x(wx), =(w,we++)) 1), hre bn)l-o) E R. ((+1))xd
5

---

Published as a conference paper at ICLR 2025
where hye represents the positional encoding of Section 3.2, 2(weee+1) 0. and dwalk d+ -dpe For simplicity, we still denote the distribution of walk feature vectors on G by P(W(G)).
For simplicitly, we consider general rather than non bonbbacktr random walks in this section. Now assume that we apply an average pooling followed by linear layer to the output of the walk aggregator in Eq. (2). By adjusting the normalization factor to constant me/VV), V). we can express the function mf.m on 9 as an average over functions of walk feature vectors:
gf.m, = m7
Σ
s(Xw)
WEP..WW((C)
where / Roon -> R is some function on walk feature vectors.
If we sample sufficiently large number of random walks, the average function (..)m.(G) converges almost surely to gr. := Ex (GW, (f ]] due to the law of large numbers. This result can be further quantified using the central limit theorem, which provides rate of convergence (see Theorem C.5 in Appendix). Furthermore, we have the following useful properties of this limit:
Theorem 4.2 (Lipschitz continuity). For some functional space of functions on walk feature vectors, we define the following distance dy 9 x + R4:
dy dy, G') == sup [x (Ex=><cmIC) JEF
-x
(5)
Then (gu, dy 2) is metric space if is a universal space and f 4n
If F contains f. then for any G.G' E Enn, we have
(9),((G) =
(6)
In particular, i E F is an funitin, the difference in outputs is bounded by the earth mover's distance Wi(:,)) between the distributions of walk feature vectors:
(gr,e(G) - (G)) s L ((W))
The Lipschitz constant, widely used to assess neural network stability under small perturbations (Vir- maux & Scaman, 2018), guarantees that Walker maintains stability when subjected to minor alterations in graph structure. Notably, parameterizing f with several neural network layers yields a Lipschitz constant comparable to that of MPNNS pseudometric space defined by the tree mover's distance (Chuang & Jegelka, 2022). However, a key distinction lies in the input space metrics: while MPNNs operate tree structures, NeuralWalker focuses on the distribution of walk feature vectors. A more comprehensive comparison of MPNNs' and Neural NeuralWalker'ss stability and generalization under distribution shift is left for future research.
Theorem 4.3 (Injectivity). Assume that F is universal space. If G and G' are non-isomorphic graphs, then there exists an f E F such that g5,e(G) + (f.) if 2 4 max((V],lv''>>
The injectivity property ensures that our model with a sufficiently large number of sufficiently long (2 4n²) random walks can distinguish between non-in non-isomorphic graphs. It is worth noting that although our assumptions include specific conditions on the random walk length establish the space as a metric, removing the length constraint still results in pseudometric space. In this case, dr,e(G G, G') > 0 if G and G' are distinguishable by the (L$/2] - 1) 1)-suggraph isomorphism test, where [-] is the floor function (i.e., they do not have the same set of subgraphs up to size (1+/2] + 1)).
Using the previous result jointly with the message- paasingg module, we arrive at the following result, which particularly highlights the advantage of combining random walks and message passing,
Theorem 4.4. For any 8 2 2, NeuralWalker equipped with the complete walk set W; is strictly more expressive than 1-WL and the (L1/2] + susuuggra isomorphism test, and thus ordinary MPNNs.
The injectivity in Thm. 4.3 is guaranteed only if F is universal functional space. This condition highlights a limitation in approaches like CRaWL (Tönshoff et al., 2023b) which employs CNNs to process walk feature vectors. CNNs can only achieve universality under strict conditions, including periodic boundary conditions and a large number of layers (Yarotsky, 2022). However, random walks generally do not satisfy periodic boundary conditions, and utilizing excessive number of

---

Published as a conference paper at ICLR 2025
Table 1:
Test performance on benchmarks from Dwivedi et (2023). Metrics with mean = std of runs are reported. The result with is obtained using the pretraining strategy presented in Section 5.2.
ZINC 12K
MNIST
CIFARIO
PATTERN
CLUSTER
GRAPHS
70K
60K
14K
12K
AVG.
23.2
70.6
117.6
118.9
117.2
AVG. # EDGES
24.9
564.5
941.1
3039.3
2150.9
METRIC
MAE
ACC
1CC1
ACC
ACC1
GCN
0,367 + 0.011
90.705 + 0.218
55.710
0.381
71,892 # 3.4
68.498 + 0.976
GIN
0.526
96.485
0.252
55.255
1.527
85.387 0.136
64.716 1.553
GATEDGON
0.282 0.015
97.340 0.143
67.312
0.311
85.568 + 0. 0.088
73.840 0.326
86.848 1
77.856
GPS
0.070 0.000
98.051 à: 0.126
0.356 72.298
86.685 + 0.059
78.016 0.180
EXPHORMER
98.55 0.03
86.70 0.03
GRIT
0.059 # 0.002
98.108 + 0.111
0.881 76.468
87.196 + 0.076
80.026 + 0.277
GRED
0.077
98.383
76.853
GMN
98.39 0.18
0.476=0042
07.14
0.004
97.944 0.050
0.259
BEURALWALKER
0.053 + 0.002"
98.692 0.079
76.9033 0.457
86,977 + 0.012 18.189 0.188
Table 2: Test performance on LRGB (Dwivedi et al., 2022). Metries with mean std of 4 runs are reported. NeuralWalker improves the best baseline by 10% and 13% on PascalVOC-SP and COCO-SP respectively. GPS-tuned refers to the results reported by Tönshoff al. (2023a) with more extensive hyperparameter tuning compared to GPS (Rampášek et al., 2022).
PASCALVOC-SP
COCO-SP
PEPTIDES-FUNC
PEPTIDES-STRUCT
PCQM-CONTACT
123.3K
15.5K
$29.4K
AYG. A NODES
479.4
476.9
150.9
130.9
30.1
AvG. # RIGERS
2,710.5
2,693.7
307.3
307.3
61.0
F1
MAE
MRR
GCN
0.2078 = 0.0031
0,1338 + 0.0007
0.6860 = 0,0050
0.2460 0.0007
0.4526 + 0.0006
GIN
0.2718 0.0054
0.2125
0.0009
0.6621 0.0067
0.2473
0.001?
0.4617 0.0005
GATEDGCN
0.3880 0.0040
0.2922 1: 0.0018
0.6765 1 0.0047
0.2477 0.0009
0.4670 0.0004
GPS
0.0100
0.3412 : 0.0044
0.6535 0. 0004
0.2500 0.0005
GPS-TUNED
0.4440 0.0065
0. 1.3884+4 + 0055
0.65
0.2509 0.0014
0.4703 0.0014
EXPHORMER
0.3975 0.0037
0.3455 + 0.0009
0.6327 1 0.0043
0.2481 : 0.0007
GRIT
0.6988 0,0082
0.2460 0.0012
GRED
0.7133 1 0.0011
0.2455 0.0013
GMN
0.4393 0.0112
0.0914
0.7071 # 0,0083
0.2473 0.0025
0.3960 0.0112
CRAWL
0.7074 a 0.0032
0.2506 a 0.0022
NALRALWALKER
0.4912 0.0042
0.4398 + 0.0033
0.7096 0.0078
0.2463 0.0005
0.4707 0.0007
layers can exacerbate issues such as over-squashing and over-smoothing. In contrast, the sequence models considered in this work, such as transformers and SSMs, are universal approximators for any sequence-tee soquence-to-seqqenne to-suuenccee functions (Yun et al., 2020; Wang & Xue, 2024). Furthermore, the proof of Thm. 4.4 suggests that random walk-based models without message passing cannot be more expressive than W-. Consequently, model is provably more expressive than CRaWI..
Finally, we have the following complexity results:
Theorem 4.5 (Complexity). The complexity of NeuralWalker, when used with Mamba (Gu Dao, 2023), is O(dn((7l-+ B8), where k. d, n. Y,Y, (maximum) number of nodes, sampling rate, length of random walks and average degree, respectively.
L. B denote the nunber of layers, hidden dimensions, the
EXPERIMENTS
In this section, we compare NelkalWalker to several SOTA models on a diverse of 19 benchmark datasets. Furthermore, we provide a detailed ablation study on components of our model. Appendix D provides more details about the experimental setup, datasets, runtime, and additional results.
5.1 BENCHMARKING NEURAL WALKER TO STATE- OF- THE-ARE--RR METHODS
We compare NeuralWalke against several popular message passing GNNs, GTs, and walk-based mod- els. GNNs include GCN (Kipf & Welling, 2016), GraphS AGE (Hamilton et al., 2017), GIN (Xu et al., 2019), GAT (Veličković et al., 2018), GatedGCN (Bresson & Laurent, 2017). Models using global message passing include GraphTrans (Wu et al., 2021), SAT (Chen et al., 2022a), GPS (Rampášek al., 2022), Exphormer (Shirzad et al., 2023), NAGphormer (Chen et al., 2022b), GRIT (Ma et al.,
7

---

Published as a conference paper at ICLR 2025
2023), Polynormer (Deng et al., 2024), GRED (Ding et al., 2024), Graph-Mamba (Wang et al., 2024), GMN (Behrouz & Hashemi, 2024). Walk-based models include CRaWL (Tönshoff et al., 2023b).
To ensure diverse benchmarking tasks, use datasets from Benchmarking- GNNNs (Dwivedi et al., 2023), Long-Range Graph Benchmark (LRGBB) (Dwivedi et al., 2022), Open Graph Benchmark (OGB) (Hu et al., 2020a), and datasets from Platonov et al. (2022); Leskovec & Krevl (2014).
Benchmarking GNNs. We evaluated NeuralWalker's performance on five tasks from the Bench- marking GNNs suite: ZINC, MNIST, CIFARIO, PATTERN, and CLUSTER (results in Table 1). Notably, NeuralWalker achieved SOTA results three out of five datasets and matched the best- performing model on the remaining two. While GRIT exhibited superior performance on the two small synthetic datasets, its scalability to larger datasets, such as those in LRGB, is limited, as demonstrated in the subsequent paragraph. It is worth noting that NeuralWalker significantly outper- forms the previous SOTA random walk-based model, CRaWL. This improvement can be attributed to the integration of message passing and the Mamba architecture, as discussed in Sections 4. A more extensive empirical comparison of them is also given in Section 5.3, These results underscore Neural 's robust performance across diverse synthetic benchmark tasks.
Long-Range
Graph Benchmark. We further evaluated NeuralWalkerf ability to capture long- range dependencies on the recently introduced LRGB benchmark, encompassing five datasets de- signed to test this very capability (details in Rampášek et al. (2022); Dwivedi et al. (2022)). Note we used the filtered Mean Reciprocal Rank (MRR), introduced by Tönshoff
that for PCQM-Contar et al. (2023a), as the evaluation metric. NalkelWalker consistently outperformed all baseline methods across all but two tasks (see Table 2). Notably, on PascalVOC-S/ and COCO-SP, where previous work has shown the importance of long-range dependencies (e.g, Tönshoff et al. (2023a)), Neural significantly surpassed the SOTA models by a substantial margin, up to a 10% improvement.
Open Graph Benchmark. To assess WalkelWalker's scalability on massive quantities of graphs, we evaluated it on the OGB benchmark, which includes datasets exceeding 100K graphs each. For computational efficiency, we employed ID CNNs as the sequence layers in this experiment. NelralWalker achieved SOTA performance on two out of the three datasets (Table 3), demonstrating its ability to handle large-scale graph data. However, the OGBG-PPA dataset presented challenges with overfitting. On this dataset, Nelkal with just one block outperformed its multiblock counterpart on this dataset, suggesting potential limitations in regularization needed for specific tasks.
Node classification large graphs. We further explored Neural ability handle large graphs in node classification tasks. We integrated NeuralWalke with Polynormer (Deng et al., 2024), the current SOTA method in this domain. In this experiment, NeuralWalker utilized very long walks (up to 1.000 steps) with a low sampling rate (S 0.01) to capture long-range dependencies, replacing the transformer layer within Polynormer that still struggles to scale to large graphs even with linear complexity. Despite eschewing transformer layers entirely. NeuralWalke achieved performance comparable to Polynormer (Table 5), showing its scalability and effectiveness in modeling large graphs. Indeed, the complexity of Neural Golrer can be flexibly controlled by its sampling rate and length, as shown in Section 4. A notable highlight is NeuralWalker's s ability to efficiently process the massive pokec dataset (1.6M nodes) using single H100 GPU with 80GB of RAM.
5.2 MASKED POSITIONAL ENCODING PRETRAINING
Explicitly utilizing random walks as sequences offers a significant advantage: it allows for the application of advanced language modeling techniques. As proof-of-concept, we adapt the BERT pretraining strategy (Devlin et al., 2019) to the positional encodings Ape of random walks. Our approach involves randomly replacing 15% of the positions in hpe with a constant vector of 0.5, with the objective of recovering the original binary encoding vectors for these positions. This method can be further enhanced by combining with other established pretraining strategies, such as attributes masking (Hu et al., 2020b). Our experiments, as shown in Table 4, demonstrate that combining these strategies (i.e., we first pretrain the model with masked positional encoding prediction and then continue with masked attributes pretraining) significantly enhances performance on the ZINC dataset.
5.3
A ABLATION STUDIES
Here, we dissect the main components of our model architecture to gauge their contribution to predictive performance and to guide dataset-specific hyperparameter optimization.
8

---

Published as a conference paper at ICLR 2025
Table 3: Test performance on OGB (Hu et al., 2020a). Met- rics with mean + std of 10 runs are reported.
Table 4: Comparison of different pretraining strategies on the ZINC dataset. The pretraining was per- formed on ZINC without using any external data.
DATASET
OGBBG-MOLPCRA
OGBG-PPA
OGRG-CODE2
GIKAPISS
437.9K
158,1K
452.7K
AVG.
26.0
243.4
125.2
2.266.1
121.2
METRIC
AP
ACC:
GCN
0 0.0034
0.6857 + 0.0061
0,1595 + 0.0018
STRATEGY
ZINCI
GIN
0.2703 a 0.0023
0.7037 a 0.0107
0.158 & 0.0026
GRAPHTRANS
0.2761 0.0029
0.1830 0,0024
PRETRAIN
0.063 0.001
SAT
1 0.0056
MASKED ATTR.
0.061 +: 0.001
GPS
0,2907 1 0.0028
0.8015 1 0.0033
0,1894 1 0.0024
MASKED PE
0.055 0.004
CRAWL
0,2986 1 0.0025
MASKED PE ATTR.
0.053 +: 0.002
WALKRAWALK
0.3686 + 0.08311
0.7888 + 0.0059
0.1957 0.0025
ZINC
CIFAR1O
PsscalVOC-SP
500
time per spoch on onc GPL (5)
0.800
0.15
0.10
0,778
Validation performance
100
0.46
100
0.08
0.723
0.50
0.50
0:75
0.35
0.75
Sumpling ratic
Sampling role 7
Sampling rale 7
0.48
100
0.195
100
200
0.100
0.75
0.41
0.075
300
Random walk lengrh
Random walk longth
Random walk length
Figure 3: Validation performance when varying sampling rate and length of random walks.
We perform ablation studies on three datasets, from small to large graphs. Our analysis focuses on three key aspects: 1) We demonstrate the crucial role of integrating local and global message passing with random walks. 2) we evaluate various options for the sequence layer to identify the optimal choice. 3) We examine the impact of varying the sampling rate and length of random walks, revealing a trade-off between expressivity and computational complexity. Notably, these parameters allow explicit control over model complexity, a unique feature of our approach compared to subgraph MPNNs, which typically exhibit high complexity. All ablation experiments were performed on the validation set, with results averaged over four random seeds. The comprehensive findings are summarized in Table 6. Since NeuralWalker" output depends the sampled random walks at inference, we demonstrate its robustness to sampling variability in Appendix D.5.
Effect of local and global message passing. Motivated by the limitations of the depth-first nature inherent in pure random walk-based encoders, discussed in Section 3.3.4, this study investigates the potential complementary benefits of message passing. We conducted an ablation study (Table 6a) comparing Walkers variants with and without local or global message passing modules. For local message passing, we employed a GIN with edge features (Xu et al., 2019; Hu et al., 2019). Global message passing was explored using virtual node layers (Gilmer et al., 2017) and transformer layers (Vaswani al., 2017; Chen et al., 2022a). Keeping the sequence layer fixed to Mamba, observed that Nelral with GIN consistently outperforms the version without, confirming the complementary strengths of random walks and local message passing. The impact of global message passing, however, varies across datasets, a phenomenon also noted by Rosenbluth et al. (2024). Interestingly, larger graphs like PascalVOC-SP demonstrate more significant gains from global message passing. This observation suggests promising directions for future research, such as developing methods automatically identify optimal configurations for specific datasets.
Comparison of sequence layer architectures. We investigated the impact of various sequence layer architectures on walk embeddings, as shown in Table 6b. The architectures examined include CNN, transformer (with RoPE), and SSMs like S4 and Mamba. Surprisingly, transformers consistently underperformed compared to other architectures, contrasting with their good performance in other domains. This discrepancy may be attributed to the unique sequential nature of walk embeddings, which might not align well with the attention mechanism utilized by transformers.

---

Published as a conference paper at ICLR 2025
Table 5: Test performance on node classification benchmarks from Platonov et al. (2022) and Leskovec & Krevl (2014). Metrics with mean + std of 10 runs are reported.
DATASET
ROMAN-EMPIRE
MINESWEEPER
TOLOKERS
QUESTIONS
POKEC
# NODES
22.662
24,492
10,000
11,758
48,921
1,632.803
# EDGES
32.927
93,050
39,402
519,000
153,540
30,622,564
METRIC
ACC
ACC
ROC 1
ROC AUC
ROC AUC 1
ACC1
GCN
73.69 0.74
48.70 0.63
0.52
76.09 =
75.45 0.17
GRAPHSAGE
85.74 + 0.67
53.63 + 0.39
93.51 0.57
82,43 0.44
76.44 + 0.62
GAT(-SEP)
0..41
52.70
0.44
76.79 0.71
72.23 0.118
GPS
$2.00
03.1
90.63
83.71 0.48
71.73 1.47
OOM
NAGPHORMER
0.77
51.26
84.19 0.66
0
68.17 = 1.53
76.59 # 0.25 OOM
EXPHORMER
0.37
53.51 0.46
0.53
0.78
73.94
POLYNORMER
92.55 + 0.37
54,81 0.49
97.46 0.36
85.91 + 0.74
78.92 = 0.89
86.10 0.00
NELKALWALKER
92.92 0.36
54.58 0.36
97.82 a: 0.40
85.56 a 0.74
78.52 1.13
86.46 0.09
Table Ablation studies of NeuralWalker. Average validation performance over 4 runs is reported.
(a) Comparison of local and global message passing (MP). The sequence layer fixed to Mamba. VN de- notes the virtual node and Trans. denotes the trans-
(h) Comparison of sequence layers. Local and global MP selected to give the hest validation perfor- mance except for the highlighted row corresponding to CRaWL, which does not use message passing.
former layer.
SEQUENCE LAYER
ZINCI
CIFARIO1
PASCALVOC-SP
(LOCAL GLOBAL)
ZINCI
CIFARI01
PASCALVOC-SPI
MAMBA
0.078
0.4877
GIN + WIO
W/O J. w/n
0.090
0.085
80.885
79.035
0.4611
0.4525
$4
MAMBA (W/o BID)
0.089
0,082
77.970
74.910
0.4522
0.4559
GIN VN
0.078
78.610
0.4672
0.088
0,4652
GIN TRANS,
TRANS.
0,084
72,850
0.4316
GIN w/O
0.085
80.885
0.4661
CNN (W7G MP)
0.116
78.760
0,3954
Mamba emerged as the top performer across all datasets, consistently outperforming its predecessors, S4 and the unidirectional version. However, CNNs present compelling alternative for large datasets due to their faster computation (lypically 2-3x faster than Mamba on A A100). This presents a practical trade-off: Mamba offers superior accuracy but requires more computational resources. CNNs might be preferable for very large datasets or real-time applications where speed is critical. In benchmarking experiments, datasets. Finally, as predicted by Thm. 4.4, both our Mamba and CNN variants with message passing significantly outperform CRaWL which relies on CNNs and does not any message passing.
employed Mamba as the sequence layer, except for the OGB
Impact of random walk sampling strategies. We examined the impact of varying random walk sampling rates and lengths on NeuralWalker's performance, using Mamba as the sequence layer. While we adjusted the sampling rate during training, we fixed it at 1.0 for inference to maximize coverage. As unticipated, a larger number of longer walks led to improved coverage of the graph's 'ss structure, resulting in clear performance gains (Figure 3). However, this improvement plateaus as walks become sufficiently long, indicating diminishing returns beyond a certain threshold. Crucially, these performance gains come the cost of increased computation time, which scales linearly with both sampling rate and walk length, as predicted by Thm. 4.5. This underscores the trade-off between expressivity and complexity, which can be explicitly controlled through these two hyperparameters. In practice, this trade-off between performance and computational cost necessitates careful consideration of resource constraints when selecting sampling rates and walk lengths. Future research could explore more efficient sampling strategies to minimize the necessary sampling rate.
6 CONCLUSION
We have introduced NeuralWalker, powerful and flexible architecture that combines random walks and message passing to address the expressivity limitations of structural encoding graph learning. By treating random walks as sequences and leveraging advanced sequence modeling techniques, NelralWalker achieves superior performance compared to existing GNNs and GTs, as demonstrated through extensive experiments various benchmarks. Looking forward, we acknowledge opportuni- ties for further exploration. First, investigating more efficient random walk sampling strategies with improved graph coverage could potentially enhance Walker'alker's performance. Second, exploring more sulf-super learning techniques for learning on random walks holds promise for extending Walker's applicability unlabeled graphs.
10

---

Published as a conference paper at ICLR 2025
AVAILABILITY
Our code is available at httppp////sshhhh...c///rrrreaaaa ker..
ACKNOWLEDGEMENTS
We thank Luis Wyss and Trenton Chang for their insightful feedback on the manuscript.
REFERENCES
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 Symposium on Foundations of Computer Science (SFCS), 1979.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR), 2021.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In International Conference Learning Representations (ICLR), 2020.
Ali Behrouz and Farnoosh Hashemi. Graph mamba: Towards learning graphs with state space models. arXiv preprint arXiv:2402.08677, 2024.
Karsten M Borgwardt and Hans-Pete Kriegel. Shortest-path kernels on graphs. In International conference on data mining (ICDM), 2005.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans. Puttern Anal. Mach. Intell., 6666)6657-668 2023.
Xavier Bresson and Thomas Laurent. arXiv:1711.07553, 2017.
Residual gated
graph convnets.
arXiv preprint
Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph-structured data. In International Conference on Machine Learning (ICML), 2020.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. International Conference on Machine Learning (ICML), 2022a.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: tokenized graph transformer for node classification in large graphs. In International Conference Learning Representations (ICLR), 2022b.
Ching-Yas Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expressiee graph transformer in linear time. In International Conference on Learning Representations (ICLR), 2024.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the North American Chapter of the Association for Computational Linguistics (NAACL), 2019.
Yuhui Ding, Antonio Orvieto, Bobby He, and Thomas Hofmann. Recurrent distance filtering for graph representation learning. In International Conference on Machine Learning (ICML), 2024.
R.M. Dudley. Real analysis and probability. Cambridge University Press, 2018 8.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference Learning Representations ()CRR), 2021.

---

Published as a conference paper at ICLR 2025
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Vijay Prakash Dwivedi, Chaitanya Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop on Reprexentation Learning on Gruphs and Manifolds, 2019.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kemels: Hardness results and efficient alternatives. In Conference on Learning Theory (COLT). Springer, 2003.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Conference on Knowledge Discovery and Data Mining (KDD), 2016.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752. 2023.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations (ICLR), 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovee. Strategies for pre-training graph neural networks. In International Conference Learning Representations (ICLR), 2019.
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 Advances in Neural Information Processing Systems (NeurIPS), 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations (ICLR), 2020b.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference on Machine Learning (ICML), 2018.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In International Conference on Machine Learning (ICML), 2003.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2016.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Jure Leskovec and Andrej Krevi. SNAP Datasets: Stanford large network dataset collection. http: // //snap. stanford. edu data, June 2014.
Derek Lim. Felix Hohne, Xiuyu Li, Sijia Linda Huang. Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non non-homophilous graphs: New benchmarks and strong simple methods. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
László Lovász. Random walks graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
12

---

Published as a conference paper at ICLR 2025
Liheng Ma, Chen Lin, Derek Lim, Adriana Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference Machine Learning (ICML), 2023.
Puneet K Dokania, Mark Coates, Philip
Pierre Mahé, Nobuhisa Ueda, Tatsuya Akutsu, Lean-Luc Perret, and Jean- San-Philippe Vert, Graph kernels for molecular pruuture-activityy relationship analysis with support vector machines. Journal of chemical information and modeling, 45(4):939-955) 2005.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. In International Conference on Machine Learning (ICML), 2024.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667 2021.
Gaspard Michel, Giannis Nikolentzos, Johannes F Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning (ICML), 2023.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29(2):429 443, 1997.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference Learning Representations (ICLR), 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Conference Knowledge Discovery and Data Mining (KDD), 2014.
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? In International Conference on Learning Representations (ICLR), 2022.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, and Martin Grohe Distinguished in uniform: Self-attention vs. virtual nodes. International Conference on Learning Representations (ICLR), 2024.
Hamed Shirzad. Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning (ICML), 2023.
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568: 127063, 2024.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the rangerange graph benchmark. In Learning Graphs Conference, 2023a.
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 (TMLRR) 2023b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova. Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
13

---

Published as a conference paper at ICLR 2025
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces, arXiv preprint arXiv:2402.00789, 2024.
Shida Wang and Beichen Xue. State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Yanbang Wang. Yen-Y Yu Chang, Yunyu Liu, Jure Leskovee, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974 2021.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini. Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, (6(1)):07-4744 2022.
Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph-based graph representation learning. Proceedings of the VLDB Endowment, 15(11):2788 229222267769 2022.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of sequence-to-sqquene functions? In International Conference on Learning Representations (ICLR), 2020.
Lianghui Zhu, Bencheng Liao, Qian Zhang, Xinlong Wang, Wenyu Liu, and Xinggang Wang. Vision mamba: Efficient visual representation learning with bidirectional state space model. arXiv preprint arXiv:2401.09417 2024.
Wenhao Zhu, Tianyu Wen, Guojic Song, Liang Wang, and Bo Zheng. On structural expressive power of graph transformers. In Conference on Knowledge Discovery and Data Mining (KDD), 2023.
14

---

Published as a conference paper at ICLR 2025
Appendix
This appendix provides both theoretical and experimental materials and is organized as follows: Section A provides more detailed background related work. Section B presents some additional remarks on Neural Walker, including limitations and societal impacts. Section provides theoretical background and proofs. Section provides experimental details and additional results.
A BACKGROUND
A.1 MESSAGE-PASSING GRAPH NEURAL NETWORKS
Graph Neural Networks (GNNs) refine node representations iteratively by integrating information from neighboring nodes. Xu et al. (2019) (Xu et al., 2019) provide a unifying framework for this process, consisting of three key steps: AGGREGATE, COMBINE, and READOUT, Various GNN architectures can be seen as variations within these functions.
In each layer, the AGGREGATE step combines representations from neighboring nodes (c.g.. using sum or mean). which are then merged with the node's ' previous representation in the COMBINE step. This is typically followed by non-linear activation function, such ReLUU. The updated representations are then passed to the next layer, and this process repeats for each layer in the network. These steps primarily capture local sub-structures, necessitating deep network to model interactions across the entire graph.
The READOUT function ultimately aggregates node representations to the desired output granularity, whether at the node or graph level. Both AGGREGATE and READOUT steps must be permutation invariant. This framework offers comprehensive perspective for understanding the diverse array of GNN architectures.
A.2 TRANSFORMER ON GRAPHS
While Graph Neural Networks (GNNs) explicitly utilize graph structures, Transformers infer node relationships by focusing on node attributes. Transformers, introduced by Vaswani et al. (2017), treat the graph (multi-)set of nodes and use self-attention to determine node similarity.
Transformer consists two main components: self-attention module and a reed-forward neural network (FFN). In self-attention, input features X are linearly projected into query (Q), key (K), and value (V) matrices. Self-attention is then computed as:
QK
Atin( X) == softmma
V VERdx
Vilee
where dout is the dimension of Q. Multi-head attention, which concatenates multiple instances of this equation, has proven effective in practice.
Transformer layer combines self-attention with skip connection and FFN:
X' - (X).
X FFN(X') ReLU(X'W,)WS
Stacking multiple layers forms Transformer model, resulting in node-level representations. However, due to self-attention's 's permutation equivariance, Transformers produce identical representations for nodes with matching attributes, regardless of their graph context. Thus, incorporating structural information, typically through positional or structural encoding such as Laplacian positional encoding random walk structural encoding (Dwivedi et al., 2021; Rampášek al., 2022), is crucial.
15

---

Published as a conference paper at ICLR 2025
A.3 STATE SPACE MODELS
As we treat random walks explicitly as sequences, recent advances in long sequence modeling could be leveraged directly model random walks. SSMs a type of these models that have shown promising performance in long sequence modeling. SSMs map input sequence ar(1) E R to some response sequence y(t) through an implicit state h(t) E R and three parameters (A, C):
((())= Ah(t) + Br((),
y(t) = Ch(().
For computational reasons, structured SSMs (S4) (Gu et al., 2021) proposes to discretize the above system by introducing a time step variable A and discretization rule, leading to reparametrization of the parameters A and B. Then, the discrete-time SSMs can be computed in two ways either as linear recurrence or global convolution. Recently, selection mechanism (Gu Dao, 2023) has been introduced to control which part of the sequence can flow into the hidden states, making the parameters in SSMs time and data-dependent. The proposed model, named Mamba, significantly outperforms its predecessors and results in several successful applications in many tasks. More recently, a bidirectional version of Mamba (Zhu et al., 2024) has been proposed to handle image data, by averaging the representations of both forward and backward sequences after each Mamba block.
B ADDITIONAL REMARKS ON NEURAL WALKER
B.1 ILLUSTRATION OF THE POSITION ENCODINGS FOR RANDOM WALKS
Here, give visual example of the positional encodings that we presented in Section 3.2. The example is shown in Figure 4.
Idantity Eacoding
0
Walk
A Adjaoency Fincoding
0
0
0
0
0 0
0 0_
Figure 4: An example of the identity encoding and adjacency encoding presented in Secion 3.2. On the random walk colored in red, we have idw (4, 3] = 1 as w4 w/ 6. We have adjw = as WggWo E is an edge of the graph.
B.2 GL.BBAL MESSAGE PASSING TECHNIQUES
Even though long random walks could be sufficient to capture global information, we empirically found that global message passing is still uscful in certain tasks. Here, consider two techniques, namely virtual node and transformer layer. Similar to Gilmer et al. (2017); Tönshoff et al. (2023b), a virtual node layer could be simple solution achieve this. Such layer is explicitly defined the following:
(+) MLP by
(+) h
Σ ΣnT(())) (T(())
(T) = h (w) (+),
(8)
DEV
where MLP is trainable MLP, h4f (x) represents the virtual node embedding at block f and Af-(x) Alternatively, one could use any transformer layer to achieve this. The vanilla transformer layer is given by:
att (v) (w) (v) Attn(h")) (v),
by (u) (ar"()) (c) + MLP (u)),
where Attn is a trainable scaled dot- product attention layer (Vaswani et al., 2017). This layer is widely used in recent GT models (Ying et al., 2021; Chen al., 2022a; Rampášek al., 2022).
16

---

Published as a conference paper at ICLR 2025
B.3 LIMITATIONS
NeuralWalker demonstrates good scalability to large graphs. However, one potential limitation lies in the trade-off between the sampling efficiency of random walks and graph coverage for very large graphs. In this work, we explored a computationally efficient sampling strategy but probably not with the optimal graph coverage. Investigating more efficient random walk sampling strategies that improve coverage while maintaining computational efficiency could further enhance NeuralWalker's performance.
Additionally, while experiments focused modern SSMs like Mamba and S4, which provide efficient implementations, we acknowledge the potential oversight of classical Recurrent Neural Networks (RNNs) such as LSTMs. This consideration is particularly relevant for scenarios with unbounded walk lengths, where RNN-based NeuralWalker models might achieve greater expressivity than their MSM-based counterparts, given RNNs' superior expressivity in terms of circuit complexity when processing unbounded sequences (Merrill et al., 2024).
Finally, we identify scarcity of publicly available graph datasets with well-defined long-range dependencies. While datasets like LRGB provide valuable examples, the limited number of such datasets hinders comprehensive evaluation and the potential to push the boundaries of long-raan raage dependency capture in graph learning tasks. Furthermore, based on our experiments and Tönshoff al. (2023a), only out of the 5 datasets in LRGB seem to present long-range dependencies.
B.4 BROADER IMPACTS
While our research primarily focuses on general graph representation learning, we recognize the importance of responsible and ethical application in specialized fields. When utilized in domains such as drug discovery or computational biology, careful attention must be paid to ensuring the trustwor- thiness and appropriate use of our method to mitigate potential misuse. Our extensive experiments demonstrate the significant potential of our approach in both social network and biological network analysis, highlighting the promising societal benefits our work may offer in these specific areas.
C THEORETICAL RESULTS
In this section, we present the background of random walks on graphs and the theoretical properties of Neural
Definition C.1 (Walk feature vector). For any graph G = (V, x, 2) and W E We(G), the walk feature vector Xw of W defined, by concatenating the node and edge feature vectors as well as the positional encodings along W of window size f, as
Xw = (x(w,,, 2(w,ww+1) hpel le) E R((+1)xdmat
where hig is the positional encoding in Section 3.2, z a(wewe+1) O, and dwalk == d d' + dre. By abuse of notation, we denote by (G) the set of walk feature vectors G, and by P(W(G)) distribution of walk feature vectors on G.
Lemma C.2. The walk feature vector with full graph coverage uniquely determines the graph, i.e. for two graphs G and G' in Gn if there exists a walk W E We(G) visiting all nodes on and a walk W' We visiting all nodes G' such that Xw Xw', then G and G' are isomorphic.
Proof. The proof is immediate following the Observation 1 of Tönshoff et al. (2023b).
Now if we replace the normalization factor (N (C)))((())) in the walk aggregator in Section 3.3.3 with simpler deterministic constant mł/[v] and apply an average pooling followed by linear layer to the output of the walk aggregator, then the resulting function Jf... G IR
+ u." T x: + defined on the graph space G can be rewritten as the average of some function of walk feature vectors:
ff.m (G)
1
Σ
f(Xw).
(10)
(WP..(W((G))
17

---

Published as a conference paper at ICLR 2025
where
s(Xw) = - Sheg b),
(11)
WLEW
and hw defined in Eq. (1) depend on Xw-
Note that the above replacement the normalization factor is not a strong assumption. is based on the following lemmas:
Lemma C.3 ((Lovász, 1993)), Let G be connected graph. For random walk W ~ P(W(G))
with W (Wn, Wl,..., Wt....), we denote by Pt the distribution of Wr. Then,
d(v)
(T)
2
where d(v) denotes the degree of node v, is the (unique) stationary distribution, i.e, if Po = a then Pt = for any t. If Po = (V), then we have
(ON(Pm(WW(G)) mld(v)
2
In particular, G is regular graph, T(V) E (Pm (W)( = mt/lv\.
1/1vI the uniform distribution nad
Lemma C.4 (LLovász, 1993)). G a non non-bipartite graph, then Pt + (V) as co.
The above two lemmas link the random normalization factor the deterministic one.
we have sufficiently large number of random walks, by the law of large numbers, we have
Ofm.r (G) C.S. Oz ((wp--
(12)
where 0. denotes the almost sure convergence. This observation inspires us to consider the following integral probability metric (Müller, 1997) comparing distributions of walk feature vectors:
d dG, = sup [x - Pxwr--(:iccry]((XX::]]]] fer
(13)
where FF is some functional class, such the class of neural networks defined by the NeuralWalker model. The following result provides us insight into the rate of convergence of m to gz
co. Theorem C.5 (Convergence rate). Assume that Varlf(Xw) = o² 00. Then, as m tends to infinity, we have
mm (G)f.m.(())-9 S, N(0,03)
where 4 denotes the convergence in distribution.
Proof. The proof follows the central limit theorem (Dudley, 2018).
dF.e is actually a metric on the graph space Gn of bounded order n if F is a universal space and is
sufficiently large:
Theorem C.6. F is universal space and é 2 4n3, then d : 9 G + R4 is metric on Gn satisfying:
(positivity) if G and G' non-isomorphic, then d, dF, 0. (symmetry) d (G, G') = dr,(
(triangle inequality) d,, (G, < dG,
Proof. The symmetry and triangle inequality are trivial by definition of d Let us focus the positivity. We assume that dG,,(G, G") = 0. By the universality of F. for any E > and C(Rdwa)) the space of bounded continuous functions on Rdwi, there exists g E F such that
| مااا0 S..
18

---

S n and Published as a conference paper at ICLR 2025
We then make the expansion
Bxwrrrmccon/((Ww) -ww.:/ E Exw=>Pwaccn)lf(X)) (awn(a))
(Xw-)))(() ( (Xw) -x (ow.
The first and third terms satisfy
Ex Pxx- - Ex Exy-- Bxw (f(Xw) g(Xw)l
and the second term equals 0 by assumption. Hence,
E FXw--P(wccc)l((XW) - Exxr== S 28,
for all f E CR and = 0. This implies P(We(G)) = P(W)(G")) by Lemma 9.3.2 of Dudley (2018), meaning that the distribution of walk feature vectors of length & in G is identical to the distribution in G". Without loss of generality, we assume that G and G' are connected and our arguments can be easily generalized to each connected component if G is not connected. Now for random walk W ~ P(W(G)), let us denote by Tw the number of steps to reach every node on the graph. Then E[Tw] is called the cover time. A well-known result in graph theory (Aleliunas et al., 1979) states that the cover time is upper bounded:
E[Tw] S 4|V[[
Therefore the cover time for graphs in G, is uniformly bounded by [[[w] S 4n as [V| [E] < n² Then, by applying Markov's incquality, have
ETwl 4n +
P[TW- 4n +e]
P[Tw 4m + +
4n +
for any > O. Thus, P[Tw- I 4n O which means that there exists random walk of not greater than 4n that visits all nodes in G. As a result, there exists a random walk of length reaching all nodes for f 2 4n P(W)(G) = P(W)(G")) implies that there also exists random walk W in G' such that Xw = Xw. As a consequence, G and G' are isomorphic following Lemma C.2.
Now if we remove the condition on the random walk length f, we still have a pseudometric space without the positivity in Thm C.6. Moreover, we define the following isomorphism test:
Definition C.7 (u-subgraph isomorphism test). We define that two graphs G and G' are not distin- guishable by the k-subgraph isomorphism test iff they have the same set of induced subgraphs of size k, iee. Sn (G) = (G') with (G) denoting the set of induced subgraphs of size k.
And have the following result which provides weak positivity of d for any {>> 0: Theorem C.8. I and G' are distinguishable by the (1+/2) 1)-subgraph isomorphism test, then dr, G') >
Proof. We assume that dr.e(G. G') = O. Using the same arguments as in Thm. C.6, we have P(W)(G)) = P(We(G')). Let [9/2] + 1. For any induced subgraph H E S& (G), there exists walk of length É, in the worst case, that visits all its nodes. To see this, let assume that G is connected without loss of generality. Then, there exists a spanning tree of H. Through depth-first search this spanning tree, there exists walk of length 2(k 1) < É that visits all the nodes, by visiting each edge at most twice in the spanning tree. Now as G and G' have the same distributions of walk feature vectors, the same walk feature vector should be found in G', thus H S2 (G'). Thus, have St (G) C (G'). Similarly, we have the other inclusion and therefore (G) = Sx
C.I STABILITY RESULTS
Now that we have a metric space (Gn, dr,1) with E 2 4mz,, we can show some useful properties of Of.e:
19

---

Published as a conference paper at ICLR 2025
Theorem C.9 (Lipschiz continuity of 95.e). For any G and G' in In if F is a finctional space containing f. we have
(9s,e(G) gr.e(G")] 5 dr,)(G,G").
(14)
Proof. The proof is immediate from the definition of dy,t.
The Lipschiz property is needed for stability to perturbations in the sense that if G' is close to G in (Gn, dF,,),, then their images by gy.e (output of the model) are also close.
C.2 EXPRESSIVITY RESULTS
Theorem C.10 (Injectivity of g5.e). Assume F is universal space. I and Gi' are non-isomorphic graphs, then there exists f E F such that g5,e(G) + g1.e(G") if 4 4max( I
Proof. We can prove this by contrapositive. We note that G, G" Graax with 7max [V]]. Assume that for all f F, (r. G) = gG.) This implies that d G") Then by the positivity of dy in Immaes G and G' are isomorphic.
The injectivity property ensures that our model with sufficiently large number of sufficiently long (2 4n²) random walks can distinguish between non-isomorphic graphs, highlighting its expressive power.
Complementary to the above results, we now show that the expressive power of our model exceeds that of ordinary message passing neural networks even when considering random walks of small size. Additionally, we show that the expressive power of our model is stronger than the subgraph isomorphism test up certain size.
We first state a result on the expressive power of the walk aggregator function (defined in Sect. 3.3.3). We show that there exist walk aggregator functions such that for node v, this function encodes (multi-)sse of induced subgraphs that v is part of. Let G, denote the (isomorphism class of) graph G rooted node and let the set xx(G,,) v) = (IC. G[( wh v}}, W (wo, we), k, W E }.))
Lemma C.11. There exists a walk aggregator function fagg such that for any nodes u E G. e E G' and walk length f, it holds that foze(1) laze if and only if (e(G,v) = xe(G",
Proof. Recall from Sect. 3.2 that the positional encoding of a walk W encodes the pairwise adjacency of nodes contained in W. In fact, this encoding also contains the complete information on subgraphs induced by prefixes of W. More formally, for length- walk W E We(G', the first & + 1 rows of the corresponding walk feature vector Xw encode the induced subgraph G Gl(wo..... w. With wyk v. it can also be inferred about the structural role of in G[( -.. wKk }}. Further recall that walk aggregator functions aggregate information from all walks passing through a node. Thus, we can design a function fage that aggregates the induced subgraph information for sets of subgraphs into node embeddings. More precisely, for a node E G and the set of walks WG) there exists such a function fuge( (1) that maps to an embedding which encodes the set v). By considering the complete set of walks We(G), we guarantee a deterministic embedding. Assuming a sufficiently powerful neural network, it can shown that such a function fagy can be realized by our model.
We are ready to prove results on Walkels ability to distinguish between substructures.
Theorem C.12. For any E 2, NeuralWalker equipped with the complete walk set We is strictly more expressive than 1-WL and the (L5/2) + 1)-subgraph isomorphism test, and thus ordinary MPNNs.
Proof. For the subgraph isomorphism test, we simply use the above theorem and Thm. C.8 which suggests that there exists f E F such that gG. # (r.) if G and G' are distinguishable by the (1%/2 + -Jssuggraph isomorphism test.
Concerning the comparison to the 1-WL test, utilize the result of lemma C.11. A walk aggre- gator function fazg. as defined in this lemma, maps nodes e E G to an embedding encoding the subgraph information re(G,w) v). For instance, using walk length & = 2, the node embeddings contain
20

---

Published as a conference paper at ICLR 2025
Table 7: Summary of the datasets Dwivedi et al. (2023; 2022): Hu et al. (2020a) used in this study.
PREDICTION
PREDICTION
DIRECTEO
NODES
EDGES
LEVEL
TASK
ZINC
12,000
23.2
24.9
No
REGRESSION
MEAN ABS. ERROR
MNIST
70,000
70.6
564.5
YES
GRAPH
10-CLASS CLASSIF.
ACCURACY
CIFARIO
60,000
117.6
941.1
YES
GRAPH
10-CLASS CLASSIF.
ACCURACY
PATTERN
INDUCTIVE NODE
BINARY CLASSIF.
CLUSTER
12,000
117.2
2,150.9
No
INDUCTIVE NODE
6-CLASS CLASSIE.
ACCURACY
PASCALVOC-SP
11,355
479.4
2.710.5
No
INDUCTIVE NODE
21-CLASS CLASSIF.
EI SCORE
COCO-SP
123,286
476.9
2.693.7
No
INDUCTIVE NODE
81-CLASS CLASSIF.
EL SCORE
PEPTIDES-FENE FUNC
15,535
150.9
307.1
No
GRAPH
10-TASK CLASSIF.
AVG. PRECISION
PCQM-
529.434
30.1
61.0
INDUCTIVE
LINK RANKING
PEPTIDES-STRIN STRUCT
15,535
150.9
307.3
No
GRAPH
11-TASK REGRESSION
MEAN ARS. ERROR
MOLP-RA
437.929
26.0
28.1
No
128. TASK CLASSIF.
AVG. PRECISION ACCURACY
OGBG-PPA
158,100
243.4
2.266.1
No
GRAPH
37-TASK CLASSIF.
DORG-CODE2
452,741
125.2
124.2
YFS
GRAPH
5 TOKEN SEQUENCE.
FI SCORE
information about the (multi-)set of triangles that nodes are part of. Then, using NeuralWalker message passing layers, this subgraph information leads to more powerful graph representations when compared to ordinary message passing without such enriched node embeddings. In fact, analogously to e.g. Bouritsas et al. (2023), it can be shown that with sufficient number of message passing layers and powerful readout network, the resulting graph representations are strictly more powerful than ordinary MPNNs.
C.3 COMPLEXITY RESULTS
Theorem C.13 (Complexity). The complexity of NeuralWalker, when used with the Mamba sequence layer (Gu & Dao, 2023), is (kdn((7 + B)), where k, d, n, "r l, denote the number of layers, hidden dimensions, the (maximum) number nodes, sampling rate, length of random walks, and the average degree, respectively.
Proof. The complexity of sampling random walks is O(nzf). The Mamba model with A: layers and hidden dimensions d operates on (nny) random walks of length f. As Mamba scales linearly to the sequence length, number of layers, and hidden dimensions (Gu & Dao, 2023), its complexity is (kdny))). The complexity of message passing layers of hidden dimensions Okdn33) where should be much smaller than yf in general.
is worth noting that the space complexity of Walker is the same its time complexity, due to the fact that Mamba is linear to the sequence length for both time and space complexity (Gu & Dao, 2023).
D EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
In this section, we provide implementation details and additional experimental results
D.1 DATASET DESCRIPTION
We provide details of the datasets used in our experiments. For each dataset, we follow their respective training protocols and use the standard train/validation/test splits and evaluation metrics.
ZINC (MIT License) (Dwivedi et al., 2023). The ZINC dataset a subset of the ZINC database, containing 12,000 molecular graphs representing commercially available chemical compounds. These graphs range from 9 to 37 nodes size, with each node corresponding to a "heavy atom" (one of 28 possible types) and each edge representing bond (one of types). The goal is to predict the constrained solubility (logP) using regression. The dataset conveniently pre-split for training. validation, and testing, with standard split of 10,000/1,0000 ,000 molecules for each set, respectively.
21

---

Published as a conference paper at ICLR 2025
Table 8: Summary of the datasets for transductive node classification Platonov et al. (2022); Leskovec & Krevl (2014) used in this study.
DATASET
HOMOPHILY SCORE
# NODES
# EDGES
# CLASSES
METRIC
ROMAN-EME EMMPRE
0.023
22.662
32,927
18
ACCURACY
AMAZON-RATINGS
0.127
24,492
93,050
ACCURACY
MINESWEEPER
0.009
10,000
39,402
2
ROC AUC
TOLOKERS
11,758
$19,000
QUESTIONS
0.072
48,921
153,540
2
ROC AUC
POKEC
0.000
1,632,803
30,622,564
2
ACCURACY
MNIST and CIFARIO (CC BY-SA 3.0 and MIT License) Dwivedi et al. (2023). MNIST and CIFARIO are adapted for graph-hased learning by converting each image into a graph. This is achieved by segmenting the image into superpixels using SLIC (Simple Linear Iterative Clustering) and then connecting each superpixel to its 8 nearest neighbors. The resulting graphs maintain the original 10-class classification task and standard dataset splits (i.e., 55K/5K/10K vrain/validation/eest for MNIST and 45K/5K/10K for CIFAR10.).
PATTERN and CLUSTER (MIT License) (Dwivedi et al., 2023). PATTERN and CLUSTER are synthetic graph datasets constructed using the Stochastic Block Model (SBM). They offer a unique challenge for inductive node-level classification, where the goal is to predict the class label unseen nodes. PATTERN: This dataset presents the task of identifying pre-defined sub-graph patterns (100 possible) embedded within the larger graph. These embedded patterns are generated from distinct SBM parameters compared to the background graph, requiring the model to learn these differentiating connection characteristics. CLUSTER: Each graph in CLUSTER consists of six pre-defined clusters generated using the same SBM distribution. However, only one node per cluster explicitly labeled with its unique cluster ID. The task is to infer the cluster membership (ID) for all remaining nodes based solely on the graph structure and node connectivity information.
PASCALVOC-SH and COCO-SP (Custom license for Pascal VOC 2011 respecting Flickr terms of use, and CC BY 4.0 license) (Dwivedi et al., 2022). VOCCAIVOC-SP and COCÓ-SP are graph datasets derived from the popular image datasets Pascal VOC and MS COCO, respectively. These datasets leverage SLIC superpixellization, a technique that segments images into regions with similar properties. In both datasets, each superpixel is represented node in graph, and the classification task to predict the object class that each node belongs to.
PEPTIDES-FUNC and PEPTIDES-STRUCE (CC BY-NC 4.0) (Dwivedi et al., 2022). Peptides-func and Peptides-struct offer complementary views of peptide properties by leveraging atomic graphs derived from the SATPdb database. Peptides-fune focuses on multi-label graph classification, aiming to predict one or more functional classes (out of 10 non-exclusive categories) for each peptide. In contrast, Peptides-stree employs graph regression to predict 11 continuous 3D structural properties of the peptides.
PCQM-CONTACE (CC BY 4.0) (Dwivedi et al., 2022). The PCQM-Contact dataset builds upon PCQM4MV2 (Hu et al., 2020a) by incorporating 3D molecular structures. This enables the task of binary link prediction, where the goal is to identify pairs of atoms (nodes) that are considered to be in close physical proximity (less than 3.5 angstroms) in 3D space, yet appear far apart (more than 5 hops) when looking solely at the 2D molecular graph structure. The standard evaluation metric for this ranking task is Mean Reciprocal Rank (MRR). As noticed by Tönshoff al. (2023a), the original implementation by Dwivedi et al. (2022) suffers from false negatives and self-loops. Thus, we use the filtered version of the MRR provided by Tönshoff et (2023a).
OGBG-MOLPCEA (MIT License) (Hu et al., 2020a). The by the Open Graph Benchmark (OGB) (Hu et al., 2020a) from MoleculeNet, focuses on multi-task binary classification of molecular properties. This dataset leverages a standardized node (atom) and edge (bond) feature representation that captures relevant chemophysical information. Derived from PubChem BioAssay, egbg-molper offers the task of predicting the outcome of 128 distinct bioassays, making it valuable for studying the relationship between molecular structure and biological activity.
dataset, incorporated
22

---

Published as a conference paper at ICLR 2025
OGBG-PPA (CC-0 license) (Hu et al., 2020a). The PPA dataset, introduced by OGB (Hu et al., 2020a), focuses on species classification. This dataset represents protein protein interactions within network, where each node corresponds protein and edges denote associations between them. Edge attributes provide additional information about these interactions, such as co-expression levels. We employ the standard dataset splits established by OGB (Hu et al., 2020a) for analysis.
OGBG-CODE2 (MIT License) (Hu et al., 2020a). CODE2 (Hu et al., 2020a) is a dataset containing source code from the Python programming language. It is made up of Abstract Syntax Trees where the task is to classify the sub-tokens that comprise the method name. We use the standard splits provided by OGB (Hu et al., 2020a).
HOMAN-EMPIRE (MIT License) (Platonov et al., 2022). This dataset creates graph from the Roman Empire Wikipedia article. Each word becomes a node, and edges connect words that are either sequential in the text grammatically dependent (based on the dependency tree). Nodes labeled by their syntactic role ( 17 most frequent roles are selected as unique classes and all the other roles are grouped into the 18th class). We use the standard splits provided by Platonov al. (2022).
AMAZON-RATINGE (MIT License) (Platonov et al., 2022). Based on the Amazon product co- purchase data, this dataset predicts a product's average rating (5 classes). Products (books, etc.) are nodes, connected if frequently bought together. Mean fastText embeddings are used for product descriptions as node features and focus on the largest connected component for efficiency (5-core). We use the standard splits provided by Platonov et al. (2022).
MINESWEEPER (MIT License) (Platonov et al., 2022). This is a synthetic dataset with a regular 100x 100 grid where nodes represent cells. Each node connects to its eight neighbors (except edges). 20% of nodes are randomly mined. The task is to predict which are mines. Node features are one-hot-encoded numbers of neighboring mines. but are missing for 50% of nodes (marked by separate binary feature). This grid structure differs from other datasets due to its regularity (average degree: 7.88). Since mines are random, both adjusted homophily and label informativeness are very low. We use the standard splits provided by Platonov et al. (2022).
TOLOKERS (MIT License) (Platonov et al., 2022). This dataset features workers (nodes) from crowdsourcing projects. Edges connect workers who have collaborated on least one of the 13 projects The task is to predict banned workers. Node features include profile information and performance statistics. This graph (1 (11.8K nodes, avg. degree 88.28) is significantly denser compared to other datasets. We use the standard splits provided by Platonov et al. (2022).
QUESTIONS (MIT License) (Platonov et al., 2022). This dataset focuses on user activity prediction. Users are nodes, connected if they answered each other's 's questions (Sept 2021 Aug 2022). The task to predict which users remained active. User descriptions (if available) are encoded using fastText embeddings. Notably, 15% lack descriptions and are identified by separate feature. We use the standard splits provided by Platonov et al. (2022).
POKEC (unknown License) (Leskovec & Krevl, 2014). This dataset retrieved from SNAP (Leskovec & Krevl, 2014) and preprocessed by Lim et al. (2021). The dataset contains anonymized data of the whole network of Pokec, the most popular online social network in Slovakia which has been provided for more than 10 years and connects more than 1.6 million people. Profile data contains gender, age, hobbies, interests, education, etc, and the task is to predict the gender. The dataset was not released with license. Thus, we only provide numerical values without any raw texts from the dataset.
D.2 COMPUTING DETAILS
We implemented our models using PyTorch Geometric (Fey & Lenssen, 2019) (MIT License). Experiments were conducted on a shared computing cluster with various CPU and GPU configurations, including a mix of NVIDIA A100 (40GB) and H100 (80GB) GPUs. Each experiment allocated resources on a single GPU, along with 4-8 CPUs and up to 60GB of system RAM. The run-time of each model measured single NVIDIA 1100 GPU.
23

---

Published as a conference paper at ICLR 2025
Table Hyperparameters for the 5 datasets from GNN Benchmarks (Dwivedi al., 2023).
HYPERPARAMETER
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
BLOCKS
3
3
16
HIDDEN
80
80
80
80
32
SEQUENCE LAYER
MAMBA (BIDIRECTIONAL)
LOCAL MESSAGE PASSING
GIN
GLOBAL MESSAGE PASSING
VN
NONE
NONE
VN
VN
DROPOUT
0.0
0.0
0.0
0.0
0.0
GRAPH POOLING
SUM
MEAN
MEAN
RW SAMPLING RATE
0.5
0.5
RW LENGTH
50
200
RW POSITION ENCODING WINDOW SIZE
32
BATCH SIZE
32
32
LEARNING RATE
0.002
0.002
0.002
0.002
0.01
EPOCHS
100
WARMUP EPOCHS
WEIGHT DECAY
1E-6
1E-6
0.0
0.0
PARAMETERS
502K 16s/8.411
112K
112K
504K
525K
TRAINING TIME (CPOCи/TOTAL)
90s/2.511
95s/2.611
57s/1.611
241s/6.711
Table 10: Hyperparameters for the 5 datasets from LRGB (Dwivedi al., 2022).
HYPHRPARAMITRR
PASCALVOC-SP COCO-SP
PEPTIDES-PUNC
PEPTIDES-STRUCT
PCQM-CONTACT
HIDDEN DIM
56
56
56
80
SEQUENCE LAYER
MAMBA (BIDIRACTIONAL)
PASSING
GLOBAL MESSAGE PASSING
TRANS. 0.0
NONE 0.0
VN
VN
VN
DROPOUT
0.0
0.0
0.0
RW SAMPLING RATE
0.5
0.25
0.5
0.5
0.5
RW LENGYH
100
100
100
100
75
16
BATCH SIZE
32
32
32
256
LEARNING RATE
0.002
0,002
0.002
0.004
0.001
WARMUP EPOCHS
10
10
10
WEIGHT DECAY
16-06
0.0
0.0
0.0
0.0
TRAINING TIME (SPOCH/UUTL)
218s/12H
1402s/78H
112s/6.24 2H
112s/6.2H
528s/22H
D.3 HYPERPARAMETERS
Given the large number of hyperparameters and datasets, did perform an exhaustive search beyond the ablation studies in Section 5.3. For each dataset, we then adjusted the number of layers, the hidden dimension, the learning rate, the weight decay based on hyperparameters reported in the related literature (Rampášek et al., 2022; Tönshoff et al., 2023b; Deng et al., 2024; Tönshoff et al., 2023a).
For the datasets from Benchmarking GNNs (Dwivedi et al., 2023) and LRGB (Dwivedi et al., 2022). we follow the commonly used parameter budgets of 500K parameters.
For the node classification datasets from Platonov et al. (2022) and Leskovec & Krevl (2014), we strictly follow the experimental setup from the state-of-the- method Polynormer (Deng al., 2024). We only replace the global attention blocks from Polynormer with NeuralWalker's 's walk encoder blocks and use the same hyperparameters selected by Polynormer (Deng et al., 2024).
We use the Adam W optimizer throughout experiments with the default beta parameters in Pytorch. We use a linear warm-up increase of the learning rate at the beginning of the training followed by its cosine decay as in Rampášck et al. (2022). The test sampling rate is always set to 1.0 if not specified. The detailed hyperparameters used Walker as well as the model sizes and runtime on different datasets provided in Table 10, 11, and 12.
24

---

Published as a conference paper at ICLR 2025
Table 11: Hyperparameters for the 3 datasets from OGB (Hu al., 2020a).
HYPERPARAMETER
OGBC-MOLPCBA
OGBG-PPA
OGBG-CODE2
BLOCKS
HIDDEN
500
384
256
SEQUENCE LAYER
CONV.
CONY.
CONY.
LOCAL MESSAGE PASSING
GATEDGCN
GIN
GIN
GLOBAL MESSAGE PASSING
PERFORMER
TRANS.
DROPOUT
0.4
GRAPH POOLING
MEAN
MEAN
MEAN
RW SAMPLING RATE
0.5
0.5
0.5
RW LENGTH
25
200
100
RW POSITION ENCODING WINDOW SIZE
32
LEARNING RATE
0.002
0.002
0.0003
EPOCHS
100
200
30
WARMUP EPOCHS
WEIGHT
13.0M
3.1M
12.5M
TRAINING TIME (EPOCH/TOTAL)
226s/6.3H
671s/37H
1597s/13.3H
Table 12: Hyperparameters for node classification datasets from Platonov et al. (2022) and Leskovec Krevl (2014). The other hyperparameters strictly follow Polynormer (Deng et al., 2024).
HYPERPARAMITER
ROMAN-EMPIRE
AMAZON-RATINGS
TOLOKERS
QUESTIONS
SEQUINCE LAYIR
MAMBA
CoNV.
DROPOUT
0.3
0.2
0.3
0.1
0.2
0.1
RW
0.01
0.01
0.01
0.01
0.001
RW LENGTH
1000
1000
1000
1000
1000
500
RW POSITION ENCODING WINDOW SIZE
$
$
8
8
8
LEARNING RATE
0.0005
0.0005
0,0005
0.001
SE-5
0.0005
(EPOCH/TOTAL)
0.505/0.35H
0.67s/0.3
6.44s/4.50
D.4 ADDITIONAL RESULTS FOR ABLATION STUDIES
We provide more detailed results for ablation studies in Table 13, A time comparison of CNN and Mamba used the sequence layers in NeuralWalker is presented in Table 14. We also report the GPU memory usage for Neural Walker on the ZINC, CIFARIO, and PascalVOC-SP datasets in Figure 5, analyzing the impact of varying the random walk sampling rate and length hyperparameters. All the other hyperparameters are fixed to the values specified in Table and 10. The figure demonstrates that Neural Walker scales strictly linearly with both the sampling rate and length, highlighting the model's 's potential for application to very large datasets.
Table 13:
Ablation studies of Walker on different choices of the sequence layer, local and global message passing. Validation performances with mean + std of 4 runs are reported. We compare different choices of sequence layers (Mamba, S4, CNN, and Transformer), local (with or without GIN) and global (virtual node (VN), Transformer, none (w/o)) message passing layers. Note that the row highlighted with the light gray color corresponds to the choices CRaWL (Tönshoff et al., 2023b).
SEQUENCE LAYER
LOCAL MP
GLOBAL MP
ZINC
CIFARI0
PASCAINOC-SP
MAMBA
GIN
VN
0.078 2 0,004
78.610 0.524
0.4672 1 0.0077
MAMBA
GIN
TRANS.
0.083
80.755
0.467
0.4877 0.0042
MAMRA
GIN
W/O
0.085 0.003
80.885 + 0.769
0.461 0.0036
MAMBA
VN
0.086 0.008
0.552 78.025
0.4570 0,0064
MAMBA
W/O
W/O
0.090 2 0.002
79.035
0.850
0.4525
0.0044
MAMBA (W/O
GIN
VN
0.089 0.004
74.910 0.547
0.4522
0.0063
S4
0.082 0.004
77.970
0.506
0.4559
0.0064
CNN
GIN
VN
0.088 0.08820.000 0.004
80.240 + 0.767
0,4652 : 0.0058
TRANS.
0.408
0.4790 0.0081
CNN
GIN
W/O
0.102 0.003
80.020 + 0.279
0.4155 0.0050
TRANS.
GIN
VN
0.084 2 0.003
72,850 0.373
0 0.0072
25

---

Published as a conference paper at ICLR 2025
Table 14: Training time (Epoch/Total) comparison when using CNN and Mamba as the sequence layer in NeuralWalker. The time values are measured on single A100 GPU.
SEQUENCE LAYER
ZINC
CIFARIO
PASCALVOC-SP
MAMBA
168/8.4H
95S/2.6H 295/0.8H
2185/12H 71s/3.9H
CNN
8.9s/5H
ZINC
CIFARIO
PsscalVOC-SP
GPU Memory usage (Gb)
0.25
0.50
0.75
1.00
0.25
0.60
0.76
1.00
0.25
0.50
0.75
1.00
Sampling ralle ?
Sampling
Sampling rali
10
50
100
Random walk length
Random walk length
Random walk length
Figure 5: GPU memory usage of Walker for training one iteration on the ZINC, CIFARIO, and PascalVOC-SP datasets. The hyperparameters are fixed the values specified Table and 10 when varying the random walk sampling rate and length. Memory consumption is measured using Pytorch.profile. library.
D.5 DRTAILED RESULTS AND ROBUSTNESS TO SAMPLING VARIABILITY
Since NeuralWalker'ss output depends on the sampled random walks, we evaluate its robustness to sampling variability. Following Tönshoff et al. (2023b), we measure the local standard deviation (local std) by computing the standard deviation of performance metrics obtained with five independent sets of random walks (details in Tönshoff et (2023b)). The complete results for all datasets are presented in Table 15. Notably, by comparing the local std to the cross-model std obtained from training different models with varying random seeds, we consistently observe a smaller local std. This finding suggests that Neural 's predictions are robust to the randomness inherent in the random walk sampling process.
D.6 ADDITIONAL RESULTS ON TRAINING AND INFERENCE TIME
In order to provide comprehensive insight into the scalability of our model across all datasets, report in Table 16 statistics for the number and length of random walks selected for each dataset, along with the corresponding training and inference times. The results demonstrate that random walk sampling is highly efficient, and typically faster than model training inference. Additionally, our model exhibits reasonable scalability with increasing graph size.
26

---

Published as a conference paper at ICLR 2025
Table 13: Detailed results for all the datasets. Note that different metrics are used to measure the performance on the datasets. For each experiment, we provide the cross-model std using different random seeds and the local std using different sets of random walks.
VALIDATION CROSS-MODIE
DATASET
METRIC
SCORE
CROSS
LOCAL
SCORE
ZINC
0.0646
0.0007
0.0005
0.0038
MNIST
ACC
0,9876
0.0008
0,0003
0.9902
0,0006
CIFARIO
ACC
0.8003
0.0019
0,0009
0.8125
0.0053
PATTERN
ACC
0.8698
0.0001
0.0001
0.8689
0.0003
CLUSTER
ACC
0.7819
0.0019
0.0004
0.7827
0.0007
PASCALVOC-SP
FI
0,4912
0.0042
0.0019
0.5053
0.0084
COCO-SP
FI
0.4398
0.0033
0.0011
0.4446
0.0030
PEPTIDES-FUNC
AP
0.7096
0.0078
0.0014
0.7145
0.0033
PEPTIDES-STRUCT
AP
0.2463
0.0005
0.0004
0.2389
0.0021
PCQM-CONTACT
0.4707
0.0007
0.0002
OGBG-MOLPCBA
AP
0.3086
0.0031
0.0010
0.3160
0.0032
OGBG-PPA
ACC
0.7888
0.0059
0.0004
0.7460
0.1957
0.0025
0.0005
0.1796
0.0031
ROMAN-EMPIRE
ACC
0,9292
0.0036
0.0005
0.9310
0.0032
AMAZON-RATINGS
ACC
0.5458
0.0036
0.0009
0.5491
0.0049
MINESWEEPER
ROC AUC
0.9782
0.0040
0.0003
0.9794
0.0047
TOLOKERS
ROC AUC
0.8556
0.0075
0.0010
0.8540
0.0096
QUESTIONS
ROC AUC
0.7852
0,0113
0.0009
0.7902
0.0086
POKEC
ACC
0.8646
0.0009
0.0001
0.8644
0,0003
Training Tine
Inference Time
Dataset
# Nodes (n)
RWs (197)
RW length (?)
7
Model
RW Sampling
Model
RW Sampling
ZINC
23.2
0.001011
1.3e-05
0.000319
0.000132
OGBG-MOLPCBA
26.0
13.0
25
12.5
0.000373
4c-06
0.000222
1.1c-05
PCQM-Contact
30.1
15.05
75
37.5
0.000725
4e-06
0.001792
3c-05
MNIST
70.6
35.3
50
25.0
0.001063
1.4e-05
0.000497
3.2o-05
CLUSTER
117.2
58.6
200
100.0
0.014039
0.000133
0,006935
0.001245
CIFAR10
117.6
58.8
50
25.0
0.001273
1c-05
0.000631
6.2c-05
PATTERN
118.9
$9.45
100
50.0
0.002797
7.9c-05
0.001502
0.00025
OGBG CODE2
125.2
62.6
100
50.0
0.002597
5.7c
0.001586
0.002108
Peptides. Func
150.9
75.45
100
50.0
0.00609
6.4e-05
0.002655
0.000149
Peptides Struct
150.9
75,45
100
50.0
0.006162
0.000104
0.002695
0.00028
OGBG-PPA
243.4
121.7
200
100.0
0.003708
0.000615
0.002411
0.004862
COCO SP
476.9
119.225
100
25.0
0.008137
05
0.007638
0.00031
PASCALVOC-SP
479.4
239.7
100
50.0
0.015187
0.002744
0.007574
0.000936
MINESWEEPER
10000.0
100.0
1000
10.0
0.15
0.024003
0.016
D.160348
TOLOKERS
11758.0
117.58
1000
10.0
0.31
0.33813
0.012
2.342794
ROMAN EMPIRE
22662.0
226.62
1000)
10.0
0.31
0.037853
0.011
0.316381
AMAZON- AMAZON-RATINGS RATINUS
24492.0
244.92
1000
10.0
0.14
0.040961
0.016
0,301582
QUESTIONS
48921.0
489.21
1000
0.26
0,400535
0.01
1.841745
POKEC
1632803.0
1632.803
5000
2.1
3.177021
102.925
9.621128
Table 16: Statistics for the number and length of random walks selected for each dataset, along with the corresponding training and inference times. Training and inference times represent the wall-clock time per graph, measured
single H100 GPU equipped with 8 AMD EPYC 9554 CPUs. For the POKEC dataset, due to its large graph size, inference times were computed entirely on CPUs. Note that training per graph can sometimes appear faster because we typically use a larger sampling rate during inference to achieve better performance. Specifically. for Benchmarking GNNs, LRGB, and OGBG datasets, the sampling rate is fixed at 1.0 during inference while is usually smaller than 1.0 during training as given in Table 9, 10, 11. For node classification datasets, the inference sampling rate is 5 or 10 times higher than the rate used during training, as shown in Table 12.
27


Reviews:
[{"review_id": "oNigYQC1Iu", "reviewer": "Reviewer_p6gD", "summary": "This paper addresses the challenge of capturing long-range dependencies in GNNs by combining random walks with local message passing. The authors utilize State Space Models (SSMs) to model random walk sequence. Theoretical analysis highlights the expressiveness of the proposed approach, and experimental results show that it outperforms the selected baselines.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The issue of long-range dependencies in GNNs is an important and valuable area of exploration.\n2. The proposed method is versatile and can be integrated with various models.\n3. The authors offer theoretical insights, including the expressiveness of the proposed method.", "weaknesses": "1. The novelty of this method is limited, as random walks, combining local and global information, and SSMs are established techniques. For example, Graph-Mamba [1] also uses random walks and Mamba on GNNs, and graph transformers typically combine global and local data.\n\n2. The datasets selected for node classification are mainly heterophilic. Including commonly used datasets like OGB would provide a more comprehensive evaluation.\n\n3. The source of the performance gains is unclear—whether they stem from pretraining, positional encodings, or SSMs. An ablation study would help clarify each component's impact.\n\n[1] Behrouz, Ali, and Farnoosh Hashemi. \"Graph mamba: Towards learning on graphs with state space models.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.", "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": "4y9lACCvIQ", "reviewer": "Reviewer_J8Bn", "summary": "In order to learn long range dependencies, this paper presents NeuralWalker architecture that samples random walks from the graph, treats them as sequences, encode these sequences using a sequence layer and finally integrates this module with local and global message passing to better learn graph structure. It provides theoretical results to show the expressive power of NeuralWalker.", "questions": "- Why Polynormer’s results are missing in LRGB and GNN benchmark experiments?\n- What are the main differences between NeuralWalker with the tokenization module in graph-mamba (Behrouz et al., 2024), where the number of random walk samples ($M$) in their framework is 1?\n- Although random walks can provide a natural sequence to learn long-range dependencies, they also can be sensitive to noisy connections. How does NeuralWalker perform in these cases?\n- In the theoretical results, don’t you need to assume that your sequence model is a universal approximator? Without this assumption how one can compare the expressive power of NeuralWalker after encoding walks with the 1-WL test?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is overall well-written.   \n- Incorporating random-walks in graph learning is an important direction mainly due to its efficiency and ability to learn the long-range dependencies.\n- Theoretical results have provided detailed discussions about the expressive power of NeuralWalker and motivates its design.\n- The training details for reproducibility are reported, which can help future studies to better understand the weaknesses/strengths of NeuralWalker.", "weaknesses": "- My main concern is that there are several claims in the paper that have remained unsupported/unclear:\n  - The authors claim that ``our approach achieves significant performance improvements on 19 graph and node benchmark datasets``. Based on the reported results NeuralWalker underperforms baselines and several missed state-of-the-art methods. Even looking at the current baselines NeuralWalker does not provide performance improvements in all the 19 datasets! \n  -  The authors claim that ``CNNs present a compelling alternative for large datasets due to their faster computation (typically 2-3x faster than Mamba on A100)``. Where are the results for this? How is this trade-off between efficiency and performance?\n  - The authors several times mentioned efficiency as the motivation of their method. I couldn’t find any comparison with baselines with respect to memory usage and speed. While training time is reported in Tables 9-12, the training time for baselines and also the memory usage of NeuralWalker and baselines are unclear. \n  - Without local/global encoding the performance of NeuralWalker significantly drops. How the results can support the importance of using random walks for long-range dependencies?\n  - Since the authors have claimed performance improvement over existing methods, it is important to choose the right baselines. For example, although the results of POLYNORMER (Deng et al., ICLR 2024) are reported in Table 5, their results are missing in other experiments. Also, the results for several recent efficient methods are missing: GSSC (Huang et al., 2024), GOAT (Kong et al., ICML 2023), and GRED (Ding et al., ICML 2024). It would be great if the authors could use consistent baselines across different experiments so the performance gain becomes clear. Also, I believe a comparison with random walk-based GNNs like GraphSAGE is required. \n- There are several missing related articles. I suggest discussing these methods to further clarify the novelty of NeuralWalker. For example, there are several recent methods that also have used sequence layers for graphs GSSC (Huang et al., 2024), and GRED (Ding et al., ICML 2024). \n- This paper has overlooked a version of graph-mamba (Behrouz et al., KDD 2024), which also uses random walks to learn long-range dependencies. I found NeuralWalker very similar to this method when the number of sampled walks per node is 1. It would be great if the authors clarify and discuss the differences. \n- Based on the results in Table 6, without local and global message passing the performance of the proposed method drops significantly. This raises concerns about the significance of the proposed method as it seems the main reason for the competitive performance of NeuralWalker is the use of local/global message-passing modules.   \n  \nPlease also see the questions.", "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": "FLk763uQqk", "reviewer": "Reviewer_CxEX", "summary": "The paper presents NeuralWalker, which combines random walks and message-passing mechanisms to capture both local and long-range dependencies in graphs. The model processes graphs by treating random walks as sequences, thereby leveraging sequence models to handle long-range interactions.", "questions": "1.\tIs the motivation for using the random walk sampler driven by memory constraints? Additionally, in Figure 3, why does the ZINC dataset display a different trend compared to the other two datasets?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tExisting graph transformers works typically incorporate random walks as positional encodings; directly integrating them into token design is an interesting approach.\n\n2.\tThe theoretical analysis provided is thorough and comprehensive.\n\n3.\tExtensive experiments are conducted, with detailed results presented both in the main text and the appendix.", "weaknesses": "1.\tThe primary concern is the unclear motivation. Why do the authors choose to integrate random walks into token design, and how could this approach benefit over graph transformers, which can already use positional encodings to capture structural information? A preliminary study exploring this choice would be helpful.\n\n2.\tBuilding on this, the purpose of incorporating multiple techniques, such as the walk aggregator, also lacks clarity. For instance, why use average pooling in the walk aggregator? Do different random walks carry the same importance?\n\n3.\tAnother concern is the lack of technical innovation. It’s difficult to discern a clear distinction between NeuralWalker and graph transformers, as NeuralWalker appears to follow general design principles of graph transformers, treating the graph as a sequence and representing tokens as the combination of nodes, edges, and positional encodings, albeit based on random walks.\n\n4.\tCould the authors clarify why SSE performs better than transformers? Since SSE and Mamba are designed based on RNNs, have bidirectional RNNs been tried as a sequence model?\n\n5.\tI also question the motivation for including global message passing although the ablation study shows it could help. When the length of random walks is long, they should already capture global information inherently. Besides, the authors directly borrow existing graph transformer methods for this, could you provide an ablation study on the choice of graph transformer in this part?\n\n6.\tFollowing this, an empirical efficiency comparison—specifically running time and memory usage—against current graph transformer baselines like Polynormer would be beneficial.\n\n7.\tAnother major issue is the absence of several recent baselines. In traditional GNNs, several works, like LazyGNN[1], aim to capture long-range dependencies. There are also state-of-the-art graph transformers, such as VCR-Graphormer[2] and GOAT[3], and crucially, since the authors use SSE as a sequence model, Graph Mamba[4] should be included as a baseline.\n\n8.\tThe datasets are not large enough, especially for node classification tasks. Commonly used datasets like the medium-sized ogbn-products or the large-sized ogbn-papers100m are not included. The current datasets are not common and cannot be considered as large-scale.\n\n[1] LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation\n\n[2] VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections\n\n[3] GOAT: A Global Transformer on Large-scale Graphs\n\n[4] Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces", "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": "zcFWHLJZWV", "reviewer": "Reviewer_ehiS", "summary": "The paper proposes the NeuralWalker architecture. This GNN processes sequential graph features obtained from random walks with sequence models such as SSMs. This process is interleaved with message passing modules. This construction aims to address the main weaknesses of prior random walk-based methods by encouraging longer-range information flow and utilizing breadth-first structural information.\n\nThe paper provides a theoretical analysis showing formally that NeuralWalker is more expressive than 1-WL and CNN-based random walk models like CRaWl. An experimental analysis further demonstrates strong overall performance on a range of standard benchmarks. The option of pertaining on the task of predicting the random walk features is explored. The experiments further show that random-walk-based methods like NeuralWalker can scale to large graphs with over 1M vertices.", "questions": "* The result that SSMs outperform Transformers in the context of NeuralWalker is very interesting. Are there some theoretical insights as to why self-attention is not well-aligned with processing walk embeddings?\n\n* I would also appreciate a comment on the point raised in \"Weaknesses\".", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* NeuralWalker successfully addresses several weaknesses in prior random-walk-based approaches by using SSMs in a novel context.\n* The provided experiments and ablations are rather comprehensive.\n* Pretraining a sequence model to predict the structural encodings of random walks is a novel idea, and the results presented here seem promising.", "weaknesses": "A weakness of this paper is a lack of discussion of \"old\" RNN architectures like LSTMs. While these have become less popular, it would be helpful to highlight why more modern long-sequence models like SSMs are preferable in the context of NeuralWalker. In fact, when compared to both Transformers and SSMs classical RNNs have been shown to have superior expressivity in terms of circuit complexity when the input sequence length is unbounded [1]. In a setting where the walk length is unbounded, an RNN-based NeuralWalker may therefore be more expressive than an SSM-based model. Exploring such a scenario in-depth is out of scope for the work presented here, but I do think a brief discussion of RNNs as an alternative sequence model choice is justified.\n\n[1] Merrill, William, Jackson Petty, and Ashish Sabharwal. \"The Illusion of State in State-Space Models.\" Forty-first International Conference on Machine Learning.", "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 (Poster)