Abstract
In this paper, Umeyama’s eigen-decomposition approach to weighted graph matching problems is critically examined. We argue that Umeyama’s approach only guarantees to work well for graphs that satisfy three critical conditions: (1) The pair of weighted graphs to be matched must be nearly isomorphic; (2) The eigenvalues of the adjacency matrix of each graph have to be single and isolated enough to each other; (3) The rows of the matrix of the corresponding absolute eigenvetors cannot be very similar to each other. For the purpose of matching general weighted graph pairs without such imposed constraints, we shall propose an approximate formula with a theoretical guarantee of accuracy, from which Umeyama’s formula can be deduced as a special case. Based on this approximate formula, a new algorithm for matching weighted graphs is developed. The experimental results demonstrate great improvements to the accuracy of weighted graph matching.
This research is supported in part by National Nature Science Foundation of China.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Almohamad, H.A.: A Polynomial Transformfor Matching Pairs of Weighted Graphs. Applied Mathematical Modelling 15, 216–222 (1991)
Almohamad, H.A., Duffuaa, S.O.: A Linear Programming Approach for the Weighted Graph Matching Problem. IEEE Trans. PAMI 15, 522–525 (1993)
Wyk, B.J.V.: Kronecker Product Successive Projection and Related Graph Matching Algorithms. Ph.D. diss., University of the Witwatersrand, Johannesburg (2002)
Davis, C., Kahan, W.M.: The Rotation of Eigenvectors by a Perturbation. III, SIAM J. Numer. Anal 7, 1–46 (1970)
Finch, A.M., Wilson, R.C., Hancock, E.R.: Matching Delaunay Triangulations by Probabilistic Relaxation. In: Proc. of Computer Analysis of Images and Patterns, pp. 350–358 (1995)
Gold, S., Rangarajan, A.: A Graduated Assignment Algorithm for Graph Matching. IEEE Trans. PAMI 18, 377–388 (1996)
Harold, W.K.: The Hungarian Method for the Assignment Problem. Naval Research Logistic Quarterly 2, 83–97 (1955)
Hummel, R., Zuker, S.: On the Foundations of Relaxation Labeling Processes. IEEE Trans. PAMI 5, 267–287 (1983)
Krcmar, M., Dhawan, A.P.: Application of Genetic Algorithms in Graph Matching. Proc. of the International Conference on Neural Networks 6, 3872–3876 (1994)
Ninoslav, T.: Relative Perturbation Theory for Matrix Spectral Decompositions. Ph.D. diss., Dept. of Mathematics, Univ. of Zagreb (2000)
Sanfeliu, A., Fu, K.S.: A Distance Measure between Attributed Relational Graphs for Pattern Recognition. IEEE Trans. SMC 13, 53–363 (1983)
Stewart, G.W., Sun, J.: Matrix Perturbation Theory. Academic Press, San Diego (1990)
Suganthan, P., Teoh, E., Mital, D.: Pattern Recognition by Graph Matching Using the Potts MFT Neural Networks. Pattern Recognition 28, 997–1009 (1995)
Tasi, W.H., Fu, K.S.: Error-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Recognition. IEEE Trans. SMC 9, 757–768 (1979)
Ullman, J.R.: An Algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery 23, 31–42 (1976)
Umeyama, S.: An Eigendecomposition Approach to Weighted Graph Matching Problems. IEEE Trans. PAMI 10, 695–703 (1988)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Zhao, G., Luo, B., Tang, J., Ma, J. (2007). Using Eigen-Decomposition Method for Weighted Graph Matching. In: Huang, DS., Heutte, L., Loog, M. (eds) Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues. ICIC 2007. Lecture Notes in Computer Science, vol 4681. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74171-8_131
Download citation
DOI: https://doi.org/10.1007/978-3-540-74171-8_131
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74170-1
Online ISBN: 978-3-540-74171-8
eBook Packages: Computer ScienceComputer Science (R0)