Modularity Based Community Detection with Deep Learning

1 Introduction

Real-world systems often appear in networks, e.g., social networks in Facebook media, protein interaction networks, power grids and the Internet. Real-world networks often consist of functional units, which manifest in the form of network modules or communities, subnetworks with nodes more tightly connected with respect to the rest of the networks. Finding network communities is, therefore, critical for characterizing the organizational structures and understanding complex systems.

A great deal of effort has been devoted to developing network community finding methods, among which, two are widely adopted and thus worth mentioning. The stochastic model [Psorakis et al., 2011] focuses on deriving generative models of networks. Such a generative model in essence maps a network to an embedding in a low-dimensional latent space. The mapping can be done by, e.g., nonnegative matrix factorization (NMF) [Wang et al., 2008]. Unlike the stochastic model, the modularity maximization model [Newman, 2006], as the name suggests, attempts to maximize a modularity function on network substructures. The optimization can be done by eigenvalue decomposition (EVD), which is equivalent to reconstructing a low-rank modularity matrix.

⇤Corresponding author.

In short, while appeared in different forms, the stochastic model and modularity maximization model share an essential commonality, i.e., mapping a network to a low-dimensional, latent space embedding. Motivated by the strong discrimination power of the modularity maximization model and the relationship between maximizing modularity and reconstructing modularity matrix by finding low-dimensional embedding, we aim to seek a more effective reconstruction algorithm for modularity optimization. However, all these types of embedding adopted in the two popular models are linear, e.g., NMF in the stochastic model and EVD in the modularity maximization model. This is in sharp contrast to the fact that real-world networks are full of nonlinear properties, e.g., a relationship (e.g., distance) among nodes may not necessarily be linear. As a result, the representation power of these linear mapping based models is limited on real-world networks.

Neural networks, particularly that with deep structures, are well known to provide nonlinear low-dimensional representations [Bourlard and Kamp, 1988]. They have been successfully applied to complex problems and systems in practice, such as image classification, speech recognition, and playing an ancient strategic board game of Go. To the best of our knowledge, however, deep neural networks have not yet been successfully applied to community detection.

Taking advantage of the nonlinear representation power of deep neural networks, we propose in this paper a nonlinear reconstruction (DNR) algorithm for community detection using deep neural networks.

It is known that information beyond network topology can greatly aid network community identification [Zhang, 2013; Yang et al., 2015]. Examples of such information include semantics on nodes, e.g., names and labels, and constraints on relationships among nodes, e.g., community membership constraints between adjacent nodes (pairwise constraints). In the current study, we extend our DNR method to a semisupervised DNR (semi-DNR) algorithm to explicitly incorporates pairwise constraints among nodes to further improve community detection.

2 Reconstruction based Community Detection

We consider an undirected and unweighted graph G = (V↪ E), where V = ¶v1↪ v2↪ ▷▷▷↪ vN♦ is the set of N vertices, and E = ¶eij♦ the set of edges each of which connects two vertices in V . The adjacency matrix of G is a nonnegative symmetric matrix A = [aij ] 2 RN⇥N + where aij = 1 if there is an edge between vertices i and j, or aij = 0 otherwise, and aii = 0 for all 1  i  N. The degree of vertex i is defined as ki = Pj aij . The problem of community detection is to find K modules or communities ¶Vi♦Ki=1 that are subgraphs whose vertices are more tightly connected with one another than with outside vertices. Here, we consider disjoint communities, i.e., Vi \ Vj = ; for i 6= j.

2.1 Stochastic Model

In stochastic model [Psorakis et al., 2011; He et al., 2015; Jin et al., 2015], aij can be viewed as the probability that vertices i and j are connected. This probability can be further considered to be determined by the probabilities that vertices i and j generate edges belonging to the same community. We introduce latent variables H = [hik] 2 RN⇥K + with hik representing the probability that node i generates an edge belonging to community k. This latent variable also captures the probability that node i belongs to community k, and each row of H can be considered as a community membership distribution of a vertex. The probability that vertices i and j is connected by a link belonging to community k is then hikhjk, and the probability that they are connected is:

As a result, the community detection problem can be formulated as a nonnegative matrix factorization A ⇡ ˆA = HHT . The NMF-based community detection approaches [Psorakis et al., 2011] aim to find a nonnegative membership matrix H to reconstruct adjacency matrix A. There are two common objective (loss) functions to quantify the reconstruction error. The first is based on the square loss function [Wang et al., 2008; Zhang et al., 2007] which is equivalent to the square of the Frobenius norm of the difference between two matrices

