  The stochastic block model is a canonical model of communities in random
graphs. It was introduced in the social sciences and statistics as a model of
communities, and in theoretical computer science as an average case model for
graph partitioning problems under the name of the ``planted partition model.''
Given a sparse stochastic block model, the two standard inference tasks are:
(i) Weak recovery: can we estimate the communities with non trivial overlap
with the true communities? (ii) Detection/Hypothesis testing: can we
distinguish if the sample was drawn from the block model or from a random graph
with no community structure with probability tending to $1$ as the graph size
tends to infinity?
  In this work, we show that for sparse stochastic block models, the two
inference tasks are equivalent except at a critical point. That is, weak
recovery is information theoretically possible if and only if detection is
possible. We thus find a strong connection between these two notions of
inference for the model. We further prove that when detection is impossible, an
explicit hypothesis test based on low degree polynomials in the adjacency
matrix of the observed graph achieves the optimal statistical power. This low
degree test is efficient as opposed to the likelihood ratio test, which is not
known to be efficient. Moreover, we prove that the asymptotic mutual
information between the observed network and the community structure exhibits a
phase transition at the weak recovery threshold.
  Our results are proven in much broader settings including the hypergraph
stochastic block models and general planted factor graphs. In these settings we
prove that the impossibility of weak recovery implies contiguity and provide a
condition which guarantees the equivalence of weak recovery and detection.
