A scalable clustering algorithm to approximate graph cuts

Abstract

Due to its computational complexity, graph cuts for cluster detection and identification are used mostly in the form of convex relaxations. We propose to utilize the original graph cuts such as Ratio, Normalized or Cheeger Cut in order to detect clusters in weighted undirected graphs by restricting the graph cut minimization to the subset of $st$-MinCut partitions. Incorporating a vertex selection technique and restricting optimization to tightly connected clusters, we therefore combine the efficient computability of $st$-MinCuts and the intrinsic properties of Gomory-Hu trees with the cut quality of the original graph cuts, leading to linear runtime in the number of vertices and quadratic in the number of edges. Already in simple scenarios, the resulting algorithm Xist is able to approximate graph cut values better empirically than spectral clustering or comparable algorithms, even for large network datasets. We showcase its applicability by segmenting images from cell biology and provide empirical studies of runtime and classification rate.