The second is based on the Kullback-Leibleer divergence (KLdivergence) between two matrices

The index of the largest element in the ith row of H indicates the community that node i belongs to.

There are many variations to the stochastic model, such as nonnegative matrix tri-factorization and stochastic block model. Nearly all of these models can be intuitively viewed as finding new representations in a low-dimensional space that can best represent and reconstruct the adjacency matrix.

2.2 ModularityMaximizationModel

This model was introduced by Newman [Newman, 2006] to maximize a modularity function Q, which is defined as the difference between the number of edges within communities and the expected number of such edges over all pairs of vertices. For example, consider a network with two communities, then

where hi equals to 1 (or -1) if vertex i belongs to the first (or second) group, kikj 2m is the expected number of edges between vertices i and j if edges are placed randomly, ki is the degree of vertex i and m = 12 Pi ki is the total number of edges in the network. By defining modularity matrix B = [bij ] 2 RN⇥N whose element is bij = aij - kikj 2m , modularity Q can be written as

where h = [hi] 2 RN is a community membership indicator vector. Maximizing Eq. (1) is NP-hard, for which many optimization algorithms have been proposed, such as extremal optimization [Duch and Arenas, 2005]. In practice, we can relax the problem by allowing variable hi to take any real value and hT h = N. To generalize Eq. (1) to K > 2 communities, we can define an indicator matrix H = [hij] 2 RN⇥K and obtain

where Tr(▷) is the trace of a matrix. Based on Rayleigh Quotient, the solution to this problem is the largest K eigenvectors of the modularity matrix B. Each row of matrix H can be regarded as a new representation of the corresponding vertex in the latent space, and clustering algorithms, such as k-means, can be used to classify the nodes into disjoint groups in the latent space.

The Eckart-Young-Mirsky Theorem [Eckart and Young, 1936] explores the relationship between the reconstruction and singular value decomposition (SVD).

Theorem 1. [Eckart and Young, 1936] For a matrix D 2 Rm⇥n (m> n), if D=U⌃VT is the singular value decomposition of D, and U, V, ⌃ = diag(σ1↪ σ2↪ ▷▷▷↪ σm) where σ1 > σ2 > ▷▷▷ > σm are as follows:

where ⌃1 is r ⇥ r, U1 is m⇥ r and V1 is n ⇥ r, then the optimal solution to the following problem

The above theorem means that the matrix reconstruction from the singular vectors corresponding to the K largest singular values is the best rank-K approximation to the original matrix under the Frobenuis norm. Since modularity matrix B is symmetric, there exists orthogonal decomposition B = U⇤UT , where ⇤ is diagonal matrix with the eigenvalues of B as the diagonal elements and UTU = I. Thus, the matrix reconstructed by the eigenvectors corresponding to the K largest eigenvalues is also the best approximation to the input matrix B with rank K. Therefore, the modularity maximization problem can be regarded as reconstructing the modularity matrix using a low-rank approximation.

Put together, stochastic model and modularity maximization can be intuitively interpreted as to find low-dimensional representations to best reconstruct given network structures. It is important to note that both of them only reconstruct original networks by linear reconstruction, using, e.g., NMF or SVD, and ignore nonlinear properties of the networks. It is unclear how NMF and SVD based approaches can be extended to accommodate nonlinear low-dimensional embedding. We aim to overcome this difficulty by using deep neural networks, the focus of the current paper.

3 Deep Nonlinear ReconstructionModel

We now present a novel deep nonlinear reconstruction (DNR) model for community detection. We first introduce an AutoEncoder, which is a key building block of the model, and then describe a stacked Auto-Encoder. While in the following discussion we focus on finding a nonlinear embedding that best reconstructs the modularity matrix B, as inspired by the SVDbased modularity maximization (Section 2.2), our method can be readily applied to other network input forms, such as adjacency and Laplacian matrices.

3.1 Reconstruction based on Auto-Encoder

