Random Graph Matching in Geometric Models: the Case of Complete Graphs

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), Yi in ℝd with noise parameter σ, the edge weights are given by Aij=kappa(Xi,Xj) and Bij=kappa(Yi,Yj) for some link function kappa. 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 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 π^* 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 Xi and Yi 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.