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 **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 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
href{https://github.com/ledenmat/pCQO-mis-benchmark/tree/refactor}{{{pCQO-MIS}}}
| Search Query: ArXiv Query: search_query=au:”Jia Liu”&id_list=&start=0&max_results=3