Community-Centric Graph Convolutional Network for Unsupervised Community Detection

1 Introduction

Real-world systems often appear in the form of networks. Examples include social networks, power grid and world trade networks. Real networks have modular structures or communities [Fortunato, 2010], which are densely connected subgraphs with nodes of close relationships and similar properties. Identification of network modular structures is an effective means to understanding the underlying organizational principles and functions of the system that the network represents. Community detection has been an active area of research, as surveyed in [Falih et al., 2018; Fortunato, 2010;

∗Corresponding author.

Fortunato and Hric, 2016], and many community detection methods have been proposed, including that based on statistical modeling [Chen et al., 2018], modularity optimization [Yang et al., 2016], matrix factorization [Wang et al., 2017].

Deep learning has recently been adopted in network analysis [Kipf and Welling, 2017; Yang et al., 2016; Jin et al., 2018; Monti et al., 2018; Pan et al., 2018]. In particular, Graph Convolutional Networks (GCN) has attracted a great deal of attention lately due to its success on supervised and semi-supervised classification of nodes in a graph [Li et al., 2018; Kipf and Welling, 2017] which can be adopted for community detection. Of particular relevance to the current study is MRFasGCN [Jin et al., 2019], a state-of-the-art GCNbased semi-supervised community detection method, which incorporates a Markov Random Fields (MRF) modeling of communities in the GCN framework.

Community detection is in essence an unsupervised learning problem. Real-world networks are typically unique - the training data from one network can be hardly used adequately for another network. As a corollary to this observation, when finding communities in a network, the only data available for analysis are the information on the network itself. A scheme of semi-supervised learning, such as the MRFasGCN method, can apply in such a way that partial label information on some of the nodes in a given network can be used to predict the community identities of the remaining unlabeled nodes in the same network. However, for most application problems, even such partial training data are costly and arduous to gather.

Therefore, to advance the state-of-the-art of community detection, it is of great technical significance and paramount practical importance to develop GCN-based algorithm for unsupervised community detection by exploiting the great power of automatic feature learning and effective optimization that deep learning can offer. It also remains to be seen if an end-to-end deep learning approach can outperform the existing methods that use statistical methods and other machine learning techniques for community finding.

We developed a novel GCN-based approach for Unsupervised Community Detection in attribute networks, referred to as GUCD. In this method, we incorporated network modeling method of MRFasGCN in the Autoencoder framework and introduced a special neural network architecture suitable for learning network communities and node semantics at the same time. We further introduced a local enhancement to the latent communities, i.e. we first constructed an aggregated graph combining the information of both topology and attributes, and then made each pair of connected nodes in this graph have similar community distributions. We conducted experiments on some real networks to compare the new approach with the best existing methods and analyzed the features of the new approach. To our best knowledge, GUCD is the first GCN method for unsupervised community finding.

2 Preliminaries

We first introduce some notations and define the problem of community detection, and then discuss MRFasGCN [Jin et al., 2019] (a GCN based semi-supervised community detection method) which serve as the bases of our new approach.

2.1 Notations and ProblemDefinition

An undirected and attributed network is represented as a graph G = (V,E,W) over a set of n nodes V = {v1, v2, . . . , vn}, a set of e edges E with eij = (vi, vj) ∈ E if an edge exists between nodes vi and vj , and a set of m node attributes W = {w1, . . . wm}. The topological structure of G is represented by an n × n adjacency matrix A = (aij)n×n , where aij = 1 if eij ∈ E, or 0 otherwise. An n × m attribute matrix X is used to denote the attributes of nodes, where xit = 1 if a node has attribute wt, or 0 otherwise.

Given an attribute network G, community detection is to partition the n nodes into K communities C = {C1,C2, . . . ,CK} so that each node vi has a community identity or label ci ∈ L = {1, 2, . . . , K}.

2.2 MRFasGCN

MRFasGCN [Jin et al., 2019] infers a partition of nodes in a network in two main parts. First, they take the original two convolutional layers of GCN [Kipf and Welling, 2017], that is

as the first two layers of the neural network to infer an initial assignment of node labels (X(2) ), where ˆ A = ˜D-1/2 ˜ A ˜D-1/2 ( ˜ A = A + In and ˜D is a diagonal matrix with ˜ dii = ∑j ˜aij) captures network topology, X is the attribute matrix, and H(0) and H(1) are weight parameters of the two convolutional layers to be trained.

