Stochastic Iterative Graph Matching
  Recent works leveraging Graph Neural Networks to approach graph matching
tasks have shown promising results. Recent progress in learning discrete
distributions poses new opportunities for learning graph matching models. In
this work, we propose a new model, Stochastic Iterative Graph MAtching (SIGMA),
to address the graph matching problem. Our model defines a distribution of
matchings for a graph pair so the model can explore a wide range of possible
matchings. We further introduce a novel multi-step matching procedure, which
learns how to refine a graph pair's matching results incrementally. The model
also includes dummy nodes so that the model does not have to find matchings for
nodes without correspondence. We fit this model to data via scalable stochastic
optimization. We conduct extensive experiments across synthetic graph datasets
as well as biochemistry and computer vision applications. Across all tasks, our
results show that SIGMA can produce significantly improved graph matching
results compared to state-of-the-art models. Ablation studies verify that each
of our components (stochastic training, iterative matching, and dummy nodes)
offers noticeable improvement.
