Efficient Calculation of Personalized Document Rankings

1 Introduction

Recently several approaches for combining social networks and document reference networks have been proposed [Hess et al., 2006], [Stein and Hess, 2006], [Garc´ıa-Barriocanal and Sicilia, 2005], [Korfiatis and Naeve, 2005]. They integrate information on social relationships into classical referencebased measures such as PageRank [Page et al., 1998] or HITS [Kleinberg, 1999]. Trust networks gained much attention because trust relationships constitute a strong basis for personalized recommendations as shown by trust-based recommender systems such as [Golbeck, 2006], [Massa and Avesani, 2004], [Avesani et al., 2005]. We call such measures operating on two-layer networks trust-enhanced visibility measures. 1

1 Other approaches like TrustRank [Gy¨ongyi et al., 2004] directly attach reliability information to a subset of documents to improve recommendations, which does not correspond to the notion of social trust (derived from a trust network) and does not allow for personalization.

They are motivated by the fact that a document can be highly visible although its content is completely untrustworthy. Examples are cases of scientific misconduct in which publications considered as valid or even as landmark papers such as the Science papers by the South-Corean stem cell researcher Hwang 2 are declared as faked. Reference-based measures still assign them a high visibility because citations are rarely removed and, as e.g. [Budd et al., 1998] showed, faked papers continue to be cited even after official retraction. In this case, more accurate rankings can be provided by looking at other users' recommendations: as it is a fake, it will no longer be recommended by anyone knowing this. Less extreme, though more frequent is that opinions on the same document differ greatly between users, for example, when a user has a very extreme, or a very progressive opinion. So this user might consider a document as very interesting, whereas most users deem it as untrustworthy. Here, it is crucial whose recommendations are taken into account: considering document reviews depending on the user's trust in the reviewer highly personalizes recommendations. However, as it is reasonable to assume that only a small fraction of documents is reviewed, we integrate trust-weighted reviews into referencebased measures that calculate recommendations for all documents. We therefore have a two-layer architecture with a document reference network and a reader trust network being connected by reviews.

Current recommender systems do not yet integrate this information although parts are already available on the web. A user's bookmarks made available via applications such as del.iciou.us 3 are e.g. simple reviews of webpages. The number of trust networks on the web increases, too. Well-known applications are Epinions or communities such as Orkut. Many users provide FOAF (Friend-of-a-Friend) files (see e. g. [Dumbill, 2002]) with their profile and relationships. An extension of the FOAF vocabulary encodes trust information 4 .

This paper analyzes how information from trust and document networks can be integrated into algorithms for personalized recommendations. Based on a general framework for such trust-enhanced visibility measures, we develop concrete functions. To consider up-to-date trust information and reviews, these functions have to be efficiently computable at query time, i. e., in the moment a user searches a document repository. As it is the reference-based measure that is typically very costly, we explore how to use precalculated visibilities. The efficiency of the measures introduced is analyzed with respect to recommendations for a single document and rankings of a set of documents. In the scope of a simulation study, the results obtained by the different functions are compared. The rest of the paper is hence structured as follows: Section 2 discusses the general framework. In section 3, we develop different trust-review-enhanced visibility measures. Section 4 presents the simulation study in which the functions are evaluated and section 5 gives the conclusion.

2 E.g. news@nature.com: http://www.nature.com/news/2005/ 051219/full/051219-3.html, (accessed June 28, 2006).

3 http://del.icio.us/

4 See the ontology for trust ratings at http://trust.mindswap.org/ ont/trust.owl (accessed June 29, 2006)

2 Framework for a Trust-Enhanced Visibility

2.1 Trust and Document Reference Networks

The two-layer architecture encompasses a document reference network and a trust network as shown in figure 1. Documents such as webpages or scientific papers refer to other documents via hyperlinks or citations. Based on the reference structure, a visibility can be calculated for each document, i.e., its importance or rank. The best-known ranking algorithm is PageRank that has originally been incorporated in Google. It computes the visibility visd of a document pd by using the weighted sum of the visibilities visk of the papers pk citing pd (based on the idea that a paper cited from many important papers must be somehow important) 5 :

where Bd is the set of pages citing pd and Ck is the set of pages cited by pk. 6 Originally N is the number of documents in the network, in general it is simply a linear scaling factor. An important feature of this function is that the visibility of any document pd depends on the visibilities of documents pj ∈ Bd citing it. Therefore, changing the visibility of one document influences the visibility of other documents. Other approaches, e. g. HITS, which determines a hub and an authority value for webpages, are based on such a recursive definition, too. The framework presented works with any reference structure-based visibility measure.

