Constrained fractional set programs and their application in local clustering and community detection

30th International Conference on Machine Learning

Thomas Bu¨hler [e-mail] ; Max Planck Institute for Informatics & Saarland University ; Saarbru¨cken ; Germany ; Matthias Hein [e-mail]

PID  :  118397

来源: CEUR

【 摘 要 】

The (constrained) minimization of a ratio of set functions is a problem frequently occur ring in clustering and community detection. As these optimization problems are typically NPhard, one uses convex or spectral relax ations in practice. While these relaxations can be solved globally optimally, they are of ten too loose and thus lead to results far away from the optimum. In this paper we show that every constrained minimization problem of a ratio of nonnegative set functions al lows a tight relaxation into an unconstrained continuous optimization problem. This result leads to a flexible framework for solving con strained problems in network analysis. While a globally optimal solution for the resulting nonconvex problem cannot be guaranteed, we outperform the loose convex or spectral relaxations by a large margin on constrained