Random Search Neural Networks for Efficient and Expressive Graph Learning

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.

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

Table 1. Mean and standard deviation of CRAWL and RSNN performance on dense NeuroGraph datasets.

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

Table 2. Mean and standard deviation of RWNN, RSNN, ESAN performance on SIDER and BBBP MoleculeNet datasets.

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

References

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

Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., & Maron, H. (2022). Equivariant subgraph aggregation networks. International Conference on Learning Representations 2022

Thanks for your review. Could you please respond to the author's rebuttal as soon as possible?

Thanks AC

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.

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

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

Table 3. Runtime, coverage, and performance as $\ell$ increases on CLINTOX fixing $m=4$ for RWNN.

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

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

References

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

Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., & Maron, H. (2022). Equivariant subgraph aggregation networks. International Conference on Learning Representations 2022

Thank you for your positive feedback! Your suggestions have significantly improved the quality of our work. We will be sure to incorporate each of them in the revised manuscript.

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.

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

Thank you for your positive and constructive feedback and for increasing your score! Your suggestions have greatly improved our work, and we will incorporate all of them in the revised manuscript.

We appreciate your detailed and thoughtful feedback and comments. Below, we address your specific comments individually.

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

References

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

Keriven, N., & Peyré, G. (2019). Universal invariant and equivariant graph neural networks. Advances in neural information processing systems, 32.

Thanks for your review. Could you please respond to the author's rebuttal as soon as possible?

Thanks AC