Exact Matching of Random Graphs with Constant Correlation

This paper deals with the problem of graph matching or network alignment for Erd\H{o}s–R'enyi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. Let $G$ and $G^{\mathrm{\prime }}$ be $G(n,p)$ Erd\H{o}s–R'enyi graphs marginally, identified with their adjacency matrices. Assume that $G$ and $G^{\mathrm{\prime }}$ are correlated such that $$\mathbb{E}$[G_{ij} G’_{ij}] = p(1-\alpha)$\mathrm{.}Forapermutation$\pi$ representing a latent matching between the vertices of $G$ and $G^{\mathrm{\prime }}$, denote by $G^{\pi }$ the graph obtained from permuting the vertices of $G$ by $\pi$. Observing $G^{\pi }$ and $G^{\mathrm{\prime }}$, we aim to recover the matching $\pi$. In this work, we show that for every $\varepsilon \in (0,1]$,thereis$n_0>0$dependingon$\varepsilon$andabsoluteconstants$\alpha_0, R > 0$withthefollowingproperty\mathrm{.}Let$n \ge n_0$,$(1+\varepsilon) \log n \le np \le n^{\frac{1}{R \log \log n}}$,and$0 < \alpha < \min(\alpha_0,\varepsilon/4)$\mathrm{.}Thereisapolynomial-timealgorithm$F$suchthat$$\mathbb{P}${F(G^\pi,G’)=\pi}=1-o(1)$. This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated Erd\H{o}s–R'enyi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.