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 ℝd; the vectors uiA and uiB of corresponding vertices satisfy ⟨ uiA,uiB⟩=ρ, and the vertex labels of the second graph are permuted by an unknown permutation π. For every fixed correlation ρ∈(0,1] and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers π exactly with probability tending to one whenever d≥(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)L0 for a suitable constant L0, 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.
Related
- Deterministic and Random Bipartite Matching on General Networks: Convex Flow Reformulation, Asymptotic Properties, and Fast Algorithms
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
- Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs
- Planarity and number of crossings in general models of random geometric graphs
- Maximum degree for random geometric graphs in the connectivity regime and beyond
BibTeX
@misc{huang2026graph,
title = {{Graph Matching in Random Geometric Graphs I: Efficient Algorithms}},
author = {Dong Huang and Ankang Jiao and Shuangping Li and Zhangsong Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16675},
eprint = {2610.16675},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16675},
}
RIS
TY - UNPB
TI - Graph Matching in Random Geometric Graphs I: Efficient Algorithms
AU - Dong Huang
AU - Ankang Jiao
AU - Shuangping Li
AU - Zhangsong Li
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16675
UR - https://arxiv.org/abs/2610.16675
AB - 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 ℝ^d; the vectors u_i^A and u_i^B of corresponding vertices satisfy ⟨ u_i^A,u_i^B⟩=ρ, and the vertex labels of the second graph are permuted by an unknown permutation π. For every fixed correlation ρ∈(0,1] and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers π exactly with probability tending to one whenever d≥(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.
ER -