Fast discrete spectral clustering with Harmonic min-max cut on Anchor Similarity Graph

Spectral clustering (SC) is a graph-based clustering algorithm widely applied in data mining and image processing. However, existing SC methods fail to deal with large-scale datasets due to the time-consuming construction of graphs and eigenvalue decomposition, and usually require additional k-means clustering to generate discrete label matrix, leading to information loss and effectiveness reduction. To address these issues, an innovative non-parametric discrete graph clustering model called Fast Discrete Spectral Clustering with Harmonic Min-Max Cut on Anchor Similarity Graph (FDSC-HMCA) is proposed in this letter. Specifically, the proposed method has the following features: (1) a novel approach, based on the anchor graph and the second-order similarity technique, is developed to construct the anchor-based adjacency matrix, making the model applicable to large-scale datasets; (2) a harmonic min-max cut framework with the anchor-based adjacency matrix is proposed, which significantly enhances robustness to “worst-case cluster” boundaries; (3) a coordinate descent (CD) algorithm is employed to solve the non-convex optimization problem of FDSC-HMCA, and the discrete label matrix is directly learned without extra k-means. Moreover, the computational complexity of the proposed method is analyzed. Experimental clustering results demonstrate that FDSC-HMCA exhibits good effectiveness and efficiency on six real-world datasets.