We consider the problem of exact and inexact matching of weighted undirected graphs, in which a bijective correspondence is sought to minimize a quadratic weight disagreement. This NP-hard problem is often relaxed as a convex quadratic program, in which the space of permutations is replaced by the space of doubly-stochastic matrices. However, the applicability of such a relaxation is poorly understood. We define a class of friendly graphs characterized by an easy-to-verify spectral property, which we believe to be almost as broad as the class of asymmetric graphs. We prove that for friendly graphs, the convex relaxation is guaranteed to find the exact isomorphism or certify its inexistence. This result is further extended to approximately isomorphic graphs, for which we develop an explicit bound on the amount of weight disagreement under which the relaxation is guaranteed to find the globally optimal approximate isomorphism. We also show that in many cases, the graph matching problem can be further harmlessly relaxed to a convex quadratic program with n separable linear equality constraints only, which is substantially more efficient than the standard relaxation involving 2n equality and n^2 inequality constraints. Finally, we show that both convex relaxations are generally unsuitable for matching symmetric graphs.

本研究考虑权重无向图的精确和非精确匹配问题，通过定义“friendly graphs”和发展准确和近似解的确切条件和界限，以及优化找到最优近似同构的能力的凸松弛技术进行解决。

图匹配：松弛与否？