Self tuning spectral clustering

"Self tuning spectral clustering" is a paper in NIPS2004 by L. Zelnik-Manor and P. Perona that realizes the very intuitive idea of multi-scale (scale space) clustering:

Abstract
Spectral clustering has been theoretically analyzed and empirically proven useful. There are still open issues:
(i) Selecting the appropriate scale of analysis,
(ii) Handling multi-scale data,
(iii) Clustering with irregular background clutter, and,
(iv) Finding automatically the number of groups.
We explore and address all the above issues. We first propose that a `local' scale should be used to compute the affinity between each pair of points. This local scaling leads to better clustering especially when the data includes multiple scales and when the clusters are placed within a cluttered background. We further suggest exploiting the structure of the eigenvectors to infer automatically the number of groups. This leads to a new algorithm in which the final randomly initialized k-means stage is eliminated.