Balanced Graph Cut With Exponential Inter-Cluster Compactness
Danyang Wu, Feiping Nie, Jitao Lu, Rong Wang, Xuelong Li · IEEE Transactions on Artificial Intelligence · 2021
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 \lbrace \mu x\rbrace$. 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$\mu$. To solve the optimization problem involved in Exp-Cut model, an efficient heuristic solver is proposed and the computational complexity is$\mathcal {O}(n^2)$per iteration. Experimental results demonstrate that our proposals outperform competitors on all benchmarks with respect to clustering performance, balanced property, and efficiency.