Graph Matching by Graduated Assignment

Abstract

A new algorithm for graph matching, which uses graduated assignment is presented, along with experimental results demonstrating large improvements in speed and accuracy over previous techniques. The softassign, a novel constraint satisfaction technique, is applied to a new graph matching energy function that uses a robust, sparse distance measure between the links of the two graphs. The softassign, which has emerged out of the neural network/statistical physics framework enforces two-way (assignment) constraints without the use of penalty terms. The algorithm's low order computational complexity [0(lm), where l and m are the number of links in the two graphs] compares favorably with most competing approaches. The method, not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching. Experiments on graphs generated from images and on randomly generated graphs, including benchmarks against a relation labeling algorithm and an algorithm employing Potts glass dynamics are reported. Over twenty-five thousand experiments were conducted. No comparable results have been reported by any other graph matching algorithm before in the research literature.