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 for the MIS size, and
characterize stationary points. To solve our non-convex objective, we propose
solving parallel multiple initializations using momentum-based gradient
descent, complemented by an efficient MIS checking criterion derived from our
theory. Therefore, 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.
| Search Query: ArXiv Query: search_query=au:”Jia Liu”&id_list=&start=0&max_results=3