# Variational Approach for Learning Community Structures

Authors: Jun Jin Choong; Xin Liu; Tsuyoshi Murata
Journal: Complexity
 (2018)

---

## Abstract

Discovering and modelingcommunity structure exist to be a fundamentally challenging task. In domains such as biology, chemistry, and physics, researchers often rely on community detection algorithms to uncover community structures from complex systems yet no unified definition of community structure exists. Furthermore, existing models tend to be oversimplified leading to a neglect of richer information such as nodal features. Coupled with the surge of user generated information on social networks, a demand for newer techniques beyond traditional approaches is inevitable. Deep learning techniques such as network representation learning have shown tremendous promise. More specifically, supervised and semisupervised learning tasks such as link prediction and node classification have achieved remarkable results. However, unsupervised learning tasks such as community detection remain widely unexplored. In this paper, a novel deep generative model for community detection is proposed. Extensive experiments show that the proposed model, empowered with Bayesian deep learning, can provide insights in terms of uncertainty and exploit nonlinearities which result in better performance in comparison to state-of-the-art community detection methods. Additionally, unlike traditional methods, the proposed model is community structure definition agnostic. Leveraging on low-dimensional embeddings of both network topology and feature similarity, it automatically learns the best model configuration for describing similarities in a community.


---

## Body

## 1. Introduction

Real-world complex systems are often projected into networks to observe complex patterns. Entities in a complex system can be represented as nodes (vertices) and their interactions represented as an edge (link). For instance, social interactions between people can be represented in the form of a social network. Publications by authors and their respective publication venues can be represented with a bipartite citation network. The flexibility of networks and its vast literature on graph theory make network science very appealing to researchers. Although networks are merely represented in forms of nodes and edges, a large complex system could easily scale from hundreds to millions of nodes and edges. This poses a very challenging task in machine learning, especially tasks such as graph clustering or more commonly known as community detection [1] in the literature of network science. Given a network (graph) with its node content and structural (link) information, community detection aims to partition the nodes in the network into a number of disjoint groups. These partitions can be formulated depending on the given definition. For example, in modularity maximization [2], each partition is compared against a null model (random network). A partition is classified as good when the modularity score is greater than partitioning a random network. On the other hand, statistical methods such as the Stochastic Blockmodel (SBM) introduced Bayesian treatment of uncertainty when partitioning the network. Nodes with similar statistical similarity have higher probability to cluster together regardless of the cluster’s density [3]. This is known as stochastic equivalence. In general, a universal definition of community structure does not exist. Nevertheless, the objective remains the same, i.e., to find a group of nodes that shares some form of similarity between one another. In this paper, such similarity is defined as latent similarity; the similarity measure is not predefined. Quantifying such similarity is arguably subjective and difficult especially when a given network can be feature-rich or structure-only; there is no one-size-fits-all solution for community detection (i.e., theno free lunch theorem). Therefore, it is essential that algorithms capture both higher-order information and structural information. To this end, we look at network representation learning [4, 5] as a potential solution.In machine learning, representation learning [6] has been successfully applied to various fields such as natural language processing and computer vision. Notably, successes of deep learning have surpassed human accuracy with ease [7]. However, these successes are difficult to be explained. More precisely, it is difficult to explain “why” deep learning model performs so well. In an attempt to solve this problem, researchers bridged the understanding gap by introducing probabilistic deep models (also known as Bayesian Deep Learning) [8]. Using fundamental building blocks from a probabilistic perspective, assumptions are given in forms of noninformative priors and the model is forced to correct these assumptions while learning. Consequently, the models become less ambiguous than a typical deep learning model which is commonly known to be a black-box.Leveraging on recent advances in representation learning, network representation learning aims at a similar objective, but from a network perspective. Given a network, the objective is to find a latent representation that generalizes for various machine learning tasks such as classification, link prediction, and clustering of nodes. Generally, a common choice for finding community structure in networks often involves a two-step approach. First, the network is embedded into a latent space (i.e., Euclidean space). Next, a general clustering algorithm such as Spectral Clustering [9] or k-means is applied to the learned embedding. For instance, Tianet al. proposed a network representation [10] learning model to learn a nonlinear mapping of the original network using a Stacked Autoencoder by showing that spectral clustering and Autoencoders have the same optimization objectives. Yanget al. considered a Stacked Autoencoder as a modularity optimization problem and further introduced a semisupervised approach throughmust-pair nodes for increased performance [11]. Assignment of communities is then obtained through k-means clustering from the latent representation that exhibits the highest modularity score. Inspired from Denoising Autoencoders [12], Wanget al. proposed Marginalized Graph Autoencoder for Graph Clustering (MGAE) [13] that artificially corrupts the feature matrix to increase the number of training data and provides a close-form solution for optimization. Spectral Clustering is then applied to the learned latent representation. Clearly, these methods all employ a two-step approach which is unsuitable for studying network generation or graph modeling [14].Instead of a costly two-step approach and ignoring uncertainty in the modeling process, the problem can be solved from a Bayesian point of view, by encoding our latent beliefs and assumptions as probabilistic graphical models. Specifically, one can assume that nodes and edges are modeled from a mixture model such as the Gaussian Mixture Model (GMM). This effectively couples the learning of cluster assignment with respect to its network representation into a joint probability distribution. Additionally, it helps to capture network properties exhibited by common networks which consequently helps in better understanding of real-world networks.Concretely, this paper proposes an extension to Variational Graph Autoencoder (VGAE) [15]. Originally, VGAE projects graph convolutions into a Univariate Gaussian latent space and have only been considered for semisupervised task such as link prediction and graph classification. The proposed model, VGAECD, relaxes this notion by introducing a Mixture of Gaussian. This is desirable as we would like to capture higher-order patterns from community structures and model its generative process. It is worth noting that similar approaches have been applied to VAE in domains such as image recognition [16]. However, these approaches are not readily applicable for networks, especially in a community detection problem.To summarize, this paper explores the idea of learning network representations using Bayesian treatment. We extend VGAE to include clustering-aware capability specifically targeting a community detection task. The contribution of this paper is summarized as follows:(i)
This paper proposes a novel generative model for community detection which is agnostic to the necessity of a predefined community structure definition. Through the process of automatic model selection, nodes are assigned a community based on the criterion that best reduces the loss function.(ii)
The proposed model inherits the benefits of Variational Autoencoder Framework. The advantages are threefold:(1) it provides a variational lower bound which is guaranteed to converge to a local minimum, (2) the lower bound is scalable, and (3) the model is generative, allowing generation of synthetic networks.(iii)
The proposed model outperforms the state-of-the-art models in community detection without requiring additional priors (unlike the Degree-Corrected SBM).


## 2. Problem Definition

A network pertaining to nodes, edges, and node features can be formally defined asG=(V,E,X), where V={vi,…,vN} consists of a set of nodes V=N, E={eij} is a set of edges, and X={x1,…,xN} is the set of node features. Each xi∈Rd defines a vector of real-values associated with node vi. From an Autoencoder’s perspective, the inputs are given in terms of structural information A∈RN×N, and node features X∈RN×d, where A denotes the adjacency matrix of G, and the node features are content information provided in forms of vector representation. In this work, we consider the undirected and unweighted network G, such that Aij=1 if eij∈E and otherwise it is equal to 0.Given the networkG, the objective of community detection or graph clustering is to partition the nodes in G into K disjoint groups {c1,c2,…,cK}, such that nodes grouped within the same cluster are close to each other while nodes in different clusters are distant in terms of network structure. Vertices grouped within the same cluster are more likely to have similarities in node features.Additionally, we consider the definition of a generative model. The discriminative model,p(θ∣X,A), infers the model parameters θ from the observed network G. Subsequently, a network G′ can be generated from the same set of parameters. Concretely, p(A∣θ)=G′. Under the model selection criterion, the model is said to be good when G′≊G and satisfies the condition of having community structures; i.e., G′ is not an Erdős–Rényi network. By definition, generative models can be considered as an ensemble learning model.


## 3. Related Work

Recent work in community detection can be broadly categorized into two types of models, namely, discriminative and generative models. The former includes a class of methods that infers communities given an observed network and, optionally, node features. Meanwhile, the latter considers the reconstruction of network while exploring plausible models that explain the observed phenomenon.


### 3.1. Discriminative Methods and Models

Predominantly, modularity maximization [2, 17] has been considered as the most successful method for detecting communities. However, it suffers from a resolution limit problem [18] and is known to exhibit degeneracies [19]. In terms of speed, label propagation [20] is capable of detecting communities in large-scale networks near linear time, though the solutions are usually nonunique. Additionally, other approaches such as WalkTrap [21], Infomap [22], Louvain [23], and their empirical competitiveness are subjected to trade-off between accuracy and scalability [24]. Representation learning methods such as GraRep [25] and CFOND [26] consider the completion of their adjacency matrix and can be generally considered as matrix factorization problem. Meanwhile, others like DeepWalk [27] and node2vec [28] consider representation of each node via a biased random walk. It assumes that neighboring nodes share similarities from the pivot node. Hence, when nodes are clustered together, they tend to co-occur on short random walks over the network.Besides standard linear methods mentioned previously, recent advances in deep learning revisited Autoencoders for networks. Particularly, GraphEncoder proposed by Tianet al. shows that optimizing the objective function of Autoencoder is similar to finding a solution for Spectral Clustering [10]. Leveraging on deep learning’s nonlinearity and recent advances in Convolutional Neural Networks, [29, 30] proposed the Graph Neural Network (GNN) and its generalization, the Graph Convolutional Neural Network (GCN) [29]. Defferrardet al. first cast the problem by projecting graph convolutions into spectral space, and convolving within this space.


### 3.2. Generative Methods and Models

