Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
This provides theoretical evidence of computational barriers in inference tasks for random graph models, addressing incremental problems in statistical physics and machine learning.
The paper tackles computational hardness for matching recovery in sparse correlated Erdős-Rényi graphs and detection in correlated sparse stochastic block models, assuming a strengthened low-degree conjecture, solving open problems from prior work.
In this paper, assuming a natural strengthening of the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdős-Rényi graphs $\mathcal G(n,q;ρ)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $ρ<\sqrtα$ lies below the Otter's threshold, solving a remaining problem in \cite{DDL23+}; (2) the detection problem between the correlated sparse stochastic block model $\mathcal S(n,\tfracλ{n};k,ε;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n};k,ε)$ when $ε^2 λs<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrtα$ lies below the Otter's threshold, solving a remaining problem in \cite{CDGL24+}. One of the main ingredient in our proof is to derive certain forms of \emph{algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{P}$ and $\mathbb{Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{P}(\mathcal A(\mathsf Y)=1)=Ω(1)$. This framework provides a useful tool for performing reductions between different inference tasks.