PageRank without hyperlinks: Reranking with PubMed related article networks for biomedical text retrieval

Jimmy Lin

Abstract

This paper explores the application of graph-based ranking algorithms, specifically PageRank and HITS, to biomedical text retrieval. By leveraging PubMed's "related article" feature to construct a synthetic link network based on content similarity, the author demonstrates significant improvements in search relevance. Evaluation on the TREC 2005 Genomics track shows that interpolating standard retrieval scores with PageRank values can boost Mean Average Precision (MAP) by up to 7.8%.

Introduction

In the early days of the web, search engines revolutionized information retrieval by leveraging the "link economy." Algorithms like PageRank and HITS (Hubs and Authorities) treated hyperlinks as manual votes of confidence, allowing engines to identify authoritative pages. However, biomedical literature databases like MEDLINE lack a dynamic hyperlink structure. While citations exist, they are static and not easily accessible for real-time search reranking. Most biomedical systems instead rely on "bag-of-words" matching, which looks for keyword overlap between queries and abstracts.

This paper addresses a central question: Can we create a "synthetic" link network based on content similarity and use it to find the most authoritative papers for a given query?

Methodology

The proposed approach utilizes a two-stage reranking pipeline that transforms a standard search result into a graph-based authority assessment.

  1. Initial Retrieval: A baseline list of the top 40 most relevant documents is generated using the Terrier search engine, employing standard probabilistic models.
  2. Graph Construction: For each document in the top 40, the system queries the PubMed API to retrieve its $k$ most "related articles." These recommendations are based on a pre-existing content-similarity algorithm within PubMed. This process creates a local network where nodes are articles and edges represent high similarity.
PubMed interface showing 'Related Articles' which serve as the basis for the synthetic link network.
  1. Graph Analysis: The author applies PageRank and HITS to this similarity network. PageRank models a "random surfer" moving between similar papers; papers that are "central" to the similarity cluster receive higher scores. HITS identifies "Authorities" (papers many others are similar to) and "Hubs" (papers that link to many authorities).
  2. Interpolation: The final ranking is determined by a weighted combination of the original search score and the new graph-based score, controlled by a parameter $\lambda$.

Experimental Setup

The study utilized the TREC 2005 Genomics track test collection, which includes a ten-year subset of MEDLINE records and 50 specific information needs (e.g., describing the role of a gene in a biological process). Human-judged relevance rankings provided the ground truth for calculating Mean Average Precision (MAP) and Precision at 20 (P20).

Key Results and Insights

The core finding is that automated similarity scores can be treated as functional equivalents to manual hyperlinks. This reinforces the "cluster hypothesis" in information retrieval: relevant documents tend to be more similar to each other than to non-relevant ones.

  • Performance Gains: Incorporating PageRank scores yielded statistically significant improvements over the baseline engine. In five-fold cross-validation, the system showed a 7.8% improvement in MAP20 and a 6.1% improvement in P20.
  • Optimal Weighting: The best performance occurred when $\lambda$ was between 0.6 and 0.8. This suggests that the most effective ranking comes from a mix of 60-80% keyword matching and 20-40% graph-based authority.
  • Network Density: Performance generally improved as the network became denser. Including up to 20 neighbors per paper provided a clearer signal of which papers were at the "heart" of the relevant cluster.
Reranking performance (MAP at 20) across different values of λ and expansion sizes.

PageRank proved more effective and robust than HITS. The author suggests this is because HITS relies on a specific "hub and authority" relationship that is less pronounced in similarity-based graphs than in traditional citation or web-link graphs.

Discussion and Limitations

While effective, this method introduces computational overhead. Building and analyzing a graph on the fly for every query is expensive. The current study focused on "local" graphs for the top 40 results; scaling this to the entire 17 million+ records in PubMed would require significant optimization or pre-computation.

Future work may explore "query-independent" link analysis, where similarity scores are pre-calculated across the entire database. This would mirror how Google handles the web, potentially making graph-based reranking fast enough for production-level biomedical search engines.

Summary updated

Abstract

Graph analysis algorithms such as PageRank and HITS have been successful in Web environments because they are able to extract important inter-document relationships from manually-created hyperlinks. We consider the application of these techniques to biomedical text retrieval. In the current PubMed® search interface, a MEDLINE® citation is connected to a number of related citations, which are in turn connected to other citations. Thus, a MEDLINE record represents a node in a vast content-similarity network. This article explores the hypothesis that these networks can be exploited for text retrieval, in the same manner as hyperlink graphs on the Web.
BibTeX
@article{lin2008pagerank,
  author = {Jimmy Lin},
  title = {{PageRank without hyperlinks: Reranking with PubMed related article networks for biomedical text retrieval}},
  journal = {BMC Bioinformatics},
  year = {2008},
  doi = {10.1186/1471-2105-9-270},
}
Figure