Triplet Enhanced AutoEncoder: Model-free Discriminative Network Embedding

1 Introduction

Real-world networks often contain billions of nodes. It is intractable to perform complex mining tasks on these original networks such as node classification, link prediction, community detection [Shao et al., 2015] and recommendation. Currently, one promising solution is network representation, targeting to embed networks into a low-dimensional space (i.e., learn a vector representation for each vertex, with the goal of reconstructing the network in the learned embedding space, while the information of the original network is retained to the maximum).

∗Corresponding Author

During the past decade, many network embedding methods have been proposed (e.g., [Tang et al., 2015; Perozzi et al., 2014; Grover and Leskovec, 2016; Wang et al., 2016; Cao et al., 2016; Zhou et al., 2017; Velickovic et al., 2018]), which can be broadly categorized as shallow model or deep model. The commonly used techniques in the shallowmodel include matrix factorization and random walk. Factorization-based methods such as LINE [Tang et al., 2015] and GraRep [Cao et al., 2015] represent the target network as a data matrix and factorize this matrix to yield low-rank embeddings. Random walk based methods like node2vec [Grover and Leskovec, 2016], learn a vector embedding by exploiting random paths to preserve the local or global network structure. For all shallow models, the major limitation is that they fail to capture the complex nonlinear network structure.

As a result, many deep models have been proposed in recent years [Perozzi et al., 2014; Wang et al., 2016; Cao et al., 2016; Velickovic et al., 2018]. For example, thanks to the powerful ability to model non-linear complex relationship, deep autoencoders are popularized in network embedding such as SDNE [Wang et al., 2016] and DNGR [Cao et al., 2016], which have achieved state-of-the-art performance.

Recent studies on semi-supervised learning have demonstrated that leveraging labeling information does help network representation, especially for prediction-related tasks [Tu et al., 2016; Li et al., 2016]. However, current works mainly focus on training a specific classifier (e.g., SVM) with labeled information, such as MMDW [Tu et al., 2016]. The classifier-dependent learning framework is not stable and only performs well in node classification task with SVM. If we use the resulting embedding for node classification or clustering with other learning models, its performance is usually not satisfactory (see Tables 5 and 6 for example).

Motivated by previous works, in this paper we introduce a new deep network embedding approach, called Triplet Enhanced AutoEncoder (TEA), aiming to preserve both nonlinear network structure and node discriminative information. To this end, the label information is reformatted as a set of triplet constraints from the perspective of metric learning, and then plugged into an autoencoder architecture to learn a deep network embedding. We evaluated the performance of TEA on both node classification and clustering tasks, and the results show that our proposed model outperforms other competitive baselines, which suggest it is beneficial to both supervised and unsupervised tasks.

To summarize, we make the following contributions.

• We employ a metric learning strategy to utilize label information for network embedding. As a semi-supervised model, TEA not only allows capturing non-linear network structure with deep autoencoder, but also preserving the node discriminative information by imposing the triplet constraints.
• The proposed model TEA is model-free, which indicates that it is independent of any specific classifier. We are also the first who "supervise" the unsupervised autoencoder by metric learning.
• We conduct extensive experiments on real-world networks, and results show the effectiveness of the proposed TEA model.

2 RelatedWork

2.1 Network Embedding

In recent years, a growing number of works are proposed to find a good network representation in a low-dimensional space. As aforementioned, one strategy is to extract latent embeddings by singular value decomposition or matrix factorization [Cao et al., 2015; Ou et al., 2016; Tu et al., 2016; Wang et al., 2017; Yang et al., 2015; Zhang et al., 2016]. This type of methods typically work on a data matrix A (e.g., adjacent matrix) that characterizes the topological properties of a given network, and then factorizes A ≈ U T V U T V U T V orA ≈U T U U T U U T U into two low-dimensional embedding matrices U and V (i.e., the new network embedding). Since the formation process of a network is complicated and highly nonlinear, thus a linear function like matrix factorization may not be adequate to map the original network to an embedding space [Cai et al., 2018].

Inspired by the word2vec [Mikolov et al., 2013], there are also many random-walk-based methods emerged [Perozzi et al., 2014; Grover and Leskovec, 2016; Pan et al., 2016; Zhou et al., 2017], which propose some implicit reduction models by gathering random walk sequences of sampled nodes throughout a network. These methods work well in practice but struggle to explain what network properties should be kept in their objective functions. Deep autoencoders are also used to learn latent embedding of A [Cao et al., 2016; Wang et al., 2016] in an unsupervised way, where achieve non-linear mapping with various activation functions. For these works, different objective functions like Kullback-Leibler divergence [Tang et al., 2015] or Huber loss [Wei et al., 2017], are applied for network embedding. In addition, some methods are proposed to apply convolutional neural networks to make use of node attributes of networks [Kipf and Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018].

