In recent times the cavity method, a statistical physics-inspired heuristic, has been successful in conjecturing computational thresholds that have been rigorously confirmed -- such as for community detection in the sparse regime of the stochastic block model  . Inspired by this, we investigate the predictions made by the cavity method for the algorithmic problemsof detecting and recovering a planted signal in a general model of sparse random graphs. The model we study generalizes the well-understood case of the stochastic block model, the less well understood case of random constraint satisfaction problems with planted assignments, as well as "semi-supervised" variants of these models. Our results include: (i) a conjecture about a precise criterion for when the problems of detection and recovery should be algorithmically tractable arising from a heuristic analysis of when a particular fixed point of the belief propagation algorithm is stable; (ii) a rigorous polynomial-time algorithm for the problem of detection: distinguishing a graph with a planted signal from one without; ( iii) a rigorous polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the planted signal significantly better than a random guess would . The rigorous algorithms are based on the spectra of matrices that arise as the derivatives of the belief propagation update rule. An interesting unanswered question raised is that of obtaining evidence of computational hardness for convex relaxations whenever hardness is predicted by the cavity method .
Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfaction problem such as planted 3-SAT, the clauses are sparse observations from which the hidden assignment is to be recovered. In the problem of community detection in a stochastic block model , the community labels are hidden variables that are to be recovered from the edges of the graph . Inspired by ideas from statistical physics, the presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a general model of statistical inference problems that includes both community detection in stochastic block models, and all planted constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where detection and recovery should be algorithmically tractable . At precisely the predicted tractable regime, we give: (i) a general polynomial-time algorithm for the problem of detection: distinguishing an input with a planted signal from one without; ( ii) a general polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the hidden assignment significantly better than a random guess would .
R
In recent times the cavity method, a statistical physics-inspired heuristic, has been successful in conjecturing computational thresholds that have been rigorously confirmed -- such as for community detection in the sparse regime of the
Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfaction problem such as planted 3-SAT, the clauses are sparse observations from which the hidden assignment is to be recovered. In the problem of community detection in a
A
, the community labels are hidden variables that are to be recovered from the edges of the graph
R
this, we investigate the predictions made by the cavity method for
ideas from statistical physics,
R
algorithmic problemsof detecting and recovering a planted signal in a
presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a
R
sparse random graphs. The model we study generalizes the well-understood case of the stochastic block model, the less well understood case of random
statistical inference problems that includes both community detection in stochastic block models, and all planted
R
with planted assignments, as well as "semi-supervised" variants of these models. Our results include: (i) a conjecture about a precise criterion for when the problems of
as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where
R
arising from a heuristic analysis of when a particular fixed point of the belief propagation algorithm is stable; (ii) a rigorous
. At precisely the predicted tractable regime, we give: (i) a general
R
a graph
an input
R
iii) a rigorous
ii) a general
R
planted signal
hidden assignment
D
. The rigorous algorithms are based on the spectra of matrices that arise as the derivatives of the belief propagation update rule. An interesting unanswered question raised is that of obtaining evidence of computational hardness for convex relaxations whenever hardness is predicted by the cavity method