{{Short description|Measure of similarity between two graphs}} thumb|upright=1.25|At first glance, the '''GED''' (graph edit distance) may appear to be 7, removing 3 edges, adding the yellow vertex, and adding edges between it and the 3 other vertices. However, the optimal set of operations would be to remove the edge between 2 colors of choice (for example, green and blue), change the third (red) to yellow, add a vertex of the now missing color (red), and connect it to the newly yellow vertex, for a GED of 4.

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.<ref>{{cite journal |first1=Alberto |last1=Sanfeliu |first2=King-Sun |last2=Fu |title=A distance measure between attributed relational graphs for pattern recognition |journal=IEEE Transactions on Systems, Man, and Cybernetics |volume=13 |issue=3 |pages=353–363 |year=1983 |doi=10.1109/TSMC.1983.6313167|s2cid=1087693 }}</ref> A major application of graph edit distance is in inexact graph matching, such as error-tolerant pattern recognition in machine learning.<ref> {{cite journal |first1=Xinbo |last1=Gao |first2=Bing |last2=Xiao |first3=Dacheng |last3=Tao |first4=Xuelong |last4=Li |title=A survey of graph edit distance |journal=Pattern Analysis and Applications |year=2010 |volume=13 |pages=113&ndash;129 |doi=10.1007/s10044-008-0141-y }}</ref>

