Approximate graph matching using probabilistic hill climbing algorithms

We consider the problem of comparison between labeled graphs. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion, and relabel operations on graph nodes and edges. Specifically, we consider two variants of the approximate graph matching problem: Given a pattern graph P and a data graph D, what is the distance between P and D? What is the minimum distance between P and D when subgraphs can be freely removed from D? We first observe that no efficient algorithm con solve either variant of the problem, unless P=NP. Then we present several heuristic algorithms based on probabilistic hill climbing techniques. Finally we evaluate the accuracy and time efficiency of the heuristics by applying them to a set of generated graphs and DNA molecules