Graph Matching in Random Geometric Graphs I: Efficient Algorithms

Abstract

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in ${\mathbb{R}}^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $⟨u_i^A,u_i^B⟩=\rho$, and the vertex labels of the second graph are permuted by an unknown permutation $\pi$. For every fixed correlation $\rho \in (0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $\pi$ exactly with probability tending to one whenever $d\ge (\log n{)}^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n{)}^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős--Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.

arXiv comment62 pages, 4 figures