More Web Proxy on the site http://driver.im/

research-article

Error Correcting Graph Matching: On the Influence of the Underlying Cost Function

Author:

H. BunkeAuthors Info & Claims

IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 21, Issue 9

Pages 917 - 922

https://doi.org/10.1109/34.790431

Published: 01 September 1999 Publication History

Abstract

This paper investigates the influence of the cost function on the optimal match between two graphs. It is shown that, for a given cost function, there are an infinite number of other cost functions that lead, for any given pair of graphs, to the same optimal error correcting matching. Furthermore, it is shown that well-known concepts from graph theory, such as graph isomorphism, subgraph isomorphism, and maximum common subgraph, are special cases of optimal error correcting graph matching under particular cost functions.

References

[1]

S.W. Lu Y. Ren and C.Y. Suen, “Hierarchical Attributed Graph Representation and Recognition of Handwritten Chinese Characters,” Pattern Recognition, vol. 24, pp. 617-632, 1991.

Digital Library

[2]

J. Rocha and T. Pavlidis, “A Shape Analysis Model with Applications to a Character Recognition System,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, pp. 393-404, 1994.

Digital Library

[3]

Y.-K. Wang K.-C. Fan and J.-T. Horng, “Genetic-Based Search for Error-Correcting Graph Isomorphism,” IEEE Trans. Systems, Man, and Cybernetics, vol. 27, pp. 588-597, May 1997.

Digital Library

[4]

S.W. Lee J.H. Kim and F.C.A. Groen, “Translation-, Rotation-, and Scale-Invariant Recognition of Hand-Drawn Symbols in Schematic Diagrams,” Int'l J. Pattern Recognition and Artificial Intelligence, vol. 4, no. 1, pp. 1-15, 1990.

[5]

A. Pearce T. Caelli and W.F. Bischof, “Rulegraphs for Graph Matching in Pattern Recognition,” Pattern Recognition, vol. 27, no. 9, pp. 1,231-1,246, 1994.

[6]

W.J. Christmas J. Kittler and M. Petrou, “Structural Matching in Computer Vision Using Probabilistic Relaxation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 749-764, 1995.

Digital Library

[7]

E.K. Wong, “Model Matching in Robot Vision by Subgraph Isomorphism,” Pattern Recognition, vol. 25, no. 3, pp. 287-304, 1992.

Digital Library

[8]

J.R. Ullman, “An Algorithm for Subgraph Isomorphism,” J. ACM, vol. 23, no. 1, pp. 31-42, 1976.

Digital Library

[9]

L.G. Shapiro and R.M. Haralick, “Structural Descriptions and Inexact Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 3, pp. 504-519, 1981.

Digital Library

[10]

B. Messmer and H. Bunke, “A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, pp. 493-505, 1998.

Digital Library

[11]

A. Sanfeliu and K.S. Fu, “A Distance Measure between Attributed Relational Graphs for Pattern Recognition,” IEEE Trans. Systems, Man, and Cybernetics, vol. 13, pp. 353-363, 1983.

[12]

R. Horaud and T. Skordas, “Stereo Correspondence through Feature Grouping and Maximal Cliques,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 11, pp. 1,168-1,180, Nov. 1989.

Digital Library

[13]

R.A. Wagner and M.J. Fischer, “The String-to-String Correction Problem,” J. ACM, vol. 21, no. 1, pp. 168-173, 1974.

Digital Library

[14]

L. Herault R. Horaud F. Veillon and J.J. Niez, “Symbolic Image Matching by Simulated Annealing,” Proc. British Machine Vision Conf., pp. 319-324, Oxford, U.K., 1990.

[15]

L. Xu and E. Oja, “Improved Simulated Annealing, Boltzmann Machine, and Attributed Graph Matching,” Lecture Notes in Computer Science 412, L. Almeida, ed., pp. 151-161, Springer Verlag, 1990.

Digital Library

[16]

H. Bunke, “On a Relation between Graph Edit Distance and Maximum Common Subgraph,” Pattern Recognition Letters, vol. 18, pp. 689-694, 1997.

Digital Library

[17]

