# Supervised Community Detection with Line Graph Neural Networks

arXiv: https://arxiv.org/abs/1705.08415 · HTML: https://mlsanity.com/paper/1705.08415/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2017.

## Built on by (most cited first, 18 of 18)

- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (2024)
- [VGAER: Graph Neural Network Reconstruction based Community Detection](https://mlsanity.com/paper/2201.04066/) (2022)
- [A Comprehensive Review of Community Detection in Graphs](https://mlsanity.com/paper/2309.11798/) (2023)
- [FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classification](https://mlsanity.com/paper/2210.13815/) (2022)
- [Non-backtracking Graph Neural Networks](https://mlsanity.com/paper/2310.07430/) (2023)
- [Graph Neural Networks Intersect Probabilistic Graphical Models: A Survey](https://mlsanity.com/paper/2206.06089/) (2022)
- [A Graph Neural Network with Negative Message Passing for Graph Coloring](https://mlsanity.com/paper/2301.11164/) (2023)
- [Graph similarity learning for change-point detection in dynamic networks](https://mlsanity.com/paper/2203.15470/) (2022)
- [Table Integration in Data Lakes Unleashed: Pairwise Integrability Judgment, Integrable Set Discovery, and Multi-Tuple Conflict Resolution](https://mlsanity.com/paper/2412.00324/) (2024)
- [Fast Community Detection based on Graph Autoencoder Reconstruction](https://mlsanity.com/paper/2203.03151/) (2022)
- [One Graph to Rule them All: Using NLP and Graph Neural Networks to analyse Tolkien's Legendarium](https://mlsanity.com/paper/2210.07871/) (2022)
- [Hybrid Graph Embeddings and Louvain Algorithm for Unsupervised Community Detection](https://mlsanity.com/paper/2509.23411/) (2025)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)
- [A Graph Convolutional Neural Network based Framework for Estimating Future Citations Count of Research Articles](https://mlsanity.com/paper/2104.04939/) (2021)
- [Self-Supervised Graph Learning with Proximity-based Views and Channel Contrast](https://mlsanity.com/paper/2106.03723/) (2021)
- [Perturbation-based Graph Active Learning for Weakly-Supervised Belief Representation Learning](https://mlsanity.com/paper/2410.19176/) (2024)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)

## Abstract (arXiv)

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.