Deep Attributed Network Embedding

1 Introduction

Networks are ubiquitous in the real world, such as social networks, academic citation networks, and communication networks. Among various networks, the attributed network has attracted much attention in recent years. Unlike the plain network where only the topological structure is available, nodes of attributed networks possess rich attributed information. These informative attributes can benefit network analysis. For example, in an academic citation network, the citation among different articles compose a network where each node is an article and each node has substantial text information about the article's topic. Another example is the social network where users connect with others and post their profiles as the attribute. Furthermore, the social science [Marsden and Friedkin, 1993; McPherson et al., 2001] has shown that attributes of nodes can reflect and affect their community structures [Huang et al., 2017b; Yang et al., 2010]. Thus, it is necessary and important to study the attributed network.

Network embedding as a fundamental tool to analyze networks has attracted a surge of attention in data mining and machine learning community recently. It is to learn a lowdimensional representation for each node of a network while preserving the proximity. Then, the downstream tasks, such as node classification, link prediction, and network visualization, can benefit from the learned low-dimensional representation. In recent years, various network embedding methods have been proposed, such as DeepWalk [Perozzi et al., 2014], Node2Vec [Grover and Leskovec, 2016], and LINE [Tang et al., 2015]. However, most of the existing approaches mainly focus on the plain network, ignoring useful attributes of nodes. For example, in the social network such as Facebook or Twitter, each user connects with others, constituting a network. Most of existing methods only focus on the connection when learning node representations. But the attribute of each node can also provide useful information. A good example is the user profile. A young user may have much more similarity with another young guy, rather than an old user. Thus, it is important to incorporate node attributes when learning node representations.

Moreover, the topological structure and attributes of networks are highly non-linear [Wang et al., 2016]. Thus, it is important to capture the highly non-linear property to discover the underlying pattern. Then, the proximity can be preserved better in the learned node representations. However, most of existing methods, such as [Huang et al., 2017a; Yang et al., 2015], only employ the shallow model, failing to capture the highly non-linear property. Furthermore, how to capture this highly non-linear property is difficult due to the complicated topological structure and attributes. Therefore, it is challenging to capture the highly non-linear property for attributed network embedding.

To address the aforementioned problems, we propose a novel deep attributed network embedding (DANE) approach for attributed networks. In detail, a deep model is proposed to capture the underlying high non-linearity in both topological structure and attributes. Meanwhile, the proposed model can enforce the learned node representations to preserve the firstorder and high-order proximity in original networks. Moreover, to learn the consistent and complementary representation from the topological structure and attributes of a network, we propose a novel strategy to combine these two kinds of information. Furthermore, to obtain a robust node representation, an efficient most negative sampling strategy is proposed to make the loss function robust. At last, extensive experiments have been conducted to verify the effectiveness of our proposed approach.

2 RelatedWorks

2.1 Plain Network Embedding

Network embedding can be traced back to the graph embedding problem, such as Laplacian Eigenmaps [Belkin and Niyogi, 2001], LPP [He and Niyogi, 2003]. These methods are to learn data embedding while preserving the local manifold structure. However, these methods are not applicable for large-scale network embedding, since they involve the time-consuming eigendecomposition operation whose time complexity is O(n3 ) where n is the number of nodes. Recently, with the development of large-scale networks, a variety of network embedding methods [Perozzi et al., 2014; Grover and Leskovec, 2016; Cao et al., 2015; Tang et al., 2015; Gao and Huang, 2018] have been proposed. For example, DeepWalk [Perozzi et al., 2014] adopts random walk and Skip-Gram to learn node representations, based on the observation that the distribution of nodes in the random walk is similar to that of words in natural language. LINE [Tang et al., 2015] proposes to preserve the first- and second-order proximity when learning node representations. And GraRep [Cao et al., 2015] is proposed to preserve high order proximity. Furthermore, Node2Vec [Grover and Leskovec, 2016] is proposed by designing a biased random walk on the flexible node's neighborhood. However, all of these methods only utilize the topological structure, ignoring the useful attribute of nodes.

2.2 Attributed Network Embedding

Attributed network embedding has attracted much attention in recent years. A wide variety of models have been proposed for attributed networks. For example, [Yang et al., 2015] proposes an inductive matrix factorization method to combine the topological structure and attributes of networks. However, it is a linear model essentially, which is not enough for the complicated attributed network. [Huang et al., 2017a; 2017b] employ the graph Laplacian technique to learn the joint embedding from the topological structure and attributes. [Kipf and Welling, 2016a] proposes a graph convolutional neural network model for attributed networks. But this model is a semi-supervised approach, failing to deal with the unsupervised case. [Pan et al., 2016] proposes to combine DeepWalk with a neural network for network representation. Nonetheless, the DeepWalk part is still a shallow model. Recently, two unsupervised deep attributed network embedding approaches [Kipf and Welling, 2016b; Hamilton et al., 2017] have been proposed. However, they can only explore the topological structure implicitly. Thus, it is necessary to explore the deep attributed network embedding method in a more effective way.

