Random Search Neural Networks for Efficient and Expressive Graph Learning

AI summary

Overview

• Research area: Graph representation learning — specifically random-walk-based neural networks (RWNNs) and their expressive power under realistic sampling budgets.
• Technical level: Advanced (the paper combines expressivity theory, coverage-time analysis, universal approximation, and randomized-invariance arguments with empirical benchmarks).
• Scope: The paper characterizes when random-walk neural networks fail to see a whole graph, proposes random search neural networks (RSNNs) built on random depth-first searches whose induced subgraphs are spanning trees, and proves efficient coverage, universal approximation, and probabilistic isomorphism invariance while benchmarking on molecular and protein graphs.

What This Paper Is About

Random walk neural networks represent a graph as a collection of sampled node sequences processed by a sequence model. Under realistic constraints — where walks are much shorter than the graph's cover time — those walks only visit part of the graph, so the model cannot see global structure even in small graphs. The paper diagnoses this limitation theoretically and introduces random search neural networks (RSNNs), which sample random depth-first searches instead of walks so that every sampled sequence covers every node, and shows that a logarithmic number of searches suffices for full edge coverage in sparse graphs.

Key Contributions

1. Characterizing RWNN expressive limitations. The authors prove that RWNNs with access to the complete multiset of walks up to the edge cover time are exactly as expressive as MPNNs (Theorem 3.1), and that under partial node/edge coverage RWNNs are strictly less expressive than MPNNs (Corollary 3.2).
2. A new model: random search neural networks (RSNNs). RSNNs operate on random depth-first searches, whose induced subgraphs are spanning trees; each search guarantees full node coverage by construction, reducing the task to achieving edge coverage across the union of induced trees.
3. Efficient coverage, universal approximation, and isomorphism invariance. In sparse graphs with bounded maximum degree, O(log|V|) searches suffice for full edge coverage with high probability (Lemma 4.1), yielding universal approximation (Theorem 4.2) and probabilistic invariance to graph isomorphism, so the expectation Φ(G) = E[f_RSNN(G)] is an isomorphism-invariant graph function (Theorem 4.3).
4. Extensive empirical analysis. RSNNs are evaluated against standard molecular baselines, RWNN variants, and other models on molecular, protein, large-scale molecular, and dense brain graph benchmarks.

Main Findings

• Logarithmic sampling beats linear sampling. In sparse graphs, RSNNs need only O(log|V|) searches to achieve full edge coverage, compared to the O(|V|) walks required by RWNNs (assuming walk lengths scale with graph size). The abstract states RSNNs achieve comparable or superior performance with up to 16× fewer sampled sequences.
• Full coverage is necessary for expressivity. Random walk cover time is O(|V||E|) in general and O(|V|²) for sparse graphs where |E| = Θ(|V|); MDLR walks also achieve O(|V|²), which is optimal among first-order walks. Because these are quadratic in graph size, guaranteeing full coverage by walks is impractical even for small and medium graphs.
• Partial coverage strictly weakens RWNNs. With incomplete node/edge coverage, there exist non-isomorphic graphs G and H that MPNNs distinguish but partial-coverage RWNNs do not — i.e., f_RWNN^PC ≺ f_MPNN.
• Explicit sampling bound. Lemma 4.1 states that for m independent searches with induced spanning trees T₁, …, T_m on a connected graph with |E| ≤ C|V| and bounded maximum degree d_max, the union contains every edge with probability at least 1 − δ when m ≥ ln(C|V|/δ) / ln(d_max/(d_max−1)).
• Universal approximation holds. Theorem 4.2 states that for any continuous graph-level function f on sparse graphs with |E| = O(|V|) and maximum degree at most d_max, an RSNN configuration exists with |f_RSNN(G) − f(G)| < ε for all G in the class, with probability at least 1 − δ.
• Invariance in distribution and in expectation. The randomized DFS procedure is probabilistically invariant to graph isomorphisms, so RSNNs satisfy f_RSNN(G) =ᵈ f_RSNN(H) and their averaged predictor is invariant. Corollary 4.4 shows that with a single sampled search per forward pass (m = 1), the mini-batch gradient is an unbiased estimator of the gradient of the invariant objective, and SGD converges almost surely to an optimizer of that objective under standard conditions.
• Runtime comparison. A single DFS costs at most O(|V|) on a sparse graph, so m searches cost O(m|V|); RWNNs sampling m walks of length ℓ cost O(mℓ). When ℓ ≪ |V|, walk sampling is faster, but short walks miss global structure.
• RSNNs outperform on molecular and protein benchmarks at low sampling budgets. At m = 1, RSNN achieves median (min, max) AUC of 88.1 (84.9, 91.5) on CLINTOX, 66.2 (63.0, 72.4) on SIDER, 87.5 (80.3, 89.9) on BBBP, and 79.8 (77.2, 83.4) on TOX21, versus RWNN-base at 71.0, 62.5, 74.1, and 71.5 respectively. On protein benchmarks at m = 1, RSNN reaches 62.2 (60.0, 65.6) on SC CL, 13.9 (10.6, 14.9) on SC FAM, 36.8 (36.5, 38.3) on EC SUB, and 49.8 (48.2, 50.8) on EC MEC, versus CRAWL at 53.0, 5.2, 28.7, and 47.0.
• At m = 16, RSNN reaches 88.5 on CLINTOX, 67.1 on SIDER, 89.4 on BBBP, 82.2 on TOX21, 77.0 on SC CL, 19.0 on SC FAM, 50.0 on EC SUB, and 59.5 on EC MEC. The paper reports that at m = 16 RWNNs approach RSNN performance on molecular benchmarks, while RSNNs outperform RWNNs across all values of m on protein benchmarks. The paper also states that at m = 16 RSNNs match or exceed Fingerprint models (Fingerprint: 66.5 CLINTOX, 70.4 SIDER, 86.2 BBBP, 79.1 TOX21; Fingerprint is not applicable to protein graphs).
• Standard baselines are also outperformed. GCN, GIN, GT, SMILES, and Fingerprint results are reported alongside RSNN; SMILES, Fingerprint, and GT are marked as not applicable to protein graphs, and GT is also marked as omitted where training exceeded 24 hours.

