Community Detection with Graph Neural Networks

By Joan Bruna, Xiang Li. 2017

87 citations recorded by the source corpus.

We study data-driven methods for community detection in graphs. This estimation problem is typically formulated in terms of the spectrum of certain operators, as well as via posterior inference under certain probabilistic graphical models. Focusing on random graph families such as the Stochastic Block Model, recent research has unified these two approaches, and identified both statistical and computational signal-to-noise detection thresholds. We embed the resulting class of algorithms within a generic family of graph neural networks and show that they can reach those detection thresholds in a purely data-driven manner, without access to the underlying generative models and with no parameter assumptions. The resulting model is also tested on real datasets, requiring less computational steps and performing significantly better than rigid parametric models.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Few-Shot Learning with Graph Neural Networks (2017, neutral): “…operations Duvenaud et al. (2015), or by generalizing the generator family to Laplacian polynomials Defferrard et al. (2016); Kipf & Welling (2016); Bruna et al. (2013), or including 2 J -th powers of A to A , A J = min(1 , A 2 J ) to encode 2 J -hop neighborhoods of each node Bruna & Li (2017).”
Attention-based Graph Neural Network for Semi-supervised Learning (2018, methodology): “There are several extensions to this model as discussed in the previous section, but this standard graph neural network has proved powerful in several problems over graphs, e.g. [9, 6, 14].”
Edge Attention-based Multi-Relational Graph Convolutional Networks (2018, unknown): “Recently Graph Convolutional Networks (GCNs) have been developed and successfully tackled tasks [29] such as matrix completion [36], manifolds analysis [31], predictions on user interest/connectivity in social network [4], extracting element representations [16, 17, 22], or generating fingerprints f”
Residual Gated Graph ConvNets (2017, background): “Finally, Bruna & Li (2017) designed a network to learn non-linear approximations of the power of graph Laplacian operators, and applied it to the unsupervised graph clustering problem.”
Mean-field theory of graph neural networks in graph partitioning (2018, background): “In fact, there have been many attempts [5, 32, 40, 41] to adopt a more complex architecture rather than A .”
Inference in Probabilistic Graphical Models by Graph Neural Networks (2018, background): “[18] also proposes spectral approximations of BP with GNNs to solve the community detection problem.”
Graph convolutional networks: a comprehensive review (2019, background): “Beyond the applications in classical problems of social science, such as community detection [42, 118], and link prediction [21, 119, 120], graph convolutional networks have been applied in many other problems.”
Universal Invariant and Equivariant Graph Neural Networks (2019, background): “However, many practical applications deal with equivariance instead, such as community detection (Bruna and Li, 2017), recommender systems (Ying et al., 2018), interaction networks of physical systems (Battaglia et al., 2016), state prediction (Sanchez-Gonzalez et al., 2018), protein interface…”
LanczosNet: Multi-Scale Deep Graph Convolutional Networks (2019, background): “Moreover, many applications have recently emerged for GNNs, including community detection [41], situation recognition [42], RGBD semantic segmentation [43], few-shot learning [21], probabilistic inference [44], continuous control of reinforcement learning [45, 46] and so on.”
A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks (2017, methodology): “However, experiments in [7] suggest that GNNs are capable of learning algorithms for community detection under the SBM essentially up to optimal thresholds, when the number of communities is small.”
Parameterized Explainer for Graph Neural Network (2020, methodology): “In the inductive setting, we select α instances for training, ( N − α ) / 2 for validation, and the rest for testing. α is ranged from [1 , 2 , 3 , 4 , 5 , 30] .”