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

Authors Haoyu Wang, Yihong Wu, Jiaming Xu, Israel Yolou

Publication date 21 February 2022

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

p i^{*}

on

[n]

and

n

iid pairs of correlated Gaussian vectors

X_{p i^{*} (i)}, Y_{i}

in

m a t h b b R^{d}

with noise parameter

s i g m a

, the edge weights are given by

A_{i j} = k a p p a (X_{i}, X_{j})

and

B_{i j} = k a p p a (Y_{i}, Y_{j})

for some link function

k a p p a

. The goal is to recover the hidden vertex correspondence

p i^{*}

based on the observation of

A

and

B

. We focus on the dot-product model with

k a p p a (x, y) = l a n g l e x, y a n g l e

and Euclidean distance model with

k a p p a (x, y) = | x - y |^{2}

, in the low-dimensional regime of

d = o (l o g 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

p i^{*}

when

s i g m a = o (n^{- 2 / d})

and almost perfect recovery with a vanishing fraction of errors when

s i g m a = 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.

This page was built for publication: Random Graph Matching in Geometric Models: the Case of Complete Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391799)