A graph matching method and a graph matching distance based on subgraph assignments

During the last decade, the use of graph-based object representation has drastically increased. As a matter of fact, object representation by means of graphs has a number of advantages over feature vectors. As a consequence. methods to compare graphs have become of first interest. In this paper, a graph matching method and a distance between attributed graphs are defined. Both approaches are based on subgraphs. In this context, subgraphs can be seen as structural features extracted from a given graph, their nature enables them to represent local information of a root node. Given two graphs G(1), G(2), the univalent mapping can be expressed as the minimum-weight subgraph matching between G(1) and G(2) with respect to a cost function. This metric between subgraphs is directly derived from well-known graph distances. In experiments on four different data sets, the distance induced by our graph matching was applied to measure the accuracy of the graph matching. Finally, we demonstrate a substantial speed-up compared to conventional methods while keeping a relevant precision. (C) 2009 Elsevier B.V. All rights reserved.