MRFasGCN then incorporates a community-oriented MRF as the third convolutional layer in the GCN. The central piece of this MRF model is an energy function, E(C|A,X), with two parts: the sum of unary potentials over all nodes and the sum of pairwise potentials over all edges:

where α is a parameter for balancing the unary and pairwise potentials. The unary potential φu (ci) = -p (ci) measures the cost for node vi taking label ci, where p (ci) = x(2) i,ci is the probability that vi has label ci, derived fromGCN in Eq. (1). The pairwise potential φp (ci, cj) = µ (ci, cj) τ (vi, vj) measures the cost for assigning labels ci and cj to nodes vi and vj , where µ (ci, cj ) denotes the semantic similarities between communities ci and cj, and τ (vi, vj) the attribute similarity or consistency between nodes vi and vj , defined as:

where h(2) cicj is the parameter to be learned, δ (ci, cj) = 1 if ci = cj, or 0 otherwise, ξ (vi, vj) = didj/2e - aij (di is the degree of node vi and e the number of edges), and β is a tradeoff parameter that balances topology and attributes. ζ (vi, vj) is defined by using the cosine similarity between the attribute vectors of nodes vi and vj, and then an asymmetric regularization is used to balance the difference of the sum of similarity on every node, i.e., Ri (ζ (vi, vj)) = ζ (vi, vj) / ∑nt=1 ζ (vi, vt).

However, minimizing the above energy function in order to yield the most probable community partition for a given network is intractable, since the pairwise potentials are defined over a complete graph rather than the sparse network. Thus, a mean filed approximation is adopted to approximate the exact distribution P(C|A,X). The updating procedure for this approximation has four steps 1) initialization, 2) message passing, 3) adding unary potentials and 4) normalization. Following these steps, MRFasGCN can transform the MRF's inference into a layer of convolutional process (that is compatible with GCN of Eq. (1)), defined as:

where Υ = (τ (vi, vj))n×n is defined in Eq. (4), H(2) are the weight parameters to be trained, and Z = (zici )n×K the final community membership of nodes (where zici denotes the probability that node vi belongs to community ci).

3 The Method

After a brief overview of our new method, we will introduce an encoder based on MRFasGCN to derive node community memberships and a dual decoder for reconstructing links and attributes based on communities. We then discuss a regularization to enhance community detection locally.

3.1 Overview

The new GCN-based approach for Unsupervised Community Detection, short-handed as GUCD, adopts Autoencoder as its overall architecture and includes three main parts (Fig. 1). In the first part (the green box to the left of Fig. 1), we adopted the three convolutional layers of MRFasGCN as the encoder of GUCD, where the first two layers were to learn a deep representation of the attribute network and the third layer was to model and derive node community membership using both the deep representation and network information. We then designed a dual decoder as the second part of GUCD (the red box to the right of Fig. 1), using the derived communities to separately reconstruct network topology and node attributes.

We first reconstructed the network topology by requiring the nodes within the same community to maintain the same link pattern (with also considering the heterogeneity of node degrees) connecting to the rest of the network, which is suitable for generating the coupling relationships between nodes. We then generated node contents using topic modelling, i.e. we assumed that the contents of nodes in the same community share similar distributions of attribute words used. We formulated the dual decoder to fully utilize (structural and content) data from diverse sources, making the decoding process suitable for unsupervised community detection. In the third part (in purple box in the middle of Fig. 1), we added a regularization of local enhancement to the latent communities, i.e. we first constructed an aggregated graph combining the information of both topology and attributes, and then made each pair of connected nodes in this graph have similar community distributions. The model was trained as a whole using the Adam optimizer [Kingma and Ba, 2015].

3.2 The Shared Encoder

We processed the network topology and node attributes together using the same encoder so as to extract hidden network characteristics, particularly latent community structures to be identified. To be specific, we adopted the three convolutional layers of MRFasGCN [Jin et al., 2019] as the encoder (the green box of Fig. 1). We used the first two layers to derive a general embedding and then derived an initial node community labels X(2) (defined in Eq. (1)) by using softmax on the embedding, which is not community-specific. We used this initial solution X(2) to define unary potentials in MRF, and then defined pairwise potentials of MRF to model communities Z (defined in Eq. (5)) hidden in network topology and attributes, leading to the third convolutional layer. Through these three layers, the derived node community labels Z not only utilize the deep representation but also are smoothly community-oriented. The node to community assignments in Z will be learned when the whole model with encoder and decoder is trained together; the high quality of the reconstructed network will require an accurate community structure at the end of the encoder.

