# 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):****Counter-Example(s):****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.