The graph edit distance between two graphs is related to the string edit distance between strings. With the interpretation of strings as connected, directed acyclic graphs of maximum degree one, classical definitions of edit distance such as Levenshtein distance,<ref>{{cite journal |author=Влади́мир И. Левенштейн |script-title=ru:Двоичные коды с исправлением выпадений, вставок и замещений символов |language=ru |trans-title=Binary codes capable of correcting deletions, insertions, and reversals |journal=Доклады Академий Наук СССР |volume=163 |issue=4 |pages=845–848 |year=1965}}</ref><ref>{{cite journal |last1=Levenshtein |first1=Vladimir I. |title=Binary codes capable of correcting deletions, insertions, and reversals |journal=Soviet Physics Doklady |volume=10 |number=8 |pages=707–710 |date=February 1966|bibcode=1966SPhD...10..707L }}</ref> Hamming distance<ref>{{cite journal |last=Hamming |first=Richard W. |author-link=Richard W. Hamming |mr=0035935 |issue=2 |journal=Bell System Technical Journal |pages=147–160 |title=Error detecting and error correcting codes |url=http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf |volume=29 |year=1950 |doi=10.1002/j.1538-7305.1950.tb00463.x |url-status=bot: unknown |archive-url=https://web.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf |archive-date=2006-05-25 |hdl=10945/46756 |s2cid=61141773 }}</ref> and Jaro–Winkler distance may be interpreted as graph edit distances between suitably constrained graphs. Likewise, graph edit distance is also a generalization of '''tree edit distance''' between rooted trees.<ref>{{cite journal |last1=Shasha |first1=D |last2=Zhang |first2=K |title=Simple fast algorithms for the editing distance between trees and related problems |journal=SIAM J. Comput. |volume=18 |number=6 |pages=1245–1262 |year=1989 |doi=10.1137/0218082 |citeseerx=10.1.1.460.5601 |s2cid=10970317 }}</ref><ref>{{cite journal |last1=Zhang |first1=K |title=A constrained edit distance between unordered labeled trees |journal=Algorithmica |volume=15 |number=3 |pages=205–222 |year=1996 |doi=10.1007/BF01975866 |s2cid=20043881 }}</ref><ref>{{cite journal |last1=Bille |first1=P |title=A survey on tree edit distance and related problems |journal=Theor. Comput. Sci. |volume=337 |issue=1–3 |pages=22–34 |year=2005 |doi=10.1016/j.tcs.2004.12.030 |doi-access=free |citeseerx=10.1.1.100.2577 }}</ref><ref>{{cite journal |last1=Demaine |first1=Erik D. |author1-link=Erik Demaine |last2=Mozes |first2=Shay |last3=Rossman |first3=Benjamin |last4=Weimann|first4=Oren |issue = 1 |journal = ACM Transactions on Algorithms |mr = 2654906 |page = A2 |title = An optimal decomposition algorithm for tree edit distance |volume = 6 |year = 2010 |doi = 10.1145/1644015.1644017 |arxiv=cs/0604037 |citeseerx=10.1.1.163.6937 |s2cid=7878119 }}</ref><ref name="xted2024">{{cite journal | author1 = Fan, Dayi | author2 = Lee, Rubao | author3 = Zhang, Xiaodong | title = X-TED: Massive Parallelization of Tree Edit Distance | journal = Proceedings of the VLDB Endowment | volume = 17 | issue = 7 | pages = 1683&ndash;1696 | year = 2024 | doi = 10.14778/3654621.3654634 | url = https://www.vldb.org/pvldb/vol17/p1683-fan.pdf }}</ref>

==Formal definitions and properties== The mathematical definition of graph edit distance is dependent upon the definitions of the graphs over which it is defined, i.e. whether and how the vertices and edges of the graph 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 <math>g_{1}</math> and <math>g_{2}</math>, written as <math>GED(g_{1},g_{2})</math> can be defined as :<math> GED(g_{1},g_{2}) = \min_{(e_{1},...,e_{k}) \in \mathcal{P}(g_{1},g_{2})} \sum_{i=1}^{k} c(e_{i})</math> where <math>\mathcal{P}(g_{1},g_{2})</math> denotes the set of edit paths transforming <math>g_{1}</math> into (a graph isomorphic to) <math>g_{2}</math> and <math>c(e) \ge 0</math> is the cost of each graph edit operation <math>e</math>.

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 <math>c</math> when the operator is cheaper than the sum of its constituents.

A deep analysis of the elementary graph edit operators is presented in <ref>{{cite book |last=Serratosa |first=Francesc |title=Redefining the Graph Edit Distance |series=S. N. Computer Science, pp: 2-438 |date=2021 }}</ref><ref>{{cite book |last=Serratosa |first=Francesc |title=Graph edit distance: Restrictions to be a metric |series=Pattern Recognition, 90, pp: 250-256 |date=2019 }}</ref><ref>{{cite book |last1=Serratosa |first1=Francesc |last2=Cortés |first2=Xavier |title=Graph Edit Distance: moving from global to local structure to solve the graph-matching problem |series=Pattern Recognition Letters, 65, pp: 204-210 |date=2015 }}</ref>

And some methods have been presented to automatically deduce these elementary graph edit operators.<ref>{{cite book |last1=Santacruz |first1=Pep |last2=Serratosa |first2=Francesc |title=Learning the graph edit costs based on a learning model applied to sub-optimal graph matching |series=Neural Processing Letters, 51, pp: 881–904 |date=2020 }}</ref><ref>{{cite book |last1=Algabli |first1=Shaima |last2=Serratosa |first2=Francesc |title=Embedding the node-to-node mappings to learn the Graph edit distance parameters |series=Pattern Recognition Letters, 112, pp: 353-360 |date=2018 }}</ref><ref>{{cite book |last1=Xavier |first1=Cortés |last2=Serratosa |first2=Francesc |title=Learning Graph Matching Substitution Weights based on the Ground Truth Node Correspondence |series=International Journal of Pattern Recognition and Artificial Intelligence, 30(2), pp: 1650005 [22 pages] |date=2016 }}</ref><ref>{{cite book |last1=Xavier |first1=Cortés |last2=Serratosa |first2=Francesc |title=Learning Graph-Matching Edit-Costs based on the Optimality of the Oracle's Node Correspondences |series=Pattern Recognition Letters, 56, pp: 22 - 29 |date=2015 }}</ref><ref>{{cite book |last1=Conte |first1=Donatello |last2=Serratosa |first2=Francesc |title=Interactive Online Learning for Graph Matching using Active Strategies |series=Knowledge Based Systems, 105, pp: 106275 |date=2020 }}</ref> And some algorithms learn these costs online:<ref>{{cite book |last1=Rica |first1=Elena |last2=Álvarez |first2=Susana |last3=Serratosa |first3=Francesc |title=On-line learning the graph edit distance costs |series=Pattern Recognition Letters, 146, pp: 52-62 |date=2021 }}</ref>

==Applications== Graph edit distance finds applications in handwriting recognition,<ref>{{citation |last1=Fischer |first1=Andreas |last2=Suen |first2=Ching Y. |last3=Frinken |first3=Volkmar |last4=Riesen |first4=Kaspar |last5=Bunke |first5=Horst |contribution=A Fast Matching Algorithm for Graph-Based Handwriting Recognition |title=Graph-Based Representations in Pattern Recognition |series=Lecture Notes in Computer Science |volume=7877 |pages=194–203 |year=2013 |doi=10.1007/978-3-642-38221-5_21 |isbn=978-3-642-38220-8 }}</ref> fingerprint recognition<ref>{{citation |last1=Neuhaus |first1=Michel |last2=Bunke |first2=Horst |contribution=A Graph Matching Based Approach to Fingerprint Classification using Directional Variance |title=Audio- and Video-Based Biometric Person Authentication |series=Lecture Notes in Computer Science |volume=3546 |pages=191–200 |year=2005 |doi=10.1007/11527923_20 |isbn=978-3-540-27887-0 }}</ref> and cheminformatics.<ref>{{cite journal |last1=Birchall |first1=Kristian |last2=Gillet |first2=Valerie J. |last3=Harper |first3=Gavin |last4=Pickett |first4=Stephen D. |title=Training Similarity Measures for Specific Activities: Application to Reduced Graphs |journal=Journal of Chemical Information and Modeling |volume=46 |number=2 |pages=557–586 |date=Jan 2006 |doi=10.1021/ci050465e |pmid=16562986 }}</ref>

==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 <ref>{{cite book |last1=Neuhaus |first1=Michel |last2=Bunke |first2=Horst |title=Bridging the Gap between Graph Edit Distance and Kernel Machines |series=Machine Perception and Artificial Intelligence |volume=68 |publisher=World Scientific |isbn=978-9812708175 |date=Nov 2007 }}</ref><ref>{{cite book |last=Riesen |first=Kaspar |title=Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications |series=Advances in Computer Vision and Pattern Recognition |publisher=Springer |isbn=978-3319272511 |date=Feb 2016 }}</ref> <ref>{{cite book |last=Serratosa |first=Francesc |title=Fast Computation of Bipartite Graph Matching |series=Pattern Recognition Letters, 45, pp: 244 - 250 |date=2014 }}</ref> <ref>{{cite book |last=Serratosa |first=Francesc |title=Speeding up Fast Bipartite Graph Matching through a new cost matrix |series=International Journal of Pattern Recognition and Artificial Intelligence, 29 (2), 1550010, [17 pages] |date=2015 }}</ref> ;<ref>{{cite book |last=Serratosa |first=Francesc |title=Computation of Graph Edit Distance: Reasoning about Optimality and Speed-up |series=Image and Vision Computing, 40, pp: 38-48 |date=2015 }}</ref> however, the runtime of at least one algorithm is linear in the number of nodes while still being cubic in the node degree.<ref>{{cite book |last1=Santacruz |first1=Pep |last2=Serratosa |first2=Francesc |title=Error-tolerant graph matching in linear computational cost using an initial small partial matching |series=Pattern Recognition Letters |date=2018 }}</ref>

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 [https://web.archive.org/web/20170810170852/http://www.vldb.org/pvldb/2/vldb09-568.pdf Zeng et al.]), and is even hard to approximate (formally, it is APX-hard<ref>{{Cite book|last=Lin|first=Chih-Long|date=1994-08-25|publisher=Springer Berlin Heidelberg|isbn=9783540583257|editor-last=Du|editor-first=Ding-Zhu|series=Lecture Notes in Computer Science|pages=74–82|language=en|doi=10.1007/3-540-58325-4_168|editor-last2=Zhang|editor-first2=Xiang-Sun|title = Algorithms and Computation|volume = 834|chapter=Hardness of approximating graph transformation problem}}</ref>).

==Tree Edit Distance==

Tree Edit Distance (TED) represents the minimum cost of transforming one tree into another using three operations: insertion, deletion, and replacement. The first polynomial-time TED algorithm was proposed by Tai in 1979<ref name="tai1979">{{cite journal | author1 = Tai, Kuo-Chung | title = The Tree-to-Tree Correction Problem | journal = Journal of the ACM | volume = 26 | issue = 3 | pages = 422&ndash;433 | year = 1979 | doi = 10.1145/322139.322143 }}</ref>. In 1989, Kaizhong Zhang and Dennis Shasha proposed the most well-known TED algorithm<ref name="zhang1989">{{cite journal | author1 = Zhang, Kaizhong | author2 = Shasha, Dennis | title = Simple Fast Algorithms for the Editing Distance between Trees and Related Problems | journal = SIAM Journal on Computing | volume = 18 | issue = 6 | pages = 1245&ndash;1262 | year = 1989 | doi = 10.1137/0218082 }}</ref>, which introduced Dynamic Programming (DP) techniques to solve TED and has a worst-case time complexity of O(n<sup>4</sup>). This method employs a series of DP tables, where each table computes the edit distance between a subpart of the first input tree and a subpart of the second input tree. Since then, substantial research efforts<ref name="klein1998">{{cite journal | author1 = Klein, Philip N. | title = Computing the Edit-Distance between Unrooted Ordered Trees | journal = Proceedings of the 6th Annual European Symposium on Algorithms (ESA '98) | year = 1998 | publisher = Springer-Verlag | location = Berlin, Heidelberg | pages = 91&ndash;102 }}</ref><ref name="demaine2010">{{cite journal | author1 = Demaine, Erik D. | author2 = Mozes, Shay | author3 = Rossman, Benjamin | author4 = Weimann, Oren | title = An Optimal Decomposition Algorithm for Tree Edit Distance | journal = ACM Transactions on Algorithms | volume = 6 | issue = 1 | pages = Article 2 | year = 2010 | doi = 10.1145/1644015.1644017 }}</ref><ref name="pawlik2011">{{cite journal | author1 = Pawlik, Mateusz | author2 = Augsten, Nikolaus | title = RTED: A Robust Algorithm for the Tree Edit Distance | journal = Proceedings of the VLDB Endowment | volume = 5 | issue = 4 | pages = 334&ndash;345 | year = 2011 | doi = 10.14778/2095686.2095692 }}</ref> have focused on improving its sequential time complexity, and it has been proven that O(n<sup>3</sup>) is the lowest theoretical bound<ref name="bringmann2020">{{cite journal | author1 = Bringmann, Karl | author2 = Gawrychowski, Paweł | author3 = Mozes, Shay | author4 = Weimann, Oren | title = Tree Edit Distance Cannot Be Computed in Strongly Subcubic Time (Unless APSP Can) | journal = ACM Transactions on Algorithms | volume = 16 | issue = 4 | pages = Article 48 | year = 2020 | doi = 10.1145/3381878 }}</ref>.

==== Parallelization ====

Despite these sequential improvements, TED remains computationally expensive for large trees, and its parallelization is highly non-trivial<ref name="shukla2015">{{cite conference | author1 = Shukla, Parijat | author2 = Somani, Arun K. | title = Tree Matching Using Data Shaping | conference = 2015 IEEE International Congress on Big Data | year = 2015 | publisher = IEEE | pages = 166&ndash;173 | doi = 10.1109/BigDataCongress.2015.32 }}</ref>. Specifically, TED computation involves both intra-table and inter-table data dependencies: entries within a DP table depend on previously computed entries, while the computation of each DP table depends on results from other tables<ref name="xted2024"></ref>. These intricate dependencies hinder parallel execution. Moreover, the severe workload imbalance across DP tables further complicates scheduling and reduces parallel resource utilization.

[https://github.com/Davis-Fan/X-TED X-TED]<ref name="xted2024"></ref> is a massively parallel framework for TED computation that addresses these structural challenges. It employs a new preprocessing algorithm to efficiently determine dependency relationships among DP tables by analyzing only the tree structures. Based on this dependency information, X-TED groups independent DP tables into batches and processes them in parallel. To handle tables of different sizes, X-TED further adopts a dynamic parallelization strategy that allocates different levels of parallel resources according to each table’s size. Extensive experiments on multicore CPUs and GPUs using real-world and synthetic trees demonstrate the effectiveness of X-TED for large-scale TED computation<ref name="xted2024"></ref>.

==References== {{Reflist}}

== External links ==

* [https://github.com/Davis-Fan/X-TED X-TED]

Category:Graph theory Category:Graph algorithms Category:Computational problems in graph theory Category:Distance