# Algorithms

Below we summarize the graph matching methods that we consider in our comparison. For a more detailed description please refer to our paper and the references below. The following table shows an overview of their characteristics and references.

method | IQP | ILP | bijective | non-pos. | 0-unary | lineariz. | norm | doubly | spectral | discret. | path fol. | fusion | duality | SGA | BCA |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

fgmd | + | + | + | ||||||||||||

fm | + | + | |||||||||||||

fw | + | + | + | ||||||||||||

ga | + | + | + | + | + | ||||||||||

ipfps | + | + | + | + | + | + | |||||||||

ipfpu | + | + | + | + | + | ||||||||||

lsm | + | + | + | + | + | ||||||||||

mpm | + | + | + | + | + | ||||||||||

pm | + | + | + | + | + | + | |||||||||

rrwm | + | + | + | + | + | ||||||||||

smac | + | + | + | + | + | + | |||||||||

sm | + | + | + | + | + | + | |||||||||

dd-ls0 | + | + | + | ||||||||||||

dd-ls3 | + | + | + | ||||||||||||

dd-ls4 | + | + | + | ||||||||||||

fm-bca | + | + | + | + | |||||||||||

hbp | + | + | + | + | |||||||||||

mp | + | + | + | ||||||||||||

mp-mcf | + | + | + | ||||||||||||

mp-fw | + | + | + |

We want to keep this benchmark also relevant in the future. If you want to see other algorithm included in the benchmark, you can submit results a new solver.

## Primal Heuristics

### Linearization based

These methods are based on iterative linearizations of the quadratic objective of the graph matching problem.

*Iterated projected fixed point* (ipfp) [Leoardeanu09] solves on each iteration the LAP obtained through linearization in the vicinity of a current, in general non-integer, assignment.
Between iterations the quadratic objective is optimized along the direction to the obtained LAP solution, which yields a new, in general non-integer assignment.
We evaluate two versions of ipfp which differ by their initialization:
ipfpu is initialized with
\(x^0\in [0,1]^{\mathcal V\times\mathcal L}\), where
\(x^0_{is}=1/\sqrt{N}\) if
\(c_{is,is}<\infty\), and
\(x^0_{is}=0\) otherwise.
Here,
\(N:= |\{ is\in\mathcal V\times\mathcal L \mid c_{is,is}< \infty \}|\).
ipfps starts from the result of the spectral matching sm [Leordeanu05] described below.

*Graduated assignment* (ga) [Gold96] optimizes the doubly-stochastic relaxation.
On each iteration it approximately solves the LAP obtained through linearization in the vicinity of a current, in general non-integer, assignment utilizing the Sinkhorn algorithm [Kosowsky94] for a given fixed temperature.
The obtained approximate solution is used afterwards as the new assignment.
The temperature is decreased over iterations to gradually make the solutions closer to integral.

*Fast approximate quadratic programming* (fw) [Vogelstein15] considers the Frank-Wolfe algprithm [Frank56] for optimizing over the set of doubly-semi-stochastic matrices.
Each iteration first solves a LAP to find the optimum of the linearization at the current solution, followed by a line search in order to find the best convex combination of the current and the new solution.
To obtain an integer solution, the objective of the LAP solution is evaluated in each iteration, and the lowest one among all solutions is kept.
The initial LAP is based on the unary costs only.
The implementation [Swoboda21] we evaluate is applicable to the general Lawler form of the problem, in contrast to the Koopmans-Beckmann form addressed in [Vogelstein15].

### Norm constraints based

*Spectral matching* (sm) [Leordeanu05]
uses a spectral relaxation that amounts to a Rayleigh quotient problem [Horn12] which can be optimized by the power iteration method. Here, each update comprises of a simple matrix multiplication and a subsequent normalization, so that
\(x^t\) is iteratively updated via
\(x^{t+1} = -C x^t / \| C x^t\|_2\).

*Spectral matching with affine constraints* (smac) [Cour07]
is similar to sm, but additionally takes into account affine equality constraints that enforce one-to-one matchings. The resulting formulation amounts to a Rayleigh quotient problem under affine constraints, that can efficiently be computed in terms of the eigenvalue decomposition.

