Exact Matching of Random Graphs with Constant Correlation

Abstract

This paper deals with the problem of graph matching or network alignment for Erdos--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) Erdos--R\'enyi graphs marginally, identified with their adjacency matrices. Assume that G and G' are correlated such that E[G_ij 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 (0,1], there is n_0>0 depending on and absolute constants _0, R > 0 with the following property. Let n n_0, (1+) n np n^1R n, and 0 < < (_0,/4). There is a polynomial-time algorithm F such that P (G^,G')=\=1-o(1). This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated Erdos--R\'enyi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.

Tasks

Reproductions