# Graph Cuts with Arbitrary Size Constraints Through Optimal Transport

arXiv: https://arxiv.org/abs/2402.04732 · HTML: https://mlsanity.com/paper/2402.04732/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 72 references that are in the map.
- First posted on arXiv 7 Feb 2024.

## Builds on (most cited first, 19 of 19)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Deep Subspace Clustering Networks](https://mlsanity.com/paper/1709.02508/) (2017)
- [Sketch Less for More: On-the-Fly Fine-Grained Sketch Based Image Retrieval](https://mlsanity.com/paper/2002.10310/) (2020)
- [Robust and Efficient Subspace Segmentation via Least Squares Regression](https://mlsanity.com/paper/1404.6736/) (2014)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering](https://mlsanity.com/paper/1605.02633/) (2016)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Constructing Balance from Imbalance for Long-tailed Image Recognition](https://mlsanity.com/paper/2208.02567/) (2022)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm](https://mlsanity.com/paper/1703.09307/) (2017)
- [Co-clustering through Optimal Transport](https://mlsanity.com/paper/1705.06189/) (2017)
- [Approximating optimal transport with linear programs](https://mlsanity.com/paper/1810.05957/) (2018)
- [Geometry of Graph Partitions via Optimal Transport](https://mlsanity.com/paper/1910.09618/) (2019)
- [Approximating the Quadratic Transportation Metric in Near-Linear Time](https://mlsanity.com/paper/1810.10046/) (2018)

## Built on by (most cited first, 1 of 1)

- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)

## Abstract (arXiv)

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 O(log(n)) compared to the classical spectral clustering algorithm but was seen to be more efficient.