A Path Following Algorithm for the Graph Matching Problem
A Path Following Algorithm for the Graph Matching Problem
复制标题
DOI：
10.1109/tpami.2008.245
复制
发表时间：
2009-12-01
影响因子：
23.6
通讯作者：
Vert, Jean-Philippe
中科院分区：
文献类型：
--
作者：
Zaslavskiy, Mikhail;Bach, Francis;Vert, Jean-Philippe
提出了一种求解标号赋权图匹配问题的凸凹规划方法。通过将加权图匹配问题改写为置换矩阵集上的最小二乘问题，并将其松弛为两个不同的优化问题：双随机矩阵集上的二次凸优化问题和二次凹优化问题，得到了凸凹规划公式。凹松弛算法具有与初始图匹配问题相同的全局极小值，但寻找其全局极小值也是一个困难的组合问题。因此，我们从凸松弛出发，沿着凸凹公式的线性插值法得到的凸凹问题的解的路径，构造了凹问题解的一个近似。该方法可以很容易地将图标签相似度的信息集成到优化问题中，从而进行带标签的加权图匹配。在四个数据集：模拟图形、QAPLib、视网膜血管图像和手写汉字上，将该算法与一些性能最好的图形匹配方法进行了比较。在所有情况下，结果都与最先进的水平具有竞争力。
We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.