Graph Cuts with Size Constraints Through Optimal Transport

Image clustering is an important task in computer vision and machine learning in general for which new applications are constantly appearing. The task of image clustering boils down to grouping images into clusters such that the images within the same clusters are similar to each other, while those in different clusters are dissimilar. A common way to obtain an image dataset partition is through graph cuts which are also used as a component in more complex clustering paradigms such as subspace clustering. However, classical \textrm{min-cut} algorithms suffer from the formation of small groups which is why more balanced variants like the normalized and ratio cuts were introduced. We believe however that these balance constraints are too restrictive for some applications (long-tailed clustering) while not being restrictive enough for other applications (when searching for perfectly balanced partitions) since the constraint is not hard. Here, we propose a new graph cut algorithm for partitioning with arbitrary size constraints by formulating the graph cut problem as a special case of the Gromov-Wasserstein problem and proposing an algorithm that is only a ratio of $\mathcal{O}(log(n))$ slower than the classical spectral clustering algorithm. Experiments on several real world dataset showcase the performance of our approach.