Random Search Neural Networks for Efficient and Expressive Graph Learning
Authors: Michael Ito
Danai Koutra
Jenna Wiens
Venue: NeurIPS 2025 poster ()
Keywords: graph neural networks
random walks
long-range dependencies
molecule graph
Primary area: deep_learning
TL;DR: We introduce random search neural networks (RSNNs), a more efficient and expressive alternative to random walk neural networks (RWNNs) that achieves strong performance on sparse graphs with significantly fewer samples.

Abstract: Random walk neural networks (RWNNs) have emerged as a promising approach for graph representation learning, leveraging recent advances in sequence models to process random walks. However, under realistic sampling constraints, RWNNs often fail to capture global structure even in small graphs due to incomplete node and edge coverage, limiting their expressivity. To address this, we propose \textit{random search neural networks} (RSNNs), which operate on random searches, each of which guarantees full node coverage. Theoretically, we demonstrate that in sparse graphs, only $O(\log |V|)$ searches are needed to achieve full edge coverage, substantially reducing sampling complexity compared to the $O(|V|)$ walks required by RWNNs (assuming walk lengths scale with graph size). Furthermore, when paired with universal sequence models, RSNNs are universal approximators. We lastly show RSNNs are probabilistically invariant to graph isomorphisms, ensuring their expectation is an isomorphism-invariant graph function. Empirically, RSNNs consistently outperform RWNNs on molecular and protein benchmarks, achieving comparable or superior performance with up to 16$\times$ fewer sampled sequences. Our work bridges theoretical and practical advances in random walk based approaches, offering an efficient and expressive framework for learning on sparse graphs.

