TL;DR
This paper tackles the challenge of efficiently computing personalized PageRank and SimRank scores on massive web graphs. The authors introduce novel algorithms that use rounding and randomized sketching to create compact "summaries" of the graph, enabling fast, on-line queries with provably optimal space usage.
What Problem Does This Paper Address?
The web is a massive graph, and understanding the relationships between pages is crucial for search engines and other applications. Personalized PageRank (PPR) and SimRank are two important link-analysis metrics that capture different aspects of these relationships. PPR measures the importance of a page based on a user's specific interests (teleportation vector), while SimRank measures the similarity between pages based on their link neighborhoods.
The core problem is that computing these metrics exactly for every possible query on a web-scale graph is computationally prohibitive. Traditional methods either require too much space to store precomputed results or are too slow to answer queries in real-time. Specifically, naive PPR computation requires re-running power iterations for each query, and naive SimRank requires computing an n x n similarity matrix. Existing scalable methods, like Monte Carlo sampling, offer approximations but with limitations on precision or flexibility. This paper aims to bridge this gap by developing algorithms that are both space-efficient and provide strong theoretical guarantees on the quality of their approximations.
Methods
The paper's main contribution lies in developing two-phase algorithms that first preprocess the graph into a compact "summary" and then answer queries efficiently from this summary.
- Rounding: The core idea is to use deterministic rounding to approximate intermediate values in the dynamic programming algorithms for PPR and SimRank. By rounding values down to a multiple of a small error parameter $\epsilon$, the number of non-zero entries in intermediate vectors can be significantly reduced. This allows for efficient storage and computation. The authors prove that this rounding approach, when applied iteratively, leads to a bounded additive error.
- Randomized Sketching: For even greater space efficiency, the authors also employ randomized sketching techniques, specifically adapting the Count-Min sketch. Sketches are compact data structures that can represent large vectors approximately. By using sketches, they can further reduce the space requirements, especially for PPR value queries, achieving theoretical optimality.
- Reduction of SimRank to PPR: A key theoretical insight is the reduction of SimRank computation to personalized PageRank on a reversed graph. This allows them to leverage existing PPR algorithms and techniques for SimRank.
Datasets
The experiments were conducted on the Stanford WebBase graph, containing approximately 80 million pages from the 2001 crawl. This is a large-scale, real-world dataset commonly used for evaluating web graph algorithms.
Key Insights and Ideas
- Rounding is surprisingly effective: Deterministic rounding, often seen as a simple approximation technique, proves to be a powerful tool for achieving space-optimal summaries for both PPR and SimRank.
- Space optimality is achievable: The paper demonstrates that it's possible to achieve theoretical lower bounds on space complexity for both value and top-list queries, a significant improvement over previous methods.
- SimRank can be reduced to PPR: This is a crucial theoretical result that allows for the application of PPR techniques to SimRank, simplifying its scalable computation.
- Trade-offs between rounding and sketching: While sketching offers better theoretical space bounds for value queries, deterministic rounding is shown to be optimal for top-list queries and offers a good balance of performance and simplicity.
Key Results
- Space-Optimal Algorithms: The paper presents algorithms for personalized PageRank and SimRank that achieve provably optimal space complexity, matching theoretical lower bounds.
- Improved PPR Value Queries: For PPR value queries, a randomized sketching algorithm improves the disk usage bound from $O(n \log n / \epsilon^2)$ to $O(n \log(1/\delta) / \epsilon)$.
- Practical Performance: Experiments on the Stanford WebBase graph show that the rounded dynamic programming approach for PPR significantly outperforms other methods in terms of approximation quality and running time.
- SimRank Efficiency: The SimRank algorithm, leveraging the reduction to PPR, also demonstrates improved performance and space efficiency.
Limitations and Future Work
- Parameter Sensitivity: The performance of the algorithms is dependent on parameters like $\epsilon$ (error) and $\delta$ (error probability), which need to be chosen appropriately.
- SimRank for $c < 1/2$: The paper leaves open the question of theoretically optimal algorithms for SimRank value and top-list queries when the teleportation constant $c$ is less than $1/2$.
- Generalization to other Markov chain properties: The authors suggest exploring whether their techniques can be extended to approximate other properties of Markov chains on massive graphs, such as hitting times.
- Further SimRank Evaluation: More thorough experimental evaluation of the SimRank approximation algorithms is recommended.
Summary updated