Topic-Sensitive PageRank
Taher H. Haveliwala∗

Stanford University
Computer Science Department
Stanford, CA 94305

taherh@cs.stanford.edu(650) 723-9273

ABSTRACTIn the original PageRank algorithm for improving the ranking of search-query results, a single PageRank vector is computed, using the link structure of the Web, to capture therelative “importance” of Web pages, independent of any particular search query. To yield more accurate search results,
we propose computing a set of PageRank vectors, biased using a set of representative topics, to capture more accurately
the notion of importance with respect to a particular topic.
By using these (precomputed) biased PageRank vectors togenerate query-specific importance scores for pages at query
time, we show that we can generate more accurate rankings
than with a single, generic PageRank vector. For ordinary keyword search queries, we compute the topic-sensitive
PageRank scores for pages satisfying the query using the
topic of the query keywords. For searches done in context(e.g., when the search query is performed by highlighting
words in a Web page), we compute the topic-sensitive PageRank scores using the topic of the context in which the query
appeared.

Categories and Subject Descriptors
H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval—search process, information filtering, retrieval models; H.3.1 [Information Storage andRetrieval]: Content Analysis and Indexing—linguistic processing

General Terms
Algorithms, Experimentation

Keywords
search, Web graph, link structure, PageRank, search in context, personalized search

1.

INTRODUCTION

Various link-based ranking strategies have been developed
recently for improving Web-search query results. The HITS
∗Supported by NSF Grant IIS-0085896 and an NSF Graduate Research Fellowship.
Copyright is held by the author/owner(s).
WWW2002, May 7–11, 2002, Honolulu, Hawaii, USA.
ACM 1-58113-449-5/02/0005.

algorithm proposed in [14] relies on query-time processing
to deduce the hubs and authorities that exist in a subgraphof the Web consisting of both the results to a query and the
local neighborhood of these results. [4] augments the HITS
algorithm with content analysis to improve precision for thetask of retrieving documents related to a query topic (as opposed to retrieving documents that exactly satisfy the user’s
information need). [8] makes use of HITS for automaticallycompiling resource lists for general topics.
The PageRank algorithm discussed in [7, 16] precomputes
a rank vector that provides a-priori “importance” estimates
for all of the pages on the Web. This vector is computed
once, offline, and is independent of the search query. At
query time, these importance scores are used in conjunction with query-specific IR scores to rank the query results.
PageRank has a clear efficiency advantage over the HITS
algorithm, as the query-time cost of incorporating the precomputed PageRank importance score for a page is low. Furthermore, as PageRank is generated using the entire Webgraph, rather than a small subset, it is less susceptible tolocalized link spam.
In this paper, we propose an approach that (as with HITS)
allows the query to influence the link-based score, yet (aswith PageRank) requires minimal query-time processing. In
our model, we compute offline a set of PageRank vectors,
each biased with a different topic, to create for each pagea set of importance scores with respect to particular topics. The idea of biasing the PageRank computation was
suggested in [6] for the purpose of personalization, but wasnever fully explored. This biasing process involves introducing artificial links into the Web graph during the offline rankcomputation, and is described further in Section 2.
By making PageRank topic-sensitive, we avoid the problem of heavily linked pages getting highly ranked for queries
for which they have no particular authority [3]. Pages considered important in some subject domains may not be considered important in others, regardless of what keywords
may appear either in the page or in anchor text referringto the page [5]. An approach termed Hilltop, with motivations similar to ours, is suggested in [5] that is designed
to improve results for popular queries. Hilltop generates
a query-specific authority score by detecting and indexing
pages that appear to be good experts for certain keywords,
based on their outlinks. However, query terms for which
experts were not found will not be handled by the Hilltop
algorithm.
[17] proposes using the set of Web pages that contain some

term as a bias set for influencing the PageRank computation, with the goal of returning terms for which a given page
has a high reputation. An approach for enhancing searchrankings by generating a PageRank vector for each possible
query term was recently proposed in [18] with favorable results. However, the approach requires considerable processing time and storage, and is not easily extended to makeuse of user and query context. Our approach to biasing the
PageRank computation is novel in its use of a small numberof representative basis topics, taken from the Open Directory, in conjunction with a unigram language model used toclassify the query and query context.
In our work we consider two scenarios. In the first, we assume a user with a specific information need issues a queryto our search engine in the conventional way, by entering
a query into a search box. In this scenario, we determine
the topics most closely associated with the query, and use
the appropriate topic-sensitive PageRank vectors for ranking the documents satisfying the query. This ensures thatthe “importance” scores reflect a preference for the link
structure of pages that have some bearing on the query.
As with ordinary PageRank, the topic-sensitive PageRankscore can be used as part of a scoring function that takes
into account other IR-based scores. In the second scenario,
we assume the user is viewing a document (for instance,browsing the Web or reading email), and selects a termfrom the document for which he would like more information. This notion of search in context is discussed in [10].
For instance, if a query for “architecture” is performed byhighlighting a term in a document discussing famous building architects, we would like the result to be different than if
the query “architecture” is performed by highlighting a termin a document on CPU design. By selecting the appropriate
topic-sensitive PageRank vectors based on the context of thequery, we hope to provide more accurate search results. Notethat even when a query is issued in the conventional way,without highlighting a term, the history of queries issued
constitutes a form of query context. Yet another source ofcontext comes from the user who submitted the query. For
instance, the user’s bookmarks and browsing history could
be used in selecting the appropriate topic-sensitive rank vectors. These various sources of search context are discussed
in Section 5.
A summary of our approach follows. During the offline
processing of the Web crawl, we generate 16 topic-sensitive
PageRank vectors, each biased (as described in Section 2)
using URLs from a top-level category from the Open Directory Project (ODP) [2]. At query time, we calculate thesimilarity of the query (and if available, the query or user
context) to each of these topics. Then instead of using asingle global ranking vector, we take the linear combinationof the topic-sensitive vectors, weighted using the similarities of the query (and any available context) to the topics.
By using a set of rank vectors, we are able to determine
more accurately which pages are truly the most importantwith respect to a particular query or query-context. Because
the link-based computations are performed offline, during
the preprocessing stage, the query-time costs are not muchgreater than that of the ordinary PageRank algorithm.

