SUPERVISED COMMUNITY DETECTION WITH LINE GRAPH NEURAL NETWORKS
Community detection in graphs can be solved via spectral methods or posterior inference under certain 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 multiclass stochastic block models, which is believed to reach the computational threshold in these cases. In particular, we propose to augment GNNs with the non-backtracking operator defined on the line graph of edge adjacencies. The GNNs are achieved good performance on real-world datasets. In addition, we perform the first analysis of the optimization landscape of using (linear) GNNs to solve community detection problems, demonstrating that under certain simplifications and assumptions, the loss value at any local minimum is close to the loss value at the global minimum/minima.
This paper presents a study of the community detection problem via graph neural networks. The presented results open the possibility that neural networks are able to discover the optimal algorithm for a given task. This is rather convincingly demonstrated on the example of the stochastic block model, where the optimal performance is known (for 2 symmetric groups) or strongly conjectured (for more groups). The method is rather computationally demanding, and also somewhat unrealistic in the aspect that the training examples might not be available, but for a pioneering study of this kind this is well acceptable.
Despite my overall very positive opinion, I found a couple of claims that are misleading and overall hurt the quality of the paper, and I would strongly suggest to the authors to adjust these claims:
** The method is claimed to "even improve upon current computational thresholds in hard regimes." This is misleading, because (as correctly stated in the body of the paper) the computational threshold to which the paper refers apply in the limit of large graph sizes whereas the observed improvements are for finite sizes. It is shown here that for finite sizes the present method is better than belief propagation. But this clearly does not imply that it improves the conjectured computational thresholds that are asymptotic. At best this is an interesting hypothesis for future work, not more. 
** The energy landscape is analyzed "under certain simplifications and assumptions". Conclusions state "an interesting transition from rugged to simple as the size of the graphs increase under appropriate concentration conditions." This is very vague. It would be great if the paper could offer intuitive explanation of there simplifications and assumptions that is between these unclear remarks and the full statement of the theorem and the proof that I did not find simple to understand. For instance state the intuition on in which region of parameters are those results true and in which they are not. 
** "multilinear fully connected neural networks whose landscape is well understood (Kawaguchi, 2016)." this is in my opinion grossly overstated. While surely that paper presents interesting results, they are set in a regime that lets a lot to be still understood about landscape of fully connected neural networks. It is restricted to specific activation functions, and the results for non-linear networks rely on unjustified simplifications, the sample complexity trade-off is not considered, etc. 
Misprint: Page 2: cetain -> certain.