Random Search Neural Networks for Efficient and Expressive Graph Learning
Michael Ito University of Michigan mbito0umic ch.mchhh. edu
Danai Koutra University of Michigan dkoutradumi ch. edu
Jenna Wiens University of Michigan wiensj riensj@uml @umi ch. edu
Abstract
Random walk neural networks (RWNNs) have emerged as promising approach for graph representation learning, leveraging recent advances in sequence models to process random walks. However, under realistic sampling constraints, RWNNs often fail to capture global structure even in small graphs due incomplete node and edge coverage, limiting their expressivity. To address this, we propose random search neural networks (RSNNs), which operate on random searches, each of which guarantees full node coverage. Theoretically, we demonstrate that sparse graphs, only Oloo [V]) searches needed to achieve full edge coverage, substantially reducing sampling complexity compared to the O(VV) walks required by RWNNs (assuming walk lengths scale with graph size). Furthermore, when paired with universal sequence models, RSNNs are universal approximators, We lastly show RSNNs probabilistically invariant graph isomorphisms, ensuring their expectation is an isomorphism- manorphismmiivariin invariant graph function. Empirically, RSNNs consistently outperform RWNNs on molecular and protein benchmarks, achieving comparable or superior performance with up to 16x fewer sampled sequences. Our work bridges theoretical and practical advances random walk based approaches, offering an efficient and expressive framework for learning on sparse graphs.
Introduction
Early work on random walk-based graph representations focused on using skip-gram objectives to learn node embeddings from sampled walks 2 Building on these ideas and leveraging recent advances in sequence modeling, random walk neural networks (RWNNs) have emerged as powerful paradigm for modern graph learning 8 overcoming the limitations of message-pasee passing neural networks (MPNNs) [ and graph transformers [2H14] by representing graphs as collections of random walks processed by sequence models. This advancement aligns with the broader research goal of identifying effective and expressive methods for graph representation learning [15 However, despite their success, RWNNs encounter critical expressivity challenges under realistic conditions due to incomplete node and edge coverage, limiting their capacity to capture structure even in small graphs (Figure DT. In our analysis, we establish that, under partial coverage, RWNNs are strictly less expressive than traditional MPNNs, highlighting the importance of complete coverage and bridging the theoretical expressivity of the two paradigms.
To illustrate the limitations of RWNNs, consider the graph composed of connected six-cycles and side chains shown Figure Capturing the full structure of this graph requires traversing every node and edge. However, since the node and edge cover times for random walk can scale as O[[]] [[[|[ [EE) (18] RWNNs require either prohibitively long walks or an impractically large number of samples to guarantee complete coverage. Under realistic sampling constraints where the walk's number of steps is significantly less than ([V]) random walks obtain only partial graph reconstruction: as shown in Figure a), subgraphs induced by short random walks can miss critical structural components,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(a) Random Walk Extraction
Original Graph
Induced subgraph from random walk 1
Induced subgrach from random walk 2
Walks obttin incomplete reconstruction under realistic sampling steps <c (V]
(b) Random Search Extraction
Induced spanning tree from random search
Induced spanning tree from random search
Search obtains complete reconstruction with log sampling searches logl[V[)
Legend
Traversed Node
Missed Node
Traversed Edge
Missed Edge
Figure I: RWNN and RSNN coverage differences. Random walks miss critical structure under realistic sampling constraints, wheras each individual search only misses single edges cycles, enabling complete reconstruction across logarithmic sampling in [V] sparse graphs.
such as the side chains connected to the six-cycles. This incomplete coverage significantly hinders RWNN expressivity. Current methods attempt to address this limitation through non-backtracking walks [ 6 and minimum-degres local rules (MDLR) 7 reducing node and edge cover time to O(VI)). Nonetheless, these approaches retain quadratic complexity with respect to graph size, making comprehensive coverage costly and impractical for even small and medium graphs.
To overcome these challenges in small and medium sized graphs, introduce random search neural networks (RSNNs), which represent graphs as collections of random searches. Critical to our analysis the insight that subgraphs induced by searches spanning trees opposed to arbitrary subgraphs induced by random walks. Each spanning tree inherently ensures full node coverage, reducing the task to achieving edge coverage across the union of induced trees. Leveraging this insight, our analysis demonstrates that RSNNs require only a logarithmic number of searches for complete edge coverage, specifically in sparse graphs where such searches improvement over the linear number of walks required by RWNNS, assuming walk lengths scale with graph size. As shown in Figure [b), the union of just few spanning trees enables complete reconstruction of the graph, including nodes and edges missed by walk-induced subgraphs. When equipped with maximally expressive sequence models, RSNNS achieve universal approximation efficiently. Furthermore, we show that RSNNs are probabilistically invariant to graph isomorphisms, ensuring their expectation an wwwpnnoohhsm-iivviian predictor. Empirically, we focus on sparse molecular and protein graph classification datasets, domains in which RWNNs have shown significant improvement over existing GNNs. Across both domains, we demonstrate that RSNNs consistently outperform existing RWNN approaches. In summary, we make the following contributions:
computationally feasible. This is substantial
.
Characterizing RWNN Expressive Limitations. Our analysis characterizes the expressive power of RWNNs, bridging the expressivity of RWNNs and MPNNs. We demonstrate that RWNNs under partial node and edge coverage are strictly less expressive than MPNNs, motivating the design of sampling strategies that guarantee full coverage.
New Model: Random Search Neural Networks. We propose random search neural networks (RSNNs), new approach that operates random searches, whose induced subgraphs are spanning trees, substantially reducing the sample size required for complete node and edge coverage in sparse graphs.
Efficient Coverage, Universal Approximation, & Isomorphism Invariance. We demon- strate that RSNNs can achieve universal approximation efficiently with logarithmic sampling in sparse graphs. RSNNs are also probabilistically invariant graph isomorphims, ensuring their expectation is an isomorphism-invant invariant function on graphs.
Extensive Empirical Analysis. Focusing on sparse molecular and protein graph bench- marks, demonstrate that RSNNs consistently outperform existing RWNNs.

---

2 Background and Preliminaries
We establish notation for graphs and random walks and next review MPNNs and RWNNs, the primary class of models under investigation. Importantly, we later bridge the expressivity of MPNNs and RWNNs. We lastly review random walk cover times, highlighting how RWNNs require prohibitively long walks or impractically large numbers of walks to guarantee full graph coverage.
2.1 Notation and Random Walks on Graphs
We define a graph G (V, A, X), where V is the set of nodes, E {0, V matrix representing the set of edges E, and X R is the node feature matrix. For each node i V, we denote its feature vector as X; and its set of immediate (one-hop) neighbors as (t). We define the augmented neighborhood (i), obtained by adding a self-loop to node i.
is the adjacency
random walk of length e on G produces a sequence of nodes W = (Wo...... we) by first sampling an initial node E V according to uniform distribution Po. and then iteratively transitioning to subsequent nodes by sampling neighbors according to a given random walk algorithm. We let W,(G) denote the set of all possible random walks of length & on G, and let P(W(G), Po) represent a probability distribution over these walks. Lastly, we define Pm (W(G) = {Wi,... Wm) as realization of a set of m independently sampled random walks from P(W(G)), Po).
2.2 Message-passing Neural Networks and GNN Expressivity
Standard GNNs adopt a pesssage-passing approach, where each layer iteratively updates a node's representation by aggregating the features of its neighbors [19]. Formally, the initial message- layer can defined as the following propagation rule at the node level for E V.
SMPNN (G); = Sags (1x, | (i))),
where Sage is a permutation-invariant function. Because of this aggregation step, MPNNs in- fundamental expressivity limitations and cannot distinguish certain classes of non-isomorphic graphs [0). We compare the expressivity of GNNs by the pairs of graphs they can distinguish (21]
introducing the following notation. For two GNNs fi and f2, write
f
YG, fi(G) (HH
fe(G) (H))..
Thus, any pair indistinguishable by fi is also indistinguishable by f2, so fi is at least as expressive as f2- The relation is strict, f2 f1, if f2 fi and there exist graphs G. H with (G) # (HH while f2( = f2( fi and fz are equally expressive, written fi = f2. if f2 3 fi and fi 3 f2- These relations coincide with notions of approximation power. For example, if f2 S1, every target approximable by /2 is approximable by f1. and there exist targets approximable by fi but not f2.
2.3 Random Walk Neural Networks
RWNNs novel class of neural network graphs that leverage sequence models process random walks sampled from the graph. Typically, an RWNN is characterized by four key components: (1) random walk algorithm that generates node sequences, (2) recording function that encodes the walks into structured representations, (3) a reader neural network that processes these representations, and (4) an aggregator that combines the representations or predictions from multiple walks.
For our analysis, we assume the following representative general version of RWNN E 8. Specifically, consider the random walk algorithm as uniform random walks of fixed length f, denoted by P.. (W)G)) := P(W,(G) U())), where U(V) denotes the uniform distribution over V. Given a sampled walk W E Pm (MGG),, we define the recording function femb We(GG) - é as follows:
fembli] == hv( + (hoe(
(I)
where hv V + Rdd is a node embedding function. Here, lipp serves as an optional position encoding that supplies extra structural context for each node in the walk (Appendix B): when such encoding is employed, it further processed by the learnable projection mapping proj Rdd - R Subsequently, assume walk embeddings produced by famb are processed by sequence model,
3

---

denoted by fee R + R Finally, embeddings from the sequence model are aggregated by permutation-imvaria
function. The choice for the function can be simple functions such as taking the mean over random walk representations such as in Wang and Cho 33, Kim et al. 77 or can be more complex as Tönshoff et al. [5], Chen et al. (6), which updates a node's representation as the aggregation of its representations across all walks using the aggregation function fags Rmxxxdd + M
Sagg(ui, = (((P).()(())
E
Σ
WEP(.,WWCI)) W.EW
where (PPm((W()) represents the number of occurrences of node i in the union of walks in Pm (W(G)). The RWNN layer is defined as the composition fEWNN f o fay. while the overall architecture fRWNN is defined as the stacking of RWNN layers. In the node classification setting, the final node representation fuge [i] produced by the last RWNN layer is directly utilized for predictions. In graph classification, an additional global pooling function aggregates these node representations into a single representation for the graph.
2.4 Random Walk Cover Times
RWNN expressivity depends on how much of the graph its random walks visit (Section 3 Here, we review results random walk node cover times, (G)) the expected number of steps walk takes to visit all nodes. For a connected graph = E). the cover time of a general uniform random walk satisfies Cv-(G) O(IVILE) 22]; in particular, for sparse graphs ((E) O(IVI) this gives Cv( = P2) Minimum-degree local rule (MDLR) walks further achieve (v) -
([()))((V13)) O(iVI²)
all graphs. which is optimal among first-order walks 7 23). Non-backtracking walks can also empirically reduce cover times on graphs [5. Even with these improvements, guaranteeing full node and edge coverage by random walks can require prohibitively long walks or impractically large numbers of walks. We therefore replace walks entirely with searches (Section 4 significantly improving the number of samples required for full coverage in comparison to random walks.
3 Expressive Power of Random Walk Neural Networks
In this section, we characterize the expressive power of RWNNs. Our main result establishes that without additional positional or structural encodings, RWNNs with access to the complete multiset of random walks whose lengths scale up to the cover time are exactly as expressive as MPNNs. practice, however, such assumptions are unrealistic: guarantecing full node and edge coverage requires walk lengths on the order of the cover time, rendering full coverage computationally infeasible. We then show that in the partial-coveral MPNNs. This limitation motivates our random search neural network (RSNN), which achieves full coverage and thus maximal expressivity at significantly lower sampling cost.
regime, RWNNs are strictly less expressive than
3.1 The Role of Coverage: RWNNs MPNNS
We first analyze the ideal setting in which the RWNN has access to complete walk sets up to the cover time. In this regime, RWNN expressive power matches that of MPNNs.
Theorem 3.1 (RWNN-MPNN Equivalence Under Full Coverage (FC)). Let G be graph. Let JRWNN denote an RWNN with injective feeq and fazg, with no additional positional encodings, applied the complete multiset of walks Wee(G) with lengths up to & Cz(G), the edge cover time of G. Let fMPNN be an MPNN with injective fagg. Then, for all graphs G, H.
fMPNN (G) = -HMPNN(H) +
fRONN (G) -FC (H).
Hence, JRWNN ~ fMPNN (i.e., FFC JRWNN and fMPNN are equal in expressive power).
4FC
Although Theorem 3.1 shows that full-coverage RWNNs and MPNNs are equal in expressivity, RWNNs under full coverage can more effective empirically. RWNNs leverage expressive sequence models capable of capturing long-range dependencies when given full graph structure in complete sequences. MPNNs instead rely on iterative neighborhood aggregation and are limited in depth by oversmoothing [24] and oversquashing (25). which in practice reduce their expressivity and

---

capabilities to capture long- range signals. This contrasts our theoretical setup where we assume MPNNs have unlimited depth, allowing them to match full-coverage RWNN expressivity.
Constructing complete walk sets with lengths up to the cover time, however, is typically computation- ally infeasible. RWNNS thus fall short of MPNNs under realistic budgets despite their inherent advantages. Indeed, as an immediate consequence of Theorem 3.1] when RWNNs operate under partial coverage, their expressive power is strictly less than that of MPNNs.
Corollary 3.2 (RWNNs Under Partial Coverage (PC)). Let JOWNN denote an RWNN of the same architectural class as in Theorem 3.7 but applied to a multiset of rundom walks that atlains only partial nodeledge coverage of the input graph. Then. for all graphs G, H,
fMPNN( (G) fAPNN (H) =
fiw (G) (RWNN((H)
and there exist non-isomorphic graphs G # H such that
JMPNN(G) * (H) while PPC JRWNN(G) PCC
(H).
Hence, JPC RWNNN R SMPPN (partial-coeeaage RWNNs are strictly less expressive than MPNNs).
Corollary 3.2 reveals a fundamental limitation of RWNNs: under partial coverage, their expressive power falls below that of classical message passing. Thus, to attain maximal theoretical expressivity. is essential to design sampling strategies that efficiently guarantee complete coverage. In order to realize the advantages of RWNNs while obtaining maximal expressivity, we introduce RSNNs (Section 4p. which replace walks with searches to guarantee full node coverage by construction and achieve full edge coverage with a small number of searches on sparse graphs.
Insights of the analysis. In proving Theorem 3.1 we introduce walk-based color refinement, Walk Weisfeiler-Lehman (WWL.; Definition A.3). which updates each node using the multiset of walks that visit it. We demonstrate that WWL upper bounds RWNN expressivity (Lemma A.5). Next, we establish that WWL operates on the same object as classical WT: unfolding trees (Definition (A. We lastly leverage this insight to establish that WWL and WL have equal distinguishing power (Theorem A.9). In essence, this construction aligns the Weisfeiler-Lehman hierarchy with RWNNs, unifying the expressive power of two seemingly distinct model classes: RWNNs, which process random walks with sequence models, and MPNNs. which process multisets of node neighborhoods with graph convolution. Formal definitions and details are in Appendix A
4 Random Search Neural Networks (RSNNs)
Motivated by our analysis of RWNNs, we propose a new sampling strategy that efficiently achieves the necessary conditions for maximal expressivity: full node and edge coverage. Since random walks require either prohibitively long walks or an impractically large number of walks to guarantee full coverage, we introduce random search neural networks (RSNNs), which represent graphs as collections of random searches. Notably, a single search guarantees full node coverage, and under the sparse graph assumption, only O(log[VV) (V)) searches are needed to capture all edges. This significantly reduces the sampling complexity compared to the O(VV) requirement for traditional RWNNs, assuming walk lengths scale on the order of ((VV). When paired with maximally expressive sequence model, RSNNs emerge as universal approximators on graphs. Moreover, we provably show RSNNs are probabilisticalyy invariant graph isomorphisss. Hence, the predictor obtained by averaging over searches is an isomorphism-invann invariiat graph function. While the computational cost of full search can be significantly larger than short random walk, we focus on sparse graphs where search is computationally feasible, addressing the limitations of RWNNs in these classes of graphs.
4.1 Search via Random DFS
RSNNs leverage a random depth-first search (DFS) procedure to obtain sequences from an input graph G. We utilize DFS rather than breadth-firs search to better preserve continuity in the sequence. RSNN obtains a random DFS by sampling a uniform root and independent random neighbors at each vertex; this induces a distribution over DFS sequences we denote Spes RSNN collects m independent searches to form the set Pm. (Spes = (Si..... Sm }. Once these searches are obtained, RSNNs leverage all the advances of RWNNs but with new benefits. We apply the recording function (Equation (T)) to each search, including positional encodings from Tönshoff et al. (5) to distinguish between disconnected nodes and true connections the sequence. Search embeddings are then processed with sequence model and the node aggregation function (Equation 2 (Figure 2).
5

---

Original
Random DFS Extraction
Sequence Model Pracessing
Aggregation
f femb
f Seeq
J Jagg
m
777
Figure 2: Overview of an RSNN layer. Starting from an input graph, m random depth-first searches extracted and encoded via Semb- Additional positional encodings indicate discontinuities in the sequence ge.g..
in search 1). These sequences are processed by a sequence model fsaq and final node representations are aggregated across sequences using fage. We highlight in blue the flow of selected node representation (shown as as it is tracked through each stage of the RSNN layer.
4.2 From Efficient Graph Coverage to Universal Approximation in RSNNs
In this section, we establish the theoretical foundations of RSNNs by demonstrating how our random search strategy efficiently obtains full graph coverage. Central to our analysis is the observation that the subgraphs induced by DFS sequences are spanning trees. Leveraging this insight, we prove the following key lemma showing that for sparse graphs with bounded degree, a logarithmic number of random searches is sufficient to guarantee full node and edge coverage with high probability.
Lemma 4.1 (Logarithmic Sampling Yields Full Edge Coverage). Let G nected graph with |E| < CVV for some constans C and a bounded maximum degree dmax- Let S1. S2..... Sm be independent random searches sampled from G, and let Tı, ..,..., Tm, be their corresponding induced spanning trees. Then, for small < 1, if
E) be a con-
CIVI
In
m
(3)
In
the union of Tí, T2..... ... Tm, contains every edge in E with probability least 1 6.
In contrast to RWNNs, which require m = O(V)) random walks of length f = O(VV)). RSNNs O(log((V)) searches of length & O(VI). With full node and
achieve complete coverage with edge coverage, RSNNs are able to capture all the information necessary to represent any function on graphs. Intuitively, this means that under our sampling strategy. RSNNs universal approximators: they can approximate any graph function arbitrarily well, provided they are paired with a universal sequence model such as transformers LSTMs (26 27).
Theorem 4.2 (Universal Approximation by RSNNs on Sparse Graphs with Bounded Degree). Let - Rdd be any continuous graph- function, function where G is the space of sparse
<> 0 and let graphs with EE| O(VV), maximum degree at most dmax and size at most [V| S Mmaax Assume m satisfies Equation 3 so that full coverage is achieved with probability at least 5. Then, with probability at least 8 there exists an RSNN configuration such that
[|. (G) [[G]] < ffor all G E E
4.3 From Expressivity to Invariance: Isomorphism Invariance of RSNNs
Having established the expressive capabilities of RSNNs, we now turn to invariance. For graphs, the target symmetry is isomorphism invariance: for all G = H. an isomorphism-invariant graph function satisfies f(G = (HH). Graph functions that capture the symmetry enjoy learning and generalization
benefits. Because RSNNs are randomized functions, adopt the notion of probabilistic invariance [7]
28: for all G = H. the random outputs satisfy S(G) - f(H). Intuitively, a randomized graph function is probabilistically invariant to graph isomorphisms its distribution is unchanged under any graph isomorphism. We demonstrate that the randomized DFS procedure used by RSNNs is probabilistically invariant: consequently, the RSNN predictor fRSNN invariant in distribution, and its expectation (G) == E[fnsNN (G))
is an isomorphism camoorphsm-invariant invariant function on graphs.
Theorem 4.3 (Probabilistic Isomorphism-Invarinn Invarianeee of RSNN). randomized search procedure on of visited vertices. We say the procedure is Vivcy) (
graph G produces sequence SG (s) .....

---

probabilistically invariant to graph isomorphisms if all graph isomorphisms n,
(T(( (
(st......s(y(n))) for all G _ H.
The randomized DFS procedure used in RSNNs satisfies the above definition. Hence, RSNNs satisfy probabilistic invariance: for all G = H. [RSNN(G) - JRSNN(H), and the averaged predictor (G) == [B[SSNN is invariant function graphs: 4(G) ) all G = H.
Learning the invariance. In addition being invariant in expectation, we show that RSNNs can learn the optimal invariant predictor throughout training even under limited sampling budgets, where expectation is only approximated (e.g., m = sampled search for each forward pass in the parameter update). At inference, the invariant predictor can then be computed exactly estimated by the Monte Carlo estimator. Our result follows Murphy al. [29] 30). For RSNN parameters W, define the model output graph G' and sampled search set S SDFs(G) as fRSNN(G, S; W).
Corollary 4.4 (SGD converges to the invariant objective). Let E(.,y) y) be differentiable and define
L(W) = E(G.g)~ E Sprs((( [[[nnNN[[G W), 8)]
At each step sample mini-batch B. {(G)
:h (0) ) i.i.d. from DD and, for each i, draw single 5 ~ SDFs(G,,) independently of w. update
W W.
Tte B
Σ V (FRSNN(G.") S W.), v.
Then E 1 V ( S/) : (0) = VW,((W)) i.e., the mini-batch gradient
is an unbiased estimator of V L. Under standard SGD conditions, W, converges almost surely optimizer W of the invariant objective.
Inference. Given a fixed point W* and a new test graph G', the invariant prediction is Es[JRSNN(G', (,,",, S; W*)], which can be exactly computed or approximated with the estimator 1 j= fRSNN ,G', Sy; W*) where Si...., Sm ~ SDFs(G").
iid.
4.4 Runtime Complexity
We compare the sampling costs of RSNNs and RWNNs. In our approach, each random search corresponds DFS traversal. Assuming sparse graph, single DFS has worst-case cost of O(VV), and obtaining m searches requires ( VI) time, efficient and computationally feasible in small to medium-sized graphs. In contrast, RWNNs generate random walks of length E, with total sampling cost O(m)). When < [V], random walk sampling can faster than random search extraction. However,
have shown, short walks fail to capture global structure, leading to reduced expressivity. Thus, while RSNN sampling is more expensive when is small, its increased coverage and performance can justify its cost, especially in graphs where full structure is critical.
5 Experiments & Results
Through empirical evaluation we aim to answer the following research questions, extending our theory by testing RSNNs on datasets with factors not explicitly addressed in the theoretical analysis (c.g., class imbalance, rich node fcatures), and testing RSNNs against models beyond our theory such canonical approaches (c.g., SMILES, Fingerprints) used commonly in molecular analysis.
RQ1 (Discriminative performance): How does RSNN discriminative performance com- pare standard baselines and RWNNs across sparse graph benchmark tasks?
RQ2 (Node and edge coverage): Do RSNNs achieve higher node and edge coverage than RWNNs as the number of sampled searches m increases, and does this increased coverage translate into improved task performance?
RQ3 (Generalization to larger and denser graphs): How do RSNNs perform on larger and denser graphs, where attaining full edge coverage is computationally expensive?
7

---

5.1 Experimental Setup
Datasets. We focus our analysis on molecular and protein benchmarks, domains where RWNNS have demonstrated strong empirical performance and where efficient coverage, long-range depen- dencies, and high expressivity are essential [5] BB]. Importandly RSNNs are not intended as a solution across all domains, but as principled alternative for sparse graphs requiring representa- tions that capture global structure. Specifically, we evaluate on four small-scale molecular graph classification datasets from MoleculeNet [2]: CLINTOX, SIDER, TOX21, and BBBP. These benchmarks span diverse molecular tasks such as toxicity and adverse reaction prediction, with graph sizes ranging from tens to hundreds nodes. We also include four protein graph classification datasets from ProteinShake [3]: EC Subelass, EC Mechanism, SC Class, and SC Family, Protein graphs are significantly larger than molecules, ranging up to thousands of nodes, making it more difficult to capture global structure. To assess scalability, we evaluate on large-scale molecular benchmarks with hundreds of thousands of graphs from Open Graph Benchmark [34]: PCBA-1030, PCBA-1458, and PCBA-4467. Lastly, to test generalization to larger and denser graphs, we evaluate on NeuroGraph-task, a brain graph benchmark, where the task is to predict one of seven mental states (e.g., emotion processing). We provide descriptive statistics for all datasets in Tables | andd] 2
Baselines. First, we compare to standard molecular learning baselines: (1) SMILES, a sequence model applied to canonical SMILES [55; (2) GCN (36 and (3) GIN [53, message-passeeee passsin GNNs; and (4) GT [12], a graph transformer model. In addition, we compare to (5) Fingerprint, multi- layer perceptron trained on hand-crafted chemical descriptors known to be effective in molecular tasks (37). Importantly, SMILES and Fingerprint not applicable in protein graphs. Second, consider four RWNN variants as basclines for comparison: (6) RWNN-base, which employs uniform random walks of length é with mean aggregation over walk representations [4]; (7) RWNN-anon. which augments the base model with a node anonymization strategy from Wang and Cho B]: (8) RWNN-mdIr, which uses minimum-degres
local rule walks from 77, anonymization, and mean aggregation; (9) CRAWL [5). which applies non-bac aa-bacctracking walks with node-level aggregation. We consider three sequence models for fsey: (a) GRU (8), (b) LSTM and (c) transformer (27).
Training and Evaluation. To ensure fair comparisons, all RWNNs and RSNN are configured with the same number of samples m, and RWNN walk lengths are set to e = [V], the number of nodes per graph, so that asymptotic runtimes are equivalent across methods. On molecular benchmarks, we sample a new set of m walks for each forward pass during training. and on protein benchmarks, precompute the set of m walks before training. Following each dataset's protocol, performance is computed AUC or accuracy. We report median (min, max) performance over five random splits (60/20/20), which is more robust than mean and standard deviation for small sample sizes. All models trained machine equipped with 8x NVIDIA GeForce GTX 1080 Ti GPUs; if a model does not converge within 24 hours, we omit it from evaluation. All remaining details are in Appendix
5.2 RQ1& & RQ2: Discriminative Performance and Coverage
First, RSNNs significantly outperform standard baselines across all benchmarks, demonstrating their effectiveness for molecular and protein learning (Table D.. Notably, at m 16. RSNNs match or exceed the performance of Fingerprint models, which do not rely on learned representations and instead use features designed by domain experts. For all RWNNs and RSNN, we present results using GRU, which performs best empirically, and include additional results for LSTMs and transformers in the Appendix [ where we observe similar trends. Compared to existing RWNNs, RSNNs exhibit greater expressivity at low sampling budgets; with a single search (m 1), RSNN significantly outperforms all RWNN variants at the same budget. Moreover, across all molecular benchmarks, RSNNs at m = 1 match or exceed the best-performing RWNNs at m = 16, highlighting their sample efficiency. While performance differences narrow at m = 16 on molecular benchmarks, RSNNs retain a substantial lead on larger protein graphs, underscoring their expressivity in structurally complex settings. On large-scale molecular benchmarks, training both RWNNs and RSNNs with m 1 becomes computationally infeasible, exceeding the 24-hour time budget. At = 1, however, RSNNs maintain strong performance and substantially outperform RWNNs (Table 2). demonstrating RSNNs' robustness under sampling constraints when computation is limited.
'Code can be found at: http:///gthtbbbommmMMLDRRaaaoddt
8

---

Table I: Median (min, max) of performance across test splits on molecular and protein benchmarks. We highlight in blue the best model for each value of m. We use " to indicate when a method is not applicable (Fingerprnt/SMIILE)
when training exceeds 24 hours (GT). RSNNs consistently outperform all RWNN variants at m = 1. While RWNNs approach RSNN performance on molecular benchmarks at m 16, RSNNs outperform RWNNs across all m on protein benchmarks.
Small Scale Molecular Benchmarkss (AUC
Protein Benchmarks (ACC
CLINTOX
SIDKR 1.5K
BRRP
TOX21
SCC
SC FCM
ECMEC
# Graphs
L.5K
2K
8K
10K
10K
13K
ISK
Avg. [V]
26.1
33.6
23.9
18.6
217.5
217.5
304.9
306.4
Arg. [5]
28.0
35.4
26.0
593.8
843,4
846.9
Ciasses
1000
Fingerprint
66.5 74.91
70.4
(556, 74.51
86.2 (83.4 92.5)
79.1 (75.1, 81.0)
SMILES
62.50552.680
61.5
(576,666 66.9
(6155 75
71.3 (66
NA
(full)
57.1
64.3
67 8
GCN
9477
64.2
(1AA 70.39
73.9 (83 31-53
67.5 (811. 71.9
63.4 643
3.
31.2 1)
52.5
GIN
59.7 (2.1.24777
66.5 (643) 09.9)
75.3 (41.) 65:39
66.9 (44A 23.4)
68.0 (57 09.3)
10.4
(33
57.4 (36.1. 99.5
RW -bsse
71.0 79.5)
62.5
74.1
(56 81
71.5 (888 M635
44.5 5 022 15.0
2.2
26.7 17.)
47.3 (06
WWNN-anoon
68.2
64.1
74.8
45
RWNN-mdll
70.7 (6. 76.11
59.8 (57AL 99
76.1
(21.1 50.00
20.8 (66 75.39
4.5 (377
(t6 27
47.2
CRAWL
70.0 (51A 73,0
64.2 (5.1 012)
77.6 (65%) 91.39
71.3 (65A 7533
53.0 (367) 53.1
5.2 (3A.58)))
28.7 (27 20
47.0 (96 47.00
RSNN (ours)
88.1 (855.915)
66.2
(630) 72.4)
$7.5 (80.3,88.9) 89.99
79.8 (71.2 83.4)
62.2 (901)
13.9 (18A, 14.9
36.8 (365, 38.3)
49.8 (41.2, 50.0
RW Nasse
83.6
64.4
84-2
76.3
53.0
337
32.7
48.1
RW OWNN-anon
84.7 0603 W9.5
0530
$210
77.2 (118. 79.3
(1.37 s1t
(52.2)
32.9 (110) 94.00
47.9
913)
112 4
RWNN-mdle
82.9 (7.3 90.4
65.5
(99 72
$1.9 (222 15
76.9 (72 91.2
51 (902 52.5
6.2 (5 7.0
32.4 (306, 31.0
48.2 (4) 41.5
CRAWL
83.0 (46 91.)
65.2
(1.3
84.5 (8277 87.0)
77.6 (25A 81.2
67.0 (66A 62.9)
10.8 05.. 11.4)
38.2 (37 39.9)
50.7 (409,5L)
RSNN (ours)
89.1 (1..999777
67.0
85.0 (90.3.9))
80,3 (71.)
71.7 (705.7338)
15,5
43.9
(4.77.43)
54.8 (51.7.55
RWNS-
85.0 s5.7)
65.2 (18 70.23
84.1 (51
78.3 (11.) 81.39
55.5
(43.699
361)
49.7
52t0
RWNN-anon
86.5 (512) 92.73
67.8 (933 70.7)
83.9 (7422 15.39
78.9 (16.1. 8210
55.0 (SLS, 55.)
9.3 (ks, 1831
36.2 (33 X, 3110
49.3
(45% 5135
RWXN-mdle
83.9
91.)
64.9
( 09.1
(4.9 96.7)
77.6 (25l) 79.0
$4.9 (521, 56.99
9.2 (84, (02)
35.5 (345, 36
49.6 (48.))18))
CRAWL
86.5.833.91
66.
69.9)
86.0 (828,
79. 1 (7677
72.7
14.1
43.7 (43 45.4)
51.7
RSNN (ours)
(8.3330.1,91131
(836,9933)
(77.)
16.0 (541
(46.)
RWNN-hase
87.8 91.11
67.2 (44 71.4)
$6.0 051.2 55.1)
80.0 (15. 81.00
59.0 (5S 012)
10.9 (K8, 11.41
(26. 1939
51.7 (ILA, 8310
RWXN-anom
(3.79117,9181
66.5 (9.3
85.8
(8111.811)
79.2 (75.) 92.2
60.1 (54.3) 61.5)
10,2 (8., 12.4)
39.3 (2.3 40.0)
51.7 (50/,, 53.2)
RW RWNN-mdlee
85.9.31.5.88
65.7 (63.5
85.4
79.1 (71.2
59.5
11.2
39.1
51.3
CRAWI
89.1 91.1
80.9
76.2
RSNN (ours)
03.50 9171
67.1 050 71m
89.4 (S11) 91.7)
82.2 (761) SL.
77.0 (350) 70.31
(1533 2611
50.0 (1U.5 51.00
68.0
We compare how node/edge coverage and per- formance varies with the number of walks or searches for RSNNs and CRAWL, the strongest RWNN baseline (Figure 3} Across all bench- marks, we observe a strong correlation between coverage and model performance. On molecu- lar graphs, RSNNS achieve full node and high edge coverage with single search (m 1), re- sulting in strong initial performance. This aligns with our theoretical analysis: each RSNN search guarantees node coverage by construction, and only few searches needed achieve full edge coverage in sparse graphs. In contrast, CRAWL begins with low node and edge coverage and only reaches RSNN-level performance at m 16, once coverage converges, highlighting RWNN limitations under small sampling budgets. On larger protein graphs, both coverage and performance improve more gradually, but RSNNs retain consistent performance advantage across all m, underscoring the benefit of efficient coverage in larger graphs.
Table 2: Median (min, max) AUC on large scale molec- ular benchmarks. We highlight in blue the best model. RSNNs outperform all RWNNs across all tasks.
Large Scale Molecular Benchmarks (AUC f)
PCBA-1030
PCBA-1458
PCBAA-467
# Gruphs
160K
195K
240K
Avg.
24.3
25.3
Avg. [B]
26.2
27.1
27,2
m.dd
63.5 08.3. 64.3)
76.2 (084,666) 26.)
75.4 (75 160)
CRAWL
64.2 00.5 66.5)
77
(W68
75.6 (752 757)
RSNN 78.8 7933)
87.0 (867,874)
85.2 (833,853)
5.3 RQ3: Generalization to Larger and Denser Graphs
Table 3: Median (min, max) of accuracy on Neuro- Graph benehmark. We highlight in blue the best model. RSNNs outperform CRAWL across m 4, 16.
To assess generalization beyond small and sparse regimes, we evaluate on a NeuroGraph benchmark of brain graphs. These graphs are substantially larger than molecules and denser than proteins, making full edge coverage expen- sive for both walks and searches. We compare RSNN against CRAWL. RSNN outperforms CRAWL at m = 4, 16, indicating that RSNNs can leverage structure even when full coverage is expensive and that their performance advan- tage remains on larger and denser graphs
NeuroCraph-task
# Graphs Avg. [V]
7500
400
Avg. [E]
7029
Max degree
153
16
CRAWL
63.4 (59.4, 64.5)
77.5. (74.A, 78.9
68.3 (30.1, 87.9)
RSNN
58.9 (57.1.615))
80.4 (78.8,
86.5 (76.5, 88.9)

---

10
0.8
Ooverage
Cenerage
Coverage
Cooerage
02
0.50
0.20
0.86
0.60
JOSNN CILANLL
BBRR CRAML
Hah- CRAME
0.06
63
16
16
Ntsber of Seaaars litt
Nambber of WalkerSoarcees (m)
Numbir WalkoSruzzzes om)
(a) BBBP Molecular Graph
(b) Structural Family Protein Graph (c) Enzyme Subelass Protein Graph
Figure 3: Coverage vs. performance across benchmarks. RSNNS achieve higher coverage and performance at low sample sizes, while CRAWL only approaches RSNN coverage and performance at m 16, highlighting strong correlation between coverage and performance.
Discussion and Conclusion
We present the first theoretical analysis of RWNNs under realistic sampling constraints, showing that their expressivity fundamentally limited without full node and edge coverage, even in small graphs. We prove that under partial coverage, RWNNs are strictly less expressive than traditional MPNNs. To address this, we introduce RSNNs, which use random depth-fire first search to guarantee full node coverage and edge coverage with only logarithmic number of samples in sparse graphs When paired with expressive sequence models, we show that RSNNs are universal approximators. Furthermore, RSNNS are also probabilistically invariant to graph isomorphisms. Empirically, RSNNs consistently outperform RWNNs on both molecular and protein benchmarks, requiring up to 16x fewer samples to achieve comparable performance.
Our work builds on recent work in RWNNs that combines random walks with expressive sequence models [3-8] These works explore various walk strategies. including uniform walks B 4 non- backtracking walks (5) minimum-degree local rule walks 77 and learnable walks (8), and propose architectural improvements to enhance expressivity and performance. We critically examine the expressivity of RWNNs under realistic sampling constraints, relaxing prior assumptions that walks long cover times. Based our analysis, propose replace random walks entirely with random searches, leading to RSNNs, a more sample-efficient and expressive alternative.
Our work is not without limitations. In particular, RSNNs are tailored to sparse, medium-sizee graphs. How to scale RSNN to extremely large, densely connected graphs remains an open question. In such settings, full-depth searches may become prohibitively expensive, and edge coverage may scale less efficiently. A promising direction is to explore truncated searches that capture key structural signal while reducing computation. This raises new questions about how coverage and expressivity behave under partial scarches, particularly in dense regimes where full coverage is infeasible.
Despite the focused scope, our results are promising: RSNNs match or exceed RWNN performance with significantly fewer samples and maintain a clear advantage across benchmarks. These findings underscore the value of replacing random walk sampling with search-based sampling in graph learning. More broadly, this work highlights the importance moving beyond local neighborhoods toward sampling strategies that capture global structure. By leveraging efficient coverage through random searches, RSNNs offer principled, expressive, and sample-efficient framework for learning on sparse graphs, laying the foundation for future exploration in other settings.
Acknowledgements
This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship under Award Number DE-SC0023112. It was also partially supported by National Science Foundation under Grants No. IIS 2212143 and IIS 2504090. We thank the anonymous reviewers and members of the MLD3 lab for their valuable feedback.
10

---

References
[1] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, 2014.
[2] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016.
[3] Yuanqing Wang and Kyunghyun Cho. Non-convolutional graph neural networks. In Advances in Neural Information Processing Systems, 2024.
[4] Yanchao Tan, Zihao Zhou, Hang Lv, Weiming Liu, and Carl Yang. Walkim: A uniform language model fine-tuning framework for attributed graph embedding. In Advances in neural information processing systems, 2023.
[5] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions Machine Learning Research, 2023.
[6] Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks. In International Conference on Learning Representations, 2025.
[7] Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade. Youngmin Ryou, and Seunghoon Hong. Revisiting random walks for learning on graphs. In International Conference on Learning Representations, 2025.
[8] Karolis Martinkus, Pál András Papp, Benedikt Schesch, and Roger Wattenhofer. Agent-based graph neural networks. In International Conference on Learning Representations, 2023.
[9] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
[10] Jiong Zhu, Yujun Yan, Lingxiao Zhao Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
[11] Michael Ito, Danai Koutra, and Jenna Wiens. Understanding gnns and homophily in dynamic node classification. In International Conference on Artificial Intelligence and Statistics. PMLR, 2025.
[12] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[13] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, 2022.
[14] Michael Ito, Jiong Zhu, Dexiong Chen, Danai Koutra, and Jenna Wiens. Learning laplacian posi- tional encodings for heterophilous graphs. In International Conference on Artificial Intelligence and Statistics. PMLR, 2025.
[15] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019.
[16] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning, 2022.
[17] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero- -SreeonSooiano,, Puneet K Dokania, Mark Coates, Philip Torr, and Sem-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference Machine Learning, 2023.
11

---

[18] Romas Aleliumas, 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 20th Annual Symposium on Foundations of Computer Science (sfes 1979), pages 218-223, IEFF Computer Society, 1979.
[19] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning. 2017.
[20] Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint 0rX7v:2003.04078, 2020.
[21] Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Machine Learning, 2021.
[22] László Lovász. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
[23] Roee David and Uriel Feige. Random walks with the minimum degree local rule have o(n cover time. SIAM Journal on Computing, 47(3):755-768. 2018.
[24] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735.
PMLR, 2020.
[25] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2020.
[26] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
[27] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[28] Benjamin Reddy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research, 21(90):1-61, 2020.
[29] Ryan L Murphy, Balasubramanian Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. In International Conference Leurning Representations, 2018.
[30] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673. PMLR, 2019.
[31] 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, 2022.
[32] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9():5533-330, 2018
[33] Tim Kucera, Carlos Oliver, Dexiong Chen, and Karsten Borgwardt. Proteinshake: Building datasets and benchmarks for deep learning protein structures. In Advances in Neural Information Processing Systems, 2023.
[34] Weihua Hu, Matthias Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs Advances in neural information processing systems, 1-22118--2113, 2020.
[35] David Weininger. Smiles, chemical language and information system. 1. introduction to methodology and encoding rules. Journal of chemical information and computer sciences, 28 (1):31-36, 1988.
12

---

[36] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference Learning Representations, 2017.
[37] David Rogers and Mathew Hahn. Extended-commectiitt fingerprints. Journal of chemical information and modeling, 50(5):742-75,, 2010.
[38] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder- decoder for statistical machine translation. In Proceedings of the 2024 Conference Empirical Methods in Natural Language Processing, 2014.
[39] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602 4609, 2019.
[40] Christopher Morris, Gaurav Rattan, and Petra Mutzel, Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824-218400, 2020.
[41] Nils M Kriege.
Weisfeiler and leman go walking: Random walk kernels revisited. Advances in Neural Information Processing Systems, 35:201 19-20132, 2022.
[42] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[43] Luis Müller and Christopher Morris. Aligning transformers with weisfeiler-leman. In Interna- tional Conference on Learning Representations, 2024.
[44] Luis Müller, Daniel Kusuma, Blai Bonet, and Christopher Morris. Towards principled graph transformers, Advances in Neural Information Processing Systems, 17:176777-12680,, 2024.
[45] Caterina Graziani, Tamara Drucks, Fabian Jogl, Monica Bianchini, Franco Scarselli, T Gartner, et al. The expressive power of path-based graph neural networks. In International Conference on Machine Learning, volume 235, pages 16226 16249. ML Research Press, 2024.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers an integral part of your paper submission. They are visible the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd a proper justification is given (e.g., "error bars expensive" or 'ee were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased eeknowledge that the true answer often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, they are properly reflected.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we discuss limitations of the work in Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
14

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes, all theoretical results are clearly stated and place all the mathematical proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experimental results are described in the main paper and the Appendix Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
15

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, all data are publicly available and code is available at:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https)
swi.iiossiippccccyoo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
16

---

Answer: [Yes]
Justification:
We leave all training and test details in the main paper and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All error bars explained in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгrоr bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, all details are in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
17

---

Question:
Does the research conducted in the paper conform, in every respect. with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification: The paper conforms in every respect to the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is a general graph representation learning framework with no positive/neggative societal impacts beyond any general machine learning framework for graphs (message-passe paasssnggg graph neural networks, graph transformers, random walk neural networks).
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No new data or models are released with high risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
18

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, all assets are properly credited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessii thcode wwwccoo/aaaooooo datasat has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
All assets properly documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects was used.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
All data used this work are publicly available datasets.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs do not impact the core methodology of the research.
Guidelines:
The answer NA means that the method development in this research does involve LLMSs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurie cttplppp...../ooooooooeoooeoeoo //oooo/rennco//2255//////11/ for what should or should not described.
20

---

A Mathematical Proofs
A.1 Random Walk Neural Network Expressive Power
We begin with the 1-Weisfeiler-Lchmaa (WL) color refinement, which iteratively updates each node's color by hashing its current color together with the multiset of its neighbors' colors (Sec- tion I.I.Ip. WL is known upper-bound MPNN expressivity [15 39] We then introduce Walk Peiiseiler-Lehmann (WWL), a walk-based refinement that updates a node from the multiset of colored walks of length < l tthat terminates number of refinement rounds f,, the maximum walk length f, and the initialization (0) (i.e., richer initial features yield finer partitions). We further show that WWL upper-bounds the expressive power of RWNNs (without positional/IID signals). Finally, using unfolding trees, which simultaneously captures the nodes visible to rounds of message passing and encodes all root-terminating walks of length S t, we prove the main expressivity results that unify MPNNs and RWNNs: equivalence under full coverage and strict separation under partial coverage (Section A.1.3). We provide a more detailed review of existing WL variants and their relation to WWL in Appendix
(Section (Section[A.1.2)) We establish monotonicity of WWL in the
A.1.1 Weisfeiler-Lehman (WL)
We begin with the I-dimensional Weisfeiler-Lehman (WI.) color-refinement procedure, which upper- bounds the expressive power of message- pasasing GNNs and, as we will show later, also upper-bounds RWNN expressive power. Intuitively, WL iteratively refines node labels by hashing each node's current label together with the multiset of its neighbors' labels.
Definition A.1 (1-WL color refinement). Let G = (V, E) be an unlabeled graph and let. (N)) denote
the neighbors of u E V. Initialize a coloring क WLL V -> with constant value (e.g., WL( (1) =
(0)
(0)
for all u). Fort 2 0, update
(++1) (t) n TW.
(u)
Hash (t) (W), (u), 11 Ww (v) ((w))) VuEV,
where Hash is injective and maps pairs of the form (current color, neighbor colors) to E. The process stabilizes at the first 1" for which TW.. FWI.
(oo) (e*) +1"+ we denote the stable coloring by TWL.
To compare two graphs G and H, run 1-WL on each. If the stable color multisets differ (e.g., some color has different node count), the graphs are certified non-isomorphic. If the stable colorings agree, the test is inconclusive (the graphs may still be non-isomorphic). For the remainder of the analysis, we write a < 3 for node-level colorings a, B then au)) = av). These notions coincide with graph-level distinguishabilit:: applying an injective readout on multiset colors and for a I yields graph-level functions fa and fa such that fa 3 fa. Thus, distinguishability at the node-level translates to distinguishability at the graph-level.
+ to mean that 8 refines ar if B()) ((v)
WL has been used to quantify the expressive power of MPNNs. For any standard message-passingg NN, its expressive power is no greater than that of WL. Moreover, if its aggregation function is injective on the multisets of node neighbors, its expressive power matches that of WL.
Lemma A.2 (MPNN vs. 1-WL Expressivity [5 39). Let fMPNN be a MPNN with permutation- invariant readout, and let kWT. denote the 1-WL coloring. Then
AMPNN I TWL.
Moreover, if the multiset aggregator Sagg used by JMPNN is injective, then
fMPNN TWL-
A.1.2 Walk Weisfeiler-Lehman (WWL)
Building on WL, we now align Meisfeiler-Lehmadd to random walk models by defining node-level WWL. scheme that refines node's label from the multiset of colored walks incident to it.
Definition A.3 (WWL. length f). Let = (V, F)) be a graph and & N. For I. 2 1, let
{ W (wo, (wo...,
.......,000. wL) w.) E L (w--1, E Vi [4]}
21

---

be the set of length- L walks, and write Wsr = - WL, the union of all walks of length I é. For node V. define its terminating- walk neighborhood
Wse(u) = W =
wL) E Wee : wz = u
Given an initial coloring -!"); + E (.. uniform or from node features), define for any walk col wwr, (W) = (Tww (wo)...., (1))
"WWL ( (wL)), the colored walk obtained by applying =11) each node in the walk. The WWL update is, for all V.
TWwL
(++1) (WWLe(u) = Hash( T (w)) (u), i col (W) W Wes(u) B))
Lemma A.4 (Monotonicity in t, l, and mo). Fix Fixlsen sesss t', and initial colorings To I T Then
(1)
(e')
(time)
" (FL
3 "Fo)
(5)
(length)
WWL
I T "WWL"
(1)
(6)
(initialiiaation)
(1) (WO)((N))
(1)
"WW)
(t) Consequently, combining each result yields a "wWi 3
á (t')
"WWI." fort S E 8. no m/b-
Proof. Monotonicity in At each step, " : (u) (=sh(= wWLLe (u), includes the current
color as an input. By injectivity of Hash, if two nodes receive the same new color then they had the
(t) same current color. Thus "WWL* "WwL and induction gives the stated inequality for / l'.
(1++1)
Monotonicity in f. & f". For each node u, the multiset of colored terminating walks of lengths < is obtained from the corresponding multiset for lengths S E by the projection that discards all walks of length > l. Therefore, if two nodes are equal under WWL they are equal under WWL (t)
as well. Injectivity of Hash yields T (t) "wwi/ I "WWI""
Monotonicity in the initialization my- Assume mo I T6- Then there exists color-forgetting map p with Mo = o Tt- Apply P pointwise to every color in each colored walk: for any terminating walk W [Wo .... W.).
(To(wo)...., (ww.)))) = (( ((T)(w).)))
Hence the multiset of coloord walks at any node is the image, under this deterministic transforma- tion. the multiset of Th coloreed walks. Consequently, equality of the T based walk multisets im-
(1) plies equality of the -babed walk multisets, and injectivity of Hash gives (ww) I (1)
(w))
The same argument iterates, since each WWL round recomputes colors from the previous round's (f) coloring via the same construction, yielding (ww I "WWL((())) for all L.
(8)
The following lemma is an analogue to expressive results on MPNNs and 1-WL. Intuitively, WWL upper bounds RWNN expressivity, and RWNNs can match WWL' F if their aggregator is injective.
Lemma A.5 (RWNN vs. WWL Expressivity). Let JEWNN be random walk neural network that, for each node u, aggregates over the multiset of all terminating walks of lengths 1,...,& l ending at u, via a permutation-invarion aggregator and a sequence encoder applied to each walk. Let TWLL denote the WWL coloring.
1. (Upper bound) For any choice of encoders/aggregattrs,
fiWNN 3 Twwl.-
That is, two graphs are indistinguishable by WWL', they are indistinguishable by fewNN-
2. (Tightness under injectivity) Suppose the sequence encoder feen is injective on length-aware color sequences and the nodewise multiset aggregator Jagx is injective. Then
feWNN
TWWLC.
22

---

Proof. (Upper bound). ff.t
(1 We prove by induction on / that "WWL:(w) "WwL (v) implies
(2)
f JRWNN()) (u) JRWNN (u).
Base case I. = O. Both procedures start from the same initialization (e.g., uniform or fixed features), so the claim holds trivially.
Inductive step. Assume the claim holds at depth t. Take u, with ((+1) (u) = (t). By injectivity of the WWL hash, the entire inputs the hash coincide, hence
T (t)
(WWw= (W) W Wge(u) H T Wwww (W") W E Wge(c)BB
where each ((()
"wwL: (W) is the length-aware color sequence along the walk W. Thus there is a bijection between terminating walks at and e that preserves these sequences. By the induction hypothesis, matched nodes with equal WWL color at round é have equal RWNN representations at depth f. Therefore, for each matched walk pair, the inputs the per- per-walk sequence encoder feeq agree elementwise, so per-walk encodings match; applying the same permutation-ine innittatiionnvaiaantt multiset aggregator fags yields FRWNN (u) = JRWNN( This completes the induction and the upper bound.
(Equivalence under injectivity). Assume Sueq is injective on length-aware sequences and Sagg is injective on multisets. Let u, v satisfy TWWL (u) & ( "wwLe , By injectivity of the WWL hash, either their current colors round differ, their multisets (4"WWI (W) W E Wee(-)) differ. In the first case, including (an injective transform of) the current node state in the RWNN update separates and v. In the second case, there no bijection between the two multisets of colored sequences; since fseq is injective on sequences and fagg is injective on multisets, the aggregated RWNN representations must differ round ++1. Combining with the upper bound, we conclude
pftt JRWNN = "WLL for all I.
A.1.3 RWNN-MPNN Equivalence Under Full Coverage (Theorem 3.1 Corollary 3.2
Unfolding Trees. We introduce the unfolding tree from Morris al. 40 Kriege 41 which makes explicit the bridge between Weisfeiler-Lehman (WL) refinement and random walks. For a node u in G. the unfolding tree at depth enumerates, with multiplicities, all vertices seen by successive layers of message passing around u. Equivalently, every leaf-to-rool path in the unfolding tree corresponds walk in G that terminates at Hence the unfolding tree simultaneously encodes (i) all messages propagated in leverage this structure to relate the expressive power of WL and WWL.
peassage-passing view and (ii) all terminating walks of length S E at u. We will
Definition A.6 (Unfolding tree 440 41). Let G = (V, E) be graph, & E N. and E V. The unfolding tree of depth l rooted at u. denoted T [e, u]. is the rooted tree defined recursively as follows:
TC u] consists of single root node labeled by
For l > 1. T u] has root labeled by u; for each neighbor e .No(u), attach child fresh copy of T v]
The first key fact ties WL colors to unfolding trees: WL's f-round color of a node is exactly the isomorphism type of its depth-E unfolding tree.
Lemma A.7 (WL ++ unfolding tree Then
(41). Let G, H be graphs, E V(G), E V(H), and L 2 1.
i WT. (u) WT. (v)
1ee, = T [e,
=
Unfolding trees also capture terminating walks: every leaf-to-root path in T u] reads off a unique length-E walk in G ending at u, and conversely. Let
W (TT ul) = il (co....,.2)
(.o...., is leaf-to-root path in TC u] }
be the multiset of vertex- serte--eeueeces read along leaf-to-root paths (ordered from leaf to root). Let We(u) denote the multiset of all length-l walks in G that terminate at (with multiplicity). Then:
Lemma A.8 (Leaf-to-root paths ++ terminating walks 41). For any u E V(G) and 1,
W W(I [e, ul)
We(u).
23

---

(cc) Theorem A.9. For any graphs G. H and any l 2 1, WWL' test has exactly the same distinguishing power as the classical I-dimensional Weisfeiler-Lehmee Lehman test. Formally,
(00) " "WWL'
(00)
"WI."
Proof. "WL 3 -
"WWL. For f= 1, the set of terminating length-1 walks node is exactly its
neighbor set ((u). Hence the WWL. update coincides with the WL update, and for every round
WWL
(2)
WLL in particular
(t)
(00) WWLL
"WL
(00)
By Lemma A.4 (monotonicity 8), WW... 3 7
WWLL for all 2 and all t. Passing to the limit, (00) (00)
(t)
(t)
(00)
WL.
"WWI."
"WWL
"WWL' 3 x WL.
(0c)
Initializing WWL with the WL limit, x x(0) = WT. . it suffices to show that one
WWL update makes no further splits. Fix u E V(G) and E V(H) with TWL (u) = T (v). By TT(,, u] _ [" vj. By Lemma A.8 leaf-to-root paths in these depth-E trees biject with the terminating walks of lengths I,..., l at u and v, respectively; a also preserves wL colors at every node of two unfolding trees. To show this, (xc)
Lemma A.7 there is root-presenv not-preserving isomorphism
(xx) suppose for contradiction, that there exists E Tale, u) with Ti-wi (x) o 1--WL (o()) Since 1-WL stabilizes in finite time on the finite disjoint union G W H, there exists finite witness round k E N (k*) such that Ti-W (x) * ii-WL =oWWi(or( (z)()). Let d be the distance from to the root in Tal., u]. By the 1-WL update rule, mismatch at node round K- forces mismatch its parent round +*+1 (the multiset of child colors differs), and inductively a mismatch at the root after d further rounds:
((k)
(k*++) W..WL
(u) +
(k*+d) (v).
W.W
This contradicts " 7/-WL (u) = xi-Wi (v). Hence a must preserve 1-WL colors every node. Conse- quently, the leaf-to-root paths in Ta (f, u) and Tn [e, v) correspond bijectively under with identical colored sequences. Thus, the corresponding multisets of WI. -colored terminating-we
sequences at
and v coincide. Together with 7 (0)) (u) (0) (v), the entire inputs to the WWL hash agree u and
v, so by injectivity of Hash we obtain π. (1)
(u) x (1)
(* (v). Hence TWL is fixed
"WWL"(> (oo))
point of WWL. By Lemma A.4 WWL is monotone in and mui since uniform <
(oc) TT.. it follows
that n (oo) "WI." I WL Combined with "WL = "WLL= I "www."- we conclude "WWI," ~ TWL
[c0)
We now leverage the preceding results to prove the main expressivity statements.
Theorem A.10 (RWNN- equivalence under full coverage). Let G be graph. Let JRWNN NN
4FC
denote an RWNN with injective feeq and fagg with no additional positional encodings, applied to the complete multiset of walks Wee(G) with lengths up & Cg Cg(G), the edge cover time of G. Let
fMPNN be an MPNN with injective fugg. Then, for all graphs G, H,
JRWNN Hence, FFC JEWNN = SMPNN (i.e., JEC JEWNN and JMPNN are equal in expressive power).
SMPNN = [MMPN(H)) -
FC JR (H).
Proof. By the standard 1-WL result for message passing (Theorem A.2 an MPNN with injective aggregation satisfies fMPNN ~ TWL- By the RWNN/WWL correspondence (Lemma A.5), full- coverage RWNN with injective Seeq and fage satisfies FFC. fRWNN ~ TwwL.. Finally, by the equivalence
TWWL' TWI. (Theorem A.9,, conclude /FC
JiWNN |MPPNN
fRNNN be an RWNN of the same architectural class as in Theorem 3.1 but applied to a multiset of terminating walks that achieves only partial node/edge coverage of the input. Then, for all graphs G, H.
Corollary A.11 (RWNNs under partial coverage). Let #PC.
fMPNN(G) {MPNN(HH
cPC JRWNN (G) fR
24

---

and there exist non-isomorphic graphs G & H such that
fMPNN + {MANN(() while
PCC [RW (RW
PC
Hence JRWNN JMPNN-
Proof. Coverage monotonicity (a direct consequence of injectivity and permutation invariance of the aggregator on multisets) implies that removing walks cannot increase distinguishing power, IPC
i.e., JRWNN 3 f RRWNN = SMPNN, which yields the implication [MPNN( = _MPPNN ()) + pPC
FC
,PC (G) = JWWNN [ For strictness, start from two isomorphic graphs and form G by adding one isolated vertex and by adding one pendant vertex new vertex attached to an existing node). PPC Then 1-WL (hence an MPNN) distinguishes G and H. However, if JRWNN is applied to walk multisets that exclude all walks visiting the added vertex in both graphs, the remaining covered walks coincide, so JRWNN (G) JKWNN (H). Thus RWNNN < [MPNN.
A.2 Random Search Neural Network Expressive Power (Lemma 4.1 Theorem 4.2
We first establish coverage lemma: for any edge e = {u, f in a connected graph G with maximum degree dmmax a randomized DFS (uniform start; i.i.d. tie- tie-breaking) includes in its spanning tree with probability at least 1/dmaxx i.e., Pr(e TDFS(G) 2 1/dmax. Building on this, we show that sampling OK log ) independent DFS trees suffices to achieve full edge coverage with high probability; in bounded-degree sparse graphs (dmax = O11) and [ = @(VV)), this reduces to Ollog (V]) searches. Equipped with such full coverage, standard universal components, and shared anonymous integer tags, RSNNs are universal approximators on graphs in the specified family.
Lemma A.12 (Edge inclusion probability under random DFS). Consider the following random-DFS procedure graph G: fix uniform distribution over the root veriex; independently for each vertex x, draw a uniformly random permutation Fy of its neighbors; run depth-first search that, upon first visiting z, explores neighbors in the order Tz. Let TDPS be the resulting DFS spanning tree. For edge E = (u, v). define
Su(e) = { E N(u)) \ fo} there exists u u path in G \ {e} whose first edge is (u, w) },
and set (e) = [e)(e)]; define Se(e) and To (e) analogously. Then
1
Prfe E E(TDES))
min- +u(e))1's (e(e)+1)
max
dmax
Proof. Let be the event that u is discovered by DFS before v. On A, when u is first processed, v is unvisited. The edge (u. v) will be taken as tree edge iff, in the random neighbor order Ta. the vertex u appears before all neighbors Su(e) that can lead from u to without using e. The positions are irrelevant: exploring any neighbor not on a path to v first cannot reach v before DFS returns to u. Since xu is a uniform permutation, the probability this sufficient event is exactly 1/(r. (e) + 1). A symmetric argument on A (i.e., when v is discovered before u) gives the bound (T. + 1). Unconditionally,
of the other neighbors
Prfe T] Pr(A) Prfe E TIA] Pr(AS) Pife E T A 2 min +a(e)+1' To(e) +15
where T is a random DFS tree. Finally, (e(e) S deg(u) - and TT(e) S deg(v) 1, hence
min(1/(ra + 1), 1/(T, + 1)} 2 1/ max/deg(1)) (u), deg(v)) 2 1/dmax-
O
Lemma A.13 (Logarithmic Sampling Yields Full Edge Coverage). Let G (V, unweighted graph with EE - CVV for some constant C and a bounded maximum degree dmax-- Let
(V,E) F) be a connected,
S1, S2..., Sm be m independent random searches sampled from G, and let Ti, T2,... Tm be their corresponding induced spanning trees. Then, for small 8 & if
CIVI
In
m >
(8)
In
the union Ti, T2,
T2.... ... , I' contains every edge in E with probability at least 1 - 6.
25

---

Proof. By Lemma A.12 the probability that any edge appears in any DFS is at least Pe 2 dmaa
1
Hence, the probability that a single DFS tree does not contain is at most Pe S Augs the spanning trees Tı, ................................ Tm are sampled independently, the probability that e missing from all trees is most
Since
m By the union bound over all |E] edges, the probability that there exists at least one edge which is not covered by the union of the m trees is at most
11
denxx
m
SCIV (1
m
B
dmax
dmax
We require this probability to at most 8:
(1
CIVI
S 8.
drnax
Taking the natural logarithm both sides gives:
(1
dmax ) In(6).
In(CIVI) + mln
Since In (1 amaxx
O, dividing by this term (and reversing the inequality) yields
In
CIVI
In
dumxx
Thus, with chosen accordingly, the union of the spanning trees contains every edge of G with probability at least 1 ò.
Definition A.14 (Anonymous identity and parent tags). Let G = (V) be a graph and let ((2) be the first search sampled on according to the RSNN search algorithm. Write 5(1) (Wo, W1,..., wy) and let (M(1), V(2)) ((n) be the vertices of G ordered by their first-visit time along 5(1), i.e. egg is the i-th distinct vertex encountered in ((1), Define the anonymous identity tag assignment
[n] by
(1 = for 1,...,7 n.
We use the same tag assignment 7 for all searches the RSNN search set on G. Because S(1) is sampled in manner equivariant vertex relabellings, the induced random tag assignment is cermutation-invarii in distribution. Now let S(1) be any search produced by the RSNN search
algorithm, and write {(i) (u) ui u..)). We define parent-tag sequence
(i)
(() -mT T (i)
() E In]
follows. For each index let ()) denote the vertex from which uf is discovered by the RSNN search algorithm along a true edge of G: when ut chosen as an initial vertex of a search, we set
q u. (J) We then define
(3)
m T T(Q())
(3)
for L o,...,Ti.
In particular, the discovery vertex 4 need not equal the previous vertex (.)) in the recorded sequence: 5(d) may contain discontinuities where consecutive vertices n and u not adjacent in G. The parent tag x{() always records, in anonymous coordinates given by 7, the vertex from which the search actually arrived at uf²) along a true edge of G. Thus, the collection of identity and parent tags (r, (mr()))) encodes all edges traversed by the RSNN searches, even across such discontinuities.
26

---

Theorem A.15 (Universal Approximation by RSNNs on Sparse Graphs with Bounded Degree), Let > O and let G + IR be any continuous graph-leve function, where G is the space of sparse, unweighted graphs with |F] O(VV)), maximum degree at most dmax. and size at most |V| S Tmmax- Assume (issN(G) uses (i) universal set encoder Jags, (ii) a universal sequence encoder favqs and (iū) anonymous identity and parent tags. Assume m satisfies Lemma so that full coverage is achieved with probability at least - 6. Then, with probability at least 1 there exists an RSNN configuration such that
I f(G) <e for all G e eg,
(9)
Proof. Let (G) be the set of search sets of size m on G. Define a target on search sets by
F(S) = F(G), S S
0, otherwise.
This f is well-defined (for any given input search set, there is single unique output), and is coomutation-ivvaiian in the multiset argument. Because the input space (bounded-length sequences over finite alphabet, aggregated into multisets of bounded size) is finite, the assumed universal sequence encoder and universal set aggregator can uniformly approximate f to error < across (G). Therefore, with those parameters, for any G and any random S(G),
UGED Smaox
Pr Pr(IIFRSNN(S)) - F(G)]] < E S FullCov(G)) = 1,
and hence unconditionally Pr(IIfRSNN(S) - F(G) < < 21
A.3 Random Search Neural Network Invariance (Theorem
4.3
Corollary 4.4
We next study invariance properties of RSNNs. Because RSNNs are randomized graph functions, we adopt a probabilistic notion of isomorphism invariance: if two graphs are isomorphic, the distributions of RSNN outputs coincide. As consequence, the expected predictor ((G) = =E[[RsNN(C)) (G)] is an isomorphism-inwe invvariant graph function. Moreover, RSNNs learn this invariance via stochastic training: sampling fresh search per step yields an unbiased gradient of the invariant risk, and under standard SGD conditions the parameters converge to a stationary point of the invariant objective. In practice, this justifies sampling with small number of searches (e.g., m=1) in limited budget regimes.
Theorem A.16 (Isomorphism-Invall Invariance of RSNN). randomized search procedure on a graph G produces sequence 5c = ($) ...., ((((c))) of visited vertices. We say the procedure is probabilis-
tically invariant to graph isomorphisms if.
d 100 ......., (((m))))((())) for all G T. H.
The randomized DFS procedure used in RSNNs satisfies the above definition. Hence, RSNNs satisfy probubilistic invariance: for all G H, [RSNN(G) - (H), and the averaged predictor (G) = [[[RSNN(G]] is an invariant function on graphs: 4 = H for all G = H.
Proof. Write XDFS (G) = (8o.-.. v1-1) for the vertex sequence produced by the randomized DFS on G. and let H = G for an isomorphism π V(G) V(H), The randomness comes from: (i) the root su (VG)) and (ii) an independent random order of neighbors at each vertex.
We prove by induction on that the next state has the same pushforward conditional law under any isomorphism
क (XDrs(G))[
x) d Xprs(H)(t) Xx,
(10)
for every valid DFS prefix x (5o, (so...., 8 G (and its image ax H). Averaging over prefixes then yields π. Tx))Fs())[t] 1 XpFs [t] for each and thus xXDFs(G) d (H).
27

---

State, admissible set, and frontier. For prefix x valid on G, let VG; = {so..... St-13 be the visited set and let ;op(G; x) be the current DFS stack top (the vertex whose adjacency list being explored). Define the admissible neighbor set
x( = -((top(G:x) \ (G;
If A # Ø. the rule "pick the unvisited neighbor at random" makes the next vertex uniform on x() If A(G;)) = Ø, the next move is the (deterministic) backtrack the parent of top(G;x) in the current DFS tree. Under an isomorphism x G H, relabeling preserves these invariants:
top H π = π (top(G:x)), Vvi(H;; = π (Vin
A(H; Tx) = π (A(G:x)))
Base case (t = 0). so ~ Uni)(V(G)) and map ~ Uvif(V so xXDrs(G)(of (D)))H)
Induction step. Assume x DDS 1] X (H) |: f). Fix any realization x of the prefix on G. There are two cases.
(i) Expansion step: A(G;x) + Conditioned on x, XDFS [G) is uniform on A(;;x). Condi- tioned on иx, Xprs( (1) [t] is uniform on A( xG; Pushing the uniform measure on A(G; x) forward by æ yields the uniform measure on TA(G: x), hence
π (XDDs(G))L x) _ XDFs(H)()) mX.
(ii) Backtrack step: x(G; determined by x: thus it is deterministic given x. Relabeling preserves parent/child relations in the explored DFS tree, so
The next state is the parent of top(G; in the DFS tree
π (XDrss x) = EDEs(H))) Xx,
In both cases, conditional laws match after applying n. Taking expectations over the distributions gives π. XDFS (G)[ XDDs( for each which completes the induction and yields
d
(DF d XDrs(H).
This proves probabilistic invariance of the randomized DFS. Since the RSNN output fRSNN is deterministic function of the search sequence, it follows that (RSNN(G) fRSNN(H), and the averaged predictor (G)) [[[fRNN an invariant graph function.
Corollary A.17 (Stochastic training converges to the invariant objective). Let E(:, v) be differen- tiable loss. Consider the expected risk
L(W)= EEGG,Y>D E (S-SSos( [e[nNNNN S; W), y)]-
At each SGD step t, sample (Gt, y1) ~ D and one search draw S. ~ SDrs(Gi), and update
W411 = W.
V {fRSNN S₁; W.), y1).
Then E V [(fnNNN (G,, Sú W.). v:) WW i.e., the single-sample gradient is unbi- ased estimator of the invariant objective's 's gradient. Under standard SGD conditions, W converges almost surely the optimal W* of the invariant objective.
Proof sketch. This follows directly from the proof of Proposition A.1 in Murphy et al. (2). re- placing permutations by RSNN searches: since the search randomness S ~ SDFS(G) (') is sampled independently of W and is differentiable with integrable gradient, we can exchange Vw and the expectations get VwL(W)
[w[[fRsNx(G,Ss) W). so the single-sample stochastic gradient is unbiased; standard Robbins-Monno/Polyat supermartingale arguments then yield a.s. convergence of SGD stationary point (and W under convexity). O
28

---

B Additional Model Details: Positional Encodings and Sampling Algorithms
In this section, we provide additional details on the positional encoding scheme and sampling algorithms used in both RSNN and RWNN models. These components are essential not only for implementation but also for theoretical expressivity. We also present detailed descriptions of the sampling procedures for both random walks and random searches. For RWNNs, we outline the walk generation algorithm, including initialization, neighbor selection, and PE encoding. For RSNNs, we describe the random depth-first search strategy, including how spanning trees are constructed and how node visitation handled.
B.1 Positional Encodings
Identity and Adjacency Encodings. Tönshoff et al. [5] and Chen et al. [6] augment each walk with two binary feature matrices that inject explicit structural context. For a walk W (Wo..... ...,, wyy on graph G, the identity encoding idw E {0. 13 (f+1)x* marks node repetitions within sliding window of size s: for indices 0 S i < l and 0 S j S s - we set
idw [ = 1 iff i - 2 1 and w; Wi-j:
and 0 otherwise. Thus column j signals whether the current node re-appeared exactly j steps earlier, explicitly encoding cycles of length j H++1, Second, the adjacency encoding adjũ- E {0, (0 (e+))xx((=1 records edges among already-vishee visited nodes that the walk does not traverse. We define
adji [i. = 1 iff i - 2 1 and (wi, w;-s) E E(G),,
and otherwise. Here, E() denotes the edge set of the input. Consequently, for every pair of nodes that appears within the window, the encoding reveals whether they are adjacent in the underlying graph. The two blocks are concatenated to form a positional encoding matrix hpg = [id, adjj [(+1)xxdg with dpe = 2s 1. Appending hpg to the raw node embeddings ensures that, once full node- and edge-coverage is achieved, the sequence model receives enough information to reconstruct the entire subgraph induced by the walk.
Anonymous Encodings. As an alternative the adentity-adjacency scheme, anonymous encodings have been proposed to capture graph structure by Wang and Cho [3] and Kim et al. [7]. For a walk W create an integer vector Wanon (W) {I...., + 1 defined recursively:
1 maxf Wanon (W) - 1]}, if we & {wo..... W;-1,
Wanon (W)
Wanon (W)ss),
if s < t is the first index with w. We-
In words, the first time node appears in the walk it is assigned the next unused label 1, 2, every subsequent visit to that same node reuses the original label. Hence Wanen is invariant to the specific node IDs yet records the order in which unique vertices discovered, providing topological context without relying on absolute labels.
Role in Expressivity. These positional encodings play critical role in the expressive power of both RWNNs and RSNNs. They serve as the main mechanism by which the walk or search encodes structural information from the underlying graph. In particular, the identity and anonymous encodings, when combined with walks that achieve full edge coverage, allow for exact reconstruction of the input graph. Meanwhile, adjacency encodings with sufficient window size and identity/parent tags introduced in Definition A. 14 enable full reconstruction even with only node coverage, as they record structural edges not explicitly traversed in the sequence. In our RSNN implementation, we rely on adjacency encodings. These are especially important for preserving expressivity in RSNNs: depth-firs. first searches introduce disconnections in the sequence, where jumps between non-adjacent nodes may obscure structure. Consider for example nodes w, and Wi+1 traversed adjacent to one another in a search sequence, but disconnected in the graph. With an appropriate window size, the adjacency encoding first signals the disconnection setting adjí + 1, = 0, then identifies the connecting edge when it appeared in the sequence setting adjw li 1, = for (w;, ( E EG). This ensures that, once full edge coverage is achieved across searches, the sequence model receives all structural information necessary to reconstruct the graph. Thus, positional encodings are central to the theoretical guarantees of RSNN expressivity.
29

---

Algorithm 1: Uniform Random Walk with Positional Encodings
Input: Graph G== (V, F), walk length I, window size
Output: Random walk W (Wn. ..., wi), encodings idjy, adjiy Sample initial node wp ~ L((V)
Initialize W <- [wr]]
for +- 1 to do the neighbors of W
Let Lt)
Sample wy ~ [(([V(Wi-11)
Append w; to W
for j to do
i 2 then
id [[,]] t 1|w, wi-sl
// Identity encoding
adji [1 + l(w, w)-s) E b)]
// Adjacency encoding
return W, idsy. adjiy
Algorithm 2: Random Depth-First Search with Adjacency Encodings
Input:
Graph (V, F),, window size
Output: Search sequence W (wo...., .,, wz). adjacency encoding adji Sample initial node ~ 2(V))
Initialize stack S [Wo]. visited set V {wn}, walk W
Initialize adjy 0 (VI((=-1)
while not empty
Pop 4 S Append u to W
for j to do then
if W|| adji [W] 4. < 1[(u, W[W] E
// Adjacency encoding
Let (u)) be unvisited neighbors of in random order foreach v E (Nu)
Push onto S Add to
return W, adjiv
B.2 Sampling Algorithms
Random Walk Sampling. We adopt standard uniform random walk procedure to extract quences from a graph (Algorithm [T. The algorithm begins by uniformly sampling a starting node from the vertex set. At each step, it selects the next node uniformly at random from the current node's neighbors. As the walk progresses, we maintain a sliding window of fixed size 8 to compute identity and adjacency encodings for each step. The algorithm takes as input the graph G, walk length 7, and window size 8, and returns both the walk and the corresponding structural encodings.
Random Search Sampling. We implement random searches in RSNNs using randomized depth- first search (DFS) traversal (Algorithm(2) The algorithm begins by sampling a starting node uniformly random from the vertex set. From there, perform standard DFS, visiting each neighbor in a random order to introduce stochasticity. As nodes are visited, they are recorded sequentially in the walk W. and only the adjacency-bass based positional encoding adjw is computed using sliding window of size s. Since DFS visits each node exactly once, identity encodings are unnecessary. The resulting walk and adjacency encoding together define the structural input for RSNNs.
30

---

C Extended Results
We present two additional experiments to complement our main findings. First, we conduct an ablation study evaluating the impact of the sequence model architecture on performance by comparing CRAWL, the best performing RWNN, and RSNNs equipped with GRUs, LSTMs, and Transformers on molecular benchmarks. This experiment helps assess whether the RSNN framework is sensitive to the choice of sequence model. Second, we report runtime comparisons between RSNNs and RWNNs to evaluate computational efficiency. Specifically, we compare training times across varying sample sizes to understand how the two approaches scale under realistic computational budgets.
C.1 Sequence Model Ablations
We evaluate the impact of sequence model architecture by comparing RSNNS and CRAWL equipped CRAwLeqqupped with GRUs, LSTMs, and Transformers (Table []. Across all configurations, the trends from the main paper hold: RSNNs consistently outperform RWNNS at low sample sizes (m = 1), regardless of sequence model. Notably, RSNNS with m 1 often match or exceed the performance of RWNNs with m = 16, reaffirming the sample efficiency advantages of random search. When m = 16 on the BACE dataset, CRAWL-LSTM and CRAWL-GRU slightly outperform their RSNN counterparts, however in the remaining comparisons RSNN always outperforms CRAWL across all m. Overall, GRUs and LSTMs perform comparably within both RSNN and RWNN variants, indicating that RSNN improvements are robust to the choice of sequence model, provided it has adequate recurrence-bast inductive bias. In contrast, Transformers underperform relative GRUs and LSTMs across most benchmarks and sample sizes. One possible explanation is that Transformers lack the hard-coded recurrence structure present in GRUs and LSTMs, relying instead global attention mechanisms
Table 4: Median (min, max) of model AUC across test splits on molecular benchmarks. We report results for each model equipped with one of three sequence models: (1) GRU, (2) LSTM, or (3) Transformer (TRSF), as indicated by the suffix. The best model for each value of m is highlighted in blue. Trends from the main paper hold across architectures: RSNNs consistently outperform RWNNs at low sample sizes, with GRUs and LSTMs yielding similar performance, while Transformers underperform across most settings.
MolcculeNet Molecular Benchmarks (AUC f)
CLINTOX
SIDER
BACE
BBBP
TOX21
TOXCAST
Graphs Avg. [V]
1.5K
1.5K
1.5K
2K
8K
9K
26.1
33.6
34.1
23.9
18.6
18.8
Avg. [E]
55,5
70,7
73.7
51.6
38.6
38.5
# Classes
2
2
2
2
2
CRAWL-TRSP
59.8 (1.))
60.3 (57.2. 68.4)
67.6 (65.2, 73.3)
74.6 (66.1. 79.4)
70.4 (65.3, 74.5)
70.8 (65.4, 75.3)
CRAWL-LSTM
66.7 (10.4. 50.2)
61.4 (57.4. 63.8)
66.2
(60.7. 71.4)
74.4 (68.4,
72.2 (67.6 76.0)
71.5 (67.7. 75.4)
CRAWL-GRU
70.0 (64.6,
64.2
67.2)
62.5 (59.2, 70.8)
(68 81.5)
71.7 (66.4, 75.3)
72.8 (67.7. 76.7)
RSNN-TRSF
82.9 87.))
65.6 (63.1. 71.9)
78.0 81.5)
85.6
77.7 (73.8, 78.9)
74.2 (7088 76.5)
RSNN-LSTM
(826.62..88.
66.8 (61.7. 72.2)
78.2 (74.3, 84.3)
87.1 (83.9, 89.5)
79.5 (77.2, 83.7)
75.6 (72.9, 80.6)
RSNN-GRU
88.1 (84.9,91. 91.5)
66.2 (63.0. 72.4)
79.7 (75.9) 83.6)
87.5 (80.3, 89.9)
79.8 (77.2, 83.4)
74.6 (72.3. 79.7)
CRAWL-TRSF
69.4 (49.0, 79.0)
64.7 (61.1, 69.5)
73.7 (68.4, 75.4)
82.6 87.77
87.7)
74.5 (71.6,
71.3 (60.1, 80.)
CRAWI-LSTM
(72.3 63.8)
66.3 (63.2, 68.8)
72.7 (67.5, 78.5)
84.0 (78.5, 88.6)
77.5 (75.3, 79.9)
74.6 (71.1, 79.9)
CRAWL-GRU
83.0 91.5)
65.2 (59.5. 71.3)
75.7 (71.0, 79.0)
84.5 (80.7, 87.0)
77.6 (75
74.4 (69.1. 77.9)
RSNN-TRSF
84.2 (63.4.
67.1 (61.6, 70.8)
79.8 (69.4. K2.5)
85.6 (79.9, 90.7)
78.0 (74.2,
76.6 (71.5,
RSNN-LSTM
88.7 (8.22.908))
67.5 (64.1,70.1) 70.1)
80.9 (75.3) 84.4)
88.9 (82.7, 91.6)
81.4 (76.3, 83.3)
76.6 (73.8 81.3)
RSNN-GRU
89.1 (80,9, 91.7)
67.0 (1.1
80.4 (76.5. 84.0)
88.0 90.5)
80.3 (77.3, 84.2)
76.1 (72.2, 79.0)
CRAWI-TRSP
68.3 (53.1.881))
65.9 (62.6. 71.4)
75.4 (66.6, 80.7)
85.4 (79.2, 89.6)
76.4 (71.8, 78.2)
75.2 (72.0, 78.7)
CRAWL-LSTM
87.2 (78.3, 89.4)
67.1 (63.6 70.7)
79.2 (76.8, 83.2)
86.8 (79.5, 91.6)
78.9 (1.7)
73.5 (68.9. 77.3)
CRAWL-GRU
86.5 (836,
66.1 (62.1. 69.9)
80.3 (71.0, 82.5)
86.0 (82.8, 89.6)
79.1 (76.7, 82.1)
75.5 (72.0, 78.6)
RSNN-TRSF
82.7 80.9)
66.8 (62.5. 72.0)
80.2 82.4)
86.4 90.7)
76.8 (75
75.2 81.4)
RSNN-LSTM
88.4 (82.2, 90.6)
67.2 (64.3, 74.6)
80.7 (74.8, 87.1)
88. 1 (82.6,91.4)
81.1 (77.7
75.9 (72.3, 82.2)
RSNN-GRU
88.3 91.3)
67.6 (63.3, 69.2)
80.0 (76.1, 85.1)
88.6 (83.6, 90.3)
82.2 (77.3, 85.3)
75.7 (73.0, 78.9)
CRAWI-TRSP
69.6 (47.6, 56.9)
65.1
70.1)
78.8 (73.5, 79.7)
85.2 (79.5, 89.3)
77.7 (75.8, 81.9)
74.88 (72.1, 80.0)
CRAWL-LSTM
87,8 (80.1, 89.5)
65.7 (63.4, 69.0)
79.5 174.4, 86.0)
87.1 (79.7, 93.9)
79.2 (77.9, 82.5)
76.2 (70.4, 79.0)
CRAWL-GRU
89.1
91.1)
65.3 (61.4, 70.8)
80.7 (76.1, 84.5)
(11.7 90.3)
80.9 (77 82.6)
76.2 (72.7, 77.9
16 RSNN-TRSF
84.4 (78.5,91.)
66.6 (63.6 73.6)
81.0 82.8)
86.0 (78.7. 70.7)
77.6 (74.5,
76.4 (72.3,
RSNN-LSTM
88.3 (81.9, 92.2)
67.3 (64.8, 71.9)
80.5 (79.0, 84.3)
88.5 (83.8, 91.2)
82.0 (78.8 83.5)
75.5 (72.9, 80.0)
RSNN-GRU
88.5 (82.0, 93.7)
67.1 (65.0) 74.0)
79.8 8. (7688 84.9)
89.4 (83.0, 91.7)
82.2 (78.,, 84.1)
76.5 (73.4, 79.3)
31

---

that may require more data to model sequential dependencies effectively, especially in low-sample regimes. These results suggest that recurrent sequence models are better suited for graph-based walk or search processing under constrained sampling budgets.
Rusttace (Sccands)
Ruantace (seconde)
TustUine (osconnda)
100
BSNN CRAWL
400
CRAWL
BSNN
300
RSNN CRAWL
200
200
100
16
16
Number Welks//eeurhhss
Nummbrr Welks/Seeuchees
Number Welkst (m)
SIDER
(b) BBBP
TOXCAST
Figure 4: Training runtime (in seconds) of RSNN and CRAWL over 25 epochs on SIDER, BBBP. TOXCAST function the number of samples m. Error bars represent standard deviation across 5 runs. At low sample counts, RSNNs exhibit comparable runtime to RWNNs; RSNNS become faster despite longer sequence lengths. We hypothesize this is due to random walks repeatedly visiting high-degree nodes, incurring more computation per step, whereas DFS-based searches visit each node exactly once.
increases,
C.2 Runtime Comparisons
Experimental Setup. To ensure fair comparison between RSNNs and CRAWL, we fix all model components except for the sampling strategy. Both models use GRU sequence model with hidden dimension 64 and are composed of 2 layers. We the positional encoding window size to 8 and batch size to 64. For each graph, the random walk length is set to / [VI, equal to the number of nodes, so that the number of sequence steps is identical between random walks and searches. As result, RSNNs and CRAWL have equivalent asymptotic runtimes per sample. We measure training runtime over 25 epochs on three molecular benchmarks, SIDER, BBBP, and TOXCAST, across varying sample sizes m E [1, 4, 8, 16). For each forward pass, fresh set of m walks or searches is sampled per graph. All experiments are run on a single NVIDIA GeForce GTX 1080 Ti GPU, with sampling parallelized across CPU workers reflect practical deployment conditions.
Results. Empirically we observe that RSNN searches are never more expensive than CRAWL walks for any tested number of walks and that for larger the RSNN implementation can even become faster (Figure 4). Although, each routine shares the same asymptotic cost, O(VVI) on our sparse graphs, they differ by constant factors that affect runtime comparisons in practice:
Random Walks Revisit Nodes with Larger Degrees. A DFS visits each vertex exactly once, while a random walk visits nodes randomly, potentially revisiting many vertices with higher degrees. Consequently, searches and random walks visit different sets of nodes. This affects runtime since operations per node depend on their degrees (e.g.. shuffling neighbors, random choices neighbors, identity/adjacency checks), incurring per-step and increasing runtimes for random walks.
computation
Per-step work. The DFS runs one for loop that updates a single -encoinngg tensor. The RWNN walk performs an identical for loop, but each iteration evaluates two conditions (identity adjacency encoding) and writes to two tensors, effectively doubling the cost of that inner loop per step.
Neighbor handling. DFS shuffles the neighbor list once per new vertex, whereas random walks rebuilds Python list and calls random. choice every step, and if non-backtracking is enabled, creates an additional filtered list. These repeated list allocations and Python-level random picks inflate wall time.
Together, these constant- differences explain why the asymptotically identical O(VVI) algo- rithms show distinct wall-time profiles: RSNN remains competitive for all m, while CRAWL exhibit longer runtimes larger m.
32

---

D Experimental Details and Code
Training and Hyperparameter Selection. All models are trained by minimizing the binary cross- entropy loss on molecular benchmarks and the negative log-likelihooe loss on protein benchmarks. Training performed for a maximum of 200 epochs with early stopping patience set to 25 epochs based on validation performance. The best-pertee rest-performing model on the validation set is selected for evaluation on the test set. We perform grid search over following hyperparameters and RSNN models:
RWNN
Number of layers: {1, 2,
Learning rate: {0.05, 0.01, 0.005, 0.001]
Batch size: (32, 64, 128)
Hidden dimension: {32, 64, 128)
Global pooling: (mean, sum, max)
Sequence model: [GRU, LSTM, Transformer]
Number of samples m: (1, 4, 8, 16)
We fix the window size 8 for both CRAWL and RSNN models. All models are optimized using the Adam optimizer 42
E Extended Discussion
Background WL and its Variants. The Weisfeiler-Lehhmnn (WL) hierarchy has become a standard lens for characterizing graph model expressivity. Xu et al. [15 first established the equivalence between I-dimensional WL and MPNNs, while Morris al. [3]. Azizian and Lelarge [2 generalized this perspective to higher-order GNNs via higher-order WL variants. Beyond MPNNs, recent work has aligned graph transformers with WL, clarifying their expressivity within the same hierarchy 43 44 In parallel, random walk kernels and path GNNs have been connected to WL as sequence- based representations
45
(WWL) refinement builds directly on this line: we introduce a walk- based color refinement and show that, under full coverage, its distinguishing power coincides with 1-WL. In doing so, we place RWNNs firmly within the WIL-centered expressivity landscape alongside MPNNs, graph transformers, and path-based GNNs, advancing unified view of diverse graph learning architectures through the WL hierarchy.
Our Walk Weisfeiler-
33


Reviews:
[{"review_id": "vu0gRBOL6Q", "reviewer": "Reviewer_kbHS", "summary": "The paper compares several methods for obtaining data about graphs via neural networks: in one approach (subgraphs GNN), the neural network is based on subgraphs, in the other (RWNN), it is based on random walks, and in the third (RSNN), it is based on random depth-first trees. The paper presents several theorems, as well as empirical results, suggesting that RSNN is superior to RWNN, which in turn is superior to subgraphs GNN. I suggest accepting this paper.", "questions": ".", "limitations": ".", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The results are strong, but it is very hard for the reader to understand what they really are, because too many notions are not well-defined. For example, the notion of expressivity is presented many times, but never rigorously defined. In line 146, there is a list of papers evaluating expressivity, but no hint as to what this expressivity is or how it is evaluated. In Theorem 3.1, it is unclear what \"equipped with maximally expressive components\" means, and so on. It would help a lot to give a definition, or at least a heuristic explanation. \n\nFrom Proposition 2.1, I guess expressivity has to do with distinguishing between nonisomorphic graphs, and that \"appropriate graph metric\" means a metric that somehow measures how graphs are close to being isomorphic. But I would be very happy with a few words affirming or refuting my guess.", "was_revised": true, "final_justification": "The authors answered my concerns to my satisfaction", "rebuttal": "We appreciate your detailed and thoughtful feedback and comments. Below, we address your specific comments individually. \n- **Does expressivity have to do with distinguishing between nonisomorphic graphs?** Yes; proposition 2.1 adopts the classical Weisfeiler–Lehman perspective, defining an RWNN as expressive when it distinguishes pairs of non-isomorphic graphs. Theorems 3.1 and 3.2 use the functional perspective, where a model is expressive if it can approximate the space of continuous graph-level functions $f : \\mathcal{G} \\to \\mathbb{R}^{d}$. These perspectives coincide for GNNs: any architecture that separates isomorphism classes is also a universal approximator on continuous graph functions, and vice versa (Chen et al., 2019). We will emphasize this equivalence in the updated version and state explicitly that Proposition 2.1 relies on the isomorphism-distinguishing criterion, whereas Theorems 3.1 and 3.2 rely on the universal-approximation criterion.\n- **In Theorem 3.1, what does \"equipped with maximally expressive components\" mean?** By “maximally expressive components,” we mean that given sufficient width/depth, every learnable sub-module can approximate any continuous function (i.e., is universal) defined on its domain. Theorem 3.1 assumes each such component has enough capacity to reach this universal regime; thus any remaining approximation error is due to the sampling scheme. We will make this definition explicit in the revised manuscript. \n- **Does \"appropriate graph metric\" mean a metric that somehow measures how graphs are close to being isomorphic?** Yes; In the proofs, we instantiate the metric with the graph-edit distance, which measures how close graphs are to being isomorphic (Keriven and Pyre 2019). We will explicitly state our use of the graph edit distance in the revised statement of Theorem 4.2.\n\n**References**\n\nChen, Z., Villar, S., Chen, L., & Bruna, J. (2019). On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32.\n\nKeriven, N., & Peyré, G. (2019). Universal invariant and equivariant graph neural networks. Advances in neural information processing systems, 32."}, {"review_id": "f8WxIwwRsC", "reviewer": "Reviewer_CoWK", "summary": "This paper presents random search neural networks (RSNNs), which operate on random searches to provide a more efficient, expressive, and generalizable model compared to random walk neural networks (RWNNs). The authors provide a series of experimental results and theoretical justifications on the advantages of RSNNs.", "questions": "See weaknesses. Additionally:\n- Tönshoff et al., 2023 state that GNNs intuitively have an advantage over RWNN methods such as CRaWl since GNNs effectively perform a breadth-first search. Given this and the fact that a final permutation-invariant function that is applied at the end, do the authors have some intuition as to if using BFS rather than DFS would meaningfully change the performance of RSNNs?\n\nReferences:\n\nTönshoff et al. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. In _TMLR_, 2023.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and easy to follow\n- Experimental results support the claim that RSNNs improve performance across several different benchmarking tasks. Inclusion of traditional molecular fingerprinting methods provide a holistic comparison for molecular models.\n- The authors provide clear theoretical analysis for RSNN - Theorem 4.2 in particular provides an interesting result.\n\nWeaknesses:\n- Although the authors present a compelling argument that RSNNs are more efficient in achieving full coverage of a graph, the following results linking higher coverage to increased expressivity seem somewhat trivial. Especially since most of the results are related to graph-level tasks, it is obvious that seeing more of the input graph would lead to better performance.\n  - Theorem 3.1 also seems somewhat trivial given a recent result in Bao et al., 2025 (Theorem 4.6) which already proves that motif/homomorphism encodings (which are directly related to subgraphs) are more expressive than random walk encodings. Could the authors please address how their result meaningfully builds upon this?\n\nReferences:\n\nBao et al. Homomorphism Counts as Structural Encodings for Graph Learning. In ICLR, 2025.", "was_revised": true, "final_justification": "The authors provide clear justification for their model design choices and will incorporate additional discussion around their theoretical results related to random walk encodings. They have also provided additional experimental results on dense graphs and compared to additional subgraph-GNN models which support their theoretical results.", "rebuttal": "Thank you for your detailed and valuable feedback. We’re encouraged that you found the paper well-written and easy to follow, our experimental results both holistic and compelling, and our theoretical analysis, particularly Theorem 4.2, insightful. Below, we address your specific comments individually. \n\n- **Coverage as an expressive bottleneck.** We agree that intuitively, “seeing more of the graph should help.” What our contribution adds is a *formal, quantitative* statement of how partial coverage limits expressivity even when the downstream sequence model is already universal and equipped with expressive positional encodings. By establishing the limitations induced by partial coverage, we give a rigorous justification for replacing random walks with our random-search sampler. \n- **How do theoretical results build on Bao et al., 2025 (Thm 4.6)?** Bao et al. compare *structural encodings*, showing that random-walk structural encoding (RWSE), defined as the diagonal entries of the $\\ell$-step random walk matrix $(D^{-1}A)^\\ell$, is strictly weaker than their motif-based encoding (MoSE) even when $\\ell$ is infinite. In contrast, our Theorem 3.1 tackles a different axis: the *expressive power of full architectures*. We study RWNNs, whose inputs are the full length-$\\ell$ walk **sequences**, not just the return probabilities along the diagonals of the random walk matrix. Consequently, an RWNN equipped with a universal sequence model is fundamentally more expressive than the RWSE structural encoding. Theorem 3.1 shows that this stronger class can become strictly less expressive than subgraph-based GNNs whenever the walk sampler fails to achieve full coverage. In other words, we pinpoint coverage of the sampling scheme rather than the capacity of the downstream sequence model as the limiting factor. This complements Bao et al., 2025: their result isolates a limitation of a *particular structural encoding*, whereas ours links expressivity to the *search strategy itself* and motivates richer samplers such as our random-search procedure. We will add a discussion after Theorem 3.1 to make this connection explicit and clarify that our contribution extends the RWSE vs MoSE comparison to the architectural level and to the role of graph coverage.\n- **BFS vs. DFS.** We adopt a depth-first search (DFS) sampler rather than breadth-first search (BFS) because DFS preserves continuity in sequences which is important in reflecting the graph structure. In contrast, BFS jumps within neighborhoods and yields many disconnected subsequences. Empirically, we observe that swapping DFS for BFS results in a slight decrease in performance. We will add this justification for utilizing DFS rather than BFS when introducing our RSNN approach."}, {"review_id": "9p8HNjFosH", "reviewer": "Reviewer_k2UB", "summary": "This paper proposes RSNN, a graph representation learning method based on depth-first search (DFS). To address the limited expressivity of RWNNs under realistic sampling constraints—due to insufficient node and edge coverage—RSNN generates spanning trees via DFS to achieve full graph coverage with significantly lower sampling cost. Theoretical and empirical results demonstrate that RSNN offers stronger expressivity and better performance, especially on sparse graphs such as molecular and protein datasets.", "questions": "1. The experiments focus on sparse molecular and protein graphs. How does RSNN perform on larger or denser graphs? Additional results or discussion would clarify its generality.\n\n2. Since subgraph GNNs are discussed theoretically, can the authors add empirical comparisons with such methods to better position RSNN?\n\n3. The paper lacks detailed explanation of methods, such as the DFS sampling and spanning tree encoding. Please clarify or provide pseudo-code to improve reproducibility.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Novel analytical perspective: The paper analyzes model expressivity from the perspective of node and edge coverage, providing a new angle for understanding the limitations of RWNNs.\n\n2. Theoretical support: It offers solid theoretical results, showing how full coverage improves RWNN performance and establishing universal approximation and generalization guarantees for RSNNs.\n\n3. The paper is clearly written and well-structured, making the motivation, methodology, and analysis easy to follow.\n\n4. Experiments on molecular and protein benchmarks demonstrate consistent and meaningful improvements over RWNNs, using fewer sampled sequences.\n\nWeaknesses:\n\n1. The experimental evaluation focuses mainly on small and relatively sparse datasets (molecular and protein graphs), leaving it unclear how well the proposed method generalizes to larger or denser graphs.\n\n2. Some technical details of the method are presented at a high level, and certain design choices (e.g., how DFS is implemented or integrated with the sequence model) are not clearly explained, making it harder to assess reproducibility and implementation complexity.", "was_revised": true, "final_justification": "The authors have addressed my concerns, and I will maintain my positive score.", "rebuttal": "Thank you very much for your thoughtful feedback! We are delighted that  you found our coverage perspective novel, our theoretical results compelling, our experiments consistent and meaningful, and our paper overall clearly written and well-structured. Below, we address your specific comments individually.  \n\n- **How does RSNN perform on larger or denser graphs?** Great question. We ran additional experiments to measure how RSNN scales to **dense** graphs (see experiments below). We don’t evaluate on large graphs because we focus our evaluation on small to medium graphs, where global structure, long-range dependencies, and high expressivity are essential, in comparison to large graphs, where locality is more important to capture and as a result message-passing GNNs already work well (e.g., node classification in citation networks). To demonstrate that RSNN generalizes beyond sparse molecular and protein graphs to **denser** graphs, we have since evaluated it on two graph classification benchmarks of dense brain networks from NeuroGraph (Said et al., 2023): a Gender prediction set of 1000 graphs (avg. 1000 nodes, avg. 46000 edges, avg. degree ≈ 46) and an Activity prediction set of 7500 graphs (avg. 400 nodes, avg. 7000 edges, avg. degree ≈ 18), both substantially denser than our molecular and protein datasets. We compare performance and runtime of RSNN vs. CRAWL, the strongest RWNN baseline. RSNN consistently outperforms CRAWL on both tasks, for all $m$, confirming its ability to leverage global structure in dense regimes (Table 1), underscoring that RSNN retains its performance advantage on denser graphs.\n\nTable 1. Mean and standard deviation of CRAWL and RSNN performance on dense NeuroGraph datasets. \n| | Gender (ACC) | Activity (ACC) |\n| ------- | ------- | ------- |\n| (m=1) CRAWL | 0.640 ± 0.021 |    0.614 ± 0.007     |\n| (m=1) RSNN | **0.662 ± 0.027**    |     **0.619 ± 0.020**    |\n| (m=4) CRAWL | 0.676 ± 0.023 |    0.763 ± 0.009     |\n| (m=4) RSNN | **0.693 ± 0.008**    |    **0.797 ± 0.014**     |\n| (m=16) CRAWL | 0.676 ± 0.033    |     0.850 ± 0.004    |\n| (m=16) RSNN |    **0.707 ± 0.023**    |     **0.865 ± 0.007**    |\n\n- **Can authors add empirical comparisons with Subgraph GNNs?** To better position RSNN against subgraph GNNs empirically, we have included the Equivariant Subgraph Aggregation Network (ESAN; Bevilacqua et al., 2022) as a subgraph‐GNN baseline. ESAN operates by constructing node‐deleted subgraphs, removing each node and its incident edges, applying a standard GNN encoder to each subgraph, and then pooling the resulting embeddings with a DeepSets module to yield a global graph representation. In our experiments (Table 2), ESAN can indeed outperform RWNN when RWNN only achieves partial coverage sampling only one walk (m = 1). However, once RWNNs attain full coverage (m = 16), they match or exceed ESAN’s performance. This aligns with our theoretical analysis that partial‐coverage RWNNs are less expressive than subgraph GNNs. RSNN on the other hand, achieves full node coverage and high edge coverage with just a single search, outperforming both RWNN and ESAN, even when m=1. We will incorporate the ESAN baseline into the main paper to strengthen our empirical evaluation.  \n\nTable 2. Mean and standard deviation of RWNN, RSNN, ESAN performance on SIDER and BBBP MoleculeNet datasets. \n| | SIDER (AUC) | BBBP (AUC) |\n| ------- | ------- | ------- |\n| ESAN | 0.660 ± 0.022 |    0.741 ± 0.046     |\n| (m=1) RWNN | 0.622 ± 0.029 |    0.736 ± 0.073     |\n| (m=1) RSNN | **0.665 ± 0.020**    |   **0.866 ± 0.023**     |\n| (m=16) RWNN | 0.664 ± 0.027    |     0.860 ± 0.017    |\n| (m=16) RSNN | **0.683 ± 0.027**    |     **0.886 ± 0.025**    |\n\n- **Implementation Details.** In the revision, we will expand Section 4 to include a comprehensive description of the DFS sampling procedure and its integration with the sequence model, based on the pseudocode from Appendix A.2. We will also present the Algorithms in the main text, showing both the random-walk and random-search sampling routines along with clear annotations on how they interface with the positional encodings (from Appendix A.1) and the sequence encoder. We will include a concise runtime and memory complexity comparison of RWNN, CRAWL, and RSNN. The full technical discussion, including extended implementation notes, will remain in Appendices A.1 and A.2 for readers seeking further details. Lastly, our code will also be made publicly available for full reproducibility. \n\n**References**\n\nSaid, A., Bayrak, R., Derr, T., Shabbir, M., Moyer, D., Chang, C., & Koutsoukos, X. (2023). Neurograph: Benchmarks for graph machine learning in brain connectomics. Advances in Neural Information Processing Systems, 36, 6509-6531.\n\nBevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., & Maron, H. (2022). Equivariant subgraph aggregation networks. International Conference on Learning Representations 2022"}, {"review_id": "fF8n5AgTwc", "reviewer": "Reviewer_jLHR", "summary": "This paper introduces Random Search Neural Networks (RSNNs), a novel graph learning framework designed to overcome the expressive limitations of existing Random Walk Neural Networks (RWNNs). The authors argue that under realistic sampling constraints, RWNNs often fail to achieve complete node and edge coverage of a graph, thereby limiting their ability to capture global structure. To address this, RSNNs replace the random walk sampling strategy with a random search procedure, specifically depth-first search (DFS). \n\nThe core contributions of the paper are both theoretical and empirical:\n\n1. Theoretical Analysis: The article theoretically proves that the RSNNs are more expressive and have tighter generalization.\n\n2. Empirical Validation: Through experiments on molecular and protein graph classification benchmarks, RSNNs are shown to consistently and significantly outperform various RWNN baselines.", "questions": "1. For the experiments, the RWNN walk length $I$ was set to |V| to ensure equivalent asymptotic runtimes with DFS. However, RWNNs are often used with much shorter walks [1]. So, RWNN walk length set to |V| may increase time complexity, but brings a slight performance improvement. Could the authors provide a comparison against RWNNs in this more conventional, computationally cheaper setting? This would offer a more direct view of the trade-off between computational cost, coverage, and performance.\n\n2. The article theoretically proves Tighter Learning Guarantees in RSNNs. Why not provide experimental evidence to further confirm this?\n\n3. RWNN has poor expressiveness due to limited coverage, so you compare it with subgraph GNN in Section 3.1. I want to know why the subgraph GNN is not used as the baseline model in the experiment.\n\nReference:\n\n[1] Nikolentzos, Giannis, and Michalis Vazirgiannis. \"Random walk graph neural networks.\" Advances in Neural Information Processing Systems 33 (2020): 16211-16222.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nImpressive Sample Efficiency: The empirical results demonstrate the practical value of RSNNs. The finding that an RSNN with a single search (m=1) can match or outperform the best RWNN with 16 walks (m=16) on several benchmarks is a standout result that underscores the method's efficiency.\n\nStrong Theoretical Foundation: The proof that partially-covered RWNNs are less expressive than subgraph GNNs (Theorem 3.1) provides a motivation for the work. The subsequent theorems establishing the efficient coverage (Lemma 4.1), universal approximation capability (Theorem 4.2), and tighter generalization bounds (Theorem 4.3) of RSNNs provide a solid theoretical underpinning for the proposed method.\n\nWeaknesses:\n\nScalability to Dense Graphs: The primary weakness is the reliance on a full depth-first search. While efficient on the sparse graphs targeted in the paper, the O(|V|+|E|) complexity of DFS would be prohibitive for very large or dense graphs. This limits the immediate applicability of the current RSNN framework to a subset of all possible graph structures.", "was_revised": true, "final_justification": "This paper introduces RSNN, a model designed to improve the ability of GNN representation. The methodology is clearly described, and the experimental results are solid and demonstrate a clear improvement over existing baselines. In the rebuttal stage, the author efficiently addresses my problem.\nWhile some details e.g. theorem statement, technical implementation, could be improved, these make it easier for readers to read.\nOverall, I believe this paper makes a meaningful contribution and could be accepted", "rebuttal": "We appreciate your thoughtful and careful feedback. We are pleased that you found our theoretical foundation strong, providing a solid foundation for RSNNs, and our empirical results on the practical value of RSNNs impressive. Below, we address your specific comments individually.\n\n- **How does RSNN scale to large and dense graphs?** Great question. We ran additional experiments to measure how RSNN scales to **dense** graphs (see experiments below). We don’t evaluate on large graphs because we focus our evaluation on small to medium graphs, where global structure, long-range dependencies, and high expressivity are essential, in comparison to large graphs where locality is more important to capture and as a result message-passing GNNs already work well (e.g., node classification in citation networks). To demonstrate our approach is scalable to **dense** graphs, we have since evaluated RSNN and CRAWL, the strongest RWNN baseline, on two dense graph classification benchmarks from NeuroGraph (Said et al., 2023): a Gender prediction set of 1000 graphs (avg. 1000 nodes, avg. 46000 edges, avg. degree ≈ 46) and an Activity prediction set of 7500 graphs (avg. 400 nodes, avg. 7000 edges, avg. degree ≈ 18), both substantially denser than our molecular and protein datasets. Across all sample lengths $m$, RSNN consistently outperforms CRAWL in accuracy (Table 1 in response to Reviewer k2UB) while remaining comparable to CRAWL runtime. On the Activity dataset, sixteen RSNN searches complete in 0.24 seconds compared to 0.32 seconds for sixteen CRAWL walks; on the denser Gender dataset, sixteen searches take 1.10 seconds versus 1.03 seconds for sixteen walks. These results show that even with DFS cost RSNN achieves comparable runtimes to RWNNs in much denser graphs, underscoring its scalability and broad applicability across a spectrum of graph densities.  \n\n- **Could the authors provide a comparison against RWNNs in a more conventional, computationally cheaper setting?** Yes, we conduct an additional experiment testing different walk lengths $\\ell$ fixing $m=4$ for RWNN on the CLINTOX dataset, measuring performance, average node coverage, and runtime for 50 train epochs. We find that shorter walks indeed yield faster sampling times but also incur lower coverage and consequently lower performance, highlighting the balance between computational efficiency and expressivity. These additional results will be included in the revised manuscript to offer a comprehensive comparison of the tradeoffs between the three factors. \n\nTable 3. Runtime, coverage, and performance as $\\ell$ increases on CLINTOX fixing $m=4$ for RWNN.\n| CLINTOX | $\\ell$=4 | $\\ell$=8 | $\\ell$=16 | $\\ell=26=\\|V_{avg}\\|$ |\n| ------- | ------- | ------- | ------- | ------- |\n|    AUC     |    0.731 ± 0.049     |     0.757 ± 0.065    |     0.798 ± 0.048    |    0.836 ± 0.029     |\n|    Avg. Node Coverage  |     0.398    |     0.533    |    0.668     |     0.749    |\n|    Avg. Runtime (sec)     |     60.268    |     83.238    |     139.939    |     211.601    |\n\n- **Why not provide experimental evidence to test RSNN generalization?** Thank you for this suggestion. We have conducted extensive empirical evaluations on molecular and protein benchmarks ranging from a few thousand to hundreds of thousands of graphs. Across these diverse datasets, RSNN consistently achieves higher test‐set performance than the RWNN baselines, providing strong practical confirmation of the tighter learning bounds established in our analysis. \n\n- **Why not compare to subgraph GNNs?** While we originally focused on RWNNs as our main baselines, you are right; we should also compare to subgraph GNNs. Thus, we have added the Equivariant Subgraph Aggregation Network (ESAN; Bevilacqua et al., 2022) to our experiments. ESAN generates one node‐deleted subgraph per node, applies a standard GNN to each, and aggregates the resulting embeddings via a DeepSets module to form the final graph representation. ESAN indeed outperforms RWNN under minimal coverage (m = 1), but RWNN matches or exceeds ESAN’s accuracy once full coverage is obtained (m = 16) (Table 2 in response to Reviewer k2UB). This empirical result aligns with our theoretical analysis that RWNNs with partial graph coverage are less expressive than subgraph GNNs. RSNN on the other hand, achieves full node coverage and high edge coverage with just a single search, outperforming both RWNN and ESAN even when m=1. We will incorporate ESAN comparisons into the main text to enrich our empirical evaluation. \n\n**References**\n\nSaid, A., Bayrak, R., Derr, T., Shabbir, M., Moyer, D., Chang, C., & Koutsoukos, X. (2023). Neurograph: Benchmarks for graph machine learning in brain connectomics. Advances in Neural Information Processing Systems, 36, 6509-6531.\n\nBevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., & Maron, H. (2022). Equivariant subgraph aggregation networks. International Conference on Learning Representations 2022"}]

Author rebuttal:

Meta-review: This paper suggest a new graph neural network based on graph random walks. The method's novelty is in its ability to achieve full node coverage faster than existing methods. Analysis of the expressive power of the model is provided, as well as strong empirical results. The reviewers were positive about the results in this paper. Initially there were some concerns regarding mathematical terminology and related works, but these concerns were addressed during the rebuttal. I recommend acceptance.
Decision: Accept (poster)