2.2 Metric Learning

Learning a good distance metric in feature space is crucial in real-world applications. Good distance metrics are important to many computer vision tasks, such as image classification and content-based image retrieval. Distance metric learning attempt to learn metrics that keep all the data points within the same classes close, while separating all the data points from different classes far apart. Prior works explored finding a mapping function ranging from a linear transform [Weinberger and Saul, 2009; Liao et al., 2015; Liu et al., 2017] to complex non-linear mappings usually represented by deep neural networks [Ding et al., 2015; Cheng et al., 2016].

3 Method

3.1 ProblemDefinition

Let us begin with formally defining the problem of network representation learning. Suppose we are given a network G = (V,E), where V = {v1, v2, ..., vn} is the set of all vertices and E = {ei,j}ni,j=1 represents the set of edges. Each edge is associated with a weight wi,j ≥ 0, wi,j = 0 if vi and vj is not linked. Otherwise, for unweighted graph wi,j = 1 and for weighted graph wi,j > 0. We let xi = [wi,0, ...,wi,n]T as the original representation of node i, let Y ∈ Rn×k be a binary matrix that collects the label of all n nodes, where k is the number of label categories.

Network embedding aims to map the graph data into a low-dimensional latent space and information of the original topology should be preserved to the maximum, where each vertex is represented as a low-dimensional vector. Namely, we aim to find a map function f : R|V |×1 → Rd×1 , d ≪ |V |. Then for each node i, the original representation vector xi becomes Φi .

3.2 DNGRRevisited

To motivate our method, we first discuss the closest related work, which is a prior deep autoencoder-based model: DNGR.

DNGR consists of three components: random surfing, positive point-wise mutual information (PPMI) calculation and stacked denoising autoencoder. Random surfing is used on the input graph to generate a probabilistic co-occurrence matrix, analogous to using the original adjacency matrix as a similarity matrix to express topological information.

PPMI matrix is transformed from the probabilistic cooccurrence matrix and used to solve the problem in word embedding that frequent words with relatively little semantic value such as meaningless stop words, these words often have a disproportionate effect on the word representations. It was proved [Cao et al., 2016] to have a better-tuned context weighting strategy compared to word2vec and Glove[Pennington et al., 2014]. It ensures that the following autoencoder model can capture high-order proximity more properly.

The point-wise mutual information (PMI) is calculated as follow:

Where |D| = ∑w ∑c #(w, c). A common approach to improving performance is to assign each negative value to 0, detailed in [Levy and Goldberg, 2014], to form the PPMI matrix

With random surfing and PPMI, the adjacency matrix is transformed into a PPMI matrix, and is finally fed into an autoencoder to obtain the network embedding. For the encoder, it consists of multiple non-linear functions that map the input data to the representation space. Similarly, the decoder consists of multiple non-linear functions mapping the embedding in the representation space to the reconstruction space. Formally, given an input xi, the hidden representations for each layer are shown as follows.

Here we use the LeakyRelu activation function as σ in our experiments. After obtaining Φi = y (K) i , we can get the output ˆ xi by decodingΦi, i.e., reverse the calculation process of the encoder. The goal of the autoencoder is to minimize the reconstruction error between the output and the input. The loss function is given as follow.

In order to enhance the robustness of DNN, each input sample x in Eq. (3) is corrupted randomly by assigning some entries in the vector to 0 with a certain probability.

The stacked denoising autoencoders aids robustness of the model in the presence of noise. It also allows capturing underlying structure, which is essential to many mining tasks such as link prediction and node classification. However, as aforementioned, existing autoencoder-based network embedding fails to preserve the node discriminative information. In the following, we will introduce triplet-loss, a metric learning perspective to integrate label information in our proposed model.

3.3 Metric Learning with Triplet-loss

Metric learning aims to find a mapping function (called metric) D : X × X → R≥0 over a vector space which used to metric the distance of two vectors xi,xj ∈ X. A popular metric is Mahalanobis distance that defined as follow.

WhereM is a positive semidefinite matrix. Originally, this term was used to describe the quadratic forms in Gaussian distributions, the matrix M plays the role of the inverse covariance matrix. For clarity we next use the shortcut notation Di,j = DM(xi,xj).

Our idea is to keep nodes with the same class to be close to each other in certain relation space, and keep vertices with different classes far apart. We define the following marginbased loss function as the objective function.

