Graph edit distance

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.A major application of graph edit distance is in inexact graph matching, suchas error-tolerant pattern recognition in machine learning. 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.A major application of graph edit distance is in inexact graph matching, suchas error-tolerant pattern recognition in machine learning. 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,Hamming distanceand 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. 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 g 1 {displaystyle g_{1}} and g 2 {displaystyle g_{2}} , written as G E D ( g 1 , g 2 ) {displaystyle GED(g_{1},g_{2})} can be defined as where P ( g 1 , g 2 ) {displaystyle {mathcal {P}}(g_{1},g_{2})} denotes the set of edit paths transforming g 1 {displaystyle g_{1}} into (a graph isomorphic to) g 2 {displaystyle g_{2}} and c ( e ) ≥ 0 {displaystyle c(e)geq 0} is the cost of each graph edit operation e {displaystyle e} .