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

Abstract

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 _^*(i), Y_i\ in 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)= x, y and Euclidean distance model with (x,y)=\|x-y\|^2, in the low-dimensional regime of d=o( 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 _i\ and _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.

Tasks

Reproductions