*Max-pooling matching* (mpm) [Cho14] resembles sm, but it replaces the sum-pooling implemented in terms of the matrix multiplication
\(-C x\) in the power iteration update of SM by a max-pooling operation.
With that, only candidate matches with the smallest costs are taken into account.

*Local sparse model* (lsm) [Jiang15] solves the relaxation
\(\max_{x} x^\top C x\), s.t.
\(||x||_{1,2} = \sqrt{\sum_{i=1}^{|\mathcal V|} \big( \sum_{k=1}^{|\mathcal L|} |x_{ik}| \big)} = 1\),
\(x \geq 0\).
The
\(l_{1,2}\)-norm
\(||x||_{1,2}\) should encourage the solution of the above relaxation to be sparse in each row when treating
\(x\) as a matrix.
This resembles the sparsity property of permutation matrices, which satisfy
\(||x||_{1,2}=|\mathcal V|\).

*Remark:*
All of the norm constraints based algorithms described above require non-positive [1] costs in order to guarantee convergence of the underlying iterative techniques.
This condition can be w.l.o.g. assumed for any graph matching problem.
The corresponding cost transformation is described in the supplement.

### Probabilistic interpretation based

*Reweighted Random Walks Matching* (rrwm) [Cho10] interprets graph matching as the problem of selecting reliable nodes in an *association graph*, whose weighted adjacency matrix is given by
\(-C\).
Nodes are selected through a random walk that starts from one node and randomly visits nodes according to a Markov transition matrix derived from the edge weights of the association graph.
In order to take into account matching constraints, the authors of [Cho10] consider a reweighted random walk strategy.

*Probabilistic matching* (pm) [Zass08] considers a probabilistic formulation of graph matching in which the quadratic objective is replaced by a relative entropy objective.
It is shown that by doing so one can obtain a convex problem formulation via marginalization, which is optimized in terms of an iterative successive projection algorithm.

*Remark:*
Most of the primal heuristics considered above aim to optimize the quadratic objective of the graph matching problem over a continuous set such as, e.g., the Birkhoff polytope.
The resulting assignment
\(x\in\mathcal R^{\mathcal V\times\mathcal L}\) is, therefore, not guaranteed to be integer.
As suggested in [Cho10], to obtain an integer assignment we solve a LAP with
\((-x)\) treated as the cost matrix.
We apply this procedure as a postprocessing step for ipfp, ga, sm, smac, mpm, lsm, rrwm, and pm.
Note that this postprocessing does not change an integer assignment.

### Path following based

*Factorized graph matching* (fgmd) [Zhou16] proposes an efficient factorization of the cost matrix to speed-up computations, and is based on the convex-concave path following strategy.
Individual problems from the path are solved with the Frank-Wolfe method [Frank56].

### Randomized generation and fusion based

*Fusion moves with a greedy heuristic* (fm) [Hutschenreiter21]
is based on the graphical model representation and consists of two parts: A randomized greedy assignment generation, and *fusion* of the assignments.
The randomized generator greedily fixes labels in the nodes in a way that minimizes the objective value restricted to the already fixed labels.
The fusion procedure merges the current assignment with the next generated one by approximately solving an auxiliary *binary* MAP inference problem utilizing QPBO-I [Rother07].
The merged solution is guaranteed to be at least as good as the two input assignments.
This property guarantees monotonic improvement of the objective value.

## Lagrange duality-based techniques

The methods below consider the Lagrange decompositions [Guignard87] of the graph matching problem [Toressani13], or its graphical model representation, see [Zhang16], [Swoboda17] and [Hutschenreiter21], and optimize the corresponding dual. The methods differ in the dual optimization and chosen primal solution reconstruction algorithms.

### Block-coordinate methods (hbp, mp-*, fm-bca)

The works [Zhang16], [Swoboda17] and [Hutschenreiter21] employ a block-coordinate ascent (BCA) technique to optimize the dual problem. Since the dual is piece-wise linear, BCA algorithms may not attain the dual optimum, but may get stuck in a sub-optimal fixed point, see [Bertsekas99] and [Savchynskyy19].

Although the elementary operations performed by these algorithms are very similar, their convergence speed and attained fixed points differ drastically. We refer to Our Paper for more details.

