Graph Matching: Relax at Your Own Risk

Understand

Graph matching---aligning a pair of graphs to minimize their edge disagreements---has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics.

• Its attention can be partially attributed to its computational difficulty.
• Although many heuristics have previously been proposed in the literature to approximately solve graph matching, very few have any theoretical support for their performance.
• A common technique is to relax the discrete problem to a continuous problem, therefore enabling practitioners to bring gradient-descent-type algorithms to bear.