Recovery thresholds in the sparse planted matching problem

TY - JOUR

T1 - Recovery thresholds in the sparse planted matching problem

AU - Semerjian, Guilhem

AU - Sicuro, Gabriele

AU - Zdeborová, Lenka

PY - 2020/8/6

Y1 - 2020/8/6

N2 - We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial-recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.

AB - We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial-recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.

U2 - 10.1103/PhysRevE.102.022304

DO - 10.1103/PhysRevE.102.022304

M3 - Article

SN - 2470-0045

VL - 102

JO - Physical Review E

JF - Physical Review E

IS - 2

ER -