Generative models can be further subdivided into algorithmic and statistical types. Examples of algorithmic models include the Kronecker Graphs [31], NetSim [32], and Block Two-Level Erdős-Rényi (BTER) model [33]. On the other hand, statistical methods attempt to approximate the true distribution via statistical inferencing or through statistical models (i.e., benchmark graphs such as GN [34], LFR [35], and mLFR [36, 37]). A widely known generative model for capturing networks with group structure is the Stochastic Blockmodel (SBM) or also known as the planted partition model. First explored by Snijders and Nowicki [38] two decades ago, the key idea behind SBM is stochastic equivalence. The probability that two nodes i and j are connected depends exclusively on their community memberships: two nodes within a community sharing the same stochasticity. However, the vanilla SBM exhibits a problem where high degree nodes are clustered into a community of their own. Karrer and Newman proposed the Degree Corrected (D.C.) SBM [39] which introduces a normalizing prior. Extensions to SBM include the Mixed Membership SBM (MMSBM) [40] for identifying mix community participation and bipartite SBM (biSBM) [41] for finding communities in bipartite networks. Today, SBM is well explored and its limitations has been widely studied [42, 43]. However, SBM is not a network representation learning model. Instead, SBM learns the latent variables Π and Z which describe the probabilities of cluster connectivity and cluster assignment, respectively, of a particular node which differs from common representation learning method.Contrary to SBM, typically Autoencoders consists of two nongenerative steps (encoder and decoder). Consequently, the learned representation cannot be generalized for generation of networks. To alleviate this problem, most recent approaches consider generative models for representation learning such as Generative Adversarial Networks (GAN) or Variational Autoencoder (VAE). For graphs, Kipf and Welling [15] introduced a variant of VAE for link prediction tasks in graphs and for GAN, and Panet al. [44] recently introduced adversarially regularized graph autoencoder (ARGA). In this work, we only consider the framework of VAE. We discuss this in Section 4.1.


## 3.1. Discriminative Methods and Models

Predominantly, modularity maximization [2, 17] has been considered as the most successful method for detecting communities. However, it suffers from a resolution limit problem [18] and is known to exhibit degeneracies [19]. In terms of speed, label propagation [20] is capable of detecting communities in large-scale networks near linear time, though the solutions are usually nonunique. Additionally, other approaches such as WalkTrap [21], Infomap [22], Louvain [23], and their empirical competitiveness are subjected to trade-off between accuracy and scalability [24]. Representation learning methods such as GraRep [25] and CFOND [26] consider the completion of their adjacency matrix and can be generally considered as matrix factorization problem. Meanwhile, others like DeepWalk [27] and node2vec [28] consider representation of each node via a biased random walk. It assumes that neighboring nodes share similarities from the pivot node. Hence, when nodes are clustered together, they tend to co-occur on short random walks over the network.Besides standard linear methods mentioned previously, recent advances in deep learning revisited Autoencoders for networks. Particularly, GraphEncoder proposed by Tianet al. shows that optimizing the objective function of Autoencoder is similar to finding a solution for Spectral Clustering [10]. Leveraging on deep learning’s nonlinearity and recent advances in Convolutional Neural Networks, [29, 30] proposed the Graph Neural Network (GNN) and its generalization, the Graph Convolutional Neural Network (GCN) [29]. Defferrardet al. first cast the problem by projecting graph convolutions into spectral space, and convolving within this space.


## 3.2. Generative Methods and Models

Generative models can be further subdivided into algorithmic and statistical types. Examples of algorithmic models include the Kronecker Graphs [31], NetSim [32], and Block Two-Level Erdős-Rényi (BTER) model [33]. On the other hand, statistical methods attempt to approximate the true distribution via statistical inferencing or through statistical models (i.e., benchmark graphs such as GN [34], LFR [35], and mLFR [36, 37]). A widely known generative model for capturing networks with group structure is the Stochastic Blockmodel (SBM) or also known as the planted partition model. First explored by Snijders and Nowicki [38] two decades ago, the key idea behind SBM is stochastic equivalence. The probability that two nodes i and j are connected depends exclusively on their community memberships: two nodes within a community sharing the same stochasticity. However, the vanilla SBM exhibits a problem where high degree nodes are clustered into a community of their own. Karrer and Newman proposed the Degree Corrected (D.C.) SBM [39] which introduces a normalizing prior. Extensions to SBM include the Mixed Membership SBM (MMSBM) [40] for identifying mix community participation and bipartite SBM (biSBM) [41] for finding communities in bipartite networks. Today, SBM is well explored and its limitations has been widely studied [42, 43]. However, SBM is not a network representation learning model. Instead, SBM learns the latent variables Π and Z which describe the probabilities of cluster connectivity and cluster assignment, respectively, of a particular node which differs from common representation learning method.Contrary to SBM, typically Autoencoders consists of two nongenerative steps (encoder and decoder). Consequently, the learned representation cannot be generalized for generation of networks. To alleviate this problem, most recent approaches consider generative models for representation learning such as Generative Adversarial Networks (GAN) or Variational Autoencoder (VAE). For graphs, Kipf and Welling [15] introduced a variant of VAE for link prediction tasks in graphs and for GAN, and Panet al. [44] recently introduced adversarially regularized graph autoencoder (ARGA). In this work, we only consider the framework of VAE. We discuss this in Section 4.1.


## 4. Methodology

### 4.1. Variational Graph Autoencoder

Variational Graph Autoencoder (VGAE) [15] extends the problem of learning network embedding to a generative perspective by leveraging on the Variational Autoencoder (VAE) framework [45]. Consider a given network G with structural information A and node features X; the inference model of VGAE parameterized by a two-layer GCN is defined as(1)qZ∣X,A=∏i=1Nqzi∣X,A(2)qzi∣X,A=Nzi∣μi,diagσi2.Here, μ and σ denote the mean and standard deviation vectors for node i which is obtained from a GCN layer, μ=GCNμ(X,A) and log⁡σ=GCNσ(X,A). The two-layer GCN is then defined as(3)GCNX,A=A^τA^XW0W1,with W0 and W1 representing the weight matrices for the first layer and second layer, respectively. W0 is shared between GCNμ(X,A) and GCNσ(X,A). τ(·) is the nonlinear function such as ReLU(·)=max(0,·) or sigmoid(t)=1/(1+e-t). A^=D-1/2AD-1/2 denotes the symmetric normalized adjacency matrix. The generative model is simply the inner product between the latent variables:(4)pA∣Z=∏i=1N∏j=1NpAij=1∣zizj=τzi⊤zj.In accordance to the VAE framework, both models can be tied together and optimized by maximizing the variational lower bound L(·):(5)log⁡pθX≥Lθ,ϕ;X=EqϕZ∣X,Alog⁡pθA∣Z-DKLqϕZ∣X∥pθZ.DKLqϕ(·)∥pθ(·) defines the Kullback-Leibler (KL) divergence between qϕ(·) and pθ(·). The lower bound can be maximized with respect to the variational parameters (θ,ϕ)=Wi via stochastic gradient descent, performed with a full-batch size. Here, the prior is defined as pθ(Z)=∏i=1N‍N(zi∣0,I), which is the isotropic Gaussian distribution, whose gradients can backpropagate via areparametrization trick [45].In the absence of node features,X becomes the identity matrix. This relaxation allows the reconstruction of a structure-only network. When provided with node features, the accuracy of VGAE link prediction improves [15].


### 4.2. Variational Graph Autoencoder for Community Detection (VGAECD)

