Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clustering
Fangyuan Xie, Jinghui Yuan, Feiping Nie, Xuelong Li · 2025
Read Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clustering by Fangyuan Xie, Jinghui Yuan, Feiping Nie, Xuelong Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18143.txt.
Introduction
Fangyuan Xie, Jinghui Yuan, Feiping Nie, and Xuelong Li recast a graph cutting problem as a bounded transport problem to speed up clustering. Their 2025 paper works on min cut, a classic way to split graphs into groups. Standard solvers run slowly, resist solution, or collapse to trivial splits.
Size limits on groups become upper and lower bounds in the new framing. The result is a double-bounded nonlinear transport problem, handled here for the first time. Their solver builds on the Frank-Wolfe method and reaches a proven shrink rate for smooth convex cases. Applied to size-limited min-cut clustering, it runs on eight benchmark sets. Scores match or beat rival methods on several sets and measures, the authors report.
Catalog record
| CREATOR | Fangyuan Xie, Jinghui Yuan, Feiping Nie, Xuelong Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18143
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clustering Fangyuan Xie, Jinghui Yuan, Feiping Nie, Xuelong Li 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 𝒪 ( 1 t ) \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. 1 Introduction Graph clustering is a fundamental issue in machine learning, widely applied in diverse fields such as computer vision ( Yan et al., 2024 ) , gene analysis ( Liu et al., 2024 ) , social network analysis ( Singh et al., 2024 ) and many others. Among the numerous graph clustering approaches, Min Cut clustering (MC) stands out as a classical method ( Henzinger et al., 2024 ) . Despite its effectiveness, the MC problem has a trivial solution in which all the objects are clustered into one cluster, where the cut of G reaches its minimal value zero. Thus, it is known that the clustering result of MC tends to produce unbalanced clusters, often resulting in small, fragmented groups due to its tendency to prioritize cuts with minimal edge weights ( Nie et al., 2010 ) . To address this limitation, various refinements to MC have been proposed ( Hagen and Kahng, 1992 ; Zhong and Pun, 2021 ; Tsitsulin et al., 2023 ) . Recently, ( Nie et al., 2024 ) propose the parameter-insensitive min cut clustering with flexible size constraints. In fact, the most direct approach to balance clustering results in MC is to add size constraints for each cluster. That is, in MC problem, the lower bound b_{l} and upper bound b_{u} are added in column sums of discrete indicator matrix Y , which guarantees each cluster contains a reasonable number of objects. Nevertheless, the optimization for the size constrained problem is not easy since the coupling of constraints. For each row of Y , it is required that only one element is one and others are zeros. The column sums need to lie in [b_{l},b_{u}] . In this paper, we relax the discrete indicator matrix into probabilistic constraints and resolve this problem from the perspective of nonlinear optimal transport. Optimal transport (OT) theory ( Ge et al., 2021 ; Fatras et al., 2021 ; Flamary et al., 2021 ) has become a fundamental tool in various fields, including machine learning ( Montesuma et al., 2024 ; Wang et al., 2024 ; Yuan et al., 2024 ) and computer vision ( Shi et al., 2024b ; Shi et al., 2023 ) . It provides a principled approach for aligning probability distributions and optimizing resource allocation. The OT problem is to minimize the inner product of cost matrix and transport matrix, which is a linear problem. Besides, it is assumed the source and target distributions are fixed. This means OT can not be applied in the size constrained MC problem directly. To address these challenges, we propose the Doubly Bounded Nonlinear Optimal Transport (DB-NOT) problem, which introduces both upper and lower bounds on the transport plan while accommodating non-linear objective functions. This novel formulation extends the classical OT framework, enabling the modeling of problems with bounded feasibility regions and non-linear optimization goals. The DB-NOT problem poses significant computational challenges due to the interaction of double-bounded constraints and the complexity of non-linear objective functions. Traditional methods for solving OT problems, such as Sinkhorn iterations ( Nguyen et al., 2024 ) or linear programming ( Peyré et al., 2019 ) , are inadequate in this setting because they are designed for linear or unconstrained formulations. Therefore, there is a pressing need for an optimization algorithm that can efficiently handle DB-NOT problem. To tackle this problem, we propose the Double-bounded Nonlinear Frank-Wolfe (DNF) method, inspired by the classical Frank-Wolfe algorithm ( Jaggi, 2013 ) . The DNF method is specifically tailored to address the challenges of the DB-NOT framework by iteratively optimizing within the feasible region defined by the double-bounded constraints. The core idea of the DNF method is to compute a feasible gradient within the constraint set that best approximates the negative gradient matrix. By searching along this feasible gradient, the DNF method efficiently minimizes the non-linear function while maintaining compliance with the double-bounded constraints. Through iterative updates and convex combinations of feasible gradients, the method ensures that the descent direction remains computationally efficient and effective. To demonstrate the practical utility of our approach, we apply the DNF to size constrained MC clustering. In summary, our contributions are fourfold. • For the first time, we formulate the Double-bounded Nonlinear Optimal Transport (DB-NOT) problem, which introduces both upper and lower bounds on the transport plan, extending the classical optimal transport framework. This problem seeks to find a transport plan that minimizes a given cost function while satisfying double-bounded constraints, ensuring that the transport plan remains within the prescribed bounds. • Inspired by the Frank-Wolfe method, we propose the DNF (Double-bounded Nonlinear Frank-Wolfe) method for solving the DB-NOT problem. The DNF method is specifically designed to handle the unique challenges in DB-NOT framework. • We establish the convergence properties of the DNF method under different assumptions on the objective function. For convex and L -smooth objectives, DNF converges to a global optimum, with the objective suboptimality decreasing at a rate of \mathcal{O}(1/t) . For general non-convex and L -smooth objectives, we show that the minimum Frank Wolfe gap among the first t iterates decreases at a rate of \mathcal{O}(1/\sqrt{t}) . • The size constrained min cut clustering framework benefits from the ability of DNF method to handle non-linear constraints effectively, ensuring clusters of appropriate sizes while minimizing the cut value. Experiments on diverse datasets, demonstrate that the DNF-based approach outperforms traditional methods in terms of clustering quality. The results underline the practical applicability and advantages of the proposed method in real-world scenarios. 2 Preliminaries 2.1 Notations The matrices are denoted by italic capital letters and vectors are presented by lowercase letters. Z=(z_{1},z_{2},\dots,z_{n})\in\mathbb{R}^{d\times n} is the data matrix, in which d is the dimensionality and n is the number of samples. Y\in Ind\in\mathbb{R}^{n\times c} is the indicator matrix, in which each row has only one element of one and the rest elements are zeros. c is the number of clusters. The affinity graph S could be constructed on Z in a number of ways, such as by using Euclidean distance, cosine similarity, or kernel-based methods like the Gaussian kernel function. The Laplacian matrix is L=D-S where D=\operatorname{diag}\{d_{11},d_{22},\dots,d_{nn}\} and d_{ii}=\sum_{j=1}^{n}s_{ij} . b_{l} and b_{u} are the minimum and maximum number of samples in each cluster. The elements in 1_{c}\in\mathbb{R}^{c} are all ones. For simplicity of