Deep Graph Matching Meets Mixed-Integer Linear Programming : Relax at Your Own Risk?

Graph matching is an important problem that has received widespread attention, especially in computer vision. Recently, several state-of-the-art methods have sought to incorporate graph matching with deep learning. However, there is no research to explain the role of the graph matching algorithm in the model. Therefore, we propose integrating a MILP formulation of the graph matching problem into the deep learning architecture. This formulation is solved to optimal, and it provides an inherent baseline. Meanwhile, similar approaches are derived by releasing the optimal guarantee of the graph matching solver and by introducing a quality level. This quality level controls the quality of the solutions provided by the graph matching solver. In addition, several relaxations of the graph matching problem are put to the test. Our experimental evaluation gives several theoretical insights and guides the direction of deep graph matching methods