2021/01/29 by Yihong Wu, Wu, Yihong, Jiaming Xu +3 · 8 citations
Computer Science · Mathematics · #05C60 #05C80 #62B10 #68Q87 #94A15 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Statistics Theory (math.ST) #cs.IT #math.IT #math.ST #msc:05C60 #msc:05C80 #msc:62B10 #msc:68Q87 #msc:94A15 #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.2102.00082
arxiv created 2022/02/16 · arxiv updated 2022/02/17
This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdős-Rényi model where the two graphs are subsampled from a common parent Erdős-Rényi graph G(n,p). For dense graphs with p=n-o(1), we prove that there exists 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 Erdős-Rényi graphs with p=n-Θ(1), we show that the all-or-nothing 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 Erdős-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.