A major drawback in VGAE’s approach is its restriction of nodes to be projected in a Univariate Gaussian space. This restriction suggests that all generated nodes come from a single clustering space. More specifically, dissimilar nodes tend to stay away from the Gaussian mean (centroid) [15]. On the contrary, the mean of the Gaussian should be a better representative of each respective community such that nodes which are similar should stay closer to their represented mean. Thus, nodes that are well represented by the mean representation hold equivalence in similarity. In this scenario, we can consider this as a relaxation of SBM which requires nodes in the same block to uphold stochastic equivalence.Utilizing this fact, we consider the unsupervised learning problem of community detection while adhering to the VGAE framework. Suppose that each node originating from a particular community is similar in some way; we can encode their similarity into the node’s representation vectorz which is better described by the mixture’s mean. The generative process then follows:(i)
For communitiesC={c1,…,cK}
(a)
Obtain a samplec~Cat(π)(b)
whereK is the number of clusters hyperparameters and πk is the prior probability for cluster k,π∈R+K, ∑k=1K‍πk=1. Cat(π) is the categorical distribution parameterized by π.(ii)
For nodesZ={z1,…,zN},
(a)
Obtain a latent vectorz~N(μc,σc2I)(b)
whereμc and σc2 are the mean and variance of the multivariate Gaussian distribution corresponding to cluster c.(iii)
Obtain a samplea by
(a)
computing the expectationμx=f(z;θ)(b)
samplea~Bern(μx)The functionf(z;θ) is optionally a nonlinear function whose input is z and is parameterized by θ. Particularly, we use the τ(zi⊤zj) inner product decoder. Bern(·) denotes the multivariate Bernoulli distribution parameterized by the latent vector μx. Then, the joint probability p(a,z,c) can be factorized as(6)pa,z,c=pa∣zpz∣cpc,with A={a1,…,aN}. Since a and c are independently conditioned on z, the factorized probabilities can be defined as(7)pc=Catc∣π(8)pz∣c=Nz∣μc,σc2I(9)pa∣z=Berna∣μxFor brevity, pθ(·)=p(·) and qϕ(·)=q(·), L(θ,ϕ;x)=LELBO(x); we can rewrite the lower bound in (5) to include the new terms:(10)log⁡px≥LELBOx=Eqz,c∣x,alogpa,z,cqz,c∣x,a,where q(z,c∣x,a) is the variational posterior which approximates the true posterior p(z,c∣x,a). Under the mean-field assumption, the approximate distribution can be factorized as(11)qz,c∣x,a=qz∣x,aqc∣x,a.Substituting (6) and (11) into (10), LELBO(x) can be rewritten as(12)LELBOx=Eqz,c∣x,alog⁡pa,z,cqz,c∣x,a=Eqz,c∣x,alog⁡pa,z,c-log⁡qz,c∣x,a=Eqz,c∣x,alog⁡pa∣z+log⁡pz∣c+log⁡pc-log⁡qz∣x,a-log⁡qc∣x,a.The inference model q(z∣x,a) is then modeled using a two-layer GCN as follows:(13)qz∣x,a=Nz;GCNμx,a,GCNσx,aI=Nz;μ~,log⁡σ~I.Similar to VGAE, the first layer’s weight matrix W0 is shared between μ~ and log⁡σ~. Substituting the terms, LELBO(x) can be further rewritten as(14)LELBOx=1L∑l=1L∑i=1Nxilog⁡μil+1-xilog⁡1-μil-12∑c=1Kγclog⁡σc2+σ~2σc+μ~-μc2σc2+∑c=1Kγclog⁡πcγc+121+log⁡σ~c2,with L being the total number of samples through sampled using the Monte Carlo Stochastic Gradient Variational Bayes (SGVB) estimator [45]. xi is the vector of node i, K is the number of clusters with πc denoting the prior probability of cluster c, and γc denotes q(c∣x,a) for brevity. μx(l) is computed as(15)μxl=τzi⊤zj,where z(l) is the lth sample from q(z∣x,a) as written in (13). To allow gradient backpropagation through the stochastic layer, thereparameterization trick is used; then z(l) can be obtained via(16)zl=μ~+σ~∘ϵl.Then, according to [45], ϵ(l)~N(0,I); ∘ is the Hadamard product operator. μ~ and σ~ are obtained through GCN(·).If we consider regroupingLELBO(x) with like-terms, (12) can be rewritten as(17)LELBOx=Eqz,c∣x,alogpa,z,cqz,c∣x,a=∫z∑cqz∣x,aqc∣x,alog⁡px,a∣zqz∣x+logpc∣zqc∣xdz=∫zqz∣x,alog⁡px,a∣zpzqz∣x,adz-∫zqz∣x,aDKLqc∣x∥pc∣zdz.The first term in (17) has no dependency on c and from the definition of KL divergence, it is nonnegative. Therefore, LELBO(x) is maximized when DKLq(c∣x)∥p(c∣z)≡0. From that, we follow [16], by defining q(c∣x,a) as(18)qc∣x,a=pc∣z≡pcpz∣c∑c′=1Kpc′pz∣c′From (18) the information loss induced by the mean-field approximation can be mitigated by forcing its dependency on the posterior p(c∣z) and noninformative prior p(c). The complete VGAECD algorithm can be found in Algorithm 1 and Figure 1 illustrates the conceptual idea of VGAECD.Algorithm 1:Variational Graph Autoencoder for Community Detection (VGAECD).
Input: Features X, Adjacency matrix A, Hyperparameters: learning rate ϵ, epochs L, size of layer 1 and 2. Output: Community Assignment Probability γ and Reconstructed Adjacency matrix A~ π ~ U ( 0,1 ) for l = 1 , . . . , L do for i = 1 , . . . , N do μ i = G C N μ ( x i , a i ) σ i = G C N σ ( x i , a i ) Sample c~Cat(c∣π) Sample zi~N(μc|i,diag(σc2|i)) Obtain reconstructed a~i=τ(zi⊤zj)⊳  Decoder Compute loss, LELBO⊳  From (14) and backpropagate gradients. end for end for Extract community assignment γ via zi⊳  From (18) Return γ, A~={a~1,...,a~N}Figure 1
Conceptual illustration of Variational Graph Autoencoder Framework for Community Detection (VGAECD). In the encoding phase, VGAECD first convolves on the network, learning structural and nodal features in the process. These pieces of information are then mapped into a latent representation,μci and σci which are parameters to Mixture of Gaussian Model. Subsequently, we can then sample to obtain a latent representation for each node z. Finally, A~ can be reconstructed using a decoding function, f(⋅). The loss is calculated and backpropagated to the latent variables.


## 4.1. Variational Graph Autoencoder

Variational Graph Autoencoder (VGAE) [15] extends the problem of learning network embedding to a generative perspective by leveraging on the Variational Autoencoder (VAE) framework [45]. Consider a given network G with structural information A and node features X; the inference model of VGAE parameterized by a two-layer GCN is defined as(1)qZ∣X,A=∏i=1Nqzi∣X,A(2)qzi∣X,A=Nzi∣μi,diagσi2.Here, μ and σ denote the mean and standard deviation vectors for node i which is obtained from a GCN layer, μ=GCNμ(X,A) and log⁡σ=GCNσ(X,A). The two-layer GCN is then defined as(3)GCNX,A=A^τA^XW0W1,with W0 and W1 representing the weight matrices for the first layer and second layer, respectively. W0 is shared between GCNμ(X,A) and GCNσ(X,A). τ(·) is the nonlinear function such as ReLU(·)=max(0,·) or sigmoid(t)=1/(1+e-t). A^=D-1/2AD-1/2 denotes the symmetric normalized adjacency matrix. The generative model is simply the inner product between the latent variables:(4)pA∣Z=∏i=1N∏j=1NpAij=1∣zizj=τzi⊤zj.In accordance to the VAE framework, both models can be tied together and optimized by maximizing the variational lower bound L(·):(5)log⁡pθX≥Lθ,ϕ;X=EqϕZ∣X,Alog⁡pθA∣Z-DKLqϕZ∣X∥pθZ.DKLqϕ(·)∥pθ(·) defines the Kullback-Leibler (KL) divergence between qϕ(·) and pθ(·). The lower bound can be maximized with respect to the variational parameters (θ,ϕ)=Wi via stochastic gradient descent, performed with a full-batch size. Here, the prior is defined as pθ(Z)=∏i=1N‍N(zi∣0,I), which is the isotropic Gaussian distribution, whose gradients can backpropagate via areparametrization trick [45].In the absence of node features,X becomes the identity matrix. This relaxation allows the reconstruction of a structure-only network. When provided with node features, the accuracy of VGAE link prediction improves [15].


## 4.2. Variational Graph Autoencoder for Community Detection (VGAECD)

