Network-Specific Variational Auto-Encoder for Embedding in Attribute Networks

1 Introduction

Network embedding (NE) is to learn a low-dimensional distributed representation for each node in a network and at the same time preserve the relationships among the nodes in the network. The learned embedding can be applied to many applications, such as network classification and clustering.

Several different NE methods have been developed [Cui et al., 2018], many of which exploit network topological structures [Perozzi et al., 2014; Grover and Leskovec, 2016; Wang et al., 2016a]. Semantics on nodes or node attributes have also been introduced to supplement the topological information to improve the quality of NE [Zhang et al.,

∗Corresponding author.

2018a]. The existing NE methods adopt techniques from spectral optimization [Huang et al., 2017], random walk [Yang et al., 2015; Pan et al., 2016], matrix factorization [Yang et al., 2016] and Auto-Encoder (AE) [Liao et al., 2018; Jin et al., 2018; Tao et al., 2019]. In particular, AE based methods have attracted much attention lately because it can well capture highly non-linear relationships in networks.

However, learning an embedding by incorporating network topological and node semantic information altogether is nontrivial, and the dimension of the combined data is much higher than that of network topology alone. The encoders used in AEs typically have discrete outputs and learn a function to directly map the data, making it difficult to deal with high-dimensional data. To cope with this problem, Variational Auto-Encoder (VAE) [Kingma and Welling, 2014] has been introduced by adding a priori constraint to the learning of embedding. The encoder of VAE infers a posterior distribution of continuous latent variables given the observed input, instead of learning the discrete latent variables directly as did in AE. As a result, it is more suitable for high-dimensional and complex data such as networks. This advantage also motivates to employ VAE to learn embedding in attributed networks. For example, the method in [Kipf and Welling, 2016] uses a graph convolutional network as a decoder to embed an attribute network under the VAE framework. The method in [Li et al., 2017] employs the doc2vec method to learn an attribute vector representation, and then integrates it with the network topology in the VAE framework. The method in [Pan et al., 2019] proposes an adversarially regularized variational graph autoencoder by considering the topological structure and node semantics in networks.

Although these VAE methods have reasonable performance, they still have serious drawbacks. They typically use the same method to map the data of network topologies and node attributes, i.e., they use the same generative mechanism, e.g. conventional neural networks, to reconstruct network topologies and node attributes. It is critical to note that network topologies and node attributes are completely different types of data. The former reflects a coupling relationship among nodes, whereas the latter represents independent node semantics. They are generally produced by completely different mechanism in nature. The existing VAE methods, as well as many NE methods, do not differentiate these two types of information, making them ineffective for many applications.

To address this problem, we developed a new networkspecific VAE approach, named as NetVAE, for embedding attribute networks. NetVAE uses a shared encoder to compress altogether the information of network topology and information of node attribute to derive an embedding. By using a shared encoder, the information from two distinct sources can have a joint embedding and share a joint training process so as to perform a co-training for cross learning. In the process of decoding, NetVAE uses a dual decoder with two different generative mechanisms to reconstruct separately the network topologies and node attributes. It has been argued that a conventional fully connected neural network is suitable for reconstruction of features of individual variables. We adopt this scheme to reconstruct node attributes. To reconstruct network topologies, we take advantages of the nonlinear, modular structures that the encoder implicitly extracts when compressing the input network. To this end, we first introduce a Gaussian mixture model (GMM) to make such latent modular structures explicit, and then introduce a block model [Holland et al., 1983], an excellent model for network topologies, to directly exploit in the decoder such modular information for structure reconstruction. We formalize the GMM and block model as a neural network layer and integrate it into the VAE. In short, we make the following contributions.

