# Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 14 Feb 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [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)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Adversarial Training for Free!](https://mlsanity.com/paper/1904.12843/) (2019)
- [Deep Interest Network for Click-Through Rate Prediction](https://mlsanity.com/paper/1706.06978/) (2017)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [Adversarial Examples: Attacks and Defenses for Deep Learning](https://mlsanity.com/paper/1712.07107/) (2017)
- [Learning from Simulated and Unsupervised Images through Adversarial Training](https://mlsanity.com/paper/1612.07828/) (2016)
- [Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction](https://mlsanity.com/paper/2006.05639/) (2020)
- [Embedding-based Retrieval in Facebook Search](https://mlsanity.com/paper/2006.11632/) (2020)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Multi-Interest Network with Dynamic Routing for Recommendation at Tmall](https://mlsanity.com/paper/1904.08030/) (2019)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Learning Tree-based Deep Model for Recommender Systems](https://mlsanity.com/paper/1801.02294/) (2018)
- [Hessian-based Analysis of Large Batch Training and Robustness to Adversaries](https://mlsanity.com/paper/1802.08241/) (2018)
- [Natural Neural Networks](https://mlsanity.com/paper/1507.00210/) (2015)
- [Joint Optimization of Tree-based Index and Deep Model for Recommender Systems](https://mlsanity.com/paper/1902.07565/) (2019)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Gradient Adversarial Training of Neural Networks](https://mlsanity.com/paper/1806.08028/) (2018)
- [Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations](https://mlsanity.com/paper/2007.07203/) (2020)
- [Relevance Proximity Graphs for Fast Relevance Retrieval](https://mlsanity.com/paper/1908.06887/) (2019)

## Built on by (most cited first, 14 of 14)

- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [Large Language Model as Universal Retriever in Industrial-Scale Recommender System](https://mlsanity.com/paper/2502.03041/) (2025)
- [REIS: A High-Performance and Energy-Efficient Retrieval System with In-Storage Processing](https://mlsanity.com/paper/2506.16444/) (2025)
- [Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.04713/) (2024)
- [MISS: Multi-Modal Tree Indexing and Searching with Lifelong Sequential Behavior for Retrieval Recommendation](https://mlsanity.com/paper/2508.14515/) (2025)
- [Robust Representation Learning for Unified Online Top-K Recommendation](https://mlsanity.com/paper/2310.15492/) (2023)
- [Deep Uncertainty-Based Explore for Index Construction and Retrieval in Recommendation System](https://mlsanity.com/paper/2408.00799/) (2024)
- [UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture](https://mlsanity.com/paper/2410.23805/) (2024)
- [GPU-accelerated Multi-relational Parallel Graph Retrieval for Web-scale Recommendations](https://mlsanity.com/paper/2502.11490/) (2025)
- [Bidding-Aware Retrieval for Multi-Stage Consistency in Online Advertising](https://mlsanity.com/paper/2508.05206/) (2025)
- [An Efficient Embedding Based Ad Retrieval with GPU-Powered Feature Interaction](https://mlsanity.com/paper/2511.22460/) (2025)
- [Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System](https://mlsanity.com/paper/2602.16124/) (2026)
- [OneShot: Index-in-Ranking with Neural Scoring for Large-Scale Retrieval](https://mlsanity.com/paper/2607.27475/) (2026)

## Abstract (arXiv)

Model-based methods for recommender systems have been studied extensively for years. Modern recommender systems usually resort to 1) representation learning models which define user-item preference as the distance between their embedding representations, and 2) embedding-based Approximate Nearest Neighbor (ANN) search to tackle the efficiency problem introduced by large-scale corpus. While providing efficient retrieval, the embedding-based retrieval pattern also limits the model capacity since the form of user-item preference measure is restricted to the distance between their embedding representations. However, for other more precise user-item preference measures, e.g., preference scores directly derived from a deep neural network, they are computationally intractable because of the lack of an efficient retrieval method, and an exhaustive search for all user-item pairs is impractical. In this paper, we propose a novel method to extend ANN search to arbitrary matching functions, e.g., a deep neural network. Our main idea is to perform a greedy walk with a matching function in a similarity graph constructed from all items. To solve the problem that the similarity measures of graph construction and user-item matching function are heterogeneous, we propose a pluggable adversarial training task to ensure the graph search with arbitrary matching function can achieve fairly high precision. Experimental results in both open source and industry datasets demonstrate the effectiveness of our method. The proposed method has been fully deployed in the Taobao display advertising platform and brings a considerable advertising revenue increase. We also summarize our detailed experiences in deployment in this paper.