A new dissimilarity measure for comparing labeled graphs

We use spectral graph theory to compare graphs that share the same node set, taking into account global graph structures. We propose a general framework using eigendecomposition of graph Laplacians. We show its special cases and propose a new dissimilarity measure that avoid problems of spectral analysis. The new dissimilarity emphasizes the importance of small eigenvalues which are known to carry the main information on graphs. General properties of the dissimilarity are discussed. The dissimilarity provides an efficient and intuitive tool for graph analysis.