On Spectral Clustering: Analysis and an algorithm

Despite many empirical successes of spectral clustering methods(cid:173) algorithms that cluster points using eigenvectors of matrices de(cid:173) rived from the data- there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly different ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well.