Robust Self-supervised Learning of Deep Graph Matching with Mixture of Modes

This project page includes the dataset of our PAMI submission.



Graph matching (GM) has been a long-standing combinatorial problem due to its NP-hard nature, with wide computational applications, especially in computer vision. Recently (deep) learning-based approaches have shown their superior performance over the traditional solvers while the methods are almost based on supervised learning which can be expensive or even impractical. We develop a unified self-supervised learning framework from matching two graphs to multiple graphs, without ground truth. Specifically, off-the-shelf classic solver is designated to serve as the reference to generate pseudo correspondence labels for training. Our framework further allows self-supervised learning with graphs from a mixture of modes, to ensure its applicability in realistic noisy settings. Meanwhile, we develop and unify the graduated assignment (GA) strategy for matching of two-graph, multi-graph, and graphs from a mixture of modes, whereby two-way constraint and classification confidence (for mixture case) are modulated by two separate annealing parameters, respectively. The GA technique also naturally allows for partial matching, which is ubiquitous in real-world scenarios. We release a new benchmark for visual GM with an emphasis on partial matching over multiple graphs. Experimental results on real-world benchmarks show our self-supervised method performs comparatively and even better against two-graph based supervised approaches.

Paper & Code
  • Preliminary conference version (in NeurIPS 2020): [link]
  • Code and pre-trained models: [github]
We propose a unified self-supervised learning framework for comprehensively three graph matching variants:
  • Two Graph Matching (2GM): Matching two graphs from the same category;
  • Multi-Graph Matching (MGM): Joint matching of more than two graphs from the same category;
  • Multi-Graph Matching with a Mixture of Modes (MGM3): Joint matching of more than two graphs from different categories.
To our best knowledge, these three problems cover all existing graph matching variants.

Our proposed self-supervised learning framework is shown as follows. Here the GM solver in white box can be any of solvers for matching either of two-graph, multi-graph, or graphs from a mixture of modes. The red modules support gradient back-propagation, and the white parts generate node correspondences (within clustered graph groups) as the pseudo supervision to train the top learnable part whose typical embodiment includes CNN and GNN.

To fulfill the unified framework for all graph matching settings, we resort to the classic graduated assignment (GA) algorithm as the embodiment of GM solver. Specifically, we combine the classic GA algorithm with modern deep learning models, and we propose three self-supervised learning graduated assignment models: GANN-2GM, GANN-MGM, GANN-MGM3 for 2GM, MGM, MGM3 settings, respectively.

The performance of our self-supervised learning models are comparative or even better than state-of-the-art supervised graph matching models.
The Released IMC-PT-SparseGM Dataset

Dataset Download Links: [google drive] [baidu drive] code: 0576

In this paper, we propose a new vision graph matching dataset namely IMC-PT-SparseGM, based on IMC-PT 2020 challenge. A comparison of existing vision graph matching datasets is presented:

Comparison of Existing Vision Graph Matching Datasets

dataset name # images # classes avg # nodes # universe partial rate data type best-known f1 (by Apr 2021)
CMU house/hotel 212 2 30 30 0.0% gray-scale 100% (learning-free, RRWM, ECCV 2012)
Willow ObjectClass 404 5 10 10 0.0% RGB 97.8% (self-supervised learning, ours)
CUB2011 11788 200 12.0 15 20.0% RGB 83.2% (supervised learning, PCA-GM, ICCV 2019)
Pascal VOC Keypoint 8702 20 9.07 6 to 23 28.5% RGB 62.8% (supervised learning, BBGM, ECCV 2020)
IMC-PT-SparseGM (ours) 25061 16 21.36 50 57.3% RGB 67.9% (self-supervised learning, ours)

A visualization of 3D point cloud labels provided by the original IMC-PT (blue) and our selected anchor points for graph matching in IMC-PT-SparseGM (red):

A visualization of graph matching labels from IMC-PT-SparseGM: