BibTeX entry

@PHDTHESIS{200705Xiao_Bai,
  AUTHOR={Xiao Bai},
  TITLE={Heat Kernel Analysis on Graphs},
  SCHOOL={University of York},
  MONTH=May,
  YEAR=2007,
  URL={http://www.bmva.org/theses/2007/2007-bai.pdf},
}

Abstract

In this thesis we aim to develop a framework for graph characterization by combining the methods from spectral graph theory and manifold learning theory. The algorithms are applied to graph clustering, graph matching and object recognition. Spectral graph theory has been widely applied in areas such as image recognition, image segmentation, motion tracking, image matching and etc. The heat kernel is an important component of spectral graph theory since it can be viewed as describing the flow of information across the edges of the graph with time. Our first contribution is to investigate how to extract useful and stable invariants from the graph heat kernel as a means of clustering graphs. The best set of invariants are the heat kernel trace, the zeta function and its derivative at the origin. We also study heat content invariants. The polynomial co-efficients can be computed from the Laplacian eigensystem. Graph clustering is performed by applying principal components analysis to vectors constructed from the invariants or simply based on the unitary features extracted from the graph heat kernel. We experiment with the algorithms on the COIL and Oxford-Caltech databases. We further investigate the heat kernel as a means of graph embedding. The second contribution of the thesis is the introduction of two graph embedding methods. The first of these uses the Euclidean distance between graph nodes. To do this we equate the spectral and parametric forms of the heat kernel to compute an approximate Euclidean distance between nodes. We use the resulting pattern of distances to embed the nodes of the graph on a manifold using a procedure similar to ISOMAP. The distribution of embedded points can be used to characterize the graphs, and can be used for the purpose of graph clustering as well. Experiments demonstrate that the algorithms can offer a useful margin of advantages over existing alternatives. The second graph embedding method uses the Young-Householder decomposition of the heat kernel to map the nodes of the graphs into a vector space. This is similar to performing kernel PCA on the heat kernel. The co-ordinates of the nodes are determined by the eigenvalues and eigenvectors of the Laplacian matrix, together with a time parameter which can be used to scale the mapping. Node correspondences are located by applying a spectral alignment algorithm to the embedded nodes. Here the third contribution of the thesis is to use the heat kernel graph embedding to transform the graph matching problem into one of point-set alignment problem. The fourth contribution of the thesis is to use the correspondence matches to construct a generative model which can be used to capture variations in graph structure using the covariance matrix for corresponding embedded point positions. This is done by using the eigenvalues and eigenvectors of the covariance matrix for the embedded node positions of sample of graphs. We show how to use this model to both project individual graph into the eigenspace of the point position covariance matrix and how to fit the model to potentially noisy graphs to reconstruct the Laplacian matrix. We illustrate the utility of the resulting method for shape analysis using data from the COIL and Caltech-Oxford databases.