Graph matching: relax or not?

Graphs are a ubiquitous mathematical abstraction employed in numerous problems in science and engineering. Of particular importance is the need to find best structure-preserving matching of graphs. Since graph matching is a computationally intractable problem, numerous heuristics exist to approximate its solution. An important class of graph matching heuristics is relaxation techniques based on replacing the original problem by a continuous convex program. Conditions for applicability or inapplicability of such convex relaxations are poorly understood. In this talk, I will show easy to check spectral properties characterizing a wide family of graphs for which equivalence of convex relaxation to the exact graph matching is guaranteed to hold.

Alex Bronstein is an associate professor in the Faculty of Computer Science at the Technion, a visiting professor at Duke University and a senior research scientist at Intel Corporation. His research interests include numerical geometry, computer vision, and machine learning. The 3D acquisition and analysis technology he developed was acquired by Intel and is being marketed under the RealSense brand.