Primal-Dual Neural Algorithmic Reasoning
Authors: Yu He
Ellen Vitercik
Venue: ICML 2025 spotlightposter (2025)
Keywords: Neural algorithmic reasoning
graph neural networks
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a general framework for Neural Algorithmic Reasoning to learn the primal-dual (exact and) approximation algorithms.

Abstract: 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.

Understanding the algorithmic reasoning ability of neural networks is crucial for quantifying their expressivity and practical deployment (Eukasz Kaiser & Sutskever, 2016; Zhou et al., 2022: Sanford et al., 2024; de Luca Foun- toulakis, 2024). However, end-to-end supervised learning often struggles with generalization for algorithmic tasks. Neural Algorithmic Reasoning (NAR) (Veličković & Blun- dell, 2021) addresses this challenge by training neural net- works to mimic operations of classical algorithms, such as Primal-Dual Neural Algorithmic Reasoning
Yu He
Ellen Vitercik 12
Abstract
Bellman- FFrd for shortest-path problems (Veličković et al., 2020). By aligning a model's architecture with an algo- rithm's 's step-wise operations, NAR enhances generalization and sample efficiency (Xu et al., 2020; 2021).
Neural Algorithmic Reasoning (NAR) trains neu- ral networks to simulate classical algorithms, en- abling structured and interpretable reasoning over complex data. While prior research has predom- inantly focused on learning exact algorithms for polynomial-imme-ae soleabll problems, extending NAR to harder problems remains an open chal- lenge. In this work, we introduce a general NAR framework grounded in the primal-dual paradigm, a classical method for designing efficient approxi- mation algorithms. By leveraging a bipartite rep- resentation between primal and dual variables, we establish an alignment between primal-dual algo- rithms and Graph Neural Networks. Furthermore, we incorporate optimal solutions from small in- stances to greatly enhance the model's reasoning capabilities. Our empirical results demonstrate that our model not only simulates but also out- performs approximation algorithms for multiple tasks, exhibiting robust generalization to larger and out-of-distribution graphs. Moreover, we highlight the framework's 's practical utility by inte- grating it with commercial solvers and applying it to real-world datasets.
Moreover, NAR addresses fundamental bottleneck of clas- sical algorithmss while they guarantee correctness and in- teroperability, they require extensive feature engineering to compress real-world data into scalar values. By embedding algorithmic knowledge into neural models, NAR enables di- rect handling of structured real-world data (Deac al., 2021; He et al., 2022; Beurer- Kellner et al., 2022; Numeroso et al., 2023). For instance, model pre- pre-trained with Bellman-Food Ford knowledge can tackle real-world transportation problems, while integrating domain-specific features such as weather conditions and traffic patterns.
Despite the success of NAR in simulating polynomial-time algorithms (Ibarz et al., 2022; Rodionov & Prokhorenkova, 2024). in particular the 30 algorithms (e.g.. sorting, search, graph) from the CLRS-30 benchmark (Veličković al., 2022) and other benchmarks (Minder et al., 2023; Markeeva et al., 2024), its extension to NP-hard problems remains an open challenge due to the difficulty in reliably generat- ing ground-truie -ruth samplers (Veličković al., 2022). This limitation creates a significant gap when applying NAR to real-world problems, many of which are inherently NP-hard. Addressing this gap is crucial, the motivation behind NAR is to enable the transfer of algorithmic knowledge to tackle complex, real-world datasets effectively.
1. Introduction
We build upon the line of NAR research that simulates clas- sical algorithms with Graph Neural Networks (GNNs) (Xu et al., 2020; Veličkovié et al., 2020; Bevilacqua et al., 2023; Rodionov & Prokhorenkova, 2023; 2024; Georgiev et al., 2024). Specifically, we focus on advancing NAR into the un- derexplored NP-hard domain (Cappart et al., 2022; Georgiev et al., 2023c) by training GNNs to replicate approximation algorithms. Additionally, we leverage findings that NAR benefits from multi-task learning (Xhonneux et al., 2021; Ibarz et al., 2022) when trained on multiple algorithms. In partieular, harness the concept of duality, which frames problems through complementary primal and dual perspec- tives, a principle that has been shown to enhance NAR (Numeroso et al., 2023) in the context of Ford-Fulkerson via the max- max-flow flow min-cut theorem.
'Department of Computer Science, Stanford University, Stan- ford, CA, USA 'Department of Management Science& Engineer- ing, Stanford University, Stanford, CA, USA. Correspondence to: Yu He <heyu@ @stanford.edus.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Primal- Manal-Duallaae Neural Algorithmic Reasoning
Our key contributions are follows:
to a range of exact and approximation algorithms.
Another line of work, Neural Combinatorial Optimization (NCO), develops neural approaches for solving NP-hard problems. However, NCO and NAR differ fundamentally. NCO focuses on learning task-specific heuristics or end-to- end optimization methods for finding (near-)optimal solu- tions (Dai al., 2018; Li et al., 2018; Joshi et al., 2019; Karalias & Loukas, 2021; Wang & Li, 2023; Wenkel et al., 2024; Yau et al., 2024), whereas NAR designs neural ar- chitectures to simulate and generalize algorithmic behav- ior across problems, allowing them to embed algorithmic knowledge in real-world settings. While our primary focus is not NCO, our framework can serve as an algorithmically informed GNN to enhance data efficiency and generalization in supervised learning. See Appendix H for details.
We propose Primal-Dual Neural Algorithmic Reason- ing (PDNAR)- general NAR framework based on the primal-dual paradigm to learn algorithms for both silyyommalltime-sllaallll and NP-hard tasks.
We establish novel alignment between primal-dum algo- rithms and GNNs using a bipartite representation between primal and dual variables.
We provide theoretical proofs showing that PDNAR can exactly replicate the classical primal-dual algorithm and inherit performance guarantees.
We go beyond algorithm replication by incorporating op- timal supervision signals from small problem instances, enabling it to outperform the algorithm is trained on' To the best of our knowledge, this the first NAR method designed to achieve this.
3. Background
We empirically validate PDNAR on synthetic algorithmic datasets, demonstrating strong generalization to larger
3.1. Problem statement: algorithmic reasoning
problem instances and OOD distributions.
The task of algorithmic reasoning is to learn a model M that approximates the behavior of a target algorithm A : X' - V, where inputs x E X map to outputs y = AAar) E y. Unlike standard funetion approximation, the goal is to model the sequence of intermediate states {S(t) 1t= generated by A during execution with trajectory (x) 5(1.
We showcase PDNAR's ' practical utility by applying it to real-world datasets and commercial solvers.
Our code can be found at https: /gi thub.ttubb.c. com/ dransyhe/pdnaz
In particular, we focus on simulating the primal-dual al- gorithm, which provides a general framework to design algorithms for both polynomial-tine commmial-imm--ollvane sole-lol and NP-hard problems. We prioritize the latter due to the limited NAR research in the ha-hard domain.
2. Related works
The most closely related work extending NAR to NP-hard domain is by Georgiev et al. (2023c), which pretrains a GNN on algorithms for oolynomial-time-sllaabb problems (e.g., Prim's 's aagorithm for MST) and using transfer learning to solve NP-hard problems (c.g.. TSP). However, this ap- proach lacks generality since each NP-hard problem requires prob-
3.2. Algorithmic tasks
We study the following algorithmic problems.
carefully selecting related silyyoommll-ime--ollllllll lem and algorithm. However, our method is inherently general, directly learning approximation algorithms for NP- hard tasks and incorporating optimal solutions from small instances to enhance the model's reasoning ability.
Definition 3.1 (Minimum Vertex Cover). Let G = EV,E) be graph where V are vertices and È are edges, and each vertex v E V has a non-negative weight wy E IR+, A vertex cover for G is subset C C V of the vertices such that for each edge (v, u) E E, either v E C, u C, or both. The objective is minimize the total vertex weight Evec We.
Only one prior work has explored the role of duality in NAR. Numeroso et al. (2023) trained a GNN to replicate the Ford- Fulkerson algorithm for the max-flow (primal) and min-cut (dual) problems. By leveraging supervision signals from both problems, their model benefits from multi-task learning to achieve better performance. However, their architecture is highly specialized for Fuld-uuleesoon, and both problems are polynomial-tine solvable and thus benefit from strong duality. In contrast, our framework is general and applicable
Definition 3.2 (Minimum Set Cover). Given a ground set U and a family of sets C C 2 with non non-negative weights ws E I++ for all sets S E C, a set cover is a subfamily C' S C such that Usee S UsecS. The objective is to minimize the total weight Σ Eser Ws-
Definition 3.3 (Minimum Hitting Set). Given ground set E of elements e with non-negative weights w. E R+ and a collection T of subsets T C E, a hitting set is a subset A C E such that AnT A for every 7 E T. The objective is to minimize the total weight E.eA We.
Many classical primal-dual algorithms achieve tight worst- case approximation bounds under the Unique Games Conjec- ture (e.g.. Khot & Regev, 2008). Although worst-case limits unlikely to be exceeded, our empirical results demonstrate improved performance a setting heyond the worst-case.
2

---

