BMVC 2004, Kingston, 7th-9th Sept, 2004
Graph Matching using Spectral Embedding and Semidefinite Programming
X. Bai, H. Yu and E. Hancock (University of York)
This paper describes how graph-spectral methods can be used to transform
the node correspondence problem into one of point-set alignment. We commence
by using the ISOMAP algorithm to embed the nodes of a graph in a
low-dimensional Euclidean space. With the nodes in the graph transformed
to points in a metric space, we can recast the problem of graph-matching
into that of aligning the points. Here we use semidefinite programming to
develop a variant of the Scott and Longuet-Higgins algorithm to find point
correspondences. We experiment with the resulting algorithm on a number
of real-world problems.
(pdf article)