Structural graph matching using the EM algorithm and singular value decomposition

Citation
B. Luo et Er. Hancock, Structural graph matching using the EM algorithm and singular value decomposition, IEEE PATT A, 23(10), 2001, pp. 1120-1136
Citations number
52
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
ISSN journal
01628828 → ACNP
Volume
23
Issue
10
Year of publication
2001
Pages
1120 - 1136
Database
ISI
SICI code
0162-8828(200110)23:10<1120:SGMUTE>2.0.ZU;2-D
Abstract
This paper describes an efficient algorithm for inexact graph matching. The method is purely structural, that is to say, it uses only the edge or conn ectivity structure of the graph and does not draw on node or edge attribute s. We make two contributions. Commencing from: a probability distribution f or matching errors, we show how the problem of graph matching can be posed as maximum-likelihood estimation using the apparatus of the EM algorithm. O ur second contribution is to cast the recovery of correspondence matches, b etween the graph nodes in a matrix framework. This allows us to efficiently recover correspondence matches, using singular value decomposition. We exp eriment with the method on both real-world and synthetic data. Here, we dem onstrate that the method offers comparable performance to more computationa lly demanding methods.