Link Prediction via Ranking Metric Dual-Level Attention Network Learning

1 Introduction

Link prediction is an important problem for complex network analysis [Liben-Nowell and Kleinberg, 2007], which has a large number of applications in many disciplines like network ranking [Zhao et al., 2015] and network clustering [Zhao et al., 2016a]. The essential problem of link prediction is to infer the missed or new relationships of the network based on the currently observed connections, which has attracted considerable attention recently [Katz, 1953; Cao et al., 2014].

Many previous approaches for the problem of link prediction are neighborhood-based methods [Menon and Elkan, 2011; Wang et al., 2007; 2016], which learn the proximity model for the link endpoints from the local neighborhood around them, and then infer their closeness for link prediction. Although the methods arising from these approaches could be simple and efficient, they still suffer from the localized view of network connection [Mart´ınez et al., 2016]. To tackle the localized view problem, the path-based approaches [Katz, 1953; Cao et al., 2014; Zhang et al., 2014]

were proposed for learning the proximity of link endpoints based on their betweenness paths, and it can be shown that such approaches are more effective [Mart´ınez et al., 2016]. Although the path-based prediction methods have achieved promising performance, most of them still suffer from the insufficiency of discriminative path feature representation [Sun et al., 2013].

Currently, the existing path-based link prediction methods [Cao et al., 2014; Zhang et al., 2014; Liu et al., 2014] learn the semantic path representation based on the hand-crafted meta feature (e.g., bag-of-words). However, the rich content information in networking nodes is not fully utilized on the feature representation in existing methods, which is critical for learning discriminative path representation [Miller et al., 2009]. Recently, various embedding methods are proposed to learn the semantic of similar words [Mikolov et al., 2013] and encode the content information into low-dimensional continuous embedding space. Since the node contents are always the sequential data with variant length, it is natural to employ the deep recurrent neural networks [Hochreiter and Schmidhuber, 1997] to learn the semantic representation of the nodes. On the other hand, learning the effective joint representation of betweenness paths is also a challenging issue for path-based link prediction. The shorter the path, the higher chance that the path influences the link formation between its endpoints [Katz, 1953]. Furthermore, the importance of the betweenness paths for link formation varies according to the specific endpoints, and a number of betweenness paths are redundant and irrelevant for link formation [Sun et al., 2013]. Thus, learning the discriminative joint representation of the betweenness paths is critical for path-based link prediction.

In this paper, we consider the problem of link prediction from the viewpoint of learning path-based proximity ranking metric embedding. We then develop the ranking metric dual-level attention networks to learn the discriminative joint representation of the betweeness paths of the endpoints for link prediction. The main contributions of this paper are illustrated as follows:

• Unlike the previous studies, we study the problem of link prediction from the viewpoint of path-based proximity ranking. We propose the dual attention networks to learn the discriminative joint representation from the betweenness paths of the endpoints for learning proxim-

ity ranking metric embedding.

• We incorporate the multi-step reasoning framework for our proposed attention networks to enable the progressive joint representation learning from the endpoint content information and their betweenness paths to further improve the performance of link prediction.
• We conduct extensive experiments on two large-scale datasets to show that our method achieves better performance than other state-of-the-art solutions to the problem.

The rest of this paper is organized as follows. In Section 2, we introduce the problem of link prediction from the viewpoint of path-based proximity ranking metric learning framework and propose the path-based ranking metric dual-level attention networks to learn the discriminative joint representation of the endpoints for link prediction. A variety of experimental results are presented in Section 3. We provide a brief review of the related work about link prediction in Section 4. Finally, we provide some concluding remarks in Section 5.

2 Link Prediction via RankingMetric Dual-Level Attention Network Learning

In this section, we first present the problem of link prediction from the viewpoint of learning proximity ranking metric embedding, and then introduce the path-based ranking metric dual-level attention network learning framework.

2.1 The Problem

