  The graph matching problem aims to discover a latent correspondence between
the vertex sets of two observed graphs. This problem has proven to be quite
challenging, with few satisfying methods that are computationally tractable and
widely applicable. The FAQ algorithm has proven to have good performance on
benchmark problems and works with a indefinite relaxation of the problem. Due
to the indefinite relaxation, FAQ is not guaranteed to find the global maximum.
However, if prior information is known about the true correspondence, this can
be leveraged to initialize the algorithm near the truth. We show that given
certain properties of this initial matrix, with high probability the FAQ
algorithm will converge in two steps to the truth under a flexible model for
pairs of random graphs. Importantly, this result implies that there will be no
local optima near the global optima, providing a method to assess performance.
