arXiv preprint ·
Graph Matching in Random Geometric Graphs I: Efficient Algorithms
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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=ρ$, and the vertex labels of the second graph are permuted by an unknown permutation $π$. For every fixed correlation $ρ\in(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\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
Classical and Quantum Information Measures Characterizing Convertibility: An Axiomatic Approach
Sampling from the Sherrington-Kirkpatrick Model up to Criticality
The Singularity Has a Distribution: Exact Timing Laws and Detection Limits for a Stochastic Intelligence Explosion
Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber Dynamics
Subgaussian Vector Balancing by an Ising Model
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.