Before presenting the problem, we first introduce some basic notions and terminologies. Since the contents of nodes in networking sites are always the sequential data with variant length, we then encode them into the fixed length feature representation using recurrent neural networks. Given a set of nodes X = {x1, x2, . . . , xn} of size n, we take the last hidden layer of recurrent neural networks as their semantic embeddings by V = {v1, v2, . . . , vn} where vi is the embedding vector for the latent representation of the i-th node. We then denote the link set of nodes in networks by E = {e1, e2, . . . , em} of size m, where ei = (xj , xk) is the i-th edge.

We denote the set of betweenness paths for the s-th node and the t-th node with length l by P (l) (s,t) , which is derived from set E. Given the path length threshold L, we consider that the path set P(s,t) is formed by P(s,t) = P (2) (s,t) ∪ P (3) (s,t) . . .∪P (L-1) (s,t) , which is the set union of P (l) (s,t) . We denote the collection of path sets by P. We then consider that the predictive function fw(P(s,t)) = wT h(P(s,t)) quantifies the likelihood of the link formation between the s-th node and the t-node based on path set P(s,t). The w is the parameter vector and h(P(s,t)) is the embedding model for path set P(s,t). Inspired by negative edge sampling [Tang et al., ], we introduce the relative ranking metric to learn the discriminative model for link prediction, which is in the form of triplet constraints. Given edge e = (xi, xj), we randomly sample another node xk ∈ X to obtain the negative link e′ = (xi, xk)

(i.e., e′ /∈ E). We then denote the triplet constraint by the order tuple (i, j, k), meaning that "the likelihood of link formation between the pair of the i-th node and the j-th node is higher than that of the pair of the i-th node and the k-th node". Let T = {(i, j, k)} be the set of triplet constraints derived from the negative sampling process based on set E in networks. More formally, we aim to learn the ranking metric function that for any (i, j, k) ∈ T , the inequality holds:

Using the notations above, we define the problem of link prediction from the viewpoint of path-based proximity ranking metric learning as follows. Given the network graph G = (X,E) with node set X and edge set E, our goal is to learn the ranking metric predictive function fw(P(s,t)) for link prediction. The endpoints e = (xs, xt) (e /∈ E) with the highest value according to fw(P(s,t)) is then returned.

2.2 Path-based Proximity RankingMetric Embedding with Recurrent Neural Networks

In this section, we propose the hierarchical path-based proximity ranking metric learning method for link prediction in networking sites in Figures 1(a) and 1(b). We first present the dual-level attention learning method and then introduce the multi-step reasoning framework for path-based ranking metric embedding.

We employ the efficient path enumeration algorithm [Wang et al., 2007] to collect the set P(s,t) of betweenness paths for the link endpoints xs and xt in network. We then choose the proper embedding method for path representation. Given a path of nodes pi = (xi1, xi2, . . . , xik) (pi ∈ P(s,t)), we learn the node-level embedding of xj by pre-trained LSTM model [Hochreiter and Schmidhuber, 1997] as vij and then use the sequence (vi1, vi2, . . . , vik) as the input of the bidirectional LSTM model for path representation. The bidirectional LSTMmodel consists of a forward LSTMmodel and a backward LSTMmodel. The backward LSTMmodel has the same network structure with the forward one while its input sequence is reversed. We denote the hidden state of the j-th node in path pi as hfij by forward LSTMmodel, and its hidden state by backward LSTM model as hbij . Thus, the hidden state of the j-th node from the bidirectional LSTM layer is denoted by hij = [hfij , hbij ], and then the representation of path pi is given by pi = (hi1, hi2, . . . , hik).

Inspired by attention mechanism [Xu et al., 2015], we propose the dual-level attention networks that jointly explore the discriminative nodes and critical paths according to the paired nodes xs and xt for link prediction. The joint representation of the paired nodes xs and xt is given by the elementwise product of their embeddings from the pre-trained LSTM model as z(0) (s,t) = vs ⊗ vt. We denote the vector z(0) (s,t) as the joint representation for paired nodes and ⊗ is the element-wise product operator. We first introduce the nodelevel attention network to explore the discriminative node embeddings from the path representation. Given the joint representation of paired nodes z(0) (s,t) and path representation pi = (hi1, hi2, . . . , hik), the node-level attention score of

