The Space Complexity of Personalized PageRank and Shortest Path Labeling Schemes.

Huacheng Yu, Hongyang ZhangarXiv 2018 · arXiv

Abstract

We present tight space lower bounds for static personalized PageRank (PPR) labeling schemes and study shortest path labeling schemes on sparse random graphs with a power law degree distribution of exponent $\beta \in (2, 3)$. We obtain upper and lower bounds parameterized by $\beta$, which are nearly tight for $\beta \in (2, 2.5)$. Our work is motivated by the success of labeling schemes that achieve state-of-the-art performance for both PPR and shortest path problems in practice.

Introduction: The Challenge of Massive Graphs

Finding the shortest path between nodes is a cornerstone of network analysis. However, on massive web-scale graphs, standard algorithms like Dijkstra’s are computationally prohibitive for real-time queries. To address this, researchers utilize Distance Sketches or landmark-based labeling. By pre-calculating distances from every node to a small set of "landmarks," query time is reduced to a simple lookup: $dist(u, v) \approx \min_{z} (dist(u, z) + dist(z, v))$.

While Pruned Landmark Labeling (PLL) has seen significant empirical success, a theoretical gap remained. We lacked provable bounds on the number of landmarks required for the power-law graphs typical of social networks. This paper bridges that gap, providing the first rigorous theoretical guarantees and a new, more efficient algorithm.

Methodology: The ApproximatePruning Algorithm

The authors introduce ApproximatePruning, a hybrid algorithm that optimizes landmark selection by distinguishing between global and local network structures:

  1. Global Landmarks: A full Breadth-First Search (BFS) with pruning is performed for a small set of high-degree "hub" nodes, forming the backbone of the distance sketch.
  2. Local Ball Growing: For the majority of nodes, the algorithm employs a lightweight local search, exploring only a restricted neighborhood (a "ball").
  3. Degree-Based Pruning: At the boundaries of these local balls, the algorithm prioritizes landmarks with higher degrees than their predecessors, leveraging the fact that high-degree nodes are more likely to lie on shortest paths.

This approach captures both global connectivity and local detail without the overhead of exhaustive global searches from every vertex.

Theoretical Insights: The Power-Law Advantage

In graphs with a power-law degree distribution ($2 < \beta < 3$), shortest paths naturally funnel through high-degree hubs. The paper proves that pruning is essential; without it, landmark schemes on sparse random graphs would require $O(n^2)$ space. With pruning, exact distances can be achieved with sub-quadratic space.

Theoretical bounds on landmark counts as a function of the power-law exponent $\beta$.

As shown in Figure 1, the total number of landmarks required varies significantly with the power-law exponent $\beta$. For the regime $\beta \in (2, 2.5)$, the derived upper and lower bounds are nearly tight, providing a solid theoretical foundation for the efficiency observed in practice.

Empirical Results

The algorithm was evaluated on diverse datasets from the Stanford Large Network Dataset Collection (SNAP), including social networks (Twitter, Youtube), web graphs (Google, Stanford), and collaboration networks (DBLP).

Comparison of ApproximatePruning and PrunedLabeling across space, preprocessing time, and query time.

Key findings include:

  • Space Efficiency: ApproximatePruning reduced landmark storage by 1.5x to 2.5x compared to standard PLL.
  • Preprocessing Speed: Preprocessing time improved by 2x to 15x. On the Google web graph, the method achieved significant speedups while maintaining a relative average error of only 0.51%.
  • Query Performance: The average number of landmarks queried remained competitive or superior to existing methods, as illustrated in the performance comparisons above.

Conclusion and Future Work

This work provides a theoretical justification for the success of landmark labeling on real-world graphs. While the current analysis focuses on the Chung-Lu random graph model, future research could extend these bounds to preferential attachment models or different network topologies like transportation maps. Closing the remaining gap for $\beta \in (2.5, 3)$ also remains an important open mathematical challenge.

Summary updated

Abstract

We present tight space lower bounds for static personalized PageRank (PPR) labeling schemes. In a labeling scheme, each vertex is assigned a \emph{label vector}; To answer a query between two vertices, only the labels of the two vertices may be accessed. We show that for any personalized PageRank labeling schemes which can approximately recover PPR values that are at least $\delta$, the total labeling size must be at least $\tilde{\Omega}(n / \sqrt{\delta})$ on sparse Erd\{o}s-R\'enyi random graphs with high probability, where $n$ is the number of vertices in the graph. The result matches the upper bound of Lofgren et al.'16. We also study shortest path labeling schemes on sparse random graphs with a power law degree distribution of exponent $\beta \in (2, 3)$. We obtain upper and lower bounds which are parameterized by $\beta$, and are nearly tight for $\beta \in (2, 2.5)$. Our work is motivated by the success of labeling schemes that achieve state of the art performance for both personalized PageRank and shortest path data structure problems in practice. We hope that the techniques can also improve the understanding on other static data structure problems where labeling schemes are successful, yet obtaining super-logarithmic query time lower bounds in the cell-probe model remains technically challenging.
BibTeX
@misc{yu2018space,
  author = {Huacheng Yu and Hongyang Zhang},
  title = {{The Space Complexity of Personalized PageRank and Shortest Path Labeling Schemes.}},
  year = {2018},
  eprint = {1712.08709},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.08709},
}
Figure