Diffusion Kernels on Graphs and Other Discrete Structures

by Risi Imre Kondor and John Lafferty

This paper introduces a diffusion kernel for graphs. First please notice that the exponential of any symetric matrix is positive definite and therefore is a Gram matrix. Then we consider a diffusion process. At time t, each node would give a proportion α of its value to it neighbors. In matrix form, it corresponds to the negative Laplacian of a graph and we simply use it for the generating matrix of the kernel (diffusion kernel).

The authors studied its continuous form, its relationship to random walks on graphs and cases on special graphs. The interesting findings are: 1) Gaussian kernel on graphs is a special case of diffusion kernel; 2) its application in images and strings.