• We developed a network-specific VAE for embedding of topological and attribute information of a network. This is the first time that these two types of information are processed differently in VAE for NE. We used the most suitable mechanisms to reconstruct network structures and node attributes separately.
• We introduced a GMM to make the nonlinear modular structures extracted by the encoder explicit so that such structures can be exploited in the decoder to improve overall embedding quality.
• We also introduced a novel network generation mechanism that combines the popular block model for networks and the GMM. The method can not only describe the inherent coupling relationship among nodes but also preserve network module structures, which helps improve the quality of embedding significantly.
• We formulated the GMM and the network generation method as an equivalent neural network layer and incorporate it in the overall VAE architecture so that an end-to-end training can be efficiently performed.

It is important to note that although our method was not originally designed for community detection, it can indeed be adopted to find communities as a by-product. Note that the dimension of the embedding does not necessarily have to be the same as the number of the actual communities in the given network, as long as the former is not smaller than the latter so that no intrinsic network property is lost after compression.

2 The Method

Let G = (V ,E) be an undirected attribute network with n nodes V = {v1,v2,...,vn} and e edges E= {eij} . The topological structures of G is specified by an adjacency matrix A ∈ Rn×n , and node semantics are represented by an attribute matrix X ∈ Rn×m of maximal m attributes. Given a network, network embedding is to learn an l ≪ n dimensional vector ui ∈ Rl for each node vi based on A and X.

2.1 Overview of the Method

The NetVAE method for embedding of attribute networks has two major components, a joint encoder and a dual decoder (Figure 1). The joint encoder maps both network topologies and node attributes jointly to derive the latent variables for the embedding of the network. The dual decoder uses two distinct generative methods to reconstruct network topologies and node attributes separately (Figure 1).

In the encoder of NetVAE, we concatenate to the network topologies and node attributes in a unified representation, and then encode the combined data using a fully connected neural network to learn the parameters, i.e., the mean and standard deviation, of the normally distributed variables of the target embedding. We then synthesize the latent variables of the embedding by using the two parameters along with a Gaussian noise.

In the decoder, we adopt two different methods to regenerate network structures and node attributes. We employ a fully connected neural network to reconstruct node attributes. We introduce a new generative mechanism that explicitly exploits the nonlinear modular structures of the original network. Note that the encoder, a neural network on its own, is able to extract the nonlinear modular structures hidden in the given network in such a way that nodes belonging to the same network module tend to be grouped together in the embedding. Such modular structures can be utilized to better re-construct the network structures. To do so, we introduce a Gaussian mixture model (GMM) to make the latent modular structures explicit in the embedding space and adopt a method, based on the block model (i.e. a popular tool for describing network with communities), to exploit the modular structures for reconstruction of network structures. We then formalize the new generationve method as a neural network. All of these components are then integrated under the framework of VAE.

2.2 The Shared Encoder

We first concatenate the two types of observed data, data of network topology in the adjacency matrix A and data of node semantics in the attribute matrix X, into a unified representation U = [A,X], where the row vector ui contains the adjacency list and attributes of node vi. We then use a fullyconnected neural network of three layers as the encoder to map each node to a nonlinear low-dimensional latent embedding space. In the first two layers of the encoder, the output of the t-th layer (for t = 1 or 2) is defined as:

where ˆh(0) i = ui , W(t) and b(t) are the weights and bias of the layers, and f(·) the activation function, such as ReLU (·), for layer t.

The outputs of the last or third layer of the encoder consist of two parameters µi and σi of the normally distributed latent variables of the embedding, which are calculated as follows,

where W(µ) and b(µ) are the weights and biases of the last layer for deriving µi, and W(σ) and b(σ) are that for σi. Following the reparameterization scheme in [Kingma and Welling, 2014], we use µi and σi as the mean and variance to synthesize the latent variable zi of the embedding of node vi as follows,

where εi is a noise sampled from the Gaussian distribution N(0, I) with zero mean and an identity covariance matrix I, and ◦ denotes the element-wise multiplication. Based on this neural network structure, we map each node vi to a latent variable zi in the low-dimensional embedding space.

To constrain the latent variable zi, as did in the original VAE [Kingma and Welling, 2014], we also impose a prior constraint, using the mean and variance of zi, to ensure the target distribution of zi to be a Gaussian distribution, i.e., we have the following constraint:

