Abstract
Min cut is an important graph partitioning method. However, current solutionsto the min cut problem suffer from slow speeds, difficulty in solving, andoften converge to simple solutions. To address these issues, we relax the mincut problem into a dual-bounded constraint and, for the first time, treat themin cut problem as a dual-bounded nonlinear optimal transport problem.Additionally, we develop a method for solving dual-bounded nonlinear optimaltransport based on the Frank-Wolfe method (abbreviated as DNF). Notably, DNFnot only solves the size constrained min cut problem but is also applicable toall dual-bounded nonlinear optimal transport problems. We prove that for convexproblems satisfying Lipschitz smoothness, the DNF method can achieve aconvergence rate of \(\mathcal{O}(\frac{1}{t})\). We apply the DNF method tothe min cut problem and find that it achieves state-of-the-art performance interms of both the loss function and clustering accuracy at the fastest speed,with a convergence rate of \(\mathcal{O}(\frac{1}{\sqrt{t}})\). Moreover, theDNF method for the size constrained min cut problem requires no parameters andexhibits better stability.