1
$\begingroup$

I have the following questions regarding the graph Laplacian for spectral clustering:

  1. What is the intuition behind projecting the Laplacian (D-A, where D is the degree matrix and A is the affinity matrix) along the k eigenvectors to determine k clusters in the dataset?

  2. The paper: "A tutorial on spectral clustering" by Ulrike von Luxburg mentions that this projection should be done along the first k eigenvectors (eigenvectors with k smallest eigenvalues), while the papers on "Self tuning spectral clustering" by Lihi Zelnik-Manor and Pietro Perona and the Ng Jordan Weiss algorithm suggests selecting the eigenvectors with the largest eigenvalues. My question is why does one suggest selecting the smallest eigenvectors and the others the largest ones for projecting onto a subspace and what is the significance of each?

  3. What is the significance of the second smallest eigenvalue being 0.1645?

$\endgroup$
  • $\begingroup$ isn't $A$ the adjacency matrix? $\endgroup$ – Dima Pasechnik Jul 23 '19 at 8:22
1
$\begingroup$

The dimension of the nullspace $N$ of $D-A$ is the number of the connected components of the graph, and moreover one can find an orthogonal basis of $N$ with non-negative eigenvectors, each of them being the indicator vector of a connected component. This is Prop.2 in A Tutorial on Spectral Clustering. Similar results hold for normalised Laplacians (cf. Prop.4 in [loc.cit.]).

This provides the intution for the general case, while selecting eigenvectors corresponding to the smallest eigenvalues.

As you compute these vectors in practice, rounding errors occur (as only for very small graphs you can hope to get an exactly computed $N$), and your 0 eigenvalues are appoximated by small in absolute value eigenvalues. So you'd need to decide what eigenvalues really approximate 0, and what eigenvalues don't. That $0.1645$ is some kind of thershold, I guess.


As to your claim that other papers suggest selecting eigenvectors with largest eigenvalues, I think you are mis-reading. E.g. check the description of Ng-Jordan-Weiss on p.7 of [loc.cit.].

| cite | improve this answer | |
$\endgroup$

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.