Research map / Learning theory and algorithms / Combinatorial and search optimization
Primal-Dual Neural Algorithmic Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PDNAR, a GNN framework that simulates primal-dual approximation algorithms for NP-hard covering/hitting problems over a bipartite primal-dual graph, augmented with optimal IP solutions from small instances, and shows it can outperform the algorithm it imitates.
Problem
Neural algorithmic reasoning has focused on polynomial-time exact algorithms; extending NAR to NP-hard problems is hard because ground-truth algorithm traces for them are difficult to generate reliably.
Approach
Represent primal (elements) and dual (sets) variables as the two sides of a bipartite graph so that message passing mirrors the primal-dual update steps, add a virtual node for the uniform dual increase rule, and supervise with both algorithm intermediate states and optimal IP solutions on small graphs so the model can exceed the approximation algorithm's quality.
Key results
- On MVC trained on 16-node graphs, PDNAR reaches a weight ratio of 0.943 to the algorithm at 16 nodes and about 0.957 at 1024 nodes, below the primal-dual algorithm (ratio 1).
- On the Airports datasets, GAT+PDNAR reaches 84.44% on Brazil versus 60.13% for GAT alone.
- Warm-starting Gurobi with PDNAR solutions cut mean solve time at 500 nodes from 78.97 s (no warm start) to 72.61 s, and inference took about 0.02 s versus 0.20 s for the algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add optimal-solution supervision from small instances (ablation) | PDNAR · MVC, larger graphs (trained on 16 nodes) | model-to-algorithm weight ratio: 0.995 ± 0.004 -> 0.943 ± 0.004 (16 nodes); 0.994 ± 0.011 -> 0.957 ± 0.002 (1024 nodes) | Helped |
| add intermediate supervision from the primal-dual algorithm (ablation) | PDNAR · MVC, larger graphs (trained on 16 nodes) | model-to-algorithm weight ratio: 1.142 ± 0.038 -> 0.943 ± 0.004 (16 nodes) | Helped |
| use the default aggregation instead of mean aggregation (ablation) | PDNAR · MVC, 16 nodes | model-to-algorithm weight ratio: 1.031 ± 0.022 -> 0.943 ± 0.004 | Helped |
| use the default aggregation instead of max aggregation (ablation) | PDNAR · MVC, 16 nodes | model-to-algorithm weight ratio: 0.968 ± 0.014 -> 0.943 ± 0.004 | Helped |
| use PDNAR instead of the approximation algorithm for Gurobi warm starts | Gurobi on MVC · 500, 600, and 750 nodes | solve time (s): 76.69 -> 72.61; 227.83 -> 209.52; 300.12 -> 292.92 | Helped |
| add PDNAR embeddings to the GCN node classifier | GCN on Airports · Airports Brazil, Europe, and USA | accuracy (%): 73.33 -> 81.11; 74.75 -> 76.88; 79.54 -> 82.82 | Helped |
Surprising findings
- Training with only algorithm intermediate states (No optm) gives ratios near 1, while adding optimal IP solutions from small graphs pushes the model below the algorithm's approximation quality.
Limitations
- Architecture is designed for hitting-set-type problems; problems like uncapacitated facility location need architectural extensions.
- Results on the Gurobi warm-start experiment are reported for a single 1-hour time-limit setup with a modest gain over no warm start.
- Model needs optimal IP solutions on small instances for supervision, which become expensive as instance size grows.
Experimental setup
Datasets: Barabási-Albert graphs (16 nodes) Barabási-Albert bipartite graphs Airports (Brazil, Europe, USA)
Benchmarks: Synthetic MVC/MSC/MHS test graphs up to 1024 nodes OOD graph families (E-R, Star, Lobster, 3-Con) Airports node classification Gurobi warm start on 500-750 node B-A graphs
Metrics: model-to-algorithm weight ratio classification accuracy solve time compute time
Baselines: GIN GAT NAR (MPNN) TripletMPNN GCN Node2Vec LapPE RWPE Gurobi default initialization
Builds on: CLRS neural algorithmic reasoning blueprint NAR (MPNN) processor TripletMPNN Ford-Fulkerson NAR with duality
Closest papers by meaning
- Deep Equilibrium Algorithmic Reasoning (NeurIPS 2024 · similarity 0.88)
- Open-Book Neural Algorithmic Reasoning (NeurIPS 2024 · similarity 0.86)
- Discrete Neural Algorithmic Reasoning (ICML 2025 · similarity 0.85)
- Understanding Transformer Reasoning Capabilities via Graph Algorithms (NeurIPS 2024 · similarity 0.85)
- Neural Reasoning Networks: Efficient Interpretable Neural Networks with Automatic Textual Explanations (AAAI 2025 · similarity 0.85)
- On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.