The trust network is established between reviewers, i.e., readers or editors who express their opinion on documents. Reviewers assign a trust value to other reviewers, giving directed and weighted edges in the trust network. High trust means that the evaluating user appreciates the evaluated user's reviews, e. g., because he or she applies similar criteria in the review. Trust between indirectly connected users, i.e., the "friends of our friends", can be inferred by trust propagation: if user um has not directly evaluated un, the trust value tum→un for un is derived by aggregating the trust values on the path from um to un. Examples for trust metrics include [Golbeck et al., 2003] and [Avesani et al., 2005]. 7 Reviews connect trust and document networks.

5 The basic idea of this algorithm was used before by [Pinski and Narin, 1976] to compute the importance of scientific journals.

6 For n pages this gives a linear system of n equations. Solving this equation system is possible but (for large n) very expensive, so an iterative approach is used. First all visi are set to some default value and then the new values r′ i are calculated repeatingly until all visi converge (for a discussion of convergence problems in leaves see [Page et al., 1998]).

2.2 Personalizing Recommendations

The two-layer architecture permits calculating a recommendation for a document (page) pd from the perspective of a person (user) um. For the recommendation, a citation-based measure on the document reference network is enhanced with information from the trust network. As this measure considers in addition the reviews made by the users in the trust network, it is called a trust-review-enhanced visibility, in the following: tre-visibility (vis tre pd ).

By interpolation on the trust network, the reviews of other users can be taken into account. So we are able to calculate recommendations for documents that are not reviewed by the requesting user her/himself. The information from the trust network tells us to which degree a review should influence the recommendation vis tre pd : the reviews made by users who user um considers as trustworthy should have most impact. So all reviews are personalized by the user's view on the trust network. By interpolating on the document reference network, recommendations cannot only be calculated for documents that have been reviewed but for all documents. As the visibility of a document depends on the visibilities of the documents citing it, reviews have an indirect impact on adjacent documents: in the example from Fig. 1, reviews r3 and r4 will influence the visibility of p1 if u1 considers the reviewers u3

7 As we aim to personalize recommendations, we use one of these trust metrics providing trust values from the user's perspective. Other trust metrics calculate global values, e. g., with metrics in the style of PageRank.

and u4 as trustworthy. While the trust tu1→u4 of u1 in u4 is directly given, tu1→u3 is interpolated by some trust metric (see Sec. 2.1) by tu1→u2 ◦ tu2→u3 . The reviews r2 and r1 exert an indirect influence on vis tre p1 through the ciations from p2 and p5 to p1.

2.3 The Trust-Enhanced Visibility

We now design the tre-visibility-framework using the structure of the document network and the trust-weighted reviews as the basis for personalizing document visibilities. In the first step by interpolation on the trust network, the trust of a user um to all others reachable from her or him is computed. Non-reachable users are given a default trust tdefault (setting tdefault = 0 implies that the corresponding reviews have no impact). This interpolation can be done efficiently for all users in parallel. For all reviews r j of a user un, we consider um's trust tum→un in un to be the trust in all reviews by un. Now um's trust in every review is known. In the second step, personalized tre-visibilities of all documents are computed by incorporating the reviews and weighting them by the trust um has in them. Here we can choose between two different approaches:

1. compute a document base visibility vis◦pj of all documents pj using some visibility function like PageRank and then derive the personalized tre-visibility vis tre pj from the user-independent document base visibility vis◦pj by including trustworthy reviews, or
2. use a modified visibility function that incorporates the reviews on each document directly when computing vis tre pj .

The first approach has the advantage to be simple and to be able to precompute 8 vis◦pj for all documents as vis◦pj is userindependent, but the integration of indirect reviews is not straightforward. The second approach automatically handles indirect reviews because the tre-visibilities are used for propagation, but here everything has to be computed on the fly, because no user-independent part exists. To be able to precompute most of the values is important for providing personalized recommendations in search engines to queries such as "should I buy this pay-per-view?" and for sorting query results in a personalized ranking. 9 Anything that has to be computed at query time increases the load of the document repository server and demands the user to wait.

Regardless of the approach used, a tre-visibility function should satisfy the following properties:

1. A review's impact on a document recommendation depends on the degree of trust that the requesting user has in the reviewer. Reviews provided by users who are fully

8 as Google does to rank millions of webpages

9 As users normally only read the documents provided on the first page of the result listing this ranking is fairly important.

• trusted should have a considerable impact on the recommendation, whereas reviews by users deemed as untrustworthy should have minimal impact.
• If no review by a trustworthy person is available, the recommendation will consist of the visibility calculated on the document network. Although this mere visibility measure is not personalized, it is appropriate: having no review by a trustworthy user does not permit inferring that the document is not worth reading.
• The degree of influence that reviews have compared with the pure structure-based visibility should be adjustable.
• Trust-weighted reviews of a document pj exert an indirect influence on the visibilities of the papers referenced in pj, because pj's visibility is modified by the reviews, and so it propagates a modified visibility to the documents that it cites.

