# Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you can get labels on the rest of the vertices by a majority vote of adding the kernel contribution. In spectral clustering, the sign of the eigenvector components of the largest eigenvalue of the Laplacian determines the class assignment of the vertices. Since these techniques seem to be doing similar things based on the graph Laplacian, is there a link between spectral clustering and the diffusion or heat kernel? Is one the generalization of the other under some assumptions?

What I have found so far:

1. The paper "The Principal Components Analysis of a Graph, and Its Relationships to Spectral Clustering" by Saerens et al. seems to say something about this. They say that one flavor of the diffusion kernel (the Euclidean Commute Time Distance) is the same as one type of spectral clustering.

2. The paper "Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators" by Nadler et al. also has a result that I am yet to parse.

3. Following "Graph spectral image smoothing using the heat kernel" by Zhan and Hancock, we can observe that if the Laplacian $L = USU^T$, (with $U$ as the eigenvectors and $S$ the diagonal matrix of eigenvalues) and the heat kernel is $H=\exp(-\beta L)$, then $H = Uexp(-\beta S)U^T$. So for some $\beta$ we just have to take the smallest eigenvalue to get the approximate $H$.

Disclaimer: This is cross-posted from CV.

• There is absolutely a link. Have a look at Mauro Maggioni's website and publications to get started, if no one else answers I might give a better answer later. – icurays1 Nov 25 '15 at 1:06
• @icurays1 do you know which paper refers to this? – highBandWidth Dec 3 '15 at 2:24