Multi-matching optimization

Application and library to solve (multi-)graph matching problems.

For licensing term, see the LICENSE file. This work uses third party software. Please refer to LICENSE-3RD-PARTY.txt for an overview and recognition.

For details, refer to our publication:

• M. Kahl, S. Stricker, L. Hutschenreiter, F. Bernard, B. Savchynskyy
  “Unlocking the Potential of Operations Research for Multi-Graph Matching”.
  arXiv Pre-Print 2024. [PDF] [ArXiv]

Python

Install via pip

`pip install pylibmgm`

Refer to the usage guide: Python Documentation

C++

0. (Install requirements)

   • Install g++ or clang (c++ compiler), meson (build system) and git
     • sudo apt install g++ meson git (Ubuntu)
     • sudo dnf install g++ meson git (Fedora)

1. Clone repository

   • git clone https://github.com/vislearn/multi-matching-optimization.git
   • cd ./multi-matching-optimization

2. Build

   • meson setup --buildtype release -Db_ndebug=true ../builddir/
   • meson compile -C ../builddir/

3. Run

   • ../builddir/mgm -i tests/hotel_instance_1_nNodes_10_nGraphs_4.txt -o ../mgm_output --mode seqseq

Usage

Minimal Usage

$ mgm -i [IN_FILE] -o [OUT_DIR] --mode [OPT_MODE]

You can use one of the small models in the tests/ directory for testing.

Input files

Input files follow the .dd file format for multi-graph matching problems, as defined in the Structured prediction problem archive. See references below.

Available CLI parameters

• --name
  Base name for the resulting .json and .log files.

• -l, --labeling
  Path to an existing solution file (json). Pass to improve upon this labeling.

• --mode ENUM
  Optimization mode. See below.

• --set-sizeINT
  Subset size for incremenetal generation

• --merge-one
  In parallel local search, merge only the best solution. Do not try to merge other solutions as well.

• -t, --threads INT
  Number of threads to use. Upper limit defined by OMP_NUM_THREADS environment variable.

• --libmpopt-seed UINT
  Fix the random seed for the fusion moves graph matching solver of libmpopt.

• --unary-constant FLOAT
  Constant to add to every assignment cost. Negative values nudges matchings to be more complete.

• --synchronize
  Synchronize a cylce inconsistent solution. Excludes: --synchronize-infeasible

• --synchronize-infeasible
  Synchronize a cylce inconsistent solution. Allow all (forbidden) matchings. Excludes: --synchronize

Optimization modes

--mode specifies the optimization routine. It provides ready to use routines that combine construction, graph matching local search (GM-LS), and swap local search (SWAP-LS) algorithms as defined in the publication.

The following choices are currently available:

Construction modes. Use these to generate solutions quickly

• seq: sequential construction
• par: parallel construction
• inc: incremental construction

Construction + GM-LS modes. A bit slower, but gives better solutions

• seqseq: sequential construction -> sequential GM-LS
• seqpar: sequential construction -> parallel GM-LS
• parseq: parallel construction -> sequential GM-LS
• parpar: parallel construction -> parallel GM-LS
• incseq: incremental construction -> sequential GM-LS
• incpar: incremental construction -> parallel GM-LS

Construction + iterative GM-LS & SWAP-LS. After construction, iterate between GM-LS and and SWAP-LS.

• optimal: sequential construction -> Until conversion: (sequential GM-LS <-> swap local search)
• optimalpar: parallel construction -> Until conversion: (parallel GM-LS <-> swap local search)

Improve given labeling.

Skip construction and perform local search on a pre-existing solution. Improve modes require a labeling to be provided via the --labeling [JSON_FILE] command line option.

• improve-swap: improve with SWAP-LS
• improve-qap: improve with sequential GM-LS
• improve-qap-par: improve with parallel GM-LS
• improveopt: improve with alternating sequential GM-LS <-> SWAP-LS
• improveopt-par: improve with alternating parallel GM-LS <-> SWAP-LS

Use as synchronization algorithm

To synchronize a pre-existing cylce inconsistent solution, call with --synchonize or --synchonize-infeasible, either disallowing or allowing forbidden matchings.

Synchronize feasible. Feasible solution. Disallows forbidden matchings.

$ mgm -i [IN_FILE] -o [OUT_DIR] --mode [OPT_MODE] --labeling [JSON_FILE] --synchonize

Synchronize infeasible. Infeasible solution. Allows forbidden matchings.

$ mgm -i [IN_FILE] -o [OUT_DIR] --mode [OPT_MODE] --labeling [JSON_FILE] --synchonize-infeasible

Software dependencies

This software incorporates and uses third party software. Dependencies are provided as meson wrap files. They should be installed automatically during the build process, but manual installation can help solve issues, if meson fails to build them.

NOTE: Links given point to the original authors publications, which may have been substantially modified. The corresponding .wrap files in this repositry's subprojects/ folder contain links to the actual code needed to compile the solver.

• spdlog
  logging library; https://github.com/gabime/spdlog
• cli11
  Command line parser; https://github.com/CLIUtils/CLI11
• nlohman_json
  json parsing. https://github.com/nlohmann/json
• unordered_dense
  A fast & densely stored hashmap; https://github.com/martinus/unordered_dense
• libqpbo
  for quadratic pseudo boolean optimization (QPBO); https://pub.ista.ac.at/~vnk/software.html
• libmpopt
  for quadratic assignment problem (QAP) optimization; https://github.com/vislearn/libmpopt
• Scipy_lap
  Linear assignment problem (LAP) solver implementation from the Scipy python package; https://github.com/scipy/scipy

References

• M. Kahl, S. Stricker, L. Hutschenreiter, F. Bernard, B. Savchynskyy
  “Unlocking the Potential of Operations Research for Multi-Graph Matching”.
  arXiv Pre-Print 2024. [PDF] [ArXiv]

• L. Hutschenreiter, S. Haller, L. Feineis, C. Rother, D. Kainmüller, B. Savchynskyy.
  “Fusion Moves for Graph Matching”.
  ICCV 2021. [PDF] [ArXiv]

• Swoboda, P., Andres, B., Hornakova, A., Bernard, F., Irmai, J., Roetzer, P., Savchynskyy, B., Stein, D. and Abbas, A.
  “Structured prediction problem archive”
  arXiv preprint arXiv:2202.03574 (2022) [PDF] [ArXiv]