Given an anchor point xa, the projection of a positive point xp belonging to the same class ya is closer to the anchor's projection than that of a negative point belonging to another class yn, by at least a margin m.

)݇ ,݆ ,݅( Training Triplet

Figure 1: The framework of the Triplet Enhanced Autoencoder (TEA).

3.4 TEA: Triplet Enhanced Autoencoder

Building upon the deep autoencoder and triplet-loss [Schroff et al., 2015], finally we have our Triplet Enhanced Autoencoder in Fig. 1. Here the model is trained using each triplet as a training instance. Given (i, j, k), first our model compute the PPMI vectors of them, then feed the encoder and output the embeddings (Φi,Φj,Φk). Second, we calculate the triplet-loss of the embeddings while feeding them into the following decoder. The output of the decoder as well as the triplet-loss is used to compute an objective function explained below. Three encoders and decoders share the same weights respectively. The embeddings and the network structure are updated by gradients propagated back from the output layers.

In detail, we simultaneously optimize two objectives of Eq. (5) and Eq. (7). Let Ltea = Lr + α ∑ Ltri, where Lr is the reconstruction loss of the autoencoder and ∑ Ltri is the triplet-loss. α is a key parameter that balances the weights of the two objectives. The network embedding is finally transformed into a joint optimization problem as follow.

Specifically, we amend Lr with a tuned regularizer as follow:

where the term ∑ (W (l) jk )2 1+(W (l) jk )2 is called weight-elimination L2norm (Ridge) regularizer. The advantage of this regularizer is making the weight matrix to be sparse while reducing overfitting, and it solves the problem that L1-norm (Lasso) regularizer cannot be differentiated [Weigend et al., 1991].

As for the distance metric function in Eq. (8), we use the Mahalanobis distance function which described in Eq.(6) to measure the distance between anchor's embedding Φi and another's embedding Φj .

Since the whole objective (8) is differentiable, we are allowed to apply mini-batch stochastic gradient descent (SGD) to optimize each W,b and M by propagating the gradients top-down from the output layers.

3.5 Time Complexity

The most time-consuming part of our method is the computation of triplet-loss and we calculate it every batch. It is not difficult to see that the training complexity of our model is O[(B + D)Bne], where B is the batch-size in our training process, D is the maximum dimension of the hidden layers, n is the number of vertices and e is the number of epochs we choose to train. Parameter D is usually related to the dimension of embedding vectors but not related to the number of vertices, e is also independent with n, B is usually tuned according to the number of node categories. Thus, the overall complexity is linear to the number of vertices in the network.

4 Experiment

In this section, we assess the effectiveness of our TEA model on real-world networks. We conduct node classification as well as clustering tasks and make comparisons with baseline algorithms. Besides, we also visualize the learned representation to demonstrate its discriminative ability.

4.1 Datasets

We use the following three typical datasets for our experiments.

• Cora 1 : This is a citation network of academic papers. The vertexes are academic papers and the directed edges are the citation relationship between papers. It contains 2,708 machine learning papers which are categorized into 7 classes, and there are 5,429 citation links among these papers.
• Citeseer 2 : This is another research paper set. These papers are from 6 classes. Similar to Cora, the links are citation relationships between the documents. It contains 3,312 publications and 4,732 connections between them. Different fromCora, it contains several self-loops.
• BlogCatalog 3 : This is a network of social relationships between users on the BlogCatalog website. The labels of this graph are the topics specified by the uploading users. After filtering out nodes with multi-label, it contains 7,288 nodes, 131,011 edges, and 37 labels.

4.2 Baseline Methods and EvaluationMetrics

We use the following four methods as the baselines to validate the performance of our approach. The first three are learned in unsupervised ways, and the last one utilizes existing label information like our approach.

• GraRep: This multi-scale method generates vertex representations by explicitly computing successive powers of the random walk transition matrix, and SVD is

1 http://www.cs.umd.edu/∼sen/lbc-proj/data/cora.tgz

2 http://www.cs.umd.edu/∼sen/lbc-proj/data/citeseer.tgz

3 http://socialcomputing.asu.edu/datasets/BlogCatalog3

applied to obtain a low-dimensional representation of nodes.

• node2vec: It adopts random walk and skip-grammodel to generate network representations. By introducing the return parameter p and the in-out parameter q, node2vec combines DFS-like and BFS-like neighborhood exploration.
• DNGR: It firstly calculates the PPMI matrix, and then learns the representations through stacked denoising autoencoder. It is an exact computation similar to our approach in spirit, however, DNGR doesn't utilize additional labeling information.
• MMDW: It is a semi-supervised method which adopts the matrix factorization form of DeepWalk, to preserve the network structure and discriminative information by equipping with a support vector machine model.

In our experiment, we performed the tasks of node classification, clustering and visualization. For the node classification task, we adopted micro-F1 and macro-F1. To further demonstrate the advantage of metric learning for leveraging the label information, we evaluated the embedding results with both logistic regression and support vector machine (both implemented by LibLinear 4 ). We applied K-means to the learned representations of nodes and adopted normalized mutual information (NMI) to assess the quality of the node clustering. Due to the sensitivity of K-means on the initial values, we repeated the clustering ten times, and the average results were reported here.

4.3 Parameter Settings

We propose a multi-layer deep structure in this paper and the number of layers varies with different datasets. The dimension of each layer is listed in Table 1. The hyper-parameters of α and β are tuned by using grid search on the validation set, the sensitivity is further evaluated in Section 4.5. The models were trained for 20 epochs with Adam optimizer.

We set the representation dimension to 100 for baseline algorithms, same as our model. The parameters in baselines are tuned. For GraRep, we set the maximum matrix transition step K = 5 for BlogCatalog, K = 3 for Cora and Citeseer. For node2vec, we set the window size as 10, the walk length as 80, the walk per vertex as 20, both in-out and return hyper-parameters are set to 0.25. For DNGR, we set the neural network structures the same as TEA. For MMDW, we set the gradient balance parameter η = 10-2 .

4 https://www.csie.ntu.edu.tw/∼cjlin/liblinear/

4.4 Results and Analysis

Here we first show our TEA can achieve considerable improvement than the unsupervised baselines with only a little label information. Afterward, we will elaborate that our TEA is model-free and outperforms other semi-supervised methods like MMDW.

Compared with Unsupervised Methods

We separate the embedding process and the evaluation process so that all the embedding output can be evaluated by more than one model. Here four-fold cross-validation is applied.

Tables 2,3 and 4 show the classification and clustering performance on different datasets. In these tables, all algorithms make full use of the topology data. TEA(5%) and TEA(10%) mean the percentages of the additional label information we use in TEA during the embedding process, and the rest of the nodes are used for evaluation. From these tables, we can observe that, compared to baselines, TEA needs only 5% labeled data to achieve an obvious improvement, especially for the SVMmodel. These results show that labeled information is really helpful for classification tasks.

To verify whether the learned representation is discriminative, we show the 2D representations of vertices using the tSNE visualization tool in Fig. 2. In this figure, each dot represents a vertex and each color represents a category. From Fig. 2, we observe that TEA learned a better clustering and separation of the vertices. In contrast, the representations learned by node2vec tend to mix together, and GraRep and DNGR are even worse. A well-separated representation is more discriminative and easier to apply downstream network mining tasks.

Compared with MMDW

Here, in contrast to the unsupervised setting, we randomly sample a portion of vertices to adopt their label information for embedding, and use four-fold cross-validation on the rest vertices to evaluate the embedding results. We increase the labeled ratio from 20% to 80%, to compare the performance of different algorithms.

Tables 5 and 6 show the classification and clustering performance on different datasets. LR means the embedding results are evaluated under the model logistic regression, and SVM means the embedding results are evaluated with SVM.

From these tables, we can observe that TEA outperforms MMDW no matter how much labeled information is available. Although the performance of MMDW is enhanced with label information under the SVMmodel, it gives poor results when a logistic regression model is applied on the learned embeddings (see Tables 5 and 6). Thus it is not a good representation. These results further demonstrate that the metric learning perspective provides a good way to leverage available labeling information, and do help network embedding. More importantly, the resulting embedding is stable and independent of any specific model.

4.5 Parameter Sensitivity

There is a key parameter involved in our objective function: α. As aforementioned, α is used to adjust the weights of two objectives (cf. Section 3.4). To test its sensitivity, we conduct experiments on both classification and clustering tasks. The performance of TEA against different values of α is given in Fig. 3(a) and Fig. 3(b) in terms of Macro-F1 and NMI on the Citeseer data, respectively. From the figure, we can observe that TEA has a fairly stable performance when α ranges from 10-2 to 102 . Depending on the specific task is classification or clustering, it gains the best performance at different locations, mainly range from 10-1 to 100 . In general, from Fig. 3, we can see that TEA achieves good performance in a wide range of parameter settings.

5 Conclusion

In this paper, we propose a triplet-loss enhanced deep autoencoder, namely TEA, to perform network embedding via metric learning. By leveraging the labeling information with the triplet-loss, TEA allows learning the vertex representations which preserve both their network structure and node discriminative information with the model-free property. Experiments on real-world datasets show the stability of TEA and achieve state-of-the-art performance compared with both supervised and unsupervised network embedding approaches.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (61403062, 61433014, 41601025), ScienceTechnology Foundation for Young Scientist of Sichuan Province (2016JQ0007), Fok Ying-Tong Education Foundation for Young Teachers in the Higher Education Institutions of China (161062) and National key research and development program (2016YFB0502300).