ThinkMatch
A research protocol for deep graph matching.
Install / Use
/learn @Thinklab-SJTU/ThinkMatchREADME
Think Match
ThinkMatch is developed and maintained by ThinkLab at Shanghai Jiao Tong University. This repository is developed for the following purposes:
- Providing modules for developing deep graph matching algorithms to facilitate future research.
- Providing implementation of state-of-the-art deep graph matching methods.
- Benchmarking existing deep graph matching algorithms under different dataset & experiment settings, for the purpose of fair comparison.
Official documentation: https://thinkmatch.readthedocs.io
Source code: https://github.com/Thinklab-SJTU/ThinkMatch
Introduction to Graph Matching
Graph Matching (GM) is a fundamental yet challenging problem in computer vision, pattern recognition and data mining. GM aims to find node-to-node correspondence among multiple graphs, by solving an NP-hard combinatorial problem named Quadratic Assignment Problem (QAP). Recently, there is growing interest in developing deep learning based graph matching methods.
Graph matching techniques have been applied to the following applications:
- <img src="https://thinkmatch.readthedocs.io/en/latest/_images/movie_synopses.png" alt="Bridging movie and synopses, ICCV 2019" width="50%">
- <img src="https://thinkmatch.readthedocs.io/en/latest/_images/superglue.png" alt="Superglue, CVPR 2020" width="50%">
- <img src="https://thinkmatch.readthedocs.io/en/latest/_images/molecules.png" alt="Molecules matching, CVPR 2021" width="50%">
-
and more...
In this repository, we mainly focus on image keypoint matching because it is a popular testbed for existing graph matching methods.
Readers are referred to the following survey for more technical details about graph matching:
- Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, Xiaokang Yang. "A Short Survey of Recent Advances in Graph Matching." ICMR 2016.
Deep Graph Matching Algorithms
ThinkMatch currently contains pytorch source code of the following deep graph matching methods:
- GMN
- Andrei Zanfir and Cristian Sminchisescu. "Deep Learning of Graph Matching." CVPR 2018. [paper]
- PCA-GM & IPCA-GM
- Runzhong Wang, Junchi Yan and Xiaokang Yang. "Combinatorial Learning of Robust Deep Graph Matching: an Embedding based Approach." TPAMI 2020. [paper], [project page]
- Runzhong Wang, Junchi Yan and Xiaokang Yang. "Learning Combinatorial Embedding Networks for Deep Graph Matching." ICCV 2019. [paper]
- NGM & NGM-v2
- Runzhong Wang, Junchi Yan, Xiaokang Yang. "Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching." TPAMI 2021. [paper], [project page]
- CIE-H
- Tianshu Yu, Runzhong Wang, Junchi Yan, Baoxin Li. "Learning deep graph matching with channel-independent embedding and Hungarian attention." ICLR 2020. [paper]
- GANN
- Runzhong Wang, Junchi Yan and Xiaokang Yang. "Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning." NeurIPS 2020. [paper]
- Runzhong Wang, Junchi Yan and Xiaokang Yang. "Unsupervised Learning of Graph Matching with Mixture of Modes via Discrepancy Minimization." TPAMI 2023. [paper], [project page]
- BBGM
- Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, Georg Martius. "Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers." ECCV 2020. [paper]
- GCAN
- Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, Bryan M. Williams. "Graph-Context Attention Networks for Size-Varied Deep Graph Matching." CVPR 2022. [paper]
- AFAT
- Runzhong Wang, Ziao Guo, Shaofei Jiang, Xiaokang Yang, Junchi Yan. "Deep Learning of Partial Graph Matching via Differentiable Top-K." CVPR 2023. [paper]
- LinSAT
- Runzhong Wang, Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, Junchi Yan. "LinSATNet: The Positive Linear Satisfiability Neural Networks." ICML 2023. [paper]
- COMMON & COMMON+
- Yijie Lin, Mouxing Yang, Jun Yu, Peng Hu, Changqing Zhang, Xi Peng. "Graph Matching with Bi-level Noisy Correspondence." ICCV 2023. [paper], [project page]
- Yijie Lin, Mouxing Yang, Peng Hu, Jiancheng Lv, Hao Chen, Xi Peng. "Learning with Partial and Noisy Correspondence in Graph Matching". TPAMI, 2026. [paper]
When to use ThinkMatch
ThinkMatch is designed as a research protocol for deep graph matching. It is recommended if you have any of the following demands:
- Developing new algorithms and publishing new graph matching papers;
- Understanding the details of deep graph matching models;
- Playing around with the hyperparameters and network details;
- Benchmarking deep graph matching networks.
When not to use ThinkMatch
You may find the environment setup in ThinkMatch complicated and the details of graph matching hard to understand.
pygmtools offers a user-friendly API, and is recommended for the following cases:
- If you want to integrate graph matching as a step of your pipeline (either learning or non-learning,
with
numpy/pytorch/jittor/paddle/mindspore/tensorflow). - If you want a quick benchmarking and profiling of the graph matching solvers available in
pygmtools. - If you do not want to dive too deep into the algorithm details and do not need to modify the algorithm.
You can simply install the user-friendly package by
$ pip install pygmtools
Official documentation: https://pygmtools.readthedocs.io
Source code: https://github.com/Thinklab-SJTU/pygmtools
Deep Graph Matching Benchmarks
PascalVOC - 2GM
| model | year | aero | bike | bird | boat | bottle | bus | car | cat | chair | cow | table | dog | horse | mbkie | person | plant | sheep | sofa | train | tv | mean | | ------------------------------------------------------------ | ---- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | | GMN | 2018 | 0.4163 | 0.5964 | 0.6027 | 0.4795 | 0.7918 | 0.7020 | 0.6735 | 0.6488 | 0.3924 | 0.6128 | 0.6693 | 0.5976 | 0.6106 | 0.5975 | 0.3721 | 0.7818 | 0.6800 | 0.4993 | 0.8421 | 0.9141 | 0.6240 | | PCA-GM | 2019 | 0.4979 | 0.6193 | 0.6531 | 0.5715 | 0.7882 | 0.7556 | 0.6466 | 0.6969 | 0.4164 | 0.6339 | 0.5073 | 0.6705 | 0.6671 | 0.6164 | 0.4447 | 0.8116 | 0.6782 | 0.5922 | 0.7845 | 0.9042 | 0.6478 | | NGM | 2019 | 0.5010 | 0.6350 | 0.5790 | 0.5340 | 0.7980 | 0.7710 | 0.7360 | 0.6820 | 0.4110 | 0.6640 | 0.40