3 Deep Attributed Network Embedding

In this section, we first give the formal definition of attributed network embedding and then develop our novel deep attributed network embedding approach.

3.1 ProblemDefinition

Let G = {E, Z} denote an attributed network with n nodes, where E = [Eij] ∈ ℜn×n is the adjacency matrix and Z = [Zij] ∈ ℜn×m is the attribute matrix. In detail, if there exists an edge between the i-th node and the j-th node, Eij > 0. Otherwise, Eij = 0. Zi· ∈ ℜm is the i-th row of Z, which denotes the attribute of the i-th node.

Before giving the problem definition, we first introduce the definition of different proximities, which is important for our approach.

Definition 1. (First-Order Proximity [Tang et al., 2015]) Given a network G = {E,Z}. The first-order proximity of two nodes i and j is determined by Eij . Specifically, a larger Eij denotes a larger proximity between the i-th node and the j-th one.

The first-order proximity indicates that if there exists a link between two nodes, they are similar. Otherwise, they are dissimilar. Thus, it can be viewed as a local proximity.

Definition 2. (High-Order Proximity [Cao et al., 2015]) Given a network G = {E,Z}, the high-order proximity of two nodes i and j is determined by the similarity of Mi· and Mj·, whereM = ˆE+ ˆE2 +· · ·+ ˆEt is the high-order proximity matrix, ˆE is the 1-step probability transition matrix which is obtained from the row-wise normalization of the adjacency matrix E.

The high-order proximity actually indicates the neighborhood similarity. Specifically, if two nodes share similar neighbors, they are similar. Otherwise, they are not similar. Here, the high-order proximity can be viewed as a global proximity.

Definition 3. (Semantic Proximity) Given a network G = {E, Z}, the semantic proximity of two nodes i and j is determined by the similarity of Zi· and Zj·.

The semantic proximity denotes that if two nodes have similar attributes, they are similar. Otherwise, they are dissimilar. Attributed network embedding is to learn the lowdimensional representation of each node based on the adjacency matrix E and the attribute matrix Z, such that the learned representation can preserve the proximity existing in the topological structure and node attributes. Formally, we aim at learning a map f : {E,Z} → H where H ∈ ℜn×d is the node representation, such that H can preserve firstorder proximity, high-order proximity and semantic proximity. Then, downstream tasks, such as node classification and link prediction, can be performed on the learned H.

3.2 Deep Attributed Network Embedding

Essentially, the attributed network embedding faces three great challenges to obtain a good embedding result. They

• are:· Highly non-linear structure: The underlying structure of the topological structure and attributes are highly non-linear, thus it is difficult to capture this non-linearity.
• Proximity preservation: The proximity in an attributed network depends both on the topological structure and the

attribute, thus how to discover and preserve the proximity is a tough problem.

• Consistent and complementary information in the topological structure and attributes: These two kinds of information provide different views for each node, thus it is important to make the learned node representations preserve the consistent and complementary information in these two modalities.

To address these three challenges, we develop a novel deep attributed network embedding (DANE) approach. The architecture is shown in Figure 1.

Overall, there are two branches where the first branch is composed of a multi-layer non-linear function, which can capture the highly non-linear network structure, to map the input M to the low-dimensional space. Similarly, the second branch is to map the input Z to the low-dimensional space to capture the high non-linearity in attributes.

Highly Non-linear Structure

To capture the highly non-linear structure, each branch in Figure 1 is an autoencoder. Autoencoder is a powerful unsupervised deep model for feature learning. It has been widely used for various machine learning applications [Jiang et al., 2016]. The basic autoencoder contains three layers, they are the input layer, the hidden layer, and the output layer, which are defined as follows:

Here, xi ∈ ℜd is the i-th input data, hi ∈ ℜd′ is the hidden representation from the encoder, and ˆxi ∈ ℜd is the reconstructed data point from the decoder. θ = {W (1) ,W (2) , b(1) , b(2) } are model parameters. σ(.) denotes the non-linear activation function.

One can learn model parameters by minimizing the reconstruction error:

To capture the high non-linearity in the topological structure and attributes, the two branches in Figure 1 employ K

layers in the encoder as follows:

Correspondingly, there will be K layers in the decoder. Here, h(K) i is the desired low-dimensional representation of the i-th node.

For our approach, the input of the first branch in Figure 1 is the high-order proximity matrix to capture the non-linearity in the topological structure. The explanation is delayed to the next section. The input of the second branch is the attribute matrix Z to capture the non-linearity in the attribute. Here, we denote the learned representation from the topological structure and attributes as HM and HZ respectively.

Proximity Preservation

