Back

Topic-sensitive PageRank

Taher H. Haveliwala

article2002TKDE2,170 citations
Stanford UniversityTopic-sensitive PageRank
Haveliwala (2002).pdf
  • Paper: The PageRank Citation Ranking : Bringing Order to the Web, Lawrence M. Page et al. (1999). This seminal paper introduces the original PageRank algorithm and random surfer model on the Web graph, providing the essential foundation that Topic-sensitive PageRank modifies with topic-biased teleportation.
  • Paper: The anatomy of a large-scale hypertextual Web search engine, Sergey Brin et al. (1998). This paper establishes the large-scale architecture of the Google search engine combining link-structure analysis and text retrieval, which contextualizes the practical need for query- and topic-specific link ranking.
  • Paper: TextRank: Bringing Order into Text, Rada Mihalcea et al. (2004). This work adapts random-walk and PageRank-style graph algorithms from Web document link graphs to natural language text for unsupervised keyword and sentence extraction.
  • Paper: LexRank: Graph-based Lexical Centrality as Salience in Text Summarization, Günes Erkan et al. (2004). This paper extends graph-based eigenvector centrality methods, analogous to PageRank, to measure lexical centrality and extract representative sentences for multi-document summarization.
Cover for Topic-sensitive PageRank

Abstract

In 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 the relative “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 to generate 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.

Keywords

Topic-sensitive PageRank

Table of Contents

  • 1. INTRODUCTION
  • Topic-Sensitive PageRank
  • 2. REVIEW OF PAGERANK
  • 3. TOPIC-SENSITIVE PAGERANK
  • 3.1 Outline of Approach
  • 3.2 ODP-biasing
  • 3.3 Query-Time Importance Score
  • 4. EXPERIMENTAL RESULTS
  • 4.1 Similarity Measure for Induced Rankings
  • 4.2 Effect of ODP-Biasing
  • 4.3 Query-Sensitive Scoring
  • 4.4 Context-Sensitive Scoring
  • 5. SOURCES OF SEARCH CONTEXT
  • 6. ONGOING WORK
  • 7. ACKNOWLEDGMENTS
  • 8. REFERENCES
  • APPENDIX
  • A. WEIGHTED SUM OF PAGERANK VECTORS

