Timezone: »

 
Spotlight
(Probably) Concave Graph Matching
Haggai Maron · Yaron Lipman

Thu Dec 06 01:15 PM -- 01:20 PM (PST) @ Room 517 CD
in Thu Track 3 -- Session 2 »

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).

Author Information

Haggai Maron (Weizmann Institute of Science)
Yaron Lipman (Weizmann Institute of Science)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors