In this paper we address the graph matching problem. Following the recent works of \cite{zaslavskiy2009path,Vestner2017} we analyze and generalize the idea of concave relaxations. We introduce the concepts of \emph{conditionally concave} and \emph{probably conditionally concave} energies on polytopes and show that they encapsulate many instances of the graph matching problem, including matching Euclidean graphs and graphs on surfaces. We further prove that local minima of probably conditionally concave energies on general matching polytopes (\eg, doubly stochastic) are with high probability extreme points of the matching polytope (\eg, permutations).

Update: I have considered the author response. Some of my previous questions have been answered. I have updated my review and "overall score". This paper focuses on graph matching problems with quadratic objective functions. These objectives are usually equivalent to a quadratic assignment problem (QAP) [1] on the permutation matrix space. The authors focused on the Frank-Wolfe algorithm (Algorithm 1) on the objectives with the relaxation from the permutation matrix space to the doubly stochastic matrix space DS.