(b) Reasoning Dual-Level Attention Network

Figure 1: The Overview of Path-based Proximity Ranking Metric Dual-Level Attention Learning (PRML). (a) The set P(s,t) of the betweenness paths for paired nodes xs and xt is collected by path enumeration algorithm. (b) The dual-level attention network h(P(s,t)) learns the discriminative joint representation of the betweenness paths for paired nodes xs and xt. (c) The path-based proximity ranking metric function fw(·) is then trained with triplet constraints T and joint representation of their betweeness paths.

node xij is given by:

where W(n) zs , Whs are parameter matrices, h(n) is parameter vector and bn is the bias vector. The hij is the hidden state of the j-th node from the bidirectional layer. For each node xij, its activation by softmax function is given

tion of node-level attention scores. Therefore, the latent representation of path pi with attention mechanism is denoted by yi = ∑j αij(z(0) (s,t) )hij. We then propose the path-level attention network to explore the critical paths according to paired nodes representation z(0) (s,t) . Given the representation of paired nodes z(0) (s,t) and the path set P(s,t), the path-level attention score of path pi ∈ P(s,t) is given by:

where W(p) zs , Wys are parameter matrices, h(p) is parameter vector and bp is the bias vector. The vector yi is the latent representation of path yi with node-level attention mechanism. We note that the shorter the path, the higher chance that the path influences the link formation between two nodes. Unlike the node-level attention, we introduce the damping factor that penalizes the contribution of longer path exponentially for path-level attention score regularization. For each path pi, its activation by softmax function is given by

normalization of path-level attention scores with path length awareness. The exp(-γli) is the damping factor for path pi, where li is the path length and γ is the coefficient. Therefore, the latent representation of path set P(s,t) with attention mechanism of paired nodes representation z(0) (s,t) is given by gz(0) (s,t) (P(s,t)) = ∑pi∈P(s,t) βi(z(0) (s,t) ) ∑j αij(z(0) (s,t) )hij , where βi(z(0) (s,t) ) is the path-level activation coefficient and αij (z(0) (s,t) ) is the node-level activation coefficient.

We then incorporate the multi-step reasoning framework [Sukhbaatar et al., 2015] for the proposed dual-level attention network to further improve the performance of link prediction. Given dual-level attention network gz(·) and path set P(s,t), the reasoning dual-level attention network learning is given by

which is recursively updated. The latent representation of path set P(s,t) is returned after the K-th update, given by h(P(s,t)) = z(K) (s,t) . The learning process of reasoning duallevel attention network is illustrated in Figure 1(b).

2.3 Proximity RankingMetric Learning

In this section, we present the details of our path-based proximity ranking metric learning method and summarize the main training process in Algorithm 1.

We first start with negative edge sampling for set E to construct the triplet constraints T for ranking metric learning. For each triplet constraint t = (i, j, k), we design its ranking loss function by

where the hyper-parameter C (0 < C < 1) controls the margin in the loss function and fw(P(i,k)), fw(P(i,j)) are the embedding functions of set P(i,k) and P(i,j) by reasoning duallevel attention network, respectively. We denote all the model coefficients including neural network parameters and the result function parameter by Θ. Therefore, the objective function in our learning process is given by:

where λ is the trade-off parameter between the training loss and regularization. To optimize the objective, we employ the stochastic gradient descent (SGD) with the diagonal variant of AdaGrad in [Kingma and Ba, 2014].

3 Experiments

In this section, we conduct several experiments on the coauthorship network DBLP and the collaborative development network Github, to show the effectiveness of our apporach for the problem of link prediction in heterogeneous networks.

3.1 Experimental Setting