3.3 The Dual Decoder

The dual decoder is the core part of the new method. It consists of two decoders, one for reconstructing network topology and the other for reconstructing node attributes.

The Decoder for Reconstructing Network Topology

This novel decoder attempts to reconstruct network topology based on the node community membership derived in the latent space. It not only makes the decoder communityoriented, but also achieves unsupervised learning for community detection. The idea is inspired by the block model for blocks, groups, or communities in networks. That is, if the community which a node vi belongs to is denoted as ci (ci = 1, 2, . . . , K), we can then define a K ×K block matrix Θ such that each element θrs in the matrix is the possibility of having an edge between any two nodes vi and vj (with ci = r and cj = s). In this case, the nodes in each of the K communities (with label r) have the same link pattern, i.e., the nodes in the same community share the same link probability with any node vj in the network, i.e. θrcj . This idea naturally describes the coupling relationship between nodes in the network since it is defined to generate pairwise rather than individuals based on community structure. The model is further improved by considering the heterogeneity of node degrees, i.e. the nodes with higher degrees should be more likely to be connected. Therefore, the model can be revised such that the possibility that nodes vi and vj are connected is didjθcicj , where di is the degree of vi. This mechanism is in concordance with the degree-corrected stochastic block model (DCSBM) [Karrer and Newman, 2011] even though the formulation is different.

Based on the above model, the expected number of links between nodes vi and vj, which respectively belong to communities ci and cj , can be written as

where zici is the probability that vi belongs to community ci, which is from the encoder, defined in Eq. (5). Considering all communities {(ci, cj) |ci, cj ∈ L}, we can then define the expected number of links between nodes vi and vj as:

By considering both the block modelling and heterogeneity degree of nodes, the model can well describe the coupling relationship among nodes in the network with community structures. The above model can be formulated as a layer of a neural network in order to incorporate it into the Autoencoder framework. As the K-dimensional vector ⃗zi = (zici )1×K denotes the probability distribution of vi belonging to different communities, the link propensity between nodes vi and vj can be revised to ai,j = sigmoid (di (⃗ziΘ⃗zT j ) dj ), which can also be written in a matrix form as:

where D = diag (d1, d2, · · · , dn). Taking Θ as the weight parameters of the neural network, Eq. (8) can then be represented by a layer of the neural network, i.e., the topological decoder. The parameters Θ can be learned by minimizing the difference between the observed adjacency matrix A and the adjacency matrix A generated from the model. This difference can be defined by using the cross-entropy loss as:

The Decoder for Reconstructing Attributes

Reconstruction of node attributes stems in topic modelling [Blei et al., 2003]. Nodes with similar semantic attributes are believed to be more likely to belong to the same community. Thus, the nodes in the same community are more likely to have similar distributions of attribute words, and different communities in a network can be characterized as representing different semantic topics.

Let P(ci|vi) = zici be the probability that node vi belongs to community ci, where Z = (zici )n×K is the matrix of node community memberships from the encoder; and P(xit = 1|ci = k) = bkt the probability that the kth (ci = k) community/topic selects an attribute word wt from the entire word set wt ∈ W, where B = (bkt)K×m is to be learned. Assume that every node-attribute pair 〈vi,wt〉 in the context (with xit = 1) is generated independently. Then, given the community ci of node vi, the probability for a node-attribute pair 〈vi, wt〉 generated will be:

Considering all communities, the probability that 〈vi,wt〉 appears in the context will be:

The above generative process can be formulated as a layer of neural network to serve as an attributed decoder. Using X = (xit)n×m, the matrix form of the above model is:

where B denotes the weight parameters in this neural network layer to be trained. Then, the likelihood that the attribute matrix X is generated by the above model is:

where xit = 1 if node vi (vi ∈ V ) has attribute wt, or 0 otherwise. Since the objective of the network generative process is to maximize this likelihood, the negative log-likelihood is then taken as the loss of this layer of the neural network,