where DKL is the KL divergence. Z, µ and σ are respectively the variable sets of zi, µi and σi, l is the dimension of latent variable zi, and uji and σj i are the j-th elements of µi and σi. This constraint will be added to the loss function as a regularization term.

2.3 The Dual Decoder

Different from the shared encoder, the decoder is composed of two distinct sub-decoders to reconstruct separately the network topology and node attributes.

The Decoder for Reconstructing Network Structure

This is the core part of the dual decoder. We first discuss the main idea and formalize it as a neural network. We then introduce a neural network variant of the Gaussian Mixture Model (GMM) to help integrate it into the VAE architecture.

The scheme for network reconstruction. Assume that there are l network modules in the given network, and the nodes in each module have the same link pattern, i.e., all nodes in the same module share the same link probability when connecting to the other nodes. (The number of modules can be also smaller than the dimension of network embedding while we make them equal here without loss of generality.) To be specific, let Γ=(γik)n×l be the distributions of the module labels for the nodes in the network, where γik denotes the probability that node vi belongs to the k-th module, and Φ= (φrs)l×l be the distributions of the links across communities where φrs denotes the link probability between any two nodes in communities r and s, respectively, and φrs = φsr for undirected networks. We first sample the module labels gi for every node vi from a multinomial distribution with parameters γi, that is:

where γi=(γik)1×l denotes the probability distribution of the label of node vi over the modules. Now consider the link between nodes vi and vj, which may follow a Bernoulli distribution aij ∼ Bernoulli(φgigj ) with parameters φgigj . Essentially, this is to generate the network links according to l types of link patterns (each of which corresponding to a module), and thus naturally describes the coupling relationship between nodes in networks considering l network communities. Note that nodes with larger degrees are more likely to be connected. We then use didjφgigj to describe the link probability between nodes vi and vj, where di is the degree of vi. We then sample each link between vi and vj from a Bernoulli distribution with parameters didjφgigj , defined as:

By considering the node degrees, (6) better describes the coupling relationship between nodes coming from l communities. This matches well with the well-known stochastic block model [Karrer and Newman, 2011], which could generate networks with well-defined statistical properties.

Formulating network reconstruction in neural network. To make the above network generative process suitable for integration into VAE, we formulate it as a layer of neural network. For convenience, we use a l-dimension vector hi to represent the module gi for node vi, where hir = 1 if r = gi, or 0, otherwise, forming a module indicator matrix H = (hir)n×l for all nodes. The probability that nodes vi and vj are connected can then be revised to ˆaij=di(hiΦhTj )dj, which can also be written in matrix form as:

where B = (bij)n×n with bij = di × dj. Since B is a constant matrix and H can be sampled from the multinomial distribution over Γ following formula (5), we can formulate (7) as a layer of neural network by taking Φ as the weights of the layer which are to be learned in training of the neural network. We then sample the observed network topology A from a Bernoulli distribution over ˆA, the likelihood of which can be defined as: p (A|ˆA) = ∏ i<j ˆaaij ij (1- ˆaij)1-aij . Since maximizing this likelihood is the objective of the network generative process, we can then take the negative log-likelihood as the loss function of this layer of the neural network,

Converting latent variables to module memberships. This new network structure reconstruction method must also specify the probabilities that a node is assigned to the l modules (i.e. Γ ). Nevertheless, the encoder described above will instead learn a set of embedding latent variables Z. We need to convert the embedding variables into node module memberships. To this end, we introduce a neural network variation of the GMM into VAE. Given the latent variables Z = {z1, z2, ..., zn} and node module labels g = {g1, g2, ..., gn}, the log-likelihood under the GMM model can be defined as:

where π′k , µ′ k and σ′ k are the mixing coefficients, mean and covariance for the k-th module in GMM. We use θ to denote the set of all these parameters for convenience. By applying Jensen's inequality to (9), we derive a lower bound of the log likelihood as ξ (θ):

