Graph Matching Tools

This toolbox proposes a common ground for several graph matching methods. We propose our methods with a set of state-of-art methods using our own implementation. The scope of this work is to offer reproducible research and alternatives.

Current available methods

Pairwise method

• KerGM
• GWL
• FGW
• RRWM
• Factorized RRWM
• GRASP

Multiway methods (state-of-art)

• HiPPI
• KMeans (as a naive way of doing the multimatch)
• MSync
• MatchEIG
• QuickMatch
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation
• IRGCL
• GA-MGMC
• MatchALS
• Symmetric Sparse Boolean Matrix Factorization
• Factorized multi-graph matching
• MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities

Multiway method (homemade)

• Kernelized multi-graph matching

Mean graph methods

• MMM method based on pairwise matching
• Wasserstein barycenter using FGW

Auxiliary methods (aka solvers...)

Optimal transport

• Sinkhorn-Knopp
• Sinkhorn algorithm with sparse Newton iterations

Manifold optimization

• Fast and accurate optimization on the orthogonal manifold without retraction

Graph generation

• Sucal pits graph using methods and code from papers 1, 2 and 3.

Installation

The package can be installed in editable mode using the following command from the base directory,

pip install -e .

We also propose a configuration for Poetry as an alternative for installation.

The documentation can be build using sphinx-build (please install the required packages for development). For example to generate the HTML documentation you can use,

sphinx-build -b html docs <output>

where is the output directory for documentation.

Examples

We provide several examples based on this toolbox,

1. KMeans for graph matching.
2. Application of our method on random graph with a comparison against MatchEIG.
3. Application of different methods on Willow and PascalVOC databases using Pytorch-Geometrics. For example to run the MKerGM method on the duck class from Willow we can execute,

gmt_demo_pytorchdata --category duck --sigma 70.0 --gamma 0.01  --rff 200 --iterations 20 --rank 10

4. Generation of simulated sucal pits graph. For example, to generate 11 graphs (one reference with 10 noisy version) and kappa=400, we can execute,

graph_matching_tools/demos/gmt_demo_generate_graph.py --add_outliers --suppress_nodes --coord_noise_kappa 400 --sample_number 10 --save

These examples may require modules that are not required in the setup.

Current Authors

• Guillaume Auzias (INT)
• François-Xavier Dupé (LIS)
• Sylvain Takerkart (INT)

All authors are from Aix-Marseille University.

Previous Authors

• Rohit Yadav (INT, LIS)
• Marius Thorre (LIS)