用神经网络模拟经典优化算法，提升复杂图问题求解能力。
Primal-Dual Neural Algorithmic Reasoning
- 基于原始-对偶框架构建神经算法推理模型
- 在多个任务上超越传统近似算法且泛化能力强
- 适合需要可解释性与高效求解的工业优化场景
神经算法推理（NAR）训练神经网络以模拟经典算法，实现对复杂数据的结构化和可解释推理。以往研究主要聚焦于可多项式时间求解的问题，而将NAR扩展到更难问题仍是开放挑战。本文提出一种基于原始-对偶范式的通用NAR框架，该范式是设计高效近似算法的经典方法。通过建立原始变量与对偶变量之间的二分图表示，我们实现了原始-对偶算法与图神经网络的对齐。此外，引入小规模实例的最优解显著提升了模型推理能力。实验表明，该模型不仅能模拟，还能在多个任务中超越传统近似算法，对更大规模及分布外图结构表现出强泛化能力。进一步地，我们将框架与商用求解器结合，并应用于真实世界数据集，验证了其实际价值。
原文摘要 · Abstract (English)
Neural Algorithmic Reasoning (NAR) trains neural networks to simulate classical algorithms, enabling structured and interpretable reasoning over complex data. While prior research has predominantly focused on learning exact algorithms for polynomial-time-solvable problems, extending NAR to harder problems remains an open challenge. In this work, we introduce a general NAR framework grounded in the primal-dual paradigm, a classical method for designing efficient approximation algorithms. By leveraging a bipartite representation between primal and dual variables, we establish an alignment between primal-dual algorithms and Graph Neural Networks. Furthermore, we incorporate optimal solutions from small instances to greatly enhance the model's reasoning capabilities. Our empirical results demonstrate that our model not only simulates but also outperforms approximation algorithms for multiple tasks, exhibiting robust generalization to larger and out-of-distribution graphs. Moreover, we highlight the framework's practical utility by integrating it with commercial solvers and applying it to real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。