Auto-Encoder is a special neural network that is used to learn a new representation that can best approximate the original data [Bourlard and Kamp, 1988; Hinton and Zemel, 1994]. We adopt modularity matrix B = [bij ] 2 RN⇥N as the input to the Auto-Encoder. Here, the elements of B are bij = aij - kikj 2m , and the ith column bi of B represents vertex i. The Auto-Encoder consists of two key components: encoder and decoder. The encoder maps the original data B to a lowdimensional embedding H = [hij] 2 Rd⇥N where d < N and the ith column of H, i.e., hi, represents vertex i in the latent spacehi = f(bi) = s(WHbi + dH)↪ (2)

where WH 2 Rd⇥N ↪ dH 2 Rd⇥1 are the parameters to be learned in the encoder, and s(▷) is an element-wise nonlinear mapping, such as sigmoid function ssigmoid(x) = 1 1+e-x or tanh function stanh(x) = ex-e-x ex+e-x . The decoder maps the latent representation H back into the original data space, i.e., reconstructs the original data from the latent representation:

where WM 2 RN⇥d ↪ dM 2 RN⇥1 are the parameters to be learned in the decoder and g(▷) is another element-wise nonlinear mapping similar to s(▷). Auto-Encoder aims at learning a low-dimensional nonlinear representation H that can best reconstruct the original data B, i.e. minimize the difference between the original data B and reconstruction data M under parameters ✓ = ¶WH↪ dH↪WM↪ dM♦

where L✓(bi↪mi) is a distance function that measures the reconstruction error. Here we adopt the Euclidean distance and sigmoid cross-entropy distance as distance functions. The sigmoid cross-entropy distance maps elements in bi = [bji] 2 RN⇥1 and mi = [mji] 2 RN⇥1 to [0↪ 1] using sigmoid function σ(x) = 1 1+e-x , and then computes the cross-entropy of them as

After training the Auto-Encoder, WH and dH are obtained and Eq. (2) can be used to generate the new representations for all vertices.

3.2 Optimization

Eq. (3) can be solved by back-propagation with stochastic gradient descent. In each iteration, the parameters ✓ = ¶WH↪ dH↪WM↪ dM♦ are updated as follows

where ↵ 2 ¶H↪ M♦. By defining z↵ = W↵x + d↵, we have

where δj↵ = @ @zj↵ L✓(xi↪ g(f(xi))) denotes the contribution of a node to the overall reconstruction error. For Euclidean distance based L✓(B↪M),

where s0 (x) is the derivative of s(x).

3.3 Stacked Auto-Encoder

Recently, deep learning has been successful on various problems in many fields, such as image classification, semantic segmentation [Liu et al., 2015; Liang et al., 2015]. However, as the number of layers increases, the space of parameters grows exponentially, making optimization inefficient. A compromising strategy is to train the network layer by layer [Vincent et al., 2010].

To take advantage of a deep architecture, we stack a series of Auto-Encoders to form a DNR model. For a deep AutoEncoder network, we train the first Auto-Encoder by reconstructing the original data, i.e., the modularity matrix B and obtain a new representation H1 2 RN⇥t1 . We then train the ith Auto-Encoder by reconstructing the output of the (i-1)th Auto-Encoder and obtain a representation Hi 2 RN⇥ti , where ti < ti-1. The number of Auto-Encoders we stack and the dimensions of new representations, i.e., tis', are discussed in Section 5.2.

4 Pairwise Constrained Semi-supervised Community Detection

We now incorporate pairwise constraints on vertices into the proposed DNR model and introduce a novel reconstruction space graph regularization for semi-supervised DNR (semiDNR). If we have a priori knowledge that vertices i and j belong to the same community, we can make use of this knowledge in two different ways. First, to classify two nodes into the same community, the new representations of nodes i and j, i.e., hi and hj, should be similar, since the new representations are used to cluster the two vertices after encoding. Second, this a priori information should also be encoded into the DNR model to further affect the embedding of other vertices. Therefore, instead of just modifying the embedding representation, we incorporate the pairwise constraints into the loss function of the Auto-Encoder in Eq. (3).

To measure the similarity of their latent representations, we can adopt either Euclidean distance or Kullback-Leibleer divergence (KL-divergence), i.e.

If nodes i and j are known to belong to the same community, we then try to minimize the difference between their new representations DLSE(hi↪ hj) . We define a pairwise constraint matrix O = [oij ] 2 RN⇥N + , where oij = 1 if nodes i and j are known to be in the same community, or oij = 0 otherwise. Thus, we can write the pairwise constraints as

