mlsanityData to 7 Oct 2026

Graph Neural Networks are Dynamic Programmers

arXiv 2203.15544 ↗First posted 29 Mar 2022cs.LG cs.AI cs.DScited by 55

Not on the map. Why?

Abstract (arXiv)

Recent advances in neural algorithmic reasoning with graph neural networks (GNNs) are propped up by the notion of algorithmic alignment. Broadly, a neural network will be better at learning to execute a reasoning task (in terms of sample complexity) if its individual components align well with the target algorithm. Specifically, GNNs are claimed to align with dynamic programming (DP), a general problem-solving strategy which expresses many polynomial-time algorithms. However, has this alignment truly been demonstrated and theoretically quantified? Here we show, using methods from category theory and abstract algebra, that there exists an intricate connection between GNNs and DP, going well beyond the initial observations over individual algorithms such as Bellman-Ford. Exposing this connection, we easily verify several prior findings in the literature, produce better-grounded GNN architectures for edge-centric tasks, and demonstrate empirical results on the CLRS algorithmic reasoning benchmark. We hope our exposition will serve as a foundation for building stronger algorithmically aligned GNNs.

Key facts. Cited by 55 papers in the map (data through 7 Oct 2026). Builds on 22 of its 50 references that are in the map. First posted on arXiv 29 Mar 2022.

Builds on

22 of 50 references.

References · 22

  1. 2017Graph Attention Networkscited by 8,854
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  6. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  7. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  8. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
  9. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  10. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  11. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  12. 2019What Can Neural Networks Reason About?cited by 155
10 more
  1. 2019Neural Execution of Graph Algorithmscited by 118
  2. 2021Neural Algorithmic Reasoningcited by 92
  3. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  4. 2020Pointer Graph Networkscited by 52
  5. 2021How to transfer algorithmic reasoning knowledge to learn new algorithms?cited by 22
  6. 2021Neural Algorithmic Reasoners are Implicit Plannerscited by 21
  7. 2020Normalized Attention Without Probability Cagecited by 19
  8. 2021Persistent Message Passingcited by 13
  9. 2021Reasoning-Modulated Representationscited by 13
  10. 2020How Does a Neural Network's Architecture Impact Its Robustness to Noisy Labels?cited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 17; 2024: 18; 2025: 7; 2026: 6.

55 papers.

Sort:

By area:

  1. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  2. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  3. 2022A Generalist Neural Algorithmic Learnercited by 58
  4. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 42
  5. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  6. 2024Position: Categorical Deep Learning is an Algebraic Theory of All Architecturescited by 32
  7. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 30
  8. 2024Simulation of Graph Algorithms with Looped Transformerscited by 29
  9. 2023Neural Algorithmic Reasoning for Combinatorial Optimisationcited by 19
  10. 2023Neural incomplete factorization: learning preconditioners for the conjugate gradient methodcited by 18
  11. 2023Deep Generative Models for Detector Signature Simulation: A Taxonomic Reviewcited by 18
  12. 2023Neural Algorithmic Reasoning Without Intermediate Supervisioncited by 16
38 more
  1. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  2. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  3. 2022Learnable Commutative Monoids for Graph Neural Networkscited by 13
  4. 2023Asynchronous Algorithmic Alignment with Cocyclescited by 13
  5. 2023SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoningcited by 11
  6. 2024On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methodscited by 10
  7. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 9
  8. 2024Discrete Neural Algorithmic Reasoningcited by 8
  9. 2024Benchmarking ChatGPT on Algorithmic Reasoningcited by 8
  10. 2023Parallel Algorithms Align with Neural Executioncited by 6
  11. 2023Latent Space Representations of Neural Algorithmic Reasonerscited by 6
  12. 2023E(2)-Equivariant Graph Planning for Navigationcited by 6
  13. 2024Recurrent Aggregators in Neural Algorithmic Reasoningcited by 6
  14. 2024Deep Equilibrium Algorithmic Reasoningcited by 4
  15. 2024Equivariant Action Sampling for Reinforcement Learning and Planningcited by 4
  16. 2025Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encodingcited by 4
  17. 2023Approximating CKY with Transformerscited by 3
  18. 2023A Category-theoretical Meta-analysis of Definitions of Disentanglementcited by 3
  19. 2023Enriching Disentanglement: From Logical Definitions to Quantitative Metricscited by 2
  20. 2023Triplet Edge Attention for Algorithmic Reasoningcited by 2
  21. 2024NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithmscited by 2
  22. 2024Machines and Mathematical Mutations: Using GNNs to Characterize Quiver Mutation Classescited by 2
  23. 2024Open-Book Neural Algorithmic Reasoningcited by 2
  24. 2022Directed Acyclic Graph Factorization Machines for CTR Prediction via Knowledge Distillationcited by 1
  25. 2023Can Euclidean Symmetry be Leveraged in Reinforcement Learning and Planning?cited by 1
  26. 2023Using Enriched Category Theory to Construct the Nearest Neighbour Classification Algorithmcited by 1
  27. 2024The Deep Equilibrium Algorithmic Reasonercited by 1
  28. 2024The Topos of Transformer Networkscited by 1
  29. 2024Network Interdiction Goes Neuralcited by 1
  30. 2026FloydNet: A Learning Paradigm for Global Relational Reasoningcited by 1
  31. 2023On the Equivalence of Graph Convolution and Mixupcited by 0
  32. 2024Harmonizing Human Insights and AI Precision: Hand in Hand for Advancing Knowledge Graph Taskcited by 0
  33. 2024Algorithm-Informed Graph Neural Networks for Leakage Detection and Localization in Water Distribution Networkscited by 0
  34. 2025Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphscited by 0
  35. 2025Learning Repetition-Invariant Representations for Polymer Informaticscited by 0
  36. 2025Automated discovery of finite volume schemes using Graph Neural Networkscited by 0
  37. 2025KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problemscited by 0
  38. 2025Disentangling Hyperedges through the Lens of Category Theorycited by 0

50 most cited of 55 All 55 (JSON)