A major drawback in VGAE’s approach is its restriction of nodes to be projected in a Univariate Gaussian space. This restriction suggests that all generated nodes come from a single clustering space. More specifically, dissimilar nodes tend to stay away from the Gaussian mean (centroid) [15]. On the contrary, the mean of the Gaussian should be a better representative of each respective community such that nodes which are similar should stay closer to their represented mean. Thus, nodes that are well represented by the mean representation hold equivalence in similarity. In this scenario, we can consider this as a relaxation of SBM which requires nodes in the same block to uphold stochastic equivalence.Utilizing this fact, we consider the unsupervised learning problem of community detection while adhering to the VGAE framework. Suppose that each node originating from a particular community is similar in some way; we can encode their similarity into the node’s representation vectorz which is better described by the mixture’s mean. The generative process then follows:(i)
For communitiesC={c1,…,cK}
(a)
Obtain a samplec~Cat(π)(b)
whereK is the number of clusters hyperparameters and πk is the prior probability for cluster k,π∈R+K, ∑k=1K‍πk=1. Cat(π) is the categorical distribution parameterized by π.(ii)
For nodesZ={z1,…,zN},
(a)
Obtain a latent vectorz~N(μc,σc2I)(b)
whereμc and σc2 are the mean and variance of the multivariate Gaussian distribution corresponding to cluster c.(iii)
Obtain a samplea by
(a)
computing the expectationμx=f(z;θ)(b)
samplea~Bern(μx)The functionf(z;θ) is optionally a nonlinear function whose input is z and is parameterized by θ. Particularly, we use the τ(zi⊤zj) inner product decoder. Bern(·) denotes the multivariate Bernoulli distribution parameterized by the latent vector μx. Then, the joint probability p(a,z,c) can be factorized as(6)pa,z,c=pa∣zpz∣cpc,with A={a1,…,aN}. Since a and c are independently conditioned on z, the factorized probabilities can be defined as(7)pc=Catc∣π(8)pz∣c=Nz∣μc,σc2I(9)pa∣z=Berna∣μxFor brevity, pθ(·)=p(·) and qϕ(·)=q(·), L(θ,ϕ;x)=LELBO(x); we can rewrite the lower bound in (5) to include the new terms:(10)log⁡px≥LELBOx=Eqz,c∣x,alogpa,z,cqz,c∣x,a,where q(z,c∣x,a) is the variational posterior which approximates the true posterior p(z,c∣x,a). Under the mean-field assumption, the approximate distribution can be factorized as(11)qz,c∣x,a=qz∣x,aqc∣x,a.Substituting (6) and (11) into (10), LELBO(x) can be rewritten as(12)LELBOx=Eqz,c∣x,alog⁡pa,z,cqz,c∣x,a=Eqz,c∣x,alog⁡pa,z,c-log⁡qz,c∣x,a=Eqz,c∣x,alog⁡pa∣z+log⁡pz∣c+log⁡pc-log⁡qz∣x,a-log⁡qc∣x,a.The inference model q(z∣x,a) is then modeled using a two-layer GCN as follows:(13)qz∣x,a=Nz;GCNμx,a,GCNσx,aI=Nz;μ~,log⁡σ~I.Similar to VGAE, the first layer’s weight matrix W0 is shared between μ~ and log⁡σ~. Substituting the terms, LELBO(x) can be further rewritten as(14)LELBOx=1L∑l=1L∑i=1Nxilog⁡μil+1-xilog⁡1-μil-12∑c=1Kγclog⁡σc2+σ~2σc+μ~-μc2σc2+∑c=1Kγclog⁡πcγc+121+log⁡σ~c2,with L being the total number of samples through sampled using the Monte Carlo Stochastic Gradient Variational Bayes (SGVB) estimator [45]. xi is the vector of node i, K is the number of clusters with πc denoting the prior probability of cluster c, and γc denotes q(c∣x,a) for brevity. μx(l) is computed as(15)μxl=τzi⊤zj,where z(l) is the lth sample from q(z∣x,a) as written in (13). To allow gradient backpropagation through the stochastic layer, thereparameterization trick is used; then z(l) can be obtained via(16)zl=μ~+σ~∘ϵl.Then, according to [45], ϵ(l)~N(0,I); ∘ is the Hadamard product operator. μ~ and σ~ are obtained through GCN(·).If we consider regroupingLELBO(x) with like-terms, (12) can be rewritten as(17)LELBOx=Eqz,c∣x,alogpa,z,cqz,c∣x,a=∫z∑cqz∣x,aqc∣x,alog⁡px,a∣zqz∣x+logpc∣zqc∣xdz=∫zqz∣x,alog⁡px,a∣zpzqz∣x,adz-∫zqz∣x,aDKLqc∣x∥pc∣zdz.The first term in (17) has no dependency on c and from the definition of KL divergence, it is nonnegative. Therefore, LELBO(x) is maximized when DKLq(c∣x)∥p(c∣z)≡0. From that, we follow [16], by defining q(c∣x,a) as(18)qc∣x,a=pc∣z≡pcpz∣c∑c′=1Kpc′pz∣c′From (18) the information loss induced by the mean-field approximation can be mitigated by forcing its dependency on the posterior p(c∣z) and noninformative prior p(c). The complete VGAECD algorithm can be found in Algorithm 1 and Figure 1 illustrates the conceptual idea of VGAECD.Algorithm 1:Variational Graph Autoencoder for Community Detection (VGAECD).
Input: Features X, Adjacency matrix A, Hyperparameters: learning rate ϵ, epochs L, size of layer 1 and 2. Output: Community Assignment Probability γ and Reconstructed Adjacency matrix A~ π ~ U ( 0,1 ) for l = 1 , . . . , L do for i = 1 , . . . , N do μ i = G C N μ ( x i , a i ) σ i = G C N σ ( x i , a i ) Sample c~Cat(c∣π) Sample zi~N(μc|i,diag(σc2|i)) Obtain reconstructed a~i=τ(zi⊤zj)⊳  Decoder Compute loss, LELBO⊳  From (14) and backpropagate gradients. end for end for Extract community assignment γ via zi⊳  From (18) Return γ, A~={a~1,...,a~N}Figure 1
Conceptual illustration of Variational Graph Autoencoder Framework for Community Detection (VGAECD). In the encoding phase, VGAECD first convolves on the network, learning structural and nodal features in the process. These pieces of information are then mapped into a latent representation,μci and σci which are parameters to Mixture of Gaussian Model. Subsequently, we can then sample to obtain a latent representation for each node z. Finally, A~ can be reconstructed using a decoding function, f(⋅). The loss is calculated and backpropagated to the latent variables.


## 5. Experiments

Community detection algorithms are often evaluated against two kinds of networks: synthetic and empirical datasets. These are discussed in detail in the following subsections.


### 5.1. Synthetic Datasets

Two synthetic networks are used in our evaluation. We consider two most common benchmark graphs used for benchmarking community detection algorithm. Namely, we used the Girvan-Newman (GN) benchmark graph [1, 34, 46] and the LFR benchmark graph [35]. The GN benchmark graph is a variant of the planted l-partition. In our experiment, we vary the zout value from a range of {1,…,8}. Each node has an average degree of k=16, with 32 nodes in each community (a total of 128 nodes) and 4 communities in total.The LFR benchmark graph is an extension of the GN benchmark graph. It is considered to be more realistic than the GN benchmark graph. It introduces a skewed degree distribution and accounts for network heterogeneity, resulting in communities that are generated in different sizes. The LFR benchmark graph is generated using default parameters as suggested by Lancichinettiet al. [35]. These parameters are number of nodes (N=1000), average degree (k=15), and minimum (cmin=30) and maximum (cmax=50) number of nodes per community. The generation follows thescale-free parameters settings of exponents τ1=-2 and τ2=-1, respectively. On average, between 20 and 30 communities are generated.


### 5.2. Empirical Datasets

The empirical datasets are divided into two kinds: networks with features and without features. The datasets are as follows:(i)
Karate: a social network represents friendship among 34 members of a karate club at a US University [47].(ii)
PolBlogs: a network of political blogs assembled by Adamic and Glance [48]. The nodes are blogs and web links between them are represented by their edge. These blogs have known political leanings and were labelled by hand by Adamic and Glance.(iii)
Cora: a citation network with 2,708 nodes and 5,429 edges. Each node corresponds to a document and the edges are citation links [49].(iv)
PubMed: A network consisting of 19,717 scientific publications from PubMed database pertaining to diabetes was classified into one of three classes (“Diabetes Mellitus, Experimental”, “Diabetes Mellitus Type 1”, “Diabetes Mellitus Type 2”). The citation network consists of 44,338 links. Each publication in the dataset is described by a TF-IDF weighted word vector from a dictionary which consists of 500 unique words.For starters, experiments are performed on datasets in accordance to Karrer and Newman. These networks (Karate and PolBlogs) are featureless and only contain structural information. The Karate network is a commonly studied empirical benchmark network for community detection. Similar to [39], only the largest connected component and its undirected form are considered for Polblogs. Next, two networks containing features are used (Cora and Pubmed) [30, 50]. Table 1 summarizes the list of datasets and their respective properties.Table 1
Empirical network datasets.
Dataset Type Nodes Edges Clusters (K) Features Karate Social 34 78 2 N/A Polblogs Blogs 1,222 16,717 2 N/A Cora Citation 2,708 5,429 7 1,433 PubMed Citation 19,717 44,338 3 500


### 5.3. Baseline Methods

We establish a baseline by comparing against several state-of-the-art methods. These methods are divided into two categories. The first category comprises discriminative methods and the second category comprises generative methods.Discriminative Methods (i)
Spectral Clustering [9] is a commonly used approach for performing graph clustering. By identifying the Fiedler Vector of the Graph Laplacian, we can divide the network into two components. Repeating this process, the graph can be subdivided further, giving more clusters in the process. (ii)
Louvain [23] is a greedy modularity optimization method for maximizing modularity score. (iii)
DeepWalk [27], proposed by Perozziet al., is a network embedding method that performs a bias random walk on a given network. (iv)
node2vec [28] is a generalization of DeepWalk. It leverages on homophily and structural roles in embedding.Generative Methods (i)
Stochastic Blockmodel (SBM) [38, 39] is a state-of-the-art generative model. It models the likelihood of two nodes forming an edge on the basis of stochastic equivalence. Degree Correction (D.C.) penalizes the formation of single node modules by normalizing the node degrees. (ii)
Variational Graph Autoencoder [15] follows the Variational Autoencoder framework by leveraging on GCN layers.


### 5.4. Evaluation Metrics

Some of the common approaches to evaluate detected communities are Normalized Mutual Information (NMI), Variation of Information (VI), and Modularity. In some cases, accuracy can be accurately measured (i.e., when the number of clustersK is 2). Furthermore, these measures are only possible when ground truth exists. Hence, we include other forms of measures which consider the quality of a partition without ground truths.


#### 5.4.1. Ground Truth

(i)
Accuracy measures the number of correctly classified clusters given the ground truth. Formally, given two sets of community labels, i.e.,C being the ground truth and C′ the detected community label, the accuracy can be calculated by (19)ACCC′=∑i=1Cδci,ci′C×100%. c i ∈ C, ci′∈C′, where δ(·) denotes the Kronecker delta, δ(ci,ci′)=1 when both labels match, and · denotes the cardinality of a set. For clustering tasks, accuracy is usually not emphasized as labels are known to oscillate between clusters. (ii)
NMI and VI are based on information theory. Essentially, NMI measures the “similarity” between two community covers, while VI measures their “disimilarity” in terms of uncertainty. Correspondingly, a higher NMI indicates a better match between both covers while VI indicates the opposite. Formally [51] (20)NMIC,C′=2IC,C′HC+HC′ and(21)VIC,C′=HC+HC′-2IC,C′, where H(·) is the entropy function and IC,C′=HC+HC′-HC,C′ is the mutual information function.


#### 5.4.2. Community Quality

(i)
Modularity (Q) [17] measures the quality of a particular community structure when compared to a null (random) model. Intuitively, intracommunity links are expected to be stronger than intercommunity links. Specifically,(22)Q=14m∑ijAij-kikj4mδci,cj, whereAij-kikj/4m measures the actual edge connectivity versus the expectation at random and δ(ci,cj) defines the Kronecker delta, where δ(ci,cj)=1 when both nodes i and j belong to the same community, and 0 otherwise. Essentially, Q approaches 1 when the partitions are considered good. (ii)
Conductance (CON) [52, 53] measures the separability of a community across the fraction of outgoing local volume of links in the community, which is defined as (23)CONC=∑i∈C,j∈C′Aijmin⁡aC,aC′, where the nominator defines the total number of edges within communityC and a(C)=∑i∈C‍(j∈V) defines the volume of set C⊆V. A better local separability of community is achieved when the overall conductance value is the smallest. (iii)
Triangle Participation Ratio (TPR) [53] measures the fraction of triads within the community C. (24)TPRC=vi∈C,vj,vk:vj,vk∈C,vi,vj,vj,vk,vi,vk∈E≠∅C, whereE denotes the total number of edges in the graph G. A larger TPR value indicates a denser community structure.


