← List all talks ...

Recent results in planted assignment problems

Yihong Wu – Professor, Yale

Thu, 22-Apr-2021 / 4:30pm / Zoom: https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ

Talk

• Video

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 in [Semerjian et al. 2020]. 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.