Levenshtein Generalization for Graphs?

Question

Is there a generalization of the levenshtein distance for searching for structures in graphs?

Answer 1

This paper might be of interest: Structural Similarity in Graphs

I am however afraid that calculating such distance would be very computationally intensive, most likely either NP or NP complete.

Answer 2

By distance you mean the total cost of insert node/delete node etc required to transform one labelled graph to another?

Perhaps the following paper will help: http://cs.nyu.edu/shasha/papers/freepap.ps

From the introduction of the paper:

We consider the problem of comparing CUAL graphs (Connected, Undirected, Acyclicgraphs with nodes being Labeled).1 Suppose we define the distance between two CUAL graphs to be the weighted number (the user chooses the weighting) of edit operations (insert node, delete node and relabel node) to transform one graph to the other. By reduction from exact cover by3-sets, one can show that nding the distance between two graphs is NP-hard. In view of the hardness of the problem, we propose a constrained distance metric, called the degree-2 distance,for graphs by requiring that any node to be inserted (deleted) have no more than 2 neighbors. As will become clear, this constraint is sensible in defining the edit operations on graphs. Further,the measure is a natural extension of the edit distance for strings [22] and Selkow’s distance fortrees [15].