Sequential Graph Matching with Sequential Monte Carlo


Seong-Hwan Jun, Samuel W.K. Wong, James Zidek, Alexandre Bouchard-Cote ;
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1075-1084, 2017.


We develop a novel probabilistic model for graph matchings and develop practical inference methods for supervised and unsupervised learning of the parameters of this model. The framework we develop admits joint inference on the parameters and the matching. Furthermore, our framework generalizes naturally to $K$-partite hypergraph matchings or set packing problems. The sequential formulation of the graph matching process naturally leads to sequential Monte Carlo algorithms which can be combined with various parameter inference methods. We apply our method to image matching problems, document ranking, and our own novel quadripartite matching problem arising from the field of computational forestry.

Related Material