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.
