In this paper, we investigate adding the regularization terms to the Min Cut cost function, in order to avoid creation of small singleton sets of clusters. We first consider the case where the regularization is the sum of the squared size of the clusters, weighted by the parameter \(\alpha \) . This regularization leads to a simple shift transformation of the input, i.e., subtracting the pairwise similarities by \(\alpha \) , which provides a straightforward quadratic cost function. We further extend the regularization to the pairwise similarities and employ an adaptive shift of the pairwise similarities which does not require fixing a regularization parameter in advance.
The size constrained Min Cut then constitutes a special case of the latter form.
Such a shift might render some pairwise similarities to be negative. We study the connection to Correlation Clustering, another cost function which performs on both positive and negative similarities, and conclude the equivalence of these two methods given the shifted (regularized) pairwise similarities in a direct and straightforward way (beyond the argument based on algorithmic reduction proposed in [1]}).
However, our method, called Shifted Min Cut, provides a principled way to deduce such negative edge weights (adaptively). Thereafter, we develop an efficient optimization method based on local search to solve the new optimization problem. We further discuss the fast theoretical convergence rate of this local search algorithm.
In the following, we study the impact of shifting the pairwise similarities on some common flat and hierarchical clustering methods where they often exhibit an invariant behaviour with respect to the shift of pairwise similarities, unlike the basic Min Cut cost function. Finally, we perform extensive experiments on several real-world datasets to study the performance of Shifted Min Cut compared to the alternatives.
