Title: Exact Recovery with Symmetries for the Doubly-Stochastic Relaxation,
Abstract: Graph matching or quadratic assignment, is the problem of labeling the
vertices of two graphs so that they are as similar as possible. A common method
for approximately solving the NP-hard graph matching problem is relaxing it to
a convex optimization problem over the set of doubly stochastic (DS) matrices.
Recent analysis has shown that for almost all pairs of isomorphic and
asymmetric graphs, the DS relaxation succeeds in correctly retrieving the
isomorphism between the graphs. Our goal in this paper is to analyze the case
of symmetric isomorphic graphs. This goal is motivated by shape matching
applications where the graphs of interest usually have reflective symmetry.
For symmetric problems the graph matching problem has multiple isomorphisms
and so convex relaxations admit all convex combinations of these isomorphisms
as viable solutions. If the convex relaxation does not admit any additional
superfluous solution we say that it is convex exact. In this case there are
tractable algorithms to retrieve an isomorphism from the convex relaxation.
We show that convex exactness depends strongly on the symmetry group of the
graphs; For a fixed symmetry group $G$, either the DS relaxation will be convex
exact for almost all pairs of isomorphic graphs with symmetry group $G$, or the
DS relaxation will fail for all such pairs. We show that for reflective groups
with at least one full orbit convex exactness holds almost everywhere, and
provide some simple examples of non-reflective symmetry groups for which convex
exactness always fails.
When convex exactness holds, the isomorphisms of the graphs are the extreme
points of the convex solution set. We suggest an efficient algorithm for
retrieving an isomorphism in this case. We also show that the "convex to
concave" projection method will also retrieve an isomorphism in this case.