Planted Matching Problem, Mehrdad Moharrami; IDS2 seminar series
From Oluwasanmi Koyejo on 10/16/2020
Abstract: We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs with n nodes. For some unknown perfect matching M*, the weight of an edge is drawn from one distribution P if the edge belongs to M* and another distribution Q otherwise. Our goal is to infer M*, exactly or approximately, from the edge weights. In this work, we take P=exp(lambda) and Q=exp(1/n), in which case the maximum-likelihood estimator of M* is the minimum-weight matching M. We obtain precise results on the overlap between M* and M, i.e., the fraction of edges they have in common. For lambda >= 4, we have almost perfect recovery, with overlap 1-o(1) with high probability. For lambda < 4, the expected overlap is an explicit function alpha(lambda) < 1: we compute it by generalizing Aldous' celebrated proof of the zeta(2) conjecture for the un-planted model, using local weak convergence to relate weighted complete bipartite graphs with n nodes to a type of weighted infinite tree, and then deriving a system of differential equations from a message-passing algorithm on this tree.