JANE: Jointly Adversarial Network Embedding

1 Introduction

Traditional network analysis designs exclusive end-to-end approaches for different tasks, such as node classification, community detection and link prediction, etc. Motivated by representation learning, network embedding unifies many network analysis tasks as a node representation learning framework. Thus, the node representation learning plays a vital role in the latter development stage of network analysis. In the past five years, many network embedding approaches [Cai et al., 2018; Shen et al., 2018] have been proposed. Some of them are motivated from language model, i.e., word2vec [Mikolov et al., 2013], such as DeepWalk [Perozzi et al., 2014] and node2vec [Grover and Leskovec, 2016]. Others adopt the mechanisms of topology reconstruction with matrix factorization or AutoEncoder, such as SDNE [Wang et al., 2016], NetMF [Qiu et al., 2018] and TADW [Yang et al., 2015]. Recently proposed Graph Neural Networks (GNNs) [Wu et al., 2019b; Yang et al., 2019c; Yang et al., 2019a; Yang et al., 2019b], such as Graph Convolutional Network (GCN) [Kipf and Welling, 2017] and Graph Attention Network (GAT) [Velickovic et al., 2018], achieve remarkable performance in semisupervised node representation classification.

∗Corresponding author.

Inspired by Generative Adversarial Network (GAN) [Goodfellow et al., 2014], which is capable of exploring the latent semantic space and capturing semantic variation in the data distribution via a perturbation distribution [Donahue et al., 2017], adversarial learning is progressively adopted into network embedding to improve robustness [Dai et al., 2018; Pan et al., 2018; Pan et al., 2019]. As shown in Figure 1(a), this capability in GAN is obtained by comparing the generated fake data, which are produced based on the samples drawn from a perturbation (usually Gaussian) distribution, with the real data. Unfortunately, this capability tends to be lost in adversarial learning based network embedding approaches, because the perturbation distribution cannot be rectified with real data. In fact, the samples generated from a perturbation distribution are directly compared to the embedding results, which are obtained from an auto-encoder, in adversarial learning based network embedding, as shown in Figure 1(b). For example, Pan et al. utilize adversarial learning to regularize the embeddings obtained from Graph Auto-Encoder [Kipf and Welling, 2016] by comparing the embeddings with the samples drawn from a Gaussian distribution [Pan et al., 2018]. This naive regularization only force the learned embeddings to be more consistent with the Gaussian distribution, rather than capturing the semantic variations. Therefore, existing network embedding approaches cannot effectively benefit from adversarial learning.

To overcome this deficit in existing adversarial learning based network embedding approaches, a novel Joint Adversarial Network Embedding (JANE) framework is proposed in this paper. Instead of directly comparing the embeddings with the samples drawn from a Gaussian distribution, JANE jointly distinguishes the real and fake combinations of the embeddings, topology information and node features. The combined topology information and node features rectifies the Gaussian distribution to capture the semantic variations in latent space, as in GAN. Specifically, our JANE framework consists of three pluggable components, Embedding module and Generator module and Discriminator module as shown in Figure 2. In the Embedding module, attention-based layerwise propagation is adopted to seamlessly and flexibly combine the topology information and node features. The Generator module creates the fake topology information and node features from fake embeddings. To improve the efficiency, the fake embeddings are constructed by adding Gaussian noises to the embeddings obtained in the Embedding module, instead of directly sampling from a Gaussian distribution. The overall objective function of JANE is defined in a min-max form, which can be optimized via alternating stochastic gradient. In each iteration, the Discriminator module is optimized by maximizing the objective function w.r.t. its parameters, then the Generator and Embedding modules are optimized by minimizing it w.r.t. their parameters. The main contributions of this paper are summarized as follows:

• We analyze the adversarial mechanism in existing adversarially regularized network embedding methods, and reveal their inabilities to capture semantic variations.
• We propose a novel Jointly Adversarial Network Embedding (JANE) framework with pluggable components to benefit the embedding methods from the adversarial mechanism.
• Extensive experiments on link prediction and node clustering demonstrate the remarkable superiority of the proposed JANE over 12 state-of-the-art methods.

