Tri-Party Deep Network Representation

1 Introduction

Many network applications, such as social networks, protein networks, and citation networks, are characterized with complex structure and rich node content information, where the network structure is naturally sparse in that only a small number of nodes are connected and the node content is usually represented as text information indicating the properties of a node, such as the title or abstract information of each paper (node) in a citation network. The complexity of networked data imposes great challenge to many machine learning tasks such as node classification in networks. To address this problem, network representation [Perozzi et al., 2014;

Tang et al., 2015; Yang et al., 2015; Tian et al., 2014; Chang et al., 2015] encodes each node in a common, continuous, and low-dimensional space while preserving the neighborhood relationship between nodes, so machine learning algorithms can be applied directly. For network representation, existing methods mainly employ network structure based methods or node content based methods.

Majority network representation methods are based on network structure. Early works aim to learn social dimensions [Tang and Liu, 2009] or knowledge bases [Bordes et al., 2011; Socher et al., 2013] to embed the entities in a network. Inspired by the deep learning techniques in natural language processing [Mikolov et al., 2013], Perozzi et al. [Perozzi et al., 2014] recently proposed a DeepWalk algorithm which employs neural network models to learn a feature vector for each node from a corpus of random walks generated from networks. These methods take the network structure as input but ignore content information associated to each node.

From the content perspective, many methods exist to represent a text message into a vector space. Early studies employ bag of word approaches (e.g., TFIDF) or topic models (e.g. LDA [Blei et al., 2003]) to represent each document as a vector. However, these models do not consider the context information of a document (i.e., order of words), resulting in suboptimal representation. Recently, neural network or deep learning based approaches [Mikolov et al., 2013; Le and Mikolov, 2014; Luong et al., 2013] have emerged for text embedding. The Skip-grammodel [Mikolov et al., 2013] employs a simple neural network model to learn distributed vectors for words. Due to its simplicity, efficiency, and scalability, Skip-grammodel is further extended as paragraph vector model [Le and Mikolov, 2014], which learns latent vector representation for arbitrary piece of text.

The drawback of existing methods [Tang and Liu, 2009; Perozzi et al., 2014; Tang et al., 2015; Le and Mikolov, 2014], regardless of network exploration approaches or text modeling methods, is twofold: (1) they only utilize one source of information, so the representation is inherently shallow. (2) all these methods learn network embedding in a fully unsupervised way. For many tasks, such as node classification, we may have a limited number of labeled nodes, which provides usefully information to assist network representation.

When considering networks as a whole, the main challenge of learning latent representation for network nodes is twofold:

(a) Input: ANetwork

(b) Output: Representation

Figure 1: Our model takes an information network as input and outputs a low-dimensional representation for each node. In this toy citation network, each node denotes a paper, links are citation relationships, and texts are paper titles. Red and blue nodes are labeled nodes from two classes (transfer learning vs. video coding). Remaining nodes are unlabeled. (1) paper 1 and paper 9 share two common words transfer and networks in their titles. If we ignore their labels, they will likely be represented with similar representation. So label is useful. (2) paper 14 and paper 1 belong to the transfer learning class. Although paper 14 is more similar to paper 9 in terms of shared title words, the weak citations/connections between paper 1 and paper 14 will make them close to each in the learned node representation space. So structure is useful for node representation. (3) By combining structure, text, and labels, our method is positioned to learn best representations.

• ÷ Network Structure, Node Content, and Label Information Integration (Challenge 1) How to learn node embedding for networks containing links and rich text information, and further tailor the representation for learning tasks provided with labeled samples?
• ÷ Neural Network Modeling (Challenge 2) How to design effective neural network models for networked data, in order to obtain deep network representation results?

In terms of neural network modeling (Challenge 2), a straightforward method for this problem is to separately learn a node vector by using DeepWalk [Perozzi et al., 2014] for network structure and learn a document vector via Paragraph Vectors model [Le and Mikolov, 2014] (the state-of-the art model to embed text into a vector space), and then concatenate these two vectors into a unified representation. However this simple combination is suboptimal because it ignores the label information, and overlooks interactions between network structures and text information.

