×

A new dissimilarity measure for comparing labeled graphs. (English) Zbl 1258.05076

Summary: 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 avoids 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banerjee, A.; Merugu, S.; Dhillon, I. S.; Ghosh, J., Clustering with Bregman divergences, J. Mach. Learn. Res., 6, 1705-1749 (2005) · Zbl 1190.62117
[2] Bunke, H.; Shearer, K., A graph distance metric based on the maximal common subgraph, Pattern Recognit. Lett., 19, 3-4, 255-259 (1998) · Zbl 0905.68128
[3] Chung, F. R.K., Spectral Graph Theory (1997), American Mathematical Society · Zbl 0867.05046
[4] Eshera, M. A.; Fu, K. S., A graph distance measure for image analysis, IEEE Trans. Syst. Man Cybern., 14, 398-407 (1984) · Zbl 0555.68058
[5] Fernández, M.-L.; Valiente, G., A graph distance metric combining maximum common subgraph and minimum common supergraph, Pattern Recognit. Lett., 22, 6-7, 753-758 (2001) · Zbl 1010.68889
[6] Heymans, M.; Singh, A. K., Deriving phylogenetic tree from the similarity analysis of metabolic pathways, Bioinformatics, 26, 17, 138-146 (2003)
[7] Hu, H.; Yan, X.; Huang, Y.; Han, J.; Zhou, X. J., Mining coherent dense subgraphs across massive biological networks for functional discovery, Bioinformatics, 21, 1, 213-221 (2005)
[8] Levenshtein, V. I., Binary codes capable of correcting deletions, insertions, and reversals, Sov. Phys. Dokl., 10, 707-710 (1966) · Zbl 0149.15905
[9] Luo, B.; Wilson, R. C.; Hancock, E. R., Spectral embedding of graphs, Pattern Recognit., 36, 2213-2230 (2003) · Zbl 1054.68105
[10] Sanfeliu, A.; Fu, K. S., A distance measure between attributed relational graphs for pattern recognition, IEEE Trans. Syst. Man Cybern., 13, 353-362 (1983) · Zbl 0511.68060
[11] Trinajstic, N.; Knop, J. V.; Muller, W. R.; Syzmanski, K.; Nikolic, S., Computational Chemical Graph Theory: Characterization, Enumeration and Generation of Chemical Structures by Computer Methods (1991), Prentice Hall · Zbl 0746.05064
[12] Vishwanathan, S. V.B.; Schraudolph, N. N.; Kondor, R.; Borgwardt, K. M., Graph kernels, J. Mach. Learn. Res., 11, 1201-1242 (2010) · Zbl 1242.05112
[13] Zeng, Z.; Tung, A. K.H.; Wang, J.; Feng, J.; Zhou, L., Comparing stars: on approximating graph edit distance, Proc. VLDB Endowment, 2, 1, 25-36 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.