Graphs Similarity Measure

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

• AKA: Graph Distance.
• Context:
  • It can result in a Graph Similarity Value.
  • It can be used by a Graph Matching Algorithm.
  • …
• Example(s):
  • a Graph Edit Distance Function.
  • …
• Counter-Example(s):
  • a Graph Path Distance Function.
  • a Graph Node Distance Function.
  • a Graph Nodes Similarity Measure.
  • a Set Distance Function.
  • a String Distance Function.
• See: Edge Distance Function, Distance Function.

---

---

References

2008

• (De Raedt & Ramon, 2008) ⇒ Luc De Raedt, and Jan Ramon. (2008). “Deriving Distance Metrics from Generality Relations.” In: Pattern Recognition Letters 30(3).

2001

• (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.

1998

• (Bunke & Shearer, 1998) ⇒ Horst Bunke, and Kim Shearer. (1998). “A Graph Distance Metric Based on the Maximal Common Subgraph.” In: Pattern Recognition Letters, 19(3-4).

1985

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

1983

• 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.

1973

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

1971

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

---