### Subgradient method (dd-ls*)

The algorithms denoted as dd-ls* with * being 0, 3 or 4 represent different variants of a dual subgradient optimization method [Toressani13].
The variant dd-ls0 addresses the relaxation equivalent to a symmetrized graphical model formulation, see supplement of Our Paper for a description.
This is achieved by considering the Lagrange decomposition of the problem into two graphical models, with
\(\mathcal V\) and
\(\mathcal L\) being the set of nodes, respectively, and a LAP subproblem.
The graphical models are further decomposed into acyclic ones, ie trees, solvable by dynamic programming, see, e.g., Chapter 9 of [Savchynskyy19].
The *tree decomposition* is not described in [Toressani13], and we reconstructed it based on the source code [Kolmogorov15] and communication with the authors.
As we observed it to be more efficient than the *max-flow subproblems* suggested in the paper [Toressani13] the latter were not used in our evaluation.

Variants dd-ls3 and dd-ls4 tighten the relaxation of dd-ls0 by considering *local subproblems* of both graphical models in the decomposition.
These are obtained by reducing the node sets
\(\mathcal V\) and
\(\mathcal L\) to
\(3\) or respectively
\(4\) elements inducing a connected subgraph of the graphical model, see [Toressani13] for details.

## References

D.P. Bertsekas. “Nonlinear programming, 2nd edition”. Athena scientific, 1999.

M. Cho, J. Sun, O. Duchenne, J. Ponce. “Finding Matches in a Haystack: A Max-Pooling Strategy for Graph Matching in the Presence of Outliers”. CVPR, 2014.

T. Cour, P. Srinivasan, J. Shi. “Balanced Graph Matching”. NeurIPS, 2007.

M. Frank, P. Wolfe, et.al. “An Algorithm for Quadratic Programming”. Naval Research Logistics Quarterly, 1956.

S. Gold, A. Rangarajan. “A Graduated Assignment Algorithm for Graph Matching”. PAMI, 1996.

M. Guignard, S. Kim. “Lagrangean Decomposition: A Model Yielding Stronger Lagrangean Bounds”. Mathematical Programming, 1987.

R.A. Horn, C.R. Johnson. “Matrix Analysis”. Cambridge University Press, 2012.

B. Jiang, J. Tang, C. Ding, B. Luo. “A Local Sparse Model for Matching Problem”. AAAI, 2015.

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

V. Kolmogorov. “Feature Correspondence via Graph Matching Source Code”. 2015. [URL]

J.J. Kosowsky, A.L. Yuille., “The Invisible Hand Algorithm: Solving the Assignment Problem with Statistical Physics”. Neural Networks, 1994.

M. Leordeanu, M. Hebert. “A Spectral Technique for Correspondence Problems Using Pairwise Constraints”. ICCV, 2005.

M. Leordeanu, M. Hebert, R. Sukthankar. “An Integer Projected Fixed Point Method for Graph Matching and MAP Inference”. NeurIPS, 2009.

C. Rother, V. Kolmogorov, V.S. Lempitsky, M. Szummer. “Optimizing Binary MRFs via Extended Roof Duality”. CVPR, 2007.

B. Savchynskyy. “Discrete Graphical Models – An Optimization Perspective”. Foundations and Trends in Computer Graphics and Vision, 2019.

P. Swoboda, C. Rother, H. Abu Alhaija, D. Kainmüller, B. Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching”. CVPR, 2017.

L. Torresani, V. Kolmogorov, C. Rother. “A Dual Decomposition Approach to Feature Correspondence”. PAMI, 2013.

J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik, S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, C.E. Priebe. “Fast Approximate Quadratic Programming for Graph Matching”. PLOS ONE, 2015.

R. Zass, A. Shashua. “Probabilistic Graph and Hypergraph Matching”. CVPR, 2008.

Z. Zhang, Q. Shi, J. McAuley, W. Wei, Y. Zhang, A. van den Hengel. “Pairwise Matching Through Max-Weight Bipartite Belief Propagation”. CVPR, 2016.

F. Zhou, F.D. la Torre. “Factorized Graph Matching”. PAMI, 2016.