See the paper for the full details : https://doi.org/10.1016/j.patrec.2021.02.014 and https://hal.archives-ouvertes.fr/hal-03163084
To intuitively demonstrate the exactness of the proposition, we proceed as follows :
We start from the Graph Edit Distance problem expressed by model F2. F2 is an Integer Linear Program. The objective function of F2 is based on a cost function c between nodes and edges.
The Graph Matching Model (GMM) holds a similarity function s between nodes and edges. We link the similarity function s with the cost function c thanks to a new similarity function s' (roughly s'=-c).
With this similarity function s', we show that F2 turns to be a maximization problem and we call this new model F2'.
F2' is modified and transformed from a linear to a quadratic model called GMM'.
GMM' is identical to the original GMM. It is sufficient to show that both models express the same problem, that is to say, the graph matching problem.