3.4 Local Enhancement

Different from the main model (e.g. theMRF part) which describes communities via global information, we further utilize local information to enhance communities from a local view. The rationale is that two nodes should have similar node community membership if they are close to each other, topologically and/or semantically, in the attribute network.

We implemented this local enhancement scheme by introducing pairwise constraints on nodes and a graph regularization term to the objective function. We first built an aggregated graph based on network topology and node attributes. To measure the proximity of a pair of nodes, we introduced a measurement method to combine their topological and attribute similarities. We computed the set of the local neighbors for each node vi, i.e.,

where Γtopo i is the set of neighbors directly adjacent to vi, and Γattr i the set of top-kattr most attribute-similar neighbors of vi, where the TF-IDF cosine similarity is used to calculate the attribute similarity of nodes. That is, let ⃗xi be the attribute vector of node vi, then for attribute unit xit, its TF-IDF value in a term vector ⃗xi is:

The cosine similarity of attributes between nodes vi and vj is then defined as:

Thereafter, we added weights to the aggregated graph. We calculated the proximity between a node and its direct neighbors in this new graph using:

where Stopo = [stopo ij ] (stopo ij = cosine (⃗ai,⃗aj)) and Sattr = [sattr ij ] (sattr ij = cosine (⃗xi, ⃗xj)) are respectively the topological and attribute similarities between node vi and its direct neighbor vj ∈ Γi, λ is a tradeoff parameter, and zero-one(·) plays the role of normalization defined as:

Given the similarity matrix S of the aggregated graph, we defined the pairwise constraint as:

where Ψ = F - S and F is a diagonal matrix with fii = ∑j sij. We then incorporated the pairwise constraint as a graph regularization in the objective function to enhance community detection locally.

Finally, the objective of the model is to minimize the following loss function::

where γ and η are the parameters that control the tradeoff between different parts of the loss. We used the backpropagation (BP) algorithm and Adam optimizer to train the model. At convergence, the algorithm produces the community label for each node by:

4 Experiments

We compared our approach with eight state-of-the-art methods on nine widely-used benchmark datasets. We also analyze the features of our method to appreciate its effectiveness.

4.1 Experiment Setup

To carry out an accurate comparison of the nine methods, we used nine public datasets with known communities (Table 1). As the networks used have ground-truth communities, we adopted two widely used metrics, i.e. accuracy (AC) [Liu et al., 2012] and normalized mutual information (NMI) [Danon et al., 2005], for performance evaluation. We applied Adam optimizer in our GUCD method using TensorFlow.

4.2 Comparison with the ExistingMethods

We first evaluated our GUCD against eight (unsupervised) community detection methods. Depending on what network information they use, these existing methods can be grouped into three types. The first type uses only network topology, which includes DCSBM [Karrer and Newman, 2011] and EdMot-SC [Li et al., 2019]. The second uses only node attributes, including LDA [Blei et al., 2003]. The third uses topology and attributes together, including Block-LDA [Balasubramanyan and Cohen, 2011], PCLDC [Yang et al., 2009], SCI [Wang et al., 2016], MISAGA [He and Chan, 2018] and TLSC [Zhang et al., 2018].

GUCD is the best on 7 and 6 out of 9 datasets in terms of AC (Table 2) and NMI (Table 3). On the remaining networks where GUCD does not perform the best, it is still competitive with the best baselines. These results demonstrate the superiority of our new approach over the existing methods.

4.3 Deep Analysis of GUCD

Similar to most existing deep learning methods, GUCD has multiple components affecting its performance. Moreover, MRFasGCN is a major component of GUCD and can be applied in different ways. Here we report the results from different combinations of different major components of GUCD.

Effects of Individual Components

We compared GUCD with six variations of GUCD. We first considered two unsupervised variants of MRFasGCN, a major component of GUCD: 1) the weight parameters H(0) , H(1) and H(2) in MRFasGCN is set to 1 without training (as the most general way), namely MasG-U1, and 2) the weight parameters is set randomly without training (as suggested as an unsupervised usage in [Kipf and Welling, 2017]), namely MasG-U2. We included in our comparison with another unsupervised variant of MRFasGCN by adding the inner product of node community membership for reconstructing links as the decoder, namely MasG-IN. (Note that this is the most common way used in unsupervised GCN models for network embedding, a different albeit similar problem.) We also tested three variants of GUCD. The first two reconstruct links and attributes separately, named as GUCD-1 and 2. The third is GUCD without the local enhancement, called GUCD-3.

