Kavli Affiliate: Jia Liu
| First 5 Authors: Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu
| Summary:
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 ReLU-based or 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 parallelized
Clique-Informed Quadratic Optimization 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
runtime relative to their inference time. Additionally, a key advantage of
pCQO-MIS is that, unlike exact and heuristic solvers, the runtime 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.
| Search Query: ArXiv Query: search_query=au:”Jia Liu”&id_list=&start=0&max_results=3