Settling the Sharp Reconstruction Thresholds of Random Graph Matching

This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated ran3 dom graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdos-Rényi model where the two graphs are subsampled from a common parent Erdos-Rényi graph G(n, p). For dense Erdos-Rényi graphs with p = n-o(1), we prove that there exists 7 a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the "all-or-nothing"phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse Erdos-Rényi graphs with p = n -(1), we show that the all-or-nothing 14 phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in Erdos-Rényi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated second-moment computation and an "area theorem"that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges.

Duke Scholars

Author Jiaming Xu Fuqua School of Business