### 5.5. Experiment Settings

For discriminative models such as node2vec and DeepWalk, the latent representation is learned first. Next,k-means is applied to the learned latent vector with K given a priori. The parameters used for node2vec are performed using exhaustive search on variables p,q∈{0.25,0.5,1,2,4} as suggested in [28]. Specifically, the parameters obtained were (p=0.5,q=4), (p=0.25,q=0.25), (p=1,q=0.25), and (p=0.5,q=1) for Karate, PolBlogs, Cora, and PubMed, respectively. As for DeepWalk, the parameters used are d=128, r=10, l=80, and k=10 which were the suggested values [27]. On the other hand, generative models like SBM (and D.C.) have several optimization strategies. In this case, we applied the Expectation-Maximization (EM) algorithm as suggested in [39].For a fair comparison between VGAE and VGAECD, we used identical layer configurations for both models. The layer configurations are (32-16), (32-16), (32-8), and (32-8) for Karate, PolBlogs, Cora, and PubMed, respectively. These configurations are determined empirically as suggested in [15]. Generally, we found the first layer to be insensitive and second layer to be sensitive. By reducing the size of the second layer with respect to the number nodes we found that 8 was ideal for Cora and PubMed. The hyperparameter K is given a priori for all methods. For a fair comparison, the average of 10 runs was taken for both discriminative and generative models. All experiments were conducted on an Ubuntu 16.06 LTS machine with 64 GB of RAM and two GeForce GTX 1080 Ti graphics cards.


### 5.6. Experiment Results

We first compare our result with 8 baseline methods on several state-of-the-art methods that employ unsupervised network embedding, except SBM: the only generative model that does learn a network embedding. Since VGAE is nonclustering, the two-step approach for clustering was applied, i.e., obtaining the latent vectors and subsequently applyingk-means. The ∗ symbol denotes methods that were confined to structural information only.


#### 5.6.1. Synthetic Dataset Performance

Figure2 depicts the performance of the proposed model in comparison to other methods. In Figure 2(a), VGAECD can be seen as a strong performer when zout≥4. On the LFR benchmark graph in Figure 2(b), the performance of VGAECD is comparable to other methods. When μ<0.4, VGAECD is capable of outperforming other methods. When μ>0.55, VGAECD is seen to exhibit similar performance to other methods. In both cases, the performance was as expected since the mixing parameter (zout and μ) is consistent with the study recoverability limit in planted partitions [42, 43].Figure 2
Comparative performance of VGAECD against other methods on synthetic networks.
(a)
GN benchmark graph (b)
LFR benchmark graph


#### 5.6.2. Empirical Dataset Performance

Experiments performed on four different empirical datasets are shown in Tables2, 3, 4, and 5 for Karate, PolBlogs, Cora, and PubMed, respectively. We measure the performance of clusters found using metrics as proposed in the Section 5.4 and the best values are marked in bold.Table 2
Experimental results on Karate dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.2297 2.0005 0.7353 0.1127 0.3702 0.7363 Louvain 0.4900 1.5205 0.3235 0.4188 0.2879 0.7333 DeepWalk 0.7198 0.8812 0.9353 0.3582 0.1337 0.9353 node2vec 0.8372 0.8050 0.9706 0.1639 0.4239 0.4549  Stochastic Blockmodel 0.0105 1.1032 0.4412 -0.2084 0.7154 0.4034 Stochastic Blockmodel (D.C) 0.8372 0.8050 0.9706 0.3718 0.1282 0.9412 VGAE∗ +k-means 0.6486 0.8189 0.9647 0.3669 0.1295 0.9407 VGAECD∗ 1.0000 0.6931 1.0000 0.3582 0.1412 0.9412Table 3
Experimental results on PolBlogs dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0014 1.1152 0.4828 -0.0578 0.5585 0.7221 Louvain 0.6446 1.0839 0.9149 0.2987 0.8130 0.1922 DeepWalk 0.7367 1.0839 0.9543 0.0980 0.3873 0.6870 node2vec 0.7545 0.8613 0.9586 0.1011 0.3827 0.6863  Stochastic Blockmodel 0.0002 1.2957 0.4905 -0.0235 0.5329 0.5657 Stochastic Blockmodel (D.C) 0.7145 0.8890 0.9496 0.4256 0.0730 0.8101 VGAE∗ +k-means 0.7361 0.8750 0.9552 0.4238 0.0752 0.8089 VGAECD∗ 0.7583 0.8583 0.9601 0.4112 0.0880 0.7913Table 4
Experimental results on Cora dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0651 2.0005 0.1252 0.0189 0.1909 0.6196 Louvain 0.4336 4.0978 0.0081 0.8142 0.0326 0.2821 DeepWalk 0.3796 2.7300 0.1626 0.6595 0.0396 0.4949 node2vec 0.3533 2.9947 0.1359 0.6813 0.1078 0.4902  Stochastic Blockmodel 0.0917 3.5108 0.1639 0.4068 0.4280 0.3376 Stochastic Blockmodel (D.C.) 0.1679 3.4547 0.1176 0.6809 0.1736 0.5112 VGAE∗ +k-means 0.2384 3.3151 0.1033 0.6911 0.1615 0.4906 VGAE +k-means 0.3173 3.1277 0.1589 0.6981 0.1517 0.5031 VGAECD∗ 0.2822 3.1606 0.1532 0.6674 0.1808 0.5076 VGAECD 0.5072 2.7787 0.1101 0.7029 0.1371 0.4987Table 5
Experimental results on PubMed dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0382 1.4341 0.3261 0.0414 0.5645 0.4935 Louvain 0.1983 3.6667 0.0954 0.7726 0.1388 0.1592 DeepWalk 0.2946 1.7865 0.3101 0.5766 0.0499 0.2461 node2vec 0.1197 1.9849 0.2228 0.3501 0.3170 0.2269  Stochastic Blockmodel 0.0004 1.9340 0.3080 -0.1620 0.1038 0.1965 Stochastic Blockmodel (D.C.) 0.1325 2.0035 0.3118 0.5622 0.8121 0.2441 VGAE∗ +k-means 0.2041 1.8096 0.3724 0.5273 0.1320 0.2898 VGAE +k-means 0.1981 1.8114 0.2751 0.5297 0.1283 0.2900 VGAECD∗ 0.1642 1.8320 0.1956 0.4966 0.1252 0.2692 VGAECD 0.3252 1.7056 0.4216 0.6878 0.1636 0.4827Generally, the experiments revealed that our method outperforms other methods when ground truth is given. In terms of cluster quality, VGAECD performs relatively well in terms of modularity score (Q). However, it retains competitiveness on Conductance (CON) and Triangle Participation Ratroio (TPR) measures. Since datasets such as Cora and PubMed have more than 2 clusters (K>2), the accuracy of labels can be affected by label oscillation. Therefore, it is a less accurate measure for measuring cluster’s label when compared to classification accuracy measures. However, accurate measures can still be obtained for datasets with only two clusters such as Karate and PolBlogs, which revealed that the proposed method is better than baseline methods. In most cases, the results of our method are comparable to SBM (D.C.). This is plausible since SBM (D.C.) has an advantage due to its prior knowledge on degree normalization. Regardless, when more than two clusters are given, the modularity score of VGAECD outperforms SBM (D.C.) as shown in Cora and PubMed datasets.


#### 5.6.3. Time Complexity Analysis

Since the proposed model follows the VAE framework, it employs a similar optimization method using SGVB. Therefore, it follows a linear-time complexity for one epoch, but requiresL number of runs to achieve convergence. The convergence rate of NMI with respect to the number of epochs can be observed in Figure 3 in comparison to VGAE. In contrast to VGAE, the proposed method can achieve convergence at a faster rate.Figure 3
NMI convergence comparison.


#### 5.6.4. Synthetic Network Generation

The implication of a generative model is its ability to generate a graph when prescribed a certain set of parameters. Therefore, a synthetic network can be generated using the proposed VGAECD model. Given parametersc and ω, we can generate a network simply by following the generative process specified in Section 4.2. However, in order to vary the community structure, we can follow the planted partition’s approach by including the mixing of a random network model:(25)ω=λωplanted+1-λωrandom.ωplanted defines the amount of actual draws from the Gaussian Mixture model and ωrandom draws from the random model. For instance, ωplanted can be specified as (26)ωplanted=n1,n2,n3,n4,where nc denotes the number of draws from the mixture model with μc and σc. In (26), we specify the number of nodes drawn for four different communities. A generated matrix A~ can be obtained as shown in decoder part of Algorithm 1. Ideally, each node is represented by z, and the Hadamard product between zi and zj determines the likelihood of edge connectivity between nodes i and j which is obtained after the nonlinearity σ(·) function.


#### 5.6.5. Network Visualization