2.

REVIEW OF PAGERANK

A review of the PageRank algorithm ([16, 7, 11]) follows. The basic idea of PageRank is that if page u has alink to page v, then the author of u is implicitly conferringsome importance to page v. Intuitively, Yahoo! is an important page, reflected by the fact that many pages point
to it. Likewise, pages prominently pointed to from Yahoo!
are themselves probably important. How much importancedoes a page u confer to its outlinks? Let Nu be the outdegree of page u, and let Rank(p) represent the importance(i.e., PageRank) of page p. Then the link (u, v) confers
Rank(u)/Nu units of rank to v. This simple idea leads tothe following fixpoint computation that yields the rank vec~ ∗ over all of the pages on the Web. If N is the
tor Rank
number of pages, assign all pages the initial value 1/N . Let
Bv represent the set of pages pointing to v. In each iteration,
propagate the ranks as follows:1∀v Ranki+1 (v) =Ranki (u)/Nu

(1)

u∈Bv

~ stabilizes to within
We continue the iterations until Rank
~ ∗ contains the Pagesome threshold. The final vector Rank
Rank vector over the Web. This vector is computed only
once after each crawl of the Web; the values can then be
used to influence the ranking of search results [1].
The process can also be expressed as the following eigenvector calculation, providing useful insight into PageRank.
Let M be the square, stochastic matrix corresponding to thedirected graph G of the Web, assuming all nodes in G haveat least one outgoing edge. If there is a link from page j topage i, then let the matrix entry mij have the value 1/Nj .
Let all other entries have the value 0. One iteration of theprevious fixpoint computation corresponds to the matrix~
vector multiplication M × Rank.
Repeatedly multiplying~ by M yields the dominant eigenvector Rank
~ ∗ of theRank~ ∗ is the solution tomatrix M . In other words, Rank
~ = M × Rank
~
Rank

(2)