2 Notations

Define an attribute network as G = (V, E,X) with vertices V = {v1, v2, ..., vN} and edges E = {e1, e2, ..., eM}. The attributes of all the vertices are represented via an attribute matrix X ∈ RN×F where the nth row of which, xn ∈ R1×F , corresponds to the attributes of vertex vn in the form of a Fdimensional vector. The network topology is represented by an adjacency matrix A = [aij ] ∈ {0, 1}N×N , where aij = 1 if an edge exists between the vertices vi and vj and vice versa. Typical attribute network embedding problem seeks a lowdimensional representation Z ∈ RN×P for all the vertices in V, where P is the dimension of the embedding. For convenience, Y ∈ RN×P , which possesses the same dimension as the embedding matrix Z, is employed to denote the N samples drawn from a specific prior distribution, e.g, Gaussian.

3 Motivations

The remarkable ability of Generative Adversarial Networks(GANs)[Goodfellow et al., 2014], which learns to generate complex data distribution, such as images, from simple latent (Gaussian) distribution, demonstrates that GANs can effectively explore the latent semantic space and capture semantic variations in the data distribution [Donahue et al., 2017]. Motivated by this, adversarial learning is adopted by network embedding [Dai et al., 2018; Pan et al., 2018; Pan et al., 2019]. Pan et al. leverages GAN to regularize the embedding results of Graph Auto-Encoder [Kipf and Welling, 2016], which adopts Graph Convolutional Network (GCN) [Kipf and Welling, 2017] as the encoder and reconstructs the topology information (adjacency matrix) [Pan et al., 2018]. They further extend this framework to reconstruct both the topology and node attributes [Pan et al., 2019]. On the other hand, Dai et al. propose Inductive DeepWalk, which is the variant of DeepWalk [Perozzi et al., 2014], and utilize GAN to regularize the embedding results of Inductive DeepWalk. Since DeepWalk is equivalent to factorizing the multi-hop normalized adjacency matrix [Qiu et al., 2018], i.e, reconstructing the topology information, it can also be considered as adversarially regularizing the embedding results of an auto-encoder. Therefore, most existing network embedding approaches, which are developed based on adversarial learning, can be unified into a framework of adversarially regularizing the embedding results of an auto-encoder, as shown in Figure 1(b).

Typically, the existing methods directly regularize the embedding results against the samples generated from a Gaussian distribution. They iteratively optimize the encoder and the discriminator to constrain the generated (encoded) embedding results to be indistinguishable from the samples, which are generated from a Gaussian distribution. However, this regularization approach cannot guarantee the embedding results to be robust. It only indicates that the embedding results obey Gaussian distribution. This phenomenon is originated from the inappropriate usage of the adversarial learning mechanism. In GAN [Goodfellow et al., 2014], the Gaussian prior can effectively capture the semantic variations in the data distribution, because the generated data are compared to the real ones, as shown in Figure 1(a). Unfortunately, the samples drawn from the Gaussian distribution are directly treated as fake data and compared to the real network embeddings in network embedding approaches. Without the discrimination between the generated data and the real data, the Gaussian prior can hardly possess the ability of exploring the latent semantic space and capturing semantic variations. Since the existing network embeddings with adversarial learning cannot fully leverage the effectiveness of adversarial learning on semantic space exploration, they cannot significantly improve the performance of original embedding methods based on GAE [Kipf and Welling, 2016], which is demonstrated in Section 5.

4 Framework

In this section, a novel Joint Adversarial Network Embedding (JANE) framework is proposed. The overview is firstly provided, followed by its three specific components: discriminator, embedding and generator modules. Finally, our objective function and optimization details are given.

4.1 Overview

