Exact Matching of Random Graphs with Constant Correlation

This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. Let G and G' be G(n, p) ErdHos--R'enyi graphs marginally, identified with their adjacency matrices. Assume that G and G' are correlated such that mathbbE[Gij G'ij] = p(1-α). For a permutation π representing a latent matching between the vertices of G and G', denote by Gπ the graph obtained from permuting the vertices of G by π. Observing Gπ and G', we aim to recover the matching π. In this work, we show that for every varepsilon ∈ (0,1], there is n0>0 depending on varepsilon and absolute constants α0, R > 0 with the following property. Let n ≥ n0, (1+varepsilon) log n ≤ np ≤ n^frac1R log log n, and 0 < α < min(α0,varepsilon/4). There is a polynomial-time algorithm F such that mathbbPF(Gπ,G')=π=1-o(1). This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated ErdHos--R'enyi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.