# GPU-accelerated Multi-relational Parallel Graph Retrieval for Web-scale Recommendations

arXiv: https://arxiv.org/abs/2502.11490 · HTML: https://mlsanity.com/paper/2502.11490/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 17 Feb 2025.

## Builds on (most cited first, 17 of 17)

- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Wide & Deep Learning for Recommender Systems](https://mlsanity.com/paper/1606.07792/) (2016)
- [Deep Learning based Recommender System: A Survey and New Perspectives](https://mlsanity.com/paper/1707.07435/) (2017)
- [Learning Tree-based Deep Model for Recommender Systems](https://mlsanity.com/paper/1801.02294/) (2018)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Neural Ranking Models with Weak Supervision](https://mlsanity.com/paper/1704.08803/) (2017)
- [A Survey on Accuracy-oriented Neural Recommendation: From Collaborative Filtering to Information-rich Recommendation](https://mlsanity.com/paper/2104.13030/) (2021)
- [DNNFusion: Accelerating Deep Neural Networks Execution with Advanced Operator Fusion](https://mlsanity.com/paper/2108.13342/) (2021)
- [Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time](https://mlsanity.com/paper/1711.07601/) (2017)
- [Latent Relational Metric Learning via Memory-based Attention for Collaborative Ranking](https://mlsanity.com/paper/1707.05176/) (2017)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Deep Item-based Collaborative Filtering for Top-N Recommendation](https://mlsanity.com/paper/1811.04392/) (2018)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation](https://mlsanity.com/paper/2202.10226/) (2022)
- [JIZHI: A Fast and Cost-Effective Model-As-A-Service System for Web-Scale Online Inference at Baidu](https://mlsanity.com/paper/2106.01674/) (2021)
- [Approximate Nearest Neighbor Fields in Video](https://mlsanity.com/paper/1508.07953/) (2015)

## Abstract (arXiv)

Web recommendations provide personalized items from massive catalogs for users, which rely heavily on retrieval stages to trade off the effectiveness and efficiency of selecting a small relevant set from billion-scale candidates in online digital platforms. As one of the largest Chinese search engine and news feed providers, Baidu resorts to Deep Neural Network (DNN) and graph-based Approximate Nearest Neighbor Search (ANNS) algorithms for accurate relevance estimation and efficient search for relevant items. However, current retrieval at Baidu fails in comprehensive user-item relational understanding due to dissected interaction modeling, and performs inefficiently in large-scale graph-based ANNS because of suboptimal traversal navigation and the GPU computational bottleneck under high concurrency. To this end, we propose a GPU-accelerated Multi-relational Parallel Graph Retrieval (GMP-GR) framework to achieve effective yet efficient retrieval in web-scale recommendations. First, we propose a multi-relational user-item relevance metric learning method that unifies diverse user behaviors through multi-objective optimization and employs a self-covariant loss to enhance pathfinding performance. Second, we develop a hierarchical parallel graph-based ANNS to boost graph retrieval throughput, which conducts breadth-depth-balanced searches on a large-scale item graph and cost-effectively handles irregular neural computation via adaptive aggregation on GPUs. In addition, we integrate system optimization strategies in the deployment of GMP-GR in Baidu. Extensive experiments demonstrate the superiority of GMP-GR in retrieval accuracy and efficiency. Deployed across more than twenty applications at Baidu, GMP-GR serves hundreds of millions of users with a throughput exceeding one hundred million requests per second.