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

Haoyu Wang, Yihong Wu, Jiaming Xu, Israel Yolou
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3441-3488, 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 π∗ on [n] and n iid pairs of correlated Gaussian vectors {Xπ∗(i),Yi} in \realsd with noise parameter σ, the edge weights are given by Aij=κ(Xi,Xj) and Bij=κ(Yi,Yj) 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)=‖, 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 Dai et al. (2019) and Kunisky and Niles-Weed (2022) in geometric models of the planted bipartite matching problem. As a side discovery, we show that the celebrated spectral algorithm of Umeyama (1988) emerges as a further approximation to the maximum likelihood in the geometric model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-wang22a, title = {Random Graph Matching in Geometric Models: the Case of Complete Graphs}, author = {Wang, Haoyu and Wu, Yihong and Xu, Jiaming and Yolou, Israel}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3441--3488}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/wang22a/wang22a.pdf}, url = {https://proceedings.mlr.press/v178/wang22a.html}, 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 $\pi^*$ on $[n]$ and $n$ iid pairs of correlated Gaussian vectors $\{X_{\pi^*(i)}, Y_i\}$ in $\reals^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)=⟨x, y ⟩$ 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 Dai et al. (2019) and Kunisky and Niles-Weed (2022) in geometric models of the planted bipartite matching problem. As a side discovery, we show that the celebrated spectral algorithm of Umeyama (1988) emerges as a further approximation to the maximum likelihood in the geometric model.} }
Endnote
%0 Conference Paper %T Random Graph Matching in Geometric Models: the Case of Complete Graphs %A Haoyu Wang %A Yihong Wu %A Jiaming Xu %A Israel Yolou %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-wang22a %I PMLR %P 3441--3488 %U https://proceedings.mlr.press/v178/wang22a.html %V 178 %X 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 $\reals^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)=⟨x, y ⟩$ 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 Dai et al. (2019) and Kunisky and Niles-Weed (2022) in geometric models of the planted bipartite matching problem. As a side discovery, we show that the celebrated spectral algorithm of Umeyama (1988) emerges as a further approximation to the maximum likelihood in the geometric model.
APA
Wang, H., Wu, Y., Xu, J. & Yolou, I.. (2022). Random Graph Matching in Geometric Models: the Case of Complete Graphs. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3441-3488 Available from https://proceedings.mlr.press/v178/wang22a.html.

Related Material