Efficient and Effective Similarity Search over Bipartite Graphs

Renchi Yang

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:

  1. 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.
  2. 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.

Figure 2: Query rewriting performance (NDCG@10) across different datasets. BHPP (leftmost bar) consistently outperforms baselines.

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.

Figure 5: Query time comparison between Approx-BHPP and baselines across six datasets. Approx-BHPP (triangles) is consistently the fastest.

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

Abstract

Similarity search over a bipartite graph aims to retrieve from the graph the nodes that are similar to each other, which finds applications in various fields such as online advertising, recommender systems etc. Existing similarity measures either (i) overlook the unique properties of bipartite graphs, or (ii) fail to capture high-order information between nodes accurately, leading to suboptimal result quality. Recently, Hidden Personalized PageRank (HPP) is applied to this problem and found to be more effective compared with prior similarity measures. However, existing solutions for HPP computation incur significant computational costs, rendering it inefficient especially on large graphs. In this paper, we first identify an inherent drawback of HPP and overcome it by proposing bidirectional HPP (BHPP). Then, we formulate similarity search over bipartite graphs as the problem of approximate BHPP computation, and present an efficient solution Approx-BHPP. Specifically, Approx-BHPP offers rigorous theoretical accuracy guarantees with optimal computational complexity by combining deterministic graph traversal with matrix operations in an optimized and non-trivial way. Moreover, our solution achieves significant gain in practical efficiency due to several carefully-designed optimizations. Extensive experiments, comparing BHPP against 8 existing similarity measures over 7 real bipartite graphs, demonstrate the effectiveness of BHPP on query rewriting and item recommendation. Moreover, Approx-BHPP outperforms baseline solutions often by up to orders of magnitude in terms of computational time on both small and large datasets.
BibTeX
@inproceedings{yang2022efficient,
  author = {Renchi Yang},
  title = {{Efficient and Effective Similarity Search over Bipartite Graphs}},
  booktitle = {The Web Conference},
  year = {2022},
  doi = {10.1145/3485447.3511959},
}
Figure