Spectral Clustering with Inconsistent Advice

Clustering with advice (often known as constrained clustering) has been a recent focus of the data mining community. Success has been achieved incorporating advice into the k-means framework, as well as spectral clustering. Although the theory community has explored inconsistent advice, it has not yet been incorporated into spectral clustering. Extending work of De Bie and Cristianini, we set out a framework for finding minimum normalized cuts, subject to inconsistent advice. Our results suggest that the framework will be successful in many situations.