Sharp thresholds in inference of planted subgraphs
From MaRDI portal
(Redirected from Publication:6427952)
Sharp thresholds in inference of planted subgraphs (scientific article; zbMATH DE number 900581902)
Sharp thresholds in inference of planted subgraphs (scientific article; zbMATH DE number 900581902)
Abstract: A major question in the study of the ErdH{o}s--R'enyi random graph is to understand the probability that it contains a given subgraph. This study originated in classical work of ErdH{o}s and R'enyi (1960). More recent work studies this question both in building a general theory of sharp versus coarse transitions (Friedgut and Bourgain 1999; Hatami, 2012) and in results on the location of the transition (Kahn and Kalai, 2007; Talagrand, 2010; Frankston, Kahn, Narayanan, Park, 2019; Park and Pham, 2022). In inference problems, one often studies the optimal accuracy of inference as a function of the amount of noise. In a variety of sparse recovery problems, an ``all-or-nothing (AoN) phenomenon has been observed: Informally, as the amount of noise is gradually increased, at some critical threshold the inference problem undergoes a sharp jump from near-perfect recovery to near-zero accuracy (Gamarnik and Zadik, 2017; Reeves, Xu, Zadik, 2021). We can regard AoN as the natural inference analogue of the sharp threshold phenomenon in random graphs. In contrast with the general theory developed for sharp thresholds of random graph properties, the AoN phenomenon has only been studied so far in specific inference settings. In this paper we study the general problem of inferring a graph planted in an ErdH{o}s--R'enyi random graph, thus naturally connecting the two lines of research mentioned above. We show that questions of AoN are closely connected to first moment thresholds, and to a generalization of the so-called Kahn--Kalai expectation threshold that scans over subgraphs of of edge density at least . In a variety of settings we characterize AoN, by showing that AoN occurs if and only if this ``generalized expectation threshold is roughly constant in . Our proofs combine techniques from random graph theory and Bayesian inference.
This page was built for publication: Sharp thresholds in inference of planted subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6427952)
