A thermodynamics approach to graph similarity

In this paper, we describe the use of concepts from the areas of spectral-graph theory, kernel methods and differential geometry for the purposes of recovering a measure of similarity between pairs of graphical structures. To do this, we commence by relating each of the graphs under study to a Riemannian manifold through the use of the graph Laplacian and the heat operator. We do this by making use of the heat kernel and the set of initial conditions for the space of functions associated to the Laplace-Beltrami operator. With these ingredients, we make use of the first law of thermodynamics to recover the thermal energy associated to the conduction of heat through the graph. Thus, the problem of recovering a measure of similarity between pairs of graphs becomes that of computing the difference in their thermal energies. We illustrate the utility of the similarity metric recovered in this way for purposes of content-based image database indexing and retrieval. © 2005 IEEE.