On the use of similarity metrics for approximate graph matching

In this paper, we investigate heuristics for approximate graph matching, in particular its formulation as a Maximum Common Edge Subgraph problem. Our experiments suggest that a small percentage of accurate node matches is sufficient to get near optimal solutions using a simple hill-climbing. The real challenge could then be to somehow drag the search in this zone. For this purpose, we discuss the use of similarity measures. We present and assess the performance of two similarity measures. Very good results were obtained on labeled graphs.