Constrained 1-Spectral Clustering
This work addresses the need for incorporating prior constraints in clustering for applications like data analysis, but it is incremental as it builds on existing 1-spectral clustering techniques.
The authors tackled the problem of integrating cannot-link and must-link constraints into spectral clustering by proposing a constrained 1-spectral clustering method, which consistently outperformed other methods in experiments.
An important form of prior information in clustering comes in form of cannot-link and must-link constraints. We present a generalization of the popular spectral clustering technique which integrates such constraints. Motivated by the recently proposed $1$-spectral clustering for the unconstrained problem, our method is based on a tight relaxation of the constrained normalized cut into a continuous optimization problem. Opposite to all other methods which have been suggested for constrained spectral clustering, we can always guarantee to satisfy all constraints. Moreover, our soft formulation allows to optimize a trade-off between normalized cut and the number of violated constraints. An efficient implementation is provided which scales to large datasets. We outperform consistently all other proposed methods in the experiments.