where Tr(▷) is the trace of a matrix, D = [dij] 2 RN⇥N + a diagonal matrix whose entries are row summation of O, i.e., dii = PNj=1 oij , and L = D - O the graph regularization matrix (Laplacian matrix) of a priori information O. Similarly, the KL-divergence based constraints can be written as:

which takes into account the asymmetry of KL-divergence and averages DKL(hi♣♣hj) and DKL(hj♣♣hi). By minimizing RLSE(O↪H) or RKL(O↪H), we expect the new representations of two nodes i and j are similar if we have some information indicating that these two nodes belong to the same community, i.e., the corresponding element oij = 1 .

By incorporating the pairwise constraints in Eq (4) with the reconstruction error function in Eq (3), we obtain the overall loss function for semi-supervised DNR (semi-DNR) as

where λ is a parameter for making a tradeoff between the reconstruction error (the first term L(B↪M)) and the consistency of the new representations with a priori information (the second term Tr(HT LH)). For semi-DNR, we can impose a graph regularization term on the reconstruction layers of all Auto-Encoders, and then evaluate the performance improvement as discussed in Section 5.3.

Eq. (4) can also be solved using back-propagation. Since the reconstruction space graph regularization term Tr(HT LH) is independent of reconstruction of M, it does not affect the update of WM and bM. Therefore, we only need to modify δiH as δiH(semi) = δiH + δigraph , where

denote how much a node is responsible for the inconsistency of the derived representation and the pairwise constraints based on the Euclidean distance and KL-divergence, respectively. Here ⊙ and ÷ denote the element-wise multiplication and division, respectively.

5 Experimental Analysis

To evaluate the proposed DNR and semi-DNR methods, we analyzed their performance on widely used synthetic benchmarks and real-world networks. We first compared DNR with seven state-of-the-art approaches, which are divided into two categories based on whether they are based on modularity maximization. The modularity based methods include the spectral (SP) algorithm [Newman, 2006], the external optimization

(EO) algorithm [Duch and Arenas, 2005], the FUA algorithm [Blondel et al., 2008], the MABA algorithm [He et al., 2012] and the (FN) algorithm [Newman, 2004]. The remaining methods include the (FEC) algorithm [Yang et al., 2007] and the Infomap algorithm [Rosvall and Bergstrom, 2008].

To assess the effectiveness of using pairwise constraints, we compared semi-DNR with two existing semi-supervised community detection algorithms, ModLink [Zhang, 2013] and GraphNMF [Yang et al., 2015]. The former transforms pairwise constraints into information of network topology, modifies the adjacency matrix and uses a conventional algorithm to find communities on new label-refined networks. The latter incorporates the labels by constraining the nodes belonging to the same community to have similar membership representations. We adopted the Normalized Mutual Information (NMI) for performance measure.

5.1 Experiment Setup

The layer configurations of the deep neural networks for different problems tested are shown in Table 2. The networks have at most 3 stacked Auto-Encoder, and the dimension of each latent space is less than that of its input and output spaces. For example, the stacked Auto-Encoder network for the LFR network consists of three Auto-Encoders, where the first is 1,000-512-1,000, the second 512-256-512 and the third 256128-256. All Auto-Encoders were trained separately. We took a modularity matrix as the input to the first Auto-Encoder, and trained the it to minimize the reconstruction error, then took the embedding result as the input to the second AutoEncoder, and so on. We set the training batch to the size of the network and ran at most 100,000 iterations. For each network we trained a DNR model with 10 random initializations, and took the latent representations from three Auto-Encoders for clustering. Here, we adopted the k-means for clustering and returned the results with the maximum modularity.

5.2 Community Detection Results

We considered two types of synthetic networks, GirvanNewman (GN) networks [Girvan and Newman, 2002] and Lancichinetti-Fortunato-Radicchi (LFR) networks [Lancichinetti et al., 2008]. Each GN network consists of 128 nodes divided into 4 communities of 32 nodes each. Each node has on average 16 edges, among which Zout edges are intercommunity edges. The results are shown in Figure 1(a). As shown, DNR outperforms all competing methods, especially when Zout > 6.

The LFR networks are more complicated than the GN networks. As suggested in [Lancichinetti et al., 2008], we set the number of nodes to 1000, the average degree to 20, the exponent of a vertex degree and the community size to -2

(a) GN newtwork with Zout=7

(b) GN newtwork with Zout=8

(c) LFR network with θ = 0▷75

