论文标题
几何模型中的随机图匹配：完整图的情况
Random Graph Matching in Geometric Models: the Case of Complete Graphs
论文作者
论文摘要
本文研究了通过潜在几何形状相关的两个完整图与边缘重量相匹配的问题，从而将与独立边缘权重的随机图匹配的最新研究扩展到了几何模型。具体而言，给定$ [n] $上的随机排列$π^*$，以及$ n $ iid对相关的高斯矢量$ \ \ \ {x_ {x_ {π^*（i）}，y_i \} $ in $ \ mathbb {r}和$ b_ {ij} =κ（y_i，y_j）$用于某些链接函数$κ$。目标是根据观察到$ a $和$ b $的观察，恢复了隐藏的顶点$π^*$。我们专注于$κ（x，y）= \ langle x，y \ rangle $和Euclidean距离模型的DOT-Prododuct模型，其中具有$κ（x，y）= \ | x-y \ |^2 $，在低维度为$ d = o（\ log log n）$的低维度（\ | x-y \ |^2 $）。我们得出了一个近似的最大似然估计量，当$σ= o（n^{ - 2/d}）$时，它可以实现$π^*$的最佳恢复，并且在$σ= o（n^{ - 1/d}）$时消失的错误恢复，几乎是完美的恢复。此外，即使潜在的坐标$ \ {x_i \} $和$ \ {y_i \} $也被证明，这些条件在理论上是最佳的，即使在种植的bipartite匹配问题的几何模型中[dck19]和[knw22]的最新结果。作为一个侧中发现，我们表明[UME88]的著名光谱算法是与几何模型中最大似然的进一步近似。
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 $π^*$ on $[n]$ and $n$ iid pairs of correlated Gaussian vectors $\{X_{π^*(i)}, Y_i\}$ in $\mathbb{R}^d$ with noise parameter $σ$, the edge weights are given by $A_{ij}=κ(X_i,X_j)$ and $B_{ij}=κ(Y_i,Y_j)$ for some link function $κ$. The goal is to recover the hidden vertex correspondence $π^*$ based on the observation of $A$ and $B$. We focus on the dot-product model with $κ(x,y)=\langle x, y \rangle$ and Euclidean distance model with $κ(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 $π^*$ when $σ=o(n^{-2/d})$ and almost perfect recovery with a vanishing fraction of errors when $σ=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.
