Skip to content
Preprint

Graph Matching in Random Geometric Graphs I: Efficient Algorithms

Oct 2026 · 0 citations
Mathematics Computer Science

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 $\langle u_i^A,u_i^B\rangle=\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\H{o}s--R\'enyi 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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.