Supervised Community Detection with Line Graph Neural Networks

Abstract

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.

Published at International Conference on Learning Representations (ICLR 2019)

References in corpus (6)

• Modularity and community structure in networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Message Passing for Quantum Chemistry
• Interaction Networks for Learning about Objects, Relations and Physics
• Covariant Compositional Networks For Learning Graphs
• Are ResNets Provably Better than Linear Predictors?

Cited by in corpus (23)

• Recent Advances and Applications of Deep Learning Methods in Materials Science
• Atomistic Line Graph Neural Network for Improved Materials Property Predictions
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Scaling Graph Neural Networks with Approximate PageRank
• Examining COVID-19 Forecasting using Spatio-Temporal Graph Neural Networks
• Continuous Influence-based Community Partition for Social Networks
• On Explainability of Graph Neural Networks via Subgraph Explorations
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• Generalization and Representational Limits of Graph Neural Networks
• Graph neural network initialisation of quantum approximate optimisation
• Recent progress in the JARVIS infrastructure for next-generation data-driven materials design
• Beyond Graph Neural Networks with Lifted Relational Neural Networks
• BatmanNet: Bi-branch Masked Graph Transformer Autoencoder for Molecular Representation
• LineMVGNN: Anti-Money Laundering with Line-Graph-Assisted Multi-View Graph Neural Networks
• Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation
• On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs
• On Graph Neural Networks versus Graph-Augmented MLPs
• Mask-GVAE: Blind Denoising Graphs via Partition
• Boosting Multitask Learning on Graphs through Higher-Order Task Affinities
• Stability and Generalization of Hypergraph Collaborative Networks
• Interferometric Graph Transform for Community Labeling
• New Insights into Graph Convolutional Networks using Neural Tangent Kernels