To preserve the semantic proximity, we minimize the reconstruction loss between the input Z of the encoder and the output ˆ Z of the decoder:

The reason is disclosed in [Salakhutdinov and Hinton, 2007]. Specifically, the reconstruction loss can enforce the neural network to capture the data manifold smoothly and thus can preserve the proximity among samples [Wang et al., 2016]. Therefore, by minimizing the reconstruction loss, our approach can preserve the semantic proximity in attributes.

Similarly, to preserve the high-order proximity, we also minimize the reconstruction loss as follows:

Specifically, the high-order proximity M denotes the neighborhood structure. If two nodes have similar neighborhood structure, which means Mi· and Mj· are similar, the learned representation HM i· and HM j· by minimizing the reconstruction loss will also be similar with each other.

As discussed before, we need to preserve the first-order proximity which captures the local structure. Recall Definition 1, two nodes are similar if there exists an edge between them. Thus, to preserve this proximity, we maximize the following likelihood estimation:

where pij is the joint probability between the i-th node and the j-th node. Note that we should preserve the first-order proximity in the topological structure and attributes simultaneously so that we can obtain the consistent result between these two kinds of information. For the topological structure, the joint probability is defined as follows:

Similarly, the joint probability based on the attribute is defined as follows:

Thus, we can preserve the first-order proximity in the topological structure and attributes simultaneously by minimizing the negative log-likelihood as follows:

Consistent and Complementary Representation

Since the topological structure and attributes are the twomodal information of the same network, we should guarantee the learned representation from them is consistent [Gao et al., 2015a; 2015b]. On the other hand, these two kinds of information describe different aspects of the same node, providing complementary information. Thus, the learned representation should also be complementary. All in all, how to learn the consistent and complementary low-dimensional representation is very important.

A direct and simple method is to concatenate these two representations HM and HZ directly as the embedding result. Although this method can maintain the complementary information between two modalities, yet it cannot guarantee the consistency between these two modalities. Another widely used method is to enforce the two branches in Figure 1 to share the same highest encoding layer, that is HM = HZ . Although this method can guarantee the consistency between two modalities, it will lose too much complementary information from two modalities due to the exactly same highest encoding layer. Therefore, how to combine the topological structure and attributes together for attributed network embedding is a challenging problem.

To address this challenging problem, we propose to maximize the following likelihood estimation:

where pij is the joint distribution between two modalities, which is defined as follows:

Additionally, sij ∈ {0, 1} denotes whether HM i· and HZ j· are from the same node. In detail, sij = 1 if i = j. Otherwise, sij = 0. Furthermore, Eq. (10) is equivalent to minimize the negative log-likelihood as follows:

By minimizing Eq. (12), we can enforce HM i· andHZ j· as consistent as possible when they are from the same node while pushing away them when they are from different nodes. On the other hand, they are not exactly same, thus they can preserve the complementary information in each modality.

However, the second term in the right hand side of Eq. (12) is over strict. For instance, if two nodes i and j are similar according to the first-order proximity, the representation HM i· and HZ j· should also be similar although they are from different nodes. That is to say we should not push them away. Thus, we relax Eq. (12) as follows:

Here, we push HM i· and HZ j· together when they are from the same node while pushing them away when two nodes are not connected.

As a result, to preserve proximities and learn the consistent and complementary representation, we optimize the following objective function jointly:

By minimizing this problem, we can obtain HM i· and HZ i· , then we concatenate them as the final low-dimensional representation of the node such that we can preserve the consistent and complementary information from the topological structure and attributes.

3.3 Most Negative Sampling Strategy

Take a more detailed look at Eq. (13), it is to solve the following problem with respect to each node:

In practice, the adjacency matrix E is very sparse since many edges are not discovered. However, the undiscovered edge does not really mean two nodes are not similar. If we push away two potential similar nodes, the learned representation will become worse.

In detail, the gradient of Lci with respect to HM j· where Eij = 0 is

According to the gradient descent method, the updating rule for HM j· is HM j· ← HM j· - αpijHZ i· where α is the step size. Since HZ i· is constant when updatingHM j· , pij determines the updating rule. Furthermore, pij depends on HM i· (HZ j· )T . If two nodes i and j are similar potentially but there is no direct link, pij will be large so that HM j· will be pushed much away from HZ i· . As a result, the embedding result will become worse and worse.

To alleviate this problem, we propose a most negative sampling strategy to get a robust embedding result. Specifically, at each iteration, we calculate the similarity between HM and HZ by P = HM (HZ )T . Then, for each node i, we select the most negative sample as follows:

Based on this negative sample, the objective function Eq. (15) becomes

where j is sampled based on Eq. (17). With this most negative sampling strategy, the potential similar nodes will not be violated as far as possible. Thus, the embedding result will be more robust.

