Abstract
In this talk, I will discuss the problem of graph matching or network alignment for Erdős--Rényi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. Let G and G' be edge-correlated graphs that are marginally G(n,p) Erdős--Rényi graphs. For a permutation pi representing a latent matching between the vertices of G and G', denote by G^pi the graph obtained from permuting the vertices of G by pi. Observing G^pi and G', we aim to recover the matching pi. We show that for graphs with constant correlation and with average degree satisfying (1+eps)*log(n)<np<n^o(1), there is a polynomial-time algorithm that recovers pi with probability 1-o(1). This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated Erdős--Rényi graphs with constant correlation. The algorithm is based on comparison of partition trees associated with the graph vertices.