  Traditionally, community detection in graphs can be solved using spectral
methods or posterior inference under probabilistic graphical models. Focusing
on random graph families such as the stochastic block model, recent research
has unified both approaches and identified both statistical and computational
detection thresholds in terms of the signal-to-noise ratio. By recasting
community detection as a node-wise classification problem on graphs, we can
also study it from a learning perspective. We present a novel family of Graph
Neural Networks (GNNs) for solving community detection problems in a supervised
learning setting. We show that, in a data-driven manner and without access to
the underlying generative models, they can match or even surpass the
performance of the belief propagation algorithm on binary and multi-class
stochastic block models, which is believed to reach the computational
threshold. In particular, we propose to augment GNNs with the non-backtracking
operator defined on the line graph of edge adjacencies. Our models also achieve
good performance on real-world datasets. In addition, we perform the first
analysis of the optimization landscape of training linear GNNs for community
detection problems, demonstrating that under certain simplifications and
assumptions, the loss values at local and global minima are not far apart.
