Learning Spectral Clustering

Spectral clustering refers to a class of techniques which rely on the eigenstructure ofa similarity matrix to partition points into disjoint clusters with points in the same cluster having high similarity and points in different clustershaving low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.