Dataless Quadratic Neural Networks for the Maximum Independent Set Problem
<|reference_start|>Dataless Quadratic Neural Networks for the Maximum Independent Set Problem: 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.<|reference_end|>
@article{alkhouri2024dataless,
    title={Dataless Quadratic Neural Networks for the Maximum Independent Set
  Problem},
    author={Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu,
  Rongrong Wang, Alvaro Velasquez},
    journal={arXiv preprint arXiv:2406.19532},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.19532},
    primaryClass={cs.DM cs.LG}
}