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.
 Graph Neural Networks(GNN) are gaining traction and generating a lot of interest. In this work, the authors apply them to the community detection problem, and in particular to graphs generated from the stochastic block model. The main new contribution here is called "line graph neural network" that operate directly over the edges of the graph, using efficiently the power of the "non backtracking operator" as a spectral method for such problems. Training such GNN on data generated from the stochastic block model and other graph generating models, the authors shows that the resulting method can be competitive on both artificial and real datasets. This is definitely an interesting idea, and a nice contribution to GNN, that should be of interest to ICML folks. References and citations are fine for the most part, except for one very odd exception concerning one of the main object of the paper: the non-backtracking operator itself! While discussed in many places, no references whatsoever are given for its origin in detection problems. I believe this is due to (Krzakala et al, 2013) ---a paper cited for other reasons--- and given the importance of the non-backtracking operator for this paper, this should be acknowledged explicitly. Pro: Interesting new idea for GNN, that lead to more powerful method and open exciting direction of research. A nice theoretical analysis of the landscape of the graph. Con:The evidence provided in Table 1 is rather weak. The hard phase is defined in terms of computational complexity (polynomial vs exponential) and therefore require tests on many different sizes.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
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.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



 Graph Neural Networks(GNN) are gaining traction and generating a lot of interest. In this work, the authors apply them to the community detection problem, and in particular to graphs generated from the stochastic block model. The main new contribution here is called "line graph neural network" that operate directly over the edges of the graph, using efficiently the power of the "non backtracking operator" as a spectral method for such problems. Training such GNN on data generated from the stochastic block model and other graph generating models, the authors shows that the resulting method can be competitive on both artificial and real datasets. This is definitely an interesting idea, and a nice contribution to GNN, that should be of interest to ICML folks. References and citations are fine for the most part, except for one very odd exception concerning one of the main object of the paper: the non-backtracking operator itself! While discussed in many places, no references whatsoever are given for its origin in detection problems. I believe this is due to (Krzakala et al, 2013) ---a paper cited for other reasons--- and given the importance of the non-backtracking operator for this paper, this should be acknowledged explicitly. Pro: Interesting new idea for GNN, that lead to more powerful method and open exciting direction of research. A nice theoretical analysis of the landscape of the graph. Con:The evidence provided in Table 1 is rather weak. The hard phase is defined in terms of computational complexity (polynomial vs exponential) and therefore require tests on many different sizes.
assistant
 Graph Neural Networks(GNN) are gaining traction and generating a lot of interest. In this work, the authors apply them to the community detection problem, and in particular to graphs generated from the stochastic block model. The main new contribution here is called "line graph neural network" that operate directly over the edges of the graph, using efficiently the power of the "non backtracking operator" as a spectral method for such problems. Training such GNN on data generated from the stochastic block model and other graph generating models, the authors shows that the resulting method can be competitive on both artificial and real datasets. This is definitely an interesting idea, and a nice contribution to GNN, that should be of interest to ICML folks. References and citations are fine for the most part, except for one very odd exception concerning one of the main object of the paper: the non-backtracking operator itself! While discussed in many places, no references whatsoever are given for its origin in detection problems. I believe this is due to (Krzakala et al, 2013) ---a paper cited for other reasons--- and given the importance of the non-backtracking operator for this paper, this should be acknowledged explicitly. Pro: Interesting new idea for GNN, that lead to more powerful method and open exciting direction of research. A nice theoretical analysis of the landscape of the graph. Con:The evidence provided in Table 1 is rather weak. The hard phase is defined in terms of computational complexity (polynomial vs exponential) and therefore require tests on many different sizes.