In spectral clustering we take eigenvector corresponding to K smallest eigenvalues. Then we do K means clustering on these eigenvector to get final clusters. What will happen if we take different number of eigenvectors than number of clusters we want ?


Theoretically, log2(k) components could be enough.

But usually clusters are not that well balanced, that you could get all 2^l combinations of eigenvectors stable, usually one will mask the other.

If you go back to the theory of spectral clustering, you'd have one eigenvector for each connected component. Now the clusters are unfortunately connected, so we don't completely get this ideal situation, but you'd expect one eigenvector for each "almost component", too.

  • $\begingroup$ Can you please share the related resource or give intuition behind sqrt(k) components? $\endgroup$ – sneh gupta Mar 7 '19 at 5:54
  • $\begingroup$ Sorry. Log2(k) of course. Enough to separate k components. $\endgroup$ – Has QUIT--Anony-Mousse Mar 7 '19 at 21:54
  • $\begingroup$ no problem.. I still have one doubt, kindly look into it. But what if that eigen vectors are more or less similar. By that I mean, each eigen vector is cutting the graph almost from the same places. Is there any proof or intution that this won't happen ? $\endgroup$ – sneh gupta Mar 9 '19 at 7:48
  • $\begingroup$ They are orthogonal. They can't cut in the same places. $\endgroup$ – Has QUIT--Anony-Mousse Mar 9 '19 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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