Because M corresponds to the stochastic transition matrix
over the graph G, PageRank can be viewed as the stationary probability distribution over pages induced by a random
walk on the Web.
One caveat is that the convergence of PageRank is guaranteed only if M is irreducible (i.e., G is strongly connected)
and aperiodic [15]. The latter is guaranteed in practice for
the Web, while the former is true if we add a damping factor
1 − α to the rank propagation. We can define a new maα
trix M 0 in which we add transition edges of probability N
between every pair of nodes in G:
1
]N ×N
(3)
N
This modification improves the quality of PageRank by introducing a decay factor 1 − α which limits the effect ofrank sinks [6], in addition to guaranteeing convergence to aunique rank vector. Substituting M 0 for M in Equation 2,
we can express PageRank as the solution to:2
M 0 = (1 − α)M + α[

~ = M 0 × Rank~
Rank
~ + α~= (1 − α)M × Rank
p

(4)
(5)

with p~ = [ N1 ]N ×1 . The key to creating topic-sensitive Page-

Rank is that we can bias the computation to increase the12Note that for u ∈ Bv , the edge (u, v) guarantees Nu ≥ 1.
~
Equation 5 makes use of the fact that ||Rank||
1 = 1.

effect of certain categories of pages by using a nonuniform
N × 1 personalization vector for p~ ([6]).3 Note that the biasing involves introducing additional rank to the appropriate
nodes in each iteration of the computation. It is not simply
a postprocessing step performed on the standard PageRank
vector.
In terms of the random-walk model, the personalization
vector represents the addition of a complete set of transition edges where the probability on an artificial edge (u, v)~ ∗ of Equais given by αpv . We will refer to the solution Rank
tion 5, with α = α∗ and a particular p~ = p~∗ , as P~R(α∗ , p~∗ ).
By appropriately selecting p~, the rank vector can be madeto prefer certain categories of pages. The bias factor α specifies the degree to which the computation is biased towards
p
~.

3.

TOPIC-SENSITIVE PAGERANK

3.1 Outline of Approach
In our approach to topic-sensitive PageRank, we precompute the importance scores offline, as with ordinary PageRank. However, we compute multiple importance scores foreach page; we compute a set of scores of the importance ofa page with respect to various topics. At query time, theseimportance scores are combined based on the topics of thequery to form a composite PageRank score for those pages
matching the query. This score can be used in conjunction
with other IR-based scoring schemes to produce a final rank
for the result pages with respect to the query. As the scoring functions of commercial search engines are not known,
in our work we do not consider the effect of these other IRscores.4 We believe that the improvements to PageRank’s
precision will translate into improvements in overall searchrankings, even after other IR-based scores are factored in.5

3.2 ODP-biasing
The first step in our approach is to generate a set of biased
PageRank vectors using a set of “basis” topics. This stepis performed once, offline, during the preprocessing of the
Web crawl. For the personalization vector p~ described in
Section 2, we use the URLs present in the various categories
in the ODP. We create 16 different biased PageRank vectors
by using the URLs present below each of the 16 top-level
categories of the ODP as the personalization vectors. In
particular, let Tj be the set of URLs in the ODP category
cj . Then when computing the PageRank vector for topic cj ,in place of the uniform damping vector p~ = [ N1 ]N ×1 , we use
the nonuniform vector p~ = v~j where
vji =

1
|Tj |

i ∈ Tj ,0

i 6∈ Tj .

(6)

3
A minor caveat: to ensure that M 0 is irreducible when p~contains any 0 entries, nodes not reachable from nonzero
nodes in p
~ should be removed. In practice this is not problematic.
4
For instance, most search engines use term weighting
schemes which make special use of HTML tags.
5
Note that the topic-sensitive PageRank score itself implicitly makes use of IR in determining the topic of the query.
However this use of IR is not vulnerable to manipulation ofpages by adversarial webmasters seeking to raise the scoreof their sites.

The PageRank vector for topic cj will be referred to as
P~R(α, v~j ). We also generate the single unbiased PageRank
vector (denoted as NoBias) for the purpose of comparison.
The choice of α will be discussed in Section 4.1.
~j consisting
We also compute the 16 class term-vectors Dof the terms in the documents below each of the 16 top-level
categories. Djt simply gives the total number of occurrencesof term t in documents listed below class cj of the ODP.
One could envision using other sources for creating topicsensitive PageRank vectors; however, the ODP data is freely
available, and as it is compiled by thousands of volunteer
editors, is less susceptible to influence by any one party.6

3.3 Query-Time Importance Score
The second step in our approach is performed at query
time. Given a query q, let q 0 be the context of q. In otherwords, if the query was issued by highlighting the term q
in some Web page u, then q 0 consists of the terms in u.
For ordinary queries not done in context, let q 0 = q. Using a unigram language model, with parameters set to theirmaximum-likelihood estimates, we compute the class probabilities for each of the 16 top-level ODP classes, conditioned
on q 0 . Let qi0 be the ith term in the query (or query context) q 0 . Then given the query q, we compute for each cj
the following:
P (cj |q 0 ) =P (cj ) · P (q 0 |cj )∝ P (cj ) ·P (q 0 )P (qi0 |cj )


(7)

i

~j .
P (qi0 |cj ) is easily computed from the class term-vector D
The quantity P (cj ) is not as straightforward. We chose to
make it uniform, although we could personalize the query
results for different users by varying this distribution. In
other words, for some user k, we can use a prior distribution Pk (cj ) that reflects the interests of user k. This method
provides an alternative framework for user-based personalization, rather than directly varying the damping vector p~
as had been suggested in [7, 6].
Using a text index, we retrieve URLs for all documents
containing the original query terms q. Finally, we compute the query-sensitive importance score of each of these
retrieved URLs as follows. Let rankjd be the rank of document d given by the rank vector P~R(α, v~j ) (i.e., the rank
vector for topic cj ). For the Web document d, we computethe query-sensitive importance score sqd as follows.
P (cj |q 0 ) · rankjd

sqd =

(8)

j

The results are ranked according to this composite score
sqd .7
The above query-sensitive PageRank computation has thefollowing probabilistic interpretation, in terms of the “random surfer” model [7]. Let wj be the coefficient used toweight the jth rank vector, with j wj = 1 (e.g., let wj =P (cj |q)). Then note that the equality
[wj P~R(α, v~j )] = P~R α,[wj v~j ]



j
6



(9)

j

See Section 6 for an approach we are exploring which reduces the ability for even malicious ODP editors to affectscores in any non-negligible way.
7
Alternatively, sqd can be used as part of a more generalscoring function.

holds, as shown in Appendix A. Thus we see that the following random walk on the Web yields the topic-sensitivescore sqd . With probability 1 − α, a random surfer on pageu follows an outlink of u (where the particular outlink ischosen uniformly at random). With probability αP (cj |q 0 ),the surfer instead jumps to one of the pages in Tj (where theparticular page in Tj is chosen uniformly at random). Thelong term visit probability that the surfer is at page v is exactly given by the composite score sqd defined above. Thus,
topics exert influence over the final score in proportion totheir affinity with the query (or query context).

4.

EXPERIMENTAL RESULTS

To measure the behavior of topic-sensitive PageRank, we
conducted a series of experiments. In Section 4.1 we describe
the similarity measure we use to compare two rankings. In
Section 4.2, we investigate how the induced rankings vary,
based on both the topic used to bias the rank vectors as wellas the choice of the bias factor α. In Section 4.3, we present
results of a user study showing the retrieval performanceof ordinary PageRank versus topic-sensitive PageRank. Finally, in Section 4.4, we provide an initial look at how theuse of query context can be used in conjunction with topicsensitive PageRank.
As a source of Web data, we used the latest Web crawl
from the Stanford WebBase [12], performed in January 2001,
containing roughly 120 million pages. Our crawl containedroughly 280,000 of the 3 million URLs in the ODP. For
our experiments, we used 35 of the sample queries given
in [9], which were in turn compiled from earlier papers.8
The queries are listed in Table 1.
Table 1: Queries usedaffirmative action
alcoholism
amusement parks
architecture
bicyclingblues
cheesecitrus grovesclassical guitar
computer vision
cruisesdeath valley
field hockey
gardeninggraphic design
gulf warhiv
java

liparilyme disease
mutual funds
national parks
parallel architecture
recycling cansrock climbing
san francisco
shakespeare
stamp collecting
sushitable tennis
telecommuting
vintage cars
volcanozen buddhism
zener

4.1 Similarity Measure for Induced Rankings
We use two measures when comparing rankings. The firstmeasure, denoted OSim(τ1 , τ2 ), indicates the degree of overlap between the top n URLs of two rankings, τ1 and τ2 . We
define the overlap of two sets A and B (each of size n) tobe |A∩B|. In our comparisons we will use n = 20. Thenoverlap measure OSim gives an incomplete picture of the8

Several queries which produced very few hits on our repository were excluded.

similarity of two rankings, as it does not indicate the degree
to which the relative orderings of the top n URLs of two
rankings are in agreement. Therefore, we also use a variantof the Kendall’s τ distance measure. See [9] for a discussionof various distance measures for ranked lists in the context
of Web search results. For consistency with OSim, we will
present our definition as a similarity (as opposed to distance)measure, so that values closer to 1 indicate closer agreement.
Consider two partially ordered lists of URLs, τ1 and τ2 , eachof length n. Let U be the union of the URLs in τ1 and τ2 .
If δ1 is U − τ1 , then let τ10 be the extension of τ1 , where τ10contains δ1 appearing after all the URLs in τ1 .9 We extend
τ2 analogously to yield τ20 . We define our similarity measure
KSim as follows:|(u, v) : τ10 , τ20 agree on order of (u, v), u 6= v||U ||U − 1|(10)
In other words, KSim(τ1 , τ2 ) is the probability that τ10and τ20 agree on the relative ordering of a randomly selected
pair of distinct nodes (u, v) ∈ U × U .
KSim(τ1 , τ2 ) =4.2 Effect of ODP-Biasing
In this section we measure the effects of topically biasing
the PageRank computation. Firstly, note that the choice ofthe bias factor α, discussed in Section 2, affects the degree
to which the resultant vector is biased towards the topic
vector used for p~. Consider the extreme cases. For α = 1,
the URLs in the bias set Tj will be assigned the score |T1 | ,and all other URLs receive the score 0. Conversely, as αtends to 0, the content of Tj becomes irrelevant to the finalscore assignment.
We chose to use α = 0.25 heuristically, after inspecting
the rankings for several of the queries listed in Table 1. We
did not concentrate on optimizing α, as we discovered thatthe induced rankings of query results are not very sensitive
to the choice of α. For instance, for α = 0.05 and α = 0.25,
we measured the average similarity of the induced rankings
across our set of test queries, for each of our PageRank vectors.10 The results are given in Table 2. We see that the
average overlap between the top 20 results for the two valuesof α is very high. Furthermore, the high values for KSim
indicate high overlap as well agreement (on average) on therelative ordering of these top 20 URLs for the two values of
α. All subsequent experiments use α = 0.25.
The differences across different topically-biased PageRank
vectors is much higher, dwarfing any variations caused by
the choice of α. We computed the average, across our test
queries, of the pairwise similarity between the rankings induced by the different topically-biased vectors. The 5 mostsimilar pairs, according to our OSim measure, are given in
Table 3, showing that even the most similar topically-biased
rankings have little overlap. Table 4 shows that the pairwise
similarities of the rankings induced by the other ranking vectors are close to 0. Having established that the topicallybiased PageRank vectors each rank the results substantiallydifferently, we proceed to investigate which of these rankings
is “best” for specific queries.
As an example, Table 5 shows the top 5 ranked URLs
9
The URLs within δ1 are not ordered with respect to one
another.
10
We used 25 iterations of PageRank in all cases.





Arts

Business

Computers

Games

Health

Home

Kids & Teens

News

Recreation

Reference

Regional

Science

Shopping

SocietySportsWorld

NoBiasArts
Business
Computers
Games
Health
Home
Kids & Teens
News
Recreation
Reference
Regional
Science
Shopping
SocietySportsWorld )NoBiasTable 4: Pairwise comparison of topically-biased rankings (

1
0.09
0.08
0.10
0.07
0.07
0.07
0.08
0.07
0.09
0.07
0.12
0.11
0.05
0.10
0.07
0.10

1
0.06
0.08
0.12
0.07
0.07
0.08
0.09
0.09
0.07
0.09
0.08
0.07
0.10
0.09
0.06

1
0.08
0.08
0.08
0.07
0.04
0.07
0.06
0.05
0.07
0.08
0.07
0.06
0.07
0.06

1
0.11
0.06
0.06
0.06
0.07
0.08
0.08
0.06
0.07
0.06
0.06
0.07
0.07

1
0.09
0.09
0.09
0.11
0.09
0.08
0.06
0.09
0.09
0.07
0.13
0.07

1
0.12
0.11
0.09
0.06
0.09
0.08
0.11
0.06
0.10
0.09
0.06

1
0.09
0.07
0.08
0.06
0.08
0.06
0.07
0.09
0.10
0.05

1
0.09
0.08
0.10
0.08
0.09
0.05
0.11
0.08
0.06

1
0.06
0.06
0.07
0.08
0.05
0.09
0.10
0.06

1
0.05
0.10
0.06
0.08
0.08
0.10
0.07

1
0.07
0.10
0.04
0.09
0.07
0.06

1
0.08
0.06
0.11
0.09
0.08

1
0.04
0.10
0.07
0.07

1
0.05
0.09
0.05

1
0.07
0.07

1
0.06

1

Table 2:Average= 0 05 0 25

similarity

Bias Set
NoBiasArts
Business
Computers
Games
Health
Home
Kids & Teens
News
Recreation
Reference
Regional
Science
Shopping
SocietySports
World

OSim
0.72
0.66
0.63
0.70
0.78
0.73
0.77
0.74
0.74
0.62
0.68
0.60
0.69
0.66
0.57
0.69
0.64

of

rankings

for

KSim
0.64
0.58
0.54
0.60
0.67
0.62
0.67
0.66
0.65
0.55
0.57
0.52
0.59
0.55
0.50
0.60
0.55

Table 3: Topic pairs yielding most similar rankings
Bias-Topic Pair
(Games, Sports)(NoBias, Regional)(Kids & Teens, Society)(Health, Home)(Health, Kids & Teens)

OSim
0.18
0.18
0.18
0.17
0.17

KSim
0.13
0.12
0.11
0.12
0.11

In this section we look at how effectively we can utilize
the ranking precision gained by the use of multiple PageRank vectors. Given a query, our first task is to determine

which of the rank vectors can best rank the results for thequery. We found that using the quantity P (cj |q) as discussed in Section 3.3 yielded intuitive results for determining which topics are most closely associated with a query.
In particular, for most of the test queries, the ODP categories with the highest values for P (cj |q) are intuitively themost relevant categories for the query. In Table 6, we list
for each test query, the 3 categories with the highest values for P (cj |q). When computing the composite sqd scorein our experiments, we chose to use the weighted sum of
only the rank vectors associated with the three topics withthe highest values for P (cj |q), rather than all of the topics.
Based on the data in Table 6, we saw no need to include thescores from the topic vectors with lower associated values
for P (cj |q).
To compare our query-sensitive approach to ordinary PageRank, we conducted a user study. We randomly selected 10
queries from our test set for the study, and found 5 volunteers. For each query, the volunteer was shown 2 result
rankings; one consisted of the top 10 results satisfying thequery, when these results were ranked with the unbiased
PageRank vector, and the other consisted of the top 10 results for the query when the results were ranked with thecomposite sqd score.12 The volunteer was asked to selectall URLs which were “relevant” to the query, in their opinion. Furthermore, they were asked to say which of the two

11

12

for the query “bicycling,” using each of the topically-biased
PageRank vectors. Note in particular that the ranking induced by the Sports-biased vector is of high quality.11 Also
note that the ranking induced by the Shopping-biased vector leads to the high ranking of websites selling bicyclerelated accessories.

4.3 Query-Sensitive Scoring

Of course this is a subjective statement; a user study ispresented in Section 4.3.

Both the title and URL were presented to the user. The
title was a hyperlink to a current version of the Web page.

Table 5: Query “bicycling”
NoBias

Arts“RailRiders Adventure Clothing”
www.RailRiders.com“Photo Contest & Gallery (Bicycling)”
www.bikescape.com/photogallery/

www.Waypoint.org/default.html
www.Gorp.com/
www.FloridaCycling.com/
HiddenTrails.com/index.htm

www.trygve.com/
www.greenway.org/
www.jsc.nasa.gov/Bios/htmlbios/young.html
www.BellaOnline.com/sports/

Business

Computers“Recumbent Bikes and Kit Aircraft”
www.rans.com“GPS Pilot”
www.gpspilot.com

www.BreakawayBooks.com
java.oreilly.com/bite-size/www.carbboom.com
www.CorporateTeamBuilding.com

www.wireless.gr/wireless-links.htm
www.linkstosales.com
www.LiftExperts.com/lifts.html
www.trygve.com/index.html

Games

Health“Definition Through Hobbies”
www.flick.com/˜gretchen/hobbies.html“Personal Fitness Trainer...”www.nfpt.com/guestbook.html

www.BellaOnline.com/sports/
www.npr.org/programs/wesun/puzzle/will.html
www.trygve.com/
www.IdeaFinder.com/showcase/forsale.htm

www.usrf.org/news/bikeriding.html
obgyn.uihc.uiowa.edu/Patinfo/Adhealth/UTI.HTM
www.nmh.org/
www.ChainreactionBicycles.com/saddles.htm

Home

Kids and Teens“25 Ways to Stay On Track”
www.exercare.com/exerinfo/motivation.htm“Camp Shohola For Boys”
www.shohola.com

www.floras-hideout.com/party/index.html
www.BicycleSource.com/contact.shtml
www.bicycleSource.com/tour.shtml
www.aoa.dhhs.gov/elderpage.html

www.EarthForce.org
www.WeissmanTours.com
www.GrownupCamps.com/homepage.html
www.EarthForce.org/welcome.htm

News

Recreation“Minnesotans for an Energy-Efficient Economy”
www.me3.org/projects/sprawl/“Adventure travel”
www.gorp.com/

www.SmithfieldTimes.com/TimesEditorl.htm
www.DaveSloan.com/about/www.TheAtlantic.com/issues/2000/11/russo.htm
www.SierraClub.org/ico/www.GrownupCamps.com/homepage.html
www.gorp.com/gorp/activity/main.htm
www.outdoor-pursuits.org/
www.NicholsExpeditions.com/

Reference

Regional“WPI Clubs & Organizations”
www.wpi.edu/Admin/SAO/guide.html“Your Guide to Outdoor Activities”
www.gorp.com/gorp/activity/main.htm

www.NoyesFamily.com/school/manciano.html
www.ThePotters.com/puzzles.html
www.Vanderbilt.edu/AnS/Germanic-Slavic/german/
www.engin.umich.edu/prog/macro/univA2.html

www.gorp.com/
www.destateparks.com/index.htm
www.tpwd.state.tx.us/park/parks.htm
www.gorp.com/gorp/activity/biking.htm

Science

Shopping“Coast to Coast by Recumbent Bicycle”
hypertextbook.com/bent/“Cycling Clothing & Accessories for Women”
www.TeamEstrogen.com/

www.SiestaSoftware.com/
www.BenWiens.com/benwiens.html
www.SusanJeffers.com/jeffbio.htm
www.EarthForce.org/welcomeA.htm

www.ShopOutdoors.com/
www.jub.com.au/books/
www.bike.com/
www.softride.com/

SocietySports“Word Search Puzzles”
www.ThePotters.com/puzzles.html“Swim, Bike, Run, & Multisport”
www.multisports.com/

www.LakeTravisbb.com/
www.vnorthland.com/hotel/barkpoint/barkpoint.htm
www.gorp.com/default.htm
www.tlcnetwork.org/

www.BikeRacing.com/
www.CycleCanada.com/
www.bikescape.com/photogallery/www.cambiecycles.com/

World“Disease Word Index”
www.pathinfo.com/lhodzpds.htm
www.ExploringEcuador.com/espindex.htm
www.camembert-france.com/bike00.html
www.AdventureRace.com/JungleMan.htm
www.dejava.com/yogya/transits.htm

Table 7: Ranking preferred by majority of users
Queryalcoholism
bicycling
citrus groves
computer vision
death valleygraphic design
gulf war
hiv
shakespeare
table tennis

Preferred by Majority
TopicSensitive
TopicSensitive
TopicSensitive
TopicSensitive
TopicSensitive
TopicSensitive
TopicSensitive
NoBiasNeither
TopicSensitive

rankings was “better” overall, in their opinion. They were
not told anything about how either of the rankings was generated. The rankings induced by the topic-sensitive PageRank score sqd were significantly preferred by our test group.
Let a URL be considered relevant if at least 3 of the 5 volunteers selected it as relevant for the query. The precision
then is the fraction of the top 10 URLs that are deemed relevant. The precision of the two ranking techniques for eachtest query is shown in Figure 1. The average precision for
the rankings induced by the topic-sensitive PageRank scores
is substantially higher than that of the unbiased PageRankscores. Furthermore, as shown in Table 7, for nearly all
queries, a majority of the users preferred the rankings induced by the topic-sensitive PageRank scores. These results
suggest that the effectiveness of a query-result scoring function can be improved by the use of a topic-sensitive PageRank scheme in place of a generic PageRank scheme.
1
NoBias
TopicSensitive

0.9
0.8

Precision

0.7

TopicSensitive Mean
(0.512)

0.6
0.5

NoBias Mean
(0.276)

0.4
0.3
0.2
0.1

hi
v
sh
ak
es
pe
ar
e
ta
bl
e
te
nn
is

gu
lf
w
ar

gr
ov
es
co
m
pu
te
rv
isi
on
de
at
h
va
lle
y
gr
ap
hi
c
de
sig
n

bi
cy
cli
ng

cit
ru
s

al
co
ho
lis
m

0

Query

Figure 1: Precision @ 10 results for our test queries.
The average precision over the ten queries is also
shown.

4.4 Context-Sensitive Scoring
In Section 4.3, the topic-sensitive ranking vectors werechosen using the topics most strongly associated with thequery term. If the search is done in context, for instance byhighlighting a term in a Web page and invoking a search,then the context can be used instead of the query to determine the topics. Using the context can help disambiguate
the query term and yield results that more closely reflect

the intent of the user. We now illustrate with an example how using query-context can help a system which uses
topic-sensitive PageRank.
Consider the query “blues” taken from our test set. This
term has several different senses; for instance it could referto a musical genre, or to a form of depression. Two Web
pages in which the term is used with these different senses,
as well as short textual excerpts from the pages, are shownin Table 8. Consider the case where a user reading oneof these two pages highlights the term “blues” to submit
a search query. At query time, the first step of our system is to determine which topic best applies to the queryin context. Thus, we calculate P (cj |q 0 ) as described in Section 3.3, using for q 0 the terms of the entire page, rather thanjust the term “blues.” For the first page (discussing music),argmaxcj P (cj |q 0 ) is Arts, and for the second page (discussing depression), argmaxcj P (cj |q 0 ) is Health. The next
step is to use a text index to fetch a list of URLs for all documents containing the term “blues” — the highlighted term
for which the query was issued. Finally, the URLs are ranked
using the appropriate ranking vector that was selected using
the P (cj |q 0 ) values (i.e., either Arts or Health). Table 9shows the top 5 URLs for the query “blues” using the topicsensitive PageRank vectors for Arts, Health, and NoBias.
We see that as desired, most of the results ranked using theArts-biased vector are pages discussing music, while all of
the top results ranked using the Health-biased vector discuss depression. The context of the query allows the system
to pick the appropriate topic-sensitive ranking vector, andyields search results reflecting the appropriate sense of thesearch term.

5. SOURCES OF SEARCH CONTEXTIn the previous section, we discussed one possible sourceof context to utilize in the generation of the composite PageRank score, namely the document containing the query term
highlighted by the user. There are a variety of other sourcesof context that may be used in our scheme. For instance,
the history of queries issued leading up to the current queryis another form of query context. A search for “basketball”
followed up with a search for “Jordan” presents an opportunity for disambiguating the latter. As another example,
most modern search engines incorporate some sort of hierarchical directory, listing URLs for a small subset of the Web,
as part of their search interface.13 The current node in thehierarchy that the user is browsing at constitutes a sourceof query context. When browsing URLs at Top/Arts, forinstance, any queries issued could have search results (fromthe entire Web index) ranked with the Arts rank vector,
rather than either restricting results to URLs listed in thatparticular category, or not making use of the category whatsoever. In addition to these types of context associated with
the query itself, we can also potentially utilize query independent user context. Sources of user context include theusers’ browsing patterns, bookmarks, and email archives. As
mentioned in Section 3.3, we can integrate user context byselecting a nonuniform prior, Pk (cj ), based on how closely
the user’s context accords with each of the basis topics.
When attempting to utilize the aforementioned sources ofsearch context, mediating the personalization of PageRank
13

See for instance http://directory.google.com/Top/Arts/or http://dir.yahoo.com/Arts/.

Table 6: Estimates for P (cj |q)affirmative action
News
Society
Reference

HealthKids & Teens
Arts

0.52
0.13
0.07

Arts
Shopping
News

0.75
0.21
0.01

Computers
Business
Reference

0.89
0.03
0.03

Home
Shopping
Regional

0.40
0.19
0.14

Computers
Games
Kids & Teens

0.77
0.05
0.05

Regional
Recreation
Kids & Teens

0.54
0.13
0.07

SportsRegional
Recreation

0.56
0.13
0.07

Sports
Shopping
Regional

0.36
0.18
0.13

Society
Kids & TeensWorld

bicyclingclassical guitar

0.63
0.14
0.04

Computers
Business
Shopping

0.53
0.10
0.06

Home
Kids & Teens
News

0.42
0.16
0.09

Computers
Science
Reference

0.27
0.16
0.10

Arts
Reference
Kids & Teens

0.53
0.14
0.09

Business
Kids & Teens
Society

0.88
0.09
0.01

Kids & Teens
News
Business

Computers
Reference
Business

0.72
0.10
0.05

Shopping
Home
Regional

0.65
0.18
0.04

Regional
Society
News

0.36
0.23
0.09

Society
Kids & Teens
Regional

0.19
0.17
0.13

HealthRegional
Recreation

0.28
0.14
0.10

gulf war

lipari

0.21
0.18
0.17

lyme disease

parallel architecture

0.96
0.01
0.01

recycling cans

0.70
0.10
0.07

Home
Business
Kids & Teens

0.34
0.21
0.15

Shopping
Recreation
Science

0.70
0.04
0.03

Shopping
RecreationHome

shakespeare

0.42
0.38
0.06

stamp collecting

telecommuting

0.44
0.39
0.02

vintage cars

zener
0.17
0.13
0.11

Table 8: Two different search contexts for the query “blues”
That Blues Music Page

0.34
0.21
0.18

death valleygraphic design

zen buddhism

0.26
0.19
0.09

citrus groves

cruises

table tennis

volcanoScience
Regional
Recreation

Recreation
Regional
Sportssan francisco

sushi
Home
Kids & Teens
Shopping

0.24
0.14
0.09

architecture

0.51
0.23
0.08

cheesenational parks

rock climbing
Recreation
Regional
SportsHome
Recreation
Shopping

java

mutual funds
Business
Regional
Home

0.52
0.12
0.08

gardeninghiv
HealthNews
Kids & Teens

Regional
Recreation
Kids & Teens

computer vision

field hockey
Sports
Shopping
Reference

amusement parks
0.47
0.20
0.06

blues

SportsRegional
HealthArts
Shopping
News

alcoholism

0.41
0.22
0.17

Postpartum Depression & the ‘Baby Blues’

http://www.fred.net/turtle/blues.shtml

http://familydoctor.org/handouts/379.html. . . If you’re stuck for new material, visit Dan Bowden’sBlues and Jazz Transcriptions - lots of older blues guitartranscriptions for you historic blues fans . . .

. . . If you’re a new mother and have any of these symptoms, you have what is called the “baby blues.” “Theblues” are considered a normal part of early motherhoodand usually go away within 10 days after delivery. However, some women have worse symptoms or symptoms last
longer. This is called “postpartum depression.” . . .

0.67
0.23
0.02

Table 9: Results for query “blues”
Arts

HealthBritannica Online
www.britannica.com
BandHunt.com Genres (Music)www.bandhunt.com/genres.html
Artist Information (Music)www.artistinformation.com/index.html
Billboard.com (Music charts)
www.billboard.com
Soul Patrol (Music)www.soul-patrol.com

Northern County Psychiatric Associates News
www.baltimorepsych.com/news.htm
Seasonal Affective Disorderwww.ncpamd.com/seasonal.htm
Women’s Mental Healthwww.ncpamd.com/Women’s Mental Health.htm
Wing of Madness Depression Support Groupwww.wingofmadness.com
Country Nurse Online
www.countrynurse.com
NoBiasTUCOWS Themes
news.tucows.com/themes/pastart.html
World’s Most Popular MP3 Service
www.emusic.com
Books, Music, DVD, and VHS Essentials
www.johnholleman.com/amastatement.html
The Official Site of Major League Baseballwww.majorleaguebaseball.com
MP3.com: Free MP3 Downloads
www.mp3.com

via a set of basis topics yields several benefits over attempting to explicitly choose a personalization vector directly.
Flexibility: For any kind of context, we can compute the context-sensitive PageRank score by using aclassifier to compute the similarity of the context withthe basis topics and then weighting the topic-sensitive
PageRank vectors appropriately. We can treat suchdiverse sources of search context such as email, bookmarks, browsing history, and query history uniformly.
Transparency: The topically-biased rank vectors haveintuitive interpretations. If we see that our system isgiving undue preference to certain topics, we can tune
the classifier used on the search context, or adjust topic
weights manually. When utilizing user context, theusers themselves can be shown what topics the systembelieves represent their interests.
Privacy: Certain forms of search context raise potential privacy concerns. Clearly it is inappropriate
to send the user’s browsing history or other personal
information to the search-engine server for use in constructing a profile. However a client-side program could
use the user context to generate the user profile locally,and send only the summary information, consisting of
the weights assigned to the basis topics, over to theserver. The amount of privacy lost in knowing onlythat the user’s browsing pattern suggests that he isinterested in Computers with weight 0.5 is much lessthan actually obtaining his browser’s history cache.
When making use of query-context, if the user is browsing sensitive personal documents, they would be more
comfortable if the search client sent to the server topic
weights rather than the actual document text surrounding the highlighted query term.

A wide variety search-context sources exist which, if utilized appropriately, can help users better manage the delugeof information they are faced with. Although we have begun
exploring how best to make use of available context, muchwork remains in identifying and utilizing search context withthe goal of personalizing Web search.

6. ONGOING WORK
We are currently exploring several ways of improving ourapproach for topic-sensitive PageRank. As discussed in theprevious section, discovering sources of search context is aripe area of research. Another area of investigation is thedevelopment of the best set of basis topics. For instanceit may be worthwhile to use a finer-grained set of topics,
perhaps using the second or third level of the Open Directoryhierarchy, rather than simply the top level. However, a finegrained set of topics leads to efficiency considerations, as thecost of the naive approach to computing these topic-sensitive
vectors is linear in the number of basis topics. See [13] forapproaches that may make the use of a larger, finer grained
set of basis topics practical.
We are also currently investigating a different approachto creating the damping vector p~ used to create the topicsensitive rank vectors. This approach has the potential ofbeing more resistant to adversarial ODP editors. Currently,
as described in Section 3.2, we set the damping vector p~
for topic cj to v~j , where v~j is defined in Equation 6. In
the modified approach, we instead first train a classifier forthe basis set of topics using the ODP data as our training
set, and then assign to all pages on the Web a distributionof topic weights.14 Let this topic weight of a page u for
category cj be wuj . Then we replace Equation 6 with∀i∈W eb [vji =Efficiency: For a small number of basis topics (suchas the 16 ODP categories), both the query-time cost
and the offline preprocessing cost of our approach islow, and practical to implement with current Web indexing infrastructure.

wij
]
k wkj

(11)

In this way, we hope to ensure that the PageRank vectors
generated are not overly sensitive to particular choices made14

For instance, the estimated class probabilities for the basis
topics.

by individual ODP editors.
We plan to investigate the above enhancements to generating the topic-sensitive PageRank score, and evaluate theireffect on retrieval performance, both in isolation and whencombined with typical IR scoring functions.

7.

ACKNOWLEDGMENTS

I would like to thank Professor Jeff Ullman for invaluablecomments and feedback. I would like to thank Glen Jeh andProfessor Jennifer Widom for several useful discussions. I
would also like to thank Aristides Gionis for his feedback.
Finally, I would like to thank the anonymous reviewers fortheir insightful comments.

8.

REFERENCES[1] The Google Search Engine: Commercial search engine
founded by the originators of PageRank.
http://www.google.com/.
[2] The Open Directory Project: Web directory for over
2.5 million URLs.
http://www.dmoz.org/.
[3] ‘More Evil Than Dr. Evil?’
http://searchenginewatch.com/sereport/99/11google.html.
[4] Krishna Bharat and Monika R. Henzinger. Improved
algorithms for topic distillation in a hyperlinked
environment. In Proceedings of the ACM-SIGIR, 1998.
[5] Krishna Bharat and George A. Mihaila. When experts
agree: Using non-affiliated experts to rank popular
topics. In Proceedings of the Tenth International
World Wide Web Conference, 2001.
[6] Sergey Brin, Rajeev Motwani, Larry Page, and Terry
Winograd. What can you do with a web in yourpocket. In Bulletin of the IEEE Computer Society
Technical Committee on Data Engineering, 1998.
[7] Sergey Brin and Larry Page. The anatomy of alarge-scale hypertextual web search engine. In
Proceedings of the Seventh International World Wide
Web Conference, 1998.
[8] S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg,
P. Raghavan, and S. Rajagopalan. Automatic resourcecompilation by analyzing hyperlink structure andassociated text. In Proceedings of the SeventhInternational World Wide Web Conference, 1998.
[9] Cynthia Dwork, Ravi Kumar, Moni Naor, and
D. Sivakumar. Rank aggregation methods for the web.
In Proceedings of the Tenth International World Wide
Web Conference, 2001.
[10] Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias,
Ehud Rivlin, Zach Solan, Gadi Wolfman, and Eytan
Ruppin. Placing search in context: the concept
revisited. In Proceedings of the Tenth International
World Wide Web Conference, 2001.
[11] Taher H. Haveliwala. Efficient computation ofPageRank. Stanford University Technical Report, 1999.
[12] J. Hirai, S. Raghavan, H. Garcia-Molina, and
A. Paepcke. Webbase: A repository of web pages. In
Proceedings of the Ninth International World Wide
Web Conference, 2000.
[13] Glen Jeh and Jennifer Widom. Scaling personalized
web search. Stanford University Technical Report,
2002.

[14] Jon Kleinberg. Authoritative sources in a hyperlinked
environment. In Proceedings of the ACM-SIAM
Symposium on Discrete Algorithms, 1998.
[15] Rajeev Motwani and Prabhakar Raghavan.
Randomized Algorithms. Cambridge University Press,
United Kingdom, 1995.
[16] Larry Page. PageRank: Bringing order to the web.
Stanford Digital Libraries Working Paper, 1997.
[17] Davood Rafiei and Alberto O. Mendelzon. What is
this page known for? Computing web page
reputations. In Proceedings of the Ninth International
World Wide Web Conference, 2000.
[18] Matthew Richardson and Pedro Domingos. The
Intelligent Surfer: Probabilistic Combination of Link
and Content Information in PageRank, volume 14.
MIT Press, Cambridge, MA, 2002 (To appear).

APPENDIX
A. WEIGHTED SUM OF PAGERANKVECTORSIn this section we derive the interpretation of the weighted
sum of PageRank vectors.15 Consider a set of rank vectors {P~R(α, v~j )} for some fixed α.16 For brevity let r~j =P~R(α, v~j ). Furthermore let r~0 = j [wj r~j ], and v~0 = j [wj v~j ].
We claim that r~0 = P~R(α, v~0 ). In other words, r~0 is itself a
PageRank vector, where the personalization vector p~ is setto v~0 . The proof follows.
Because each r~j satisfies Equation 5 (with p~ = v~j ), we
have that


r~0 ≡



[wj r~j ](12)[wj ((1 − α)M r~j + αv~j )](13)[(1 − α)wj M r~j ] +[αwj v~j ](14)[wj v~j ]

(15)

j

=
j

=
j

j

[wj r~j ] + α= (1 − α)Mj= (1 − α)M r~0 + αv~0

j

(16)

Thus r~0 satisfies Equation 5 for the personalization vectorp~ = v~0 , and our proof is complete.

15

The proof that follows is based on discussions with Glen
Jeh (see [13]).
16
See the end of Section 2 for the description of our notation.