The reference-based visibility measure has to be chosen depending on the type of document network: cyclic networks such as the Web normally require different measures as typically acyclic publication networks.

3 TRE-Visibilities

In this section we introduce several functions to compute the trust-review-enhanced document visibility. We use the following definitions: for a document pd, Rpd is the set of direct reviews on pd, and vis◦pd is the (precalculated) document base visibility. The distance ki,d of a direct review ri ∈ Rpj to pd is the length 10 of the shortest path from pj to pd (if no path exists, ki,d :=∞).

All trust values are in [0,1]. Reviews are non-negative and in the same range as the visibilities computed by the chosen structure-based visibility function. 11

3.1 Simple TRE-Visibility

The simplest approach to compute the tre-visibility of pd is to combine the reviews ri ∈ Rpd of pd , weighted with the respective trust ti in ri, and vis◦pd . To indicate the impact of vis◦pd , it is weighted by its visibility contribution vc which is globally set by the user, e. g., vc := 0.5. So the document base visibility can be treated as additional reviewwith r0 :=vis◦pd and t0 :=vc. This gives the simple tre-visibility:

10 i. e. the number of edges

11 This can be achieved by scaling either the reviews or the visibilities, e. g., by choosing an appropriate N in the PageRank.

3.2 Integrated TRE-Visibility

The tres-visibility algorithm is appealing in its simplicity but neglects indirect reviews. As in structure-based visibility algorithms like PageRank or HITS the visibility of a document depends on the visibilities of the documents citing it, an indirect effect of reviews on adjacent documents can be achieved by simply swapping the computation sequence: instead of first computing the document visibility and then adding the reviews, the reviews are directly incorporated in the visibility function, e. g. with PageRank 12 :

As the visibility vis trei pd of a document pd now depends on the visibilities vis trei pk of the documents pk ∈ Bd citing it, the reviews on the documents pk have an impact on vis trei pd ; in other words: the trust-review-enhanced visibilities are propagated through the document network.

The drawback of this approach is that the visibilities of all documents are now user-dependent: the visibility vis′pd of a document pd can no longer be precomputed offline because it is influenced by the trust-weighted reviews of the documents citing it, and on those of the documents citing these and so on. 13 Precomputing personalized rankings for all users would only be possible for a very small set of users (a small trust network), while computing the complete ranking on the fly at query time is only possible for small document sets. So we need some more efficient visibility algorithm.

3.3 Path-based TRE-Visibility

We therefore have to develop a function that uses precalculated visibilities vis◦pd for all documents pd like the tresvisibility function (Sec. 3.1) but that additionally takes into account indirect reviews like the integrated trei-visibility (Sec. 3.2).

12 Obviously this can be done in a similar way for other visibility functions.

13 This also holds for other recursive approaches for integrating a second, user-dependent source of information in a recursive visibility function, see e. g. the twr-visibility function of [Hess et al., 2006].

The trei-visibility vis trei p58 of document p58 shown in Fig. 2 is computed by the reviews on p58 and the visibilities vis trei p42 and vis t rei p30 of p42 and p30, which depend on the reviews on p42 and p30 and so on. The visibility vis trei p42 of p42 contributes by 1 3 and vis t rei p30 by 1 2 to vis◦p58 , because p42 has 3 and p30 2 outgoing citations and (according to PageRank) the visibility of a document is distributed over all outgoing citations. The reviews on p42 thus contribute by 1 3 to p58, as they are part of vis trei p42 . This

also works for larger distances: a review ri on p11 contributes to p42 by 1 3 and therefore along the path [ p11 1 3→ p42 1 3→ p58 ] 1 1 2→ p58 ] by 1

