Research map / Graph learning / GNN architectures
Random Search Neural Networks for Efficient and Expressive Graph Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes random search neural networks (RSNNs), which feed random DFS searches (spanning trees guaranteeing full node coverage) into sequence models, achieving logarithmic-sample edge coverage on sparse graphs and outperforming random-walk GNNs with up to 16x fewer samples.
Problem
Random walk neural networks (RWNNs) under realistic sampling budgets fail to cover all nodes and edges, limiting expressivity and sample efficiency on sparse graphs.
Approach
Replace random walks with random DFS searches, whose induced subgraphs are spanning trees guaranteeing full node coverage, so only O(log|V|) searches are needed for full edge coverage in sparse graphs; proves universal approximation and probabilistic isomorphism invariance.
Key results
- At m=1, RSNN reaches 88.1 AUC on CLINTOX vs. best RWNN 71.0 (RWNN-base), and 62.2 ACC on SC CL vs. 53.0 for CRAWL.
- RSNN at m=1 matches or exceeds the best RWNNs at m=16 on molecular benchmarks, consistent with the claimed up to 16x sample efficiency.
- On NeuroGraph-task (dense), RSNN reaches 86.5 accuracy at m=16 vs. 68.3 for CRAWL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace random walks with random DFS searches at m=1 | RWNN · CLINTOX | AUC: 70.0 -> 88.1 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · SIDER | AUC: 64.2 -> 66.2 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · BBBP | AUC: 77.6 -> 87.5 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · TOX21 | AUC: 71.7 -> 79.8 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · SC Class | accuracy: 53.0 -> 62.2 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · SC Family | accuracy: 5.2 -> 13.9 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · EC Subclass | accuracy: 28.7 -> 36.8 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · EC Mechanism | accuracy: 47.0 -> 49.8 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · PCBA-1030 | AUC: 64.2 -> 78.8 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · PCBA-1458 | AUC: 77.0 -> 87.0 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · PCBA-4467 | AUC: 75.6 -> 85.2 | Helped |
| Replace random walks with random DFS searches at m=1 | RWNN · NeuroGraph-task | accuracy: 63.4 -> 58.9 | Hurt |
Surprising findings
- CRAWL at m=1 is worse than RSNN by large margins, and RWNN-base trails GCN/GIN on protein benchmarks at small m.
Limitations
- Tailored to sparse, medium-sized graphs; full-depth DFS can be expensive on large or dense graphs.
- Dense-graph generalization evaluated on only one benchmark (NeuroGraph) and compared only against CRAWL.
Experimental setup
Datasets: MoleculeNet CLINTOX MoleculeNet SIDER MoleculeNet BBBP MoleculeNet TOX21 ProteinShake EC Subclass ProteinShake EC Mechanism ProteinShake SC Class ProteinShake SC Family OGB PCBA-1030 OGB PCBA-1458 OGB PCBA-4467 NeuroGraph-task
Benchmarks: CLINTOX SIDER BBBP TOX21 SC CL SC FAM EC SUB EC MEC PCBA-1030 PCBA-1458 PCBA-4467 NeuroGraph-task
Metrics: AUC accuracy
Baselines: SMILES GCN GIN Graph Transformer Fingerprint RWNN-base RWNN-anon RWNN-mdlr CRAWL
Builds on: random walk neural networks CRAWL minimum-degree local rule walks Weisfeiler-Lehman test
Closest papers by meaning
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.92)
- Non-convolutional graph neural networks. (NeurIPS 2024 · similarity 0.88)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.88)
- From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers (ICML 2025 · similarity 0.86)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.86)
- Towards Scalable and Deep Graph Neural Networks via Noise Masking (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.