Graph edit distance explained

In mathematics and computer science, graph edit distance (GED) is a measure of similarity (or dissimilarity) between two graphs.The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983.[1] A major application of graph edit distance is in inexact graph matching, suchas error-tolerant pattern recognition in machine learning.[2]

The graph edit distance between two graphs is related to thestring edit distance between strings.With the interpretation of strings as connected, directed acyclic graphs of maximum degree one, classical definitionsof edit distance such as Levenshtein distance,[3] [4] Hamming distance[5] and Jaro–Winkler distance may be interpreted as graph edit distancesbetween suitably constrained graphs. Likewise, graph edit distance isalso a generalization of tree edit distance betweenrooted trees.[6] [7] [8] [9]

Formal definitions and properties

The mathematical definition of graph edit distance is dependent upon the definitions ofthe graphs over which it is defined, i.e. whether and how the vertices and edges of thegraph are labeled and whether the edges are directed.Generally, given a set of graph edit operations (also known as elementary graph operations), the graph edit distance between two graphs

g1

and

g2

, written as

GED(g1,g2)

can be defined as

GED(g1,g2)=

min
(e1,...,ek)\inl{P

(g1,g2)}

k
\sum
i=1

c(ei)

where

l{P}(g1,g2)

denotes the set of edit paths transforming

g1

into (a graph isomorphic to)

g2

and

c(e)\ge0

is the cost of each graph edit operation

e

.

The set of elementary graph edit operators typically includes:

vertex insertion to introduce a single new labeled vertex to a graph.

vertex deletion to remove a single (often disconnected) vertex from a graph.

vertex substitution to change the label (or color) of a given vertex.

edge insertion to introduce a new colored edge between a pair of vertices.

edge deletion to remove a single edge between a pair of vertices.

edge substitution to change the label (or color) of a given edge.

Additional, but less common operators, include operations such as edge splitting that introduces a new vertex into an edge (also creating a new edge), and edge contraction that eliminates vertices of degree two between edges (of the same color). Although such complex edit operators can be defined in terms of more elementary transformations, their use allows finer parameterization of the cost function

c

when the operator is cheaper than the sum of its constituents.

A deep analysis of the elementary graph edit operators is presented in [10] [11] [12]

And some methods have been presented to automatically deduce these elementary graph edit operators.[13] [14] [15] [16] [17] And some algorithms learn these costs online:[18]

Applications

Graph edit distance finds applications in handwriting recognition, fingerprint recognition and cheminformatics.[19]

Algorithms and complexity

Exact algorithms for computing the graph edit distance between a pair of graphs typically transform the problem into one of finding the minimum cost edit path between the two graphs.The computation of the optimal edit path is cast as a pathfinding search or shortest path problem, often implemented as an A* search algorithm.

In addition to exact algorithms, a number of efficient approximation algorithms are also known. Most of them have cubic computational time [20] [21] [22] [23] [24]

Moreover, there is an algorithm that deduces an approximation of the GED in linear time [25]