As summarized in Section 3, the main drawback in Adversarially Regularized Network Embedding is the inability to capture semantic variations due to the direct comparison between the embeddings and samples generated from a Gaussian prior. To overcome this vital issue, a novel Joint Adversarial Network Embedding (JANE) framework is proposed to jointly discriminate the real and fake combinations of topology, node features and embeddings, instead of directly comparing the embeddings with the samples drawn from Gaussian distribution. As illustrated in Figure 2, JANE consists of three pluggable components, Embedding module (E), Generator module (G), and Discriminator module (D). Although the philosophy of JANE is similar to that of GAN, as given in Figure 1(a), they still possess two major differences. Firstly, an Embedding module is introduced in JANE, because the intention of JANE is to produce network embeddings instead of generating new data(attribute network). Secondly, instead of generating fake attribute network completely based on the samples obtained from Gaussian distribution, as in GAN, the embedding results of real attribute network (as shown in yellow rectangle) are combined with the samples generated from Gaussian distribution to produce the fake embeddings, and then generate the fake attribute network. In the following, the adopted discriminator, embedding and generator methods are introduced. Note that the proposed JANE is an adversarial network embedding framework, thus its three components are all replaceable.

4.2 Discriminator Module

The most remarkable difference of JANE from the existing adversarial learning based network embedding approaches is the input to the discriminator. To rectify the Gaussian prior with real data, the discriminator of our proposed JANE distinguishes the real and fake combinations of topology, node features and embedding results, as

where A and X are the given real adjacency matrix and node features, Z and Z′ are the real and fake embeddings, A′ and X′ are the generated fake adjacency matrix and node features. || denotes the concatenation operation. This kind of input possesses two characteristics. Firstly, topology and node features are both included into the input of our discriminator. This is motivated by GAN [Goodfellow et al., 2014; Donahue et al., 2017] that only the comparison between the real and fake data can constrain the Gaussian prior to capture semantic variations in latent embedding space. Secondly, instead of directly comparing embedding results with the samples drawn from Gaussian distribution as in Figure 1(b), JANE compares real and fake embeddings, because we intend to seek network embeddings instead of generating new attribute network. To distinguish whether the input combination is real, the discriminator is built on a multi-layer perceptron (MLP) parameterized byWD and the output layer only has one dimension based on a sigmoid function.

4.3 EmbeddingModule

The embedding module encodes the attribute network G = (V, E,X) as a collection Z of real value vectors, each row of which corresponds to a vertex. Recently, graph neural networks (GNNs) achieve state-of-the-art in semi-supervised node classification on attribute networks [Wu et al., 2019b]. Motivated from a first-order approximation of the spectral graph convolution, Graph Convolutional Network (GCN) [Kipf and Welling, 2017] adopts layer-wise attribute propagations to augment the node features. Although GCN significantly improves the performance of node classification, its main drawback is the fixed propagation weights, which are completely determined by the degrees of the two connected nodes [Wu et al., 2019a; Li et al., 2018]. To make the embedding module flexible, the propagation weights are assumed to be learnable according to the features in the two connected nodes. Here, self-attention [Bahdanau et al., 2015; Wang et al., 2019] is adopted to estimate the weights, similar to Graph Attention Network (GAT) [Velickovic et al., 2018],

where xi is the feature of vertex vi, i.e., the ith row of X, Θ ∈ RF×P is the mapping from features to embeddings, and b ∈ R2P is the attention weights to be learned. Then, the node embeddings can be obtained by averaging its weighted neighbourhoods as

For stability, multi-head self-attention [Vaswani et al., 2017] is adopted to boost the performance. Since JANE aims to construct node embeddings instead of node classification, the parameters b and Θ cannot be directly obtained with the supervision from the given node label information. In JANE, they are obtained with the weak supervision from the real and fake labels of the combinations. Note that the current embedding module can be replaced with other approaches as long as they possess similar functionalities.

4.4 Generator Module

Since the inputs to the discriminator are the real and fake combinations of the topology, node features and the embeddings, the task of our Generator module is to generate the fake combination based on the samples drawn from a Gaussian distribution. Inspired by GAN, the most straightforward approach is treating the samples generated from a Gaussian distribution Y ∈ RN×P , which possesses the same dimension as the embedding matrix Z, as the fake embeddings, and then generate fake topology and node features. However, it is ineffective for the high-dimensional output, such as adjacency matrix of large network. Since the samples drawn from Gaussian distribution tend to capture the semantic variations of the latent space, the fake embeddings can be constructed from the obtained real embeddings as

