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

Abstract: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 \(\mathcal{O}(\frac{1}{t})\). 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.

Machine Learning (cs.LG)

arXiv:2501.18143 [cs.LG]

(or arXiv:2501.18143v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2501.18143 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.