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, in-sertion, 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 can 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.