| Paper ID | D6-S4-T3.2 |
| Paper Title |
Settling the Sharp Reconstruction Thresholds of Random Graph Matching |
| Authors |
Yihong Wu, Yale University, United States; Jiaming Xu, Sophie H. Yu, Duke University, United States |
| Session |
D6-S4-T3: Graphs |
| Chaired Session: |
Monday, 19 July, 23:00 - 23:20 |
| Engagement Session: |
Monday, 19 July, 23:20 - 23:40 |
| Abstract |
This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian setting where the two graphs are complete graphs with correlated Gaussian weights and the Erdős–Rényi graph setting 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^{-\Theta(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.
|
