Recovery thresholds in the sparse planted matching problem

Abstract

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.

19 pages, 8 figures

References in corpus (16)

• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Shift in the velocity of a front due to a cut-off
• Front propagation into unstable states: Universal algebraic convergence towards uniformly translating pulled fronts
• Convergence in law of the minimum of a branching random walk
• A survey of max-type recursive distributional equations
• Maximum Weight Matching via Max-Product Belief Propagation
• The number of matchings in random graphs
• Core percolation in random graphs: a critical phenomena analysis
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Extremal Paths on a Random Cayley Tree
• Inference in particle tracking experiments by passing messages between images
• Typology of phase transitions in Bayesian inference problems
• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• Random-link matching problems on random regular graphs
• The Planted Matching Problem: Phase Transitions and Exact Results

Cited by in corpus (5)

• Disordered Systems Insights on Computational Hardness
• The planted $k$-factor problem
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• The planted matching problem: Sharp threshold and infinite-order phase transition
• Planted matching problems on random hypergraphs