Balanced Graph Cut With Exponential Inter-Cluster Compactness

Recently, balanced graph-based clustering has been a hot issue in clustering domain, but the balanced theoretical guarantees of previous models are either qualitative or based on a probabilistic random graph, which may fail to various real data. To make up this vital flaw, this letter explores a novel balanced graph-based clustering model, named exponential-cut (Exp-Cut), via redesigning the intercluster compactness based on the exponential transformation exp μ x. It is worth noting that exponential transformation not only provides a bounded balanced tendency for Exp-Cut, but also helps Exp-Cut to achieve balanced results on an arbitrary graph via adjusting its curvature μ. To solve the optimization problem involved in Exp-Cut model, an efficient heuristic solver is proposed and the computational complexity is O(n2) per iteration. Experimental results demonstrate that our proposals outperform competitors on all benchmarks with respect to clustering performance, balanced property, and efficiency.