Exact Matching of Random Graphs with Constant Correlation

Abstract

This paper deals with 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^{\prime }$ be $G(n,p)$ Erdős--Rényi graphs marginally, identified with their adjacency matrices. Assume that $G$ and $G^{\prime }$ are correlated such that $\mathbb{E}[G_{ij}{G}_{ij}^{\prime }]=p(1-\alpha )$. For a permutation $\pi$ representing a latent matching between the vertices of $G$ and $G^{\prime }$, denote by $G^{\pi }$ the graph obtained from permuting the vertices of $G$ by $\pi$. Observing $G^{\pi }$ and $G^{\prime }$, we aim to recover the matching $\pi$. In this work, we show that for every $\epsilon \in (0,1]$, there is $n_0>0$ depending on $\epsilon$ and absolute constants ${\alpha }_0,R>0$ with the following property. Let $n\ge n_0$, $(1+\epsilon )\log n\le np\le n^{\frac{1}{R\log \log n}}$, and $0<\alpha <\min ({\alpha }_0,\epsilon /4)$. There is a polynomial-time algorithm $F$ such that $\mathbb{P}\{F(G^{\pi },G^{\prime })=\pi \}=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 with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.

55 pages, 1 figure

References in corpus (1)

• Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality

Cited by in corpus (2)

• Testing network correlation efficiently via counting trees
• Aligning random graphs with a sub-tree similarity message-passing algorithm