where the probability distribution qi (gi) in (10) can be freely chosen. The equality holds when qi (gi) is equal to the real posterior distribution. So we can derive it as follows:

Ignoring the item that are not related to parameters θ and marginalizing gi, ξ (θ) can be further written as:

To apply this lower bound to VAE, we introduce a layer of neural network instead of traditional Bayes rules to calculate the posterior distribution γi based on the latent variable zi, that is:

which serves as the E-step in the EM algorithm. Here, W(γ) and b(γ) are the weights and biases in this neural network layer. By setting the derivatives of ξ (θ) with respect to π′k , µ′ k and σ′ k to zero, we estimate the parameters as follows:

which collectively serve as the M-step in the EM algorithm.

Next, to integrate this GMM model into the neural network, we follow the technique proposed in [Zong et al., 2018] and add the following energy term E(zi) to every node based on the parameters in (14), i.e.,

We further calculate the average energy of all the n nodes,

which is added to the loss function of VAE. By minimizing the loss in training the neural network, we derive an accurate γi to be used for reconstructing network structures.

The Decoder for Reconstructing Node Attributes

Besides network topology, we also need to reconstruct the node attributes. To this end, we use the latent variable zi for each node vi as the input to a fully connected neural network to reconstruct node attributes. This is formulated in the same way as in (1) for the encoder, but with increased dimensions of the outputs layer by layer. We use the output of the last layer as the final reconstructed node attributes, denoted as ˆxi. The loss or objective function of this decoder is

where ℓ is the cross entropy between ˆxi and xi.

2.4 The UnifiedModel and its Optimization

To sum up, the loss function of the whole NetVAE model is defined as:

The training process is to minimize the loss function of a given network. The first two items, Lt in (8) and La in

(17), are the reconstruction errors of the network structures and node attributes, respectively. The third item, Lp in (4), is a prior constraint item, which encourages the distributions of the latent variables to match the prior distributions. The last item, Lc in (16), is the average energy from introducing GMM. The NetVAE can then be optimized via stochastic gradient descent in back-propagation. The overall complexity of this method is competitive with that of the original VAE.

3 Experimental Analysis

We validated and evaluated NetVAE on two widely used applications of network node classification and node clustering (i.e., community detection). Here we also present the results and an analysis to understand why the method works.

3.1 Experiment Setup

We used seven public datasets with varying sizes (Table 1). Among these datasets, Cornell, Texas, Washington and Wisconsin (which are sub-datasets of WebKB) are webpage datasets from four universities. Citeseer is a citation network. UAI2010 contains articles information fromWikipedia pages. Pubmed is a scientific publications dataset.

We compared NetVAE with two types of network embedding methods. 1) Topology-based methods: DeepWalk [Perozzi et al., 2014], Node2Vec [Grover and Leskovec, 2016] and SDNE [Wang et al., 2016a]; and 2) Methods using both topological and attribute information: TADW [Yang et al., 2015], VGAE [Kipf and Welling, 2016], TriDNR [Pan et al., 2016], SNE [Liao et al., 2018] and ARVGA [Pan et al., 2019]. VGAE and ARVGA are both the VAE-based methods.

For fair comparison, we set the embedding dimension l = 64 for all methods and used the default values for the other parameters of these methods. We also used the Tensorflow deep learning tool with a learning rate of 0.001.

3.2 Node Classification

After network embedding was done, we applied the LibSVM (SVM) and LibLINEAR (LINEAR) software packages in Weka as the classifiers for all methods. We used 10-fold cross-validation to train the classifier. Then, to measure the result, we employed accuracy (AC) [Liu et al., 2012] as the metric. NetVAE performs the best on 6 and 5 of the 7 networks using SVM and LINEAR respectively (Table 2). To be specific, NetVAE on average outperformed the best baseline method (i.e., TADW ) by 11.20% using SVM and 6.48% using LINEAR. In particular, NetVAE performs better than the other two VAE-based methods (i.e, VGAE and ARVGA) which also use the topological and attribute information.

3.3 Node Clustering

