Primal-Dual Neural Algorithmic Reasoning
Authors: Yu He, Ellen Vitercik
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5. Experiments. Dataset distributions and hyperparameter details of all experiments are provided in Appendices C, D, and E. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Stanford University, Stanford, CA, USA 2Department of Management Science & Engineering, Stanford University, Stanford, CA, USA. Correspondence to: Yu He <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 General primal-dual approximation algorithm. Algorithm 2 COVER(G = (V, E), w, ϵ). Algorithm 3 COVER(G = (V, E), w, ϵ). |
| Open Source Code | Yes | Our code can be found at https://github.com/dransyhe/pdnar. |
| Open Datasets | Yes | Dataset We evaluate PDNAR s ability to simulate the approximation algorithms for the three NP-hard algorithmic problems described in Section 3.2. The training dataset includes 1000 random graphs of size 16 for each task. We use Barabási-Albert graphs for vertex cover. For set cover and hitting set, we generate Barabási-Albert bipartite graphs with a preferential attachment parameter b = 5. Each test set consists of 100 graphs and is repeated for 10 seeds. We showcase such an application using the Airports datasets (Brazil, Europe, USA) (Ribeiro et al., 2017). |
| Dataset Splits | Yes | The training dataset includes 1000 random graphs of size 16 for each task. ... Each test set consists of 100 graphs and is repeated for 10 seeds. For the vertex cover problem, we generate three OOD test sets comprising Erd os Rényi (ER), Star, Lobster, and 3-connected planar (3-Con) graphs. We create 10 random train/val/test splits for the transductive task with a ratio of 60%/20%/20%. |
| Hardware Specification | Yes | 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. |
| Software Dependencies | Yes | Furthermore, the optimal solutions are generated with the default IP solver in scipy, which is based on Hi GHS (Schwendinger & Schumacher, 2023; Huangfu & Hall, 2018). R package version 0.1-10. Table 8. ... Gurobi 9.5 ( 1.00s) ... Gurobi 9.5 ( 2.00s) We use the default TPE hyperparameter search algorithm from optuna (Akiba et al., 2019) with a median pruner. |
| Experiment Setup | Yes | For training, we use the Adam optimizer with an initial learning rate of 1e-3 and weight decay of 1e-4, coupled with the Reduce LROn Plateau scheduler with default settings. Additionally, we use a batch size of 32, a hidden dimension of 32, and a maximum of 100 epochs. Table 7. Additional hyperparameters for real-world dataset experiments. Brazil Europe USA GCN lr=0.0005 lr=0.001 lr=0.001 hid_dim=32 hid_dim=32 hid_dim=64 dropout=0.5 dropout=0.1 dropout=0.3 num_layer=3 num_layer=3 num_layer=3 |