Efficient Retrieval of Matrix Factorization-Based Top-k Recommendations: A Survey of Recent Approaches

Dung D. Le, Hady Wirawan LauwJAIR 2021 · OpenReview

TL;DR

This paper surveys recent advancements in efficiently retrieving top-k recommendations from Matrix Factorization (MF) models. It addresses the critical bottleneck of real-time recommendation retrieval in large-scale systems by categorizing and analyzing various techniques for fast candidate generation and ranking, crucial for delivering personalized experiences without sacrificing speed.

What Problem Does This Paper Address?

Recommender systems are ubiquitous, aiming to present users with a personalized list of "top-k" items. Matrix Factorization (MF) is a dominant technique for this, learning low-dimensional representations (vectors) for users and items. While MF excels at learning user preferences (preference elicitation), the subsequent step of retrieving these top-k recommendations (recommendation retrieval) becomes a major challenge. Naively calculating the similarity (inner product) between a user's vector and every single item's vector in a massive catalog (millions or billions of items) is computationally prohibitive for real-time applications. This paper tackles this "recommendation retrieval bottleneck" by surveying and organizing methods that accelerate this process.

Methods

The paper surveys techniques that optimize the recommendation retrieval phase, which is broken down into two main steps:

  1. Candidate Generation: This step aims to quickly identify a smaller subset of potentially relevant items, significantly reducing the number of items that need to be scored. Approaches include:
  2. Indexing Structures: Pre-processing item vectors into structures like Locality Sensitive Hashing (LSH), spatial trees, or similarity graphs to enable sub-linear time searching.
  3. Item Ranking Estimation: Approximating the ranking of inner product scores without direct computation, using methods like sorted indices lists or sampling.
  4. Exact Methods: Techniques that guarantee finding the exact top-k items but are more efficient than brute-force linear scanning, such as sequential scanning with pruning or hardware-accelerated solvers.
  5. Candidate Ranking: Once a candidate set is generated, this step re-ranks them to select the final top-k. Methods here focus on:
  6. Discrete Representation: Encoding user and item vectors into binary codes, allowing for faster similarity computations (e.g., Hamming distance) instead of inner products. This includes quantization-based and optimization-based discretization.
  7. Quantization: Approximating inner product computations by representing vectors with a smaller set of representative vectors (codebooks), such as Vector Quantization and Product Quantization.

Datasets

Not explicitly discussed in the paper. The paper focuses on surveying existing methods and their theoretical complexities rather than presenting new experimental results on specific datasets.

Key Insights and Ideas

  • The Retrieval Bottleneck is Real: The paper strongly emphasizes that while preference elicitation has seen much progress, the retrieval phase is the true hurdle for large-scale, real-time recommendation systems.
  • Two-Stage Approach is Standard: The division of retrieval into candidate generation and candidate ranking is a fundamental paradigm that most efficient methods adhere to.
  • Trade-offs are Inevitable: Achieving speed often comes at the cost of some accuracy (approximate methods), and vice-versa. The paper highlights how various methods allow tuning this accuracy-efficiency trade-off.
  • Inner Product Search is a General Problem: The core challenge of MF recommendation retrieval (Maximum Inner Product Search - MIPS) is a well-studied problem in broader areas like similarity search, meaning solutions from those fields are often adapted.
  • Data Structure Choice Matters: The choice between data-dependent (e.g., similarity graphs) and data-independent (e.g., LSH) indexing structures has implications for construction cost, update flexibility, and query performance.

Key Results

The paper is a survey, so it doesn't present new empirical results. Instead, it synthesizes the state-of-the-art by:

  • Comprehensive Taxonomy: Organizing a wide range of retrieval methods into clear categories (candidate generation, candidate ranking) and sub-categories.
  • Theoretical Analysis: Providing insights into the computational complexities (construction time, candidate generation time, candidate ranking time) of various approaches, often summarized in tables.
  • Qualitative Comparisons: Discussing the strengths, weaknesses, and trade-offs of different methods in terms of accuracy, efficiency, and applicability to various scenarios (e.g., budgeted queries, handling negative values).

Limitations and Future Work

  • Limitations of Existing Methods:
    • Many sampling methods struggle with non-negative item/user vectors.
  • Quantization-based discretization can suffer from significant information loss.
  • Similarity graph construction can be computationally expensive.
  • Some methods require frequent updates to retrieval-efficient structures as data changes.
  • Future Work Directions:
    • Developing efficient data structures for hybrid representations (combining sparse and dense vectors).
  • Creating unified frameworks that jointly optimize preference elicitation and recommendation retrieval.
  • Adapting efficient retrieval techniques for complex deep neural network-based recommender models.
  • Investigating how approximate retrieval methods impact other recommendation objectives like novelty, coverage, and serendipity.
  • Addressing the scalability challenges of ever-growing user and item bases.

Summary updated

Abstract

Top-k recommendation seeks to deliver a personalized list of k items to each individual user. An established methodology in the literature based on matrix factorization (MF), which usually represents users and items as vectors in low-dimensional space, is an effective approach to recommender systems, thanks to its superior performance in terms of recommendation quality and scalability. A typical matrix factorization recommender system has two main phases: preference elicitation and recommendation retrieval. The former analyzes user-generated data to learn user preferences and item characteristics in the form of latent feature vectors, whereas the latter ranks the candidate items based on the learnt vectors and returns the top-k items from the ranked list. For preference elicitation, there have been numerous works to build accurate MF-based recommendation algorithms that can learn from large datasets. However, for the recommendation retrieval phase, naively scanning a large number of items to identify the few most relevant ones may inhibit truly real-time applications. In this work, we survey recent advances and state-of-the-art approaches in the literature that enable fast and accurate retrieval for MF-based personalized recommendations. Also, we include analytical discussions of approaches along different dimensions to provide the readers with a more comprehensive understanding of the surveyed works.
BibTeX
@article{le2021efficient,
  author = {Dung D. Le and Hady Wirawan Lauw},
  title = {{Efficient Retrieval of Matrix Factorization-Based Top-k Recommendations: A Survey of Recent Approaches}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  url = {https://openreview.net/forum?id=wx5qFEpDyH},
}
Figure