Research map / Learning theory and algorithms / Combinatorial and search optimization
Which Algorithms Can Graph Neural Networks Learn?
Solveig Wittig, Antonis Vasileiou, Robert R Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| individualize the root node (1-iWL MPNN instead of standard 1-WL MPNN) (ablation) | min-aggregation MPNN for SSSP · SSSP, ER (1024 nodes) | test score (lower is better): 0.9645 -> 0.0038 | Improved |
| individualize the root node (1-iWL MPNN instead of standard 1-WL MPNN) (ablation) | min-aggregation MPNN for SSSP · SSSP, General (64 nodes) | test score (lower is better): 0.8393 -> 0.0032 | Improved |
| use proposed regularizer instead of plain l1 (ablation) | min-aggregation MPNN for SSSP · SSSP, General (64 nodes) | test score (lower is better): 0.0061 -> 0.0032 | Improved |
| use proposed regularizer instead of l2 (ablation) | min-aggregation MPNN for SSSP · SSSP, General (1024 nodes) | test score (lower is better): 0.0369 -> 0.0033 | Improved |
| increase test graph size from 64 to 1024 nodes | 1-iWL MPNN trained on path graphs · SSSP, ER-ConstDeg | test score (lower is better): 0.0035 -> 0.0030 | No clear effect |
| unbounded average degree (ER) instead of bounded degree (ER-ConstDeg) | 1-iWL MPNN · SSSP test sets | test score (lower is better): 0.0035 -> 0.0034 | No clear effect |
Closest papers by meaning
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.88)
- Deep Equilibrium Algorithmic Reasoning (NeurIPS 2024 · similarity 0.88)
- Simulation of Graph Algorithms with Looped Transformers (ICML 2024 · similarity 0.88)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.87)
- Primal-Dual Neural Algorithmic Reasoning (ICML 2025 · similarity 0.87)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · 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.
