Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition
By Bin Luo, Edwin Robert Hancock. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
385 citations recorded by the source corpus.
This paper describes an efficient algorithm for inexact graph matching. The method is purely structural, that is, it uses only the edge or connectivity structure of the graph and does not draw on node or edge attributes. We make two contributions: 1) commencing from a probability distribution for matching errors, we show how the problem of graph matching can be posed as maximum-likelihood estimation using the apparatus of the EM algorithm; and 2) we cast the recovery of correspondence matches between the graph nodes in a matrix framework. This allows one to efficiently recover correspondence matches using the singular value decomposition. We experiment with the method on both real-world and synthetic data. Here, we demonstrate that the method offers comparable performance to more computationally demanding methods.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing
View Paper: https://www.semanticscholar.org/paper/99921b2d99d10edb18edaa790f07bc3601086308
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Rémi Flamary
- Nicolas Courty
- Mohammad Rostami
- Alain Rakotomamonjy
- Devis Tuia
- Ronald M. Summers
- Shijun Wang
- Soheil Kolouri
In Computer Vision and Pattern Recognition
- Alain Rakotomamonjy
- Rémi Flamary
- Nicolas Courty
- Mohammad Rostami
- Devis Tuia
- Ronald M. Summers
- Shijun Wang
- Soheil Kolouri
In Signal Processing
Citations in the corpus
- Optimal Transport for Domain Adaptation (2014, background): “In this sense, the domain adaptation problem can be seen as a graph matching problem [10], [11], [34] as each source sample has to be”
- Machine Learning and Radiology (2012, background): “assignment matrix which defines the correspondence between two vertex sets as hidden variable and proposed an integrative expectation–maximization (EM) algorithm to solve this problem (Luo and Hancock, 2001).”
- Thirty Years Of Graph Matching In Pattern Recognition (2004, neutral): “Lades93[85], Pavlidis95[118], Wiskott97[170], Cho98[26], Duc99[39] Fisher73[51], Kittler89[80], Almohamad93[3], Christamas95[27], Pelillo95 [119], Pelillo95 [120], Gold96[61], Rangarajan96[127], Bomze97[12], Wilson97[167], Pelillo98 [121], Branca99[13], Huet99[71], Medasani99[105], Pelillo99[122, 12”