S. Rice H. Bunke and T. Nartker, “Classes of Cost Functions for String Matching,” Algorithmica, vol. 18, no. 2, pp. 271-280, 1997.

Digital Library

Cited By

Zhao YQi JTrisedya BSu YZhang RRen H(2023)Learning Region Similarities via Graph-Based Deep Metric LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.325380235:10(10237-10250)Online publication date: 8-Mar-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3253802
Jia LGaüzère BYger FHoneine P(2021)A Metric Learning Approach to Graph Edit Costs for RegressionStructural, Syntactic, and Statistical Pattern Recognition10.1007/978-3-030-73973-7_23(238-247)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-73973-7_23
Ontañón S(2020)An overview of distance and similarity functions for structured dataArtificial Intelligence Review10.1007/s10462-020-09821-w53:7(5309-5351)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s10462-020-09821-w
Show More Cited By

Index Terms

Error Correcting Graph Matching: On the Influence of the Underlying Cost Function
1. Computing methodologies
  1. Machine learning
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Matching graphs with unique node labels

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that ...
Matching graphs with unique node labels

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that ...
Error-tolerant geometric graph similarity and matching
Highlights
- An intuitive approach to graph similarity and matching using geometric graphs.
- ...
Abstract
Geometric graph matching is the process of evaluating the similarity between geometric graphs, where each vertex has an associated coordinate point in a plane. Exact matching computes a strict correspondence between two geometric ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Pattern Analysis and Machine Intelligence

IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 21, Issue 9

September 1999

145 pages

ISSN:0162-8828

Editors:
Kevin Bowyer
Univ. of South Florida, Tampa
,
Patrick Flynn
Ohio State Univ., Columbus

Issue’s Table of Contents

Copyright © Copyright © 1999 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 September 1999

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao YQi JTrisedya BSu YZhang RRen H(2023)Learning Region Similarities via Graph-Based Deep Metric LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.325380235:10(10237-10250)Online publication date: 8-Mar-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3253802
Jia LGaüzère BYger FHoneine P(2021)A Metric Learning Approach to Graph Edit Costs for RegressionStructural, Syntactic, and Statistical Pattern Recognition10.1007/978-3-030-73973-7_23(238-247)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-73973-7_23
Ontañón S(2020)An overview of distance and similarity functions for structured dataArtificial Intelligence Review10.1007/s10462-020-09821-w53:7(5309-5351)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s10462-020-09821-w
Chen LLin GWang SWu Q(2020)Graph Edit Distance Reward: Learning to Edit Scene GraphComputer Vision – ECCV 202010.1007/978-3-030-58529-7_32(539-554)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-58529-7_32
Sejwal VAbulaish MAkerkar RJung J(2019)Context-Based Rating Prediction using Collaborative Filtering and Linked Open DataProceedings of the 9th International Conference on Web Intelligence, Mining and Semantics10.1145/3326467.3326489(1-9)Online publication date: 26-Jun-2019
https://dl.acm.org/doi/10.1145/3326467.3326489
Reischmann TKuchen HHung CPapadopoulos G(2019)A web-based e-assessment tool for design patterns in UML class diagramsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297520(2435-2444)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297520
Darwiche MConte DRaveaux RT’kindt V(2019)Solving the Graph Edit Distance Problem with Variable Partitioning Local SearchGraph-Based Representations in Pattern Recognition10.1007/978-3-030-20081-7_7(67-77)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-20081-7_7
Lin CLemarchand LEuler RSparkes I(2018)Modeling the Geometry and Dynamics of the Endoplasmic Reticulum NetworkIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2015.238922615:2(377-386)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1109/TCBB.2015.2389226
Dutta ALlads JBunke HPal U(2018)Product graph-based higher order contextual similarities for inexact subgraph matchingPattern Recognition10.1016/j.patcog.2017.12.00376:C(596-611)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1016/j.patcog.2017.12.003
Bougleux SBrun LCarletti VFoggia PGazre BVento M(2017)Graph edit distance as a quadratic assignment problemPattern Recognition Letters10.1016/j.patrec.2016.10.00187:C(38-46)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.patrec.2016.10.001
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents