Learning Graph Matching
  As a fundamental problem in pattern recognition, graph matching has
applications in a variety of fields, from computer vision to computational
biology. In graph matching, patterns are modeled as graphs and pattern
recognition amounts to finding a correspondence between the nodes of different
graphs. Many formulations of this problem can be cast in general as a quadratic
assignment problem, where a linear term in the objective function encodes node
compatibility and a quadratic term encodes edge compatibility. The main
research focus in this theme is about designing efficient algorithms for
approximately solving the quadratic assignment problem, since it is NP-hard. In
this paper we turn our attention to a different question: how to estimate
compatibility functions such that the solution of the resulting graph matching
problem best matches the expected solution that a human would manually provide.
We present a method for learning graph matching: the training examples are
pairs of graphs and the `labels' are matches between them. Our experimental
results reveal that learning can substantially improve the performance of
standard graph matching algorithms. In particular, we find that simple linear
assignment with such a learning scheme outperforms Graduated Assignment with
bistochastic normalisation, a state-of-the-art quadratic assignment relaxation
algorithm.
