Abstract
Similarity search over bipartite graphs is essential for applications like online advertising and recommender systems. However, existing measures often overlook bipartite-specific properties or fail to capture high-order information accurately. While Hidden Personalized PageRank (HPP) is effective, it suffers from directional bias and high computational costs on large graphs. This paper introduces Bidirectional Hidden Personalized PageRank (BHPP) to resolve the bias and presents Approx-BHPP, an efficient algorithm with rigorous accuracy guarantees and optimal computational complexity. Our experiments demonstrate that BHPP significantly improves result quality in query rewriting and item recommendation, while Approx-BHPP achieves speedups of up to orders of magnitude over state-of-the-art baselines.
Introduction
Bipartite graphs model relationships between two distinct sets of entities, such as users and products or queries and webpages. Finding similar items within these graphs is a core task for recommendation engines. Hidden Personalized PageRank (HPP) has emerged as a powerful metric for this purpose, yet it has two major flaws:
- Directional Bias: HPP is asymmetric; the similarity from node A to B is not necessarily the same as from B to A, leading to suboptimal recommendations.
- Computational Cost: HPP operates on a "hidden" transition matrix that becomes extremely dense on large graphs, making standard computation methods prohibitively slow or memory-intensive.
Methodology: BHPP and Approx-BHPP
We propose a two-fold solution: a refined similarity metric and a high-performance algorithm to compute it.
Bidirectional HPP (BHPP)
To fix the inherent bias of HPP, we define BHPP as the sum of HPP values in both directions: $\pi(u, u_i) + \pi(u_i, u)$. This ensures that similarity is mutual and captures the topological structure of the graph more effectively. We leverage a mathematical symmetry trick to compute bidirectional similarity almost as fast as unidirectional similarity.
The Approx-BHPP Algorithm
Calculating BHPP exactly is too slow for real-world applications. Approx-BHPP combines two novel techniques to provide fast, accurate estimates:
- SS-Push (Selective and Sequential Push): Standard "push" algorithms struggle with high-degree "super-nodes." SS-Push adaptively switches between selective pushes for efficiency and sequential batch pushes when a node has too many neighbors to process individually.
- PI-Push (Power Iteration-based Push): This uses mathematical symmetry to transform target-node HPP values into source-node values, refining estimates using Power Iteration without ever materializing the massive, dense hidden matrix.
A key innovation is the "decoupling" trick: instead of calculating the dense matrix $P = U \cdot V$ directly, we perform multiplications in the order $(x \cdot U) \cdot V$. This keeps operations linear relative to the number of edges, saving massive amounts of memory.
Experimental Evaluation
We evaluated our approach using seven real-world bipartite datasets across two main tasks: query rewriting (using click graphs like Avito and KDDCup) and item recommendation (using user-item graphs like DBLP and MovieLens).
Effectiveness in Query Rewriting
BHPP consistently outperforms eight existing similarity measures, including SimRank and standard HPP. As shown in Figure 2, BHPP achieves the highest NDCG@10 scores across multiple datasets, demonstrating its superior ability to capture relevant similarities in search contexts.
Computational Efficiency
Approx-BHPP provides massive speedups while maintaining a mathematical guarantee that the error will never exceed a user-defined threshold ($\epsilon$). For common accuracy requirements ($\epsilon = 10^{-2}$), it was two orders of magnitude faster than the best existing competitors on almost all datasets. Figure 5 illustrates this performance gap across various graph types.
Conclusion
BHPP and the Approx-BHPP algorithm provide a robust framework for similarity search in bipartite graphs, combining theoretical rigor with practical performance. While highly effective for static graphs, future research will focus on extending these bidirectional techniques to dynamic bipartite graphs where edges are constantly added or removed.
Summary updated