Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Graph Alignment via Birkhoff Relaxation
Authors: Sushil Varma, Irène Waldspurger, Laurent Massoulié
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct simulations on the Gaussian Wigner Model to verify our results and provide further insights (The code is publicly available at https://github.com/smv30/convex_rel_ for_graph_alignment). We set n = 400 (unless otherwise specified) and consider σ {0, 0.1, 0.2, . . . , 1}. For these parameters, we test the performance of three convex relaxations: GRAMPA [11], simplex [2], and Birkhoff. We set the regularization parameter to 0.2 in GRAMPA as suggested by the authors. The convex relaxations are solved using the cvxpy library in Python using SCS (Splitting Conic Solver) and we set use_indirect to True, recommended for large instances for better memory management. We then project the solution of the convex relaxation to the set of permutation matrices using the Hungarian algorithm. For each n and σ, we repeat the simulation 10 times and report the average fraction of correctly matched vertices in Figure 1. |
| Researcher Affiliation | Academia | Sushil Mahavir Varma Industrial and Systems Engineering University of Michigan Ann Arbor Michigan, USA EMAIL Irène Waldspurger CNRS, INRIA Université Paris Dauphine Paris, France EMAIL Laurent Massoulié INRIA, DI/ENS PSL Research University Paris, France EMAIL |
| Pseudocode | No | The paper describes mathematical formulations of algorithms and discusses their theoretical properties and empirical performance, but it does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | We conduct simulations on the Gaussian Wigner Model to verify our results and provide further insights (The code is publicly available at https://github.com/smv30/convex_rel_ for_graph_alignment). |
| Open Datasets | No | We conduct simulations on the Gaussian Wigner Model to verify our results and provide further insights... We say that A, B Rn n follows the Gaussian Wigner Model when for all i, j [n], we have Bπ (i),π (j) = Aij+σZij, where A, Z are i.id. GOE matrices |
| Dataset Splits | No | The paper describes generating data based on the Gaussian Wigner Model for simulations, setting parameters like n and σ, and repeating simulations. It does not refer to fixed datasets with explicit training/test/validation splits. |
| Hardware Specification | No | We run the simulations on a CPU with 50GB of memory and impose a maximum run time of 3 hours for each instance. |
| Software Dependencies | No | The convex relaxations are solved using the cvxpy library in Python using SCS (Splitting Conic Solver) and we set use_indirect to True, recommended for large instances for better memory management. |
| Experiment Setup | Yes | We set n = 400 (unless otherwise specified) and consider σ {0, 0.1, 0.2, . . . , 1}. For these parameters, we test the performance of three convex relaxations: GRAMPA [11], simplex [2], and Birkhoff. We set the regularization parameter to 0.2 in GRAMPA as suggested by the authors. The convex relaxations are solved using the cvxpy library in Python using SCS (Splitting Conic Solver) and we set use_indirect to True, recommended for large instances for better memory management. |