  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.
