Compressed constrained spectral clustering framework for large-scale data sets

The method of incorporating constraint information into spectral clustering, i.e., \constrained spectral clustering (CSC), can greatly improve clustering accuracy, and thus has been widely employed in the machine learning literature. In this paper, we propose a compressed CSC framework by combining specific graph constructions with a recently introduced CSC model. Particularly, our framework has ability to avoid losing the main partition information in the compression process. By presenting a theoretical analysis and empirical results, we demonstrate that our new framework can achieve the same clustering solution as that of the original model with the specific graph structure. In addition, because our framework utilizes landmark-based graph construction and the approximate matrix decomposition simultaneously, it can be applied to both feature and graph data in a more general way. Moreover, the parameter setting in our framework is rather simple, and therefore it is very practical. Experimental results indicate that our framework has advantages in terms of efficiency and effectiveness.