将最小割问题转化为双边界非线性输运，实现快速高精度聚类。
Dual-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clustering
- 提出双边界非线性输运框架，用Frank-Wolfe方法求解
- 收敛速度达O(1/√t)，性能优于现有方法且无需调参
- 适用于多种约束最小割场景，稳定性强
最小割是重要的图划分方法，但现有解法存在速度慢、难求解、易陷入简单解等问题。本文首次将最小割问题松弛为双边界约束，并将其视为双边界非线性最优输运问题。针对此问题，提出基于Frank-Wolfe的DNF方法。证明对于满足Lipschitz光滑性的凸问题，该方法收敛率为\(\mathcal{O}(\frac{1}{t})\)。应用于最小割时，其损失与聚类准确率均达当前最优，收敛速率\(\mathcal{O}(\frac{1}{\sqrt{t}})\)，且无需参数调节，表现更稳定。
原文摘要 · Abstract (English)
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 dual-bounded constraint and, for the first time, treat the min cut problem as a dual-bounded nonlinear optimal transport problem. Additionally, we develop a method for solving dual-bounded nonlinear optimal transport based on the Frank-Wolfe method (abbreviated as DNF). Notably, DNF not only solves the size constrained min cut problem but is also applicable to all dual-bounded nonlinear optimal transport problems. 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 the DNF method to the min cut problem and find that it achieves state-of-the-art performance in terms of both the loss function and clustering accuracy at the fastest speed, with a convergence rate of \(\mathcal{O}(\frac{1}{\sqrt{t}})\). Moreover, the DNF method for the size constrained min cut problem requires no parameters and exhibits better stability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。