# Dual Algorithmic Reasoning

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 36 references that are in the map.
- First posted on arXiv 9 Feb 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [End-to-End Differentiable Proving](https://mlsanity.com/paper/1705.11040/) (2017)
- [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)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [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)
- [Neural Bipartite Matching](https://mlsanity.com/paper/2005.11304/) (2020)
- [Reasoning-Modulated Representations](https://mlsanity.com/paper/2107.08881/) (2021)

## Built on by (most cited first, 21 of 21)

- [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 Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [Transformers meet Neural Algorithmic Reasoners](https://mlsanity.com/paper/2406.09308/) (2024)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods](https://mlsanity.com/paper/2403.04929/) (2024)
- [Recursive Algorithmic Reasoning](https://mlsanity.com/paper/2307.00337/) (2023)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [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)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Are Large-Language Models Graph Algorithmic Reasoners?](https://mlsanity.com/paper/2410.22597/) (2024)
- [Open-Book Neural Algorithmic Reasoning](https://mlsanity.com/paper/2501.00072/) (2024)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [GRASP: Accelerating Shortest Path Attacks via Graph Attention](https://mlsanity.com/paper/2310.07980/) (2023)
- [A Context-Enhanced Framework for Sequential Graph Reasoning](https://mlsanity.com/paper/2412.09056/) (2024)
- [Leveraging Classical Algorithms for Graph Neural Networks](https://mlsanity.com/paper/2510.21574/) (2025)
- [UltRAG: a Universal Simple Scalable Recipe for Knowledge Graph RAG](https://mlsanity.com/paper/2603.28773/) (2026)
- [Richer Representations for Neural Algorithmic Reasoning via Auxiliary Reconstruction](https://mlsanity.com/paper/2606.00559/) (2026)

## Abstract (arXiv)

Neural Algorithmic Reasoning is an emerging area of machine learning which seeks to infuse algorithmic computation in neural networks, typically by training neural models to approximate steps of classical algorithms. In this context, much of the current work has focused on learning reachability and shortest path graph algorithms, showing that joint learning on similar algorithms is beneficial for generalisation. However, when targeting more complex problems, such similar algorithms become more difficult to find. Here, we propose to learn algorithms by exploiting duality of the underlying algorithmic problem. Many algorithms solve optimisation problems. We demonstrate that simultaneously learning the dual definition of these optimisation problems in algorithmic learning allows for better learning and qualitatively better solutions. Specifically, we exploit the max-flow min-cut theorem to simultaneously learn these two algorithms over synthetically generated graphs, demonstrating the effectiveness of the proposed approach. We then validate the real-world utility of our dual algorithmic reasoner by deploying it on a challenging brain vessel classification task, which likely depends on the vessels' flow properties. We demonstrate a clear performance gain when using our model within such a context, and empirically show that learning the max-flow and min-cut algorithms together is critical for achieving such a result.