In order to exploit both structure and text information for network representation (Challenge 1), a recent work TADW [Yang et al., 2015] shows that DeepWalk is equivalent to factorize a matrix M (sum of a series transition matrix). However, this method has following drawbacks: (1) The accurate matrix M for factorization is non-trivial and very difficult to obtain. As a result, TADW has to factorize an approximate matrix, which will weaken its representation power; (2) TADW simply ignores the context of text information (e.g., orders of words), so cannot appropriately capture the semantics of the words and nodes in a network setting; (3) unlike neural network models that can scale up to millions of records in a single machine [Mikolov et al., 2013], TADW requires expensive matrix operation like SVD decomposition, which prohibits TADW from handling large scale data.

In this paper, we propose a tri-party deep network representation model, TriDNR, which uses a coupled neural network architecture to exploit network information from three parties: node structure, node content, and node labels (if available). At the node level, we maximize the probability of observing the surrounding nodes given a node vi in a random walk sequence, which well preserves inter-node relationship in networks. At the node content and node label levels, we maximize the co-occurrence of word sequence given a node and co-occurrence of word sequence given a label, which accurately captures the node-word correlation and label-word correspondence. The tri-party information mutually enhances each other for optimal node representation. An example of using TriDNR to represent nodes of a citation network to a two dimensional space is shown in Fig 1.

2 ProblemDefinition

An information network is represented as G = (V↪ E↪ D↪ C), where V = ¶vi♦i=1↪··· ↪N consists of a set of nodes, ei↪j = (vi↪ vj) 2 E is an edge encoding the edge relationship between the nodes, di 2 D is a text document associated with each node vi, C = L S U is the class label information of the network, with L denoting the labeled nodes and U being the unlabeled nodes. The network representation aims to learn a low-dimensional vector vvi 2 Rk (k is a smaller number) for each node vi in the network, so that nodes close to each other in network topology or with similar text content, or sharing the same class label information are close in the representation space. Fig 1 demonstrates the importance of combining structure, text, and labels for learning good representations.

In this paper, we assume the network has partial labeled nodes. If the label set L = ;, the representation becomes pure unsupervised, and our proposed solution is still valid.

3 Preliminary: Skip-Gram and DeepWalk

Recently, Skip-Gram [Mikolov et al., 2013], which is a language model exploiting word orders in a sequence and assuming that words closer are statistically more dependent or related, has drawn much attention due to its simplicity and efficiency. Specifically, Skip-Gram aims to predict the context (surrounding words) within a certain window given current word by maximizing the following log-likelihood:

where b is the context width (window size), wt-b : wt+b is a sequence of words excluding the word wt itself. The probability P(wt-b : wt+b♣wt) is computed as:

Eq. (2) assumes that the contextual words wt-b : wt+b are independent given word wt. P(wt+j ♣wt) is computed as:

where vw and v0w are the input and output vectors of w. After training the model, the input vector vw can be used as the final representation of word w.

3.1 DeepWalkModel

Motivated by the Skip-Gram, DeepWalk [Perozzi et al., 2014] constructs a corpus S that consists of random walks generated from the network. Each random walk v1 ! v3 ! · · · ! vn can be considered as a sentence and each node vi can be considered as a word in neural language models. Then DeepWalk algorithm trains the Skip-Gram model [Mikolov et al., 2013] on random walks, and obtain a distributed representation vector for each node. The objective of DeepWalk model is to maximize the likelihood of the surrounding nodes given current node vi for all random walks s 2 S:

where N is the total number of nodes. The architecture of DeepWalk model is illustrated in the left panel of Fig 2.

DeepWalk can only utilize the network information for model learning, without considering any text information augmented with each node and label information provided by the specific task like node classification.

4 Tri-Party Deep Network Representation

In this section, we present our tri-party deep network representation algorithm for jointly utilizing network structure, text content, and label information to learn a latent vector for each node in the network.

We use neural network models to learn vvi , the latent representation for node vi in a network. This latent representation vvi acts as an input vector in our neural network model. More specifically, our TriDNR algorithm consists of two steps:

1. Random Walk Sequence Generation uses network structure as the input and randomly generates a set of walks over the nodes, with each walk rooting at a node vi and randomly jumping to other nodes each time. The random walk corpus can capture the node relationship.
2. Coupled Neural Network Model Learning embeds each node into a continuous space by considering the following information: (a) random walk corpus which captures the inter-node relationship, (b) the text corpus which models the node-content correlations, (c) label information which encodes label-node correspondences.

4.1 Model Architecture

Our coupled neural network model architecture is illustrated in the right panel of Fig 2, which has the following properties:

