Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin
cs.LG
Submitted: 2025-01-30
Updated: 2026-09-02
Comments: Corrected formatting issues and other errors
License: http://creativecommons.org/licenses/by/4.0/
The gist: Min cut is an important graph partitioning method.
Terminology
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 O(1 over 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.
Sources
- Convergence Rate of Frank-Wolfe for Non-Convex Objectives
- Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions
- Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks