Efficient and Effective Similarity Search over Bipartite Graphs

Renchi Yang*

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


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.

Original languageEnglish
Title of host publicationWWW '22: Proceedings of the ACM Web Conference 2022
PublisherAssociation for Computing Machinery (ACM)
Number of pages11
ISBN (Print)9781450390965
Publication statusPublished - 25 Apr 2022
Event31st ACM World Wide Web Conference, WWW 2022 - Virtual, Online, Lyon, France
Duration: 25 Apr 202229 Apr 2022

Publication series

NameWWW: International World Wide Web Conference


Conference31st ACM World Wide Web Conference, WWW 2022
Internet address

Scopus Subject Areas

  • Computer Networks and Communications
  • Software

User-Defined Keywords

  • Approximate Algorithms
  • Bipartite Graphs
  • Similarity Search


Dive into the research topics of 'Efficient and Effective Similarity Search over Bipartite Graphs'. Together they form a unique fingerprint.

Cite this