MATCHING RECOVERY THRESHOLD FOR CORRELATED RANDOM GRAPHS

For two correlated graphs which are independently sub-sampled from a common Erdos-Renyi graph G(n, p) , we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p = n-alpha +o(1) for alpha E (0 , 1] , we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.

Automated summary

This paper focuses on recovering the latent vertex matching of two correlated graphs which are independently sub-sampled from a common Erdos-Renyi graph G(n, p) without labels. A sharp information-theoretic threshold is established to determine the possibility of correctly matching a positive fraction of vertices, when p = n-alpha +o(1) for alpha E (0, 1]. Our result improves a constant factor in a recent work by Wu, Xu and Yu.