BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank

Download PDF

Abstract

In bipartite graph analysis, similarity measures play a pivotal role in various applications. Among existing metrics, the Bidirectional Hidden Personalized PageRank (BHPP) stands out for its superior query quality. However, the computational expense of BHPP remains a bottleneck. Existing approximation methods either demand significant matrix storage or incur prohibitive time costs. For example, current state-of-the-art methods require over 3 hours to process a single-source BHPP query on the real-world bipartite graph Orkut, which contains approximately 3 × 108 edges. We introduce BIRD, a novel algorithm designed for answering single-source BHPP queries on weighted bipartite graphs. Through meticulous theoretical analysis, we demonstrate that BIRD significantly improves time complexity to O˜︁(𝑛), as compared to the previous best one, O˜︁(𝑚), under typical relative error setting and constant failure probability. (𝑛, 𝑚 denote the number of nodes and edges respectively.) Extensive experiments confirm that BIRD outperforms existing baselines by orders of magnitude in large-scale bipartite graphs. Notably, our proposed method accomplishes a single-source BHPP query on Orkut using merely 7 minutes.