Efficient algorithms match vertices in complex geometric graphs
Graph Matching in Random Geometric Graphs I: Efficient Algorithms
Data Structures and Algorithms
Summary
Matching points between two related complex networks can be very tricky when the networks are created using hidden geometric rules. The authors study this problem and present a new efficient method that can find the correct matching between the points with high accuracy. Their approach uses special patterns counted around each point to amplify small clues linking the two networks, even when the data is in a high-dimensional space. They also analyze challenges related to the geometry and show when their method works best based on the data’s dimensions.
What this means in practice
- •For data integration teams: Match entities accurately across complex datasets modeled by geometric relations using the proposed polynomial-time algorithm.
- •For network engineers: Improve detection of corresponding nodes in paired communication or sensor networks where geometric relations influence connections.
Authors
Dong Huang, Ankang Jiao, Shuangping Li, Zhangsong Li
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.