Dynamic personalized pagerank in entity-relation graphs

Soumen Chakrabarti

In modern information retrieval, searching massive Entity-Relation (ER) graphs—where nodes represent diverse entities like authors, companies, or papers—requires more than simple keyword matching. Users often seek "proximity" results: for instance, finding a researcher closely associated with a specific company who has published on a particular topic.

An example of an Entity-Relation (ER) graph showing nodes like Person, Company, and Paper connected by various relationships.

The gold standard for ranking these proximity searches is Personalized PageRank (PPR). However, PPR presents a significant scalability challenge. Computing PPR at query time is too slow for interactive use (often exceeding 10 seconds), while precomputing PPR vectors for every possible term requires astronomical storage—potentially hundreds of gigabytes for even moderately sized datasets like CiteSeer.

HubRank: A Hybrid Solution

Presented at WWW 2007, HubRank addresses this "Holy Grail" of graph search by finding a middle ground between slow query-time computation and bloated precomputation. HubRank achieves query times of 200–300 milliseconds—roughly 40x faster than standard PageRank—while maintaining an index size comparable to a standard text search engine.

Methodology: Localizing the Problem

HubRank's efficiency stems from its ability to "localize" the PageRank calculation. Instead of processing the entire graph, it focuses on a small, relevant neighborhood.

Active Subgraph Expansion

When a query is initiated, HubRank expands an "active subgraph" around the query terms. This expansion is strategically bounded by two types of nodes:

  1. Blockers: These are "hubs"—frequently searched nodes for which HubRank has precomputed "fingerprints" (compact sketches of PPR vectors).
  2. Losers: These are nodes determined to be too distant from the query source to significantly impact the final ranking.
The HubRank expansion process: identifying an active subgraph bounded by blockers (cached hubs) and losers (distant nodes).

Workload-Driven Hub Selection

A key innovation is the use of query logs to identify which nodes should serve as hubs. By prioritizing nodes that appear frequently in actual user behavior, HubRank exploits the Zipfian (power-law) distribution of search terms. This allows the system to achieve massive speedups by indexing only a small fraction of the most "merit-worthy" nodes.

Monte Carlo Fingerprints and Dynamic Resolution

Rather than storing dense, exact PPR vectors, HubRank utilizes Monte Carlo fingerprints—probabilistic sketches generated by random walks. These fingerprints are stored at varying resolutions. At query time, HubRank uses an "abandon threshold" ($\delta$) to load only the most significant portions of these fingerprints, drastically reducing I/O overhead without sacrificing ranking quality.

Key Insights and Results

The authors evaluated HubRank using the CiteSeer corpus, consisting of approximately 700,000 words and 1.1 million entity nodes.

  • Entities as Superior Hubs: The study found that indexing central entities (e.g., prominent authors or companies) is often more effective at blocking graph expansion than indexing words alone. A hybrid hub set of both words and entities yielded the best performance.
  • Efficiency: The HubRank index for CiteSeer required only 63 MB, compared to the estimated 102 GB needed for full PPR vectors. Furthermore, the indexing phase was 52 times faster than a full vocabulary precomputation.
  • Accuracy: Despite its approximations, HubRank maintained a high precision of 0.91. In contrast, simply truncating standard PPR vectors to fit the same storage footprint resulted in a precision of only 0.55.

Conclusion

HubRank demonstrates that high-performance, personalized proximity search on large-scale ER graphs is achievable through intelligent hub selection and localized computation. By leveraging query workloads and compact probabilistic fingerprints, it provides a scalable path forward for complex graph-based information retrieval.

Summary updated

Abstract

Extractors and taggers turn unstructured text into entity-relation(ER) graphs where nodes are entities (email, paper, person,conference, company) and edges are relations (wrote, cited,works-for). Typed proximity search of the form <B>type=personNEAR company~"IBM", paper~"XML"</B> is an increasingly usefulsearch paradigm in ER graphs. Proximity search implementations either perform a Pagerank-like computation at query time, which is slow, or precompute, store and combine per-word Pageranks, which can be very expensive in terms of preprocessing time and space. We present HubRank, a new system for fast, dynamic, space-efficient proximity searches in ER graphs. During preprocessing, HubRank computesand indexes certain "sketchy" random walk fingerprints for a small fraction of nodes, carefully chosen using query log statistics. At query time, a small "active" subgraph is identified, bordered bynodes with indexed fingerprints. These fingerprints are adaptively loaded to various resolutions to form approximate personalized Pagerank vectors (PPVs). PPVs at remaining active nodes are now computed iteratively. We report on experiments with CiteSeer's ER graph and millions of real Cite Seer queries. Some representative numbers follow. On our testbed, HubRank preprocesses and indexes 52 times faster than whole-vocabulary PPV computation. A text index occupies 56 MB. Whole-vocabulary PPVs would consume 102GB. If PPVs are truncated to 56 MB, precision compared to true Pagerank drops to 0.55; incontrast, HubRank has precision 0.91 at 63MB. HubRank's average querytime is 200-300 milliseconds; query-time Pagerank computation takes 11 seconds on average.
BibTeX
@inproceedings{chakrabarti2007dynamic,
  author = {Soumen Chakrabarti},
  title = {{Dynamic personalized pagerank in entity-relation graphs}},
  booktitle = {The Web Conference},
  year = {2007},
  doi = {10.1145/1242572.1242650},
}
Figure