We give a quasipolynomial time algorithm for the graph matching problem (also known as noisy or robust graph isomorphism) on correlated random graphs. Specifically, for every $gamma>0$, we give a $n^{O(log n)}$ time algorithm that given a pair of $gamma$-correlated $G(n,p)$ graphs $G_0,G_1$ with average degree between $n^{varepsilon}$ and $n^{1/153}$ for $varepsilon = o(1)$, recovers the ground truth permutation $piin S_n$ that matches the vertices of $G_0$ to the vertices of $G_n$ in the way that minimizes the number of mismatched edges. We also give a recovery algorithm for a denser regime, and a polynomial-time algorithm for distinguishing between correlated and uncorrelated graphs. Prior work showed that recovery is information-theoretically possible in this model as long the average degree was at least $log n$, but sub-exponential time algorithms were only known in the dense case (i.e., for $p > n^{-o(1)}$). Moreover, Percolation Graph Matching, which is the most common heuristic for this problem, has been shown to require knowledge of $n^{Omega(1)}$ seeds (i.e., input/output pairs of the permutation $pi$) to succeed in this regime. In contrast our algorithms require no seed and succeed for $p$ which is as low as $n^{o(1)-1}$.
Download