How do I choose number of clusters when Eigengap heuristic suggest 1 for spectral clustering?

Question

Eigengap heuristic Method suggest number of clusters k is usually given by the value of k that maximizes the eigengap (difference between consecutive eigenvalues). I plotted the Eigenvalue distribution for my Data: [

Eigengap heuristic would suggest cluster number: 1. How should I choose number of clusters in this case ?

Answer 1

The first eigenvalue in your plot is non-zero, whereas the last is one.

This seems to suggest that the Laplacian whose eigenvalues you are computing is different from the standard Laplacian $ L = D - W$, where $D$ is the matrix whose diagonal entries are degrees of nodes and $W$ is the weighted adjacency matrix. So in your plot, $\lambda_{19} = 1$ and $\lambda_{18} \neq 1$ but is $\approx 1$ which is indicative of the graph being one connected component.

So the correct way to interpret your plot would be to invert it ($\lambda \mapsto 1 - \lambda$) and then arrange them in increasing order, or to arrange them in decreasing order as-is.

Then you can use the eigengap heuristic to choose a suitable value for the number of clusters (7 seems to be a good choice as $\lambda_{13}-\lambda_{12}$ is large compared to $\lambda_{14}-\lambda_{13}$, or maybe 3 if the number of clusters is a constraint).

This is described in greater detail in Luxborg's excellent tutorial on Spectral Clustering, and you can find a footnote in Ng et al's seminal paper on the same.