Then, the fake node features and adjacency matrix can be respectively generated from Z′ . Here, the simplest generators are adopted for demonstration. The fake node features are generated by feeding the fake embeddings into a fullyconnected layer parameterized by WG ∈ RP×F , as

where the nonlinear activation function LeakyReLU(.) is adopted with a negative input slope α = 0.2. The fake adjacency matrix is generated by multiplying the fake embedding Z′ with its transposition as

because previous work indicates that many embedding methods are equivalent to factorizing the topology information matrix, such as multi-hop adjacency matrix [Qiu et al., 2018]. To improve the nonlinearity, the sigmoid(.) activation function is adopted here. Note that the above generators can also be replaced with others possessing similar functionalities.

4.5 Objective Function and Optimization

The JANE framework consists of three pluggable components, Embedding module (E), Generator module (G), and Discriminator module (D). Let pAX be the joint distribution of the topology and node features for (a, x) ∈ ΩA×X. The encoder E : ΩA×X → ΩZ induces a distribution pE(z|a, x) = δ(z - E(a, x)), which maps topology a and node features x into the latent space z. The generator G : ΩZ → ΩA×X generates topology and node attributes from the embeddings with pG(a, x|z) = δ((a, x) - G(z)) and pG(a, x) = Ez∼pZ [pG(a, x|z)]. The discriminator D : ΩZ×A×X → {0, 1} takes the inputs from the combinations of embeddings, topology information and node features, and then predicts PD(L|z, a, x), where L = 1 if topology a and node features x are real, i.e., sampled from the real data distribution pAX, and L = 0 if topology a and node features x are generated, i.e., the output of G(z), with z ∼ pZ. The objective function of JANE is defined in a min-max form as

where V (D, E, G) is defined as

Note that our Embedding module (E), Generator module (G), and Discriminator module (D) are parameterized by (Θ, b), WG and WD, respectively. This min-max objective function can then be optimized via the same alternating stochastic gradient as that in GAN [Goodfellow et al., 2014]. In each iteration, the discriminator parameter WD is updated by taking one or more steps in the positive gradient direction, ∇WD V (D,E,G), then the embedding parameters (Θ, b) and generator parameters WG are together updated by taking a step in the negative gradient direction, -∇Θ,b,WG V (D, E, G).

5 Evaluations

To demonstrate the superiority of the proposed JANE framework, link prediction and node clustering tasks on three widely used citation networks (Cora, Citeseer and Pubmed as shown in Table 1) are adopted. In each network, the nodes represent the scientific publications, while the edges denote the citations. Each node feature is a bag-of-words representation of a publication. Note that the publications are divided into groups according to their research fields.

Experimental settings. For all the experiments, two attention layers with 8 and 1 attention heads are adopted for attention-based embedding module, and three fullyconnected layers are employed in both the discriminator and generator. For fair comparison, the dimension of each embedding, i.e. P, is set to 16 for all the methods. Adam optimizer is adopted with the initial learning rates for the discriminator and other two components as 0.001 and 0.008, respectively. Both L2 regularization and dropout are exploited.

5.1 Link Prediction

For the link prediction task, the proposed JANE is compared to 6 state-of-the-art baselines, including Spectral Clustering method [Tang and Liu, 2011], standard DeepWalk [Perozzi et al., 2014], Graph Auto-Encoder (GAE) and its variational extension VGAE [Kipf and Welling, 2016], Adversarially Regularized Graph Auto-Encoder (ARGA) and its variational extension ARVGAE [Pan et al., 2018]. Two metrics, i.e., Area Under Curve (AUC) and Average Precision (AP), are adopted to quantify the performances according to the evaluation protocol in GAE [Kipf and Welling, 2016]. For each citation network, the edges are randomly divided into three groups. 85%, 5% and 10% of the edges are utilized in training, validation (hyper-parameters tuning) and performance testing, respectively. For each network, experiments are repeated 10 times on 10 different random edge partitions, and the average performances are reported in Table 2.

