Primal-Dual Neural Algorithmic Reasoning
This work addresses the problem of enabling neural networks to simulate complex algorithms for researchers in machine learning and algorithmic reasoning, representing a novel method rather than an incremental improvement.
The paper tackles the challenge of extending Neural Algorithmic Reasoning to harder problems by introducing a primal-dual framework, which outperforms approximation algorithms on multiple tasks and generalizes robustly to larger and out-of-distribution graphs.
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.