We present the data preparation procedure for obtaining the datasets from both networks. For DBLP dataset, we choose the faculty in research institutions as the user node, and the paper with the number of citations greater than 3 as the item node. The DBLP dataset contains 15,728 user nodes and 97,523 item nodes. The number of observed links between user node and item node is 118,245, and the number of observed links among item nodes is 247,081. For Github dataset, we choose the developer that participates in more than 20 projects as user node, and the project developed by more than 500 users as item node. The Github dataset is composed of 2,407 user nodes and 6,490 item nodes. The number of observed links between user node and item node is 19,153 and the number of observed links among user nodes is 13,153. Thus, the average degree in DBLP data is 3.2 and average degree in Github data is 3.6. We sort the network links based on their established timestamps. We use the first 70% links as training set, 10% ones as the validation set and the remaining 20% links as the testing set. So the training, validation and test data do not have overlap. The dataset will be provided later.

3.2 Performance Comparisons

We evaluate the performance of our proposed method based on three widely-used ranking evaluation criteria for the problem of link prediction, i.e., mean average precision (MAP) [Chang et al., 2015; Wang et al., 2016], normalized discounted cumulative gain (nDCG) and area under the curve (AUC) [Menon and Elkan, 2011; Wang et al., 2007]. We compare our proposed method with other six state-of-the-art methods for the problem of network link prediction as follows:

• FactRank method [Menon and Elkan, 2011] employs the low-rank approximation based ranking function for link prediction form the partial observed network adjacent matrix.
• Katz method [Katz, 1953] estimates the likelihood of the unknown links based on the set of betweenness path of their endpoints.
• LPGM method [Wang et al., 2007] is the local probabilistic graphical model based on the co-occurrence probability of two nodes for link prediction.
• MMMF method [Zhu et al., 2016] is the max-margin matrix factorization model for predicting the missing links in the partially observed network.
• HNE method [Chang et al., 2015] learns the heterogeneous network embedding of both user node and item node based on the network content and its observed structure for link prediction.
• SDNE method [Wang et al., 2016] learns the vertex embedding of heterogeneous network based on first-order

and second-order network proximity for link prediction.

Among them, method Katz is based on set of betweenness path for the link endpoints, methods FactRank is ranking model based on low-rank approximation, methods LPGM and MMMF are probabilistic model, and methods HNE and SDNE are network embedding model for link prediction. Unlike the previous studies, our method PRML learns the ranking metric predictive function based on path set for link prediction. We then denote our PRML with one reasoning step by PRML(1) and our method with two steps by PRML(2), respectively.

Tables 1 and 2 show the experimental results of the methods on MAP@10, NDCG@10 and AUC using Github and DBLP datasets, respectively. The hyperparameters and parameters which achieve the best performance on the validation set are chosen to conduct the testing evaluation. We report the average value of all the methods on three evaluation criteria. The experiments reveal two-fold interesting points:

• The path-based learning method Katz achieves better performance than the neighborhood-based factorization method FactRank, which suggests that the path-based information is critical for link prediction.
• The deep network embedding methods HNE and SDNE outperform the other baseline algorithms. This suggests that the performance of link prediction can be improved with discriminative node feature representation.
• In all the cases, our PRMLmethod achieves the best performance. This fact shows that the proximity ranking metric learning framework that exploits both discriminative joint representation of betweenness paths and multistep reasoning can further improve the performance of link prediction.

In our approach, there are three essential parameters, which are the dimension of node embedding, the proportion of training data used for model learning and the threshold of path length using both validation datasets. We plot the performance of PRML(1) and PRML(2) using Github dataset with red and green lines, while illustrating the performance of PRML(1) and PRML(2) using DBLP dataset using blue and black lines. We then investigate the effect of these parameters of our method by varying the dimension of node embedding from 60 to 180 in Figures 2(a), 2(b) and 2(c), the proportion of training data for model learning from 10% to 90% in Figures 3(a), 3(b) and 3(c), and the threshold of path length from 3 to 11 in Figures 4(a), 4(b) and 4(c), respectively. We observe that our method achieves the best performance on Github dataset when the dimension of node embedding is set to 120 and the threshold of path length is set to 7. We also report that the best performance of our method can be achieved on DBLP dataset when the dimension of node embedding is set to 150 and the threshold of path length is set to 9. This suggests that by leveraging the proximity sequence of nodes with reasoning dual-level attention network, we can further improve the performance of link prediction.