Community assignments for Cora dataset are visualized in Figure4. Since Cora has several disconnected nodes, only the largest connected component is visualized. Among them, VGAECD has closer resemblance to the ground truth’s cluster assignment. Notably VGAECD is able to recover a community structure in the center of the network. Additionally, it also has less tendency to cluster nodes that are far away which is seen in VGAE + k-means and SBM (D.C.). DeepWalk, however, appears to have a resolution problem, resulting in larger clusters merging together. This can be seen as the number of clusters depicted in the largest component is fewer than K=7. This problem is not observed in node2vec since the sampling strategies are generalization of DeepWalk. This generalization of p and q allows node2vec to explore more locations. In contrast, DeepWalk is highly restricted to visiting nodes within the pivot node’s vicinity. However, to achieve the observed results, node2vec requires a costly parameter search which is not ideal. Among the baseline methods, Spectral Clustering and Louvain appear to struggle in finding a community structure, even though they performed very well on synthetic benchmark graphs. Louvain in particular had a very competitive NMI score, but visually, the results are not very satisfactory.Figure 4
Visualization of community assignment on Cora Dataset (largest connected component).
(a)
Ground truth (b)
VGAECD (c)
Spectral clustering (d)
Louvain (e)
DeepWalk (f)
VGAE +k-means (g)
SBM (D.C.) (h)
node2vec


## 5.1. Synthetic Datasets

Two synthetic networks are used in our evaluation. We consider two most common benchmark graphs used for benchmarking community detection algorithm. Namely, we used the Girvan-Newman (GN) benchmark graph [1, 34, 46] and the LFR benchmark graph [35]. The GN benchmark graph is a variant of the planted l-partition. In our experiment, we vary the zout value from a range of {1,…,8}. Each node has an average degree of k=16, with 32 nodes in each community (a total of 128 nodes) and 4 communities in total.The LFR benchmark graph is an extension of the GN benchmark graph. It is considered to be more realistic than the GN benchmark graph. It introduces a skewed degree distribution and accounts for network heterogeneity, resulting in communities that are generated in different sizes. The LFR benchmark graph is generated using default parameters as suggested by Lancichinettiet al. [35]. These parameters are number of nodes (N=1000), average degree (k=15), and minimum (cmin=30) and maximum (cmax=50) number of nodes per community. The generation follows thescale-free parameters settings of exponents τ1=-2 and τ2=-1, respectively. On average, between 20 and 30 communities are generated.


## 5.2. Empirical Datasets

The empirical datasets are divided into two kinds: networks with features and without features. The datasets are as follows:(i)
Karate: a social network represents friendship among 34 members of a karate club at a US University [47].(ii)
PolBlogs: a network of political blogs assembled by Adamic and Glance [48]. The nodes are blogs and web links between them are represented by their edge. These blogs have known political leanings and were labelled by hand by Adamic and Glance.(iii)
Cora: a citation network with 2,708 nodes and 5,429 edges. Each node corresponds to a document and the edges are citation links [49].(iv)
PubMed: A network consisting of 19,717 scientific publications from PubMed database pertaining to diabetes was classified into one of three classes (“Diabetes Mellitus, Experimental”, “Diabetes Mellitus Type 1”, “Diabetes Mellitus Type 2”). The citation network consists of 44,338 links. Each publication in the dataset is described by a TF-IDF weighted word vector from a dictionary which consists of 500 unique words.For starters, experiments are performed on datasets in accordance to Karrer and Newman. These networks (Karate and PolBlogs) are featureless and only contain structural information. The Karate network is a commonly studied empirical benchmark network for community detection. Similar to [39], only the largest connected component and its undirected form are considered for Polblogs. Next, two networks containing features are used (Cora and Pubmed) [30, 50]. Table 1 summarizes the list of datasets and their respective properties.Table 1
Empirical network datasets.
Dataset Type Nodes Edges Clusters (K) Features Karate Social 34 78 2 N/A Polblogs Blogs 1,222 16,717 2 N/A Cora Citation 2,708 5,429 7 1,433 PubMed Citation 19,717 44,338 3 500


## 5.3. Baseline Methods

We establish a baseline by comparing against several state-of-the-art methods. These methods are divided into two categories. The first category comprises discriminative methods and the second category comprises generative methods.Discriminative Methods (i)
Spectral Clustering [9] is a commonly used approach for performing graph clustering. By identifying the Fiedler Vector of the Graph Laplacian, we can divide the network into two components. Repeating this process, the graph can be subdivided further, giving more clusters in the process. (ii)
Louvain [23] is a greedy modularity optimization method for maximizing modularity score. (iii)
DeepWalk [27], proposed by Perozziet al., is a network embedding method that performs a bias random walk on a given network. (iv)
node2vec [28] is a generalization of DeepWalk. It leverages on homophily and structural roles in embedding.Generative Methods (i)
Stochastic Blockmodel (SBM) [38, 39] is a state-of-the-art generative model. It models the likelihood of two nodes forming an edge on the basis of stochastic equivalence. Degree Correction (D.C.) penalizes the formation of single node modules by normalizing the node degrees. (ii)
Variational Graph Autoencoder [15] follows the Variational Autoencoder framework by leveraging on GCN layers.


## 5.4. Evaluation Metrics

Some of the common approaches to evaluate detected communities are Normalized Mutual Information (NMI), Variation of Information (VI), and Modularity. In some cases, accuracy can be accurately measured (i.e., when the number of clustersK is 2). Furthermore, these measures are only possible when ground truth exists. Hence, we include other forms of measures which consider the quality of a partition without ground truths.


### 5.4.1. Ground Truth

(i)
Accuracy measures the number of correctly classified clusters given the ground truth. Formally, given two sets of community labels, i.e.,C being the ground truth and C′ the detected community label, the accuracy can be calculated by (19)ACCC′=∑i=1Cδci,ci′C×100%. c i ∈ C, ci′∈C′, where δ(·) denotes the Kronecker delta, δ(ci,ci′)=1 when both labels match, and · denotes the cardinality of a set. For clustering tasks, accuracy is usually not emphasized as labels are known to oscillate between clusters. (ii)
NMI and VI are based on information theory. Essentially, NMI measures the “similarity” between two community covers, while VI measures their “disimilarity” in terms of uncertainty. Correspondingly, a higher NMI indicates a better match between both covers while VI indicates the opposite. Formally [51] (20)NMIC,C′=2IC,C′HC+HC′ and(21)VIC,C′=HC+HC′-2IC,C′, where H(·) is the entropy function and IC,C′=HC+HC′-HC,C′ is the mutual information function.


### 5.4.2. Community Quality

(i)
Modularity (Q) [17] measures the quality of a particular community structure when compared to a null (random) model. Intuitively, intracommunity links are expected to be stronger than intercommunity links. Specifically,(22)Q=14m∑ijAij-kikj4mδci,cj, whereAij-kikj/4m measures the actual edge connectivity versus the expectation at random and δ(ci,cj) defines the Kronecker delta, where δ(ci,cj)=1 when both nodes i and j belong to the same community, and 0 otherwise. Essentially, Q approaches 1 when the partitions are considered good. (ii)
Conductance (CON) [52, 53] measures the separability of a community across the fraction of outgoing local volume of links in the community, which is defined as (23)CONC=∑i∈C,j∈C′Aijmin⁡aC,aC′, where the nominator defines the total number of edges within communityC and a(C)=∑i∈C‍(j∈V) defines the volume of set C⊆V. A better local separability of community is achieved when the overall conductance value is the smallest. (iii)
Triangle Participation Ratio (TPR) [53] measures the fraction of triads within the community C. (24)TPRC=vi∈C,vj,vk:vj,vk∈C,vi,vj,vj,vk,vi,vk∈E≠∅C, whereE denotes the total number of edges in the graph G. A larger TPR value indicates a denser community structure.


## 5.4.1. Ground Truth

(i)
Accuracy measures the number of correctly classified clusters given the ground truth. Formally, given two sets of community labels, i.e.,C being the ground truth and C′ the detected community label, the accuracy can be calculated by (19)ACCC′=∑i=1Cδci,ci′C×100%. c i ∈ C, ci′∈C′, where δ(·) denotes the Kronecker delta, δ(ci,ci′)=1 when both labels match, and · denotes the cardinality of a set. For clustering tasks, accuracy is usually not emphasized as labels are known to oscillate between clusters. (ii)
NMI and VI are based on information theory. Essentially, NMI measures the “similarity” between two community covers, while VI measures their “disimilarity” in terms of uncertainty. Correspondingly, a higher NMI indicates a better match between both covers while VI indicates the opposite. Formally [51] (20)NMIC,C′=2IC,C′HC+HC′ and(21)VIC,C′=HC+HC′-2IC,C′, where H(·) is the entropy function and IC,C′=HC+HC′-HC,C′ is the mutual information function.


## 5.4.2. Community Quality

(i)
Modularity (Q) [17] measures the quality of a particular community structure when compared to a null (random) model. Intuitively, intracommunity links are expected to be stronger than intercommunity links. Specifically,(22)Q=14m∑ijAij-kikj4mδci,cj, whereAij-kikj/4m measures the actual edge connectivity versus the expectation at random and δ(ci,cj) defines the Kronecker delta, where δ(ci,cj)=1 when both nodes i and j belong to the same community, and 0 otherwise. Essentially, Q approaches 1 when the partitions are considered good. (ii)
Conductance (CON) [52, 53] measures the separability of a community across the fraction of outgoing local volume of links in the community, which is defined as (23)CONC=∑i∈C,j∈C′Aijmin⁡aC,aC′, where the nominator defines the total number of edges within communityC and a(C)=∑i∈C‍(j∈V) defines the volume of set C⊆V. A better local separability of community is achieved when the overall conductance value is the smallest. (iii)
Triangle Participation Ratio (TPR) [53] measures the fraction of triads within the community C. (24)TPRC=vi∈C,vj,vk:vj,vk∈C,vi,vj,vj,vk,vi,vk∈E≠∅C, whereE denotes the total number of edges in the graph G. A larger TPR value indicates a denser community structure.


## 5.5. Experiment Settings

