Graph Matching via convex relaxation to the simplex
Ernesto Araya Valdivia Hemant Tyagi
This paper addresses the Graph Matching problem, which consists of finding
the best possible alignment between two input graphs, and has many applications
in computer vision, network deanonymization and protein alignment. A common
approach to tackle this problem is through convex relaxations of the NP-hard
\emph{Quadratic Assignment Problem} (QAP).
  Here, we introduce a new convex relaxation onto the unit simplex and develop
an efficient mirror descent scheme with closed-form iterations for solving this
problem. Under the correlated Gaussian Wigner model, we show that the simplex
relaxation admits a unique solution with high probability. In the noiseless
case, this is shown to imply exact recovery of the ground truth permutation.
Additionally, we establish a novel sufficiency condition for the input matrix
in standard greedy rounding methods, which is less restrictive than the
commonly used `diagonal dominance' condition. We use this condition to show
exact one-step recovery of the ground truth (holding almost surely) via the
mirror descent scheme, in the noiseless setting. We also use this condition to
obtain significantly improved conditions for the GRAMPA algorithm [Fan et al.
2019] in the noiseless setting.