What is the difference between affinity matrix eigenvectors and graph Laplacian eigenvectors in the context of spectral clustering?

In spectral clustering, it's standard practice to solve the eigenvector problem

$$L v = \lambda v$$

where $L$ is the graph Laplacian, $v$ is the eigenvector related to eigenvalue $\lambda$.

My question: why bother taking the graph Laplacian? Couldn't I just solve the eigenvector problem for the graph (affinity matrix) itself, like the guy did in this video?

PS: I made this same question in CrossValidated but I think this is a more appropriate channel. Forgive me if I'm wrong.

• Video link is broken :( Apr 22, 2020 at 19:14

The concept is the same but you are getting confused by the type of data. Spectral Clustering as Ng et al. explain is about clustering standard data while the Laplacian matrix is a graph derived matrix used in algebraic graph theory.

So the point is that whenever you encode the similarity of your objects into a matrix, this matrix could be used for spectral clustering.

If you have standard data i.e. a sample-feature matrix, you can find the proximity or affinity or whatever you want to call it as a matrix and apply spectral clustering.

If you have a graph, this affinity would be anything like adjacency matrix, distance matrix or Laplacialn matrix and solving the eigenfunction for such a matrix gives you the corresponding result.

The point about using Laplacian rather than adjacency is to keep the so-called affinity matrix positive semi-definite (and normalized Laplacian matrix is a better choice as it gives you normalized eigenvalues between 0 and 2 and reveals the structure of graph much better).

So the long story short is that as long as you have a matrix containing the affinity of your data you can use spectral clustering in general. The difference is in details (i.g. the property of normalized Laplacian I just mentioned)

• Yes, I think I'm a little confused. It's still not clear to me. If I have standard data (no affinity related), I can make it an affinity matrix A by taking the pairwise distance between the data samples. Now if I see A as a graph, I can take the Laplacian and solve for the eigenvectors and get a solution; if I don't see A as a graph, I could simply solve for the matrix eigenvectors (PCA) and get a solution. What's the difference? Dec 13, 2015 at 11:44
• I read your question again. The answer is the properties (e.g. the one I mentioned in my answer) Laplacian matrix provides for better decomposition. However you absolutly can sole eigenfunction for any similarity related matrices and get some results which are different just in details. For instance about the PCA you mentioned: PCA takes the covariance matrix so it captures where the variance is high but in general the concept follows the same direction as the other spectral decomposition techniques. I'll proofread my answer soon as I see some "Saturday Night" sentences ;) Dec 13, 2015 at 16:36