Matching Correlated Random Geometric Graphs

Shuangping Li (Yale University) https://simons.berkeley.edu/talks/shuangping-li-yale-university-2026-10-15 Probabilistic Phenomena on Graphs, Groups, and Manifolds We study graph matching for two correlated random geometric graphs whose vertex labels have been permuted. The graphs are generated from correlated latent points on the high-dimensional sphere, with edges determined by thresholded inner products. We give a polynomial time algorithm that can achieve exact recovery of the hidden matching for any fixed positive correlation. We also characterize the information-theoretic threshold for exact recovery, up to constant factors, over a broad range of dimensions. This is based on joint work with Dong Huang, Ankang Jiao, and Zhangsong Li.