First exact learnability result: GNNs can execute graph algorithms like BFS and Bellman–Ford
kfountou · x · 2026-09-03
A new paper, "Learning to Execute Graph Algorithms Exactly with Graph Neural Networks," extends the neural algorithmic reasoning program with the first positive exact learnability result: assuming bounded degree and finite precision, GNNs trained with gradient descent can exactly execute graph algorithms in the LOCAL model, including flooding, BFS, DFS and Bellman–Ford. Training uses only local information.
More from Research
- CBAI opens Fall AI Safety fellowship: $15k stipend, 10 weeks in Boston — benno_krojer · 2026-09-03
- What 12 million empirical research results can teach us — RexDouglass · 2026-09-03
- GamowLabs to launch RareBench challenge: can you tell synthetic genomes from real ones? — danielmckinn0n · 2026-09-03
- NEJM: Single-Dose In-Vivo B-Cell Depletion Helps All 16 Refractory Autoimmune Patients — EricTopol · 2026-09-03
- Multi-Teacher On-Policy Distillation emerges as 2026 post-training paradigm used in frontier models — cwolferesearch · 2026-09-03
- Protein folding models have always used recycling — effectively recurrent depth with stop grad — amyxlu · 2026-09-03