  The (constrained) minimization of a ratio of set functions is a problem
frequently occurring in clustering and community detection. As these
optimization problems are typically NP-hard, one uses convex or spectral
relaxations in practice. While these relaxations can be solved globally
optimally, they are often 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 non-negative set functions allows a tight relaxation into an
unconstrained continuous optimization problem. This result leads to a flexible
framework for solving constrained problems in network analysis. While a
globally optimal solution for the resulting non-convex problem cannot be
guaranteed, we outperform the loose convex or spectral relaxations by a large
margin on constrained local clustering problems.