The experimental results on nine benchmark problems revealed that GUCD performed the best on 7 and 7 out of the 9 networks in terms of AC (Table 4) and NMI (Table 5). Specifically, GUCD is on average 17.45% (and 24.49%) and 23.99% (and 29.18%) more accurate than MasG-U1 and MasG-U2 in AC (and NMI). By some extra experiments we also observed that to achieve similar performances with GUCD, MRFasGCN needs almost 30%, 30%, 30%, 30%, 20%, 0.2%, 0.8%, 2% and 0.05% supervised information for the nine datasets respectively in training. This validates not only the effectiveness of our unsupervised framework using Autoencoder, but also the soundness of the communityoriented dual decoder, i.e. we use different while the most suitable mechanisms to reconstruct links and attributes respectively for community detection. Besides, GUCD is on average 17.3% (and 22.55%) more accurate than MasG-IN in AC (and NMI). This further validates the soundness of the new decoding mechanisms (i.e. we reconstruct links by modelling that nodes in the same community share the same link pattern, and reconstruct attributes based on topic modelling) over the existing methods for reconstructing links alone via the inner product operation. In addition, GUCD is on average 15.99% (and 22.4%), 2.35% (and 1.06%), and 1.71% (and 3.4%) more accurate than GUCD-1, GUCD-2, and GUCD-3 in terms of AC (and NMI). This demonstrates that the topological and attributed decoders both are effective. The strategy for local enhancement also helps meliorate overfitting caused by the sparsity of networked data.

Qualitative Analysis

To further validate the effectiveness of our new decoding mechanism over the one that most commonly used in network embedding, we further compared GUCD and MasGIN by showing the results of AC and NMI as a function of the number of iterations. Consider the results on Twitter as an example. As shown in Fig. 2, the GUCD results match more closely to the ground truth than MasG-IN, and the result of the former is more stable than that of the latter with more training cycles, suggesting that the new decoding mechanisms are suitable for unsupervised community detection.

5 RelatedWork

The current work of GCN focuses primarily on node classification [Kipf and Welling, 2017], which has been adopted for semi-supervised community detection [Li et al., 2018; Jin et al., 2019]. However, community detection is, in essence, an unsupervised problem since little training data are available for most applications. It is imperative to develop novel GCN methods for unsupervised community finding.

A related line of work is network embedding using GCN. For example, the ARGA method [Pan et al., 2018] adopts an adversarially regularized graph Autoencoder, which uses the same encoder and decoder as GAE [Kipf and Welling, 2016] while introduces an adversarial module to force the node representation to follow a suitable prior distribution. The ARGA method has also been extended to use graph convolution, instead of inner product, as the decoder to reconstruct links; the resulting method can reconstruct links better than reconstructing both links and attributes [Pan et al., 2019]. For unsupervised learning, most of the existing methods focus primarily on reconstructing network structures, as their performance degrades when being used to reconstruct links and attributes together. These existing methods seem to be suitable for representation learning, e.g., embedding, but not adequate for unsupervised community detection, a more difficult learning task. This has been experimentally shown by the comparison between GUCD and its variant MasG-IN (using inner product to reconstruct links), as shown in Fig. 2 and Tables 4 & 5.

6 Conclusion and Discussion

This is the first approach extending GCN effectively to unsupervised community detection. Using the Autoencoder framework, we focused on community identification rather than network embedding in the encoder; and used the most suitable mechanisms to reconstruct links and attributes separately. We also introduced a local enhancement to ameliorate the issue of overfitting brought by the sparsity of networked data. We carried out experiments and demonstrated the superiority of the new approach. We further showed the effectiveness of the novel decoding mechanism for generating links and attributes against the most commonly used methods for reconstructing links alone. Even though the new approach was designed for community detection, the underlying idea may be readily extended to GCN-based network embedding as discussed in Related Work.

Acknowledgments

This work was supported by the Natural Science Foundation of China (61832014, 61876128, 61772361, U1736103).