# Graph Neural Networks are Dynamic Programmers

arXiv: https://arxiv.org/abs/2203.15544 · HTML: https://mlsanity.com/paper/2203.15544/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [How to transfer algorithmic reasoning knowledge to learn new algorithms?](https://mlsanity.com/paper/2110.14056/) (2021)
- [Neural Algorithmic Reasoners are Implicit Planners](https://mlsanity.com/paper/2110.05442/) (2021)
- [Normalized Attention Without Probability Cage](https://mlsanity.com/paper/2005.09561/) (2020)
- [Persistent Message Passing](https://mlsanity.com/paper/2103.01043/) (2021)
- [Reasoning-Modulated Representations](https://mlsanity.com/paper/2107.08881/) (2021)
- [How Does a Neural Network's Architecture Impact Its Robustness to Noisy Labels?](https://mlsanity.com/paper/2012.12896/) (2020)

## Built on by (most cited first, 30 of 55)

- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [Relational Attention: Generalizing Transformers for Graph-Structured Tasks](https://mlsanity.com/paper/2210.05062/) (2022)
- [Position: Categorical Deep Learning is an Algebraic Theory of All Architectures](https://mlsanity.com/paper/2402.15332/) (2024)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)
- [Neural incomplete factorization: learning preconditioners for the conjugate gradient method](https://mlsanity.com/paper/2305.16368/) (2023)
- [Deep Generative Models for Detector Signature Simulation: A Taxonomic Review](https://mlsanity.com/paper/2312.09597/) (2023)
- [Neural Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [Learnable Commutative Monoids for Graph Neural Networks](https://mlsanity.com/paper/2212.08541/) (2022)
- [Asynchronous Algorithmic Alignment with Cocycles](https://mlsanity.com/paper/2306.15632/) (2023)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)
- [On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods](https://mlsanity.com/paper/2403.04929/) (2024)
- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Latent Space Representations of Neural Algorithmic Reasoners](https://mlsanity.com/paper/2307.08874/) (2023)
- [Parallel Algorithms Align with Neural Execution](https://mlsanity.com/paper/2307.04049/) (2023)
- [E(2)-Equivariant Graph Planning for Navigation](https://mlsanity.com/paper/2309.13043/) (2023)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Deep Equilibrium Algorithmic Reasoning](https://mlsanity.com/paper/2410.15059/) (2024)
- [Equivariant Action Sampling for Reinforcement Learning and Planning](https://mlsanity.com/paper/2412.12237/) (2024)
- [Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encoding](https://mlsanity.com/paper/2501.00712/) (2025)
- [Approximating CKY with Transformers](https://mlsanity.com/paper/2305.02386/) (2023)
- [A Category-theoretical Meta-analysis of Definitions of Disentanglement](https://mlsanity.com/paper/2305.06886/) (2023)

## 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.