We train the proposed method on machines with Linux OS, Intel(R) Core i7-5930K 3.50GHz and two GTX TITAN X graphic cards. The running time of training PRML(1) and PRML(2) on Github dataset are 8 hours and 14 hours. The time cost of learning PRML(1) and PRML(2) on DBLP dataset are 11 hours and 19 hours. The running time for the training process validates the efficiency of our proposed method.

4 RelatedWork

In this section, we briefly review some related work on link prediction and network embedding.

The problem of link prediction is to estimate the proximity of the link endpoints based on the partially observed links and the node contents in network, which has attracted considerable attention recently [Menon and Elkan, 2011; Wang et al., 2007; Zhu et al., 2016]. The early link prediction approaches are to compute the similarity between each pair of network nodes for determining the proximity, which are based on the number of shared common features [Lin, 1998] and localized neighborhood features [L¨u et al., 2009]. To leverage the correlated link features, several matrix factorization models [Menon and Elkan, 2011; Cao et al., 2014; Agrawal et al., 2013; Leskovec et al., 2010] have been proposed to make prediction from the observed network links. Menon et al. [Menon and Elkan, 2011] employ the supervised matrix factorization method for solving the link prediction problem. Cao et al. [Cao et al., 2014] study the problem of collective prediction of multiple types of links in heterogeneous information networks. Agrawal et al. [Agrawal et al., 2013] propose a matrix factorization based method with trace norm for link sign prediction. Zhao et al. [Zhao et al., 2016b] propose the user preference learning method for predicting the online link between the user and the item. Leskovec et al. [Leskovec et al., 2010] study the link sign prediction problem in online social networks. On the other hand, various probabilistic approaches [Wang et al., 2007;

Miller et al., 2009] have also been developed for learning a link probability distribution model from the observed network. Unlike previous studies, we formulate the problem of link prediction from the viewpoint of path-based proximity ranking metric learning with recurrent neural networks.

Recently, deep learning models show great potential for learning effective representation for network mining applications [Perozzi et al., 2014; Chang et al., 2015], which exploit the network structure for node embedding. Perozzi et al. [Perozzi et al., 2014; Tang et al., ] propose the local network structure embedding method. Chang et al. [Chang et al., 2015] propose the embedding method for heterogeneous networks. Yang et al. [Yang et al., ] develop the learning method for attributed networks. Liu et al. [Liu et al., 2017] propose the proximity embedding for the semantic search on heterogeneous graph. Fang et al. [Fang et al., 2016] develop the metagraph-based learning for semantic proximity graph search. However, the objective of proximity ranking metric learning in our problem is different from these deep learning models. Thus, these methods may not be directly suitable for our problem.

5 Conclusion

In this paper, we consider the problem of link prediction from the viewpoint of learning path-based proximity ranking metric embedding. We propose a novel ranking metric network learning framework by jointly exploiting both nodelevel and path-level attentional proximity of the endpoints to their betweenness paths in order to learn the discriminative joint representation for link prediction. We then develop the path-based dual-level attention learning method with recurrent neural networks for proximity ranking metric embedding. We next incorporate the multi-step reasoning framework for the proposed dual-level attention networks to further improve the performance of link prediction. The extensive experiments on two large-scale datasets show that our method achieves better performance than other state-of-theart solutions to the problem.

Acknowledgements

This work was supported by National Basic Research Program of China (973 Program) under Grant 2013CB336500, and National Natural Science Foundation of China under Grant 61602405, Fundamental Research Funds for the Central Universities 2016QNA5015 and the China Knowledge Centre for Engineering Sciences and Technology. The Project is also Supported by the Key Laboratory of Advanced Information Science and Network Technology of Beijing (XDXX1603). We thank the support from the National Natural Science Foundation of China (No. 61502418) and the research grant for Human-centered Cyber-physical Systems Programme at Advanced Digital Sciences Center from Singapores Agency for Science, Technology and Research (A*STAR).