# Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 46 references that are in the map.
- First posted on arXiv 30 Jan 2025.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [OTA: Optimal Transport Assignment for Object Detection](https://mlsanity.com/paper/2103.14259/) (2021)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Learning Smooth Neural Functions via Lipschitz Regularization](https://mlsanity.com/paper/2202.08345/) (2022)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [MaskClustering: View Consensus based Mask Graph Clustering for Open-Vocabulary 3D Instance Segmentation](https://mlsanity.com/paper/2401.07745/) (2024)
- [Optimal Transport for Treatment Effect Estimation](https://mlsanity.com/paper/2310.18286/) (2023)
- [Shortest Paths in Graphs of Convex Sets](https://mlsanity.com/paper/2101.11565/) (2021)
- [MuSe-GNN: Learning Unified Gene Representation From Multimodal Biological Graph Data](https://mlsanity.com/paper/2310.02275/) (2023)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [Double-Bounded Optimal Transport for Advanced Clustering and Classification](https://mlsanity.com/paper/2401.11418/) (2024)
- [Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions](https://mlsanity.com/paper/2406.17506/) (2024)
- [Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping](https://mlsanity.com/paper/2408.02932/) (2024)
- [Deterministic Near-Linear Time Minimum Cut in Weighted Graphs](https://mlsanity.com/paper/2401.05627/) (2024)

## 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)

Min cut is an important graph partitioning method. However, current solutions to the min cut problem suffer from slow speeds, difficulty in solving, and often converge to simple solutions. To address these issues, we relax the min cut problem into a double-bounded constraint and, for the first time, treat the min cut problem as a double-bounded nonlinear optimal transport problem. Additionally, we develop a method for solving double bounded nonlinear optimal transport based on the Frank-Wolfe method (abbreviated as DNF). We prove that for convex problems satisfying Lipschitz smoothness, the DNF method can achieve a convergence rate of (O(frac1t)). We apply DNF to size-constrained min-cut clustering and evaluate it on eight benchmark datasets. DNF achieves competitive clustering performance and matches or outperforms the compared baselines on several datasets and metrics.