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
Venue: ICML 2025 poster (2025)
Keywords: Maximum Independent Set
Quadratic optimization
Gradient Descent
Combinatorial Optimization
Primary area: optimization->discrete_and_combinatorial_optimization

Abstract: Combinatorial Optimization (CO) addresses many important problems, including the challenging Maximum Independent Set (MIS) problem. Alongside exact and heuristic solvers, differentiable approaches have emerged, often using continuous relaxations of quadratic objectives. Noting that an MIS in a graph is a Maximum Clique (MC) in its complement, we propose a new quadratic formulation for MIS by incorporating an MC term, improving convergence and exploration. We show that every maximal independent set corresponds to a local minimizer, derive conditions with respect to the MIS size, and characterize stationary points. To tackle the non-convexity of the objective, we propose optimizing several initializations in parallel using momentum-based gradient descent, complemented by an efficient MIS checking criterion derived from our theory. We dub our method as **p**arallelized **C**lique-Informed **Q**uadratic **O**ptimization for MIS (pCQO-MIS). 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-of-distribution tuning and reliance on (un)labeled data required by data-centric methods, while achieving superior MIS sizes and competitive run-time relative to their inference time. Additionally, a key advantage of pCQO-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 GitHub repository: https://github.com/ledenmat/pCQO-mis-benchmark/tree/refactor.

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Ismail R. Alkhouri 12 Cedric Le Denmat 3
Yingjie Li Cunxi Yu Jia Liu Rongrong Wang? Alvaro Velasquez
Abstract
1. Introduction
Combinatorial Optimization (CO) addresses many important problems, including the chal- lenging Maximum Independent Set (MIS) prob- lem. Alongside exact and heuristic solvers, dif- ferentiable approaches have emerged, often us- ing continuous relaxations of quadratic objectives. Noting that an MIS in a graph is a Maximum Clique (MC) in its complement, we propose a new quadratic formulation for MIS by incorporating an MC term, improving convergence and exploration. We show that every maximal independent set cor- responds to local minimizer, derive conditions with respect to the MIŞ size, and characterize sta- tionary points. To tackle the non-convexity of the objective, we propose optimizing several initial- izations in parallel using momentum- based gra- dient descent, complemented by efficient MIS checking criterion derived from our theory. We dub our method as parallelized Clique-Informed Quadratic Optimization for MIS (pCQO-MIS). Our experimental results demonstrate the effec- tiveness of the proposed method compared to exact, heuristic, sampling, and data-centric ap- proaches. Notably, our method avoids the out-of- distribution tuning and reliance on (un)labeled data required by data-centric methods, while achieving superior MIS sizes and competitive run- time relative to their inference time. Additionally, a key advantage of PCQO-MIS is that, unlike ex- act and heuristic solvers, the run-time scales only the
In his landmark paper (Karp, 1972), Richard Karp estab- lished connection between Combinatorial Optimization Problems (COPs) and the NP-hard complexity class, imply- ing their inherent computational challenges. Additionally, Richard Karp introduced the concept of reducibility among combinatorial problems that are complete for the complexity class NP.
Although there exists direct reduction between some COPs such as the case with the Maximum Independent Set (MIS), Maximum Clique (MC), and Minimum Vertex Cover (MVC) - which allows a solution for one problem to be di- rectly used to solve another, other COPs differ significantly. For example, there exists no straightforward reduction be- tween MIS and the Kidney Exchange Problem (KEP) (MeEl- fresh et al., 2019) (or the Traveling Salesman Problem (TSP) (Dantzig et al., 1954)).
In this paper, we focus on the MIS problem, one of the most fundamental in combinatorial optimization, with many applications including frequency assignment in wireless networks (Matsui & Tokoro, 2000), task scheduling (Eddy & Kochenderfer, 2021), and genome sequencing (Joseph et al., 1992; Zweig et al., 2006).
The MIS problem involves finding a subset of vertices in a graph G = (V, E) with maximum cardinality, such that no two vertices in this subset are connected by an edge (Tarjan & Trojanowski, 1977). In the past few decades, in addi- tion to commercial Integer Programming (IP) solvers (e.g.. CPLEX (IBM), Gurobi (Gurobi), and most recently CP- SAT (Perron & Didier)), powerful heuristic methods (e.g.. ReduMIS in (Lamm et al., 2016)) have been introduced to tackle the complexities inherent in the MIS problem. Other solvers can be broadly classified into aanch-and-bound based global optimization methods (Akiba & Iwata, 2016), and approximation algorithms (Boppana & Halldórsson, 1992).
with the number of nodes in the graph, number of edges. Our code is available at the GitHub repository (pCQO-MIS).
University of Michigan, Ann Arbor Michigan State University "Ohio State University "University of Maryland, College Park 2 Universiity of Colorado, Boulder. Correspondence to: Ismail R. msu.cdu>.
Alkhouri <ismailal umi
More recently, differentiable approaches have been explored (Bengio et al., 2021), falling into two main categories: (i) data-driven methods, where a neural network (NN) is trained to fit a distribution over training graphs, and (ii) dataless
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
methods (Alkhouri et al., 2022; Schuetz et al., 2022). Both approaches rely on some formulations of the MIS problem, such the continuous relaxation of the MIS Quadratic Un- constrained Binary Optimization (QUBO) or ReLU-based objective functions. However, data-driven methods often suffer from unsatisfactory generalization performance when faced with graph instances whose structural characteristics differ from those in the training dataset (Böther al., 2022: Gamarnik, 2023).
2. Preliminaries
Consider an undirected graph represented as G (V, where V is the vertex set and E S V VVVin is the edge set. The number of nodes (resp. edges) is denoted by V (resp. |E] = m), where | denotes the cardinality of set. Unless otherwise stated, for node E V, we use N(e) = {u E V (u, E }} to denote the set of its neighbors. The degree of a node e E V is denoted by d(u) = [V('),, and the maximum degree of the graph by (G). For a subset of nodes U C V, we use G[U] = (U, E(UJ) represent the subgraph induced by the nodes in U, where E[U] {(u, u) E u, U E U}. Given graph G. its complement is denoted by G' = (V, E"), where E' = V x V E is the set of all the edges between nodes that are not connected in G. Consequently, if |E"| = m'. then m + mm' = n - 1)/2 represents the number of edges in the complete graph on V. For any v E V. (" = {u E V ((uuu) v) E E'} denotes the neighbor set of in the complement graph G' (V, E.). The adjacency matrix of graph G is denoted by Ac E {0, 1jmxx. We use I to denote the identity matrix. The trace of matrix A is denoted by Ir( AA) For any positive integer n, [v] := (1,...,,)) n). The vector (resp. matrix) of all ones and size n (resp. n x n) is denoted by e, (resp. Jn = e,,))) Furthermore, we use 1(-) to denote the indicator function that returns (resp. 0)
Notations:
In this paper, we present new differentiable dataless solver for the MIS problem based on an improved quadratic op- timization formulation, a parallel optimization strategy. and momentum- gradient descent, which we dub as parallelized Clique-Informed Quadratic Optimization for the MIS problem (pCQO-MIS). The contributions of our work are summarized follows:
1. MIS Quadratic Formulation with MC Term: Lever- aging the direct relationship between the MIS and MC problems, we propose a new formulation that incorpo- rates an MC term into the continuous relaxation of the MIS quadratic formulation.
2. Theoretically:
We derive a sufficient and necessary condition for the parameter that penalizes the inclusion of adjacent nodes and the MC term parameter with respect to (w.r.t.) the MIS size.
when its argument is True (resp. False).
Problem Statement: In this paper, we consider the NP- hard problem of obtaining the maximum independent set (MIS). Next, we formally define MIS and the complemen- tary Maximum Clique (MC) problems.
We show that all local minimizers are binary vectors that sit on the boundary of the box constraints, and establish that all these local minimizers correspond to maximal independent sets.
Definition (MIS Problem). Given an undirected graph G (V,F), the goal of MIS is to find a subset of vertices I C such that [(I)) = 0, and [I] is maximized.
We prove that if non-binary stationary points exist, they are saddle points and not local minimizers, with their existence depending on the graph type and con- nectivity.
Definition 2 (MC Problem). Given undirected graph = E), the goal of MC is to find a subset of vertices C V such that G[C) is complete graph, and [C] is maxi- mized.
3. Optimization Strategy: To improve exploration with our non-convex optimization, we propose the use of GPU parallel processing of several initializations for each graph instance using projected momentum-basee gradient descent.
For the MC problem, the MIS of a graph is an MC of the complement graph (Karp, 1972). This means that MIS Z in G is equivalent MC C in G².
4. Efficient MIS Checking: Drawing from our theoretical results on local minimizers and stationary points, we develop an efficient MIS checking function that signifi- cantly accelerates our implementation.
Given a graph G, if I is Maximal Independent Set (MaxIS), then E([Z) 0. but [Z] is not necessarily the largest in G. If I is an Independent Ser (IS) that it is not maximal, then E(() is an empty set, but there exists at least one & I such that
5. Experimental Validation:
We evaluate our approach challenging benchmark graph datasets, demonstrating its efficacy. Our method achieves competitive or superior performance compared to state-of-the-re art heuristic, exact, and data data-driven approaches in terms of MIS size and/or run-time.
E(Z U {x))) = 0
(1)
See Figure 1 for an example. We note that, in this paper, we use MIS and MaxIS interchangeably.
Let zu be an entry of the binary vector z E {0, 13" that corresponds to a node E V. The integer linear program
2

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Y 2 1, introduced discourage sparsity in the solution. The function f(x) can also be expressed as
f(x)
Σx X +Y DEV
Σ
X,Xu
Σ
X,
(u,D)E
(,,D)E
G = E)
G' (V,
Utilizing the identity
Figure A graph G (lef)) and its complement graph G' (right). Sets MIS; = {Ui, 24 83} and MIS₂ = {13, 11 )s} correspond maximum independent set in G and an MC in G'. Set MaxIS (2) corresponds to maximal independent set as its not of maximum cardinality. Set IS = {ei, is not maximal independent set because IS U {us} is equivalent to MIS] = {v1, U4, Us}.
A = J, I- AG
(5)
x² x = ||x 1. and the non-negative entries of x for which we can write ||x[| = x" J'x, our proposed function can be rewritten as
7+ 2
2 A + 7/2 (1x1 |x (6)
((x) = -
In particular, we incorporate ry that penalizes edges in graph G on the optimization objective. The third term is informed by the duality between the MIS and MC problems.
(ILP) for MIS is (Nemhauser & Trotter, 1975):
max =E/0,1)"
En, Z DEV
s.t. 2o Zu S V(u,u) E. (2)
The rationale behind the third term - x A in (4) (cor- responding to the edges of the complement graph G') is to (i) encourage the optimizer to select two nodes with no edge connecting them in G (implying an edge in G'), and (ii) discourage sparsity given the last term of (6).
Furthermore, the following QUBO in (3) (with optimal solution that is equivalent to the optimal solution of the above ILP) can also be used to formulate the MIS problem (Pardalos & Rodgers, 1992):
Let z" be binary minimizer of (4) with
max e (0.1))
70 - ZT AGZ.
(3)
I(z') = (0 E V x = 1}
2
Then, we have:
where To 0 a parameter that penalizes the selection of two nodes with an edge connecting them. In (Mahdavi Pa- [(a') = - = - (
(8)
jouh et al., 2013), it was shown that the condition To 1 is both sufficient and necessary for local minimizers to corre- spond to binary vectors representing MaxISs.
eEV
This expression includes only the first and third terms, as there are no edges connecting any two nodes in I(z").
In Appendix D, we review various approaches for solving the MIS problem.
Remark Given that the number of non-zero entries in
Ag 2m (with one entry for each edge in G and Ag being symmetric), the computational cost of continuous relax- ation of the QUBO formulation in (3) (with box constraints) is Omm). Because the vector-matrix multiplication in (6) is only in the second term, the computational cost of our proposed function also (mm). This means that includ- ing the MC term in our proposed objective results in the same computational cost as (3) with [0, 1]".
3. Clique-Informed Differentiable Quadratic MIS Optimization
In this section, we first introduce the quadratic optimization (CQO) formulation for the MIS prob- lem. Next, we provide theoretical insights into the objective function, and then present parallelized optimization strategy using momentum- based gradient descent (MGD).
3.2. Theoretical Insights
3.1. Optimization Reformulation Our proposed optimization reformulation is
In this subsection, we provide theoretical insights where we first examine the constant Hessian of fx) in (4). Then, we provide the necessary and sufficient condition for y and y for any MaxIS to correspond to local minimizers of (4). Moreover, we also provide sufficient condition for all local minimizers of (4) to be associated with a MaxIS. Additionally, we show that if non-binary stationary points exist, they are saddle points. We relegate the detailed proofs to Appendix A.
xxx A 2 Ix Axx (4) 2
min f(x) == e 1
where 7 > 1, analogous to YQ in (3), serves as the edge
penalty parameter. The third term represents the maximum clique (MC) term we propose this paper, with parameter
3

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Definition 3 (MaxIS vector). Given a graph G (V, E), a binary vector 10, is called MaxIS vector if there exists MaxIS I of G such that x, = 1 for all i E I, and X; = O for all i & I.
minimizers ISs. Then, we show that any IS, that is not maximal, is not local minimizer.
The assumption y 1+ ((") in Theorem 2 is stronger than that in Theorem 1. The trade-off of selecting larger value is that, while it ensures that only MaxISs are local minimizers, it also increases the non-convexity of the optimization problem, making it more challenging to solve.
Remark 3.
Lemma 1. For any non-complete graph G, the constant hessian of f(x) in (4), i.e., yAG - AaG is always a nnn-posiivv-semideffne (non-PSD) matrix.
Proof Sketch: Here, show that the Hessian is non- PSD matrix by showing that for any MaxIS vector the condition x" (yAg 7 Arr x 2 0 can not be satisfied.
Remark 4. Although the proposed box- cox-constrained quadratic Problem (4) is still NP-hard solve for the global minimizer(s), it is a relaxation of the original integer programming problem. It can leverage gradient informa- tion, allowing the use of high-perffrmanee computational resources and parallel processing to enhance the efficiency and scalability of our approach.
The result in Lemma indicates that our quadratic optimiza- tion problem always non-convex for any non-complete graph. The work in (Burer & Letchford, 2009) discusses the complexity of box-constrained continuous non-convex quadratic optimization problems.
Theorem 1 (Necessary and Sufficient Condition on and ' for MaxIS vectors to be local minimizers of (4)). Given an arbitrary graph G = (V, E) and its corresponding for- mulation in (4), suppose the size of any MIS of G is k. Then, y 2 1+ necessary and sufficient for all MaxIS vectors to be local minimizers of for arbitrary graphs.
In the following theorem, we provide results regarding points where the gradient of [(x) is zero
Theorem 3 (Non-Extremal Stationary Points). For any graph G. assume that there exists point x' such that vxf(x')= = 0, i.e.
Proof Sketch: Given MaxIS I with [I| = k, we derive the bound by considering the boundary points enforced by the box-constraints, and the gradient of [xx w.r.t. some
x' : (1AG - -'A.)
(10)
Then, x' is not local minimizer of (4) and therefore does not correspond to MaxIS.
U E I.. I.
Remark 2. Theorem offers guidance on selecting 7 and y While the MIS set size & is typically unknown in advance, it's possible to use classical estimates of k to inform the choice of these parameters. For example, as shown in (Wei, 1981),& & can be bounded by
Proof Sketch: We show that x' is not local minimizer by showing that it can not be binary, building upon the result on Lemma 2.
Remark 5. The above theorem implies that while there may exist a non-binary stationary point , a saddle point, not a local minimizer, as indicated by the zero gradient vector and by Lemma (the Hessian is always non-PSD). Momentum-based Gradient Descent (MGD) is typically ef- fective at escaping saddle points and converging to local minimizers, which serves as one motivation of its use in PCQO-MIS. Furthermore, we observe that this specific sad- dle point is never encountered in our empirical evaluations and that depends on the structure of the graph. In many in- stances, lies outside the box constraints, depending on the graph's density and connectivity. Further discussion about the existence of saddle points is provided in Appendix C.
Σ 1-)
(9)
"EV
which could provide a useful estimate for this purpose.
Next, we provide further characterizations of the local mini- mizers of (4).
Lemma 2. All local minimizers of (4) are binary vectors.
Proof Sketch: We prove this by showing that for any coordi- nates of x with non- non-binary values, one necessary condition for any local minimizer can not be satisfied.
Building on the result of Lemma 2, we provide a stronger condition on y and 7f that ensures all local minimizers of (5) correspond to a MaxIS.
3.3. Optimization Strategy
Theorem 2 (Local Minimizers of (4)). Given graph G = (V, E) and yet > 1 1+'))(G") all local minimizers of (4) are MaxIS vectors of G.
Given the highly non-convex nature of our optimization problem, this section introduces the PCQO-MIS method for efficiently obtaining MaxISs. We first describe the projected MGD and parallel initializations used. Then, we present the efficient MaxIS checking criterion, followed by a detailed outline of the algorithm.
Proof Sketch: By Lemma 2. we examine the local mini- mizers that are binary. With this, we prove that all local
4

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
3.3.1. PROJECTED MOMENTUM-BASED GRADIENT DESCENT
3.3.3. EFFICIENT IMPLEMENTATION OF MAXIMAL IS CHECKING
As previously discussed, our function in (4) is highly non- convex which makes finding the global minimizer(s) chal- lenging task. However, first-order gradient- based optimizers are effective for finding a local minimizer given an initial- ization in [0, 1l".
Given a binary vector E {0, with
I(z) = {u E V Zu = =],
(14)
the standard approach to check whether it is IS and then whether it is a MaxIS involves iterating over all nodes to examine their neighbors. Specifically, this entails verifying that (7) no two nodes (v, u) E E with Z, = Z, = exist (IS checking), and (it) there does not exist any u & I(z) such that Ve E I()), u É (V(w) (MaxIS checking). How- ever, as the order and density of the graph increase, the computational time required for this process may become significantly longer.
Given the full differentiability of the objective in (4), with the gradient vector defined as
g(x) = Vx/(x) e,, (7AG - Y )x, (II)
MGD empirically proves to be computationally efficient. Specifically, let E RR,, 3 E (0, 1), and 0 represent
the velocity vector, momentum parameter, and optimization step size for MGD, respectively.
Matrix-vector multiplication can be used for IS checking, as the condition (z." Ag = 0) indicates the presence of edges in the graph. If z Ag > O, then z can be immedi- ately identified as not being an IS. While this approach effi- ciently checks for IS validity, it cannot determine whether the IS is maximal.
The projected MGD (Polyak, 1964) updates are then defined as follows:
v + Bv ag((x) x + (x v).
(12a)
(12b)
Building on the characteristics of local minimizers and the non-extremal stationary points of (4), discussed in Lemma 2, Theorem 2, and Theorem 3, we propose an efficient im- plementation for checking whether a vector x E [0, 1]" corresponds a MaxIS.
We implement the updates (12) based on our empirical observation that sxed-step-size gradient descent for (4) is sensitive to the choice of step size and frequently fails to converge to local minimizers due to overshooting. This serves as another motivation of why we adopt Momentum- based Gradient Descent (MGD), as further supported in Appendix E.4.
Specifically, Lemma 2, demonstrates that all local minimiz- ers are binary. Subsequently, in Theorem 2, we establish that all local minimizers correspond to MaxISs. This im- plies that all binary stationary points resulting from the updates in (12) within our box-constrained optimization in (4) are local minimizers situated at the boundary of (o, 1)m and correspond to MaxISs, as further elaborated in the proof of Theorem 2. Consequently, we propose new MaxIS checking condition that relies single matrix-vectoo mul- tiplication. For given E [0, 1)", we first obtain its binary representation as a vector z, where Z, = 1(x, > 0) for all v E V. We then verify whether the following condition is satisfied.
3.3.2. DEGREE PARALLEL INITIALIZATIONS
For a single graph, propose use various points in [0, 1]" and execute the updates in (12) in parallel for each. Given a specified number of parallel processes M, we de- fine Smi to denote the set of multiple initializations, where |Smil = M.
Based on the intuition that vertices with higher degrees are less likely belong to an MIS compared to those with lower degrees (Alkhouri et al., 2022), we initialize Smi with M samples drawn from Gaussian distribution ((m, nI). Here, mi is the mean vector, initially set to h, where h is:
1(2 (22 -ooPPoojoo.. 13- (2-oz(z)) ag(z)))
(15)
Equation (15) represents simple projected gradient descent step to determine whether is at the boundary of the box- constraints. If (15) holds true, then the MaxIS is given by [(z), as defined in (14).
h d(v) A(G) VU V
(13)
h
max, h
Remark 6. As previously discussed, the work in (Mah- davi Pajouh et al., 2013) showed that any binary minimizer of box-constrained continuous relaxation of (3) corre- sponds to a MaxIS when To > 1. This means that verifying whether a binary vector corresponds to a MaxIS using the proposed projected gradient descent step can also be applied
7) is hyper-paramette that regulates the exploration around m. Once the optimization for each initialization is complete, we proceed with the MaxIS checking procedure for all the
results, which we discuss next.
5

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Algorithm 1 PCQO-MIS.
Remark 8. While Theorem 2 indicates how to select y and
Input: Graph G = (V, E), set of initializations Smi. number of itterttion T per one initialization, edge-penalty parameter y, MC term parameter y', and MGD parameters: Step size a, and momentum parameter 3.
y' other hyper-parameters (i.e., o; B3 and T) still need to be tuned to obtain feasible solutions. In Appendix E. we describe a basic grid search procedure to select these parameters.
Output: The best obtained MaxIS I in
01: Initialize SManS= = {.) (Empty set collect MaxISs)
4. Experimental results
02: For x{0] E Smi (Parallel Execution)
03: Initialize v0] <-
4.1. Settings, Baselines, & Benchmarks
04: For t E [Z]
We code our objective function and the proposed algorithm using C++. For baselines, utilize Gurobi (Gurobi) and the recent Google solver CP-SAT (Perron & Didier) for the ILP in (2), ReduMIS (Lamm et al., 2016), iSCO' (Sun et al., 2023), and four learning-based methods: DIMES (Qiu et al.,
05:
Obtain g(x(t- - - ( 1x]
06:
Obtain v[t] = Bv(t - 1| + ax(((t - 1J)
07:
Obtain x(t) = Projoo. (x(t - 1| v(t))
08:
Obtain z [2] with - 10. [7] > 0), Ve V
09: If 1 (z(T)= = Projjo.aj
og(2(7])))
2022), DIFUSCO (Sun & Yang, 2023), LwD (Ahn et al.,
10:
Then SMaus <- Swass U [x][T)
2020), and the GCN method in (Li et al., 2018) (commonly referred to as 'Intel'). We note that, following the analysis in (Böther et al., 2022), GCN's code cloning to ReduMIS is disabled, which was also done in (Qiu et al., 2022; Sun & Yang, 2023). To show the impact of the MC term, we include the results of PCQO-MIS without the third term (i.c.. 7 = 0) which we term PQO-MIS (see also Appendix E.5).
11: Return I argmaxzess Z
using (3) as:
1 z = Projjo. a (z + a(en - -oAA22))
(16)
Aligned with recent methods (DIMES, DIFUSCO, and iSCO), we we employ the Erdos-Renyi (ER) (Erdos et al., 1960) graphs from (Qiu et al., 2022) and the SATLIB graphs from (Hoos & Stützle, 2000) as benchmarks. The ER dataset consists of 128 graphs with 700 to 800 nodes and 0.15, where is the probability of edge creation. The SATLIB dataset consists of 500 graphs (with at most 1, 3,7 nodes and 5, 978 edges). Additionally, the GNM random graph generator function of NetworkX (Hagberg al., 2008) is uti- lized 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. Appendix E.2, and Appendix E.3, respectively.
In Section 4.4, we show the speedups obtained from using this approach as compared to the standard iterative approach discussed earlier in this subsection.
3.3.4. THE PCQO-MIS ALGORITHM
We outline the proposed procedure in Algorithm 1. As shown, the algorithm takes a graph G. the set of initial- izations Smi. the maximum number of iterations per batch T (with iteration index t), the edge penalty parameter % the MC term parameter y' step size a, and momentum parameter 3 as inputs.
For each initialization vector in set Smi and iteration t E [T), Lines 5 to 7 involve updating the optimization variable x[t]. After T iterations, in Lines 8 to 10, the algorithm checks whether the binary representation of x[T] corresponds to a MaxIS using (15). Finally, the best-found MaxIS, deter- mined by its cardinality, is returned in Line 10.
For PCQO-MIS, the syper-parameters are set as given in Ta- ble 12 of Appendix E.9. Further implementation details and results are provided in Appendix E, Our code is available online".
After M 1 optimizations are complete (i.e., when the batch is complete), another set of initializations are placed in Smi Then Algorithm 1 is executed again, depending on the time budget and the availability of the computational re- sources (number of batches). When Algorithm is executed again, the vector v is not re-initialized, but rather main- tained from the previous batch. Subsequent runs depend sampling from (m, r/I) where is set to the binarized vector of the best obtained MaxIS from the previous run. Remark 7. Optimizing initialized points around a binary vector that corresponds to a MaxIS shows that PCQO-MIS can be used as local search heuristic for MIS.
4.2. ER and SATLIB Benchmark Results
Here, we present the results of PCQO-MIS alongside the considered baselines, using the SATLIB and ER bench- marks. These results are measured in terms of average MIS size across the graphs in the dataset and the total sequential run-time (in minutes) required to obtain the results for all the graphs. Results are given in Table 1, where the last 4
kespo: /ggtthub. con/ htt.//ooooooorrrreeeeeeo www.srccoosssseeeeee d1025
paae / oun adeemaa L/ p000 miy benchmarkk
6

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Dataset: SATLIB
Dutaset: ER
Method
Type
Training Data
MIS Size (1)
Run-time (J)
Training Data
MIS Size (1)
Run-time (U)
ReduMIS (Lamm al., 2016)
Heuristies
425.96
37.58
44.87
52.13
CP-SAT (Perron Didier)
Exact
425.9
0.56
41.15
64
Gurobi (Gurobii
Exact
425.96
8.32
39.14
64
GCN et al., 2018)
SL+G
SATLIB
420,66
23.05
SATLIB
34.86
23.05
LwD (Ahn al., 2020)
RL4S
SATLIB
422.22
18.83
ER
41.14
6.33
DIMES (Qiu al., 2022)
RL+TS
SATLIB
423.28
20.26
ER
42.06
12.01
DIFUSCO (Sun & Yang. 2023)
RL+G
SATLIB
424.5
8.76
ER
38.83
8.8
DIFUSCO (Sun & Yang, 2023)
RL+S
SATLIB
425.13
23.74
ER
41.12
26.27
iSCO (Sun et al., 2023)
S
X
422,664
"22.35"
X
44,57
"14.88"
pQO-MIS (i.e.. 7'
QO
412.888
16.964
X
40.398
5.78
PCQO-MIS PCQO-MIS
QO
425.148
56.722
45.109
54.766
QO
424.686
31,901
45.078
40.555
PCQO-MIS PCQO-MIS
QO
424.096
20.3
X
44,969
20.875
QO
423.706
16.394
X
44.5
5.563
Table I: Benchmark dataset results in terms of average MIS size and total sequential run-time (minutes). RL, SL, G. QO, S, and TS represent Reinforcement Learning. Supervised Learning, Greedy decoding, Quadratic Optimization, Sampling, and Tree Search, respectively. The results of the carming-based methods (other than DIFUSCO) and ReduMIS sourced from (Qiu al., 2022) and run using single NVIDIA A100 40GB GPU and AMD EPYC 7713 CPU. The results of DIFUSCO are sourced from (Sun & Yang. 2023) and run using single NVIDIA V100 GPU and Intel Xeon Gold 6248 CPU. The run-time for learning methods exclude the training time (underlined), PCQO-MIS run-times exclude the hyper-parameters tuning time that was done on one graph for each dataset (see Appendix E.9.1). I). The PCQO-MIS, CP-SAT, and Gurobi results are run using an NVIDIA RTX3070 GPU and Intel 19-12900K CPU. The results for iSCO were produced using an NVIDIA A 100 40GB GPU and AMD EPYC 7H12 CPU. We note that the run time reported iSCO (Table I in (Sun et al., 2023)) is for running multiple graphs in parallel, not a sequential total run time. We evaluated iSCO in the same way. If they are run sequentially, the extrapolated run-time is ~0000 minutes for SATLIB and ~ 140 minutes for ER. ReduMIS employs the local search procedure from (Andrade et al., 2012) for multiple rounds, which other method in the table uses, following the study in (Böther et al., 2022). Different run-times for PCQO-MIS correspond to using different number of batches (See Appendix E.10). For more details about the requirements of each method, see Appendix D.I.
rows show the PCQO-MIS results for different run-times. We note that the ER results from the exact solvers are lim- ited to 30 seconds per graph to ensure total run-times that are comparable to those of other methods, In what follows, we provide observations on these results.
is shorter than the inference time of any learning- based method), pCQO-MIS reports larger MIS sizes than any learning method (44.5 vs. 42.06). Furthermore, our ap- proach does not rely on additional techniques such as Greedy Decoding (Graikos et al., 2022) and Monte Carlo Tree Search (Fu et al., 2021).
All learning-basee methods, except for GCN, require train- ing a separate network for each graph dataset, as shown in the third and sixth columns of Table 1, highlighting their generalization limitations. In contrast, our method is more generalizable, requiring only the tuning of hyper- parameters for each set of graphs. See Appendix E.8 for a comparison between PCQO-MIS and DIFUSCO using graphs with densities that are different from the training setting of DIFUSCO.
When compared to the sampling approach, iSCO, our method reports larger MIS sizes while requiring signif- icantly reduced sequential run-time. We note that the iSCO paper (Sun et al., 2023) reports lower run time as compared to other methods. This reported run time is achieved by evaluating the test graphs in parallel, in con- trast to all other methods that evaluated them sequentially, To fairly compare methods in our experiments, we opted to report sequential test run time only. We conjecture that the extended sequential run-time of iSCO, compared to its parallel run-time, due to its use of simulated anneal- ing. Because simulated annealing depends the energy of the previous step when determining the next step, it is inherently more efficient for iSCO to solve many graphs in parallel than in series.
When compared to learning-based approaches, our method outperforms all baseline methods in terms of MIS size, all without requiring any training data. We note that the reported run times for learning-based methods exclude training time, which can vary depending on sev- eral factors, including graphs sizes, available computing resources, the number of data points, and the specific neu- ral network architecture used. under minutes (which
knowing
For SATLIB, which consists of sparser graphs (relative to

---

Given the same run-time. when comparing the results of PQO-MIS (i.e., V = 0) and the results of PCQQ-MIS, we observe that when the MC term is included, PCQO-MIS reports larger MIS sizes. On average, using the MC term yields nearly 11 (resp. 4) nodes improvement for SATLIB (resp. ER). A detailed study about the impact of the clique Differentiable Quadratic Optimization For The Maximum Independent Set Problem
350
ReduMIS
300
Gurobi
CP-SAT
Run-time (minutes)
250
PCQO-MIS (Ours)
200
150
100
50
0-
(50, 613, 7.6)
(500, 62375. 13.4) (Number of Nodes n, Number of Edges m, Avg. MIS Size)
(1000, 249750, 15)
(1500, 562125, 16)
(2000. 999500, 16.4)
Figure 2: Total run-time in minutes (y-axis) of PCQO-MIS, ReduMIS, CP-SAT, and Gurobi for the GNM graphs with n E {50,500 1000, 1500, 2000), m = - ), and the average MIS size of 5 graphs (x-axis). This choice of the number of edges indicates that half of the total possible edges (w.r.t. the complete graph) exist. Here, we also use an NVIDIA RTX3070 GPU and Intel 19-12900K CPU. For n > 500, Gurobi and CP-SAT are not included due to excessive run cun-times.
the ER graphs with p = 0.15). PCQO-MIS falls just short when compared to ReduMIS, Gurobi, and CP-SAT (ex- act and heuristic solvers). The reason ReduMIS achieves SOTA results here is that it applies a large set of MIS- specific graph reductions, along with the 2-opt local search procedure (Andrade et al., 2012). PCQO-MIS and other baselines do not apply the 2-opt procedure fol- lowing the study in (Böther et al., 2022) where it was conjectured that most methods will converge to the same solutions if this local search procedure is applied (for each solution found). We note that ReduMIS iteratively applies this heuristic. For denser graphs, most of these graph reductions are not applicable. Gurobi and CP-SAT solve the ILP in (2) where the number of constraints is equal to the number of edges in the graph. This means that Gurobi and CP-SC CPTS are expected to perform better on SATLIB, where there are fewer constraints, compared to denser graphs like ER.
term is given in Appendix E.5.
4.3. Scalability Results
It is well-established that relatively denser graphs pose greater computational challenges compared to sparse graphs. This is due to the applicability of graph reduction techniques such as the LP reduction method in (Nemhauser & Trotter, 1975), and the unconfined vertices rule (Xiao & Nagamochi, 2013) (see (Lamm al., 2016) for a complete list of the graph reduction rules that apply only on sparse graphs). For instance, by simply applying the LP graph reduction tech- nique, the large-scale highly sparse graphs (with several hundred thousand nodes), considered in Table 5 of (Li et al., 2018), reduce to graphs of a few thousands nodes with often dis dis-cooneeted sub-graphs that can be treated independently.
Therefore, the scalability and performance of ReduMIS are significantly dependent on the sparsity of the graph. This dependence emerges from the iterative application of vari- ous graph reduction techniques (and the 2-opt local search in (Andrade et al., 2012)) in ReduMIS, specifically tailored for sparse graphs. For instance, the ReduMIS results pre- sented in Table (Ahn et al., 2020) are exclusively based on very large and highly sparse graphs. This conclusion is substantiated by both the sizes of the considered graphs and the corresponding sizes of the obtained MIS solutions. As such, in this subsection, we investigate the scalability of PCQO-MIS against the SOTA methods: ReduMIS, Gurobi, and CP-SAT on denser graphs
On ER, our method not only reports larger average MIS size but also generally requires less run-time. Specifically, in under 21 minutes, our method (PCQO-MIS) achieves better results than ReduMIS, CP-SAT, and Gurobi. In under 55 minutes, we achieve 109. We emphasize that we outperform the SOTA MIS heuristic solver and two commercial solvers
To generate suitably dense graphs, we utilized the Net- workX GNM graph generator with the number of edges set to m = m It is important to note that the density of these graphs is significantly higher than those considered in the previous subsection (and most of the graphs consid-
WWe note that learning-basel methods, such (Qiu et al., 2022; Sun & Yang, 2023), ReduMIS label training graphs under the supervised learning setting.
8

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Run timetime (seconds)
20
Standard
Our MIS checking (with the third term)
Our MIS checking (without the third term)
10
(500.0.1)
(500,0.4)
(500.0.7)
(1000,0.1) (1000.0.4) (1000,0.7) (2000.0.1) (2000.0.4) (2000.0.7)
ER graph size and probability of edge creation (n.p)
Figure 3: Average run-time results of our MIS checking vs. the standard iterative approach across different graph sizes and densities. Orange and green results correspond to using the criteria (15) and (16), respectively.
ered in recent learning-based and sampling studies). This choice of the number of edges in the GNM graph genera- tor indicate that half of the total possible edges (w.r.t. the complete graph) exist. Results are provided in Figure 2. As observed, for dense graphs, as the graph size increases, our method requires significantly less run-tim compared to all baselines, while reporting the same average MIS size (third entry of each tuple in the x-axis). For instance, when n is 500, our method requires less than 12 seconds solve the 5 graphs, whereas other baselines require 35 minutes more to achieve the same MIS size. For the case of = 2000, our method requires less than 4 minutes whereas ReduMIS requires nearly 350 minutes. These results indicate that, un- like ReduMIS and II.P solvers, the run-time of our method scales only with the number of nodes in the graph, which is significant improvement.
forward yet effective method demonstrates competitive per- formance compared to state-of tfrtthe-rrt learning, sampling, and heuristic methods. This research offers a distinctive perspective on approaching discrete optimization problems through a parameter-efficien procedure optimized from the problem structure rather than from datasets.
Impact Statement
This work introduces novel quadratic optimization frame- work, PCQO-MIS, that advances combinatorial optimiza- tion research by tackling the Maximum Independent Set (MIS) problem with enhanced scalability and performance. By leveraging a clique-informed quadratic formulation and momentum-basee baaed parallel optimization, PCQO-MIS achieves superior MIS sizes while maintaining competitive run-times. Unlike data-centric approaches, it eliminates dependency on labeled data and out-of-distribution tuning, offering robust generalization across graph instances. Fur- thermore, its run-time efficiency, scaling with nodes rather than edges, positions PCQO-MIS as a transformative ap- proach for large- scale-scllelaa graph problems, bridging the gap between theory and practical applicability in optimization.
4.4. Impact of the Proposed MIS Checking Criterion
In this subsection, we evaluate the impact of the proposed MIS checking method on the run-time performance of the execute PCQO-MIS
PCQO-MIS algorithm. Specifically, for 7 = 1000 iterations, performing MIS checking at each iteration. The average run-time (seconds) results for 10 ER graphs, covering various graph sizes and densities, are illustrated in Figure 3, with the x-axis representing different values of n (graph size) and p (probability of edge creation that indicates density). We compare these results the standard MIS checking approach, which involves iterating over all nodes to examine their neighbors, as discussed in Section 3.3.3. The results suggest that the execution time for PCQO-MIS is significantly reduced with our efficient implementation compared to the standard method as the graph order increases.
Acknowledgments
JL acknowledges Defense Advances Research projects Agency (DARPA)'s Young Faculty Award (YFA) D24AP00265. CY acknowledges NSF2349670 and NSF2403135. The authors would like thank Curie Kim and Mingju Liu from the University of Maryland, College Park, for their help in evaluating large ER graphs under time constraints. We would also like to thank Yikai Wu and Haoyu Zhao from Princeton University for insightful discussions about the optimization in PCQO-MIS, and for sharing the BA graphs. This research was developed with funding from DARPA. The views, opinions, and/or findings expressed those of the authors and should not be interpreted as representing the official views of the Department of Defense the U.S. Govemment. Distribution Statement "A" (Approved for Public Release Distribution Unlimited).
method with the
5. Conclusion
This paper addressed the challenging Maximum Indepen- dent Set (MIS) Problem within the domain of Combinatorial Optimization by introducing a clique-in iiquue-ifformed continuous quadratic formulation. By eliminating the need for any train- ing data, PCQO-MIS distinguishes itself from conventional learning approaches. Utilizing momentum-based gradient descent and parallel GPU implementation, straight-

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
References
Defferrard, M., Bresson, X., and Vandergheynst, Con- volutional neural networks on graphs with fast localized spectral filtering, Advances in neural information pro-
Ahn, S., Sco, Y., and Shin, J. Learning what to defer for maximum independent sets. In International Conference on Machine Learning, pp. 134.144. PMLR, 2020.
cessing systems, 29:3844-388 3852, 2016.
Akiba, T. and Iwata, Y. Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover. The- oretical Computer Science, 609:211-223 2016.
Eddy, D. and Kochenderfer, M. J. A maximum indepen- dent set method for scheduling earth-observing satellite constellations, Journal of Spacecraft and Rockets, 58(5): 1416-1429, 2021. doi: 10.2514/ 002211/41.23444 .334931.
Alkhouri, I. R., Atia, G. K., and Velasquez, A. A differen- tiable approach to the maximum independent set problem using dataless neural networks. Neural Networks, 155: 168-176, 2022.
Erdos, P., Rényi, A., et al. On the evolution of random graphs. Publ. Math. Inst. Hung, Acad. Sci, 5(1): 1960.
Andrade, D. V., Resende, M. G., and Werneck, F. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525-547, 2012.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelli- gence, volume 35, pp. 7474-7482, 2021.
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439):509-512, 1999.
Gamarnik, D. Barriers for the performance of graph neu- ral networks (gnn) in discrete random structures. Pro- ceedings of the National Academy of Sciences, 120(46): e231 e2314092120, 2023.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: methodological tour d' d'horizon, European Journal of Operational Research, 290(2):405-221, 2021.
Goshvadi, K., Sun, H., Liu, X., Nova, A., Zhang, R., Grath- wohl, W., Schuurmans, D., and Dai, H. Dises: A bench- mark for discrete sampling. Advances in Neural Informa- tion Processing Systems, 36, 2024.
Berman, P. and Schnitger, G. On the complexity of approx- imating the independent set problem. Information and Computation, 96(1):77-94, 1992.
Boppana, R. and Halldórsson, M. M. Approximating max- imum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2):180-116, 1992.
Graikos, A., Malkin, N., Jojic, N., and Samaras, D. Diffu- sion models blug-and-pla priors. Advances in Neural Information Processing Systems, 35:14715-14725 2022.
Böther, M., KiBig, O., Taraz, M., Cohen, S., Seidel, K., and Friedrich, T. What's wrong with deep learning in tree search for combinatorial optimization. International Conference on Learning Representations, 2022.
Gurobi. Gurobi Optimization. gurobi.com com.
URL https: //ww.
Hagberg, A. A., Schult, A., and Swart, P. Exploring net- work structure, dynamics, and function using networkx. In Varoquaux, G., Vaught, T., and Millman. J. (eds.). Pro- ceedings of the 7th Python in Science Conference, pp. 11 - -15, Pasadena, CA USA, 2008
Burer, S. and Letchford, A. N. On nonconvex quadratic programming with box constraints. SIAM Journal on Optimization, 10(2):1073-10) 2009.
Dai, H., Dai, B., and Song, L. Discriminative embeddings of latent variable models for structured data. In International conference on machine learning, pp. 2702-2711. PMLR, 2016.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851 2020.
Dai, H., Khalil, F. B., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31 International Con- ference on Neural Information Processing Systems, pp. 6351-6366 2017.
Hoos, H. H. and Stützle, T. Satlib: An online resource for research on sat. Sat, 2000:283-29,, 2000.
IBM.
IBM ILOG CPLEX Optimization Studio. URL https:/ ibm. wwwmpproducttaaeeemoooooooooooee i po0--pplex-opttmiiaaa studi...
Dantzig, G. B., Fulkerson, D. R., and Johnson, S. M. Solu- salesman problem. Journal
tion of large-scale of the Operations Research Sociery of America, 2(4):393- 410, 1954.
Ichikawa, Y. Controlling continuous relaxation for combi- natorial optimization. Advances in Neural Information
Processing Systems, 37:47189 472161, 2024.
10

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Johnson, D. S. and Trick, M. A. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, volume 26. American Mathemati- cal Soc., 1996.
Polyak, B. T. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Qiu, R., Sun, Z., and Yang. Y. Dimes: A differentiable meta solver for combinatorial optimization problems. Ad- vances in Neural Information Processing Systems, 35: 25531-25546, 2022.
Joseph, D., Meidanis, and Tiwari, P. Determining dna sequence similarity using maximum independent set algo- rithms for interval graphs. In Algorithm Theory SWAT
'92, pp. 326-337. Springer, Berlin, Heidelberg, 1992.
Schuetz, M. J., Brubaker, J. K., and Katzgraber, H. G. Com- binatorial optimization with physics-inspired graph neu- ral networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Karp. R. M. Reducibility among combinatorial problems. In Complexity of computer computations, pp. 85-103. Springer, 1972.
Lamm, S., Sanders, P., Schulz, C., Strash, D., and Wer- neck, R. F. Finding npar-optimal independent sets at scale. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 138-150. SIAM, 2016.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint 1707. 06347, 2017.
Singh, K. K. and Govinda, L.. simple and efficient heuris- tic algorithm for maximum clique problem. 2014 IEEE 8th International Conference on Intelligent Systems and Control (ISCO), 2014.
Langley, P. Crafting papers on machine learning. In Proceed- ings of the 17th International Conference on Machine Learning (ICML 2000), 2000.
Li, Z., Chen, Q., and Koltun, V. Combinatorial optimization with graph convolutional networks and guided tree search. In NewrlPS, 2018
Sun, H., Dai, H., Xia, W., and Ramamurthy, A. Path auxil- iary proposal for meme in discrete space. In International Conference on Learning Representations, 2021.
Mahdavi Pajouh, F., Balasundaram, B., and Prokopyev, O. A. On characterization of maximal independent sets via quadratic optimization. Journal of Heuristics, 2013.
Sun, H., Goshvadi, K., Nova, A., Schuurmans, D., and Dai, H. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning, pp.
32859-32874, PMLR, 2023.
Marino, R., Buffoni, L.,, and Zavalnij. B. A short review on novel approaches for maximum clique problem: from classical algorithms graph neural networks and quan- tum algorithms. arXiv preprint arXiv:2403.09742 2024.
Sun, Z. and Yang. Y. Difusco: Graph-based diffusion solvers for combinatorial optimization. arXiv preprint arXiv:2302.08224, 2023.
Matsui, S. and Tokoro, K. A new genetic algorithm for minimum span frequency assignment using permutation and clique. Central Research Institute of Electric Power Industry, Tokyo, Japan, 2000.
Tarjan, R. E. and Trojanowski, A. E. Finding maximum independent set. SIAM Journal on Computing, 6(3):537- 546, 1977.
Wei, V. K. A lower bound on the stability number of simple graph. Technical report, Bell Laboratories Technical Memorandum Murray Hill, NJ, USA, 1981.
McElfresh, D. C., Bidkhori, H., and Dickerson, J. P. Scal- able robust kidney exchange. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1077-1084, 2019.
Williamson, D. P. and Shmoys, D. B. The design of approx- imation algorithms. Cambridge university press, 2011.
Nemhauser, G. L. and Trotter, L. tural properties and algorithms. Mathematical Progrum- ming, 8(1):232-248; 1975.
E. Vertex packings: Struc-
Wu, Y., Zhao. H.. and Arora, S. Unrealized expectations: Comparing ai methods vs classical algorithms for maxi- mum independent set. arXiv preprint arXiv:2502.03669, 2025.
Pardalos, M. and Rodgers, G. A branch and bound algorithm for the maximum clique problem. Computers & operations research, 19(5):363-375 1992.
Xiao, M. and Nagamochi, H. Confining sets and avoid- ing bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theoretical Computer Science, 469:92-104, 2013.
Perron, L. and Didier, F. Cp-sat. URL https: //developers.gooeeooo gwwgge. com/ opt imization cp/op_solver/

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Zweig, K. A., Kaufmann, M., Steigele, S., and Nieselt, K. K. On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences. Algoritims for Molecular Biology, 2006.
12

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Appendix
In this appendix, we begin with detailed proofs in Appendix A, followed by discussion on how the proposed objective corresponds to dataless quadratic neural network in Appendix B. Appendix C presents study the feasibility of saddle points. We review prior MIS solvers in Appendix D, and provide additional experimental results, implementation details, and ablation studies in Appendix E.
A. Proofs
We begin by re-stating our main optimization problem:
min f(x) = Σ x
x +
Σ X,Xu - - Σ
X, = -c 7 2'
Acx 2
X (17)
2
NEV
(u,t)EE
(u,r)EE
The gradient of fxx in (17) is
xx((x)= = g((x = BB + 17AA7-77AA -
-
(18)
where, for some E V, we have
0f(x) 11 Σ
X - Σ
X
(19)
0x.
(E)((o
(EN
A.1. Proof of Lemma
Re-statement: For any non-complete graph G, the constant hessian of f(x) in (4), ie., ~Ag - 7 A'', always a non-positive-semidennie (non-PSI) matrix.
Proof. The hessian, (7Ag A'A')). ) is independent xf we must have
x. If (yAG AAo') ) is PSD, then, by definition of PSD matrices,
x" (7AA - A
0, [0, 1]"
(20)
which is not possible as for any Xy that corresponds to a MaxIS, we have xX (7Ag)xx = (no edges in MaxIS w.r.t. G)
and 7/ x Ag X < 0 (a MaxIS in G is maximal clique in G').
A.2. Proof of Theorem
Re-statement: Given an arbitrary graph G = EV and its corresponding formulation in (17), suppose the size any MIS
of G Then, 7 2 1 1+ 7/k is necessary and sufficient for all MaxIS vectors to be local minimizers (17) for arbitrary graphs.
Proof. Let Z be MaxIS. Define the vector x such that contains I's at positions corresponding to the nodes in the set S, and 0's at all other positions. For any MaxIS to local minimizer (17), is sufficient and necessary to require that
af(x)
2 0, Ve & I and dx.
(21)
0f(x)
Ox, S 0, E
(22)
Here, x, is the element of x at the position corresponding to node v. Equation (21) is derived because if u & I, then x = 0 (by the definition of x²) so is at the left boundary of the interval [o, 1]. For the left boundary point to be a local minimizer, it requires the derivative to be non-ne non-negative (i.e., moving towards the right only increases the objective). Similarly, when x 1, is at the right boundary for (22), at which the derivative should be non-positive.
13

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
The derivative of f computed in (19) can be rewritten
0f(x)
- mm - -y Vu I,
(23)
0x,
where
my = (()))
(24)
the number of neighbors of in I and
4
nzj
(25)
is the number of non-neighbors of e in I, Here, (v)) Here,
= {u (u. E E.
By this definition, we immediately have 1 1 my - |Z| and - b. - [Z], where the upper and lower bounds for m, and b. are all attainable by some special graphs. Note that the lower bound of m, 1, and that due the fact that is a MaxIS, so any other node (say v) will have at least edge connected to node I.
Plugging (23) into (21), we obtain
1 1+
Y
(26)
mc
Since we're seeking a universal y for all the graphs, we must set my to its lowest possible value, 1, and t, to its highest possible value & (both are attainable by some graphs), and still requires 7 to satisfy (26). This means is necessary and sufficient to require y 2 ykk. In addition, (22) satisfied unconditionally and therefore does not impose any extra condition on y.
A.3. Proof of Lemma 2
Re-statement: All local minimizers of (17) are binary vectors.
Proof. x" be any local minimizer of (17). If all the coordinates of x" are either complete, otherwise, at least one coordinate of x" is in the interior (0, 1) and we aim to prove that this is not possible (i.e. such non-binary x" cannot exist as minimizer) by contradiction. We assume the non- non-binary x" exists, and denote the set of non-binary coordinates as
then x" is binary and the proof is
J x E (0, 1))
(27)
Since x" is non-binary, J 0. Since the objective function f(x) of (17) is twice differentiable with respect all x, with Xj E (0, 1), then necessary condition for x* to be a local minimizer is that
fx('') = 00 v²f(x"), =
where Vf(x*)), is the vector V fx"") restricted to the index set J. and V v2f('')), is the matrix V fxx") whose and column indices are both restricted to the set J.
However, the second necessary condition v²f(x*), > 0 cannot hold. Because if it does, then we must have tr( tr(V²f(x*)), 0 (the trace cannot strictly equal to 0 as V fxx((")), L,(AG ? A' II * where I, denotes the identity matrix with row indices restricted to the index set J). However, on the other hand, we have
Lr( )r(V2J(x')),) = (r( A'A 0,
as the diagonal entries of AG and A are all 0, which leads to a contradiction.
A.4. Proof of Theorem 2
Re-statement: Given graph G = (V, E) and set 7 2 L+''A(G"), all local minimizers of (17) correspond to a MaxIS in G.
Proof. By lemma 2, we only consider binary vectors as local minimizers. With this, we first prove that all local minimizers are Independent Sets (ISs). Then, we show that any IS, that not a maximal IS, is not local minimizer.
14

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Here, show that any local minimizer is IS. By contradiction, assume that vector x, by which x, = X such that (ve w) E E (a binary vector with edge in G), is local minimizer. Since X2 1 is the right boundary of the interval < 0. Together with (19), this implies
[0, 11, for it to be local minimizer, we must have of
ox.
-1+7
Σ (EN(")
Σ (E)
Xu 0.
(28)
Re-arranging (28) yields to
Σ X 514 (EN())
E MEN"())
Xu
(29)
Given that 21 114 +''(("") the condition in (29) can not be satisfied even if the LHS attains its minimum value (which is yn) and the RHS attains a maximum value. The maximum possible value of the RHS is 1 + d'(v) = n - d(v), where d'(v) is the degree of node in G", and the maximum possible value of d'(v) is (G"). This means that when an edge exists in x. it can not be a fixed point. Thus, only ISs are local minimizers.
Here, we show that Independent Sets that are not maximal are not local minimizers. Define vector x E {0. 1)" that corresponds an IS I(x). This means that there exists node u E V that is not in the IS and is not in the neighbor of all nodes in the IS. Formally, if there exists u & I(x) such that Ve I(x), & NWw), then I(x) is an IS, not maximal IS. Note that such an x satisfies x, 0 and
0f -1 + 0x,
Σ X X (EN(1)
Σ (EN
X -- 7f
Σ (EN
Xu <0,
(30)
which implies that increasing x,, can further decrease the function value, contradicting to x being local minimizer. In (30), the second summation is 0 as (() n I(x) 0, which results in -(1 + EveA(()) Xx) that is always negative. Thus,
any binary vector that corresponds to an IS that is not maximal is not local minimizer.
A.5. Proof of Theorem 3
Re-statement: For any graph G, assume that there exists point x' such that Vxf(x') 0,i.e,, (1A0-1'A0 -AA Then, x' is not a local minimizer of (17) and therefore does not correspond to MaxIS.
Proof. By Lemma 2, we know that all local minimizers are binary. By contradiction, assume that x' is a binary local minimizer. Then, the system of equations (7AG A'A )x' = en implics that, for all E V, the following equality must be satisfied.
Σ (EN(v))
X
11
(31)
uEN((1)
If x' is binary and corresponds to a MaxIS in the graph, then the first term of (31) is always 0, which reduces (31) to
Σ
x. 1.
(32)
(E)
E3.( is an equality that can not be satisfied as X', 2 0, E V and 2 1. Thus, x' is not a local minimizer.
B. Connection to dataless Quadratic Neural Networks
Our proposed objective in (4) corresponds to dataless quadratic neural networks (dQNN), illustrated in Figure 4 (right). Here, the dQNN comprises two fully connected layers. The initial activation-free layer encodes information about the nodes (top n = 5 connections), edges of G (middle m = 4 connections). and edges of G" (bottom m' = 6 connections), all without a bias vector. The subsequent fully connected layer is an activation- free layer performing a vector dot- dot-product between the fixed weight vector (with -1 corresponding to the nodes and edges of G' and the ddges-penalty parameter 7)), and the output of the first layer.
15

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Encoding of
Encoding of
Encodingg oy EV
Encoding of,,
Encoding of e.
Encoding of
G (V,
X2 E [0.1]
Encading of (o,
E [0.1]
Encoding (s)
f(0
Encoding of (Py.0.)
X E [0.1]
Encoding (x.. E
X₂ E [0.1]
Encoding Encoding
X; [0.1]
Encoding (t) 6
Encoding (tr,
Encoding of (V)
Encodinn (4)
G' = (V,5)
Encoding of (12, e
Encoding of
Figure 4: Graph G (left) and its corresponding dataless quadratic neural network (right).
C. Empirical Observations on the Non-Extremal Stationary Point x'
In this section, we empirically demonstrate how the non-extremal stationary point x', analyzed in Theorem 3, varies with the type of graph. Specifically, we aim to show that, for many types of graphs, this saddle point is outside the box constraints, depending on the graph connectivity. To this end, we consider GNM and ER graphs with different densities, as well as small and large graphs from the SATLIB dataset.
In Figure 5, we obtain x' = (7AG - 7 )'Arrr--e, with 7 = n and > = for every considered graph. Each subplot in Figure shows the values of x (y-axis) for every node (x-axis), with the title specifies the graph used.
As observed, among all the graphs, only the eey-hhghh-ensity GNM graph (with results shown inside the dashed box in Figure 5) has x' E [0, 1j (i.e., within the box-constraints of (4)). Note that this graph was generated with m 4945 where the total number of possible edges in the complete graph with n = 100 is 4950 edges.
For all other graphs, we have x' & [0, 1]", as indicated by the values strictly below 0. This means that by applying the projection (12), x' infeasible.
D. Related Work
1) Exact and Heuristic Solvers: Exact approaches for NP-hard problems typically rely on branch-and- bound global optimization techniques. However, exact approaches suffer from poor scalability. which limits their uses in large MIS problems (Dai et al., 2016). This limitation has spurred the development of efficient approximation algorithms and heuristics. For instance, the well-known NetworkX library (Hagberg et al., 2008) implements a heuristic procedure for solving the MIS problem (Boppana & Halldórsson, 1992). These polynomial-time heuristics often incorporate a mix of sub-procedures, including greedy algorithms, local search sub-routines, and genetic algorithms (Williamson & Shmoys, 201 1). However, such heuristics generally cannot theoretically guarantee that the resulting solution is within a small factor of optimality. In fact, inapproximability results have been established for the MIS problem (Berman & Schnitger, 1992).
Among existing MIS heuristics, ReduMIS (Lamm et al., 2016) has emerged as the leading approach. The ReduMIS framework contains two primary components: (f) an iterative application of various graph reduction techniques (e.g., the linear programming (LP) reduction method (Nemhauser & Trotter, 1975)) with a stopping rule based on the non- applicability of these techniques; and (ii) an evolutionary algorithm. The ReduMIS algorithm initiates with a pool of independent sets and evolves them through multiple rounds. In each round, selection procedure identifies favorable nodes by executing graph partitioning, which clusters the graph nodes into disjoint clusters and separators to enhance the solution. In contrast, our PCQO-MIS approach does not require such complex algorithmic operations (e.g., solution combination operation, community detection, and local search algorithms for solution improvement (Andrade et al., 2012)) as used in ReduMIS. More importantly, ReduMIS and ILP solvers scale with the number of nodes and the number of edges (which constraints their application on highly dense graphs), whereas PCQO-MIS only scales w.r.t. the number nodes, as demonstrated in our experimental results (Section 4.3).
16

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
-2.75
-0013
Crin Lo EOS 500))
CAP Crag 100, 10000
Cresh CS 100, 2004
0:22
OVN Gragn Iy 105,11 20601
22.0 Sn 180 6643)
0.05
40000
CATUR Cr 1ihh you 230, 333444
0.3005
GATT DI Creahh OO 2TL 2200
3.2100
5AT1 Bi E1 1254.11 00251
3011
58821
2013
00055
0.002
0.005
11
-250
100 22.00
4.313
300 750
1350
Figure 5: Values of the non-extremal stationary point x' (y-axis) w.r.t. every node v E V (X-axis) across different ER and GNM graphs well as small and large SATLIB graphs, indicated by the title of each subplot. Among all the considered graphs, only the high-density GNM graph, indicated by the dashed square, has x' E [0, 10.0
2) Data-Driven Learning-Based Solvers: Data-driven approaches for the MIS problem can be classified into SL and RL methods. These methods depend on neural networks trained to fit the distribution over (un)labeled training graphs.
A notable SL method is proposed in (Li et al., 2018), which combines several components including graph reductions (Lamm et al., 2016). Graph Convolutional Networks (GCN) (Defferrard et al., 2016), guided tree search, and the solution improvement local search algorithm (Andrade et al., 2012). The GCN is trained on SATLIB graphs using their solutions as ground truth labels, enabling the learning of probability maps for the inclusion of each vertex in the optimal solution. Then, subset of ReduMIS subroutines is used to improve their solution. While the work in (Li et al., 2018) reported on-par results to ReduMIS, it was later shown by (Böther et al., 2022) that setting the GCN parameters random values performs similarly to using the trained GCN network.
Recently, DIFUSCO was introduced in (Sun & Yang. 2023), an approach that integrates Graph Neural Networks (GNNs) with diffusion models (Ho et al., 2020) to create a graph-based diffusion denoiser. DIFUSCO formulates the MIS problem in the discrete domain and trains a diffusion model to improve a single or a pool of solutions.
RL-based methods have achieved more success in solving the MIS problem when compared SL methods. In (Dai et al., 2017), Deep Q-Network (DQN) is combined with graph embeddings, facilitating the discrimination of vertices based on their influence on the solution and ensuring scalability to larger instances. Meanwhile, the study presented in (Ahn et al., 2020) introduces the Learning What to Defer (LwD) method, an unsupervised deep RL solver resembling tree search, where vertices are iteratively assigned to the independent set. Their model is trained using Proximal Policy Optimization (PPO) (Schulman et al., 2017).
The work in (Qiu al., 2022) introduces DIMES, which combines compact continuous space to parameterize the distribution of potential solutions and meta-learning framework to facilitate the effective initialization of model parameters during the fine-tuning stage that is required for each graph.
It is worth noting that the majority of SL and RL methods are data-dependert in the sense that they often require the training of a separate network for each dataset of graphs. These data-dependent methods exhibit limited generalization performance when applied to for each graph dataset (see columns and in Table 1). An example of the weak generalization of DIFUSCO is given in
graph data. This weak generalization stems from the need to train a different network
17

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Appendix E.8. In contrast, our approach differs from and RL-based methods in that it does not rely on any training datasets. Instead, our method utilizes simple yet effective graph-encoded continuous objective function, which is defined solely in terms of the connectivity of given graph.
The method in (Alkhouri et al., 2022) introduced dataless neural networks (dNNs) tailored for the MIS problem. Notably, their method operates without the need for training data and relies on n trainable parameters. Their proposed method uses a ReLU-based continuous objective to solve the MIS problem. However, for scaling up, graph partitioning and local search algorithms were employed.
3) Dataless Differentiable Methods:
The work in (Schuetz al., 2022) introduced pyysics-Inspired Graph Neural Network (PI-GNN), dataless approach for solving COPs that optimizes the parameters of GNN over one graph using a continuous relaxation of (3) with box-constraints. However, only d-regular graphs were used for evaluation. Multiple studies followed PI-GNN including the work in (Ichikawa, 2024).
4) Discrete Sampling Solvers:
In recent studies, researchers have explored the integration of energy-based models with parallel implementations of simulated annealing to address combinatorial optimization problems (Goshvadi et al., 2024) without relying on any training data. For example, in tackling the MIS problem, the work in (Sun et al., 2023) proposed a solver that combines (i) Path Auxiliary Sampling (PAS) (Sun et al., 2021) and (ii) the QUBO formulation in (3). However, unlike PCQO-MIS, these approaches entail prolonged sequential run-time and require fine-tuning of several hyperparameters. Moreover, the energy models utilized in this method for addressing the MIS problem may generate binary vectors that violate the "no edges" constraint inherent to the MIS problem. Consequently, a post-processing procedure becomes necessary.
D.1. Requirements Comparison with Baselines
In Table 2, we provide an overview comparison of the number of trainable parameters, pyper-parameters and additional techniques needed for each baseline. ReduMIS depends on large set of graph reductions (see Section 3.1 in (Lamm et al., 2016)) and graph clustering, which is used for solution improvement.
Method
Size
Hyper-Parameters
Additional (tchniques/Poeeeddeg
ReduMIS
n variables
N/A
Many graph reductions, and graph clustering
Gurobi
n variables
N/A
N/A
CP-SAT
n variables
N/A
N/A
GCN
> n trainable parameters
Many as it is learning-based
Tree Search
LwD
> n trainable parameters
Many as it is learning-based
Entropy Regularization
DIMES
X nx trainable parameters
Many as it is learning-based
Tree Search or Sampling Decoding
DIFUSCO
> n trainable parameters
Many as it is learning-based
Greedy Decoding or Sampling Decoding
iSCo
variables
Temperature, Sumpler, Chain length
Post Processing for Correction
PCQO-MIS
R trainable parameters
a, B, Y T, and y
Degree-hused Parallel Initializations
Table 2: Requirements comparison with baselines. For the ILPs (Gurobi and CP-SAT), trainable parameters correspond to binary decision variables. ReduMIS is not an optimization method. However, they use n binary variables, one for each node.
For learning- bearning-based methods, although they attempt to 'fit' a distribution over training graphs, the parameters of a neural network architecture are optimized during training. This architecture typically much larger than the number of input coordinates (> n)). For instance, the network used in DIFUSCO consists of 12 layers, each with 5 trainable weight matrices. Each weight matrix is of size 256 x 256, resulting in 3932160 trainable parameters for the SATLIB dataset (which consists of graphs with at most 1347 nodes). Moreover, this dependence on training a NN introduces several hyper-parameters such as the number of layers, size of layers, choice of activation functions, etc.
It's important to note that the choice of the sampler in iSCO introduces additional syper-parameters. For instance, the PAS sampler (Sun et al., 2021) used in iSCO depends on the choice of the neighborhood function, a prior on the path length, and the choice of the probability of acceptance.
18

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
E. Additional Experiments
E.1. Results using DIMACS Graphs
In this section, we evaluate our proposed algorithm using graph instances from the DIMACS dataset. These graph instances have known optimal solutions listed in the recent MC survey paper (Marino al., 2024). The DIMACS benchmark part of the second DIMACS Implementation Challenge (Johnson & Trick, 1996), which focused problems related Clique, Satisfiability,, and Graph Coloring. The benchmark contains variety of graphs derived from coding theory, and fault diagnosis, among others.
As observed, we were able to solve 49 out of the 61 DIMACS graphs we tested within a 30-second time budget per graph, while ReduMIS was able to solve 58 in the same amount of time.
For our method, we use following set of hhper-pprameteee We emphasize that these graphs are very diverse (in terms of both order and density as indicated in columns 2 and 4) and using set of syper-parameters indicate that our method may not be highly sensitive in terms of finding feasible solutions. This also indicates that if we perform per graph hyper-parameters tuning, our method has the potential of reporting improved results.
a = 0.01, 3 0.3, 7 500, - 1,
2.25, 7 500.
Graph Name
Density
Optimal
PCQO-MIS
ReduMIS
c fat500-11
500
120291
0.9600
14
14
14
c-fat500-2
500
115611
0.9267
26
26
c-fat200-1
200
18366
0.9229
12
12
12
c-fat200-2
200
16665
0.8374
24
24
c f-t5500
500
101559
0.8141
64
64
64
p hat300-1
300
33917
0.7562
8
8
p.hat1000-1
1000
377247
0.7552
10
10
10
p-hat700-1
700
183651
0.7507
11
11
11
p-hat500-1
500
93181
0.7469
9
9
p.hat1500-1
1500
839327
0.7466
12
hamming6-4
1312
0.6508
4
c fa
500
78123
0.6262
126
126
126
c-fat200-5
200
11427
0.5742
58
58
58
p-hat300-2
300
22922
0.5111
25
25
25
p.hat1000:
1000
254701
0.5099
46
46
46
brock200_2
200
10024
0.5037
12
12
p 700-2
700
122922
0,5024
44
44
DSJC1000_55
1000
249674
0.4998
15
15
c2000.5
2000
999164
0.4998
16
15
16
sanr400.0.5
400
39816
0.4989
13
13
13
DSJC500_5
500
62126
0.4980
13
13
13
p hat500-2
500
61804
0.4954
36
36
36
p-hat1500-2
1500
555290
0.4939
65
65
65
johnson8-2-4
28
168
0.4444
brock20c_3
200
7852
0.3946
15
hamming8-4
256
11776
0.3608
16
16
16
keller4
171
5100
0.3509
11
11
brock800_1
800
112095
0.3507
23
20
21
brock200
200
6811
0.3423
17
16
17
sanr200.00 7.
200
6032
0.3031
18
18
18
san200_0.77
200
5970
0.3000
30
30
30
sanr400.0.7
400
23931
0.2999
21
p hat hat1000-3
1000
127754
0.2558
68
67
68
Continued on next page
19

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Graph Name
Density
Optimal
PCQO-MIS
ReduMIS
3
300
11460
0.2555
36
36
36
brock200_1
200
5066
0.2546
21
21
21
p h00-3
700
61640
0.2520
62
62
62
brock400L1
400
20077
0.2516
27
25
25
p.hat500-3
500
30950
0.2481
50
50
50
p.hat1500-3
1500
277006
0.2464
94
93
94
johnson16 6-
120
1680
0.2353
8
8
johnson8
0.2319
14
hamming10-4
1024
89600
0.1711
40
40
40
johnson32-2-4
496
14880
0.1212
16
16
16
sanr200.0.9
200
2037
0.1024
42
42
42
C125.9
125
787
0.1015
34
34
34
C250.9
250
3141
0.1009
44
44
44
gen400-p0 99.5
99.75
400
7980
0.1000
75
75
gen400_p0. 9_55
400
7980
0.1000
55
55
gen200 1112000pp..3000 p0.9.44
200
1990
0.1000
44
42
44
gen200_p0.99 9955
200
1990
0.1000
55
55
55
san200_0.9.2
200
1990
0.1000
60
60
60
san400 0.9
400
7980
0.1000
100
100
100
san200_0.9.1
200
1990
0.1000
70
70
70
s san200_0. 9.3
200
1990
0.1000
44
44
gen400_p0. 9_65
400
7980
0.1000
65
65
65
C500.
500
12418
0.0995
57
56
57
C1000.9
1000
49421
0.0989
68
65
67
hamming6-2
64
192
0.0952
32
32
32
MANN_a9
45
72
0.0727
16
16
16
hamming8-2
256
1024
0.0314
128
128
128
hammi ng 0-2
1024
5120
0.0098
512
512
512
Table 3: Performance PCQO-MIS on the DIMACS graphs dataset as compared to the known optimal solution (column
5) and SOTA heuristic ReduMIS (column 7). Graphs are ordered based on graph density n(x-1j (column 4). For our method, the time limit 30 seconds per graph. Bold results indicate the cases where pCQO-MIS or ReduMIS don't achieve the optimal.
2nz
E.2. Results of Large Random ER Graphs Under Time Constraints
In this subsection, we compare our method with Gurobi and ReduMIS using 10 ER graphs with n = 3000 and 10.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7) with time budget of 30 seconds using the following machine: CPU Intel(R) Xeon(R) Gold 6418H and GPU NVIDIA RTX A6000.
Average MIS Size at different p
Method
p 0.1
p= 0.2
p= = 0.3
=
p = 0.5
p= 0.6
p == 0.7
ReduMIS
61.5
Gurobi
55.6
29.1
20.3
14.3
10.8
8.8
7.1
PCQO-MIS (Ours)
39.8
25.2
18.5
14.3
Table 4: Evaluation of PCQO-MIS the ReduMIS and Gurobi with time budget of 30 seconds using ER graphs with
3000 and different probability of edge creation, i.e., p. This approximately indicates the density in the graph. This means that the number of edges is from 449850 (for p = 0.1) to 31 3148950 (for p 0.7).
Results are given Table 4. As observed, under a time budget of 30 seconds, out method outperforms the ILP solver and ReduMIS. The axper-parameterr tuning was done using one graph for every p and as recommended in Appendix E.9.1. For example, for p = 0.1, we used one graph out of the 10 and performed the quick grid search, then used the parameters for the
20

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
remaining 9.
E.3. Results of BA Graphs from (Wu et al., 2025)
In this subsection, we report results on Barabási- (BA) graphs corresponding to those used Table of (Wu et al., 2025). These graphs were generated using the NetworkX library and are parameterized by n and q, where denotes the number of nodes and denotes the number of edges attached from a new node to existing nodes (Barabási & Albert, 1999). We evaluate graphs with E {100, (100,300, 1000}. The results from ReduMIS and OnlineMIS are taken directly from (Wu et al., 2025), while results for our method were obtained using a total runtime of 33.7 minutes, which includes hyperparameter tuning. This differs from (Wu et al., 2025)'s setup, which used time limit of up to 96 hours. For additional details on their experiment setup and hardware, see the caption of Table 2 in (Wu et al., 2025).
Results are presented in Table 5. We match ReduMIS exactly in six cases, and report close result in another. However, in Iwo cases, method underperforms with a difference of more than three nodes.
Ti
OnlineMIS
ReduMIS
Average MIS Size PCQO-MIS (Ours)
100
5
39.5
39.5
39.5
100
15
21.63
21.63
21.63
300
5
123.13
123.13
123.13
300
15
71.38
71.38
71.38
300
50
49.88
50
50
1000
5
417.13
417.13
416.625
1000
15
245
246.38
241.875
1000
50
115.75
116.88
111.75
1000
150
150
150
150
Table 5: Evaluation of PCQO-MIS vs. ReduMIS using set of the BA graphs in (Wu et al., 2025). OnlineMIS is an accelerated version of ReduMIS, where a fewer number of graphs reductions are used after performing local search. Results of ReduMIS and OnlineMIS are as reported in (Wu et al., 2025).
In our experiment, we used 7/ 1, T 250, and = 0.9. For the remaining hyperparameters, we perform grid search over a E {0.01, 0.001, 0.0001, 0.00001} and y E {100, 200, 500, 750} for each graph and report the best result.
E.4. Impact of the Adopted Momentum-based Gradient Descent Optimizer
Extremal stationary points may be rare and depend of the graph connectivity as was discussed Appendix A.5. However, our use of MGD not solely motivated by the need to escape these unwanted points when they exist. It is also driven by the empirical observation that, when starting from the same initial point, MGD converges minimizers with larger MaxIS values while avoiding the overshooting observed with vanilla GD. Also, momentum is generally used accelerate convergence of GD. To support our claim that MGD converges to better minima compared to GD, we conduct the following experiment: We use 5 ER graphs with n 100 and p E {0.3, 0.6} (probability of edge creation) and run GD vs. MGD, using the same 7, 7/, a and the initializations. Table 6 shows the results. As observed, on average, MGD converges to larger MIS. Furthermore, MGD avoids the all 0's which is the case of overshooting in GD.
p
0.3
p 0.6
Step size a
GD Avg. MIS
MGD Avg. MIS
GD Avg. MIS
MGD
Avg. MIS
0.0001
11.2 11.7
12.9
6.7
6.9
0.0002
12.8
0.0
6.3
Table 6: Comparison of average MIS sizes for different step sizes a using GD and MGD across different densities (as indicated by = 0.3 and 0.6). For both cases, we use 7 = n and 7 ==1.
F.5. Ablation Study on the Clique Term in PCQO-MIS
In PCQO-MIS, the clique term is introduced to (i) encourage the optimizer to select two nodes connected by an edge in the complement graph, leveraging the duality between the clique and MIS problems, and (ii) to discourage sparsity in the solution given the L norm in (6). This is our motivation and intuition.
21

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
The improvements observed empirically in terms of enhancing stability, preventing overshooting, and leading to better minima.
Tables and 8 compare the cases with and without the clique term (i.e., >' = vs. 7 0) over the ER dataset used in Table 1. The results are presented as the average MIS size (Table 7) and the number of steps for first solution (Table 8) in the format "without-with" and are obtained across different values of a (step size) and 7 (edge penalty parameter). The results are reported after optimizing 50 batches of initializations for each unique set of hyper-parameters. We note that the range of y is selected based on the criterion in Theorem 2.
Step size
7 350.0
450.0
525.0
7 600.0
4c-06
-9.07
0.0-39.18
0,0 400.7
0.0 42.59
9c-06
0.0 44.51
0.0 44.21
0.0 43.87
0.0 43,57
4c-05
0.0-41.52
0.0-41.21
0.0 40.99
0.0 40.69
9c-05
0.0-40.70
0.0-40.61
40.54
0.0 40.60
0.0004
40.50-41.00
40.35 40.94
40.39 40.71
0.0009
40.34 44.244
10.42-41.11
40.44 40.91
40.45 40.77
0,004
40.28-41.11 41.11
40.45-40.92
40.38 40.86
40.39 40.79
0.009
40.55 -0.50
40.35 40.75
40.27 40.85
0.04
40.39-41.2
40.35 40.93
40.44 400.8
0.09
40.35-41.11
40.95
40.40 40.90
40.46 40.84
0.4
40.42 41.22
40.32 40.98
40.43 40.90
40.29 40.82
0.9
40.39
41.15
40.34 41.03
40.21 40.86
40.10 40.60
Table 7: Average MaxIS size in the format "without-with the clique term, across different values of step size a and edge penalty parameter yy. Bold results correspond to the cases where PCQO-MIS obtained better results than the best of pQO (underlined).
The following are the key observations from Table 7 for which the bold results correspond to cases where using the clique term resulted in a MaxIS size higher than the best of the "without" case (underlined):
1. As observed, the difference between best PCQO (with) and the best pQO (without) is nearly 4 nodes which is similar to what report in T nearly 4.1 nodes on average.
2. When 7 our approach returns better results across learning rates and 7 compared to 7 0. Additionally, 7 = 0 is not competitive compared with any of the baseline solvers we tested in this paper, as it achieves most 40.55 (the underlined result in the table). Only when the clique term is introduced does our method become competitive with other solvers.
3. Out of all combinations above, there are only two cases where y' = 0 is slightly better.
In addition to average MaxIS size, we evaluated how many optimizer steps were required to obtain the first MaxIS solution for each set of parameters. The results are reported as the average time to first solution over the ER dataset in Table 8. In all cases, 7' = 7 finds a viable solution first. We conjecture that, due to the presence of the third clique term, a "smoother" optimization landscape is created for each of the evaluated hyperparameter sets.
We note that the above results indicate that there might exist set of hyper-parameter with no MC term that result in better MaxIS when compared to using the MC term. However, from our experiments, we only obtain the competitive results with baselines when the MC term is included.
E.6. Comparison with a Clique Heuristic Solver
In this subsection, we include comparison results of 31 graphs (from DIMACS dataset) with efficient clique heuristic solver called the Minimal Independent Set based Approach (MISB) (Singh & Govinda, 2014), which demonstrated competitive performance on these graphs with n < 500.
Table 9 shows the results of 5 graphs as examples. The complete table can be found online The results of MISB is sourced from Table of (Singh & Govinda, 2014). can be seen that our algorithm consistently outperforms MISB and achieves optimal near-optimal solution. Here, p is the graph density.
htt gie / hubb con/ Iedermet /pC00- mi benchnerk rk /bcl the in Compa in laon. with MDTR MML Mal ver.gdf
22

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Step size
7 350.0
7 450.0
7 525.0
? 600.0
4e-06
N/A 425,00
N/A 442.00
N/A 436,45
N/A 4434.99
9e-06
N/A 261.44
N/A 244.73
N/A 234.52
N/A 222.99
4c-05
N/A 733.29
N/A WA-78 71.94
N/A 71.35
N/A 70.45
9c-05
N/A 44.226
N/A 47.54
N/A 48.34
N/A 48.91
0.0004
206.95 29.82
208.50-311
209.69 32.80
210. 86 33.79
0.0009
134.53 26.66
26.63
136.81 - 28.56
138.15 29.88
139.29 30.82
0.004
89.53 24.00
91.95 26.09
93,42 27,48
94.66 28.65
0.009
81.19- 23,41
83.63 25,62
85.07 27.04
86.31 28.38
0.04
74.05 23.31
76.39 25.46
77.86 26.92
79.20 28.11
0.09
72.23 23.38
74,66 - 25,49
76.05 26.98
77.31 28.14
0.4
70.51 23.33
72.91 25,43
74.32 26.90
75.55 28.16
0.9
69.92 23.34
72.27 25,42
73.71 26.92
74.99 28.15
Table 8: Average number of steps to converge the format "without with" the clique term, for various step sizes a and
edge penalties y. Bold results follow Table
Graph Name
77
Density
Optimal
Ours
MISB MC Solver (Singh & Govinda, 2014)
co-Sat500-2
500
115611
0.92
26
26
p 300-2
22922
0.51
25
25
samr200.0
0.30
brock400_1
20077
0.25
25
gen200_p0.. 9_55
200
1990
0.10
55
55
49
Table 9: Comparison between pCQO-MIS and MISB clique solver.
We note that in the recent survey paper about clique solvers (Marino al., 2024), the authors recognized ReduMIS (Lamm et al., 2016) (the main heuristic we compare with in our paper) as "extremely effective" for solving the clique problem (see Section 3. when compared to other methods.
E.7. Comparison with the Relu-based Dataless Solver
Here, we compare PCQO-MIS with the dataless Neural Network (dNN) MIS solver in (Alkhouri et al., 2022). In this experiment, we use 10 GNM graphs with (n,m) (100, 500) and report the average MIS size and average run-time (in seconds) for solving one initialization. The results are given in Table 10. As observed, PCQO-MIS outperforms the dNN-MIS method in (Alkhouri et al., 2022) in terms both the run-time and MIS size.
Method
Average MIS Size
Average Run- Time (seconds)
dNN-MIS (Alkhouri et al., 2022)
27.4
24
PCQO-MIS (Ours)
29.9
0.7
Table Evaluation of PCQO-MIS vs. the MIS dNN solver in (Alkhouri et al., 2022) terms of MIS size and run-time (seconds) over 10 GNM graphs with (n, m) = 5100,500).
E.8. Comparison with Leading data-centric Solver with Different Densities
In this subsection, we compare our approach with the leading data-driven baseline, DIFUSCO. DIFUSCO uses a pre-trained diffusion model trained on ER700-800 graphs (with p = 0.15) labeled using ReduMIS.
Here, we compare PCQO-MIS to DIFUSCO using graphs (with n 700) with varying edge creation probabilities, p. The results, presented in Table 11, averaged over 32 graphs for each p, with DIFUSCO utilizing 4-sample decoding. For PCQO-MIS, hwwiSS,,ppppaaaae hyperparameters remain fixed across all values of p.
As observed, our method consistently outperforms DIFUSCO in both average MIS size and run-time. Notably, our run-time remains constant as the number of edges increases, supporting our claim that the run-time scales only with the number of nodes in the graph. DIFUSCO reports relatively smaller MIS sizes, particularly for = 0.05 and p = 0.2, which are slightly different from the training graphs. This underscores the generalization limitations of leading learning- baaeed method.
23

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
DIFUSCO
(Sun & Yang, 2023)
PCQO-MIS (Ours)
Probability of Edge Creation p
Avg. MIS Size (1)
Run-time (4)
Avg. MIS Size (1)
Run-time ())
0.05
88.25
4.62
97.34
4.73
0.10
58
8.63
59.25
4.71
(Training setting DIFUSCO)
40.81
0.2
29.22
17.66
33.78
4.45
Table 11: Evaluation of PCQO-MIS the ER70OO-rained DIFUSCO (with 0.15) in (Sun & Yang, 2023) in terms of average MIS size and sequential run-time (minutes) over 32 ER graphs for each p.
E.9. PCQO-MIS Hyper-Parammeers
In this subsection, we outline the PCQO-MIS parameters (i.e., 7, 7/, a. B, and r)) used in the paper, along with examples from the tuning procedure conducted select these parameters.
Table 12 provides the specific parameter values used for Table 1 and Figure 2 in Section 4. These hyper-papee peeeerr-rametrrss selected based on grid search as those provided in Table 13 and Table 14 for the ER dataset. The captions of these tables provide the parameters we fix and the parameters we vary, and in both cases, we report the average MIS size of ER graphs. Other than the first three columns of the last row of Table 13, the reported average MIS size (in both tables) vary between 37.67 and 41.83. This indicates that PCQO-MIS results do not vary significantly with the choice these parameters term of finding feasible solutions.
Graph Dataset
Edges-penalty
MC parameter
Step size a
Momentum ,
Steps T'
Exploration parameter
SATLIB
900
3e
0.875
30
2,25
ER
350
7
9e
0.9
450
2,25
GNM with a {50, 500, 1000)
100
5
le
0.55
200
GNM with n (1500, 2000)
100
10
1e
0.55
200
Table 12: Hyper-parameters for PCQO-MIS used in Section those in Table 13 and Table 14.
This selection is made based on ablation studies such as
Step Size
8 0.5
8 0.7
le-2 2
41.83
38.83
38.17
39.83
5e
42.00
38.83
37.50
40.17
lc-3
41.17
38.67
38.17
39.67
40.83
39.00
40.00
le
37.67
41.17
41.00
5c-5
38.33
41.50
40.50
40.00
5.67
35.33
17.83
40.67
Table 13: Average MIS size of 6 ER graphs for different values a and [3. Here, 7 = -300, 7/ = and 300. The
initialization of x(0] is h in Eq. (13).
Edges Penalty
MC Term 7'
PCQO-MIS (MaxIS Size)
300
1
40.67
300
5
40.16
500
5
40.33
775
1
39.33
775
5
39.67
Table 14: Average MaxIS size of ER graphs using different values of y and y Here, 1e-5, B 0.9, and T 300.
The initialization of x[0] is h in Eq. (13).
1. A BASIC WARM START PROCEDURE FOR HYPER-PARAMETTE TUNING
Here, we describe the procedure the grid search we used for our hyper-paramete tuning. We first perform a grid search over the following parameters using T = 750. We use a E {0.5, 0.05, 0.005, 0.0005, 0.0001, 0.00001, 0.000001, 0.0000001) }. (0.99, 0.9, 0.75). 7 E (250, 500, 1000, 2000, 5000), and 7' E (1, Based on the results of these combinations,
24

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
second loop that takes all the best choices from the grid search and reduces T until it impacts solution size. This procedure takes approximately 30 seconds to
ER graph.
To run our method on new graphs, we recommend using the parameters tuning grid search.
E.10. Results of Table based on the Number of Batches
In this subsection, provide the main PCQO-MIS results based on the number of batches. Table 15 (resp. Table 16) presents the results for the SATLIB (resp. ER) dataset. The results of Table are obtained from these tables.
Batches Solved
pCQO MIS (MIS Size)
PCQO-MIS MIS (Run time)
408,286 286
0.408
417.228
20
420.276
4.726
30
421.610
6.996
40
422.456
9.265
50
422.988
11.533
60
423
13.799
70
423.706
16.065
80
423 423.930 930
18.329
90
424.096
20.593
100
424.278
110
424.406
25.119
120
424.508
27,380
130
424. 226.606
29.641
140
424 686
31 901
150
424.736
34.161
160
424.798
36.419
170
424.856
38,678
180
424.906
40.935
190
424 424.950 950
43.191
200
425.00
45,448
210
425.032
47.704
49,959
230
425.098
$2,214
240
425.126
$4,468
250
425.148
56.722
Table 15: PCQO-MIS SATLIB results (average MIS size and total run time in minutes) including the number of batches used (column 1).
25

---

Differentiable Quadratic Optimization For The Maximum Independent Set Problem
Batches Solved
PCQO-MIS (MIS Size)
POQO-MIS (Run time)
39.344
0.153
10
43.086
1.159
20
43.836
2.266
44.117
3.367
44.367
4,466
50
44.500
5.563
60
44.578
6.659
70
44.656
7.753
80
44.695
8.848
90
44,750
9.942
100
44.789
11.035
110
44,828
12.129
120
44.836
13.222
130
44.859
14.315
140
150
44.898
16,502
160
44,914
17,595
170
44,938
18,688
180
44, 961
19.781
190
44,969
20.875
200
44.977
21.968
210
44.984
23.062
220
45.000
24.155
230
45.016
25 249
240
45.023
26,342
250
45.023
27.435
260
270
45.039
29.622
280
45.039
30.715
290
45.047
31 809
300
45.055
32,902
310
45,062
33,996
320
45.070
35.089
330
45.078
36.182
340
45.078
37.276
350
45.078
38.369
360
45.078
39.462
380
45.078
41.648
390
45.078
42.741
400
45.094
43.834
410
45.094
44.928
420
45.094
46.021
430
45.094
47.115
440
45.094
48,208
450
102
49,301
460
45.102
50.393
470
45,102
$1.486
490
45.102
S3.672
500
45.109
54.766
Table 16: PCQO-MIS ER results (average MIS size and total run time in minutes) including the number of batches used
(column 1).
26


Reviews:
[{"review_id": "wVTatGHwSU", "reviewer": "Reviewer_HPTx", "summary": "In solving the Maximum Independent Set (MIS) problem, the authors propose its continuous relaxation as an optimization problem of a quadratic differentiable function, which can be solved by first-order gradient-based method starting from multiple parallel initial points. The proposed method named parallelized Clique-Informed Quadratic Optimization of MIS (pCQO-MIS) is compared with other MIS solvers.\n\n## Update after rebuttal\n\nMy concerns and questions about the paper have been clarified, and I intend to maintain my original recommendation 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": "We would like to thank the reviewer for their comments. Below is a point-by-point response. \n\n### (C1) **As the optimization method is based on the first-order gradient method, the proposed algorithm has advantage on the scalability, showing less run-time on denser and bigger graph. However, the heuristic or the exact method seems to be more beneficial in graphs with less number of edges and vertices**\n\nUtilizing a first-order gradient method indeed allows our method to scale to larger graphs, which is particularly evident in relatively denser graphs, as shown in the results of Figure 2.\n\nHowever, as the reviewer correctly points out, for sparse graphs, methods like ReduMIS and ILP solvers tend to yield better solutions in terms of both MIS size and run-time. In ILP solvers, the number of constraints exactly equals the number of edges in the graph. Since sparser graphs have fewer edges, these solvers are able to find solutions more quickly. Similarly, ReduMIS benefits from a greater effectiveness of MIS-specific graph reductions it employs when operating on sparser graphs.\n\n### (C2) **Good selection of hyperparameter $\\gamma$ is essential in finding the correct solution, thus solving the problem repeatedly with different hyperparameters is unavoidable in practice.**\n \nWe agree with the reviewer that selecting $\\gamma$ according to Theorem 9 is important for guaranteeing that all local minimizers are feasible MaxISs.\n\nTo obtain the best solutions in our method, hyper-parameters fine-tuning is needed in some cases. An example of such a fine-tuning procedure is discussed in Tables 7 and 8 of Appendix D.5.\n\nWe say \"in some cases\" because in our evaluation on the DIMACS graphs in Table 3, we applied a set of hyperparameters optimized on one graph of the dataset, across the entire dataset and obtained the optimal solution in 49 out of 61 graphs. Note that these graphs are very diverse and vary not only in terms of graph order but also density (see columns 2 to 4 of Table 3).\n\nHyper-parameter tuning is not a major bottleneck as there have been several studies for automatic and efficient hyper-parameter tuning (such as bilevel optimization [A]) and our method can be integrated with them. \n\n[A] Franceschi et al, \"Bilevel Programming for Hyperparameter Optimization and Meta-Learning\" ICML2018\n\n### (C3) **Regarding to (4), $x^T ee^T x = \\||x\\||^2_1$ does not hold if any of the element of is negative; but this does not seem to be relevant with the main arguments.**\n \nThe reviewer is indeed correct. Thanks for pointing this out. Given that $x\\in [0,1]^n$, there won't be negative elements. To be more rigorous, in the revised paper, we will add the following sentence before presenting Eq. (4). \"For $x\\in [0,1]^n$, we can write $x^T ee^T x = \\||x\\||^2_1$ and therefore (introduce equation 4)\". \n\n### (Q1) **Can you give more detailed explanation about why (9) indicates MaxIS?**\n\nThank you for your question. The condition in Eq. (9) checks whether some $z\\in \\{0,1\\}^n$ is a **fixed point or not** given a projected gradient descent step. This is based on our characterizations of the proposed objective, which indicates that all binary fixed points are local minimizers and therefore MaxISs. \n\nWe reach this conclusion by showing that: \n\n1. All local minimizers are binary (Lemma 8), and \n2. All local minimizers are MaxISs if $\\gamma > 1 + \\gamma' \\Delta(G')$ (Theorem 9)\n\nAnother reason that Eq. (9) can be used for checking MaxIS is due to Theorem 12: When $x'$ such that $\\nabla_xf(x')=0$ exists, then it is also a fixed point. However, in the proof of Theorem 12, we show that $x'$ can not be binary. Therefore, in Eq. (9), we only check $z\\in \\{0,1\\}^n$ which is the binarized version of $x$. This means that if the optimizer reaches a binary fixed point, then it must be MaxIS. \n\nWe hope that we have answered the reviewer's question. Please let us know if it remains unclear. \n\n### (Q2) **In Table 1, the run-time of the exact method differ too much between the two datasets. I am suspecting that this phenomenon happens because in the number of constraints in the integer linear program becomes too many in the dense ER dataset. Is there a way to work around this constraint rather than listing all constraint for all edges?**\n \nThe reviewer is correct. The main reason for exact methods taking longer times on denser graphs is that, in the MIS problem, the number of constraints in the ILP exactly equals the number of edges in $G$. Cutting plane methods [B] may be used to reduce the number of constraints in the ILP, but such a method for the exact ILP methods is beyond the scope of our paper, as we focus on differentiable approaches. \n\n[B] G. Nemhauser and L. Wolsey, \"Integer and Combinatorial Optimization,\" Wiley 1998.", "claims_and_evidence": "The continuous relaxation of the MIS problem seems to be valid.", "methods_and_evaluation_criteria": "The experiment presented is comparison of benchmarks between pQQ-MIS and other existing MIS solvers. All procedure seems valid.", "theoretical_claims": "The main theoretical claims seem to be correct.", "experimental_designs_or_analyses": "The experiment presented is comparison of benchmarks between pQQ-MIS and other existing MIS solvers. All procedure seems valid.", "relation_to_broader_scientific_literature": "The proposed optimization strategy, MGD, is a first-order gradient-based optimization which has a benefit in scalability. In this sense, we can think about an optimization strategy that utilizes multiple parallel computational nodes when the given $\\mathbf{A}_{G}$ is too big to fit in a single machine.", "essential_references_not_discussed": "No special reference I would like to add.", "other_strengths_and_weaknesses": "As the optimization method is based on the first-order gradient method, the proposed algorithm has advantage on the scalability, showing less run-time on denser and bigger graph. However, the heuristic or the exact method seems to be more beneficial in graphs with less number of edges and vertices. \n\nAlso, good selection of hyperparameter $\\gamma$ is essential in finding the correct solution, thus solving the problem repeatedly with different hyperparameters is unavoidable in practice.", "other_comments_or_suggestions": "Regarding to (4), $x^TJ_nx = \\Vert x \\vert_1^2$ does not hold if any of the element of $x$ is negative; but this does not seem to be relevant with the main arguments.", "questions_for_authors": "1. Can you give more detailed explanation about why (9) indicates MaxIS?\n\n2. In Table 1, the run-time of the exact method differ too much between the two datasets. I am suspecting that this phenomenon happens because in the number of constraints $z_v + z_u \\leq 1, \\forall (v,u) \\in E$ in the integer linear program becomes too many in the dense ER dataset. Is there a way to work around this constraint rather than listing all constraint for all edges?", "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": "iMer6eS8BX", "reviewer": "Reviewer_keSC", "summary": "The paper introduces pCQO-MIS, a new quadratic optimization approach for solving the Maximum Independent Set (MIS) problem. By incorporating a maximum clique (MC) term, the method improves convergence and exploration, using parallelized momentum-based gradient descent to efficiently find maximal independent sets. The authors provide theoretical results ensuring that local minimizers correspond to maximal independent sets and present an efficient procedure for MIS checking. Experimental results show that pCQO-MIS outperforms existing exact, heuristic, and data-driven methods, achieving larger MIS sizes and faster runtimes, particularly for denser graphs, without the need for training data.", "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": "We would like to thank the reviewer for their comments.\n\nWe are glad that the reviewer finds our method well-motivated. We also appreciate the reviewer acknowledging that we prove the correctness of the method, ensuring that local minimizers correspond to maximal independent sets.\n\nPlease see our response below regarding the comparison with a clique solver.\n\n### (C) **Comparison with a clique-based method.**\n\nWe thank the reviewer for their comment. \n\nIn the recent survey paper about the MC solvers [A], the authors recognized ReduMIS (the heuristic we compare against in our submission) as **\"extremely effective\"** for solving the clique problem (see Section 3.3.1 of [A]) when compared to other methods. \n\nTo fully address the reviewer's comment, we have included comparison results of 31 graphs (from DIMACS) with an MC heuristic solver called MISB [B], which demonstrated competitive performance on the selected graphs with $n\\leq 500$. \n\nBelow we show the results of 5 graphs as examples. The complete results can be found in (https://anonymous.4open.science/r/pCQO-mis-benchmark-81AF/Comparison_with_MSIB_MC_Solver.pdf). The results of MISB is sourced from Table 1 of [B]. It can be seen that our algorithm *consistently outperforms* MISB and achieves optimal or near-optimal solution in these cases. Here, $\\rho$ is the graph density. \n\n| Graph Name |  $n$  | $m$    | $\\rho$ | Optimal | Ours  | MISB Clique Solver [B] | \n|-------------|----------|--------|--------------|-|-|-|\n| cc-fat500-2 | 500 |\t115611 | 0.92 | 26 | **26** |  26 | \n| p_hat300-2 | 300 |22922 | 0.51 | 25 | **25** |  24 |\n| sanr200_0.7 | 200 |6032 | 0.3 | 18 | **18** |  16 |\n| brock400_1 | 400 |20077| 0.25 | 27 | **25** |  23 |\n| gen200_p0.9_55 | 200 |1990| 0.1 | 55 | **55** |  49 | \n\nWe plan to include additional comparisons in the camera-ready version if our paper is accepted.\n\n[A] A Short Review On Novel Approaches For Maximum Clique Problem: Form Classical Algorithms to Graph Neural Networks and Quantum Algorithms. March 2024. (https://arxiv.org/pdf/2403.09742v1)\n[B] A simple and efficient heuristic algorithm for maximum clique problem. ISCO 2014.", "claims_and_evidence": "The proposed method is well motivated from the duality of MIS and clique problem. The authors prove the correctness of the method ensuring that local minimizers correspond to maximal independent sets.", "methods_and_evaluation_criteria": "The proposed algorithm together with the efficient MIS checker makes the proposed method both efficient and effective. The authors evaluate the performer of the method with comparison to several baselines on graphs with different density. Comparison on both quality and run time are provided.", "theoretical_claims": "No", "experimental_designs_or_analyses": "Yes, The authors evaluate the performer of the method with comparison to several baselines on graphs with different density. Comparison on both quality and run time are provided. Just wonder how the proposed algorithm compares to clique-based method?", "relation_to_broader_scientific_literature": "The MIS is a NP-problem with wide applicability.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "y0Z4vNWAmI", "reviewer": "Reviewer_sDzA", "summary": "This paper proposes a novel solution for the Maximum Independent Set Problem (MIS), a well-known NP-hard problem. The proposed method extends the quadratic formulation by [Pardalos & Rodgers, 1992] by introducing a max clique term into the non-convex objective function. The optimization is performed using projected momentum-based gradient descent, and a rounding step is applied to obtain a candidate solution for MIS. The method is designed to leverage GPU-based parallel execution.\n\nThe authors conduct experiments on Erdős-Rényi (ER) graph datasets and SATLIB graph datasets, demonstrating that the proposed approach outperforms existing learning-based methods. Additionally, on high-density graphs, the method achieves superior performance compared to exact solvers such as Gurobi and CP-SAT, as well as heuristic solvers like ReduMIS.", "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": "We would like to thank the reviewer for their comments. Please refer to (https://anonymous.4open.science/r/pCQO-mis-benchmark-81AF/Tables_rebuttal.md) for Tables A, B, & C. \n\nWe are glad that the reviewer finds the paper to be well-structured & highly readable & that our claims are clear & supported both theoretically & experimentally. \n\n### (W1) **Additional results for the clique term**. \n\nThe clique term is introduced to (i) encourage the optimizer to select two nodes connected by an edge in the complement graph, leveraging the MIS & MC duality, & (ii) to discourage sparsity in the solution given the $\\ell_1$ norm. We note that the computational cost for including the third term is the same as not including it (Remark 3).\n\nWe have empirically observed that the third term improves the optimization process by enhancing stability, preventing overshooting, & leading to better minima.\n\nTable A compares the cases *without* (pQO) & *with* (pCQO) the clique term ($\\gamma' = 0$ vs. $\\gamma' = 7$) over the ER dataset used in Table 1. The results are presented as the average MIS size in the format \"without–with\" & are obtained across different values of $\\alpha$ (learning rate) & $\\gamma$ (edge penalty parameter). The results are reported after optimizing 50 batches of initializations for each set of hyper-parameters. We note that the range of $\\gamma$ is selected based on the criteria in Theorem 9. \n\nKey observations from Table A (bold results correspond to cases where pCQO resulted in a MaxIS size higher than the best of the pQO case (underlined)) are:\n\n1. The difference between pCQO & pQO is nearly 4 nodes which is similar to what we report in Table 1.\n\n2. pCQO approach returns better results across most $\\alpha$'s' & $\\gamma$'s' compared to pQO. Additionally, $\\gamma' = 0$ is not competitive compared with most other baselines, as it achieves at most 40.55 (the underlined result in the table). Only when the clique term is introduced does our method become competitive with other solvers.\n\n3. Out of all combinations above, there are only two cases where pQO is slightly better. \n\nAdditionally, we evaluated how many optimizer steps were required to obtain the first MaxIS solution for pCQO & pQO. See Table B. In all cases, pCQO finds a viable solution first. We conjecture that, due to the presence of the third clique term, a \"smoother\" optimization landscape is created for each of the evaluated hyperparameter sets. We will include the above experiments in the revised version of the paper. \n\n### (W2) **The motivation of MGD.**\n\nExtremal stationary points depend on graph connectivity, as noted in Appendix C. However, our use of MGD is not solely to escape these points but also due to the empirical observation that, from the same initial point, MGD converges to minimizers with larger MaxIS values while avoiding the overshooting seen in vanilla GD. Additionally, momentum generally accelerates GD convergence. We will revise the remark to clarify this point.\n\nIn Table C, we use 5 ER graphs with $n=100$ & $p\\in \\{{0.3,0.6\\}}$ (probability of edge creation) & run GD vs. MGD, **using the exact same $\\gamma, \\gamma', \\alpha,$ & the initializations.** As observed, on average, MGD converges to larger MIS. Furthermore, MGD avoids the all 0's which is the case of overshooting in GD. \n\n\n### (W3) **Large high-density graphs.**\n\nWe appreciate the reviewer’s comment. The main advantage of our solver is most evident for dense, large graphs, where (i) ILPs are impractical due to extensive run-time, & (ii) ReduMIS fails to significantly reduce graph size. Our motivation is to address these challenges rather than focus on a specific application.\n\nWe will clarify this in the revised paper & leave application-specific explorations for future work. MIS has broad applications in scheduling, genome sequencing, & fault detection, often involving large, dense graphs. For instance, [A] applies conflict graph constructions in genome sequencing.\n\nEven sparse graphs can become dense in dynamic settings.\n\n[A] On the Maximal Cliques in C-Max-Tolerance Graphs & Their Application in Clustering Molecular Sequences\n\n### (W4) **Sensitivity to hyper-parameters.**\n\nThank you for your comment. When we stated that our method is not very sensitive to the selection of these hyperparameters, we meant that a range of values can yield feasible solutions. In other words, obtaining results with our method does not heavily depend on precise hyper-parameter tuning, as long as they satisfy the condition in Theorem 9. We will refine this claim to better align with our intended meaning.\n\nThat said, we agree with the reviewer that achieving the best results require hyper-parameter tuning. We note that we do hyper-parameter tuning on one instance & apply it on the other graphs. This means that the additional running time of each graph increases by the tuning time divided by the total number of graphs in the dataset. We will include this discussion in the revised paper.", "claims_and_evidence": "The authors' claims are clear throughout the paper and are supported both theoretically and experimentally.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria are meaningful. While the datasets used in the main text feel somewhat insufficient, the additional experiments in the appendix make the overall evaluation satisfactory.", "theoretical_claims": "I conducted a brief verification of the theoretical claims and did not find any particular issues.", "experimental_designs_or_analyses": "I have reviewed the experimental setup and did not identify any major issues.", "relation_to_broader_scientific_literature": "This paper contributes to an important research topic in the field of combinatorial optimization, namely the Maximum Independent Set problem, by developing a novel differentiable solver. The proposed method is simple, achieves favorable experimental results, and is considered to make a sufficient contribution.", "essential_references_not_discussed": "All important citations have been properly included without any issues.", "other_strengths_and_weaknesses": "Overall, this paper is well-structured and highly readable. The approach is straightforward and convincing in relation to its objective, and the claims are well-supported both theoretically and experimentally.\n\nThe weaknesses are as follows. \n\n* I did not fully understand why the maximum clique term in Equation (3) leads to such significant improvements. The authors provide an explanation on the right side of line 124, but it does not seem entirely convincing in justifying the substantial improvements observed in Table 1. Further investigation of this aspect, possibly using additional experimental results, could strengthen the credibility of the approach.\n\n* In Appendix B, it is stated that non-extremal stationary points $x'$ are rarely contained within the box constraint, and even if they are, they appear at most at a single point. In this case, the ability of MGD to escape saddle points, as discussed in Remark 13, might not be very useful. If this is the case, the motivation for using MGD, as described in Remark 13, seems less convincing.\n\n* The experimental results suggest that the proposed method performs particularly well on high-density graphs (i.e., graphs with a large number of edges) compared to existing exact solvers and heuristic approaches. However, how common is it to need to find independent sets in such high-density graphs? In practical applications, aren't graphs often less dense? It would be helpful if the authors could clarify the intended application areas of their approach. That being said, I do not mean to suggest that developing strong methods for high-density graphs is unimportant in this research field.\n\n* The authors have conducted a sensitivity analysis of the parameters in the proposed method, which is commendable. However, in Section D.5, they state:\n\"Other than the first three columns of the last row of Table 7, the reported average MIS size (in both tables) varies between 37.67 and 41.83. This indicates that pCQO-MIS is not very sensitive to the choice of these parameters.\"\nContrary to this claim, I got the impression that the output is relatively sensitive to parameter choices. This is because, in the Maximum Independent Set problem, once a provisional solution is found, increasing the solution size by even one can be quite difficult. As a result, the variation between 37 and 42 could indicate a significant difference in solution quality.\nFurthermore, from Table 6, it appears that the parameters need to be adjusted for each problem instance. If these parameters must be determined through an ablation study, wouldn’t this require additional computational cost for the proposed method?", "other_comments_or_suggestions": "* A.3. Proof of Lemma 9 in appendix should be A.3. Proof of Lemma 8.", "questions_for_authors": "Please see Other Strengths And Weaknesses.", "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 authors develop a novel gradient-based optimization problem for the max independent set problem, which incorporates an additional term corresponding to the complementary graph’s max clique problem, scaled by a hyperparameter gamma. This results in an optimization problem that is non-convex but amenable to modern gradient optimization techniques, and the authors parallelize the optimization over initializations and settings of gamma. Experimentally, they show that their method is competitive with various state of the art solvers, but is more computationally scalable in settings with more edges. 

Overall, reviewers were generally positive, viewing the work as an interesting practical development on an important problem, which provides a benefit for a certain type of scalability.  Authors agreed to include new experiments comparing at least one max clique solver, as well.
Decision: Accept (poster)