A Continuous Method for Graph Matching Based on Continuation

摘要

Graph matching has long been a fundamental problem in artificial intelligence and computer science. Because of the NP-complete nature, approximate methods are necessary for graph matching. As a type of approximate method, the continuous method is widely used in computer-vision-related graph matching tasks, which typically first relaxes the original discrete optimization problem to a continuous one and then projects the continuation solution back to the discrete domain. The continuation scheme usually provides a superior performance in finding a good continuous local solution within reasonable time, but it is limited to only the continuous optimization problem and therefore cannot be directly applied to graph matching. In this paper we propose a continuation scheme based algorithm directly targeting at the graph matching problem. Specifically, we first construct an unconstrained continuous optimization problem of which the objective function incorporates both the original objective function and the discrete constraints, and then the Gaussian smooth based continuation is applied to this problem. Experiments witness the effectiveness of the proposed method.