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.


1 Answer 1


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 definitions http://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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.