(d) LFR network with θ = 0▷8

Figure 2: Comparison of semi-DNR and two competing methods on GN and LFR networks.

and -1 respectively, and varied the mixing parameter θ from 0.6 to 0.8. To fully evaluate the performance on networks with different community sizes, we generated two groups of networks: one with community sizes from 10 to 50 while the other from 20 to 100. The results on these two groups of networks are shown in Figs 1(b) and 1(c). As shown, DNR can successfully detect small and large communities. It achieves the best performance when θ > 0▷65 on networks with small community size (middle figure, Figure 1) and θ > 0▷6 on networks with large community sizes (right figure, Figure 1). While Infomap performs slightly better than DNR when is small, it completely fails when θ > 0▷75.

In summary, the experimental results on synthetic networks showed that the deep nonlinear model is more effective on difficult networks with vague community structures and is competitive on easy networks with clear community structures. While the factors for such a superb performance compared with other modularity-based methods remains to be further investigated, it may be partially attributed to the nonlinear structure of our new model, which helps to mitigate the resolution limit [Fortunato and Barthelemy, 2007] and the extreme degeneracy [Good et al., 2010] problems, both of which are often suffered from modularity optimization.

Nine widely-used real networks, listed in Table 1, were used for evaluation. As shown in previous work [Psorakis et al., 2011], no single unified loss function seemed to exist that can successfully detect communities in all networks. In our experiments, we also adopted the Euclidean distance and sigmoid cross-entropy as error functions. We used sigmoid crossentropy instead of KL-divergence because the former can be integrated with the sigmoid function for back-propagation.

The results are shown in Table 1. Here, we compared DNR with other well-known modularity-based community detection methods. As shown in the table, DNR with the L2 norm (DNR L2) and with the cross-entropy distance (DNR CE) outperforms most of the competing modularity-based optimization algorithms.

5.3 Semi-supervised Community Detection Results

To evaluate the new semi-supervised deep nonlinear reconstruction (semi-DNR) method, we used networks on which it is difficult to find satisfactory community structures without label information. As shown in Figure 2, the performance is mediocre on GN network with Zout = 8 and LFR network with θ = 0▷75 and 0▷8. Besides, we chose GN network with Zout = 7 where the methods without labels can also achieve better results for comparison. Here, we set the balancing parameter λ = 1000. We also verifed the effects of pairwise constraints on more than one layer i.e., only the bottom layer, both bottom and middle layers and all the three layers.

The results are shown in Figure 2. On the GN with Zout = 7, all the methods have similar improvements by enforcing the same percent of labels. On the networks where unsupervised methods cannot obtain satisfactory results, in comparison, the semi-DNR achieves much better performance with the same number of labels. For example, with 20% pairwise constraints, the NMI of semi-DNR achieves 0.95 while that of GraphNMF and ModLink only achieve 0.76 and 0.79, respectively, on LFR network with θ = 0▷8 (right figure in Figure 2). This means the semi-DNR is much more efficient on the use of pairwise constraints than other methods. Furthermore, the performance of enforcing pairwise constraints on multi-layers has similar improvements. It illustrates that semi-DNR can fully explore pairwise constraints by only one layer graph regularization.

6 Conclusion

In order to overcome the serious drawback of linear low-rank embedding used by the widely adopted stochastic model and modularity maximization model for network community identification, we proposed a nonlinear model in deep neural networks to gain representation power for large complex networks; developed an algorithm using the model for network community detection; and further extended this method to a semi-supervised deep nonlinear reconstruction algorithm by incorporating pairwise constraints. Extensive experimental results on synthetic and real networks illustrate that our new methods outperform the existing state-of-the-art methods for network community identification. In the future, we plan to study model selection using the latent space embedding from DNR to make the model and methods more robust.

7 Acknowledgments

This work was supported by National Natural Science Foundation of China (No. 61503281, 61502334, 61303110, 61422213), "Strategic Priority Research Program" of the Chinese Academy of Sciences (XDA06010701), Open Funding Project of Tianjin Key Laboratory of Cognitive Computing and Application, Foundation for the Young Scholars by Tianjin University of Commerce (150113), the Talent Development Program of Wuhan, the municipal government of Wuhan, Hubei, China (2014070504020241), and an internal research grant of Jianghan University, Wuhan, China, as well as by United States National Institutes of Health (R01GM100364).