Eigenvectors of graph Laplacian for spectral clustering

Question

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?

Answer 1

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.].

Answer 2

I suspect that the difference is using the adjacency matrix $A$ vs. using the Laplacian matrix $L = D-A$.

If I remember correctly, Ng Jordan Weiss use a normalized version of the adjacency matrix $A$, so higher value in $A_{ij}$ means stronger connection between $i$ and $j$. The important spectral components of the graph are then captured in the larger eigenvectors of the matrix.

In the other version, using the Laplacian $L$, where higher value of $L_{ij}$ means weaker connection between $i$ and $j$ (relative to $i$ and other nodes). So the important spectral components would be captured in the smaller eigenvectors of $L$ - representing where the graph has the least "weak" connections.

What do you think? Did I get it right?