Structural graph matching using the EM algorithm and singular value decomposition

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 connectivity structure of the graph and does not draw on node or edge attributes. We make two contributions. Commencing from a probability distribution for matching errors, we show how the prob-lem of graph-matching can be posed as maximum likeli-hood estimation using the apparatus of the EM algorithm. Our second contribution is to cast the recovery of corre-spondence matches between the graph-nodes in a matrix framework. This allows us to efficiently recover correspon-dence matches using singular value decomposition. We ex-periment with the method on both real-world and synthetic data. Here we demonstrate that the method offers compara-ble performance to more computationally demanding meth-ods.