Cardinality-Constrained Binary Quadratic Optimization via Extreme Point Pursuit, with Application to the Densest K-Subgraph Problem

Cardinality-constrained binary quadratic optimization appears in various applications such as finding a densest size-constrained subgraph from a graph. It is a challenging combinatorial problem, and in this paper we tackle the problem by a continuous optimization approach. Our method, called the extreme point pursuit, works by relaxing the cardinality-constrained binary set to its corresponding convex hull, and then by adding an appropriate penalty function to encourage the solution to be an extreme point of the convex hull. The resulting extreme-point pursuit formulation is non-convex. As an intuitive strategy to try to avoid poor local minima, we adopt a homotopy optimization method wherein we start with an easy convex problem and gradually change the landscape of the problem to approach the extreme-point pursuit formulation. Experiments based on real-world large-scale graph data are performed to demonstrate the performance and efficiency of our method.