# Neural Algorithmic Reasoning for Graph Saddle Point Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 70 references that are in the map.
- First posted on arXiv 5 Oct 2026.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [The Why and How of Convex Clustering](https://mlsanity.com/paper/2507.09077/) (2025)
- [Resistance Distance and Linearized Optimal Transport on Graphs](https://mlsanity.com/paper/2404.15261/) (2024)
- [Robust Graph-Based Semi-Supervised Learning via p-Conductances](https://mlsanity.com/paper/2502.08873/) (2025)

## Abstract (arXiv)

Neural algorithmic reasoning, or aligning a neural network with an algorithmic paradigm, has emerged as an approach to solving polynomial-time-solvable and computationally harder combinatorial optimization problems. We propose a new message-passing framework based on the Chambolle-Pock Primal--Dual Hybrid Gradient (PDHG) method called textscGraphPDHG for solving general graph saddle-point problems. Theoretically, we show that textscGraphPDHG can efficiently solve a family of graph saddle-point problems by simulating PDHG. We also show that our network can learn an accelerated PDHG algorithm. Experimentally, we support our results on accelerated PDHG by evaluating the performance of our model as a learned warm start for second-order optimization techniques (SSNAL). We also show that alignment with PDHG leads to stronger size generalization than non-aligned graph neural network (GNN) baselines. Overall, we propose a novel architecture for solving a general family of optimization problems on graphs.