arXiv：cs.LG· Samantha Chen, Jesse He, Coleman Clougherty, Gal Mishne, Chester Holtz·· 4 小时前AI 评分34
GraphPDHG：面向图鞍点问题的神经算法推理框架
Neural Algorithmic Reasoning for Graph Saddle Point Problems
AI 导读
研究者提出基于 Chambolle-Pock 原始-对偶混合梯度（PDHG）方法的神经消息传递框架 GraphPDHG，用于求解通用图鞍点问题，理论上可高效模拟 PDHG 求解一类图鞍点问题，并能学习加速版 PDHG 算法。实验显示，该模型作为二阶优化方法 SSNAL 的学习型热启动可提升性能，且与 PDHG 对齐后，其规模泛化能力优于未对齐的 GNN 基线。
正文
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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07255 [cs.LG] |
| (or arXiv:2610.07255v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07255 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Samantha Chen [view email]
[v1]
Mon, 5 Oct 2026 18:55:21 UTC (386 KB)
来源：arXiv：cs.LG · arxiv.org