As can be observed, the performance improvement of ARGA over GAE, which is the basis of ARGA, is only about 1%, because of the ineffective adoption of the adversarial mechanism. The proposed JANE consistently and significantly outperforms the state-of-the-arts. It achieves about 3% performance gains (both in AUC and AP) in average, compared to ARGA, where an adversarial learning between the embeddings and input samples is exploited. These gains are attributed to the novel adversarial learning between the real and fake combinations of embeddings, topology and node features, and the adopted attention-based embedding method.

5.2 Node Clustering

For the node clustering task, another 6 state-of-the-art methods are adopted besides of the 6 baselines mentioned in Section 5.1, including K-Means, Graph Encoder [Tian et al., 2014], Deep Representations for Graph Clustering (DNGR) [Cao et al., 2016], Relational Topic Models (RTM) [Chang and Blei, 2009], Robust Multi-View Spectral Clustering (RMSC) [Xia et al., 2014] and Text-Associated DeepWalk (TADW) [Yang et al., 2015]. All the baselines can be categorized into 4 classes, methods based on topology, methods based on both the topology and node features, methods based on GNNs and methods based on adversarial learning. To characterize the clustering performance, 6 metrics are utilized, including Accuracy (ACC), Precision, Normalized Mutual Information (NMI), Average Rand Index (ARI) and F1 score, which combines both the precision and recall rates.

The results on the Cora, Pubmed and Citeseer networks are shown in Tables 3, 4 and 5, respectively. The specific clustering performances of our proposed JANE remarkably surpass other baselines in almost all the metrics. For example, JANE achieves 9%, 8% and 2% gains on Cora, Citeseer and Pubmed, respectively, according to the F1 score. JANE's superior performances demonstrate that it can effectively and efficiently explore the latent space and capture the variations in semantic space. Note that the performance gain of JANE is less significant in NMI, which is more sensitive to the results of small cluster, compared to the results in other metrics. It indicates that most of our gains come from the large clusters.

5.3 Impacts of the Perturbation Distributions

By distinguishing the real and fake combinations instead of only the embeddings, JANE constrains the perturbation distribution to capture the semantic variations of the latent space. Thus, the impacts of different perturbation distributions, including Gaussian, Truncated Gaussian and Uniform distributions, on the node clustering task is verified. In Truncated Gaussian distribution, the sampled values, whose magnitude is more than 2 standard deviations from the mean, are dropped. The results, which are shown in Figure 3, demonstrate that the original Gaussian perturbation distribution is more suitable for semantic variation exploration than the others. These phenomenons satisfy the law of large numbers. The worst performance of Uniform distribution can be attributed to its inability of capture the latent space structure due to its uniform property. The performance of Truncated Gaussian distribution is between those of Gaussian and Uniform distributions, because the truncation tends to cause improper fitting to the latent space structure. This experiment illustrates that the semantic variations of latent space can be captured by distinguishing the real and fake combinations of the embeddings, topology and features.

6 Conclusions and Discussion

In this paper, the widely used adversarial mechanism in existing network embedding methods is analyzed and questioned, because they are incapable to capture semantic variations in latent space, which can be attributed to the direct comparison of the embedding results and the samples drawn from Gaussian prior without any rectifications from real data. To overcome this vital issue, a novel Jointly Adversarial Network Embedding (JANE) framework with pluggable components is proposed to benefit the network embedding methods from the adversarial mechanism. Remarkable performance improvements on link prediction and node clustering tasks have been achieved by the proposed JANE, which verifies that the proposed JANE can effectively explore the latent space and capture the semantic variations The experiments for studying the impacts of different perturbation distributions demonstrate the importance of capturing the semantic variations with proper prior distribution.

Acknowledgments

This work was supported in part by the National Key R&D Program of China under Grant 2017YFC0820106, in part by the National Natural Science Foundation of China under Grant 61972442, Grant 61802282, Grant 61802391 and Grant U1936210, in part by the Key Program of the Chinese Academy of Sciences under Grant QYZDB-SSW-JSC003, in part by the Hebei Province Innovation Capacity Enhancement Project under Grant 199676146H, and in part by the Fundamental Research Funds for Central Universities.