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