Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity function, say $e^{-\rho(x,y)}$.What I called Kleinberg-consistency is commonly referred to in the clustering literature as Kleinberg's consistency axiom. A clustering algorithm takes a finite point set $S$ together with a metric $\rho$ as input, and returns a clustering $\mathcal{C}$ of $S$, which is just a nontrivial partition of $S$.The clustering algorithm $A$ is consistent if it satisfies the following property: Run $A$ on point set $S$ with metric $\rho$, to obtain some clustering $\mathcal{C}$. Now take any $\rho'$ such that all $x,y\in S$ that fell into the same cluster $C\in\mathcal{C}$ satisfy $\rho'(x,y)\le\rho(x,y)$ while for all $x,y$ that fell into distinct clusters, we have $\rho'(x,y)\ge\rho(x,y)$. Consistency requires that if we run $A$ on $(S,\rho')$, we obtain the same clustering $\mathcal{C}$ as we did for $\rho$.Question: Is there any specific natural spectral clustering algorithm that is known (not) to be Kleinberg-consistent?NB: The question is explicitly not about the statistical consistency of spectral clustering, which has been addressed in the literature.
Kleinberg-consistency of spectral clustering
machine learning;lg.learning;clustering
Answering my own question, with a hat tip to Misha Belkin (private correspondence). It is easy to see that the unnormalized mincut and the RatioCut algorithm (see here for precise definitionshttp://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf) are Kleinberg-consistent. This is because the intra-cluster distances/similarity does not influence the objective function in any way.The Ncut-based clustering algorithm, however, is not Kleinberg-consistent. This can be seen by making the similarity weights within some cluster sufficiently large that it is able to absorb nearby clusters with negligible extra charge.