Multi-Resolution Spectral Graph Matching
Victor Gonzalez, Antonio Ortega · 2019
In this paper we study the problem of inexact weighted graph matching, where the goal is to find the correspondence between the vertices of two similar graphs. We propose a novel multi-resolution approach that improves the performance of single resolution graph matching which can be jointly combined with state-of-the art graph matching algorithms. Spectral graph matching determines the best correspondence between the graphs at each resolution by identifying vertex permutations that minimize the distance between the spectrum of the two graphs. To obtain graphs at lower resolutions, we propose a graph downsampling method that aims at selecting nodes in each graph so as to guarantee that matching at the lower resolutions will be possible. A key contribution of our work is to estimate the reliability of matching at each resolution and then use this information to obtain a weighted matching reliability across all resolutions. A comparison with other spectral graph matching algorithms demonstrates the benefits of the proposed approach.