  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 computationally challenging 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 broad class of friendly graphs
characterized by an easily verifiable spectral property. 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 only n separable linear equality constraints, which is
substantially more efficient than the standard relaxation involving 2n equality
and n^2 inequality constraints. Finally, we show that our results are still
valid for unfriendly graphs if additional information in the form of seeds or
attributes is allowed, with the latter satisfying an easy to verify spectral
characteristic.