1. Inter-node RelationshipModeling. The upper layer of TriDNR learns the structure relationship from the random walk sequences, under assumption that connected nodes are statistically dependent on each other.
2. Node-content correlations Assessing. The lower layer of TriDNR models the contextual information (nodecontent correlations) of words within a document.
3. Connections. We couple these two layers by the node v1 in the model, indicating that v1 is influenced by both random walk sequences and node content information.
4. Label-content Correspondence Modeling To utilize the valuable class label information of each node, we also use the label of each document as input and simultaneously learn the input label vectors and output word vectors, providing directly modeling between node labels and node content.

Note that the label information is not used for inter-node relationship modeling. This is because we can hardly assess the class label of a random walk sequence.

The lower level (panel) of Fig 2, which exploits document and class label information, can be formalized by the following objective function:

where w-b : wb is a sequence of words inside a contextual window of length b. ci is the class label of node vi. Note that if no label information is used (i.e., ♣L♣ = 0), the first term vanishes, Eq. (5) will become the Paragraph Vector model [Le and Mikolov, 2014], which exploits the text information to learn vector representation for each document.

Given a network G which consists of N nodes (i.e., V = ¶vi♦i=1↪··· ↪N), suppose the random walks generated in G is S, our TriDNR model aims to maximize the following loglikelihood:

where ↵ is the weight that balances network structure, text, and label information. b is the window size of sequence, and wj indicates the j-th word in a contextual window.

Given equation Eq. (6), the first term requires the calculation of P(vi+j♣vi), the probability of observing surrounding nodes given current node vi, which can be computed using the soft-max function as follows:

where vv and v0v are the input and output vector representation of node v. Furthermore, the probability of observing contextual words w-b : wb given current node vi is:

where v0wj is the output representation of word wj and W is the number of distinct words in the whole network. Similarly, the probability of observing the words given a class label ci is defined as:

From Eq. (8) and Eq. (9), we know that the text information and label information will jointly affect v0wj , the output representation of word wj , which will further propagate back to influence the input representation of vi 2 V in the network. As a result, the node representation (i.e., the input vectors of nodes) will be enhanced by both network structure, text content, and label information.

4.2 Model Optimization

We train our model Eq. (6) using stochastic gradient ascent, which is suitable for large-scale data. However, computing the gradient in Eq. (7) is expensive, as it is proportional to the number of nodes in the network N. Similarly, computing the gradient in Eq. (8) and Eq. (9) are proportional to the unique number of words in the document content W. To handle this problem, we resort to the hierarchical soft-max [Morin and Bengio, 2005], which reduces the time complexity to O(Rlog (W)+Nlog (N)) where R is the total number of words in the document content.

Specifically, the hierarchical model in our algorithm uses two binary trees, one with distinct nodes as leaves and another with distinct words as leaves. The tree is built using Huffman algorithm so that each vertex in the tree has a binary code and more frequent nodes (or words) has shorter codes. There is a unique path from the root to each leaf. The interval vertices of the trees are represented as real-valued vector with the same dimension as the leaves. So instead of enumerating all nodes in Eq. (7) in each gradient step, we only need to evaluate the path from the root to the corresponding leaf in the Huffman trees. Suppose the path to the leaf node vi is a sequence of vertices (l0↪ l1↪ · · · ↪ lP ), (l0 = root, lP = vi), then

where P(lt♣vi) can be further modeled by a binary classifier which is defined as:P(lt♣vi) = σ(v>vi v0vlt ) (11)

here σ(x) is the sigmoid function, and v0vlt is the representation of tree vertex lt's parent. By doing this, the time complexity is reduced to O(Nlog N). Similarly, we can use hierarchical soft-max technique to compute the words and labels in Eq. (8) and Eq. (9).

5 Experimental Results

5.1 Experimental Setup

We report our experimental results on two networks. Both of them are citation networks and we use the paper title as node content for each node in the networks.

DBLP dataset 1 consists of bibliography data in computer science [Tang et al., 2008]. Each paper may cite or be cited by other papers, which naturally forms a citation network. In our experiments, we select a list of conferences from 4 research areas, database (SIGMOD, ICDE, VLDB, EDBT, PODS, ICDT, DASFAA, SSDBM, CIKM), data mining (KDD, ICDM, SDM, PKDD, PAKDD), artificial intelligent (IJCAI, AAAI, NIPS, ICML, ECML, ACML, IJCNN, UAI, ECAI,COLT, ACL, KR), computer vision (CVPR, ICCV, ECCV, ACCV, MM, ICPR, ICIP, ICME). The DBLP network consist of 60,744 papers (nodes), 52,890 edges in total.

