Graph Cuts with Arbitrary Size Constraints Through Optimal Transport
Chakib Fettal Lazhar Labiod Mohamed Nadif
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 regularized Gromov-Wasserstein problem. We then propose to
solve it using accelerated proximal GD algorithm which has global convergence
guarantees, 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.