<p>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
<a href="http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf" rel="nofollow noreferrer">http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf</a>
) are Kleinberg-consistent. This is because the intra-cluster distances/similarity does not influence the objective function in any way.</p>

<p>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.</p>

CC BY-SA 3.0
2017-03-02T21:50:34.353Z
2017-03-02T21:50:34.353Z
Aryeh
<p>Spectral clustering refers to a family of graph-based algorithms, which usually rely on a <em>similarity</em> function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity function, say $e^{-\rho(x,y)}$.</p>

<p>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 <em>clustering</em> $\mathcal{C}$ of $S$, which is just a nontrivial partition of $S$.</p>

<p>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$.</p>

<p><b>Question</b>: Is there any specific natural spectral clustering algorithm that is known (not) to be Kleinberg-consistent?</p>

<p>NB: The question is explicitly <em>not</em> about the statistical consistency of spectral clustering, which has been addressed in the literature.</p>

<machine-learning><lg.learning><clustering>
Kleinberg-consistency of spectral clustering
Aryeh
# Kleinberg-consistency of spectral clustering

(Asked by: username_0 on 2017-02-28)

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.

**Tags:** machine-learning, lg.learning, clustering


---

## 1 answers

### Answer by username_0 on 2017-03-02. Score: 0 | Accepted answer

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.


---

