The planted matching problem: sharp threshold and infinite-order phase transition

DOI10.1007/S00440-023-01208-6MaRDI QIDQ6095833zbMATH OpenFDO

Authors Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang

Publication date 8 September 2023

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.09383

zbMATH Keywords

Bhattacharyya coefficientinformation-theoretic thresholdlinear assignmentphase transitionplanted matching recovery

Mathematics Subject Classification ID

Combinatorial probability (60C05) Information theory (general) (94A15)

Abstract: We study the problem of reconstructing a perfect matching $M^{\ast }$ hidden in a randomly weighted $nimesn$ bipartite graph. The edge set includes every node pair in $M^{\ast }$ and each of the $n(n-1)$ node pairs not in $M^{\ast }$ independently with probability $d/n$. The weight of each edge $e$ is independently drawn from the distribution $mathcalP$ if $ein{M}^{\ast }$ and from $mathcalQ$ if $eotin{M}^{\ast }$. We show that if $sqrtdB(mathcalP,mathcalQ)le1$, where $B(mathcalP,mathcalQ)$ stands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator of $M^{\ast }$ converges to $0$ as $noinfty$. Conversely, if $sqrtdB(mathcalP,mathcalQ)ge1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$ under both the sparse and dense model, resolving the conjecture in [Moharrami et al. 2019, Semerjian et al. 2020]. Furthermore, in the special case of complete exponentially weighted graph with $d=n$, $mathcalP=exp(lambda)$, and $mathcalQ=exp(1/n)$, for which the sharp threshold simplifies to $lambda=4$, we prove that when $lambdale4-epsilon$, the optimal reconstruction error is $expleft(-Theta(1/sqrtepsilon)ight)$, confirming the conjectured infinite-order phase transition in [Semerjian et al. 2020].

Recommendations

• The planted matching problem: phase transitions and exact results
• The planted k-factor problem
• Matching recovery threshold for correlated random graphs
• Reconstruction and estimation in the planted partition model
• A proof of the block model threshold conjecture

Cites work

• A proof of Parisi's conjecture on the random assignment problem
• A Remark on Stirling's Formula
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs
• Hidden Hamiltonian cycle recovery via linear programming
• scientific article; zbMATH DE number 4043612 (Why is no real title available?)
• scientific article; zbMATH DE number 3103174 (Why is no real title available?)
• Information Limits for Recovering a Hidden Community
• Introduction to Random Graphs
• Long paths and Hamiltonicity in random graphs
• On the Expected Value of a Random Assignment Problem
• On the number of circuits in random graphs
• Percolation of averages in the stochastic mean field model: the near-supercritical regime
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Random graph dynamics
• Scaling window for mean-field percolation of averages
• The (2) limit in the random assignment problem
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The planted k-factor problem
• The planted matching problem: phase transitions and exact results
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(10)

• The planted matching problem: phase transitions and exact results
• scientific article; zbMATH DE number 2084722 (Why is no real title available?)
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Matching recovery threshold for correlated random graphs
• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein
• Counting stars is constant-degree optimal for detecting any planted subgraph
• Sharp thresholds in inference of planted subgraphs
• Low coordinate degree algorithms. I: Universality of computational thresholds for hypothesis testing
• Finding planted cycles in a random graph
• Geometric planted matchings beyond the Gaussian model

This page was built for publication: The planted matching problem: sharp threshold and infinite-order phase transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095833)