CiteSeer-M10 is a subset [Lim and Buntine, 2014] of CiteSeerX data 2 which consist of scientific publications from 10 distinct research areas: agriculture, archaeology, biology, computer science, financial economics, industrial engineering, material science, petroleum chemistry, physics, and social science. This dataset consists of multidisciplinary 10 classes, with 10,310 publications and 77,218 edges in total.

The following algorithms are comparing in our paper:

1. DeepWalk [Perozzi et al., 2014] learns network representation using network structure only.
2. LINE [Tang et al., 2015] is a state-of-the-art algorithm for network representation based on network structure.
3. Doc2Vec [Le and Mikolov, 2014] is the Paragraph Vectors algorithm which embeds any piece of text in a distributed vector using neural network models. Here we use PV-DBOWmodel in [Le and Mikolov, 2014].
4. LDA [Blei et al., 2003] is the Latent Dirichlet allocation algorithm that learns a topic distribution to represent each document (or text).

1 http://arnetminer.org/citation (V4 version is used)

2 http://citeseerx.ist.psu.edu/

1. RTM [Chang and Blei, 2009] is the relational topic model which captures both text and network structure to learn topic distributions of each document.
2. TADW [Yang et al., 2015] is a state-of-the-art algorithm that utilizes both network and text information to learn the network representation.
3. DW+D2V approach simply concatenates the vector representations learned by different neural network models, i.e., DeepWalk and Doc2Vec.
4. TriDNR is our proposed tri-party deep network representation algorithm that exploits network structure, node content, label information for learning.
5. DNRL is a variant of our TriDNR, which only uses node content and label information (lower layer of Fig 2) and ignores the network structure information.

Measures & Parameter Setting We perform node classification to evaluate the quality of different algorithms. In each network, p% nodes are randomly labeled, the rest are unlabeled. The whole network, including node content, are used to learn the network representation. Once we obtained the node vectors using different comparing methods, we train a linear SVM from the training data (nodes) to predict unlabeled nodes. We choose a linear classifier, instead of nonlinear model or sophisticated relational classifiers [Sen et al., 2008], in order to reduce the impact of complicated learning approaches on the classification performance.

The default parameter for TriDNR are set as follows: window size b=8, dimensions k =300, training size p = 30%, ↵ = 0▷8. For fairness of comparison, all comparing algorithms will use the same same number of features k. The parameters for other algorithms will keep the same or be close to TriDNR as much as possible. For instance, for all neural network models, we use window size b = 8. The rest parameters are set following the suggestion in their original papers. For each parameter setting, we repeat the experiment 10 times and report the average results and standard deviation.

5.2 Performance on Node Classification

We vary the percentages of training samples p% from 10% to 70% and report the results in Table 1 and Table 2.

Number of Features Number of Features

Figure 3: Results with Different Number of Features k.

Table 1 and Table 2 show that DeepWalk and LINE algorithms perform fairly poor on citation networks. This is mainly because the network structure is rather sparse and only contains limited information. Doc2Vec (Paragraph Vectors) is much better than DeepWalk, especially on DBLP dataset, as the text content (title) has rich information comparing to network structure. When concatenating the embeddings from DeepWalk and Doc2Vec, as DW+D2V does, the representation is substantially improved. However, DW+D2V is still far from optimal, comparing with TriDNR algorithm.

Importance of Label Information. Our experimental results show that DNRL, which uses label information to learn the network embedding (only used the lower layer of our TriDNR model), has already significantly outperformed the naive combination of two neural network models (DW+D2V). This observation validates the importance of label information for network representation.

Effectiveness of Coupled design. When we add another layer of neural network on top of DNRL, our proposed TriDNR model shows that it outperforms DeepWalk, Doc2Vec, and DW+D2V by a large margin. The experimental result demonstrated the importance of using label information and the effectiveness of our coupled architecture design.

Topic model based algorithms: As for the topic model based algorithms, relational topic model (RTM) outperforms the traditional topic model LDA. This is because RTM takes the network structure into consideration. Both LDA and RTM are not comparable to TriDNR.