For discriminative models such as node2vec and DeepWalk, the latent representation is learned first. Next,k-means is applied to the learned latent vector with K given a priori. The parameters used for node2vec are performed using exhaustive search on variables p,q∈{0.25,0.5,1,2,4} as suggested in [28]. Specifically, the parameters obtained were (p=0.5,q=4), (p=0.25,q=0.25), (p=1,q=0.25), and (p=0.5,q=1) for Karate, PolBlogs, Cora, and PubMed, respectively. As for DeepWalk, the parameters used are d=128, r=10, l=80, and k=10 which were the suggested values [27]. On the other hand, generative models like SBM (and D.C.) have several optimization strategies. In this case, we applied the Expectation-Maximization (EM) algorithm as suggested in [39].For a fair comparison between VGAE and VGAECD, we used identical layer configurations for both models. The layer configurations are (32-16), (32-16), (32-8), and (32-8) for Karate, PolBlogs, Cora, and PubMed, respectively. These configurations are determined empirically as suggested in [15]. Generally, we found the first layer to be insensitive and second layer to be sensitive. By reducing the size of the second layer with respect to the number nodes we found that 8 was ideal for Cora and PubMed. The hyperparameter K is given a priori for all methods. For a fair comparison, the average of 10 runs was taken for both discriminative and generative models. All experiments were conducted on an Ubuntu 16.06 LTS machine with 64 GB of RAM and two GeForce GTX 1080 Ti graphics cards.


## 5.6. Experiment Results

We first compare our result with 8 baseline methods on several state-of-the-art methods that employ unsupervised network embedding, except SBM: the only generative model that does learn a network embedding. Since VGAE is nonclustering, the two-step approach for clustering was applied, i.e., obtaining the latent vectors and subsequently applyingk-means. The ∗ symbol denotes methods that were confined to structural information only.


### 5.6.1. Synthetic Dataset Performance

Figure2 depicts the performance of the proposed model in comparison to other methods. In Figure 2(a), VGAECD can be seen as a strong performer when zout≥4. On the LFR benchmark graph in Figure 2(b), the performance of VGAECD is comparable to other methods. When μ<0.4, VGAECD is capable of outperforming other methods. When μ>0.55, VGAECD is seen to exhibit similar performance to other methods. In both cases, the performance was as expected since the mixing parameter (zout and μ) is consistent with the study recoverability limit in planted partitions [42, 43].Figure 2
Comparative performance of VGAECD against other methods on synthetic networks.
(a)
GN benchmark graph (b)
LFR benchmark graph


### 5.6.2. Empirical Dataset Performance

Experiments performed on four different empirical datasets are shown in Tables2, 3, 4, and 5 for Karate, PolBlogs, Cora, and PubMed, respectively. We measure the performance of clusters found using metrics as proposed in the Section 5.4 and the best values are marked in bold.Table 2
Experimental results on Karate dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.2297 2.0005 0.7353 0.1127 0.3702 0.7363 Louvain 0.4900 1.5205 0.3235 0.4188 0.2879 0.7333 DeepWalk 0.7198 0.8812 0.9353 0.3582 0.1337 0.9353 node2vec 0.8372 0.8050 0.9706 0.1639 0.4239 0.4549  Stochastic Blockmodel 0.0105 1.1032 0.4412 -0.2084 0.7154 0.4034 Stochastic Blockmodel (D.C) 0.8372 0.8050 0.9706 0.3718 0.1282 0.9412 VGAE∗ +k-means 0.6486 0.8189 0.9647 0.3669 0.1295 0.9407 VGAECD∗ 1.0000 0.6931 1.0000 0.3582 0.1412 0.9412Table 3
Experimental results on PolBlogs dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0014 1.1152 0.4828 -0.0578 0.5585 0.7221 Louvain 0.6446 1.0839 0.9149 0.2987 0.8130 0.1922 DeepWalk 0.7367 1.0839 0.9543 0.0980 0.3873 0.6870 node2vec 0.7545 0.8613 0.9586 0.1011 0.3827 0.6863  Stochastic Blockmodel 0.0002 1.2957 0.4905 -0.0235 0.5329 0.5657 Stochastic Blockmodel (D.C) 0.7145 0.8890 0.9496 0.4256 0.0730 0.8101 VGAE∗ +k-means 0.7361 0.8750 0.9552 0.4238 0.0752 0.8089 VGAECD∗ 0.7583 0.8583 0.9601 0.4112 0.0880 0.7913Table 4
Experimental results on Cora dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0651 2.0005 0.1252 0.0189 0.1909 0.6196 Louvain 0.4336 4.0978 0.0081 0.8142 0.0326 0.2821 DeepWalk 0.3796 2.7300 0.1626 0.6595 0.0396 0.4949 node2vec 0.3533 2.9947 0.1359 0.6813 0.1078 0.4902  Stochastic Blockmodel 0.0917 3.5108 0.1639 0.4068 0.4280 0.3376 Stochastic Blockmodel (D.C.) 0.1679 3.4547 0.1176 0.6809 0.1736 0.5112 VGAE∗ +k-means 0.2384 3.3151 0.1033 0.6911 0.1615 0.4906 VGAE +k-means 0.3173 3.1277 0.1589 0.6981 0.1517 0.5031 VGAECD∗ 0.2822 3.1606 0.1532 0.6674 0.1808 0.5076 VGAECD 0.5072 2.7787 0.1101 0.7029 0.1371 0.4987Table 5
Experimental results on PubMed dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0382 1.4341 0.3261 0.0414 0.5645 0.4935 Louvain 0.1983 3.6667 0.0954 0.7726 0.1388 0.1592 DeepWalk 0.2946 1.7865 0.3101 0.5766 0.0499 0.2461 node2vec 0.1197 1.9849 0.2228 0.3501 0.3170 0.2269  Stochastic Blockmodel 0.0004 1.9340 0.3080 -0.1620 0.1038 0.1965 Stochastic Blockmodel (D.C.) 0.1325 2.0035 0.3118 0.5622 0.8121 0.2441 VGAE∗ +k-means 0.2041 1.8096 0.3724 0.5273 0.1320 0.2898 VGAE +k-means 0.1981 1.8114 0.2751 0.5297 0.1283 0.2900 VGAECD∗ 0.1642 1.8320 0.1956 0.4966 0.1252 0.2692 VGAECD 0.3252 1.7056 0.4216 0.6878 0.1636 0.4827Generally, the experiments revealed that our method outperforms other methods when ground truth is given. In terms of cluster quality, VGAECD performs relatively well in terms of modularity score (Q). However, it retains competitiveness on Conductance (CON) and Triangle Participation Ratroio (TPR) measures. Since datasets such as Cora and PubMed have more than 2 clusters (K>2), the accuracy of labels can be affected by label oscillation. Therefore, it is a less accurate measure for measuring cluster’s label when compared to classification accuracy measures. However, accurate measures can still be obtained for datasets with only two clusters such as Karate and PolBlogs, which revealed that the proposed method is better than baseline methods. In most cases, the results of our method are comparable to SBM (D.C.). This is plausible since SBM (D.C.) has an advantage due to its prior knowledge on degree normalization. Regardless, when more than two clusters are given, the modularity score of VGAECD outperforms SBM (D.C.) as shown in Cora and PubMed datasets.


### 5.6.3. Time Complexity Analysis

Since the proposed model follows the VAE framework, it employs a similar optimization method using SGVB. Therefore, it follows a linear-time complexity for one epoch, but requiresL number of runs to achieve convergence. The convergence rate of NMI with respect to the number of epochs can be observed in Figure 3 in comparison to VGAE. In contrast to VGAE, the proposed method can achieve convergence at a faster rate.Figure 3
NMI convergence comparison.


### 5.6.4. Synthetic Network Generation

The implication of a generative model is its ability to generate a graph when prescribed a certain set of parameters. Therefore, a synthetic network can be generated using the proposed VGAECD model. Given parametersc and ω, we can generate a network simply by following the generative process specified in Section 4.2. However, in order to vary the community structure, we can follow the planted partition’s approach by including the mixing of a random network model:(25)ω=λωplanted+1-λωrandom.ωplanted defines the amount of actual draws from the Gaussian Mixture model and ωrandom draws from the random model. For instance, ωplanted can be specified as (26)ωplanted=n1,n2,n3,n4,where nc denotes the number of draws from the mixture model with μc and σc. In (26), we specify the number of nodes drawn for four different communities. A generated matrix A~ can be obtained as shown in decoder part of Algorithm 1. Ideally, each node is represented by z, and the Hadamard product between zi and zj determines the likelihood of edge connectivity between nodes i and j which is obtained after the nonlinearity σ(·) function.


### 5.6.5. Network Visualization

Community assignments for Cora dataset are visualized in Figure4. Since Cora has several disconnected nodes, only the largest connected component is visualized. Among them, VGAECD has closer resemblance to the ground truth’s cluster assignment. Notably VGAECD is able to recover a community structure in the center of the network. Additionally, it also has less tendency to cluster nodes that are far away which is seen in VGAE + k-means and SBM (D.C.). DeepWalk, however, appears to have a resolution problem, resulting in larger clusters merging together. This can be seen as the number of clusters depicted in the largest component is fewer than K=7. This problem is not observed in node2vec since the sampling strategies are generalization of DeepWalk. This generalization of p and q allows node2vec to explore more locations. In contrast, DeepWalk is highly restricted to visiting nodes within the pivot node’s vicinity. However, to achieve the observed results, node2vec requires a costly parameter search which is not ideal. Among the baseline methods, Spectral Clustering and Louvain appear to struggle in finding a community structure, even though they performed very well on synthetic benchmark graphs. Louvain in particular had a very competitive NMI score, but visually, the results are not very satisfactory.Figure 4
Visualization of community assignment on Cora Dataset (largest connected component).
(a)
Ground truth (b)
VGAECD (c)
Spectral clustering (d)
Louvain (e)
DeepWalk (f)
VGAE +k-means (g)
SBM (D.C.) (h)
node2vec


