Computational phase transitions in sparse planted problems?
share
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 problems of 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.
READ FULL TEXT