Random Graph Matching in Geometric Models: the Case of Complete Graphs
Random Graph Matching in Geometric Models: the Case of Complete Graphs
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Haoyu Wang;Yihong Wu;Jiaming Xu;Israel Yolou
中科院分区：
文献类型：
--
作者：
Haoyu Wang;Yihong Wu;Jiaming Xu;Israel Yolou
本文研究了两个边权通过潜在几何相关的完全图的匹配问题，将最近的一系列关于边权独立的随机图匹配的研究扩展到几何模型。具体地说，给定一个随机排列$\pi^*$在$[n]$和$n$ iid对相关高斯向量$\{X_{\pi^*（i）}，Y_i\}$在$\mathbb{R}^d$与噪声参数$\sigma$，边缘权重由$A_{ij}=\kappa（X_i，X_j）$和$B_{ij}=\kappa（Y_i，Y_j）$对于某个链接函数$\kappa$给出。目标是根据$A$和$B$的观测值恢复隐藏顶点对应$\pi^*$。在低维区域d=o（\log n）$中，我们重点研究了$\kappa（x，y）=\langle x，y \rangle$的点积模型和$\kappa（x，y）=\|x-y\|^2$的欧氏距离模型，其中潜在的几何结构是最明显的.我们得到一个近似的极大似然估计，可证明达到，以高概率，完美的恢复$\pi^*$时，$\sigma=o（n^{-2/d}）$和几乎完美的恢复与零分数的错误时，$\sigma=o（n^{-1/d}）$。此外，这些条件被证明是信息理论上最优的，即使观察到的潜在坐标$\{X_i\}$和$\{Y_i\}$，补充最近的结果[DCK 19]和[KNW 22]在几何模型的种植二分匹配问题。作为一个侧面的发现，我们证明了著名的谱算法[Ume 88]作为几何模型中最大似然的进一步近似而出现。
This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries, extending a recent line of research on random graph matching with independent edge weights to geometric models. Specifically, given a random permutation $\pi^*$ on $[n]$ and $n$ iid pairs of correlated Gaussian vectors $\{X_{\pi^*(i)}, Y_i\}$ in $\mathbb{R}^d$ with noise parameter $\sigma$, the edge weights are given by $A_{ij}=\kappa(X_i,X_j)$ and $B_{ij}=\kappa(Y_i,Y_j)$ for some link function $\kappa$. The goal is to recover the hidden vertex correspondence $\pi^*$ based on the observation of $A$ and $B$. We focus on the dot-product model with $\kappa(x,y)=\langle x, y \rangle$ and Euclidean distance model with $\kappa(x,y)=\|x-y\|^2$, in the low-dimensional regime of $d=o(\log n)$ wherein the underlying geometric structures are most evident. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $\pi^*$ when $\sigma=o(n^{-2/d})$ and almost perfect recovery with a vanishing fraction of errors when $\sigma=o(n^{-1/d})$. Furthermore, these conditions are shown to be information-theoretically optimal even when the latent coordinates $\{X_i\}$ and $\{Y_i\}$ are observed, complementing the recent results of [DCK19] and [KNW22] in geometric models of the planted bipartite matching problem. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.