Differentiable Quadratic Optimization For the Maximum Independent Set Problem
Authors: Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, Alvaro Velasquez
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experimental results demonstrate the effectiveness of the proposed method compared to exact, heuristic, sampling, and data-centric approaches. Notably, our method avoids the out-ofdistribution tuning and reliance on (un)labeled data required by data-centric methods, while achieving superior MIS sizes and competitive runtime relative to their inference time. Additionally, a key advantage of p CQO-MIS is that, unlike exact and heuristic solvers, the run-time scales only with the number of nodes in the graph, not the number of edges. Our code is available at the Git Hub repository (p CQO-MIS). We evaluate our approach on challenging benchmark graph datasets, demonstrating its efficacy. Our method achieves competitive or superior performance compared to state-of-the-art heuristic, exact, and data-driven approaches in terms of MIS size and/or run-time. |
| Researcher Affiliation | Academia | 1University of Michigan, Ann Arbor 2Michigan State University 3Ohio State University 4University of Maryland, College Park 5University of Colorado, Boulder. Correspondence to: Ismail R. Alkhouri <EMAIL; EMAIL>. |
| Pseudocode | Yes | Algorithm 1 p CQO-MIS. Input: Graph G = (V, E), set of initializations Sini, number of iterations T per one initialization, edge-penalty parameter γ, MC term parameter γ , and MGD parameters: Step size α, and momentum parameter β. Output: The best obtained Max IS I in G 01: Initialize SMax IS = { } (Empty set to collect Max ISs) 02: For x[0] Sini (Parallel Execution) 03: Initialize v[0] 0 04: For t [T] 05: Obtain g(x[t 1]) = en +(γAG γ AG )x[t 1] 06: Obtain v[t] = βv[t 1] + αg(x[t 1]) 07: Obtain x[t] = Proj[0,1]n(x[t 1] v[t]) 08: Obtain z[T] with zv[T] = 1(xv[T] > 0), v V 09: If 1 z[T] = Proj[0,1]n z[T] αg(z[T]) 10: Then SMax IS SMax IS I(z[T]) 11: Return I = argmax I SQ |I| |
| Open Source Code | Yes | Our code is available at the Git Hub repository (p CQO-MIS). Our code is available online3. (footnote 3: https://github.com/ledenmat/p CQO-mis-benchmark) |
| Open Datasets | Yes | Aligned with recent methods (DIMES, DIFUSCO, and i SCO), we employ the Erdos-Renyi (ER) (Erdos et al., 1960) graphs from (Qiu et al., 2022) and the SATLIB graphs from (Hoos & St utzle, 2000) as benchmarks. Additionally, the GNM random graph generator function of Network X (Hagberg et al., 2008) is utilized for our scalability experiment in Section 4.3. Results for the DIMACS graphs (Johnson & Trick, 1996), larger ER graphs, and the BA graphs from (Wu et al., 2025) are given in Appendix E.1, Appendix E.2, and Appendix E.3, respectively. |
| Dataset Splits | No | The paper uses well-known benchmark datasets such as Erdos-Renyi (ER) graphs, SATLIB graphs, GNM graphs, DIMACS graphs, and BA graphs. It evaluates its method based on the average MIS size across these datasets or a subset of graphs from them. For example, 'The ER dataset consists of 128 graphs with 700 to 800 nodes and p = 0.15' and 'The SATLIB dataset consists of 500 graphs'. The evaluation is typically performed on the entire set of graphs or a specific selection (e.g., 10 ER graphs with n=3000), not using explicit train/test/validation splits as would be typical for machine learning models that are trained and tested. Therefore, no specific dataset splits are provided for reproducibility in the context of splitting data for training/validation/testing a model. |
| Hardware Specification | Yes | The p CQO-MIS, CP-SAT, and Gurobi results are run using an NVIDIA RTX3070 GPU and Intel I9-12900K CPU. Here, we also use an NVIDIA RTX3070 GPU and Intel I9-12900K CPU. In Appendix E.2, the machine used is: CPU Intel(R) Xeon(R) Gold 6418H and GPU NVIDIA RTX A6000. |
| Software Dependencies | No | The paper mentions implementing the objective function and algorithm using C++. It also uses Gurobi, CP-SAT, and Network X as baselines or for graph generation. However, it does not provide specific version numbers for any of these software components (e.g., 'Gurobi 10.0', 'CP-SAT vX.Y', 'NetworkX vA.B.C') which are necessary for reproducible software dependencies. |
| Experiment Setup | Yes | For p CQO-MIS, the hyper-parameters are set as given in Table 12 of Appendix E.9. Table 12 provides specific values for Edges-penalty γ, MC parameter γ', Step size α, Momentum β, Steps T, and Exploration parameter η for each graph dataset (SATLIB, ER, GNM). For example, for SATLIB, γ = 900, γ' = 1, α = 3e-4, β = 0.875, T = 30, η = 2.25. |