Graph Cuts with Arbitrary Size Constraints Through Optimal Transport
This addresses the need for more adaptable graph cuts in applications like imbalanced clustering, offering a method that is not too restrictive or too loose in balance constraints.
The authors tackled the problem of graph partitioning with flexible size constraints by proposing a new algorithm based on Gromov-Wasserstein with a concave regularizer, achieving global convergence and sparsity with an additional computational cost of O(log(n)) compared to spectral clustering.
A common way of partitioning graphs is through minimum cuts. One drawback of classical minimum cut methods is that they tend to produce small groups, which is why more balanced variants such as normalized and ratio cuts have seen more success. However, we believe that with these variants, the balance constraints can be too restrictive for some applications like for clustering of imbalanced datasets, while not being restrictive enough for when searching for perfectly balanced partitions. Here, we propose a new graph cut algorithm for partitioning graphs under arbitrary size constraints. We formulate the graph cut problem as a Gromov-Wasserstein with a concave regularizer problem. We then propose to solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point, results in sparse solutions and only incurs an additional ratio of $\mathcal{O}(\log(n))$ compared to the classical spectral clustering algorithm but was seen to be more efficient.