Sampling Complexity The sampling complexity is dominated by the computation of the similarity P whose complexity is O(n2 ) while the complexity of Eq. (13) is also O(n2 ). Note that we omit the complexity of computing each pij. Thus, there is no much increased overhead to employ our sampling strategy. As a result, our proposed sampling strategy is efficient and effective.

4 Experiments

4.1 Experiment Settings

Datasets In our experiments, we employ four benchmark datasets 1 : Cora, Citeseer, PubMed, and Wiki. The first three datasets are paper citation networks. The edge of each network is the citation link. The attribute of each node is the bagof-words representation of the corresponding paper. Wiki is a network with nodes as web pages. The link among different nodes is the hyperlink in the web page. We summarize the statistics of these benchmark datasets in Table 1.

Baselines To evaluate the performance of our proposed DANE, we compare it with 9 baseline methods, including 4 plain network embedding methods and 5 attributed network embedding methods. The former category contains DeepWalk [Perozzi et al., 2014], Node2Vec [Grover and Leskovec, 2016], GraRep [Cao et al., 2015], and LINE [Tang et al., 2015]. The latter one includes TADW [Yang et al., 2015], ANE [Huang et al., 2017b], Graph Auto-Encoder (GAE) [Kipf and Welling, 2016b], Variational Graph Auto-Encoder (VGAE) [Kipf and Welling, 2016b], and SAGE [Hamilton et al., 2017]. For DeepWalk and Node2Vec, we set the window size as 10, the walk length as 80, the number of walks as

1 https://linqs.soe.ucsc.edu/data

10. For GraRep, the maximum transition step is set to 5. For LINE, we concatenate the first-order and second-order result together as the final embedding result. For the rest baseline methods, their parameters are set following the original papers. At last, the dimension of the node representation is set as 200.

To obtain the high-order matrix M in Definition 2, we utilize the random walk as DeepWalk [Perozzi et al., 2014] to obtain the high-order context of each node and then construct the adjacency matrix M with a sliding window size as 10. Moreover, the architecture of our approach for four datasets is summarized in Table 2. We use LeakyReLu [Maas et al., ] as the activation function.

4.2 Results and Analysis

Node Classification To show the performance of our proposed DANE, we conduct node classification on the learned node representations. Specifically, we employ ℓ2-regularized Logistic Regression as the classifier. To make a comprehensive evaluation, we randomly select {10%, 30%, 50%} nodes as the training set and the rest as the testing set respectively. With these randomly chosen training sets, we use five-fold cross-validation to train the classifier and then evaluate the classifier on the testing sets. To measure the classification result, we employ Micro-F1 (Mi-F1) and Macro-F1 (Ma-F1) as metrics. The classification results are shown in Table 3,4,5,6 respectively. From these four tables, we can find that our proposed DANE achieves significant improvement compared with plain network embedding approaches, and beats other attributed network embedding approaches in most situations.

Node Clustering To show the performance of our proposed approach on the unsupervised task, we conduct node clustering on the learned node representations. Here, we employ K-means as the clustering method and use clustering accuracy as the metric. The clustering result is summarized in Table 7. From this table, we can find that our approach achieves much better clustering performance than the others for most cases, which further verifies the effectiveness of our proposed DANE.

Network Visualization To further show the embedding result of our approach, we visualize the node representation by using t-SNE [Maaten and Hinton, 2008]. Due to the space limitation, we only post the result of three representative baseline methods for the Cora dataset. The visualization result is shown in Figure 2. From Figure 2, we can find that our approach can achieve more compact and separated clusters compared with the rest baseline methods. Thus, our approach can achieve better performance on both supervised and unsupervised tasks.

Effect of the Sampling Strategy To evaluate the effect of our sampling strategy, we compare it with two alternative methods. The first one is the random sampling method (DANE-RS). The second one is the importance sampling method (DANE-IS). For DANE-IS, we use pi = exp(-Pij ) ∑j exp(-Pij) , ∀i as the sampling probability. Intuitively, this probability will let dissimilar points have large probability. With these two sampling methods, we learn node representations and then conduct node classification on the learned node representations for the Cora dataset. The result is shown in Table 8. We can find that DANE-RS has the worst performance since it fails to discriminate different negative samples. DANE-IS has a better result, but it is still worse than our method. Because our proposed sampling strategy can always find the most negative samples to refine node representations as far as possible.

5 Conclusion

In this paper, we propose a novel deep attributed network embedding approach, which can capture the high non-linearity and preserve the proximity both in the topological structure and node attributes. Meanwhile, the proposed approach can learn a consistent and complementary representation from the topological structure and node attributes. The effectiveness has been verified by extensive experiments.

Acknowledgements

This work was partially supported by the following grants: NSF-IIS 1302675, NSF-IIS 1344152, NSF-DBI 1356628, NSF-IIS 1619308, NSF-IIS 1633753, NIH R01 AG049371.