Trace Formula Analysis of Graphs.

In this paper, we explore how the trace of the heat kernel can be used to characterise graphs for the purposes of measuring similarity and clustering. The heat-kernel is the solution of the heat-equation and may be computed by exponentiating the Laplacian eigensystem with time. To characterise the shape of the heat-kernel trace we use the zeta-function, which is found by exponentiating and summing the reciprocals of the Laplacian eigenvalues. From the Mellin transform, it follows that the zeta-function is the moment generating function of the heat-kernel trace. We explore the use of the heat-kernel moments as a means of characterising graph structure for the purposes of clustering. Experiments with the COIL and Oxford-Caltech databases reveal the effectiveness of the representation. [ABSTRACT FROM AUTHOR]