skip to content

Analysis of graphs using diffusion processes and random walks (a random walk through spectral graph theory)

Presented by: 
E Hancock [York]
Tuesday 18th March 2008 - 11:00 to 12:00
INI Seminar Room 1

This talk will focus on how graph-structures can be analysed using diffusion processes and random walks. It will commence by explaining the relationship between the heat equation on a graph, the spectrum of the Laplacian matrix (the degree matrix minus the weighted adjacency matrix) and the steady-state random walk. The talk will then focus in some depth on how the heat kernel, i.e. the solution of the heat equation, can be used to characterise graph structure in a compact way. One of the important steps here is to show that the zeta function is the moment generating function of the heat kernel trace, and that the zeta function is determined by the distribution of paths and the number of spanning trees in a graph. We will then explore a number of applications of these ideas in image analysis and computer vision. This will commence by showing how the heat kernel can be used for the anisotropic smoothing of complex non-Euclidean image data, including tensor MRI. We will then show how a similar diffusion process based on the Fokker-Planck equation can be used for consistent image labelling. Thirdly, we will show how permutation invariant characteristics extracted from the heat-kernel can be used for learning shape classes. If time permits, the talk will conclude by showing how quantum walks on graphs can overcome some of the problems which limit the utility of classical random walks.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons