Efficient and Effective Similarity Search over Bipartite Graphs

Renchi Yang

TL;DR

This paper introduces Bidirectional Hidden Personalized PageRank (BHPP), a new similarity measure for bipartite graphs that fixes the inherent bias found in previous methods. To make this computationally feasible on massive datasets, the author developed Approx-BHPP, an algorithm that provides rigorous accuracy guarantees while running orders of magnitude faster than existing state-of-the-art solutions.

What Problem Does This Paper Address?

Bipartite graphs—which model relationships between two different sets of entities like users and products, or queries and webpages—are the backbone of modern recommendation engines and online advertising. To find "similar" items in these graphs, researchers often use Hidden Personalized PageRank (HPP).

However, HPP has two major flaws:

  1. Bias: HPP is directional. The similarity from node A to node B isn't necessarily the same as from B to A. This "one-sided" view leads to suboptimal recommendations.
  2. Computational Cost: HPP operates on a "hidden" transition matrix that represents multi-step jumps between nodes of the same type. On large graphs, this matrix becomes incredibly dense, making standard computation methods prohibitively slow or memory-intensive.

Methods

The author proposes a two-fold solution: a better metric and a faster way to calculate it.

1. Bidirectional HPP (BHPP)

To fix the bias, the paper defines 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.

2. The Approx-BHPP Algorithm

Calculating BHPP exactly is too slow, so the author designed Approx-BHPP, which combines two novel sub-algorithms:

  • SS-Push (Selective and Sequential Push): Standard "push" algorithms (which spread similarity scores like fluid through a pipe) struggle with high-degree 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 a mathematical symmetry trick to transform target-node HPP values into source-node values. It then refines these estimates using a few rounds of matrix-vector multiplication (Power Iteration) without ever having to fully "materialize" the massive, dense hidden matrix.

Datasets

The study evaluated the approach using 7 real-world bipartite datasets across two main tasks:

  • Click Graphs (Query Rewriting): Avito, KDDCup, and AOL. These track which ads or URLs users clicked after specific search queries.
  • User-Item Graphs (Recommendation): DBLP (author-venue), MovieLens (user-movie), Last.fm (user-song), and Amazon-Games (user-game).

Key Insights and Ideas

  • The "Decoupling" Trick: The biggest bottleneck in bipartite similarity is the matrix $P = U \cdot V$. Instead of calculating $P$ directly (which is slow and dense), the author performs multiplications in the order $(x \cdot U) \cdot V$. This keeps the operations linear relative to the number of edges, saving massive amounts of memory.
  • Greedy Adaptation: The "aha moment" in the SS-Push algorithm is the realization that neither selective nor sequential pushing is always best. By tracking a "computational budget," the algorithm dynamically switches strategies to handle "super-nodes" (nodes with thousands of connections) that usually crash traditional algorithms.
  • Symmetry as a Shortcut: The paper leverages a specific lemma showing that the ratio of HPP values between two nodes is related to the ratio of their weighted degrees. This allows the algorithm to compute bidirectional similarity almost as fast as unidirectional similarity.

Key Results

  • Better Recommendations: In item recommendation tests (e.g., MovieLens), BHPP outperformed 8 other measures—including SimRank and standard HPP—by significant margins. On the DBLP dataset, it improved precision and recall by roughly 0.7–0.9% over the next best competitor.
  • Massive Speedups: Approx-BHPP is significantly faster than baseline solutions. For common accuracy requirements ($\epsilon = 10^{-2}$), it was two orders of magnitude faster than the best existing competitors on almost all datasets.
  • Theoretical Rigor: Unlike many heuristic-based similarity measures, Approx-BHPP comes with a mathematical guarantee that the error will never exceed a user-defined threshold ($\epsilon$).

Limitations and Future Work

The current version of Approx-BHPP is designed for static graphs, where the relationships between nodes don't change during the computation. However, real-world graphs like social networks or live ad auctions are highly dynamic. The author notes that extending this bidirectional approach to temporal or dynamic bipartite graphs—where edges are constantly being added or removed—is the next major hurdle for this research.

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},
}

Loading related content...

Figure