Learning Graph Matching

Simple item page
dc.creatorCaetano, Tiberio S.
dc.creatorMcAuley, Julian J.
dc.creatorCheng, Li
dc.creatorLe, Quoc V.
dc.creatorSmola, Alex J.
dc.date2008-06-17
dc.date.accessioned2026-07-07T09:45:17Z
dc.date.available2026-07-07T09:45:17Z
dc.descriptionAs 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.
dc.description10 pages, 4 figures
dc.identifierhttps://arxiv.org/abs/0806.2890
dc.identifierhttp://arxiv.org/abs/0806.2890
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163148
dc.subjectComputer Vision and Pattern Recognition
dc.subjectMachine Learning
dc.titleLearning Graph Matching
dc.typetext

Files

Collections

arXiv