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:
- 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.
- Local Ball Growing: For the majority of nodes, the algorithm employs a lightweight local search, exploring only a restricted neighborhood (a "ball").
- 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.
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).
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