Knowls

  1. Knowl 1 — Topic-Sensitive PageRank Architecture

    model/method

    Topic-Sensitive PageRank is a link-based web search ranking framework that tailors authority rankings to specific query topics without incurring query-time graph iterations. The framework consists of two phases:

    1. Offline computation: Instead of computing a single global PageRank vector over the web graph, the search engine precomputes a fixed set of kk topic-biased PageRank vectors r⃗j=PR(α,v⃗j)\vec{r}_j = PR(\alpha, \vec{v}_j) for j∈{1,…,k}j \in \{1, \dots, k\}, where each vector is biased toward a representative base topic (such as the top-level categories of the Open Directory Project).
    2. Query-time evaluation: Given a user query qq (and optional query context q′q'), a text classifier estimates the posterior probability distribution P(cj∣q′)P(c_j \mid q') over the basis topics cjc_j. A composite topic-sensitive score sqds_{qd} for each candidate web page dd is then calculated as the weighted sum of the document's scores across the topic vectors: sqd=∑j=1kP(cj∣q′)⋅rankjds_{qd} = \sum_{j=1}^k P(c_j \mid q') \cdot rank_{jd} where rankjd=(r⃗j)drank_{jd} = (\vec{r}_j)_d is the score of page dd in topic vector r⃗j\vec{r}_j. The composite score sqds_{qd} is used to rank search results or integrated into a broader scoring function alongside traditional text-based information retrieval scores.

  2. Knowl 2 — Offline Computation of Topic-Biased PageRank Vectors

    algorithm

    To bias PageRank computations toward specific subjects offline, a set of kk basis topics {c1,…,ck}\{c_1, \dots, c_k\} (such as the 16 top-level categories of the Open Directory Project) is selected. For each topic cjc_j, let TjT_j denote the set of seed URLs belonging to category cjc_j.

    A non-uniform personalization vector v⃗j\vec{v}_j of dimension N×1N \times 1 (where NN is the number of pages in the web crawl) is constructed by distributing uniform probability mass across the URLs in TjT_j: vji={1∣Tj∣if page i∈Tj0if page i∉Tjv_{ji} = \begin{cases} \frac{1}{|T_j|} & \text{if page } i \in T_j \\ 0 & \text{if page } i \notin T_j \end{cases}

    The topic-biased PageRank vector r⃗j=PR(α,v⃗j)\vec{r}_j = PR(\alpha, \vec{v}_j) is then computed by solving the stationary equation: r⃗j=(1−α)Mr⃗j+αv⃗j\vec{r}_j = (1 - \alpha) M \vec{r}_j + \alpha \vec{v}_j where MM is the stochastic web link transition matrix (mij=1/Njm_{ij} = 1/N_j if page jj links to page ii, where NjN_j is the out-degree of page jj) and α∈(0,1)\alpha \in (0, 1) is the damping parameter (typically α=0.25\alpha = 0.25). The vector is solved via power iteration until r⃗j\vec{r}_j converges to within a designated tolerance.

  3. Knowl 3 — Query-Time Topic Classification and Composite Scoring

    algorithm

    At query time, when a user submits a query qq with optional context q′q' (with q′=qq' = q if no extra context is present), candidate documents matching the query terms are ranked according to the following algorithm:

    Input: Query context terms q′=(q1′,q2′,…,qm′)q' = (q'_1, q'_2, \dots, q'_m), precomputed topic-biased PageRank rank vectors r⃗j=PR(α,v⃗j)\vec{r}_j = PR(\alpha, \vec{v}_j) for categories cjc_j (j∈{1,…,k}j \in \{1, \dots, k\}), category term-vectors D⃗j\vec{D}_j, candidate search result set DqD_q
    Output: Composite query-sensitive PageRank scores sqds_{qd} for each d∈Dqd \in D_q
    for each category cjc_j do
        Compute topic posterior using a unigram language model:
        P(cj∣q′)∝P(cj)⋅∏i=1mP(qi′∣cj)P(c_j \mid q') \propto P(c_j) \cdot \prod_{i=1}^m P(q'_i \mid c_j)
        where P(qi′∣cj)=count(qi′∈D⃗j)∑tcount(t∈D⃗j)P(q'_i \mid c_j) = \frac{\text{count}(q'_i \in \vec{D}_j)}{\sum_t \text{count}(t \in \vec{D}_j)} and P(cj)P(c_j) is uniform across classes
    Normalize P(cj∣q′)P(c_j \mid q') such that ∑j=1kP(cj∣q′)=1\sum_{j=1}^k P(c_j \mid q') = 1
    Retain only the top 3 categories with the highest P(cj∣q′)P(c_j \mid q') and renormalize their weights to sum to 1
    for each document d∈Dqd \in D_q do
        sqd←∑jP(cj∣q′)⋅(r⃗j)ds_{qd} \leftarrow \sum_j P(c_j \mid q') \cdot (\vec{r}_j)_d
    return {sqd}d∈Dq\{s_{qd}\}_{d \in D_q}

    The resulting composite score sqds_{qd} represents the stationary probability of visiting page dd in a random walk where a random surfer follows out-links with probability 1−α1 - \alpha and teleports to a random page in topic TjT_j with probability α⋅P(cj∣q′)\alpha \cdot P(c_j \mid q').

  4. Knowl 4 — Linearity of Personalized PageRank Vectors Under Convex Combinations

    theoretical result

    Let PR(α,p⃗)PR(\alpha, \vec{p}) denote the unique PageRank vector for damping factor α∈(0,1)\alpha \in (0, 1), stochastic transition matrix MM, and personalization probability vector p⃗\vec{p} (with ∥p⃗∥1=1\|\vec{p}\|_1 = 1), defined by the linear system: PR(α,p⃗)=(1−α)M⋅PR(α,p⃗)+αp⃗PR(\alpha, \vec{p}) = (1 - \alpha) M \cdot PR(\alpha, \vec{p}) + \alpha \vec{p}

    For any set of kk personalization vectors {v⃗1,…,v⃗k}\{\vec{v}_1, \dots, \vec{v}_k\} with corresponding PageRank vectors r⃗j=PR(α,v⃗j)\vec{r}_j = PR(\alpha, \vec{v}_j), and any non-negative weights wj≥0w_j \ge 0 such that ∑j=1kwj=1\sum_{j=1}^k w_j = 1, the weighted sum of the PageRank vectors satisfies: ∑j=1kwjPR(α,v⃗j)=PR(α,∑j=1kwjv⃗j)\sum_{j=1}^k w_j PR(\alpha, \vec{v}_j) = PR\left(\alpha, \sum_{j=1}^k w_j \vec{v}_j\right)

    This confirms that taking a query-dependent convex combination of precomputed topic-biased PageRank vectors at query time yields the exact PageRank vector that would result from running PageRank from scratch with the composite personalization vector p⃗=∑jwjv⃗j\vec{p} = \sum_j w_j \vec{v}_j.

  5. Knowl 5 — Search Query Disambiguation via Context-Sensitive Scoring

    model/method

    Context-sensitive scoring exploits contextual cues surrounding a query to disambiguate term meanings and route the search to the appropriate topic vectors. Instead of classifying query string qq alone, the broader context q′q' is supplied to the topic classifier P(cj∣q′)P(c_j \mid q'). Sources of search context include:

    1. Surrounding document context: The text of a document or web page from which a user highlights a query term. For example, selecting the term "blues" within a music-related page produces a high classification score for the Arts category (P(Arts∣q′)=0.52P(\text{Arts} \mid q') = 0.52), returning musical artist sites, whereas selecting "blues" within a medical article produces a high score for Health (P(Health∣q′)=0.72P(\text{Health} \mid q') = 0.72), returning clinical depression support resources.
    2. User history and bookmarks: Prior search history (e.g., searching for "Jordan" after "basketball") or personal bookmark/history profiles, which can be encoded into non-uniform prior distributions Pk(cj)P_k(c_j) reflecting specific user interests.
    3. Client-side privacy preservation: To preserve user privacy, full personal browsing history or document text can be processed locally on the client machine to generate the low-dimensional basis weight vector w⃗=(P(c1∣q′),…,P(ck∣q′))\vec{w} = (P(c_1 \mid q'), \dots, P(c_k \mid q')), transmitting only the summary weights to the search server.

  6. Knowl 6 — Rank Similarity Measures: Overlap ($OSim$) and Kendall's Tau Variant ($KSim$)

    definition

    To evaluate the similarity and stability of two top-nn ranked URL lists, τ1\tau_1 and τ2\tau_2, two metrics are used:

    1. Overlap Metric (OSimOSim): Measures the proportion of shared documents in the top nn positions, ignoring their internal order: OSim(τ1,τ2)=∣τ1∩τ2∣nOSim(\tau_1, \tau_2) = \frac{|\tau_1 \cap \tau_2|}{n} where n=20n = 20 is standard.

    2. Kendall's τ\tau Variant (KSimKSim): Measures the agreement between the relative orderings of documents. Let U=τ1∪τ2U = \tau_1 \cup \tau_2. Extensions τ1′\tau'_1 and τ2′\tau'_2 are constructed by appending the missing elements U∖τ1U \setminus \tau_1 to the end of τ1\tau_1 in arbitrary order, and similarly for τ2\tau_2. KSimKSim is the probability that τ1′\tau'_1 and τ2′\tau'_2 agree on the pairwise relative order of distinct elements (u,v)∈U×U(u, v) \in U \times U: KSim(τ1,τ2)=∣{(u,v):τ1′,τ2′ agree on the order of (u,v),u≠v}∣∣U∣(∣U∣−1)KSim(\tau_1, \tau_2) = \frac{\left|\{(u, v) : \tau'_1, \tau'_2 \text{ agree on the order of } (u, v), u \ne v\}\right|}{|U|(|U| - 1)} A score of 1.01.0 represents identical relative ordering, while 0.00.0 represents total disagreement.

  7. Knowl 7 — Empirical Distinctness of Topic Vectors and Insensitivity to Damping Factor

    empirical result

    Experiments conducted on a 120-million-page crawl (containing roughly 280,000 URLs categorized in the 16 Open Directory Project top-level topics) evaluated the properties of topic-biased PageRank vectors across 35 test queries:

    1. Insensitivity to α\alpha: Comparing induced rankings between damping factors α=0.05\alpha = 0.05 and α=0.25\alpha = 0.25 showed high average top-20 overlap (OSim=0.69±0.06OSim = 0.69 \pm 0.06) and rank correlation (KSim=0.58±0.05KSim = 0.58 \pm 0.05). This indicates that search result ordering is robust to the choice of damping factor, leading to the selection of α=0.25\alpha = 0.25.
    2. Topic Vector Orthogonality: Pairwise comparison of top-20 rankings across different topic vectors revealed low overlap. The 5 most similar topic-biased vector pairs exhibited average pairwise OSimOSim scores between 0.170.17 and 0.180.18 and KSimKSim scores between 0.110.11 and 0.130.13:
      • (Games, Sports): OSim=0.18,KSim=0.13OSim = 0.18, KSim = 0.13
      • (NoBias, Regional): OSim=0.18,KSim=0.12OSim = 0.18, KSim = 0.12
      • (Kids & Teens, Society): OSim=0.18,KSim=0.11OSim = 0.18, KSim = 0.11
      • (Health, Home): OSim=0.17,KSim=0.12OSim = 0.17, KSim = 0.12
      • (Health, Kids & Teens): OSim=0.17,KSim=0.11OSim = 0.17, KSim = 0.11

    All other topic pairs yielded pairwise similarity metrics close to 00, demonstrating that individual topic vectors establish genuinely distinct notions of page importance.

  8. Knowl 8 — Precision@10 and User Preference for Topic-Sensitive vs. Unbiased PageRank

    empirical result

    A blind user study was performed with 5 volunteer evaluators examining the top 10 search results for 10 test queries, comparing Topic-Sensitive PageRank scoring (sqds_{qd}) against standard unbiased PageRank (NoBias). A URL was classified as relevant if at least 3 out of 5 volunteers deemed it relevant.

    Could not parse LaTeX table

    Across the 10 queries, Topic-Sensitive PageRank achieved an average Precision@10 of 0.5120.512, compared to 0.2760.276 for unbiased PageRank. In 8 of the 10 queries, a majority of users preferred the result list generated by Topic-Sensitive PageRank; 1 query resulted in a tie (shakespeare), and 1 query favored unbiased PageRank (hiv).

  9. Knowl 9 — Content-Classified Personalization Vectors to Mitigate Directory Manipulation

    model/method

    Constructing personalization vectors v⃗j\vec{v}_j strictly from human-curated Open Directory Project (ODP) category URLs leaves the authority scores vulnerable to subjective or malicious manipulation by volunteer directory editors.

    To eliminate reliance on explicit directory seed lists, a statistical text classifier can be trained on ODP category text and subsequently evaluated over all crawled web pages u∈Webu \in \text{Web}. This yields a soft topic affiliation weight wujw_{uj} for page uu with respect to category cjc_j. The personalization vector v⃗j\vec{v}_j is then defined across all web pages as: vji=wij∑kwkjv_{ji} = \frac{w_{ij}}{\sum_{k} w_{kj}} where wijw_{ij} is the predicted probability that document ii belongs to topic cjc_j. This spreads the teleportation probability mass continuously across all relevant pages on the Web rather than concentrating it solely on directory entries.

Coverage note — The full 16x16 pairwise topic correlation matrix (Table 4) and the individual term classification distributions for all 35 test queries (Table 6) were omitted in favor of summary statistics and representative illustrative query examples, as they provide redundant data points for the same underlying findings.

References

  1. 1.The Google Search Engine: Commercial search engine founded by the originators of PageRank. http://www.google.com/.
  2. 2.The Open Directory Project: Web directory for over 2.5 million URLs. http://www.dmoz.org/.
  3. 3.'More Evil Than Dr. Evil?' http://searchenginewatch.com/sereport/99/11-google.html.
  4. 4.Krishna Bharat and Monika R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. In Proceedings of the ACM-SIGIR, 1998.
  5. 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. 6.Sergey Brin, Rajeev Motwani, Larry Page, and Terry Winograd. What can you do with a web in your pocket. In Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 1998.
  7. 7.Sergey Brin and Larry Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the Seventh International World Wide Web Conference, 1998.
  8. 8.S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, and S. Rajagopalan. Automatic resource compilation by analyzing hyperlink structure and associated text. In Proceedings of the Seventh International World Wide Web Conference, 1998.
  9. 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. 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. 11.Taher H. Haveliwala. Efficient computation of PageRank. Stanford University Technical Report, 1999.
  12. 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. 13.Glen Jeh and Jennifer Widom. Scaling personalized web search. Stanford University Technical Report, 2002.
  14. 14.Jon Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1998.
  15. 15.Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, United Kingdom, 1995.
  16. 16.Larry Page. PageRank: Bringing order to the web. Stanford Digital Libraries Working Paper, 1997.
  17. 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. 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).

Citation

MLA
Haveliwala, T. H. “Topic-sensitive PageRank”. Proceedings of the 11th International Conference on World Wide Web, 2002, pp. 517–26, https://doi.org/10.1145/511446.511513.
APA
Haveliwala, T. H. (2002). Topic-sensitive PageRank. Proceedings of the 11th International Conference on World Wide Web, 517–526. https://doi.org/10.1145/511446.511513
Chicago
Haveliwala, T. H. 2002. “Topic-sensitive PageRank”. Proceedings of the 11th International Conference on World Wide Web, 517–26. https://doi.org/10.1145/511446.511513.
Harvard
Haveliwala, T.H. (2002) “Topic-sensitive PageRank”, Proceedings of the 11th international conference on World Wide Web. ACM, pp. 517–526. Available at: https://doi.org/10.1145/511446.511513.
Vancouver
1. Haveliwala TH (2002) Topic-sensitive PageRank. In: Proceedings of the 11th international conference on World Wide Web. ACM, pp 517–526

BibTeX

@inproceedings{Haveliwala_2002, series={WWW02}, title={Topic-sensitive PageRank}, url={http://dx.doi.org/10.1145/511446.511513}, DOI={10.1145/511446.511513}, booktitle={Proceedings of the 11th international conference on World Wide Web}, publisher={ACM}, author={Haveliwala, Taher H.}, year={2002}, month=May, pages={517–526}, collection={WWW02} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF