Efficient and Expressive Graph Learning via Random Search Neural Networks
Michael Ito, Danai Koutra, Jenna Wiens
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 graph structure even in small graphs due to 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 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 expressive sequence models, RSNNs are universal approximators and offer stronger generalization. Empirically, RSNNs consistently outperform RWNNs on sparse 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 methods, offering an efficient and expressive framework for learning on sparse graphs.