[BUG] Multi-graph matching solvers do not return a cycle consistent solution

[sebastianstricker]

Describe the bug I ran into issues while testing on the hotel/house/synthetic datasets, that are commonly used to compare multi-graph matching solvers.

Neither CAO, nor Floyd produce a cycle consistent solution on the example problem. gamgm seems to solve a specific variant of the multi-graph matching problem and is not applicable to this general case i think?

To Reproduce I wrote a minimal working example that showcases the error: https://github.com/sebastianstricker/pygmtools-multi-graph-error/

Expected behavior Return of cycle consistent solutions.

Environment:

• OS: Fedora
• Python Version: 3.12.5
• Pygmtools Version: 0.5.3
• Environment report:

Linux-6.10.5-200.fc40.x86_64-x86_64-with-glibc2.39
Python 3.12.5 (main, Aug  7 2024, 00:00:00) [GCC 14.2.1 20240801 (Red Hat 14.2.1-1)]
NumPy 2.1.1
SciPy 1.14.1
pygmtools 0.5.3
Torch not installed
Paddle not installed
Jittor not installed
No GPU found. If you are using GPU, make sure to install pynvml: pip install pynvml

[sebastianstricker]

To make this repository run, i had to write a parser from the public .dd file format (Swoboda, Paul, et al. “Structured prediction problem archive”. (2022)).

The multigraph matching problem is well defined via the costs of the upper triangular part of each pairwise affinity matrix. If you have insight in how to correctly set the remaining, redundant matrix entries that are required as an input for pygmtools, I would highly appreciate it!

Maybe you already have your own parser or could point out errors within mine.

[JzMaple]

@sebastianstricker Hello, I believe there is some misunderstanding of the CAO and Floyd algorithms. These two algorithms do not guarantee that the solution to multi-graph matching will be cycle consistent. In fact, they relax the cycle consistency constraint and include it as part of the optimization objective. In other words, the optimization objective becomes a weighted function of both the affinity score and cycle consistency, rather than just the affinity score.

You may want to check section 3.1 of Floyd's paper Unifying offline and online multi-graph matching via finding shortest paths on supergraph for further details.

[sebastianstricker]

I see. Thanks for the quick reply!

[rogerwwww]

Hi Sebastian,

Just one more comment on gamgm: if you have the adjacency matrices (which I believe is the case in your example), you will be able to run the algorithm

[sebastianstricker]

Hi Runzhong,

If that is possible that would be great!

However, each individual graph matching problem is given by a single cost matrix as in Lawler's form of the QAP. More specifically, as node to node assignment costs (diagonal terms) and pairwise assignment terms (off-diagonal terms).

To my understanding, it is possible to formulate any Koopmans-Beckman QAP as a Lawler QAP but not the other way around?