Algorithms

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.

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.