heatingma/pygmtools
0
1---2language:3- zh4- en5tags:6- pygmtools7- deep-learning8- graph-matching9---10 11<img src="https://pygmtools.readthedocs.io/en/latest/_static/images/pygmtools_logo.svg" alt="pygmtools: Python Graph Matching Tools" width="800"/>12 13-----------------------------------------14 15``pygmtools`` (Python Graph Matching Tools) provides graph matching solvers in Python and is easily accessible via:16 17```bash18$ pip install pygmtools19```20 21Official documentation: https://pygmtools.readthedocs.io22 23Source code: https://github.com/Thinklab-SJTU/pygmtools24 25Graph matching is a fundamental yet challenging problem in pattern recognition, data mining, and others.26Graph matching aims to find node-to-node correspondence among multiple graphs, by solving an NP-hard combinatorial27optimization problem.28 29Doing graph matching in Python used to be difficult, and this library wants to make researchers' lives easier. 30To highlight, ``pygmtools`` has the following features:31 32* *Support various solvers*, including traditional combinatorial solvers (including linear, quadratic, and multi-graph) 33 and novel deep learning-based solvers;34* *Support various backends*, including ``numpy`` which is universally accessible, and some state-of-the-art deep 35 learning architectures with GPU support: 36 ``pytorch``, ``paddle``, ``jittor``, ``tensorflow``, ``mindspore``; 37* *Deep learning friendly*, the operations are designed to best preserve the gradient during computation and batched 38 operations support for the best performance.39 40## Installation41 42You can install the stable release on PyPI:43 44```bash45$ pip install pygmtools46```47 48or get the latest version by running:49 50```bash51$ pip install -U https://github.com/Thinklab-SJTU/pygmtools/archive/master.zip # with --user for user install (no root)52```53 54Now the pygmtools is available with the ``numpy`` backend.55 56The following packages are required, and shall be automatically installed by ``pip``:57 58```59Python >= 3.760requests >= 2.25.161scipy >= 1.4.162Pillow >= 7.2.063numpy >= 1.18.564easydict >= 1.765appdirs >= 1.4.466tqdm >= 4.64.167wget >= 3.268```69 70## Available Graph Matching Solvers71This library offers user-friendly API for the following solvers:72 73* [Two-Graph Matching Solvers](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.classic_solvers.html)74 * Linear assignment solvers including the differentiable soft 75 [Sinkhorn algorithm](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.linear_solvers.sinkhorn.html) [1], 76 and the exact solver [Hungarian](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.linear_solvers.hungarian.html) [2].77 * Soft and differentiable quadratic assignment solvers, including [spectral graph matching](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.classic_solvers.sm.html) [3] 78 and [random-walk-based graph matching](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.classic_solvers.rrwm.html) [4].79 * Discrete (non-differentiable) quadratic assignment solver 80 [integer projected fixed point method](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.classic_solvers.ipfp.html) [5]. 81* [Multi-Graph Matching Solvers](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.multi_graph_solvers.html)82 * [Composition based Affinity Optimization (CAO) solver](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.multi_graph_solvers.cao.html) [6] 83 by optimizing the affinity score, meanwhile gradually infusing the consistency.84 * Multi-Graph Matching based on 85 [Floyd shortest path algorithm](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.multi_graph_solvers.mgm_floyd.html) [7].86 * [Graduated-assignment based multi-graph matching solver](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.multi_graph_solvers.gamgm.html) [8][9]87 by graduated annealing of Sinkhorn’s temperature.88* [Neural Graph Matching Solvers](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.neural_solvers.html)89 * Intra-graph and cross-graph embedding based neural graph matching solvers 90 [PCA-GM](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.neural_solvers.pca_gm.html) 91 and [IPCA-GM](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.neural_solvers.ipca_gm.html) [10]92 for matching individual graphs.93 * [Channel independent embedding (CIE)](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.neural_solvers.cie.html) [11]94 based neural graph matching solver for matching individual graphs.95 * [Neural graph matching solver (NGM)](https://pygmtools.readthedocs.io/en/latest/api/_autosummary/pygmtools.neural_solvers.ngm.html) [12]96 for the general quadratic assignment formulation.97 98## Available Backends99This library is designed to support multiple backends with the same set of API. 100Please follow the official instructions to install your backend.101 102The following backends are available:103 104* [Numpy](https://numpy.org/) (**default** backend, CPU only)105 106<img src="https://pygmtools.readthedocs.io/en/latest/_images/numpy_logo.png" alt="numpy logo" width="200"/>107 108* [PyTorch](https://pytorch.org/) (GPU friendly, deep learning friendly)109 110<img src="https://pygmtools.readthedocs.io/en/latest/_images/pytorch_logo.png" alt="pytorch logo" width="200"/>111 112* [Jittor](https://github.com/Jittor/Jittor) (GPU friendly, JIT support, deep learning friendly)113 114<img src="https://pygmtools.readthedocs.io/en/latest/_images/jittor_logo.png" alt="jittor logo" width="200"/>115 116* [PaddlePaddle](https://www.paddlepaddle.org.cn/en) (GPU friendly, deep learning friendly)117 118<img src="https://pygmtools.readthedocs.io/en/latest/_images/paddle_logo.png" alt="paddle logo" width="200"/>119 120* [Tensorflow](https://tensorflow.google.cn/) (GPU friendly, deep learning friendly)121 122<img src="https://pygmtools.readthedocs.io/en/latest/_images/tensorflow_logo.png" alt="tensorflow logo" width="200"/>123 124### Development status (0.3.8)125 126| | Numpy | PyTorch | Jittor | PaddlePaddle | Tensorflow | MindSpore |127| ------------------- | ----- | ------- | ------ | ------------ | ---------- | --------- |128| Linear Solvers | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ |129| Classic Solvers | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ |130| Multi-Graph Solvers | ✔ | ✔ | ✔ | ✔ | 📆 | 📆 |131| Neural Solvers | ✔ | ✔ | ✔ | ✔ | 📆 | 📆 |132| Examples Gallery | ✔ | ✔ | ✔ | ✔ | 📆 | 📆 |133 134✔: Supported; 📆: Planned for future versions (contributions welcomed!).135 136For more details, please [read the documentation](https://pygmtools.readthedocs.io/en/latest/guide/get_started.html#install-other-backends).137 138## Pretrained Models139 140The library includes several neural network solvers. The pretrained models shall be automatically downloaded upon 141needed from Google Drive. If you are experiencing issues accessing Google Drive, please download the pretrained models142manually and put them at ``~/.cache/pygmtools`` (for Linux).143 144Available at:145[[google drive]](https://drive.google.com/drive/folders/1O7vkIW8QXBJsNsHUIRiSw91HJ_0FAzu_?usp=sharing)146[[baidu drive]](https://pan.baidu.com/s/1MvzfM52NJeLWx2JXbbc6HA?pwd=x8bv)147 148## The Deep Graph Matching Benchmark149 150``pygmtools`` is also featured with a standard data interface of several graph matching benchmarks. Please read 151[the corresponding documentation](https://pygmtools.readthedocs.io/en/latest/guide/benchmark.html) for details.152 153We also maintain a repository containing non-trivial implementation of deep graph matching models, please check out154[ThinkMatch](https://thinkmatch.readthedocs.io/) if you are interested!155 156## Chat with the Community157 158If you have any questions, or if you are experiencing any issues, feel free to [raise an issue](https://github.com/Thinklab-SJTU/pygmtools/issues/new) on GitHub. 159 160We also offer the following chat rooms if you are more comfortable with them:161 162* Discord (for English speakers): 163 164 [](https://discord.gg/8m6n7rRz9T)165 166* QQ Group (for Chinese speakers)/QQ群(中文用户): 696401889167 168 [](https://qm.qq.com/cgi-bin/qm/qr?k=NlPuwwvaFaHzEWD8w7jSOTzoqSLIM80V&jump_from=webapi&authKey=chI2htrWDujQed6VtVid3V1NXEoJvwz3MVwruax6x5lQIvLsC8BmpmzBJOCzhtQd)169 170## Contributing171Any contributions/ideas/suggestions from the community is welcomed! Before starting your contribution, please read the172[Contributing Guide](https://github.com/Thinklab-SJTU/pygmtools/blob/main/CONTRIBUTING.md).173 174## Developers and Maintainers175 176``pygmtools`` is currently developed and maintained by members from [ThinkLab](http://thinklab.sjtu.edu.cn) at 177Shanghai Jiao Tong University. 178 179## References180<!--MLA style references-->181 182[1] Sinkhorn, Richard, and Paul Knopp. "Concerning nonnegative matrices and doubly stochastic matrices." Pacific Journal of Mathematics 21.2 (1967): 343-348.183 184[2] Munkres, James. "Algorithms for the assignment and transportation problems." Journal of the society for industrial and applied mathematics 5.1 (1957): 32-38.185 186[3] Leordeanu, Marius, and Martial Hebert. "A spectral technique for correspondence problems using pairwise constraints." International Conference on Computer Vision (2005).187 188[4] Cho, Minsu, Jungmin Lee, and Kyoung Mu Lee. "Reweighted random walks for graph matching." European conference on Computer vision. Springer, Berlin, Heidelberg, 2010.189 190[5] 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).191 192[6] 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.193 194[7] 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.195 196[8] 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.197 198[9] 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.199 200[10] 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).201 202[11] Yu, Tianshu, et al. "Learning deep graph matching with channel-independent embedding and hungarian attention." International conference on learning representations. 2019.203 204[12] 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).