Recent results in planted assignment problems

Abstract: Motivated by applications such as particle tracking, network de-anonymization, and computer vision, a recent thread of research is devoted to statistical models of assignment problems, in which the data are random weight graphs correlated with the latent permutation. In contrast to problems such as planted clique or stochastic block model, the major difference here is the lack of low-rank structures, which brings forth new challenges in both statistical analysis and algorithm design.

In the first half of the talk, we discuss the linear assignment problem, where the goal is to reconstruct a perfect matching planted in a randomly weighted bipartite graph, whose planted and unplanted edge weights are independently drawn from two different distributions. We determine the sharp threshold at which the optimal reconstruction error (fraction of misclassified edges) exhibits a phase transition from imperfect to perfect. Furthermore, for exponential weight distributions, this phase transition is shown to be of infinite order, confirming the conjecture of Semerjian, Sicuro, and Zdeborova. The negative result is shown by proving that, below the threshold, the posterior distribution is concentrated away from the hidden matching by constructing exponentially many long augmenting cycles.

In the second half of the talk, we discuss the quadratic assignment problem (graph matching), where the goal is to recover the hidden vertex correspondence between two edge-correlated Erdos-Renyi graphs. We prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of the vertices and below which matching any positive fraction is impossible, a phenomenon known as the “all-or-nothing” phase transition. The proof builds upon a tight characterization of the mutual information via the truncated second-moment method and an appropriate “area theorem”. Achieving these thresholds with efficient algorithms remains open.

This talk is based on joint work with Jian Ding, Jiaming Xu, Dana Yang and Sophie Yu. Preprints available at:https://arxiv.org/abs/2103.09383, https://arxiv.org/abs/2008.10097, https://arxiv.org/abs/2102.00082.

–

Bio: Yihong Wu is an associate professor in the Department of Statistics and Data Science at Yale University. He received his B.E. degree from Tsinghua University in 2006 and Ph.D. from Princeton University in 2011. He is a recipient of the NSF CAREER award in 2017 and Sloan fellowship in 2018. He is broadly interested in the theoretical and algorithmic aspects of high-dimensional statistics, information theory, and optimization.