## 5.6.1. Synthetic Dataset Performance

Figure2 depicts the performance of the proposed model in comparison to other methods. In Figure 2(a), VGAECD can be seen as a strong performer when zout≥4. On the LFR benchmark graph in Figure 2(b), the performance of VGAECD is comparable to other methods. When μ<0.4, VGAECD is capable of outperforming other methods. When μ>0.55, VGAECD is seen to exhibit similar performance to other methods. In both cases, the performance was as expected since the mixing parameter (zout and μ) is consistent with the study recoverability limit in planted partitions [42, 43].Figure 2
Comparative performance of VGAECD against other methods on synthetic networks.
(a)
GN benchmark graph (b)
LFR benchmark graph


## 5.6.2. Empirical Dataset Performance

Experiments performed on four different empirical datasets are shown in Tables2, 3, 4, and 5 for Karate, PolBlogs, Cora, and PubMed, respectively. We measure the performance of clusters found using metrics as proposed in the Section 5.4 and the best values are marked in bold.Table 2
Experimental results on Karate dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.2297 2.0005 0.7353 0.1127 0.3702 0.7363 Louvain 0.4900 1.5205 0.3235 0.4188 0.2879 0.7333 DeepWalk 0.7198 0.8812 0.9353 0.3582 0.1337 0.9353 node2vec 0.8372 0.8050 0.9706 0.1639 0.4239 0.4549  Stochastic Blockmodel 0.0105 1.1032 0.4412 -0.2084 0.7154 0.4034 Stochastic Blockmodel (D.C) 0.8372 0.8050 0.9706 0.3718 0.1282 0.9412 VGAE∗ +k-means 0.6486 0.8189 0.9647 0.3669 0.1295 0.9407 VGAECD∗ 1.0000 0.6931 1.0000 0.3582 0.1412 0.9412Table 3
Experimental results on PolBlogs dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0014 1.1152 0.4828 -0.0578 0.5585 0.7221 Louvain 0.6446 1.0839 0.9149 0.2987 0.8130 0.1922 DeepWalk 0.7367 1.0839 0.9543 0.0980 0.3873 0.6870 node2vec 0.7545 0.8613 0.9586 0.1011 0.3827 0.6863  Stochastic Blockmodel 0.0002 1.2957 0.4905 -0.0235 0.5329 0.5657 Stochastic Blockmodel (D.C) 0.7145 0.8890 0.9496 0.4256 0.0730 0.8101 VGAE∗ +k-means 0.7361 0.8750 0.9552 0.4238 0.0752 0.8089 VGAECD∗ 0.7583 0.8583 0.9601 0.4112 0.0880 0.7913Table 4
Experimental results on Cora dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0651 2.0005 0.1252 0.0189 0.1909 0.6196 Louvain 0.4336 4.0978 0.0081 0.8142 0.0326 0.2821 DeepWalk 0.3796 2.7300 0.1626 0.6595 0.0396 0.4949 node2vec 0.3533 2.9947 0.1359 0.6813 0.1078 0.4902  Stochastic Blockmodel 0.0917 3.5108 0.1639 0.4068 0.4280 0.3376 Stochastic Blockmodel (D.C.) 0.1679 3.4547 0.1176 0.6809 0.1736 0.5112 VGAE∗ +k-means 0.2384 3.3151 0.1033 0.6911 0.1615 0.4906 VGAE +k-means 0.3173 3.1277 0.1589 0.6981 0.1517 0.5031 VGAECD∗ 0.2822 3.1606 0.1532 0.6674 0.1808 0.5076 VGAECD 0.5072 2.7787 0.1101 0.7029 0.1371 0.4987Table 5
Experimental results on PubMed dataset.
NMI (↑) VI (↓) ACC (↑) Q (↑) CON (↓) TPR (↑) Spectral Clustering 0.0382 1.4341 0.3261 0.0414 0.5645 0.4935 Louvain 0.1983 3.6667 0.0954 0.7726 0.1388 0.1592 DeepWalk 0.2946 1.7865 0.3101 0.5766 0.0499 0.2461 node2vec 0.1197 1.9849 0.2228 0.3501 0.3170 0.2269  Stochastic Blockmodel 0.0004 1.9340 0.3080 -0.1620 0.1038 0.1965 Stochastic Blockmodel (D.C.) 0.1325 2.0035 0.3118 0.5622 0.8121 0.2441 VGAE∗ +k-means 0.2041 1.8096 0.3724 0.5273 0.1320 0.2898 VGAE +k-means 0.1981 1.8114 0.2751 0.5297 0.1283 0.2900 VGAECD∗ 0.1642 1.8320 0.1956 0.4966 0.1252 0.2692 VGAECD 0.3252 1.7056 0.4216 0.6878 0.1636 0.4827Generally, the experiments revealed that our method outperforms other methods when ground truth is given. In terms of cluster quality, VGAECD performs relatively well in terms of modularity score (Q). However, it retains competitiveness on Conductance (CON) and Triangle Participation Ratroio (TPR) measures. Since datasets such as Cora and PubMed have more than 2 clusters (K>2), the accuracy of labels can be affected by label oscillation. Therefore, it is a less accurate measure for measuring cluster’s label when compared to classification accuracy measures. However, accurate measures can still be obtained for datasets with only two clusters such as Karate and PolBlogs, which revealed that the proposed method is better than baseline methods. In most cases, the results of our method are comparable to SBM (D.C.). This is plausible since SBM (D.C.) has an advantage due to its prior knowledge on degree normalization. Regardless, when more than two clusters are given, the modularity score of VGAECD outperforms SBM (D.C.) as shown in Cora and PubMed datasets.


## 5.6.3. Time Complexity Analysis

Since the proposed model follows the VAE framework, it employs a similar optimization method using SGVB. Therefore, it follows a linear-time complexity for one epoch, but requiresL number of runs to achieve convergence. The convergence rate of NMI with respect to the number of epochs can be observed in Figure 3 in comparison to VGAE. In contrast to VGAE, the proposed method can achieve convergence at a faster rate.Figure 3
NMI convergence comparison.


## 5.6.4. Synthetic Network Generation

The implication of a generative model is its ability to generate a graph when prescribed a certain set of parameters. Therefore, a synthetic network can be generated using the proposed VGAECD model. Given parametersc and ω, we can generate a network simply by following the generative process specified in Section 4.2. However, in order to vary the community structure, we can follow the planted partition’s approach by including the mixing of a random network model:(25)ω=λωplanted+1-λωrandom.ωplanted defines the amount of actual draws from the Gaussian Mixture model and ωrandom draws from the random model. For instance, ωplanted can be specified as (26)ωplanted=n1,n2,n3,n4,where nc denotes the number of draws from the mixture model with μc and σc. In (26), we specify the number of nodes drawn for four different communities. A generated matrix A~ can be obtained as shown in decoder part of Algorithm 1. Ideally, each node is represented by z, and the Hadamard product between zi and zj determines the likelihood of edge connectivity between nodes i and j which is obtained after the nonlinearity σ(·) function.


## 5.6.5. Network Visualization

Community assignments for Cora dataset are visualized in Figure4. Since Cora has several disconnected nodes, only the largest connected component is visualized. Among them, VGAECD has closer resemblance to the ground truth’s cluster assignment. Notably VGAECD is able to recover a community structure in the center of the network. Additionally, it also has less tendency to cluster nodes that are far away which is seen in VGAE + k-means and SBM (D.C.). DeepWalk, however, appears to have a resolution problem, resulting in larger clusters merging together. This can be seen as the number of clusters depicted in the largest component is fewer than K=7. This problem is not observed in node2vec since the sampling strategies are generalization of DeepWalk. This generalization of p and q allows node2vec to explore more locations. In contrast, DeepWalk is highly restricted to visiting nodes within the pivot node’s vicinity. However, to achieve the observed results, node2vec requires a costly parameter search which is not ideal. Among the baseline methods, Spectral Clustering and Louvain appear to struggle in finding a community structure, even though they performed very well on synthetic benchmark graphs. Louvain in particular had a very competitive NMI score, but visually, the results are not very satisfactory.Figure 4
Visualization of community assignment on Cora Dataset (largest connected component).
(a)
Ground truth (b)
VGAECD (c)
Spectral clustering (d)
Louvain (e)
DeepWalk (f)
VGAE +k-means (g)
SBM (D.C.) (h)
node2vec


## 6. Conclusion

In this paper, we propose a novel community detection algorithm termed Variational Graph Autoencoder for community detection (VGAECD). It generalizes VGAE for community detection tasks. The model is capable of learning both features and structural information and encodes them into a community-aware latent representation. The low-dimensional representation learned differs from previous network representation methods. Concretely, the latent representations themselves are parameters to a probabilistic graphical model, i.e., the Gaussian Mixture Model. Therefore, this allows us to draw samples from the learned model itself and generate synthetic graphs like SBM. Additionally, the flexibility of the proposed method shows that, by leveraging on more feature information, it is capable of outperforming other methods in community structure recovery. Unlike other representation learning methods which require a two-step approach (applyingk-means as the second step), VGAECD is a generative model capable of recovering communities in a single step. Moreover, in comparison to existing state-of-the-art generative models such as SBM, VGAECD is community structure definition agnostic. Specifically, nodes are not forced to be similar under a specific similarity measure. This is an advantage over other community detection algorithms where the definition of community structures is always assumed. This is a desirable feature in cases where networks can have a mixture of community structures, i.e., multilayer networks.



---

*Source: 4867304-2018-12-13.xml*