pygmtools: Python Graph Matching Tools¶
pygmtools provides graph matching solvers in Python and is easily accessible via:
$ pip install pygmtools
Official documentation: https://pygmtools.readthedocs.io
Source code: https://github.com/Thinklab-SJTU/pygmtools
Graph matching is a fundamental yet challenging problem in pattern recognition, data mining, and others. Graph matching aims to find node-to-node correspondence among multiple graphs, by solving an NP-hard combinatorial optimization problem.
Doing graph matching in Python used to be non-trivial, and this library wants to make researchers’ lives easier.
pygmtools has the following features:
Support various solvers, including traditional combinatorial solvers (including linear, quadratic, and multi-graph) and novel deep learning-based solvers;
Support various backends, including
numpywhich is universally accessible, and some state-of-the-art deep learning architectures with GPU support:
Deep learning friendly, the operations are designed to best preserve the gradient during computation and batched operations support for the best performance.
You can install the stable release on PyPI:
$ pip install pygmtools
or get the latest version by running:
$ pip install -U https://github.com/Thinklab-SJTU/pygmtools/archive/master.zip # with --user for user install (no root)
Now the pygmtools is available with the
The following packages are required, and shall be automatically installed by
Python >= 3.5 requests >= 2.25.1 scipy >= 1.4.1 Pillow >= 7.2.0 numpy >= 1.18.5 easydict >= 1.7 appdirs >= 1.4.4 tqdm >= 4.64.1
Available Graph Matching Solvers¶
This library offers user-friendly API for the following solvers:
Linear assignment solvers including the differentiable soft Sinkhorn algorithm , and the exact solver Hungarian .
Soft and differentiable quadratic assignment solvers, including spectral graph matching  and random-walk-based graph matching .
Discrete (non-differentiable) quadratic assignment solver integer projected fixed point method .
Composition based Affinity Optimization (CAO) solver  by optimizing the affinity score, meanwhile gradually infusing the consistency.
Multi-Graph Matching based on Floyd shortest path algorithm .
Graduated-assignment based multi-graph matching solver  by graduated annealing of Sinkhorn’s temperature.
Intra-graph and cross-graph embedding based neural graph matching solvers PCA-GM and IPCA-GM  for matching individual graphs.
Channel independent embedding (CIE)  based neural graph matching solver for matching individual graphs.
Neural graph matching solver (NGM)  for the general quadratic assignment formulation.
This library is designed to support multiple backends with the same set of API. Please follow the official instructions to install your backend.
The following backends are available:
Numpy (default backend, CPU only)
PyTorch (recommended backend, GPU friendly, deep learning friendly)
PaddlePaddle (GPU friendly, deep learning friendly)
Jittor (GPU friendly, deep learning friendly)
For more details, please read the documentation.
The Deep Graph Matching Benchmark¶
pygmtools is also featured with a standard data interface of several graph matching benchmarks. We also maintain a
repository containing non-trivial implementation of deep graph matching models, please check out
ThinkMatch if you are interested!
Any contributions/ideas/suggestions from the community is welcomed! Before starting your contribution, please read the Contributing Guide.
Developers and Maintainers¶
pygmtools is currently developed and maintained by members from ThinkLab at
Shanghai Jiao Tong University.
 Sinkhorn, Richard, and Paul Knopp. “Concerning nonnegative matrices and doubly stochastic matrices.” Pacific Journal of Mathematics 21.2 (1967): 343-348.
 Munkres, James. “Algorithms for the assignment and transportation problems.” Journal of the society for industrial and applied mathematics 5.1 (1957): 32-38.
 Leordeanu, Marius, and Martial Hebert. “A spectral technique for correspondence problems using pairwise constraints.” International Conference on Computer Vision (2005).
 Cho, Minsu, Jungmin Lee, and Kyoung Mu Lee. “Reweighted random walks for graph matching.” European conference on Computer vision. Springer, Berlin, Heidelberg, 2010.
 Leordeanu, Marius, Martial Hebert, and Rahul Sukthankar. “An integer projected fixed point method for graph matching and map inference.” Advances in neural information processing systems 22 (2009).
 Yan, Junchi, et al. “Multi-graph matching via affinity optimization with graduated consistency regularization.” IEEE transactions on pattern analysis and machine intelligence 38.6 (2015): 1228-1242.
 Jiang, Zetian, Tianzhe Wang, and Junchi Yan. “Unifying offline and online multi-graph matching via finding shortest paths on supergraph.” IEEE transactions on pattern analysis and machine intelligence 43.10 (2020): 3648-3663.
 Solé-Ribalta, Albert, and Francesc Serratosa. “Graduated assignment algorithm for multiple graph matching based on a common labeling.” International Journal of Pattern Recognition and Artificial Intelligence 27.01 (2013): 1350001.
 Wang, Runzhong, Junchi Yan, and Xiaokang Yang. “Graduated assignment for joint multi-graph matching and clustering with application to unsupervised graph matching network learning.” Advances in Neural Information Processing Systems 33 (2020): 19908-19919.
 Wang, Runzhong, Junchi Yan, and Xiaokang Yang. “Combinatorial learning of robust deep graph matching: an embedding based approach.” IEEE Transactions on Pattern Analysis and Machine Intelligence (2020).
 Yu, Tianshu, et al. “Learning deep graph matching with channel-independent embedding and hungarian attention.” International conference on learning representations. 2019.
 Wang, Runzhong, Junchi Yan, and Xiaokang Yang. “Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching.” IEEE Transactions on Pattern Analysis and Machine Intelligence (2021).