by 1 9 , and along the path [ p11 3→ p30 6 . The total contribution of a review ri on p11 to the visibility of p42 is therefore 1 9 + 1 6 = 5 18 .

In general: the contribution c π j of a review ri of a document pj along a path π = [ pj → q1 → q2 → . . . → qm → pd ] is c π j = 1 |Cp j | + 1 |Cq1 | + 1 |Cq2 | +. . .+ 1 |Cqm | .

By restricting the review influence to some maximum distance kmax, all indirect reviews and their contributions can be precomputed offline for all documents. 14 So we get

with ci being the contribution of review ri to pd. If ri is a direct review on pd, ci = 1. If ri is a review of a document pj, ci is the sum of the contributions of ri along all paths [ p j → . . . → pd ] with path length less or equal to kmax.

3.4 Distance-based TRE-Visibility

We can simplify the tre-visibility calculation by determining the contribution of a review ri solely by its distance ki,d to pd, following the idea that a review should have a larger impact if it is closer to the paper. 15 With β for finetuning the impact of indirect reviews, we get:

14 This can be done very efficiently by simply propagating all reviews of a document pi to all documents pa ∈Ci cited by it, annotated with the outdegree |Ci| and repeated for kmax steps.

15 This is implicitly also true for the trep-visibility if each document in a path cites more than one other document, and the average number of documents cited is larger than the number of paths.

3.5 Efficient Computation

Discussing the runtime of the functions described above, we have to distinguish the overall costs and costs at query time. While offline computation of large document repositories is costly, it is feasible as e. g. Google shows. Critical is the time needed to answer a single search query. As mentioned before it is impossible to compute the visibilities of all documents of a large document repository at query time. On the other hand, it is also impossible to precompute personalized rankings of all documents for all users, as this would even offline be to costly. Thus trei is at least not appropriate for personalized search engines.

We could reduce computation costs by restricting the visibility computation to the subset of documents we are interested in (e. g. the set of documents matching the search term). Unfortunately, this is not possible for trei because the treivisibility of the documents in the subset depends on the treivisibility of the documents they are cited by and so on. 16

Here the other tre-visibility functions come into play: the data on both subnets can be precomputed, and only the join has to be done on the fly. The trust of any user in any other user can be precomputed offline, which automatically gives the trust in each review. Re-computation is required if trust edges change or new users join (but not, if new reviews are given!). The base visibility vis◦p j of each document p j can also be precomputed. The simple tre-visibility tres of the subset of documents the user is interested in can now be computed in a single run through these documents. For using trep or tred, each document additionally has to know its indirect reviews, and these sets of reviews can also be precomputed by simply propagating all reviews through the document network while computing the base document visibility. New reviews are propagated through the document network at the time they are created. So at query time all to be done is the join: for all documents pj in the selected subset, all direct and indirect reviews and the document base visibility vis◦p j are summed up, weighted by their corresponding trust values in order to compute vis tre p j . And finally the documents are sorted to provide a personalized ranking.

4 Simulation

It is obvious that the functions presented take direct (and indirect) reviews weighted by their trust values into account and compute personalized tre-visibilities. The interesting question is how much the presented functions differ and which impact they give to indirect reviews.

We compare the different tre-visibility functions by computing tre-visibilities from the perspective of a test user u on 10 document reference networks, each with ≈ 12000 documents (with 2 to 7 references) and 1000 reviews randomly distributed. The test user's trust in each reviewwas uniformly distributed in [0, 1]. The document base visibilities were computed by PageRank with α = 0.85 and N = 100. Now the trevisibilities of all documents were computed using tres, trei, trep and tred (with vc = 0.5, kmax = 3, β = 3). By comparing the visibilities (vis A pd , vis B pd ) of a node pd as computed by two visibility algorithms A and B we can see how big the differences between A and B are. If A and B would compute the same function, the difference would be 0. Table 1 gives the average difference of the visibilities computed by algorithm A and B, respectively, over all documents: Δdirect is the average difference of documents with at least one direct review, Δindirect the same for documents without direct review and Δtotal the overall difference. 17

16 This does not fully hold for HITS, where the computation is in fact done on a subset.

The first four lines of Tab. 1 show the differences to PageRank. Obviously, direct reviews have high impact on all trevisibility functions, but also the effect of indirect reviews is considerable (with the exception of tres, certainly). In the next three lines Δdirect is most interesting, which shows to which amount the visibility of directly reviewed documents is changed by additional indirect reviews (which are not considered by tres but by the other functions). The next two lines show (Δindirect) that tred and trep differ from trei (we did not expect them to totally resemble trei), but much less than from PageRank. And finally the last line shows, that trep and tred are very close so that for the given networks the average number of 4.5 outgoing citations per document (affecting trep) is well resembled by setting β = 3 (pretests with β = 2 gave large differences). This also shows that the parameters of the functions used have to be adjusted for each network size and structure to give appropriate results.

5 Conclusion

In this paper, we introduced different trust-enhanced visibility function integrating document visibilities, user-dependent trust information and reviews for personalized document recommendations. We attached importance to design functions that calculate personalized rankings efficiently at query time.

17 We did this separately for all 10 networks, but the differences between them were so small (standard deviation s < 1%), that we only show the average over all networks.

Therefore, we analyzed how to use pre-calculated information on both networks that is joint on the fly. The simulation study compared the functions, and we can conclude that the path-based and the distance-based tre-visibility permit computing personalized recommendations of the same quality as the costly recursive tre-visibility while being efficiently computable, and thus appropriate for search engines. On the basis of these results, we now aim to develop a personalized recommender system integrating our efficient trust-enhanced visibility computation.

Acknowledgments

This work was partially supported by the German Academic Exchange Service (DAAD) and the German Science Foundation (DFG).