Differentiable Quadratic Optimization For the Maximum Independent Set Problem

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.

We are glad that the reviewer finds the paper to be well-structured & highly readable & that our claims are clear & supported both theoretically & experimentally.

(W1) Additional results for the clique term.

The 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).

We have empirically observed that the third term improves the optimization process by enhancing stability, preventing overshooting, & leading to better minima.

Table 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.

Key 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:

1. The difference between pCQO & pQO is nearly 4 nodes which is similar to what we report in Table 1.

2. 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.

3. Out of all combinations above, there are only two cases where pQO is slightly better.

Additionally, 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.

(W2) The motivation of MGD.

Extremal 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.

In 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.

(W3) Large high-density graphs.

We 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.

We 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.

Even sparse graphs can become dense in dynamic settings.

[A] On the Maximal Cliques in C-Max-Tolerance Graphs & Their Application in Clustering Molecular Sequences

(W4) Sensitivity to hyper-parameters.

Thank 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.

That 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.

We would like to thank the reviewer for their comments.

We 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.

Please see our response below regarding the comparison with a clique solver.

(C) Comparison with a clique-based method.

We thank the reviewer for their comment.

In 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.

To 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$.

Below 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.

We plan to include additional comparisons in the camera-ready version if our paper is accepted.

[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) [B] A simple and efficient heuristic algorithm for maximum clique problem. ISCO 2014.

We would like to thank the reviewer for their comments. Below is a point-by-point response.

(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

Utilizing 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.

However, 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.

(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.

We agree with the reviewer that selecting $\gamma$ according to Theorem 9 is important for guaranteeing that all local minimizers are feasible MaxISs.

To 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.

We 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).

Hyper-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.

[A] Franceschi et al, "Bilevel Programming for Hyperparameter Optimization and Meta-Learning" ICML2018

(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.

The 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)".

(Q1) Can you give more detailed explanation about why (9) indicates MaxIS?

Thank 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.

We reach this conclusion by showing that:

1. All local minimizers are binary (Lemma 8), and
2. All local minimizers are MaxISs if $\gamma > 1 + \gamma' \Delta(G')$ (Theorem 9)

Another 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.

We hope that we have answered the reviewer's question. Please let us know if it remains unclear.

(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?

The 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.

[B] G. Nemhauser and L. Wolsey, "Integer and Combinatorial Optimization," Wiley 1998.