Primal- Dual Neural Algorithmic Reasoning
Minimize
Σ
WrTt
Minimize
Σ
We
Maximize
Σ 1/1 TET
eEE
CEE
subject to
Σ 11 E
subject to
Σ
Ie 21,
VT
subject to
Σ yr S Wes e
eET
EET
TREE
de E (0, l}: Ve E
0, YeE
WT 2 0, VI ET
(a) Minimum Hitting Set (MHS) (b) LP relaxation of MHS
(c) Dual of LP relaxation of MHS
Figure I. Ze E {0, 1] for each element E E be the variables, where = represents that element is included in the hitting set A. the IP formulation of MHS is shown in (a). Let n, E RR" the primal variables, the relaxation of MHS is shown (b). Let yr E IR" for each set T E T be the dual variables, the dual problem of the LP relaxation of MHS is shown in (c).
Algorithm 1 General primal-dual approximation algorithm
Input: (T, E, w): a ground set E with weights w, a family of subsets T C 2 A - 0: for all E F. We
while 37: Tnn = do
V + : AAAAA =0}
repeat
for T E do ôr + min.er | } ΣT:err dr
Uniform increase (optional):
for E A do r. 4 ro
(6.1): A + minrevôr
until Be & A
0
(6.2): for E F \ A do t re --Te-((T:e
A + AU {e: Te = 0}
end while Output: A
The minimum vertex cover problem is a foundational NP- hard problem with wide-reaching applications, where its dual problem is the well-studied maximum edge-packing problem. This primal-dual pair inspired a famous 2- approximation algorithm proposed by Hochbaum (1982) and many follow-up works. The minimum set cover prob- lem is a generalization of vertex cover to hypergraphs, pro- viding a more complex structural setting to evaluate algo- rithmic reasoning. Lastly, the hitting set is equivalent to the set cover problem, but its formulation more naturally extends to a wide range of problems, including vertex cover, Steiner tree, feedback vertex set, and many more (Goemans & Williamson, 1996).
ally, the dual of an LP mingsole =o x: Ax > b} is defined as maxy20fy b: A y S c). The weak duality principal states that any feasible solution to the primal problem has a larger objective value than any feasible solution to the dual problem. Based on this principle, the primal-dual frame- work iteratively updates both the primal and dual solutions, closing their gap and ensuring they improve in tandem.
Based on the primal-dual framework, an a-approximation algorithm (Bar- Yehuda & Even, 1981; Hochbaum, 1982; Goemans & Williamson, 1996; Khuller et al., 1994) for the general hitting set problem was developed, where the maximal cardinality of the subsets. The pseudocode of the algorithm is shown in Algorithm Given a hitting set problem (T, E, w), the algorithm progresses over series of rounds. At each round, the algorithm increases some of the dual variables yr until a constraint Ereer Vr S we becomes equality, at which point the element e is added to the hitting set A. Although the algorithm does not explicitly define the dual variables yr, it can be interpreted gradu- ally increasing the dual variables by an amount 87 in each round, as shown in Line 1. This is implemented by defining residual weight r. = we - ET.eeT yr, which is defined in terms of the step sizes 8r, as shown in Line 1. Once re = 0 for some e & A (i.e. the constraint becomes tight), e is added the hitting set A (Lines and 1). This process repeated until A is valid hitting set (Line 1).
3.3. A general primal-dual approximation algorithm
We now illustrate a general primal-dual approximation al- gorithm using the Minimum Hitting Set (MHS) problem concrete example. MHS can be formulated as an integer program (IP) as shown in Figure ((a), where variables are restricted to integer values. The linear programming (LP) relaxation relaxes the integer constraints and allows vari- ables to take continuous values, making the problem more tractable. This is illustrated in Figure 1(b).
Every LP formulation has dual version. For MHS, Figure 1(b) is the primal and Figure (c) is the dual. More gener-
3

---

Primal- Duul Neural Algorithmic Reasoning
A general framework This algorithm can be reformu- lated to recover many classical (exact approximation) algorithms (Goemans & Williamson, 1996). For example, vertex cover can be seen as a hitting set problem, where ele- ment e E E corresponds to vertex v E V. and subset 7 E 'T corresponds to an edge that connects two vertices. This al- lows a direct adaptation of Algorithm to solve the vertex cover problem. Moreover, Khuller et al. (1994) propose a sublinear-time vertex cover approximation algorithm which is a simple generalization of Algorithm 1 (see Appendix A). They relax the dual constraint using a parameter > 0, such that vertex e is included in the cover r. S. ewe, instead of Te = 0. This leads to a 2/ apppprooimaaiion algorithm with a runtime of (In² [T] In L). Since set cover extends vertex cover to hypergraphs, this algorithm can be adapted into an r1(1 - ->aappoximaaionn algorithm for set cover, where is the maximal cardinality of the sets. We will later empirically show how well our framework simulates these algorithms. Moreover, the generality of the primal-dual framework is not limited by approximation algorithms for NP-hard tasks: it also recovers exact algorithms for some polynomial time-solvabee problems, such as Kruskal's 's min- imum spanning tree algorithm (Kruskal, 1956).
blueprint (Veličković & Blundell, 2021). In this framework, the processor is typically pesssng--assing GNN (Gilmer et al., 2017), operating in a latent space to simulate sin- gle step of algorithmic execution. The encoder transforms the input value (e.g.. element weight) into this latent space, while the decoder reconstructs the final prediction from it (e.g., whether to include the element in the solution). We continue using Algorithm for MHS as an example.
Bipartite graph construction Given hitting set problem (T, E,), we represent as a bipartite graph with elements E (primal) the left-hand side (LHS) and sets T E T (dual) on the right-hand side (RHS), as illustrated in Figure 2. An edge connects an element e and a set T if e E T. Let (e) denote the set of neighbors of node e. As outlined in Algorithm 1, the algorithm incrementally adds elements e to the hitting set A. When an element is added, we remove node e by masking it out, along with its neighboring sets T E (e), which are now hit. Consequently, the violation set V {T' An T = 0} consists of the remaining sets T still in the graph. Once A becomes a valid hitting set, the violation set V is empty. Next, at each timestep t. we let r(!) denote the residual weight of element e and d! denote its current node degree. Therefore, the initial residual weight (0) is defined as its cost We, and the initial degree d! is given by H[T: : E T.).
Uniform increase of dual variables Some problems ben- efit from simultaneously increasing all dual variables 87 at the same rate (Agrawal et al., 1995; Goemans& & Williamson, 1995). An example is how Kruskal's algorithm greedily se- lects the minimum-cos cost edge that connects two distinct com- ponents. This corresponds to increasing the dual variables for all connected components simultancously until there is an edge whose dual constraint becomes tight. The incorpora- tion of this uniform increase rule is illustrated from Line 6.1 and Line 6.2 in Algorithm 1. This rule provides a more bal- anced approach that attends to all dual variables, allowing the framework to adapt to a broader range of algorithms.
Encoder The architecture includes two MLP encoders, fr and fa. which encode the residual node weight r and node degree d!! respectively, for each element e E E. These en- coders transform all features into a high-dimensional latent space for the processor:
h = (-(r((-))) "),
h hd
fa(d 1)).
4. Primal-Dual Neural Algorithmic Reasoning (PDNAR)
Processor The processor is a message-passing GNN ap- plied to the bipartite graph. A general message-passing framework (Gilmer et al., 2017) comprises a message func- tion the and an update function dg. The node feature h!? of node v is transformed via
We now present our framework of using a GNN to simulate the general primal-dual approximation algorithm, represent- ing the primal-dual variables as two sides in bipartite graph (Section 4. 1). We also show how the uniform increase rule can be incorporated with a virtual node that connects to all dual nodes in the bipartite graph (Section 4.2). Furthermore, we explain how we use optimal solutions from integer pro- gramming solvers as additional training signals (Section 4.4), and later show how it allows the PDNAR to surpass the performance of the approximation algorithm.
h = 6b (199
vo(h!!)) (EN())
where the and 6o are usually shallow MLPs and + is permutation invariant function, such sum or max. We now demonstrate how this message- saauggggassinggggg framework is applied to the bipartite graph to simulate the primal-dual approximation algorithm.
4.1. Architecture
Step (1): This step corresponds Line of Algorithm 1, where increment of for each set T' E V is computed. Let h be the hidden representation of 8(!) We aggregate
We adopt the encoder- processor framework (Ham- rick et al., 2018) from the neural algorithmic reasoning
4

---

Primal-Dual Neural Algorithmic Reasoning
Primal
a
Dual
rc
[1-11
fr
h
9r
a(t)
Σ
ge
min
h
Iu
dl
((-1))
fd
mnnn
qr
1 (1))
de
T
h (0)
h
(8)
+ (
95
87
(a)
(b)
Figure 2. (a) Bipartite graph construction. (b) The architccture of PDNAR with the encoder, processor, and dccoder colored distinctively. A only used when the uniform increase rule applicd.
messages from connected elements (T) using message function Je with min aggregation operation:
output has not produced a valid hitting set, we greedily add the element with the highest re/d, value the solution. Empirically, find our model rarely requires it.
(1) min ge ( ( hT
eEN(T)
4.2. Uniform increase dual variables
Step (2): This step corresponds to Line 1 of Algorithm 1, where residual weight r! for each element e E E A is computed. Therefore, the dual variable update hy is passed back to its connected elements using sum aggregation and an update function Iu:
The uniform increase rule requires global communication among all dual variables. To achieve this, we introduce virtual node that connects every set T T. as shown in Figure 2. Below, we describe how Step (2) in the processor is adjusted to accommodate this modification.
(0) Du
(0)
Σ (cN
Step (2.1): The virtual node aggregates all messages from the dual variables 1y via min aggregation, cor- responding Line 6.1 via h min h
Decoder At each timestep f, Algorithm 1 computes three types of intermediate quantities: (1) whether include an element e in the hitting set, represented by -ic E {0, 1}. (2) the residual weights of element r_()) and (3) the increment to the dual variable g(t) We utilize separate MLP
Step (2.2): The global information is passed back to dual variables with temporary h1 = ( and then to the primal variables h.C with an update function Da and sum aggregation. This corresponds to Line 6.2 via decoders, qas Gr, and gs, to compute each of these quantities:
h (h ETEN(e) h hT)).
( = (
p()) = gr (h (1)
8(0)
qo (h
The intermediate quantity A (x) is also given by Algorithm 1. We use an additional decoder ga to predict Å ga (h( and add LMSF Å (0) A to the total loss algo
Training Given the recurrent nature of our architec- ture, we apply noisy teacher forcing (Veličković et al., 2022) with probability of 0.5 to determine whether to use hints hints- ground-truth values for intermediate quantities above-as inputs for the next timestep. Otherwise, the model's prediction from the previous timestep is passed on. This approach allows the model follow its recur- rent flow while reducing the risk of error propagation. The recurrent model is repeated for maximum of |E| timesteps terminates early when the solution becomes a valid hitting set. The loss function is defined as c(() (BCE (a(()) _(1) + (MSE(P!!) (()) + LMSE (8()) ((t)) averaged across timesteps. During test time, if the model
((t)
4.3. Theoretical justification
Algorithmic alignment is critical for generalization in NAR (Xu et al., 2020; 2021). We show that PDNAR can exactly replicate the behavior of Algorithm 1.
Theorem 4.1. Given hitting set problem (T E, W. let A(T, E, w) be the solution produced by Algorithm I, which terminates after K timesteps. There exists a parameter configuration θ for a PDNAR model Me such that, at timestep K, the model output satisfies M (K) (T, E, E.
and (
A(T, F,, w). Furthermore, let (2(()) (1) 8(0) A A(0) be
5

---

Primal- DDaal Neural Algorithmic Reasoning
the intermediate quantities computed by Algorithm at each timestep t. Then, the PDNNAR model satisfies (T, M@(T, M
5.1. Synthetic algorithmic datasets
Dataset We evaluate PDNAR's ability to simulate the approximation algorithms for the three harhard algorithmic problems described in Section 3.2. The training dataset includes 1000 random graphs of size 16 for each task. We use Barabási-Alberi graphs for vertex cover. For set cover and hitting set, we generate Barabási- with a preferential attachment parameter b = 5. Each test set consists of 100 graphs and is repeated for 10 seeds.
w) = (ax(), r(()) 8(1) ( where A is omitted if the uniform increase rule is not applied.
In our proof of Theorem 4.1 (Appendix B), we show that this can be achieved with a PDNAR model using 8 layers. Therefore, PDNAR inherits the approximation ratio and convergence guarantees of the primal-dual approximation algorithm it learns, as described in Corollary 4.2.
bipartite graphs
Baselines We compare with three types of baselines. (i) GNNs for end-to-end node classification trained with op- timal labels: GIN (Xu et al., 2019) and GAT (Veličković et al., 2018). (ii) NAR models to simulate the approxima- tion algorithm: NAR (MPNN) (Veličković et al., 2020) and the more expressive TripletMPNN (Ibarz et al., 2022) at the cost of training efficiency. Both models do not use the bipartite representation, and therefore trained only on intermediate states of primal variables. (iii) Variations of PDNAR: No algo (trained without intermediate supervision from the algorithm) and no optm (trained without optimal solutions). Additionally, PDNAR's s aggregation strategy is specifically tailored to align with the algorithm's 's structure. We test alternative mean and max aggregation methods.
Corollary 4.2. There exists a parameterization of the PDNAR model MM with 8 layers such that, after K itera- tions, M ( (T, E, w) yields an a-approximation to the op- timal solution the MIS problem, where a = mmxxee ((T') and K = O(E))
This guarantee also extends to the 2/(1 - e)-approximation algorithm (Khuller et al., 1994) for MVC (and thus MSC),
Corollary 4.3. Given e E (0,1) there exists a parameter- ization of the PDNAR model Me with 8 layers such that, after K iterations, M(K) (V, E, w) yields an 2/(1 - -)- approximation to the optimal solution of the MVC problem, where K= = Ollog m log(1/c)) and m = |
Table shows PDNAR achieves the best performance. By combining losses from intermediate steps of the approx- imation algorithm and optimal solutions from IP solvers, PDNAR yields the lowest ratios across all test cases. More- over, PDNAR's performance remains stable across differ- ent graph sizes, indicating strong generalization to larger problems. Comparisons with other baselines (such as "No optm") show that incorporating supervision from optimal solutions improves the quality of final predictions, allow- ing PDNAR to outperform the primal- -dual algorithm it was designed to simulate. In contrast, training without interme- diate steps (such as "No algo") leads to a significant drop in generalization, highlighting that the primal-dual algo- rithm provides critical reasoning capabilities beyond merely learning optimal solution patterns.
4.4. Use of optimal solutions from solvers
We can compute optimal solutions using IP solvers for small problem instances. We use the default IP solver in scipy based on HiGHS (Schwendinger & Schumacher, 2023; Huangfu & Hall, 2018). These optimal solutions are used as additional training signals to guide the model toward better outcomes. However, unlike the primal-dual algorithm, which provides intermediate steps. IP sol vers only produce the final optimal solution. Therefore, the corresponding loss defined as fopu = LBCE ( .x2 ). where K is the final timestep. The overall loss is then the sum of the intermedi- ate losses from the primal-dual algorithm and the optimal solution loss, given by L -= 인 Et=1 a(g) + Loptm- The motivation stems from the fact that IP solvers are computa- tionally expensive, especially for larger problem instances. By training PDNAR using optimal solutions from IP solvers on smaller problem instances instances-alloving it to exceed the performance of the approximation algorithm- we can lever- age its generalization ability to create a cost-efficient, high- performance model for much larger problems.
Our model is a general NAR framework for wide range of algorithms that uses the primal-dual paradigm. In Table 1, we see PDNAR is effective across all three tasks. For ver- tex cover, we demonstrate its applicability to graph-based based algorithms. set cover, we extend the framework to hyper- graphs using a bipartite structure, highlighting its flexibility beyond traditional graph settings. Additionally, the uniform increase rule proves effective for hitting set, which can be instantiated to range of exact and approximation algo- rithms. Notably, these results suggest that our approach may achieve even better performance when trained on more chal- lenging instances where the optimal solutions significantly outperform those of approximation algorithms.
5. Experiments
Dataset distributions and hyperparameter details of all ex- periments are provided in Appendices C, D, and E.
6

---

Primal- Duul Neural Algorithmic Reasoning
Table 1. Modell-t- toollooto-l weight ratio trained on 16-node graphs and tested on larger graphs, calculated by the sum of weights from the model solution divided by the sum of weights from the algorithm solution (Wmoda/ Watgo). ). Smaller is better for minimization tasks.
Model
(1x)
32 (2x)
64 (4x)
(8x)
256 (16x)
512 (32x)
1024 (64x)
GIN
0.987 1: 0.011
1,40 1: 0.041
1.097 1: 0.089
1.087 1 0.061
1.109 1 0.073
1.120 0.083
1.116 + 0.083
GAT
0,962 :: 0.106
1.039 1: 0.085
1.072 1: 0.099
1,071 4: 0.085
1.108 1: 0.106
1.114 0.096
1.125 4: 0.082
MVC
NAR
0.998
0.999 0.12
1,005 2011
1,002 1
1,009 0.015
1.013 0.12
1,018 0013
TripleMMPNN
0.982 = 0.015
0.986 + 0.015
0.991 + 0.13
0.995 + 0.020
1,000 = 0.013
1.001 0.0099
1.005 + 0.019
No algo
1.142 +: 0.038
1.115 0.027
1.110 4: 0.038
1,099 + 0.052
1,091 + 0.034
1,099 0.006
1,095 4 0.008
optan
0.995 +
1.001 0.044
0.05
0.938 + 0.009
0,998
+ 0.011
0.994 + 0.111
PDNAR (mnean)
1,031 1: 0.022
1.062 0.001
1.099 0.029
1.107 1 0,047
1,107 1: 0,046
1.122 0.019
1.126 1 0.055
PDNAR (max)
0.968 = 0.014
1.011 0012
1.003 + 0012
1,005 + 0.014
1,006 = 0.013
1.010 + 0.15
1.007 + 0013
PDNAR
0.943 +
0.957 0.002
0.002
0.958 + 0.002
0.958 = 0/002
0.958 0.002
0.957 + 0.002
No algo
1,028 = 0.016
1.025 + 0.04
1.10 0017
1.017 = 0.020
1.012 = 0.018
1.008 = 0.03
1.006 + 0.027
MSC
optm
1,008 =: 0.006
1,008 1: 0.008
0.997 + 0.008
0,992 : 0.006
0.981 = 0.004
0.973 0.002
0.975 + 0.002
PDNAR
0.979 =
0,918 0.013
0.947 0.009
0.915 + 0.005
0.920 0.007
0.915 0.06
0.913 + 0.003
algo No upizn
1.047 = 0.008
1,050 1: 0.006
1.049 + 0.007
1,036 + 0.016
1,065 = 0.023
1.122 0.011
1,256 + 0.036
MIIS
1.002 + 0.000
1.008 0.003
0.994 0.006
0.999 + 0.007
1,005 0.010
1.015 0.013
1.053 + 0.018
PDNAR
0.989 = 0.002
0.982 + 0.005
0.985 + 0.005
0.965 + 0.006
0.990 = 0.008
0.996 0.009
1,027 + 0.000
Table 2. Model-to-alloorthh weight ratio trained on B-A (bipartite) graphs and tested on OOD graph families.
(1x)
(2x)
64 (4x)
128 (8x)
256 (16x)
512 (32x)
1024 (64x)
E-R
0,955 0.04
0.934 0004
0.934
0,950 +
0,992 + D.0F
0,989 0.008
0,993 0.008
Star
0.966 1: 0.001
0.979 0.00
0.977 1: 0.005
0.982 1 0.006
0,989 = 0,005
0,992 0.007
0.998 1: 0.006
MVC
Lobster
0.971 0.00
0.965 + 0008
0.972 = 0.004
0.960 + 0.005
0.970 = 0.008
0.966 = 0.009
0.966 : 0.009
3-Con
0.974 0.002
0.965 1: 0.002
0.965 :: 0.005
0.957 :: 0.006
0.963 = 0.006
0,962 0.008
0,961 :: 0.009
MSC
6 == 3
0,943 1: 0.008
0.941 4: 0.005
0.916 +: 0.008
0.918 1: 0.006
0.924 :: 0,003
0,929
0.003
0.922 ::: 0,004
+: 0.010
0.950 + 0015
0.955 :: 0.016
0.940 : 0.013
0.944 = 0.010
0,941 0.017
0.943 + 0.012
MHS
6 == 3
0,988 1: 0.002
0.995 1 0.003
0.985 :: 0.004
0.982 1: 0.005
0.982 : 0,002
1.008
0.015
1.005 +1: 0,036
8
0.979 0.002
0.978 0.055
0.973 +: 0.008
0,960 +: 0,000
0.983 :: 0.010
1.008
0.015
1.014 +: 0.018
5.2. Size and OOD generalization
underscores the key strength of PDNAR - we can train it efficiently using small problem instances and apply it to much larger, unseen problems that are computationally expensive to solve.
Dataset We evaluate the model's generalization perfor- mance on larger and OOD graph families, using the same training set as before. For the vertex cover problem, we generate three OOD test sets comprising Frdōs-Rénn) (E- R), Star, Lobster, and 3-connected planar (3-Con) graphs. These graph types pose unique challenges for the vertex cover problem due to their distinct structural properties. For set cover and hitting set, we vary the preferential attachment parameter & to and to generate OOD bipartite graphs.
5.3. Real-world datasets
We now present a practical use case of our model. One of the key strengths of NAR is its ability to embed algo- rithmic knowledge in neural networks to tackle real-world challenges. Previous works applied NAR to reinforcement learning (Deac et al., 2021), brain vessels (Numeroso et al., 2023), and computer network configuration (Beurer-Kellle et al., 2022). Traditional algorithms designed for specific problems face a significant limitation: they cannot be di- rectly applied to real-world data without substantial prepro- cessing. Indeed, real-world graphs generally consist of high- dimensional features rather than simple scalar weights the standard input for most traditional algorithms. As a result, applying traditional algorithms would necessitate extensive feature engineering to derive scalar weights, which may lead to the loss of crucial information embedded in the high-dimensional features.
Table 1 demonstrates that PDNAR, trained on 16-node graphs, scales robustly to larger graphs of up 1024 nodes for MVC. We highlight that prior NAR research typically evaluates up to 128 nodes. Furthermore, Table 2 shows PDNAR's ability to generalize to graphs from OOD fam- ilies. Notably, these graph types can exhibit significantly different optimal sizes: Réngi graphs require an aver- age of 80% of nodes, while Star graphs need only 15% (see Table 5), highlighting the strong generalization ability of PDNAR. Obtaining optimal solutions for small instances is fast and efficient, even for hard problems, particularly with integer programming solvers like Gurobi (Gurobi Optimiza- tion, LLC, 2024). However, the computational complexity increases exponentially as the problem size grows. This
In contrast, PDNAR overcomes this limitation by integrat- ing feature encoder that learns to estimate vertex weights
7

---

Primal- Dual Neural Algorithmic Reasoning
directly from raw data, eliminating the need for manual pre- processing. We showcase such an application using the Air- ports datasets (Brazil, Europe, USA) (Ribeiro et al., 2017). In these graphs, the nodes represent airports, and the edges represent commercial flight routes. The goal is to predict the activity level of each airport, where vertex cover solutions can be highly valuable predicting node influence.
Table 3. Accuracy (%) for the three Airports datasets comparing embeddings generated using different methods.
Brazil
Europe
USA
GCN
58,89 1:7722
63.87 + 10.74
77.48
2.28
GCN+LapPE
61.48 + 19:23
73.50 + 3.3
78.11
+: 2.94
GCN+RWPE
58.15 + 2015
73.25
4.47
77.56
3.28
GCN+Degree
71.48 + 15:53
70.37
4.16
79.25
=: 2.16
Architecture and baselines We follow similar evaluation settings as Numeroso et al. (2023). We use three base mod- els to perform node classification: GCN (Kipf& & Welling, 2017), GAT (Veličković et al., 2018), and GraphSAGE (Hamilton et al., 2017). Then, we use PDNAR to produce embeddings to be concatenated with the base model's out- puts before final classification layer. We use a pretrained PDNAR on B-A graphs of size 16, keeping only the pro- cessor and degree encoder. We train new encoder that learns to map new node features into the shared latent space of the processor, enabling it to replicate the vertex cover problem-solving behavior on airport data. The pretrained components are frozen, and a single pesssag--passing step is performed. We compare PDNAR's embeddings against several baselines: Vode2Vee (Grover& & Leskovec, 2016) and a degree encoder. The latter helps to show that PDNAR captures more complex information beyond node degrees. We also compare with two positional encodings: LapPE (Dwivedi et al., 2022a) and RWPE (Dwivedi et al., 2022b).
GCN+N2V
73.33 5:44
74.75
= 5.12
79.54
2.19
GCN+PDNAR
81.11 + 9.46
76.88 +: 5.10
82.82 #: 3.06
GAT
60.13 + 15:68
65.85 1: 9.68
80.59 +
GAT+LapPE
62.22 # 19:23
71.00 + 4.57
79.54 +: 2.57
GAT+RWPE
66.30 + 21.24
73.87
+ 5.93
82.39
1.99
GAT+Degree
66.30 + 12:27
77.75 4.10
82.82 2.08
GAT+N2V
75.56
75.87
5.00
82,65 1,58
GAT+PDNAR
84.44 8.89
81.25
:: 4.51
85.13
1.79
SAGE
44.82 + 17:40
61.82 : 10.38
78.07
3.30
SAGE+LapPE
62.59 +: 22.98
64.12 +: 21.72
79.50
2.02
SAGE+RWPE
50.74 + 25.23
73.38 + 3.54
80,80 2.65
SAGE+
74.44 + 12:74
75.50 + 9.19
81.53
2.18
SAGE+N2V
80.00
6.46
76.12 3:75
83.15 3.20
SAGE+PDNAR
85.56 1 7.49
80.75 +: 2.38
83.28 2.04
Metries We report the average solving times of all cases when optimal solutions are found (Solve time). We also measure the average computation time to generate the warm- start solutions using the primal-dual algorithm and the model per graph (Compute time). Results are recorded in seconds and averaged across seeds.
Table 3 shows that PDNAR achieves significant improve- ments in all datasets. Note that Vece2Vec has an additional advantage by directly training on the graphs to produce the embeddings. PDNAR's superior performance over the de- gree encoder also indicates that it captures more complex information by integrating both learned node weights from features and degree information to replicate vertex cover. This showcases the important practical value of NAR in em- bedding algorithmic knowledge in real-world applications, overcoming the bottleneck of traditional algorithms.
Table 4. Performance of warm starting Gurobi using solutions from PDNAR trained on 16-node graphs and solutions from the primal- dual approximation algorithm.
Solve time (optimal found)
Compute time
#Nodes
Method
None
78.97 2:24
500
Algorithm
76.69 = 1.54
0.20
PDNAR
72.61 = 2.13
0.02
5.4. Commercial optimization solvers
None
230.84 + 19.59
600
Algorithm
227.83 + 19.32
0.30
Another practical use case for PDNAR is to warm start large-scale commercial solvers, such as Gurobi (Gurobi Optimization, LLC, 2024), by initializing variables with its predictions. The motivation is that providing a starting point closer to the optimal solution can lead to faster solving times and improved efficiency.
PDNAR
209.52 + 14.15
0.03
None
299.01 + 23.53
750
Algorithm
300.12 + 22.89
0.39
PDNAR
292.92 + 18.61
0.03
Table 4 shows that PDNAR outperforms both the default initialization and the approximation algorithm in all cases, achieving the fastest mean solving time. The improvement from using the model over the algorithm is greater than that of the algorithm over no warm start. Additionally, the model's inference time is nearly 10 times faster than the approximation algorithm's computation time. This demon- strates a practical use case: by simulating an approxima- tion algorithm and leveraging optimal solutions on small
Dataset We evaluate the vertex cover problem by com- paring Gurobi's default initialization to warm starts using solutions from the primal-dual algorithm and our model. Trained on 1000 B-A graphs of size 16, the model generates solutions for random larger B-A graphs, with 100 graphs per size. Gurobi's 's default parameters are used, with a thread count of and 1 hhouur time limit.
8

---

Primal- Dual Neural Algorithmic Reasoning
instances, the model generates high-quality solutions for larger problems, improving efficiency for large-scale com- mercial solvers, such Gurobi.
References
Agrawal, A., Klein, P., and Ravi, R. When trees collide: An approximation algorithm for the gener- alized steiner problem on networks. SIAM Journal on Computing, 24())440-456, 1995. doi: 10.1137/ S00975337992236337, URL https: //t::///oiiiio org/10. 1137/8009753999223222
6. Conclusions
We propose a general NAR framework using the primal- dual paradigm. Our approach can simulate approximation algorithms for NP-hard problems, greatly extending NAR's capability beyond the polynomial timeiiill-im--oolaabll domain. Furthermore, we leverage both the intermediate states gener- ated by the primal-dual algorithm and optimal solutions ob- tained from integer programming solvers on small problem instances, which can be obtained efficiently. While interme- diate algorithmic steps provides a foundation for reasoning, incorporating optimal solutions enables the model to surpass the algorithm's 's performance. Empirical results demonstrate that our framework is effective and robust, showing strong generalization to larger problems and OOD distributions. Additionally, we present two practical applications: gener- ating algorithmically informed embeddings for real-world datasets and warm-starting commercial solvers.
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 2019.
Bar- Yehuda, R. and Even, S. linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2): 198-203, 1981. ISSN 0196-6774,
doi: URL
science/artionn hiteeo///rttccee///////66/////11
Beurer-Kellner, L., Vechev, M., Vanbever, L., and Veličković, Learning to configure computer networks with neural algorithmic reasoning. In Koyejo, S., Mo- hamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Sys- tems, volume 35, pp. 730-742. Curran Associates, Inc., 2022.
Limitation and future work The primal-dual framework underlies many algorithmic problems, making our approach broadly applicable. Our architecture is currently designed for the hitting set problem, which can be reformulated as many other algorithmic problems. However, problems that do not reduce to hitting set may require architectural exten- sions. For instance, the uncapacitated facility location prob- lem involves two types of dual variables that need special- ized handling. Other advanced techniques (Williamson & Shmoys, 2011), such selectively updating dual variables to improve scalability, can further extend our framework to a broader class of approximation algorithms. Future work could also explore the multi-task learning setting (Ibarz et al., 2022) in PDNAR by training on multiple approxima- tion algorithms simultaneously.
Bevilacqua, B., Nikiforou, K., Ibarz, B., Bica, L,, Pa- ganini, M., Blundell, C., Mitrovic, J., and Veličković, P. Neural algorithmic reasoning with causal regular- isation. In Krause, A., Brunskill, E., Cho, K., En gelhardt, B., Sabato, S., and Scarlett, J. (eds.), Pro- ceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 2272-2288. PMLR, 23-29 Jul 2023. Utthtts::/ httpss///pccccednegeeeeee mlr press/ v202 /bvi law.uaaaauuuaaaa .html.
Borodin, A., Karavasilis, C., and Pankratov, D. An exper- imental study of algorithms for online bipartite match- ing, 2018. URL http:: /ttt:p::/aaxiv..oo org/ abs 1808. 04863.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Bounsi, W., Ibarz, B., Dudzik, A., Hamrick, J. B., Mar- keeva, L., Vitvitskyi, A., Pascanu, R., and Veličković, P. Transformers meet neural algorithmic reasoners. arXiv preprint arXiv:2406.00 09308, 2024.
Acknowledgement
Cappart, Q., Chételat, D., Khalil, E., Lodi, A., Morris, C., and Veličković, Combinatorial optimization and rea- soning with graph neural networks, 2022.
We thank the anonymous reviewers for their valuable feed- back on this manuscript. This work was supported in part by NSF grant CCF-2338226.
Cormen, T. H., Leiserson, C. E.,, Rivest, R. L., and Stein, C. Introduction to Algorithms. The MIT Press, edition, 2001.
9

---

Primal- -uall Neural Algorithmic Reasoning
Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., and Song, L. Learning Combinatorial Optimization Algorithms over Graphs, February 2018. URL /ttp:://aaxvv...///ae abs/1704. 01 01665. arXiv: 170..0160.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model arbitrarily large tsp instances. Pro- ceedings of the AAAI Conference Artificial Intelli- gence, 35(8):7474-7882 May 2021. doi: 10.1609/ aaai.v35i8. 16916. URL /tt.httts/::/os.aaaiiii madex.pppl. wtw.:p/p/...../aaaicceee///eeeee
de Luca, A. B. and Fountoulakis, K. Simulation of graph algorithms with looped transformers. In ICML, 2024. URL https:://///. https:://penneeeeeeeeeee http://pppreeeeeeee wtwpeeviiewweee/oouumre.. id=aA2326y3hf.
Gasse, M., Chételat, D., Ferroni, N., Charlin, I.,, and Lodi, A. Exact Combinatorial Optimization with Graph Convo- lutional Neural Networks, October 2019. URL http:// a arxiv arxiv.org/ abs 1906.. 62.9. arXiv:190.016629
Deac, A., Bacon, P.-L., and Tang, Graph neural induction of value iteration, 2020. URL httpss://axxi....... abs/ 2009/200..00 12604.
Georgiev, D. and Liò, P. Neural bipartite matching, 2020. arxiv. URL wwt.tt://///..... http::////xxvv.rrro/p/oe .rgg abs /205. 11304.
Deac, A.-I., Veličković, P., Milinkovic, O., Bacon, P.-L.., Tang, J., and Nikolic, M. Neural algorithmic reasoners are implicit planners. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 15529-15542. Curran Associates, Inc., 2021. URL https::/prrcceedngggg.. oc cc/paper_  /ttpppee_fileeeeppprr/////////11 92288112262244113302222222222223 pdf.
Georgiev, D., Barbiero, P., Kazhdan, D., Veličković, P., and Lió, P. Algorithmic concept- based explainable reason- ing. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6))6685- 66966, Jun. 2022. doi: 10.1609/ aaai.v36i6.20623. URL /aaatpppp////ssaaaaaaaaaaa orgi index. php/ AAAI
Georgiev, D., Vinas, R., Considine, S., Dumitrascu, B., and Lio, P. NARTI: Neural Algorithmic Reasoning for Trajectory Inference. In The 2023 ICML Workshop on Computational Biology, 2023a.
Dudzik, A. J., von Glehn, T., Pascanu, R., and Veličković, P. Asynchronous algorithmic alignment with cocy- cles. In Villar, S. and Chamberlain, B. (eds.), Pro- ceedings of the Second Learning on Graphs Con- ference, volume 231 of Proceedings of Machine Learning Research, pp. 3:1-3:17. PMLR, 27-30 Nov 2024. URL WUtLtttps:/pproced... pttp///eeoeeeesseeeeeeee/oes. mlr .tl..resss/////// v231 h231/dudzik24a html.
Georgiev, D., Liò, P., and Buffelli, D. The deep equilibrium algorithmic reasoner. arXiv preprint arXiv:2402.cm 06445, 2024.
Georgiev. D. G., Lio, P., Bachurski, J., Chen, J., Shi, T., and Giusti, L. Beyond erdos-renyi: Generaliza- tion in algorithmic reasoning on graphs. In The Second Learning Graphs Conference, 2023b. https:: / //openreview.rr wwwparvvwwee.ee//oouui...... http:/orrumniiexxxxX9900000
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y., and Bresson, X. Benchmarking graph neural org/ abs/ networks, 2022a. httptt:ss///aae 2003.000 00982.
Georgiev, D. G., Numeroso, D., Bacciu, D., and Lio, P. Neural algorithmic reasoning for combinatorial optimi- sation. In The Second Learning on Graphs Conference, 2023c. URL https: htt.tttss///ppeeeeeee// wpwpreeeeeeeeeeeeeeeeeeeee net forum? i id=NBawTT5ep7.
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In International Confer- ence on Learning Representations, 2022b. URL https: //openreview net forum? d= jnvCphYj.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O.,, and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference on machine learning. pp. 1263-1272. PMLR, 2017.
Engelmayer, V., Georgiev, D. G., and Veličković, P. Parallel algorithms align with neural execution. In The Second Learning on Graphs Conference, 2023. URL https: //openreview. net. formmoorumm// wwtp:mmddddccceccemmmmmmm
Goemans, M. X. and Williamson, D. P. A general ap- proximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. doi: 10. 10.11377550097539799322228 URL attpss:/ htapps:://dd. /oi. /tg//1..137/55000 org//10..1337/8097733352222222
Estermann, B., Lanzendörfer, L. A., Niedermayr, Y., and Wattenhofer, R. Puzzles: A benchmark for neural al- gorithmic reasoning, 2024. URL https: //arxiv... org/abs//447.
Goemans, M. X. and Williamson, D. P. The primal-dual method for approximation algorithms and its application to network design problems, pp. 144-191. PWS Publish- ing Co., USA, 1996.
10

---

Frimal-Dual Neural Algorithmic Reasoning
Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discov- ery and data mining, pp. 864, 2016.
Joshi, C. K., Cappart, Q.. Rousseau, L.-M,, and Laurent, T.
Learning the Travelling Salesperson Problem Requires Rethinking Generalization, May 2022. URL http: arxiv. azxiv.org/aal owo.orgg///.... 2006 07054. arXiv:2006.07054.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https: www. , gurobi com.
JürB, J., Jayalath, D. H., and Veličkovié, P. Recursive al- gorithmic reasoning. In Villar, S. and Chamberlain, B. (eds.), Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pp. 5:1-5:14. PMLR, 27-30 Nov 2024. httptttt://///t http:////occeeddeeeooooo mwr. www..rew..rrprr.o.mmmmmmm.mm.m.. presa/ html.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances neural information processing systems, 30, 2017.
Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J. B., and Battaglia, P. W. Relational inductive bias for physical construction in humans and machines. arXiv preprint (rXiv:8806001200 2018.
Karalias, N. and Loukas, A. Erdos Goes Neural: an Unsuper- vised Learning Framework for Combinatorial Optimiza- tion on Graphs, March 2021. URL http: httth://axxxtt /arxivv. orgg/bss/200/ /2006 10643. urXiv:2006.10641
Hayderi, A., Saberi, A., Vitercik, E., and Wikum, A. MAG- NOLIA: Matching algorithms via GNNs for online value- to-go approximation. In Forty-first International Con- ference on Machine Learning, 2024. URL https: //openreview net. forum? www.mmmmidddddiii--- 7Ra9. Betileew.eeeteeeee
Khot, S. and Regev, O. Vertex cover might be hard to approximate to within 2- e. Journal of Computer and System Sciences, 74(3):335- 349, 2008.
Khuller, S., Vishkin, U., and Young, N. A primal-dual parallel approximation technique applied to weighted set and vertex covers. Journal of Algorithums, 17(2):280-289 September 1994. ISSN 0196-6774. doi: 10.1006/jagm. 1994.1036 URL http: / dx wrg...or/.o...... 1006/ jagm 1999.11335
He, Y., Veličković, P., Lio, P., and Deac, A. Continu- ous neural algorithmic planners. Rieck, B. and Pas- canu, R. (eds.), Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Ma- chine Learning Research, pp. 54:1-54:13, PMLR, 09- 12 Dec 2022, URL https:tt///// httpss////cccedeeeeee mll. press/v19g hhee2..mmmmm
Kipf, T. N. and Welling, M. Semi-supervised classi- fication with graph convolutional networks. In In- ternational Conference on Learning Representations, 2017. URL https: //tp::////ppeeeieee... net//frum? id Ld=SJU4ayYg1.
Hochbaum, D. Approximation algorithms for set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555-556, 1982.
Huangfu, Q. and Hall, A. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119-142 2018. doi: 10.1007/ s12532-017-0110-5
Kruskal, J. B. On the shortest spanning subtree of graph and the traveling salesman problem. Proceedings of the American Mathematicul society, 7(1):48-50, 1956.
Kujawa, Z. Poole, J., Georgiev, D., Numeroso, D., and Liò, P. Neural algorithmic reasoning with multiple correct solutions, 2024. URL https: bttapp:///rxivv.. www.i.ovorrrooo. abs/ 2409. 2409.06953.
Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Ben- nani, M., Csordás, R., Dudzik, A., Bošnjak, M., Vitvit- skyi, A., Rubanova, Y., Deac, A., Bevilacqua, B., Ganin, Y., Blundell, C., and Veličković, P. A generalist neural algorithmic learner, 2022.
Li, B., Yang, L., Chen, Y., Wang, S., Chen, Q. Mao, H., Ma, Y., Wang, A., Ding, T., Tang, J., and Sun, R. PDHG-Unrolled earning-to-Optimizz Method for Large- Scale Linear Programming, June 2024. URL http:// / arxiv. www.vorrg/aaa.. abs 2406 01908. arXiv:2406.0199
Jain, R., Veličković, P., and Liò, P. Neural priority queues for graph neural networks, arXiv preprint arXiv:2307.09660. 2023.
Jin, Y., Song, G., and Shi, C. Gralsp: Graph neural networks with local structural patterns, 2019. URL https:// arxiv. orgo abs 0tbs/19110 1111119111000 19677.7675.
Li, Z., Chen, Q., and Koltun, V. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search, October 2018. URL abs 1//01110.1000 10659. arXiv:1810.10659
07675.
Joshi, C. K., Laurent, T., and Bresson, X. An Efficient Graph Convolutional Network Technique for the Travel- ling Salesman Problem, October 2019. URL http:// arxiv. org/rrggaoooo abs 190...9966..0 01227. 1rXiv.1906.01227.
Markeeva, L., McLeish, S., Ibarz, B., Bounsi, W., Ko- zlova, O., Vitvitskyi, A., Blundell, C., Goldstein, T.

---

Primal-Dual Neural Algorithmic Reasoning
Schwarzschild, A., and Veličković, The cirs-text algo- rithmic reasoning language benchmark. arXiv preprint arXiv:2406.000 04229, 2024.
The clrs algorithmic reasoning benchmark. In Inter- national Conference Machine Learning, pp. 22084 22102. PMLR, 2022.
Minder, J., Grötschla, F., Mathys, J., and Wattenhofer, R. SALSA-CLRS: A sparse and scalable benchmark for al- gorithmic reasoning. In The Second Learning on Graphs Conference, 2023. URL https: /ppereevee.....
Veličković, P. and Blundell, C. Neural algorithmic reasoning. Patterns, 2(7):100273, July 2021. ISSN 2666-3899, doi: 10. 10.1016//.paatee:2211.00002 URL http: /di. org/10 0tt//0..116/11 patter 2021 2021. 100273.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P. and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018. URL https: http///pppneeeeeeeeeeeeeeeeeeeep net wwt.neruum i id=rJXMpiXC2,
Mirjanic, V. V. Pascanu, R., and Veličković, P. La- tent space representations of neural algorithmic reason- ers. In The Second Learning Graphs Conference, 2023. URL httttp:://peerevviiii net/ Eorum? Rd==RPOY
Veličković, P., Ying, R., Padovano, M., Hadsell, R., and
Numeroso, D., Bacciu, D., and Veličkovié, Dual algo- rithmic reasoning. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: h//peeneevew...t htt./ew.eee.ooooooo worumoiiiiiooooo.ooooooooooooi hd-hhwkkkdtttll.. IF.
Blundell, C. Neural execution of graph algorithms. In International Conference Learning Representations, 2020. URL https:/ wwwp/eevppeeeeeeeeeeeee net/ /tr//f?omm id=SkgKOOEtvs.
Ribeiro, L. F., Saverese, P. H., and Figuciredo, D. R. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, KDD '17. ACM, August 2017. doi: 10. 1LL14///399993330999666. URL http:///ee doi. doi. 3098061.
Wang, H. and Li, P. Unsupervised Learning for Com- binatorial Optimization Needs Meta-Leaminng, Jan- uary 2023. URL http://////// /ttt::///xxxv.../// http://///bb///0// 03116. arXiv.2301.03116.
Wenkel, Cantürk, S., Horoi, S., Perlmutter, M., and Wolf, G. Towards general recipe for combinatorial optimization with multi-filter GNNs. In The Third Learning on Graphs Conference, 2024. URL https: / //openreviets eiew net/ forum? d= fwQvb271.
0Tr//1..114/3099720
Rodionov, G. and Prokhorenkova, L. Neural algorithmic reasoning without intermediate supervision. In Thirty- seventh Conference on Neural Information Processing Systems, 2023. URL httpth::sspsspeeeeeeeee n Forum?id=VBwSACORS
Williamson, D. P. and Shmoys, D. B. The primal-dual method. In The Design of Approximation Algorithms, chapter 7, pp. 161-194. Cambridge University Press, 2011.
Rodionov, G. and Prokhorenkova, L. Discrete neural al- gorithmic reasoning, 2024. URL //rxiv.. org/abs/ htg/abs/24022 11628.
Xhonneux, I..P.,, Deac, A.-I., Veličković, P., and Tang, J. How to transfer algorithmic reasoning knowledge to learn new algorithms? Advances in Neural Information Pro- cessing Systems, 34:19500-19512, 2021.
Rossi, E., Charpentier, B., Di Giovanni, F., Frasca, F., Gün- nemann, S., and Bronstein, M. M. Edge directionality improves learning on heterophilic graphs. In Learning on Graphs Conference, pp. 25-1. PMLR, 2024.
Xhonneux, S., He, Y., Deac, A., Tang. J., and Gidel, G. Deep cquilibrium models for algorithmic reasoning. In The Third Blogpost Track at ICLR 2024, 2024. https: / / /oopereviewwwooomommoooo. net/ forum? innrum?ice diiidddiaan aga.gg111440 4G5,
Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, V. Under- standing transformer reasoning capabilities via graph al- gorithms, 2024. URL https: /tte:///arxiii /ttxxvvvvv.//////// org/ abs/ 2405. 18512.
Xu, K. and Veličković, P. Recurrent aggregators in neural algorithmic reasoning. arXiv preprint (ttl::20090775555 2024.
Schwendinger, F. and Schumacher, D. highs: 'HIGHS' Optimization Solver, 2023. URL attps://CRAN CRRNN. R- wtwp:jet...rpppaageeeeeieeee sion 0.1-10.
Xu, K. Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, Representation learning on graphs with jumping knowledge networks. In International confer- ence machine learning, pp. 5453-5462. PMLR, 2018.
R package ver-
Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Ban- ino, A., Dashevskiy, M., Hadsell, R., and Blundell, C.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference
12

---

Primal-Dua Neural Algorithmic Reasoning
Learning Representations, 2019. URL https:// openreview. net. fentt//orrmmidddrre 6 A5Km.
Xu, K., L., J., Zhang, M., Du, S. S., ichi Kawarabayashi, K., and Jegelka, What can neural networks reason about? In International Conference on Learning Reprexentations, 2020. URL https: http//pppeeeeeeeeeeeeeeeeee nww.eeeeeeeeeeeeeee.eeee......ee forum? id Id-rJXbJeHFFS.
Xu, K., Zhang, M., Li, J., Du, S., Kawarabayashi, K.-I. and Jegelka, S. How neural networks extrapo- late: From feedforward graph neural networks. In International Conference Learning Representations, 2021. URL https:::p......m........tt ht/p//pperrevieeeeee net/ Eorum? id=UH- CCCCLICC.
Yau, M., Karalias, N., E. Xu, and Jegelka, S. Are graph neural networks optimal approximation algo- rithms? In The Thirty-eighth Annual Conference on Neu- ral Information Processing Systems, 2024, URL ht tps: /oopenreview net forum? i Sww.1xxbblmmm.....m
Zhou, H., Nova, A., Larochelle, H., Courville, A., Neyshabur, B., and Sedghi, H. Teaching algorithmic reasoning via in-context learning, 2022. URL https: //arxiv. org/ 2211/ 09066.
Zhu, Z., Zhang, Z., Xhonneux, L.PP., and Tang, J. Neural bellman-ford networks: A general graph neural network framework for link prediction. In Ranzato, M., Beygelz- imer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 29476-29490. Curran Associates, Inc., 2021. URL https://proceddings.eeu..r. cc cc/paper_fiiieeeccce /bapee/ffllee/ppee/////////e// Saaf33009Saatcb1099bbc1ccbb-bbb2 pdf.
Eukasz Kaiser and Sutskever, Neural gpus learn al- gorithms, 2016. URL /ttttp://arxiv..... abs/ 1511.08228.
13

---

Primal- Dual Neural Algorithmic Reasoning
A. Additional details of vertex cover and set cover
A.1. Primal-dual pair: vertex cover and edge packing
Given a graph G (V, E), where V are vertices and E' are edges, each vertex v has a non-negative weight R* w.
Definition A.1 (Minimum vertex cover). vereex-cover for is a subset C S V the vertices such that for each edge (v,w) E E, either C, C. or both. The objective is to minimize the total vertex weight Evec
Definition A.2 (Maximum edge packing), An edge- adge-packing is an assignment p E + R of non-negative weights to the edges e E E, such that for any vertex E V, the total weight Emive p(e) assigned the edges e that are incident to is most w wv). The objective is maximize the total edge weight P(e)
The edge packing problem is the dual of the LP relaxation of the vertex cover problem, which also has many practical implications, such as resource allocation. Because of this relationship, the primal-dual pair becomes key problems for studying approximation algorithms and the primal-dual framework. Let f0, 1) indicate whether each vertex E V is in the cover, and E IR+ be the non-negative weight assigned to each edge E E. The two problems can be formulated as:
Min
Σ w(v)xz VEV
Max
Σ y/e
cEE'
sub. to Tu Fy 2 Vc v)) E E Th (0,1}, VoEV
sub. to
Σ Ve S w(v), Veev
c:ecc
Ye 2 0, Ve E E.
A.2. Pseudocode of MVC algorithm
A (1(1 aapproxximttion algorithm for the minimum vertex cover (MVC) problem was proposed by Khuller et al. (1994). It can be interpreted as an instantiation of the general primal-dual approximation algorithm without uniform increase (Algorithm 1). In the following, we give the original algorithm as illustrated in the original paper (Khuller et al., 1994).
Intuitively, the algorithm maintains packing p and partial cover C, = {v E V p(E())) 2 (1 c)w(v)), and gradually increases the edge weights p(e) as much as possible. When the constraint on the residual vertex weight is met, a vertex o is removed and added to the cover Cp. The process iterates until p emaximal and Cp is a cover. Let (,) be the set of remaining edges incident vertex v, (v) = [v)] be the degree, and (v) w(v) p(E(v)) be the residual weight. The following pseudocode of the algorithm described in Khuller et al. (1994).
Algorithm 2 COVER(G EV,E),
1: for V do
2: upp(v) + w(v): Ep(u)= + E(u); do(v) |B(r)
3: end for
4: while edges remain do
5: for each remaining edge (u, v) do
6: 8((u, u)) min (w) mp(e)
(u) do(e)
7: end for
8: for each remaining vertex v do
9: (w) < (p)r) - Evc 5(e)
10:
if (v)(v) S w(e) then
11: delete v and its incident edges; update F.((.) and d-)-)
12: end if
13: end for
14:
end while
Output: the set of deleted vertices
14

---

Primal- Dual Neural Algorithmic Reasoning
A.3. Primal-dual pair: Set cover and element packing
The minimum set cover (MSC) problem generalization MVC hypergraphs. Similar the edge packing, the element packing is the dual of the LP relaxation of the set cover problem.
Definition A.3 (Minimum Set Cover), Given a universe U and a family of sets 2 with non-negative weights W:C R+, set cover is subfamily C' C C such that Usec.S Usec.S The objective is minimize the total weight Esec w(S).
Definition A.4 (Maximum Element Packing). An element-packing is assignment p p:u R+ of non-negative weights to the clements U, such that for any set S E C, the total weight Lees p(e) is at most w(S). The objective is to maximize the total element weight Eeeu p(e).
Let {0, } indicate whether each set S E C is in the cover C", and ye E R be the non-negative weight assigned to each element e E U. The two problems can be formulated as:
Min
w( w(S)zs
Max
Σ ye
SEC
sub. to
Σ 2 1, Ve Eu
sub. to
Σ S w((),, 4A E C
SieES
6ES
as (0,1), ESEC
Ve 0, Ve Ed.
A.4. Pseudocode of MSC Algorithm
The above algorithm be extended for cover r/(1 appppooxxinttoon algorithm, where is the maximal cardinality of sets. The following pseudocode is the adapted approximation algorithm to solve vertex cover hypergraph.
Algorithm 3 COVER(G (V,E),
1: for VEVVVl do
2: (pp())+ + w()): Ep(u) + E(u); do(0) + [B(r)
3: end for
4: while edges remain do
5: for each remaining edge e (v(
6: 8(e) minlaee (p(
7: end for
8: for each remaining vertex v do
9: (p) + (p( (v) 6(e) if (v)(v) S c- w()) then 11: delete v and its incident edges; update (-))) and (-)
10:
12: end
13: end for
end while
15:
Output: the set of deleted vertices
B. Proof of Theorem 4.1
Given a hitting set problem (T, E, w). construct a bipartite graph B explained in Section 4.1. Let (t)) denote the bipartite graph at timestep then (()) = B. If we remove a node e and its incident edges from the graph when an element
is included the hitting set timestep f, an action denoted by æe (t) 1, then the bipartite graph B(t) changes accordingly.
Therefore, the degrees of primal nodes ()) can be computed via d fTT E, max;re(o.....) (x())) for some function
where the max function is applied element-wise. WLOG, let denote the hidden dimension. We can now prove the theorem using mathematical induction.
1. Base (t 0): This is true because the inputs M (T, (0, (w. :ee E},0,0) (z) (0), 20,8800 8(0) A A
15

---

Primal- Duall Neural Algorithmic Reasoning
2. Induction step (t > 0): To formulate the strong induction hypothesis, let (xx(1, r(t), , (+2) be the intermediate quantites computed by Algorithm 1 for each timestep l' E [O,..., 6- 11. assume Me We now prove that M
(()) (T, E, w) - (xlt)) (()) ((t) (())
( (T, E, w) = (x(0), (()) 8(0) (1).
The inputs for the 1hh step of our recurrent model are the outputs from the (1 - 1) step. By the induction hypothesis, for some function f. and the model outputs satisfy & (1' wt for all l' E [0,-.,4-1] 1] via the strong induction hypothesis, have d' (t-1)) (t( 1)
the model output f:(t11) = r(t-1), Furthermore, since d = f(T, E, max.eeo.....
We take the natural logarithmic form of ((t-1) and ( as inputs to the encoders.
Both encoders Jr and Sa are MLPs. We define the weight of Sr as Wf, [1, 0, .... 0J E R We define the weight of fa as Sa2 110,,... .... 0] [= Therefore.
1 fr(r(--1)) WG. In (-1
= [lare 1,,,.., 0] E Raxl
h& fa(d
(0)
Wo In d(-1))
= [In 1), o.... 0] R
The first step performs message-passing from the primal node representations h to the dual nodes h via (0) min (1 (8) h d ). Let be an MLP with ELU activation, then we set Wg. = [1, 0, ..... 0, -1,0,.., 0J E g1x2n
(t)).
bg. = [1] E R,, and W = [1,0,... ..., 0] Rax1 thus:
9.
ge (h( W a
ELU W [1 (1111) + by.
W de
ELU((11, O, ... 11,10,0 -1,0, 0, ...,, 0]T
[ln (Irr( O. O, In d(t- 0, ... 0]) + 1
W ae
ELU In (t-1)
+ +1) In Ind _ (((-1))
In Te (1-1) de
W 9.
ELU
[1-1]
(--1) Since ELU(x)= = ex -1 i S 0, and
de I- S 0.
(t-1)
ge (h(
W
ge
exp
In
Te
df (1-1)
1+11
r
(1-1)
[1, 0, ...,
de (--1)
(1-1)
Te
d(t-1) D..... 0] Rex1
Therefore, the hidden representation ( for each set T E T, is:
(1) = min
(h())) cEN(T)
(t-1)
min
Te
[(-1)) 0, O,... 0]
eTN(TT de
16

---

Primal-Dual Neural Algorithmic Reasoning
Algorithm 4 General primal-dual approximation algorithm
1: Input: (T,E, E. w): a ground set with weights w, and a family of subsets C 2
2: A <-D for all E: re t- we
3: while 37 T An 0 do
4: V - [T' ( AnT 0}
5: repeat
6: for each E V/ do df t- min.eT ( }
Uniform increase (optional):
for each e E do re f- re ET.EET 8T
(6.1): A + minrevôr
8: until 3e $ A re =
(6.2): for E E A do ret re -
9:
A AU Fo 0}
10: end while
11:
Output: A
(1-1)
= =| min
eEN(() d([-1j 0, 0,....0 0]
= 15 .......0. 0] E 1x (From Line of Algorithm 4)
The next step performs message-passingg from the dual node representations h and then updates the primal representations
h via h (t)
Iu (h!)) ETEN(e) h ). We use ELU activation function on the previously computed h and bias
b, = [1, ..., 0] E _=x1, Since r(( (t-1) O, we have:
h ELU (12)) + by
ELU (Inrtt-)) ........) 01) + [1, O,.,,....
(exp (Inr((-1)) - -1+ 1,,00 1,0, 0] [_((-1), .,.....0 0] E m
The update function gu is also an MLP. We define its weights to be W = =1,,0..., 0,,00,,.., 00T E R2222 Then, the
hidden dimension h (+) for each element E becomes:
(1)
Iu
h
(0)
Σ
hT
(0)
TEN(e)
W
h 10
Σ
NT
(EN(()
[1. .... 0, -1, O, ....
[r[ (1-1)) 0, ...... 0, Σ
5 0. O..... 0]
TEN(e)
[[](t-1)
Σ
$ O......
(EN(e)
= -(r(0) 0, .... 0) E gax1
(From Line of Algorithm 4)
17

---

Primal-Duue Duaa Neural Algorithmic Reasoning
Alternatively, if the uniform increase rule is incorporated, have additional virtual node that connects all dual variables. Its hidden representation h computed as:
h min hT TET
(() O,,,,..)) 0]
min TET
[min 67 o,....0 0] TET
= [A (0) 0, 0] E Rxx1
(From Line 6.1 of Algorithm 4)
Then let h7 00 the primal variable updates becomes:
h
9u
h0
Σ (EN(C)
hy
((E)
W
he
Σ
hT
(())
TEM(e)
[1, 0, -1,0, O]T
(r((t-1), 0, 0,,.,,,, Σ
A (0) .......,
TEN(e)
[r(t-1) -d(t-1) A (1)
= [r(() .,..... R (From Line 6.2 of Algorithm 4)
For the decoders yz, 4r, Qs (and 4a if uniform increase is used), they map hidden representations (.. hy (and (t uniform increase is used) predictions for the intermediate quantities computed by the algorithm. We define Wa.
(c)
WG, We Wns 0,,0, ..... OJ E IR-x For (t) it is binary classification task, where (t) = if (2) 0 to add
the element e to the hitting set. Define o: IR + {0, 1}. where
1, i
a(x)
0.
else
We note that although sigmoid function in architecture, the sigmoid function can approximate o(x) to arbitrary precision by adjusting its temperature. Therefore, we have
a(0) ol (h(
W ua (h(
(1, 0, 0] (T .........) 0) ((0)
x (Definition of xx(())
For the other three intermediate quantities:
x(0) = (1)
Wq. (h) (t)
[1,0, ..., 0] [r. .,...... 0
[r.0),0,...
r((
18

---

Primal-Dus Neural Algorithmic Reasoning
qo (b4)))
Was (hg)
11,0, ..... .,,0 1 ........
of A
9 (h
W4 (hl2)
[1, 0, .....
T [ [A (,,0,,000000 ...,0
(0)
Therefore, @ ET,Eww) = (x=(),(() ((0),,(0) A A1) and the induction step is completed.
C. Datasets
C.1. Synthetic datasets
We provide the details of the graph distributions used to generate random graphs for both training and testing.
Barabási-Albert (B-A) graph Barabási-Albert graphs for both training and testing are randomly generated using networkx. www.baaaaaaa................a.aa aatsssslaberrrrrpppeee The number of edges attach from new node to existing nodes is randomly chosen from [1, 10]. Node weights for primal variables uniformly sampled from [0, 1].
Erdós-Rény: (E-R) graph We use networkx erdor aecloosrrei_gg__e_e to generate random Erdós Rényi graphs with edge probability uniformly sampled from 0.8).
Star graph Star graphs are generated by randomly partitioning the nodes into I to 5 sets. Within each node set, star graph is generated with center node connected to all other nodes. Random edges between the star graphs are then added to ensure the graph is connected.
Lobster graph To generate a lobster graph, the number nodes on the "backbone" m is randomly sampled from [1, n- 1]. where n the total number of nodes in the graph. Then, another nodes are added the backbone nodes to start "branches" where < k I (n m). Finally, the remaining nodes (if any left from
k) are randomly attached to the branches.
3-Connected (3-Con) Planar graph networkx. random reqular___rreeeee paaph,, and then checked to if it is 3-connected and planar. The process is repeated until valid 3-connected planar graph is found, or if it reaches the limit of 100 attempts.
3-regular graph is randomly generated with
Table Percentage of nodes being in the optimal vertex cover for different graph familics.
B-A
E-R
Star
Lobster
3-Con
16 nodes
43%
71%
23%
40%
61%
32 nodes
49%
80%
15%
41%
60%
64 nodes
45%
88%
8%
41%
59%
Garabási-Albert bipartite graph We use the same distribution generate random Barabási-Albert bipartite graph as described in Borodin et al. (2018) and Hayderi et al. (2024). Given parameters (m, b), generate bipartite graph G' on the right-hand side (RHS) via preferential attachment scheme. Given
nodes the left-hand side (LHS) and LHS nodes, we attach each RHS node to LHS nodes sampled without replacement, where the probability of selecting an dogrec(v)
LHS node is proportional to Pr[u]
Σ. (egree(v"))
19

---

Primal-Duu Neural Algorithmic Reasoning
The parameter b can be varied to generate OOD graphs. For training, we choose b 5. For testing OOD generalization, we use b = 3 and b generate test graphs with sparser and denser preferential attachment.
For vertex cover and set cover, we use Algorithm 2 and Algorithm 3 (Khuller et al., 1994) to generate intermediate supervisions, which are instantiations of Algorithm 1 with improved efficiency, as explained in Section 3.3. For hitting set, we use Algorithm with the uniform increase rule. Furthermore, the optimal solutions are generated with the default IP solver in scipy, which is based on HiGHS (Schwendinger Schumacher, 2023; Huangfu & Hall, 2018).
C.2. Gurobi datasets
Random B-A graphs are generated following the same distribution described above. For testing, we generate B-A graphs with 500, 600, and 750 nodes. We use the trained model to perform inference on the testing set and retrieve vertex cover solutions. We also use Algorithm 2 (Khuller et al., 1994) to compute solutions with = 0.1. The comparison of the solutions from the model and the algorithm is shown in Table 6. The two sets of solutions are then used to initialize variables to warm-start the Gurobi solver. We also compare them with Gurobi's default initialization (i.e., no warm start). We use the default parameter settings of Gurobi, setting thread count to I (model. setParam (' Threads', 1)), the time limit to 3600s (model. set P Param (" T Time L Limit', 3600)), ) and random seed (model. setParam (1 Seed', seed)). ), Each experiment is repeated with 5 seeds.
Table The ratio of total weights of the solutions generated by the model compared with those generated by the algorithm (Wpead/ Matgo). We also report the percentage of uncovered edges from the solutions generated by the model (i.e. how often the cleanup stage is required).
500 nodes
600 nodes
750 nodes
Wpred/ Walgo
0.972
0.970
0.970
Uncovered edges
0%
0%%
0%
C.3. Real-world datasets
Airports The Airports datasets (Ribeiro et al., 2017) consist of three airport networks from Brazil (131 nodes, 1038 edges), Europe (399 nodes, 5995 edges), and the USA (1190 nodes, 13599 edges). The nodes represent airports, and the edges represent commercial flight routes. The node features are one-hot encoded node identifiers, as described in (Jin et al., 2019). The task is predict the activity level of each airport, measured by the total number of landings plus takeoffs, or the total number of people arriving plus departing. It is classification task with 4 labels, with label assigned to the 25% least active airports, and so on, according to the quartiles of the activity distribution. We create 10 random train/val/test splits for the transductive task with a ratio of 60% /20%.
D. Hyperparameters
All GPU experiments were performed on Nvidia Quadro RTX 8000 with 48GB memory. The Gurobi experiments were conducted on Intel Xeon E7-8890x with 144 cores and 12TB memory.
Synthetic and Gurobi experiments For training, we use the Adam optimizer with an initial learning rate of 1e-3 and weight decay of le-4, coupled with the ReduceLLRnnlaan size of 32, a hidden dimension of 32, and a maximum of 100 epochs. For testing, we use the trained model with the lowest validation loss.
scheduler with default settings. Additionally, we use a batch
Real-world dataset experiments We use the same optimizer and scheduler settings as in the synthetic experiments. Additionally, we also apply early stopping with a patience of 10 epochs based on validation loss and set the scheduler with a patience of 20 epochs. All embeddings have fixed dimension of 32. For testing, use the model with the lowest validation loss. The base models are used with max jumping knowledge (Xu et al., 2018) and 1.2 normalization after each layer (Rossi et al., 2024). We conduct hyperparameter search for each base model on Airports datasets (Brazil, Europe, USA), then use the setting for all embedding methods. Due to the high computational costs of WikipediaNetworkk (Chameleon, Squirrel) and PPI datasets, hyperparameter search is only done with GCN. We use the default TPE hyperparameter search algorithm from optuna (Akiba et al., 2019) with a median pruner. The searchable parameters are lr=[0.01, 0.001, 0.0005), hid dim=[32,
20

---

Hhimll-Dual Neural Algorithmic Reasoning
64, 128], dropout=[001, 0.3, 0.5], and num_layer=[1,, 3, 5]. For training Vode2Vec (Grover & Leskovec, 2016),
walk_ lalk_lenghh=20, context_size=10 balks_per_node=llle with 100 epochs.
Table 7. Additional hyperparameters for weal-world dataset experiments.
Brazil
Europe
USA
1r=0.0055
1r=00001
1r=0.001
GCN
hid did
hid hid_dim=32
hid dim==44
dropout=0.5
dropout=0.1
dropout=0.3
num 3am___aee=3
num lum_layer=3
num_ hum_layer=3
1r=0.001
1r=0.001
1r=0.001
GAT
hid dim=32
hid did_dmm32
did_dim=32
dropout=0.3
dropout=0.1
dropout=0.1
num_layer=3
num_layer=3
num_layer=3
1r=0.0005
1=0.0005
lr=0.001
SAGE
hid ndd_dim=2
hid_dim=32
hid hid_dim=64
0r0pout=0.5
dropout=0.3
dropout=0.1
num_layer=t
num_layers
num_layer=3
E. Additional architectural details
In practice, due to the potentially high degree variance, apply log transformation the node degree de) before encoding with fa for better generalization, i.c. h = (ln( 1)). Then, for decoding a!*) = qz (h which represents whether to include element e to the solution, we apply a sigmoid activation function to convert logits to probabilities. For minimum vertex cover and minimum set cover, since multiple elements can be included into the solution each timestep. set threshold of 0.5 decide whether to include the element. For minimum hitting set, since the uniform increase rule is used, only one element is included into the solution at each timestep, we choose the element with the highest probability to include in the hitting set. Lastly, we add dropouts in between processor layers with probability of 0.2 for Gurobi and real-world experiments. This helps the model to generalize to much larger graphs at a slight cost of approximation ratios.
F. Limitation and future work
While our framework a general one that can learn any algorithm designed with the primal-dual paradigm, the architecture deseribed in the paper can be directly adapted solve any problem represented by the hitting set formulation. The hitting set provides flexible structure for modeling various optimization problems by selecting a subset of elements that "hits" or "covers" all required constraints, represented as sets. This formulation is versatile because it can capture diverse constraints (e.g., nodes, edges, paths, cycles), making it applicable to numerous problems. As discussed in Section 3.3, Algorithm can be reformulated to recover many classical (exact or approximation) algorithms for problems that are special cases of the hitting set, covering both polynomial- Goemans & Williamson (1996) and Williamson & Shmoys (2011), including shortest s-t path, minimum spanning tree, vertex cover, set cover, minimum-com arborescence, feedback vertex set, generalized Steiner tree, minimum knapsack, and facility location problems.
solvable and NP-hard problems. Some of these special cases are illustrated in
We note that not all problems can be directly represented by the hitting set formulation. As a minimization problem, the hitting set does not naturally align with maximization objectives, making the primal-dual approximation algorithm less straightforward to apply. However, the primal-dual framework can still be extended to maximization problems by carefully reformulating the primal-dual pair, where the dual a minimization problem, and adapting Algorithm 1. Then, similarly, the algorithm starts with feasible dual solution and iteratively updates both primal and dual variables reduce the gap between them. Therefore, PDNAR, with its bipartite graph structure, still be extended handle maximization problems with appropriate adjustments to Algorithm 1.
Furthermore, while Algorithm 1 provides general framework for designing primal-dual approximation algorithms, it can be further strengthened by incorporating techniques to enhance the algorithmic performance. One such technique the uniform increase rule, which we have shown how can be integrated into our framework. Future work can incorporate other advanced techniques, such those outlined in (Williamson & Shmoys, 2011), to further extend our framework's 's ability to
21

---

Primal-Dual Neural Algorithmic Reasoning
accommodate a broader range of primal-dual approximation algorithms with improved worst-case guarantees.
Lastly, our method may not explicitly preserve the worst-case approximation guarantees of the primal-dual algorithm in practice. Instead, our model focuses on learning solutions that perform better for the training distribution and generalize well to new instances. While this does not mean that the worst-case guarantees are secured, it is important to note that such cases are often less common in real-world scenarios. One of the core strengths of NAR lies in leveraging pretrained GNN with embedded algorithmic knowledge to tackle real-world datasets. Therefore, we believe it valuable to train models to produce high-que quality solutions for common cases, even if they do not preserve worst-case guarantees. This aligns with the overarching goals of NAR.
G. Related works on neural algorithmic reasoning
We provide a more comprehensive review of existing works on Neural Algorithmic Reasoning (NAR) and highlight our contributions in this context.
Neural algorithmic reasoning The algorithmic alignment framework proposed by Xu et al. (2020) suggests that GNNs are particularly well-suited for learning dynamic programming algorithms due to their shared aggregate-update mechanism. Additionally, Veličković et al. (2020) demonstrates the effectiveness of GNNs in learning graph algorithms such as BFS and Bellman-Ford. These foundational works have contributed to the development of neural algorithmic reasoning (Veličković & Blundell, 2021), which investigates the potential of neural networks, particularly GNNs, to simulate traditional algorithmic processes. This research direction has since inspired several follow-up studies, including efforts to instantiate the framework for specific algorithms (Deac et al., 2020; Georgiev & Liò, 2020; Zhu et al., 2021), applications to real-world use cases (Deac et al., 2021; He et al., 2022; et al., 2024), architectural improvements (Georgiev et al., 2022; Bevilacqua et al., 2023; Rodionov & Prokhorenkova, 2023; Jain et al., 2023; Engelmayer et al., 2023; Mirjanic et al., 2023; Georgiev et al., 2023b; Dudzik al., 2024; Jürß et al.. 2024; Xhonneux al., 2024; Georgiev al., 2024; Rodionov & Prokhorenkova, 2024; Xu & Veličković, 2024; Kujawa et al., 2024), and integration with large language models (Bounsi et al., 2024). Our work advances NAR by introducing general framework designed to tackle combinatorial optimization problems, particularly NP-hard ones, with the objective of simulating and outperforming primal-dual approximatin algorithms.
Kellner et al., 2022; Georgiev et al., 2023a; Numeroso et al., 2023; Estermann
Combinatorial optimization with GNNs The CLRS benchmark (Veličković et al., 2022) and its extensions (Minder et al., 2023; Markeeva et al., 2024) are widely recognized for evaluating GNNs on 30 algorithms from the CLRS textbook (Cormen et al., 2001) and more. However, these algorithms are limited to polynomial-time problems, leaving the more challenging NP-hard problems largely unexplored in neural algorithmic reasoning. A comprehensive review by Cappart et al. (2022) summarizes the current progress of using GNNs for combinatorial optimization. The most relevant work (Georgiev et al., 2023c) trains GNNs algorithms for polynomial-time- time-solvable problems and test them NP-hard problems, demonstrating the value of algorithmic knowledge over non-algorithmically informed models. In contrast, our approach bridges this gap by extending GNNs to tackle NP-hard problems through the use of primal-dual approximation algorithms. Furthermore, we integrate optimal solutions from integer programming, which guides the model toward better outcomes during training. To the best of our knowledge, our method is the first of its kind to surpass the performance of the algorithms it was originally trained on.
Multi-task learning for NAR Early work by Veličković et al. (2020) demonstrated that BFS and Bellman-Ford are best learned jointly, and subsequent studies have highlighted broader benefits of multi-task learning when GNNs are trained on multiple algorithms simultancously (Xhonneux al., 2021; Ibarz et al., 2022). Building this, Numeroso et al. (2023) leveraged the primal-dual principle from linear programming to successfully learn the Ford-Fulkerson algorithm using the max-flow min-cut theorem. However, their approach was tailored specifically for Ford-Fulkerson and did not generalize to other primal- scenarios or address NP-hard problems. To overcome these limitations, our work introduces a general framework that employs the primal-dual principle to enable GNNs to benefit from multi-task learning across a broad range of optimization problems, particularly those expressible as instances of the general hitting set problem.
22

---

Primal- Dual Neural Algorithmic Reasoning
H. Contribution to Neural Combinatorial Optimization (NCO)
Most GNN-based supervised learning methods for NCO learn task-specific heuristics or optimize solutions in an end-to-end manner (Joshi et al., 2019; Li et al., 2018; Gasse et al., 2019; Fu et al., 2021). These end-to-end approaches rely exclusively on supervision signals derived from optimal solutions, which are computationally expensive to obtain for hard instances. such labels can limit generalization (Joshi et al., 2022). In contrast, our method trains on synthetic data obtained efficiently from a polynomial-time approximation algorithm. The embedding of algorithmic knowledge also demonstrates strong generalization. The addition of optimal solutions are derived from small problem instances, enabling our model to outperform the approximation algorithm and generalize effectively to larger problem sizes,
Furthermore, dependence
Our approach represents a previously underexplored area of NCO research with GNNs, offering a general framework to build an algorithiicalyy informed GNN to tackle combinatorial optimization problems. Unlike end-to-end methods, we leverage intermediate supervision signals from polynomial-tine approximation algorithms, which can be generated efficiently, to address key bottlenecks in data efficiency and generalization. Additionally, we fill the gap in autoregressive methods for NCO using GNNs by aligning our architecture with the primal-dual method, enabling the GNN to simulate a single algorithmic step in an efficient and structured manner.
We provide additional empirical evidences on the RB benchmark graphs, which are well-known hard instances for the Minimum Vertex Cover (MVC) problem. We compared our method with several NCO baselines. Given the supervised nature of our approach, obtaining optimal solutions for RB200/500 graphs is computationally challenging. Therefore, we tested the generalization of our model, trained on Barabási-Albert graphs of size 16 (using intermediate supervision from the primal-dual algorithm and optimal solutions), on the larger RB200/500 graphs. We compare with EGN (Karalias & Loukas, 2021) and Meta-EGN (Wang& & Li, 2023), two powerful NCO baselines for these benchmarks, as well as two algorithms (the primal-dual approximation algorithm and the greedy algorithm) and Gurobi. The results are summarized in Table 8.
Table 8. Approximation ratio of solutions compared with optimal solutions for MVC (lower is better).
Method
RB200
RB500
EGN
1.031 + 0.004
1.021 + 0.002
Meta-EGN
1.028 + 0.005
1.016 + 0.002
PDNAR (ours)
1.029 = 0.005
1.020 = 0.004
Primal-dual
1.058 + 0.003
1.056 + 0.004
Greedy
1.124 + 0.002
1.062 + 0.005
Gurobi 9.5 (5 1.00s)
1.011 + 0.003
1.019 + 0.003
Gurobi 9.5 (< 2.00s)
1.008 = 0.002
1.019 = 0.003
From Table 8, we observe that PDNAR outperforms EGN and is competitive with its improved variant, Meta-EGN. Notably, EGN and Meta-EGN are trained directly 4000 RB200/500 graphs, while our method trained solely on 1000 Barabási-Albert graphs with just 16 nodes and tested out-of-distribution.. This highlights the data efficiency and strong generalization capability of PDNAR.
We note that both EGN and Meta-EGN are unsupervised methods, whereas our method adopts a supervised approach. A fairer comparison would involve supervised basclines for NCO. However, current focus of NCO has primarily shifted towards unsupervised methods, leaving existing supervised baselines with outdated performances. Obtaining labels for large graphs, such as RB200/500, is also computationally prohibitive. Additionally, supervised methods usually require a combination of external solvers or search algorithms, which is different setting than ours. In summary, our supervised approach addresses this underexplored direction of NCO by addressing its key challenges - PDNAR as an algorithmically informed GNN that leverages efficiently obtainable labels while demonstrating strong generalization capabilities.
I. Duality in linear programming
Duality in linear programming has been utilized in training neural networks to tackle optimization problems. Li al. (2024) introduces a Seamningto--Ottmne method mimic Primal-Dual Hybrid Gradient method for solving large-scale LPs. While they focus on developing efficient solvers for LPs, we aim to simulate the primal-dual approximation algorithm for NP-hard problems using GNNs. Although both approaches reference the primal-dual framework, this similarity is superficial.
23

---

Primal-Duu Dual Neural Algorithmic Reasoning
The primal-dual terminology is widely used in optimization, but work applies it study algorithmic reasoning. For example, the primal-dual approximation algorithm can be instantiated many traditional algorithms, such Kruskal's algorithm for MST. Furthermore, unlike Li et al. (2024), method relies on intermediate supervision from the primal-dual algorithm to guide reasoning, ensuring that the model learns to mimic algorithmic steps. We also incorporate optimal solutions into the training process to improve solution quality, allowing our model to outperform the primal-dual algorithm is trained on. Moreover, the architectures differ significantly: our method employs a recurrent application of GNN to iteratively solve problems, while Li et al. (2024) does not use GNNs or recurrent modeling. These distinctions highlight that our focus is not on solving LPs but on leveraging NAR generalize algorithmic reasoning for NP-hard problems.
24


Reviews:
[{"review_id": "PvMTOiM6Az", "reviewer": "Reviewer_MtfB", "summary": "The authors propose Primal-Dual Neural Algorithmic Reasoning (PDNAR),  for training neural networks to simulate classical approximation algorithms. The core idea is to leverage primal-dual paradigm,  by representing primal and dual variables as a bipartite graph and parameterzing by GNN. Optimal solutions from small problem instances are incorporated as training signals, enabling the network to surpass the performance of the original algorithms.\n\nThe authors demonstrate that their method outperforms existing baselines acrosss NP-hard problems like vertex cover, set cover, and hitting set. \n\nCode is also shared.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time reading our paper and providing valuable feedback!\n\nWe appreciate your **positive** acknowledgement of our **empirical design**, **results**, and **application**. \n\nWe address your questions in the following: \n\n> Are there any failure cases? What kind of scenarios should use this approach? Where does it fail?\n\nWe note that the primal-dual framework is a core method for many algorithmic problems, so our proposed framework is general. On the other hand, our current architecture design is based on the hitting set. While hitting set can be reformulated as many other problems (e.g. vertex cover, set cover, etc), problems that are not directly formulated as the hitting set may require further adjustment. For example, the uncapacitated facility location problem has two types of dual variables that require different handling, which our current model does not adapt to. We believe these can be interesting future directions to extend our model to an even broader set of algorithms. We will add more elaboration and examples in the revised paper. \n\n> What if optimal solution is not easy to obtain? Are there any such cases? How would the algorithm fare.\n\nWe only train on very small instances on the scale of 16, so obtaining optimal solutions is not a problem, especially with advanced integer programming solvers like HiGHS and Gurobi. Futhermore, while optimal solutions give an advantage to our model to surpass the approximation algorithm, we included an ablation to train with the algorithmic steps only. This setup corresponds to “No optm” in Table 1. We can see in MVC, “No optm” outperforms traditional NAR, and has better generalization ability than both NAR and TripletMPNN (the latter is much more computationally expensive). This highlights the strength of our model, which aligns closely with the primal-dual framework and leverages both primal and dual training signals. We will add a discussion of these points in Section 5.1. \n\nThank you so much for the questions! We hope these answers address them. Please let us know if you require further clarification!", "claims_and_evidence": "1. Generalization to larger graphs: Results shown in Table 1. Trained on smaller, inference on larger.. better quality.\n2. Generalize to graphs from OOD families: Table 2. OOD samples were used for evaluation.\n3. Application of warm start large-scale commercial solvers, such as Gurobi: Table 4, better initialization leads to lower running time,", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Not checked in detail.", "experimental_designs_or_analyses": "Yes. The evaluation seems correct.", "relation_to_broader_scientific_literature": "PDNAR directly trains GNNs to simulate and improve upon approximation algorithms for NP-hard tasks.\nPDNAR goes beyond simply replicating algorithms by incorporating optimal solutions from small problem instances as training signals. This helps them outperform existing method.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths\n\n1. Ablations are done with and without optimal solution integration. (  no optm).. Without optm the quality reduces.\n2. Application is shown -> Initialization  Gurobi helps in reducing running time.\n3. Code is shared.", "other_comments_or_suggestions": "Check questions for authors.", "questions_for_authors": "1. Are there any failure cases? What kind of scenarios should use this approach? Where does it fail? \n2. What if optimal solution is not easy to obtain? Wow does the method fare when high quality but non-optimal solutions are available). I believe if this helps then its an advantage in cases where obtain optimal for small instances is also hard. are there any such cases? How would the algorithm fare. This is an optional expt. But a small discussion(even without experiments) on this should improve the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Sfjnv4ITS3", "reviewer": "Reviewer_jk4v", "summary": "This paper presents a general NAR framework based on the primal-dual paradigm, aiming to solve NP-hard problems that traditional NAR methods struggle with by mimicking approximation algorithms. The authors provide a detailed model description, theoretical justifications, and empirical validation on three NP-hard graph tasks. Overall, I find the paper novel and well-written. However, I still have concerns regarding certain details. If the authors can address these issues, I would be willing to reconsider my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback on our paper, which we summarize below. \n- Paper: **novel** and **well-written**\n- Motivation: **meaningful** and **valuable**\n- Theoretical support: **solid**\n- Writing: **clear**, **well-structured and well-organized**\n\nWe address your questions in the following:  \n\n> The proposed method aims to directly learn approximation algorithms for NP-hard tasks. The authors only discuss three NP-hard problems related to graphs, which may limit the generality of their approach.\n\nWe politely point out that while Minimum Vertex Cover is a graph problem, both Minimum Set Cover and Minimum Hitting Set are not graph problems. Furthermore, Minimum Hitting Set is a general formulation of a wide range of graph and non-graph problems. What we propose was a bipartite graph representation which “turns” these problems into graphs using primal and dual variables. This is based on the fact that all linear programs have a dual formulation. \n\n\n\n> I am curious about how this method performs on problems that are not NP-hard. If it can effectively approximate both NP and non-NP problems, it would make the approach even more compelling. \n\nThank you for highlighting that our primal-dual framework applies to both NP-hard and polynomial-time solvable problems. While this is true, we emphasize that our main contribution lies in the NP-hard domain. In NAR, NP-hard tasks were previously underexplored due to the lack of optimal solutions and the complexity of the problems. Therefore, we focus on extending NAR beyond exact algorithms for tractable problems and into the space of approximation algorithms for NP-hard tasks. Furthermore, the goals are different. In tractable problems, the aim is to simulate an algorithm that *already* produces optimal solutions. In our case, the objective is to outperform the approximation algorithm itself. To do this, we leverage optimal solutions from integer programming solvers, which is only meaningful in the NP-hard setting. As a result, we evaluate performance based on solution quality (weight ratio), rather than accuracy as commonly used in prior NAR work on tractable problems. We elaborate on this point in the next response.\n\n\n> I remain concerned about the construction of effective training and testing sets, as obtaining reliable ground truth for NP-hard problems is inherently challenging.\n\nWe clarify that only *training* requires obtaining ground-truth labels. Since we train on small problem instances on the scale of 16, these are fast to obtain with integer programming solvers like HiGHS and Gurobi. Then, we *test* against the approximation algorithm on larger problems. As shown in the caption of Table 1, the metric we use is the *model-to-algorithm weight ratio*: the sum of weights from the model solution divided by the sum of weights from the algorithm solution ($w_{model}/w_{algo}$). Therefore, a weight ratio < 1 means the model produces higher-quality solutions than the algorithm. In summary, we show that training on these small optimal instances enables the model to outperform the algorithm on larger problems (up to scale of 1024).\n\n\n> For NP problems, should the authors consider multiple approximation algorithms rather than a single one?\n\nThank you for suggesting this! Yes, training an NAR model on multiple algorithms simultaneously has been proven to be effective [1, 2]. Therefore, we hypothesize that our models can also enjoy multi-task learning benefits by training on multiple approximation algorithms simultaneously. However, the multi-task training setup requires more intricate designs, such as the selection of approximation algorithm pairs/sets and architectural design. We believe this is outside the scope of the current paper, but it points to a meaningful direction for future work: how multi-task learning transfers from exact algorithms to approximation algorithms for NAR. We will add these points to Future Work in the revised paper. \n\nWe sincerely thank the reviewer for your valuable feedback and highlighting interesting future directions. We hope we answered your questions, and please don’t hesitate if you require further clarification. Thank you very much! \n\n\n[1] A Generalist Neural Algorithmic Learner, Ibarz et al, LoG 2022.  \n[2] How to transfer algorithmic reasoning knowledge to learn new algorithms? Xhonneux et al., NeurIPS 2021.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "This paper extends the traditional NAR to NP-hard problems", "essential_references_not_discussed": "yes", "other_strengths_and_weaknesses": "Strengths:\n1. This paper extends traditional NAR to NP-hard problems, which I find meaningful and valuable.\n2. The paper provides solid theoretical support for its approach.\n3. The writing is clear, and the paper is well-structured and well-organized.\n\n\nWeaknesses:\n\n1. The proposed method aims to directly learn approximation algorithms for NP-hard tasks. However, the authors only discuss three NP-hard problems related to graphs, which may limit the generality of their approach.\n\n2. I am curious about how this method performs on problems that are not NP-hard. If it can effectively approximate both NP and non-NP problems, it would make the approach even more compelling.\n\n3. For NP problems, should the authors consider multiple approximation algorithms rather than a single one?\n\n4. I remain concerned about the construction of effective training and testing sets, as obtaining reliable ground truth for NP-hard problems is inherently challenging.", "other_comments_or_suggestions": "see weakness", "questions_for_authors": "see weakness", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S95631gg2d", "reviewer": "Reviewer_WLAv", "summary": "The authors present a neural architecture adopting the primal-dual framework, as studied in algorithm design especially for the approximation of NP-hard problems.  Using the minimum hitting set as the primary case study, the authors prove the proposed architecture satisfies the requirement of algorithmic alignment, i.e., it can replicate the intermediate states produced by the actual algorithm as described in Algorithm 1.  Importantly, the authors propose a training strategy enabling the neural architecture to learn from small instances with known solutions.  Beyond replicating the algorithm, the resulting neural solver can surpass the quality of the solvers used to train it, and the embeddings computed by the trained neural architecture can have other benefits.  A comprehensive suit of experiments adequately support those claims, establishing the efficacy of the proposed approach.  Further valuable discussion is presented in the appendices, e.g., more discussion of related work, as well as a summary of limitations.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your time carefully **reading our main paper and appendices** and for **strongly supporting** our paper! Thank you for highlighting our experiments and discussion in the appendix as comprehensive and helpful.  \n\nWe answer your questions in the following:  \n\n> I was hoping the authors would do an ablation study of the uniform update rule.\n\nWe conducted an ablation by comparing the model with and without the uniform update rule on the MHS (minimum hitting set) problem. Recall that the primal-dual approximation algorithm for MHS requires the uniform update rule. Results in Table R1 show that the uniform update rule design in our model helps to improve the model performance due to its better alignment with the algorithm. \n\nTable R1. Ablation of the uniform update rule on MHS.\n\n| Uniform update rule | 16 (1x)           | 32 (2x)           | 64 (4x)           | 128 (8x)          | 256 (16x)         | 512 (32x)         | 1024 (64x)        |\n|----------------------|-------------------|-------------------|-------------------|-------------------|-------------------|-------------------|-------------------|\n| No                   | 0.996 ± 0.003     | 0.983 ± 0.010     | 0.999 ± 0.013     | 0.987 ± 0.013     | 0.977 ± 0.005     | 1.009 ± 0.013     | 1.060 ± 0.028     |\n| Yes                  | 0.990 ± 0.003     | 0.981 ± 0.003     | 0.983 ± 0.006     | 0.965 ± 0.005     | 0.979 ± 0.005     | 1.004 ± 0.013     | 1.043 ± 0.022     |\n\n\n\n\n> I see Appendix F mentions possible strengthening using ``other advanced techniques'' without specifics. It would have helped to even hint at 1-2 such techniques.\n\n\nYes, similar to the uniform update rule, there are other advanced techniques to enhance the basic primal-dual framework to design approximation algorithms. One example is selectively choosing the number of dual variables to increase at each timestep, strengthening scalability. Another example is specialized handling of dual variables with different types, which is required for the uncapacitated facility location problem. These techniques can be incorporated into our framework as extensions, which we leave for future work. We will add more specifics and examples about these techniques in our revised paper. \n\n> Only glanced at the proofs in Appendix B... It would help to recall the pseudocode, highlighting which part is being mirrored at each proof step. \n\nThanks for reading our proof and providing helpful suggestions on its readability! We will include a side-by-side reference to the algorithm’s pseudocode in Appendix B. And thank you for pointing out the typo. We will fix it in our revision as well. \n\n\nWe are grateful for your support and hope we have addressed your questions. Please let us know if you require further clarification. Thank you very much!", "claims_and_evidence": "- A key claim is algorithmic alignment, which is supported by a theoretical proof in Appendix B.\n- Empirical results further demonstrate the efficacy of the approach and proposed architecture.", "methods_and_evaluation_criteria": "The contributions are supported by a comprehensive set of evaluations of synthetic, OOD, and real-world datasets, along with a comparison to commercial solvers.", "theoretical_claims": "Only glanced at the proofs in Appendix B.  The presented strong induction seems to make sense.  It's a bit difficult to follow given its length, mirroring the steps of the algorithm.  It would help to recall the pseudocode, highlighting which part is being mirrored at each proof step.\n\nOne remark: the last line mentioned $\\Theta_{\\text{dual}}$ while I expected $\\mathcal{M}_\\Theta$.", "experimental_designs_or_analyses": "Each section seemed to use reasonable datasets, e.g., known graph families, datasets used in prior studies, or comparing to established solvers.", "relation_to_broader_scientific_literature": "The authors adequately discuss related works in algorithm theory, neural reasoning, neural combinatorics optimization, and linear programming.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I was hoping the authors would do an ablation study of the uniform update rule.", "other_comments_or_suggestions": "I see Appendix F mentions possible strengthening using ``other advanced techniques'' without specifics.  It would have helped to even hint at 1-2 such techniques.", "questions_for_authors": "No further questions at this time.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OAoTdy1JKK", "reviewer": "Reviewer_aupK", "summary": "This work proposed a framework PDNAR, that lies within the neural algorithmic reasoning framework, uses a bipartite MPNN to simulate the primal dual algorithm on solving minimum hitting set problem and its extensions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and highlighting the strengths of our paper, which we summarize below.\n- Paper: **well-written** and **easy to follow**\n- Problem definition: **solid** \n- Novelty:  **significant**\n- Benchmark datasets: **good**\n- Empirical results: **strong** \n\nWe address your questions in the following: \n\n> I check the proof in the appendix. The assumption of MPNN is that it uses MLPs. But there exist some functions like ln or fractional that cannot directly be simulated by MLPs.\n\nThanks for checking our proof in the appendix! As shown in Line 767, the logarithm is hard-coded as a feature transformation, and thus is not to be simulated by MLPs. The logarithm is used so that the fractional/division can be achieved by subtraction followed by the ELU activation function. This avoids simulating division with MLPs. \n\n> You remove the variables in the bipartite graph by masking them out, but how? By assigning 0s? Does it influence batchnorm or something? \n\nWhen removing a variable, we remove all its edges in the bipartite graph, so it does not effectively participate in future message-passing steps. The edges are removed by applying a true/false mask. Empirically, we do not apply BatchNorm. \n\n> Could you explain more what is the NAR baseline and how is it essentially different from PDNAR? Because PDNAR is also NAR.\n \nThe processor of PDNAR was specially designed to align with the primal-dual approximation algorithm (Section 4.1). For the NAR baseline, we use the conventional choice of MPNN with max aggregation (e.g. [1]). Furthermore, the NAR baseline does not use the primal-dual bipartite formulation, and therefore, is only trained on the primal but not the dual signal. Results align with the previous findings that multi-task learning helps in NAR (e.g. [1]). We will edit “Baselines” in Section 5.1 to highlight the differences and architectural details for the NAR baseline. \n\n> The algorithm 1 is hard to read without explanation. Some notations are messy. \n\nThank you for pointing out the areas that we can improve for the readability! We will enhance the explanation of the algorithm in Section 3.3 and make the pseudocode more intuitive to understand. We will also include a notation table and ensure the notational consistency in our revised paper.\n\nWe thank the reviewer for your valuable feedback. We hope these answer your questions, and please let us know if you require further clarification. Thank you very much!\n\n\n[1] Neural Execution of Graph Algorithms, Veličković et al, ICLR 2020.", "claims_and_evidence": "They provided theoretical proof that MPNN can simulate the algorithm. \nThey provided experimental results that PDNAR outperforms the baselines in all the experiments.", "methods_and_evaluation_criteria": "The problem definition is solid, the proposed method makes sense and the benchmark datasets (both real world and synthetic) are good.", "theoretical_claims": "I check the proof in the appendix. \nThe assumption of MPNN is that it uses MLPs. But there exist some functions like ln or fractional that cannot directly be simulated by MLPs.", "experimental_designs_or_analyses": "I checked all the experiments.", "relation_to_broader_scientific_literature": "The work focused on MHS problem and its extensions, which are some essential families of CO problems.\nThe work also established the effectiveness of bipartite representation and MPNN approach for the primal dual algorithm.", "essential_references_not_discussed": "Not that I know, they discussed wide related work in the appendix as well.", "other_strengths_and_weaknesses": "Strength:\n- Overall the paper is well written and easy to follow. \n- The novelty is significant, and the experiment results are pretty strong.\n\nWeakness:\n- The algorithm 1 is hard to read without explanation.", "other_comments_or_suggestions": "Some notations are messy, for example some symbols $E, A$ are overridden without clarifying.", "questions_for_authors": "- You remove the variables in the bipartite graph by masking them out, but how? By assigning 0s? Does it influence batchnorm or something?\n- Could you explain more what is the NAR baseline and how is it essentially different from PDNAR? Because PDNAR is also NAR.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes to train neural networks that can simulate classical approximative algorithms for optimization problems. The underlying GNNs can simulate primal-dual algorithms. Experimentally, their method is able to outperform some baselines on a few classical combinatorial problems.
Reviewers note good experimental results, novelty and being well-written and all recommend acceptance. The rebuttal is also positively acknowledged. Therefore the final recommendation is also to acept the paper.
Decision: Accept (spotlight poster)