Pygmtools

<img src="https://pygmtools.readthedocs.io/en/latest/_static/images/pygmtools_logo.svg" alt="pygmtools: Python Graph Matching Tools" width="800"/>

---

pygmtools is published in JMLR! Please cite our paper if our tools are useful in your research!

---

pygmtools (Python Graph Matching Tools) 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 difficult, and this library wants to make researchers' lives easier. To highlight, 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 numpy which is universally accessible, and some state-of-the-art deep learning architectures with GPU support: pytorch, paddle, jittor, tensorflow, mindspore;
• Deep learning friendly, the operations are designed to best preserve the gradient during computation and batched operations support for the best performance.

Installation

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 numpy backend.

The following packages are required, and shall be automatically installed by pip:

Python >= 3.8
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
networkx >= 2.8.8
aiohttp
async-timeout

Available Graph Matching Solvers

This library offers user-friendly API for the following solvers:

• Two-Graph Matching Solvers
  • Linear assignment solvers including the differentiable soft Sinkhorn algorithm [1], and the exact solver Hungarian [2].
  • Soft and differentiable quadratic assignment solvers, including spectral graph matching [3] and random-walk-based graph matching [4].
  • Discrete (non-differentiable) quadratic assignment solver integer projected fixed point method [5].
• Multi-Graph Matching Solvers
  • Composition based Affinity Optimization (CAO) solver [6] by optimizing the affinity score, meanwhile gradually infusing the consistency.
  • Multi-Graph Matching based on Floyd shortest path algorithm [7].
  • Graduated-assignment based multi-graph matching solver [8][9] by graduated annealing of Sinkhorn’s temperature.
• Neural Graph Matching Solvers
  • Intra-graph and cross-graph embedding based neural graph matching solvers PCA-GM and IPCA-GM [10] for matching individual graphs.
  • Channel independent embedding (CIE) [11] based neural graph matching solver for matching individual graphs.
  • Neural graph matching solver (NGM) [12] for the general quadratic assignment formulation.
  • Graph edit neural network A-star (GENN-A*) [13] for the graph edit distance problem.

Available Backends

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)

<img src="https://pygmtools.readthedocs.io/en/latest/_images/numpy_logo.png" alt="numpy logo" width="200"/>

• PyTorch (GPU friendly, deep learning friendly)

<img src="https://pygmtools.readthedocs.io/en/latest/_images/pytorch_logo.png" alt="pytorch logo" width="200"/>

• Jittor (GPU friendly, JIT support, deep learning friendly)

<img src="https://pygmtools.readthedocs.io/en/latest/_images/jittor_logo.png" alt="jittor logo" width="200"/>

• PaddlePaddle (GPU friendly, deep learning friendly)

<img src="https://pygmtools.readthedocs.io/en/latest/_images/paddle_logo.png" alt="paddle logo" width="200"/>

• Tensorflow (GPU friendly, deep learning friendly)

<img src="https://pygmtools.readthedocs.io/en/latest/_images/tensorflow_logo.png" alt="tensorflow logo" width="200"/>

• MindSpore (GPU friendly, deep learning friendly)

<img src="https://pygmtools.readthedocs.io/en/latest/_images/mindspore_logo.png" alt="mindspore logo" width="200"/>

For more details, please read the documentation.

Pretrained Models

The library includes several neural network solvers. The pretrained models shall be automatically downloaded upon needed from the hosted model repository. If you are experiencing issues with automatic download, please download the pretrained models manually and put them at ~/.cache/pygmtools (for Linux).

Available at: [huggingface] [google drive] [baidu drive]

The Deep Graph Matching Benchmark

pygmtools is also featured with a standard data interface of several graph matching benchmarks. Please read the corresponding documentation for details.

We also maintain a repository containing non-trivial implementation of deep graph matching models, please check out ThinkMatch if you are interested!

Chat with the Community

If you have any questions, or if you are experiencing any issues, feel free to raise an issue on GitHub.

We also offer the following chat rooms if you are more comfortable with them:

• Discord (for English speakers):

  

• QQ Group (for Chinese speakers)/QQ群(中文用户): 696401889

  

Contributing

Any contributions/ideas/suggestions from the community is welcomed! Before starting your contribution, please read the [Contributing Guide](https://github.com/Thinklab-SJTU/