A Tutorial on Spectral Clustering by Ulrike von Luxburg
April 2013
For some of my recent work, I needed to make use of spectral clustering. The initial papers I read all used similar approaches, but the details varied dramatically. None of the articles appeared to offer any justification for their variations. It all appeared to be black magic.
Enter Ulrike von Luxburg. I guess it should not be much of a surprise that a paper titled “A Tutorial on Spectral Clustering” explains the actual details behind spectral clustering. von Luxburg describes the reasons behind the basic approach and attempts to explain the technique in terms of graph cuts, random walks, and perturbation theory.
I found the comparisons to graph cuts most illuminating. Spectral clustering can be thought of as a graph cut with relaxed constraints. The relationship is clearly outlined for two clusters, but holds for larger numbers of clusters.
This comparison immediately brings two things to mind. First, if you are using spectral clustering, you are trying to approximate a graph cut. Before reading this paper, I did not make the connection that my goal was a graph cut. Second, there are no guarantees about the quality of the spectral clustering solution; it can be arbitrarily worse than the optimal graph cut. If that is the case, are their better, more direct approaches to approximating the optimal graph cut?
Parameter settings and variations are also discussed. The discussion on the connectedness of the actual graph was very helpful for me. The algorithm I was using called for a fully-connected graph. von Luxburg recommends only using the k-nearest neighbors and I found much better performance following that guideline.
This tutorial is a very good, well-written paper. It helped me obtain better performance than I would have by just following the algorithms outlined in more specific articles. Also, it is always good to understand the assumptions you implicitly make by choosing a particular approach.