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.
- 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.
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.
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: