MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
  and Degree Descent Criterion
Dehua Peng Zhipeng Gui Huayi Wu
As the most typical graph clustering method, spectral clustering is popular
and attractive due to the remarkable performance, easy implementation, and
strong adaptability. Classical spectral clustering measures the edge weights of
graph using pairwise Euclidean-based metric, and solves the optimal graph
partition by relaxing the constraints of indicator matrix and performing
Laplacian decomposition. However, Euclidean-based similarity might cause skew
graph cuts when handling non-spherical data distributions, and the relaxation
strategy introduces information loss. Meanwhile, spectral clustering requires
specifying the number of clusters, which is hard to determine without enough
prior knowledge. In this work, we leverage the path-based similarity to enhance
intra-cluster associations, and propose MeanCut as the objective function and
greedily optimize it in degree descending order for a nondestructive graph
partition. This algorithm enables the identification of arbitrary shaped
clusters and is robust to noise. To reduce the computational complexity of
similarity calculation, we transform optimal path search into generating the
maximum spanning tree (MST), and develop a fast MST (FastMST) algorithm to
further improve its time-efficiency. Moreover, we define a density gradient
factor (DGF) for separating the weakly connected clusters. The validity of our
algorithm is demonstrated by testifying on real-world benchmarks and
application of face recognition. The source code of MeanCut is available at
https://github.com/ZPGuiGroupWhu/MeanCut-Clustering.