Graph Edit Distance Function

A Graph Edit Distance Function is a Graph Distance Function for two Graphs that Counts the number of Graph Edit Operation?s.

• AKA: Graph Edit Distance, Graph Edit Distance Measure, GED.
• Context:
  • It is a type of Edit Distance Function.
  • It can be used by a Graph Edit Matching Algorithm. … Graph Matching Task.
• See: String Edit Distance Measure.

---

---

References

2006

• (Justice & Hero, 2006) ⇒ Derek Justice, and Alfred Hero. (2006). “A Binary Linear Programming Formulation of the Graph Edit Distance.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(8). doi:10.1109/TPAMI.2006.152
  • A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric . …

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

1997

• (Bunke, 1997) ⇒ Horst Bunke. (1997). “On a Relation Between Graph Edit Distance and Maximum Common Subgraph.” In: Pattern Recognition Letters, 18(9).

1983

• (Bunke & Allerman, 1983) ⇒ Horst Bunke, and G. Allerman. (1983). “Inexact Graph Matching for Structural Pattern Recognition.” In: Pattern Recognition Letters

---