Despite the above algorithms sometimes working well in practice, in general the problem of computing graph edit distance is NP-hard (for a proof that's available online, see Section 2 of Zeng et al.), and is even hard to approximate (formally, it is APX-hard[26]).

Notes and References

  1. Alberto. Sanfeliu. King-Sun. Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics. 13. 3. 353–363. 1983. 10.1109/TSMC.1983.6313167. 1087693.
  2. Xinbo. Gao. Bing. Xiao. Dacheng. Tao. Xuelong. Li. A survey of graph edit distance. Pattern Analysis and Applications. 2010. 13. 113 - 129. 10.1007/s10044-008-0141-y.
  3. Влади́мир И. Левенштейн. ru:Двоичные коды с исправлением выпадений, вставок и замещений символов. ru. Binary codes capable of correcting deletions, insertions, and reversals. Доклады Академий Наук СССР. 163. 4. 845–848. 1965.
  4. Levenshtein. Vladimir I.. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady. 10. 8. 707–710. February 1966.
  5. Hamming . Richard W. . Richard W. Hamming . 0035935 . 2 . . 147–160 . Error detecting and error correcting codes . 29 . 1950 . 10.1002/j.1538-7305.1950.tb00463.x . bot: unknown . https://web.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf . 2006-05-25 . 10945/46756 . 61141773 .
  6. Shasha. D. Zhang. K. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput.. 18. 6. 1245–1262. 1989. 10.1137/0218082. 10.1.1.460.5601. 10970317.
  7. Zhang. K. A constrained edit distance between unordered labeled trees. Algorithmica. 15. 3. 205–222. 1996. 10.1007/BF01975866. 20043881.
  8. Bille. P. A survey on tree edit distance and related problems. Theor. Comput. Sci.. 337. 1–3. 22–34. 2005. 10.1016/j.tcs.2004.12.030. free. 10.1.1.100.2577.
  9. Demaine. Erik D.. Erik Demaine. Mozes. Shay. Rossman. Benjamin. Weimann. Oren. 1. ACM Transactions on Algorithms. 2654906. A2. An optimal decomposition algorithm for tree edit distance. 6. 2010. 10.1145/1644015.1644017. cs/0604037 . 10.1.1.163.6937. 7878119.
  10. Book: Serratosa , Francesc . Redefining the Graph Edit Distance. S. N. Computer Science, pp: 2-438. 2021 .
  11. Book: Serratosa , Francesc . Graph edit distance: Restrictions to be a metric. Pattern Recognition, 90, pp: 250-256. 2019 .
  12. Book: Serratosa. Francesc. Cortés. Xavier. Graph Edit Distance: moving from global to local structure to solve the graph-matching problem. Pattern Recognition Letters, 65, pp: 204-210. 2015 .
  13. Book: Santacruz. Pep. Serratosa. Francesc. Learning the graph edit costs based on a learning model applied to sub-optimal graph matching. Neural Processing Letters, 51, pp: 881–904. 2020 .
  14. Book: Algabli. Shaima. Serratosa. Francesc. Embedding the node-to-node mappings to learn the Graph edit distance parameters. Pattern Recognition Letters, 112, pp: 353-360. 2018 .
  15. Book: Xavier. Cortés. Serratosa. Francesc. Learning Graph Matching Substitution Weights based on the Ground Truth Node Correspondence. International Journal of Pattern Recognition and Artificial Intelligence, 30(2), pp: 1650005 [22 pages]. 2016 .
  16. Book: Xavier. Cortés. Serratosa. Francesc. Learning Graph-Matching Edit-Costs based on the Optimality of the Oracle's Node Correspondences. Pattern Recognition Letters, 56, pp: 22 - 29. 2015 .
  17. Book: Conte. Donatello. Serratosa. Francesc. Interactive Online Learning for Graph Matching using Active Strategies. Knowledge Based Systems, 105, pp: 106275. 2020 .
  18. Book: Rica. Elena. Álvarez. Susana. Serratosa. Francesc. On-line learning the graph edit distance costs. Pattern Recognition Letters, 146, pp: 52-62. 2021 .
  19. Birchall. Kristian. Gillet. Valerie J.. Harper. Gavin. Pickett. Stephen D.. Training Similarity Measures for Specific Activities: Application to Reduced Graphs. Journal of Chemical Information and Modeling. 46. 2. 557–586. Jan 2006. 10.1021/ci050465e. 16562986.
  20. Book: Neuhaus. Michel. Bunke. Horst. Bridging the Gap between Graph Edit Distance and Kernel Machines. Machine Perception and Artificial Intelligence. 68. World Scientific. 978-9812708175. Nov 2007.
  21. Book: Riesen , Kaspar . Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. Advances in Computer Vision and Pattern Recognition. Springer. 978-3319272511. Feb 2016 .
  22. Book: Serratosa , Francesc . Fast Computation of Bipartite Graph Matching. Pattern Recognition Letters, 45, pp: 244 - 250. 2014 .
  23. Book: Serratosa , Francesc . Speeding up Fast Bipartite Graph Matching through a new cost matrix. International Journal of Pattern Recognition and Artificial Intelligence, 29 (2), 1550010, [17 pages]. 2015 .
  24. Book: Serratosa , Francesc . Computation of Graph Edit Distance: Reasoning about Optimality and Speed-up. Image and Vision Computing, 40, pp: 38-48. 2015 .
  25. Book: Santacruz. Pep. Serratosa. Francesc. Error-tolerant graph matching in linear computational cost using an initial small partial matching. Pattern Recognition Letters. 2018 .
  26. Book: Lin, Chih-Long. 1994-08-25. Springer Berlin Heidelberg. 9783540583257. Du. Ding-Zhu. Lecture Notes in Computer Science. 74–82. en. 10.1007/3-540-58325-4_168. Zhang. Xiang-Sun. Algorithms and Computation. 834. Hardness of approximating graph transformation problem.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Graph edit distance".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.