Edit distance between two graphs

Question

I'm just wondering if, like for strings where we have the Levenshtein distance (or edit distance) between two strings, is there something similar for graphs?

I mean, a scalar measure that identifies the number of atomic operations (node and edges insertion/deletion) to transform a graph G1 to a graph G2.

score 22 · Answer 1 · answered Jun 10 '13 at 11:17

22

I think graph edit distance is the measure that you were looking for.

Graph edit distance measures the minimum number of graph edit operations to transform one graph to another, and the allowed graph edit operations includes:

Insert/delete an isolated vertex
Insert/delete an edge
Change the label of a vertex/edge (if labeled graphs)

However, computing the graph edit distance between two graphs is NP-hard. The most efficient algorithm for computing this is an A*-based algorithm, and there are other sub-optimal algorithms.

answered Jun 10 '13 at 11:17

Jason

573
1
3
15

@ivotro these slides introduce the basic concepts of GED, http://orion.math.iastate.edu/rymartin/talks/EditDist/editIITcolloq.pdf – Jason Jan 24 '16 at 05:14
@jason.Z these papers/ PPT talks about the theory of GED, is there any implementation based on latest suggestions in GED? – Vishrant Sep 22 '17 at 18:09

score 10 · Answer 2 · answered Sep 14 '13 at 14:00

10

You should look at the paper A survey of graph edit distance

answered Sep 14 '13 at 14:00

J.-E. Pin

238
3
9

score 4 · Answer 3 · answered May 16 '13 at 16:43

4

For a general graph it is a NP-complete problem as others mentioned in their answer. But for tree graph there are well known polynomial algorithms. May be most famous of them is "Zhang Shasha" algorithm which was published in 1989.

answered May 16 '13 at 16:43

Shafaet

425
1
6
17

score 3 · Answer 4 · answered May 06 '13 at 14:47

Note:

The Levenshtein distance (or edit distance) is between two strings

But in Graph you should search between at least N! position that you find Identity of each edge and vertex. You can compare between two graph by unique index easily,But The master question is define identity for each vertex and edge.this question (find identity for each vertex and edge in two graph that they can to transform ) is very hard and was called isomorphism problem (NP-Complete). You can search about isomorphism graph.

Edit distance between two graphs

4 Answers4

Linked