The approach of random walk on heterogeneous bibliographic graph has been proven effective in the previous studies. In this study, by using various kinds of positive and negative feedbacks, we propose the novel method to enhance the performance of meta-path-based random walk for scholarly recommendation. We hypothesize that the nodes on the heterogeneous graph should play different roles in terms of different queries or various kinds implicit/explicit feedbacks. Meanwhile, we prove that the node usefulness probability has significant impact for the path importance. When positive and negative feedback information is available, we can calculate each node's proximity to the feedback nodes, and use the proximity to infer the usefulness probability of each node via the sigmoid function. By combining the transition probability and the usefulness probability of nodes on the path instance, we propose the new random walk function to compute the importance of each path instance. Experimental results with ACM full-text corpus show that the proposed method (considering the node usefulness) significantly outperforms the previous approaches.
H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval
The volume of scientific publications has increased dramatically in the past couple of decades, which challenges existing systems and methods to retrieve and access scientific resources. Classical text-based information retrieval algorithms can recommend the candidate publications for scholars. However, most of them ignored the complex and heterogeneous relations among the scholarly objects. Not until recently, some studies proved that adopting the mining approaches on heterogeneous information networks Copyright c 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
Published on CEUR-WS: http://ceur-ws.org/Vol-1393/. could significantly improve the scholarly recommendation performance [3,7,9,12]. For instance, Liu et al., [2,3] constructed the heterogeneous scholarly graph and proposed a novel ranking method based on pseudo relevance feedback (PRF), which can effectively recommend candidate citation papers via different kinds of metapaths on the graph.
In this paper, we intend to further investigate feedback information and enhance the meta-path-based random walk performance. Intuitively, for different information needs, when user feedbacks are available, the nodes on the graph should play different roles in the final measure. For example, given two different queries "Content-based Citation Recommendation" and "Heterogeneous Information Network", the same paper "ClusCite: effective citation recommendation by information network-based clustering" may be retrieved by scholarly search engines, e.g., Google Scholar. But the target paper can be more useful (positive) for the second query than the first one. As another example, for user X, if she prefers to cite influential scholars’ work, the highly cited authors will be useful for her. While for user Y, if she tends to cite the frontiers, she will mark the newest publications and the newly topics as the useful feedback information. Therefore, the same node may perform significantly different based on different information needs and feedback information. Furthermore, by using (implicit/explicit positive/negative) feedbacks, it is possible to infer the usefulness probability of other nodes on the graph. So that, the importance of path instance will vary in terms of the probability of node usefulness.
The main contribution of this paper is threefold. First, in this paper, the feedback is not limited to documents. In scholarly network, user could provide feedback judgments for authors, keywords and venues, either useful or not useful. If the explicit user feedback is unavailable, we propose an approach to automatically generate the feedback nodes based on user queries and the relationships among the entities on the heterogeneous graph. Second, we infer the usefulness of the nodes in terms of feedback information. For instance, a node is less useful when it is close to the negative node(s). We make a conjecture that the usefulness probability of each node depends on its average proximity to the feedback set and can be estimated via sigmoid function. Third, we emphasize the node usefulness has a great impact on the path importance. Our approach about computing the random walk probability differs from the previous study in that, not only the transition probability, but also the usefulness probability of the node should be taken into account for random walk. To verify these hypotheses, we adopt a number of meta-paths on the graph (Figure 1) and make a comparison between the classical random walk function and the novel method. Experimental results on ACM corpus show that the proposed method significantly outperforms the original one.
The remainder of this paper is structured as follows. We 1) review relevant methodologies for pseudo relevance feedback, 2) introduce the preliminaries, 3) propose the improved methods, 4) describe the experiment setting and evaluation results, and 5) conclude with a discussion and outlook.
Pseudo relevance feedback, also known as blind relevance feedback, provides a way for automatic local analysis. When the user judgments or interactions are not available, it turns out to be an effective method to improve the retrieval performance. Traditional pseudo relevance feedback tends to treat the top ranked documents as relevant feedback, and then expand the initial queries. However, some of the top retrieved documents may be irrelevant, which could result in noisy feedback into the process. So that, there are various efforts to improve the traditional pseudo feedback. [11] exploited the possible utility of Wikipedia for query dependent expansion. From the perspective of each query and each set of feedback documents, [4] proposed how to dynamically predict an optimal balance coefficient query expansion rather than using a fixed value. [1] suggested to use evolutionary techniques along with semantic similarity notion for query expansion. [6] introduced an approach to expand the queries for passage retrieval, not based on the top ranked documents, but via a new term weighting function, which gives a score to terms of corpus according to their relatedness to the query, and identify the most relevant ones. Instead of using term expansion, graph-based feedback provides a new ranking assumption based on topology expansion. [2] used the pseudo relevant papers as the seed nodes, and then explored the potential relevant nodes via specific restricted/combined meta-paths on the heterogeneous graph. Our study is motivated by this approach and mainly focused on updating the random walk algorithm by investigating both the positive and negative feedbacks. In fact, positive and negative feedback approach has been studied in image retrieval [5]. With several steps of positive and negative feedback, the retrieval performance could be increasingly enhanced. From the view of negative feedback, [10] studied and compared different kinds of methods, it addressed that negative feedback is important especially when the target topic is difficult and initial results are poor. Besides, using multiple negative feedback methods could be more effective.
Following the work [2,8], an information network can be defined as follows.
DEFINITION 1. (Information network) An information network is defined as a directed graph G = (V; E ) with an object type mapping function : V ! A and a link type mapping function : E ! R, where each object v 2 V belongs to one particular object type (v) 2 A, each link e 2 E belongs to a particular relation (e) 2 R, and if two links belong to the same relation type, the two links share the same starting object type as well as the ending object type.
When there are more than one type of node or link in the information network, it is called heterogeneous information network. In [8], Sun further defined meta-path as follows.
DEFINITION 2. (Meta-path) A meta-path P is a path defined on the graph of network schema TG = (A; R), and is denoted in the form of A_ 1 R!1 A_ 2 R!2 : : : R!l A_ l+1, which defines a composite relation R = R1 R2 : : : Rl between types A_ 1 and A_ l+1, where denotes the composition operator on relations.
Given a specific scholarly network, there can be many kinds of meta-paths. For example, P !w A w P ? is a simple meta-path on the scholarly network, denoting all the papers published by the seed paper’ author. P is the starting paper node (seed node) in this path. P ? denotes the candidate publication node. More examples can be found in Table 1. 4. 4.1
Generally, given user initial queries, a list of ranking publications would be found via text retrieval. Based on the top ranked documents, user would probably give explicit judgments on whether the related keywords, authors or venues are useful or not. However, explicit feedback is not easy to get. In this study, we propose methods to infer the implicit feedback nodes on the heterogeneous graph according to the given information.
The feedback is a collection of multiple nodes marked with useful (positive) or unuseful (negative) on the heterogeneous graph. We represent this collection as N F . N FP and N FN denote the positive and negative nodes set respectively. The kinds of feedback nodes in discussion include keyword (K), author (A) and venue (V). 4.1.1
Since we know the initial queries (i.e., author provided paper keywords) that the users should be most concerned with, it is reasonable to take the explicit keywords KP as the positive feedback nodes. Next, we will infer the positive authors and venues based on KP . We deem that the authors or venues that are highly likely related to KP are positive as well. So we rank authors via meta-paths KP co!n A? and KP r P !w A?, and take the top ranked Kpos authors as the pseudo positive authors AP . Similarly, we locate the positive venues via KP co!n V ? and KP r P !p V ?, and select the top ranked Kpos venues as the positive nodes VP . 4.1.2
Intuitively, to generate the negative feedbacks, our basic assumption is that the negative nodes should be directly related to the searched results, but least relevant to the explicit positive keywords. First, based on text retrieval results, we define the top ranked topK papers as Pr, and then we locate the keywords, authors and venues r that are directly connected to Pr via different meta-paths, Pr ! w p Kr, Pr ! Ar and Pr ! Vr.
Next, we filter collections of Kr, Ar and Vr. 1. Rank the keywords Kr via the transition probability of meta-path KP c!on P !r Kr. Use the last ranked Kneg keywords as the pseudo negative nodes KN . 2. Similar to keywords, rank the authors Ar via the transition probability of meta-path KP c!on P !w Ar, and use the last ranked Kneg authors as the pseudo negative nodes AN . 3. Rank the venues Vr via KP c!on P !p Vr, and use the last ranked Kneg venues as the negative nodes VN . Here we use KP c!on P instead of KP r P because the "contribution" characterizes the importance of each paper, given a topic. It does not necessarily means paper is relevant to topic [2]. Even if one paper is not explicit relevant to some topic, it might also be important. The "contribute" conveys more information.
Thus, we obtain all the positive and negative feedback nodes. N FP includes KP , AP and VP . N FN contains KN , AN and VN . 4.2
Unlike previous studies, in this paper, the importance of nodes on scholarly network is not even. The usefulness probability of node Ni is determined by the feedback nodes. Intuitively, if node Ni is more closely related to the positive nodes, it could be more useful. Conversely, if Ni is much closer to the negative nodes, and further away from the positive nodes, it indicates that Ni may be not very useful. Therefore, the proximity between given node and feedback node set is very crucial. We should note that the usefulness probability of each node varies from different feedback node sets.
To infer the usefulness probability of node Ni, we adopt the sigmoid function Pu(Ni) = 1+e 1D(Ni) to convert the proximity into probability, where controls the convergent rate (default is 1). In our assumption, if Nj is positive node, Pu(Nj ) = 1, otherwise P (Nj ) = 0. D(Ni) denotes the proximity between Ni and the feedback node set N F . It can be derived from the following formula.
D(Ni) = PNk2NjNFNFNd(jNi;Nk) PNj 2NjFNPFPd(jNi;Nj )) , where jN FN j and jN FP j represents the size of collection N FN and N FP respectively. d(Ni; Nj ) indicates the proximity between node Ni and node Nj . In this paper, we will estimate the proximity d(Ni; Nj ) based on the paths Ni Nj on the graph. There could be lots of path instances connected node Ni and Nj . If the length of path is too long, the influence would be too small to be considered. We assume the maximum of path length is 10. Then we select the shortest path and define its length as the proximity d(Ni; Nj ).
If D(Ni) is negative, it reflects node Ni is closer to negative nodes than positive ones, which means node Ni could be less important, and vice versa. Particularly, if D(Nj ) ! +1, it indicates that Nj is far away from negative feedback nodes, so the importance of this node approach to 1; If D(Nj ) = 0, it indicates that Nj has the same distance to negative and positive nodes, then Pu(Nj ) = 0:5 ; If D(Nj ) ! 1, it indicates that Nj is closest to negative feedback node, then Pu(Nj ) ! 0. 4.3
Meta-path illustrates how the nodes are connected in the heterogeneous graph. Once a meta-path is specified, a meta-path-based ranking function is defined, so that relevant papers determined by the ranking function can be recommended [3]. It turns out that meta-path based feedback on heterogeneous graph performs better than other methods (PageRank) based PRF [2]. Random walk on heterogenous network can explore more global information, combining multiple feedback nodes, which might be very important for the recommendation tasks.
In order to quantify the ranking score of candidates relevant to the seeds following one given meta-path, a random walk based approach was proposed in [2]. The relevance between P and P ? can be estimated via s(ai(1); a(jl+1)) = Pt=ai(1) a(l+1) RW (t), j where t is a path instance from node ai(1) to a(jl+1) following the specified meta-path, and RW (t) is the random walk probability of the instance t.
Suppose t = (ai(11); ai(22); : : : ; ai(ll++11)), the random walk probability can be computed via RW (t) = Qj w(ai(jj); ai(;jj++11)). While this formula only considers the weight of link on the path instance. Based on our hypothesis, the node usefulness probability has a great effect on the path importance. So in this study, we propose a novel random walk function as follows.
RW (t) = Qj ( w(ai(jj); ai(;jj++11))+(1 ) Pu(ai(;jj++11))), where Pu(ai(;jj++11)) is the usefulness probability of the node ai(;jj++11) on the path (derived from section 4.2), and determines which factor is more important. Theoretically, we need to tune for each metapath to optimize the weight of each sub-meta-path. For this study, we set = 0:6.
Then, the random walk probability will be decided by the transition probability and the usefulness probability of the node on the path instance. In this paper, we use eight meta-paths to investigate the novel random walk method with node feedback information for citation recommendation. All the meta-paths are listed in Table 1. 5. 5.1
We used 41,370 publications (as candidate citation collection), published between 1951 and 2011, on computer science for the experiment (mainly from the ACM digital library). As [2] introduced, we constructed the heterogeneous graph shown in Figure 1 and Table 2.
For the evaluation part, we used a test collection with 274 papers. The selected papers have more than 15 citations from the candidate citation collection. 5.2
Attaining different types of feedback information is the most important part in this research. Since it is not available to get the user judgments right away. We used the method introduced in section 4.1 to create positive and negative feedback nodes. As aforementioned, the collection KP is the set of user given keywords. It is explicit positive feedbacks. While AP and VP can be derived by their connectivity to set KP based on the heterogeneous graph. Here we set Kpos = 10, and take the top 10 ranked authors/ venues as the implicit positive feedbacks.
Next, we produced the implicit negative feedback nodes. Through the text retrieved results, we grabbed the top ranked papers as Pr (topK = 20). Then we located the list of keywords/ authors/ venues which have direct correlations to Pr, but the least relevance to KP . Find the last ranked Kneg = 10 and used them as KN , AN and VN respectively. 5.3
In the evaluation part, we experimented with 8 different metapaths. For each meta-path, two sets of results were shown on row ‘N’ and ‘Y’ in Table 3. The ‘N/Y’ column in Table 3 indicates whether we use the positive and negative feedback nodes or not for computing the path importance. ‘N’ indicates that the result was from the baseline in [2], while ‘Y’ means multiple feedback nodes were employed and the node influence was appended into the final random walk function. MAP and NDCG are used as the ranking function training and evaluation metrics. For MAP, binary judgment is provided for each candidate cited paper (cited or not cited). NDCG estimates the cumulative relevance gain a user receives by examining recommendation results up to a given rank on the list. We used an importance score, 0-4, as the candidate cited paper importance to calculate NDCG scores. Apparently, in most cases, row ‘Y’ significantly outperforms row ‘N’ , which shows that the positive/negative feedbacks enhance the random walk performance quite well. We also used t-test to verify this improvement and most meta-paths are significantly refined.
In this study we use multiple kinds of feedback nodes and propose a new method to enhance the meta-path-based random walk performance. The new random walk function considers both transition probability and node usefulness probability on the path instance. We find that the node influence varies from the set of feedback nodes, which could be inferred based on the explicit user queries via a series of steps. Experimental results with ACM data illustrate that the new approach with positive/negative feedback information helps to improve the performance of meta-path-based recommendation.
For further study, we will continue this approach based on real user explicit feedbacks and design the personalized recommendation model to improve user experience. Not only the node usefulness is related to the feedback nodes, but also the weight of each relation type may be affected by the feedback nodes or retrieval task. If the retrieval task is to search the relevant papers based on given authors, the author feedback nodes will be more useful for "writtenby" relation, "writtenby" and "co-author" relation might be more important. This hypothesis will be discussed in the next step. Besides, more sophisticated inference models will be adopted which may enhance the ranking performance.
Node/Edge P A V K P !c P P !w A
p P ! V A !co A P !r K K con P
! K con A
! K con V ! NO. 1 2 3 4 5 6 7 8
Relevant paper’s author’s other papers can be relevant Relevant paper’s cited papers can be relevant Relevant paper’s cited paper’s cited paper can be relevant Relevant paper’s cited papers’ authors’ papers can be relevant Relevant paper’s author’s co-author’s papers can be relevant Relevant paper’s author’s cited papers can be relevant Paper can be relevant if it is cited by the ones published at the same venue as the relevant paper P p ! V p P w! A w P ? Paper can be relevant if its authors’ papers are published at the same venue as the relevant paper 8. REFERENCES [1] P. Bhatnagar and N. Pareek. Improving pseudo relevance feedback based query expansion using genetic fuzzy approach and semantic similarity notion. Journal of Information Science, page 0165551514533771, 2014. [2] X. Liu, Y. Yu, C. Guo, and Y. Sun. Meta-path-based ranking with pseudo relevance feedback on heterogeneous graph for citation (VLDB’11), Seattle, WA, 2011. [9] Y. Sun, B. Norick, J. Han, X. Yan, P. S. Yu, and X. Yu. Integrating meta-path selection with user-guided object clustering in heterogeneous information networks. In Proc. of 2012 ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD’12), Beijing, China, 2012. [10] X. Wang, H. Fang, and C. Zhai. A study of methods for negative relevance feedback. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, pages 219–226. ACM, 2008. [11] Y. Xu, G. J. Jones, and B. Wang. Query dependent pseudo-relevance feedback based on wikipedia. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pages 59–66. ACM, 2009. [12] X. Yu, X. Ren, Y. Sun, B. Sturt, U. Khandelwal, Q. Gu, B. Norick, and J. Han. Recommendation in heterogeneous information networks with implicit user feedback. In Proc. of 2013 ACM Int. Conf. Series on Recommendation Systems (RecSys’13), pages 347–350, Hong Kong, 2013.