Adjustable Balanced Min-Max Cut for graph clustering

Graph clustering methods have attracted considerable attention due to their superior performance in capturing complex data structures. Among them, Min-Max Cut (MCut) is a classic graph partitioning criterion that balances intra-cluster similarity and inter-cluster separability. However, traditional MCut-based clustering lacks an explicit mechanism for controlling clustering balance and suffers from high computational complexity during optimization. To address these limitations, we propose a novel graph clustering model—Adjustable Balanced Min-Max Cut (ABMC). ABMC incorporates an adjustable balance mechanism that enables explicit control over the preference for clustering balance. Meanwhile, we design an improved coordinate descent algorithm that avoids the continuous relaxation, eigen-decomposition and post-processing steps commonly required by spectral methods, reducing the time complexity from O(n³) to O(|E|) (where n denotes the number of samples and |E| the number of edges). Experimental results on multiple benchmark datasets demonstrate that the proposed method achieves significant advantages in both clustering accuracy and computational efficiency.