On the Performance of a Canonical Labeling for Matching Correlated Erdos-Renyi Graphs

When

14/05/2018    
10:00 am-10:30 am
Matthias Grossglauser
EPFL

Where

LINCS / EIT Digital
23 avenue d'Italie, 75013 Paris

Event Type

Recent results have characterized the exact information-theoretic threshold for graph matching in correlated Erd?s-Rényi graphs. However, very little is known about the existence of efficient algorithm to achieve graph matching without seeds. In this work, we identify a region in which a straightforward and efficient canonical labeling algorithm, initially introduced in the context of graph isomorphism, succeeds in matching correlated Erd?s-Rényi graphs. The algorithm has two steps. In the first step, all vertices are labeled by their degrees and a trivial minimum distance matching (i.e., simply sorting vertices according to their degrees) matches the a fixed number of highest degree vertices in the two graphs. Having identified this subset of vertices, the remaining vertices are matched using a noisy variant of a bipartite matching algorithm.

Joint work with Osman Dai, Daniel Cullina and Negar Kiyavash