TriDNR vs. TADW: The results in Table 1 and 2 demonstrate that TriDNR is also superior to TADW. This is because: (1) TADW is a matrix factorization algorithm which factorizes a matrix M (sum of a series transition matrix) together with a text matrix T . In reality, an accurate M is very computationally expensive so TADW only factorizes an approximate M, which will affect its representation power; (2) TADW does not consider context information, and its T matrix cannot preserve the orders of word; (3) TADW does not explore the valuable label information for a specific task, resulting in suboptimal result only. In contrast, TriDNR takes each document (node) and the words within of a window (including the order information) into consideration, which well preserve the neighborhood relationship and documents. Additionally, TriDNR exploits label information, which significantly improves the representation power, leading to a good classification performance.

Overall, TriDNR significantly outperforms its peers. With p%=70, TriDNR (0.777) beats DeepWalk (0.434) and TADW (0.681) by 79.0% and 14.1% in the Citeseer-M10 network.

Results with different number of dimensions k

We vary the number of dimensions (k) used in comparing algorithms, and report the results in Fig 3. When k increases from 50 to 150, there is a slightly increase for TriDNR algorithm. Afterwards, not much difference is observed with different number of features. The results show that TriDNR is very stable with various dimension size.

5.3 Case Study

In this subsection, we retrieve the most similar nodes w.r.t. a given query node. Specifically, we compute the top 5 nearest neighbors with Consine distance based on the vector representations learned by different algorithms. The results are shown in Table 3.

The query paper is the best paper of KDD 2006 and is also one of the top-10 downloaded paper according to ACM digital library 3 (access on 19/01/2016). Basically, the paper considers using advanced optimization techniques like cutting plane algorithm for training linear svm algorithm.

Table 3 shows that all results retrieved by TriDNR are similar or closely related to SVM or optimization techniques. For instance, the first result optimized cutting plane algorithm for support vector machines is actually a following-up work of the query paper. In contrast, the results returned by Doc2Vec or TADW only have 1 record matching with the query, which is mostly based on the term linear time. For DeepWalk, there are indeed some similar answers by using the network information (citation relationship), because this is a highly cited

3 http://dl.acm.org/event.cfm?id=RE329

Table 3: Top-5 Similar Node Search: matched results are (÷)

Query: Training Linear SVMs in Linear Time [Joachims, 2006]

TriDNR :

1. optimized cutting plane algorithm for support vector machines (÷)
2. a sequential dual method for large scale multi-class linear svms (÷)
3. proximal regularization for online and batch learning (÷)
4. a dual coordinate descent method for large-scale linear svm (÷)
5. bootstrap based pattern selection for support vector regression (÷)

Doc2Vec :

1. training linear discriminant analysis in linear time (÷)
2. circularity measuring in linear time
3. mining association rules in hypertext databases
4. approximate matching in xml
5. disaggregations in databases

DeepWalk :

1. bootstrap based pattern selection for support vector regression (÷)
2. large margin training for hidden markov models with ...
3. optimized cutting plane algorithm for support vector machines (÷)
4. extremely fast text feature extraction for classification and indexing
5. proximal regularization for online and batch learning (÷)

TADW :

1. Circularity Measuring in Linear Time
2. Training Linear Discriminant Analysis in Linear Time (÷)
3. Maximal Incrementality in Linear Categorial Deduction
4. Variational Linear Response
5. How Linear are Auditory Cortical Responses

paper (1348 according to Google Scholar by 19/01/2016). However, its result are still worse than our TriDNR algorithm.

5.4 Network Visualization

An important application of network representation is to create meaningful visualizations that layout a network in two dimensional space. Following [Tang et al., 2015], we learn a low-dimensional representation for each node and map the Citeseer-10 network into a 2D space in Fig 4.

In Fig 4, the visualization using Doc2Vec and TADW algorithms are not very meaningful, in which the papers from the same cluster are not clustered together. The result obtained by DeepWalk is slightly better, in which a large group is formed representing the research of Petroleum Chemistry. However papers from other groups are still highly overlapping. The visualization results of TriDNR are quite clear, with meaningful layout for each class.

6 Conclusion

In this paper, we proposed a Tri-party deep network representation algorithm. We argued that most exiting algorithms are simple shallow methods that only use one aspect of node information. In addition, none of the existing method is able to utilize the label information in the network for representation. Accordingly, we proposed a coupled neural network based algorithm to exploit inter-node relationships, node-content correlation, and label-content correspondence in a networks to learn an optimal representation for each node in the network. Experimental results demonstrated the superb performance of our algorithms. The key contribution of the paper is twofold: (1) we exploit network representation from multiple parties and different network levels, and (2) we propose a new neural network model for deep network representation learning.