Graphs Similarity Measure

Jump to: navigation, search

A Graphs Similarity Measure is a similarity measure for two graphs.




  • (Luo & Hancock, 2001) ⇒ Bin Luo and Edwin R. Hancock. (2001). “Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(10).
    • Graph matching is a task of pivotal importance in high-level vision since it provides a means by which abstract pictorial descriptions can be matched to one another. Unfortunately, since the process of eliciting graph structures from raw image data is a task of some fragility due to noise and the limited effectiveness of the available segmentation algorithms, graph matching is invariably approached by inexact means (Shapiro & Haralick, 1985), (Sanfeliu & Fu, 1983).
    • We set our work in context with a brief review of the related literature. Some of the pioneering work on graph matching was undertaken in the early 1970's by (Barrow & Popplestone, 1971) and by (Fischler & Enschlager, 1973). These two studies provided proof of concept for the use of relational structures in high-level pictorial object recognition.



  • L.G. Shapiro and R.M. Haralick. (1985). “A Metric for Comparing Relational Descriptions.” In: IEEE Trans. Pattern Analysis and Machine Intelligence]], 7(1).


  • A. Sanfeliu and K. S. Fu. (1983). “A Distance Measure between Attributed Relational Graphs for Pattern Recognition.” In: IEEE Trans. Systems, Man, and Cybernetics, 13(3).
  • (Bunke, 1983) ⇒ Horst Bunke. (1983). “What is the Distance Between Graphs?" In: Bulletin of the EATCS, 20:35{39.


  • M. Fischler and R. Elschlager. (1973). “The Representation and Matching of Pictorical Structures.” In: IEEE Trans. Computers, 22(1).


  • H. G. Barrow and R. J. Popplestone. (1971). “Relational Descriptions in Picture Processing.” In: Machine Intelligence, 5.