Saarland University, Machine Learning Group, Fak. MI - Mathematik und Informatik, Campus E1 1, 66123 Saarbr├╝cken, Germany     

Machine Learning Group
Department of Mathematics and Computer Science - Saarland University


by Syama Sundar Rangapuram and Matthias Hein

An important form of prior information in clustering comes in the form of must-link and cannot-link constraints. In the paper [1], we presented a generalization of the popular spectral clustering technique to integrate such constraints. Motivated by the recently proposed 1-spectral clustering [2], our method is based on a tight relaxation of the constrained normalized cut problem into a continuous optimization problem. In contrast to the existing constrained spectral clustering methods, we can always guarantee to satisfy all constraints. Moreover, our soft formulation also allows to optimize a trade-off between normalized cut and the number of violated constraints. Our efficient implementation, that scales to large datasets, shows that our method consistently outperforms all the other proposed methods.


Constrained 1-Spectral Clustering has been developed by Syama Sundar Rangapuram, Max Planck Institute for Computer Science and Matthias Hein, Department of Computer Science, Saarland University, Germany. The Matlab code for Constrained 1-Spectral Clustering is published as free software under the terms of the GNU GPL v3.0. Please include a reference to the paper Constrained 1-Spectral Clustering and include the original documentation and copyright notice.

Download Constrained 1-SpectralClustering Code       (Version: 1.1, Matlab/C Code)

Unzip the file and see README.txt to setup and run the program. If there is any problem using this code, contact Syama Sundar Rangapuram:


[1] S. Rangapuram and M. Hein,
Constrained 1-Spectral Clustering,
In International conference on Artificial Intelligence and Statistics (AISTATS), 2012. PDF  (Long version: PDF )

[2] M. Hein and T. Bühler,
An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA,
In Advances in Neural Information Processing Systems 23 (NIPS 2010), accepted.
PDF  (Supplementary material: PDF )