Abstract
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 \textsc{GraphPDHG} for solving general graph saddle-point problems. Theoretically, we show that \textsc{GraphPDHG} 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.
Keywords
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Chen, S., He, J., Clougherty, C., Mishne, G., & Holtz, C. (2026). Neural Algorithmic Reasoning for Graph Saddle Point Problems. https://omanscience.com/en/articles/neural-algorithmic-reasoning-for-graph-saddle-point-problems
MLA 9
Chen, Samantha, et al. "Neural Algorithmic Reasoning for Graph Saddle Point Problems." https://omanscience.com/en/articles/neural-algorithmic-reasoning-for-graph-saddle-point-problems.
Chicago (author–date)
Chen, Samantha, Jesse He, Coleman Clougherty, Gal Mishne, and Chester Holtz. 2026. "Neural Algorithmic Reasoning for Graph Saddle Point Problems." https://omanscience.com/en/articles/neural-algorithmic-reasoning-for-graph-saddle-point-problems.
Harvard
Chen, S., He, J., Clougherty, C., Mishne, G. and Holtz, C. (2026) 'Neural Algorithmic Reasoning for Graph Saddle Point Problems', Available at: https://omanscience.com/en/articles/neural-algorithmic-reasoning-for-graph-saddle-point-problems.
Vancouver
Chen S, He J, Clougherty C, Mishne G, Holtz C. Neural Algorithmic Reasoning for Graph Saddle Point Problems. https://omanscience.com/en/articles/neural-algorithmic-reasoning-for-graph-saddle-point-problems
IEEE
S. Chen, J. He, C. Clougherty, G. Mishne, and C. Holtz, "Neural Algorithmic Reasoning for Graph Saddle Point Problems," https://omanscience.com/en/articles/neural-algorithmic-reasoning-for-graph-saddle-point-problems.