Methodology in Plain English

The authors first ask a theoretical question: what can a random walk network actually see? They borrow the walk-based color-refinement idea of Weisfeiler–Lehman to show that a walk network fed every walk up to the cover time sees exactly what a message-passing network sees — but that any walk network fed only a partial sample sees strictly less. That motivates changing the sampling object entirely.

Instead of sampling node sequences by walking step by step (where the sequence can wander and miss parts of the graph), RSNNs sample a random depth-first search. A DFS visits every node, so each individual search gives full node coverage, and the subgraph it induces is a spanning tree rather than an arbitrary subgraph. The coverage question then reduces to whether the union of a few spanning trees includes every edge. The authors prove a bound showing that logarithmically many searches suffice on sparse graphs of bounded degree.

The sampled searches are encoded with the same recording function used by RWNNs, including positional encodings that mark discontinuities in the sequence (where a DFS backtracks across a gap rather than along an edge), then processed by a sequence model such as a GRU, LSTM, or transformer, and finally aggregated across searches into node representations. Because the DFS procedure is randomized but symmetric with respect to graph isomorphisms, the resulting predictor is invariant in distribution, and its expectation is an invariant graph function — which the authors argue can be learned even with one search per forward pass.

Empirically, all models are given the same number of samples m, and RWNN walk lengths are set to ℓ = |V| so that asymptotic runtimes match. Performance is reported as the median (min, max) over five random 60/20/20 splits, using AUC on molecular benchmarks and accuracy on protein benchmarks. Training uses up to 24 hours on a machine with 8 × NVIDIA GeForce GTX 1080 Ti GPUs, and models that do not converge in that window are omitted. Datasets span small molecules (CLINTOX, SIDER, BBBP, TOX21, with average |V| between 18.6 and 33.6), proteins (SC CL and SC FAM at average |V| = 217.5 and average |E| = 593.8, EC SUB at 304.9/843.4, EC MEC at 306.4/846.9), large-scale molecular benchmarks (PCBA-1030, PCBA-1458, PCBA-4467), and a dense brain graph benchmark (NeuroGraph-task, predicting one of seven mental states).

Why This Matters

Impact on research. The paper bridges two model families that had been analyzed separately — random walk networks and message-passing networks — by showing they have equal distinguishing power under full coverage and a strict gap under partial coverage. It also reframes graph sampling: rather than asking how long a walk must be to see everything, it asks how few spanning structures can cover all edges.

Real-world applications.

• Molecular property and toxicity prediction: the CLINTOX, SIDER, TOX21, and BBBP benchmarks correspond to clinical toxicity and adverse reaction tasks.
• Protein function and structure classification: the EC Subclass, EC Mechanism, SC Class, and SC Family tasks cover enzyme classification and structural classification.
• Large-scale chemical screening: the PCBA benchmarks (PCBA-1030, PCBA-1458, PCBA-4467) involve hundreds of thousands of graphs.
• Neuroimaging: NeuroGraph-task predicts mental states such as emotion processing and language from dense brain graphs.

Industry relevance. Drug discovery and molecular design pipelines depend on accurate graph-level property prediction from limited labelled data, and protein engineering depends on function annotation at scale. A method that extracts comparable or better performance from far fewer sampled sequences reduces the compute and time cost of running sequence models over graph data, which matters when screening large compound or protein libraries. The released code at https://github.com/MLD3/RandomSearchNNs supports adoption.

Future Directions

• Dense graphs. The theory and the coverage guarantee are stated for sparse graphs with bounded degree; the paper explicitly includes RQ3 asking how RSNNs perform on dense graphs where full edge coverage is computationally expensive, and the provided excerpt does not report those results.
• Beyond the assumption that walk lengths scale with graph size. The O(log|V|) versus O(|V|) comparison assumes walk lengths scale with graph size; behavior under other length regimes is left open.
• Sequence-model dependence. Universal approximation is conditional on pairing RSNNs with universal sequence models such as transformers or LSTMs; how much of the guarantee survives with weaker sequence models is not settled in the content presented.
• Sampling cost trade-offs. The paper notes that when ℓ ≪ |V|, random walk sampling is cheaper per sample than DFS extraction, leaving open how to adaptively choose between searches and walks based on graph size and degree.

Target Audience

Researchers and graduate students in graph machine learning, graph neural networks, and geometric deep learning who care about expressivity theory (Weisfeiler–Lehman, MPNN limitations, universal approximation) and about sampling strategies for graph representation learning. It is also relevant to applied researchers and practitioners in computational chemistry, drug discovery, protein science, and neuroimaging who work with sparse graph benchmarks and care about how many sampled sequences a model needs to perform well. A background in graph theory, random walks, and basic measure-theoretic probability is required to follow the proofs in full.

Authors’ 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.