Résumé: Graph Edit Distance (GED) problem is a well-known tool used to measure the similarity/dissimilarity be- tween two graphs. It searches for the best set of edit operations (in terms of cost) that transforms one graph into another. Due to the NP-hardness nature of the problem, the search space increases exponen- tially making exact approaches impossible to use for large graphs. In this context, there is a huge need for approaches that give near-optimal results in reasonable time. In this paper, we propose a tree-based approximate approach for dealing with GED problem. It operates on a search tree that models all possi- ble solutions of the problem. Since exploring the whole tree is impractical; this approach keeps only the best k nodes at each level of the tree for further exploration. This reduces enormously the execution time without scarifying the solution quality. Experiments using small and medium size data-sets show the low deviation of our results as compared to the optimal results of a Depth First Search algorithm. Moreover, our approach show a strong scalability potential by dealing with large data-sets in low execution time.

Langue: Anglais
Thème Informatique

Mots clés:
Graph matching
Graph Edit Distance (GED)
Approximate approach
pattern recognition