From dense subgraph to graph matching: A label propagation approach

Graph matching (GM) is a fundamental problem in computer science, and it has been successfully applied to provide solutions to many problems in computer vision. In this paper, we consider GM as a clustering problem in an association graph whose nodes represent candidate correspondences between two graphs to be matched. And we take the dense subgraph as a good prior for correct correspondences, thus we propose a label propagation approach to expand the dense subgraph to resolve the whole cluster. The label propagation approach is achieved by an affinity-preserving manifold ranking algorithm with a dynamic label vector which enforces the matching constraints. And the matching constraints is introduced through a doubly-stochastic normalization procedure. Extensive experiments demonstrate that our algorithm outperforms the state-of-the-art GM algorithms especially in the presence of outliers and deformation.