Graph Matching Based on Node Signatures

Abstract : We present an algorithm for graph matching in a pattern recognition context. This algorithm deals with weighted graphs, based on new structural and topological node signatures. Using these signatures, we compute an optimum solution for node-to-node assignment with the Hungarian method and propose a distance formula to compute the distance between weighted graphs. The experiments demonstrate that the newly presented algorithm is well suited to pattern recognition applications. Compared with four well-known methods, our algorithm gives good results for clustering and retrieving images. A sensitivity analysis reveals that the proposed method is also insensitive to weak structural changes.