Random graph matching: fundamental limits and efficient algorithms
Sophie H. Yu
Abstract:
This poster focuses on the detection and recovery problems of matching two Erdos-Renyi random graphs. Specifically, for detection, we aim to decide whether the two observed graphs are independent, or edge-correlated under some latent node correspondence. For recovery, our goal is to recover the latent node correspondence given the two graphs are edge-correlated. In the dense graph regime, we prove that both detection and recovery exhibit an “all-or-nothing” phase transition at a sharp threshold. For sparse graphs, we identify the information-theoretic threshold within some constant factor. Meanwhile, we propose new algorithms for both detection and recovery problems based on counting the co-occurrences of signed trees for a family of non-isomorphic trees. Our algorithms significantly improve the prior work in terms of statistical accuracy, running time, and graph sparsity.
This poster is a summary of our recent papers accepted to Annals of applied probability and IEEE transaction on Information Theory, and a newly submitted paper to Annals of statistics.