Stable and Informative Spectral Signatures for Graph Matching
This work addresses graph matching for computer vision and network analysis, presenting incremental improvements to existing methods.
The paper tackles the approximate weighted graph matching problem by introducing stable and informative first and second order compatibility terms based on spectral signatures, which show superior performance in experiments on synthetic graphs, the CMU house sequence, and real images.
In this paper, we consider the approximate weighted graph matching problem and introduce stable and informative first and second order compatibility terms suitable for inclusion into the popular integer quadratic program formulation. Our approach relies on a rigorous analysis of stability of spectral signatures based on the graph Laplacian. In the case of the first order term, we derive an objective function that measures both the stability and informativeness of a given spectral signature. By optimizing this objective, we design new spectral node signatures tuned to a specific graph to be matched. We also introduce the pairwise heat kernel distance as a stable second order compatibility term; we justify its plausibility by showing that in a certain limiting case it converges to the classical adjacency matrix-based second order compatibility function. We have tested our approach on a set of synthetic graphs, the widely-used CMU house sequence, and a set of real images. These experiments show the superior performance of our first and second order compatibility terms as compared with the commonly used ones.