Similarly, we adopted k-means for node clustering and AC and NMI (normalized mutual information) [Liu et al., 2012] as the metrics. Here NMI was used because it has been widely adopted for node clustering. Our NetVAE method performs the best on 5 of the 7 networks in AC, and 6 of the 7 networks in NMI (Table 3). On average, NetVAE improved upon the best baseline (i.e., TADW) by 6.10% in AC and 16.18% in NMI. This further validate the effectiveness of NetVAE.

Node clustering is also the so-called community detection problem. Here we further compare our method with some existing methods that are specially designed for community detection on attribute networks, since NetVAE is also community-specific. The methods that we compared include Block-LDA [Balasubramanyan and Cohen, 2011], SCI [Wang et al., 2016b] and TLSC [Zhang et al., 2018b]. NetVAE performs the best on 5 and 6 of the 7 networks in terms of AC and NMI respectively (Table 4). On average, NetVAE improved upon the best baseline (i.e., TLSC) by 14.28% in AC and 17.03% in NMI. The two types of comparisons validate that we can derive better embedding by taking into consideration network modular structures, and the learning of embedding can enhance community detection.

3.4 Why Our ApproachWorks

To have a deep understanding on why NetVAE works, we examine two factors that have the greatest impact on the effectiveness and performance of NetVAE.

The Dual Decoder Architecture

In order to evaluate the effectiveness of the new dual decoder architecture, we compare NetVAE with its variant OVAE that uses a shared decoder using the fully connected neural network architecture for reconstruction of both network structures and node attributes. When compared on the node clustering task, NetVAE always outperforms OVAE (Table 5), with an average improvements of 7.67% in AC and 6.52% in NMI. This result revealed that by honoring the difference between network structures and node attributes and their different contributions to forming network modules as well as treating these two types of information in separate reconstruction processes, we are able to have better results.

Mechanism for Network Reconstruction

To analyze the factor, we compared the network structures generated from NetVAE and that from its variant OVAE with the shared decoder using neural networks. We reconstruct the network using the method in [Wang et al., 2016a]. This method calculates the cosine similarities between pairs of all of the nodes in the embedding space, and ranks the node pairs in a non-increasing order of similarity. It then selects the top k node pairs as links in the reconstructed network, and uses precision@k (i.e., the proportion of the actual edges in the original network that appear in the k reconstructed edges) as the metric. Here due to space limitation we show the results on Citeseer alone (Figure 2(a)). As shown, the precision@k of NetVAE is always higher than that of OVAE. The result indicates that the network reconstruction depends on network embedding in the VAE framework and a better reconstruction depends on a better embedding. This result may also be due to the way that we take advantage of community-specific coupling relationship among nodes in structure reconstruction.

We further analyzed the effectiveness of the new network generation mechanism in NetVAE by testing if it could better preserve the statistical properties of the original network. As an example, we present the node degree distributions of the original networks and of the networks reconstructed by NetVAE and OVAE (Figure 2(b)). As shown, the node degree distributions of the network reconstructed by NetVAE match better with the original network than that of OVAE.

4 Conclusion

We developed a novel network-specific variational autoencoder, called NetVAE, for embedding of attribute networks. This is the first to distinguish these two types of information of network topology and node attributes under the VAE framework. NetVAE has three immanent features. First, it uses a shared encoder to compress both network structures and node attributes so that a co-training can be done in the model fitting process to perform transfer learning between network structures and node semantics. Second, it introduces a dual decoding scheme to take a good advantage of the difference between network structures and node semantics as in reality these two types of information are often drawn from different sources. The dual decoder has one decoder of fully connected neural network for reconstruction of node attributes and another special neural network that incorporates a block model for exploiting network module structures and incorporates module-specific node coupling relationships. Third, a Gaussian mixture model is introduced between the shared encoder and the dual decoder, which assigns nodes to network modules in the embedding space. The extensive experimental results demonstrated the superior performance of the new approach over the existing methods.

Acknowledgments

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