# Random Search Neural Networks for Efficient and Expressive Graph Learning

arXiv: https://arxiv.org/abs/2510.22520 · HTML: https://mlsanity.com/paper/2510.22520/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 26 Oct 2025.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs](https://mlsanity.com/paper/1811.01900/) (2018)
- [Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing](https://mlsanity.com/paper/2102.08786/) (2021)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Towards Principled Graph Transformers](https://mlsanity.com/paper/2401.10119/) (2024)
- [Non-convolutional Graph Neural Networks](https://mlsanity.com/paper/2408.00165/) (2024)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Aligning Transformers with Weisfeiler-Leman](https://mlsanity.com/paper/2406.03148/) (2024)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)

## Built on by (most cited first, 1 of 1)

- [When and How to Canonize: A Generalization Perspective](https://mlsanity.com/paper/2605.11008/) (2026)

## Abstract (arXiv)

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