Research map / Graph learning / GNN architectures
Non-convolutional graph neural networks.
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 RUM, a convolution-free GNN that samples random walks per node and feeds semantic features and anonymous-experiment topology indices through GRUs, claiming expressiveness beyond WL, relief from over-smoothing/over-squashing, and fast GPU speed.
Problem
Convolution-based GNNs suffer from limited expressiveness (bounded by the WL test), over-smoothing, over-squashing, and need specialized sparse kernels for efficient computation.
Approach
Replace message passing with per-node random walks terminating at each node; each walk is encoded by a GRU over its node features (semantic) and its anonymous-experiment index sequence (topological), and node embeddings are Monte Carlo averages over walks, with no convolution operator.
Key results
- On Cora, CiteSeer, PubMed RUM reports 84.1, 75.5, 82.2 accuracy versus GCN 81.5, 70.3, 79.0 (as reported in its table).
- On CSL isomorphism test RUM reaches 93.2% accuracy while GCN, GAT, GIN, GraphSAGE stay at 10% (chance).
- On the Computer co-purchase dataset RUM underperforms (77.8 vs GCN 82.6), attributed to high average degree (18.36).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RUM instead of the strongest listed baseline | Node classification · Cora | accuracy: 85.5_{\pm 0.5} -> 84.1_{\pm 0.9} | Hurt |
| use RUM instead of the strongest listed baseline | Node classification · CiteSeer | accuracy: 74.2_{\pm 1.7} -> 75.5_{\pm 0.5} | Helped |
| use RUM instead of the strongest listed baseline | Node classification · PubMed | accuracy: 80.3_{\pm 0.4} -> 82.2_{\pm 0.2} | Helped |
| use RUM instead of the strongest listed baseline | Node classification · Computer | accuracy: 83.5_{\pm 2.2} -> 77.8_{\pm 2.3} | Hurt |
| use RUM instead of the strongest listed baseline | Node classification · Photo | accuracy: 91.2_{\pm 2.3} -> 92.7_{\pm 0.1} | Helped |
| use RUM instead of the strongest listed baseline | Graph classification · IMDB-B | accuracy: 75.1_{\pm 5.1} -> 81.1_{\pm 4.5} | Helped |
| use RUM instead of the strongest listed baseline | Graph classification · MUTAG | accuracy: 93.6_{\pm 8.6} -> 91.0_{\pm 7.1} | Hurt |
| use RUM instead of the strongest listed baseline | Graph classification · PTC | accuracy: 68.2_{\pm 7.2} -> 69.8_{\pm 6.3} | Helped |
| use RUM instead of the strongest listed baseline | Node classification · Texas | accuracy: 77.6_{\pm 3.8} -> 80.0_{\pm 7.0} | Helped |
| add topological walk representation ωu (ablation) | RUM · Cora | accuracy: 82.2 \pm 1.0 -> 84.1_{\pm 0.9} | Helped |
| add semantic walk representation ωx (ablation) | RUM · Cora | accuracy: 35.0 \pm 1.0 -> 84.1_{\pm 0.9} | Helped |
| add self-supervision loss Lself (ablation) | RUM · Cora | accuracy: 78.4 \pm 0.1 -> 84.1_{\pm 0.9} | Helped |
Surprising findings
- On the dense Computer dataset RUM is outperformed even by GCN and GAT, which the authors attribute to high-variance embeddings for high-degree graphs.
Limitations
- Performs poorly on very dense graphs (average degree above 15) such as Computer, due to high variance of node representations.
- Only unbiased random walks and undirected graphs are considered; 2-cycles (tottering) are not excluded.
- Theoretical claims rely on assumptions of injectivity and universality of the component networks, and the main expressiveness theorem depends on the Reconstruction Conjecture.
Experimental setup
Datasets: Cora CiteSeer PubMed Coauthor CS Computer Photo TU datasets MoleculeNet OGB-PRODUCTS CSL Texas Wisconsin
Benchmarks: Cora CiteSeer PubMed Coauthor CS Computer Photo Texas Wisconsin Cornell IMDB-B MUTAG PROTEINS
Metrics: accuracy RMSE Dirichlet energy inference throughput memory
Baselines: GCN GAT GraphSAGE MoNet GCNII PairNorm GraphCON RAW-GNN CRaWl AgentNet GIN GSN
Builds on: GCN GAT Weisfeiler-Lehman isomorphism test anonymous walk embeddings GRU
Closest papers by meaning
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.89)
- Random Search Neural Networks for Efficient and Expressive Graph Learning (NeurIPS 2025 · similarity 0.88)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.88)
- Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention (ICLR 2025 · similarity 0.87)
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.87)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.87)
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.