mlsanityData to 14 Oct 2026

Neural Execution of Graph Algorithms

arXiv 1910.10593 ↗First posted 23 Oct 2019stat.ML cs.AI cs.DScited by 121

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) are a powerful representational tool for solving problems on graph-structured inputs. In almost all cases so far, however, they have been applied to directly recovering a final solution from raw inputs, without explicit guidance on how to structure their problem-solving. Here, instead, we focus on learning in the space of algorithms: we train several state-of-the-art GNN architectures to imitate individual steps of classical graph algorithms, parallel (breadth-first search, Bellman-Ford) as well as sequential (Prim's algorithm). As graph algorithms usually rely on making discrete decisions within neighbourhoods, we hypothesise that maximisation-based message passing neural networks are best-suited for such objectives, and validate this claim empirically. We also demonstrate how learning in the space of algorithms can yield new opportunities for positive transfer between tasks---showing how learning a shortest-path algorithm can be substantially improved when simultaneously learning a reachability algorithm.

Key facts. Cited by 121 papers in the map (data through 14 Oct 2026). First posted on arXiv 23 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 27; 2022: 25; 2023: 22; 2024: 21; 2025: 16; 2026: 10.

121 papers.

Sort:

By area:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  2. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  4. 2021Identity-aware Graph Neural Networkscited by 198
  5. 2021PonderNet: Learning to Pondercited by 168
  6. 2022Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphscited by 144
  7. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  8. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 106
  9. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  10. 2021Neural Algorithmic Reasoningcited by 94
  11. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 84
  12. 2021OOD-GNN: Out-of-Distribution Generalized Graph Neural Networkcited by 78
38 more
  1. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  2. 2021Graph Neural Networks Inspired by Classical Iterative Algorithmscited by 60
  3. 2022A Generalist Neural Algorithmic Learnercited by 59
  4. 2022Graph Neural Networks are Dynamic Programmerscited by 55
  5. 2022Multimodal learning with graphscited by 54
  6. 2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
  7. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 49
  8. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  9. 2025Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokenscited by 41
  10. 2021Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limitscited by 38
  11. 2021Latent Execution for Neural Program Synthesiscited by 35
  12. 2023Code Execution with Pre-trained Language Modelscited by 34
  13. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 31
  14. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 30
  15. 2024Simulation of Graph Algorithms with Looped Transformerscited by 30
  16. 2022Backpropagation through Combinatorial Algorithms: Identity with Projection Workscited by 29
  17. 2023Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalizationcited by 29
  18. 2024The CLRS-Text Algorithmic Reasoning Language Benchmarkcited by 28
  19. 2021Spatial Aggregation and Temporal Convolution Networks for Real-time Krigingcited by 27
  20. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24
  21. 2023Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problemscited by 24
  22. 2021How to transfer algorithmic reasoning knowledge to learn new algorithms?cited by 22
  23. 2021Neural Algorithmic Reasoners are Implicit Plannerscited by 21
  24. 2023Dual Algorithmic Reasoningcited by 21
  25. 2023Neural Algorithmic Reasoning for Combinatorial Optimisationcited by 19
  26. 2021Large-scale graph representation learning with very deep GNNs and self-supervisioncited by 18
  27. 2022Neural Approximation of Graph Topological Featurescited by 17
  28. 2022Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networkscited by 17
  29. 2023Neural Algorithmic Reasoning Without Intermediate Supervisioncited by 17
  30. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  31. 2021Persistent Message Passingcited by 13
  32. 2021Reasoning-Modulated Representationscited by 13
  33. 2021Implicit vs Unfolded Graph Neural Networkscited by 13
  34. 2022Learnable Commutative Monoids for Graph Neural Networkscited by 13
  35. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  36. 2023Asynchronous Algorithmic Alignment with Cocyclescited by 13
  37. 2024Transformers meet Neural Algorithmic Reasonerscited by 13
  38. 2021Algorithmic Concept-based Explainable Reasoningcited by 12

50 most cited of 121 All 121 (JSON)