Stochastically Robust Personalized Ranking for LSH Recommendation Retrieval

Dung D. Le, Hady W. LauwAAAI 2020 · OpenReview

Abstract

Locality Sensitive Hashing (LSH) is a cornerstone technique for approximate nearest neighbor search, enabling efficient recommendation retrieval by encoding user and item vectors into binary hash codes. However, standard matrix factorization models often suffer from performance degradation because they ignore the stochastic nature of LSH hash functions. We present SRPR (Stochastically Robust Personalized Ranking), a framework that incorporates LSH stochasticity directly into the learning process. By optimizing real-valued latent vectors to be resilient to hashing noise, SRPR achieves superior recommendation accuracy after LSH indexing compared to state-of-the-art baselines on large-scale datasets.

Introduction

In modern recommender systems, the retrieval phase—identifying the top $k$ items for a user from a pool of millions—is a significant computational bottleneck. While Matrix Factorization (MF) provides high-quality latent representations, the exhaustive inner-product computation required for ranking is often prohibitive in real-time settings.

Locality Sensitive Hashing (LSH) addresses this by mapping high-dimensional vectors to short binary strings, where similarity is approximated by Hamming distance. Despite its efficiency, LSH is inherently stochastic. This randomness can cause the ranking of items in the hash space to deviate significantly from the original vector space, leading to a drop in recommendation quality. This paper introduces SRPR to bridge this gap by learning "LSH-friendly" vectors.

The SRPR Framework

The SRPR framework operates in two distinct phases: a learning phase and a retrieval phase.

The two-phase SRPR framework: Phase I learns LSH-robust latent vectors, and Phase II performs efficient top-k retrieval using LSH.

Learning Stochastic Robustness

Unlike traditional models that treat hashing as a post-processing step, SRPR factors the mathematical properties of LSH into the training objective. The authors derive a mathematical foundation (Lemma 1) to calculate the probability that LSH will preserve the relative ranking of two items for a specific user. They identify a specific quantity, $\gamma_{uij}$, which represents how "safe" a ranking is from being flipped by the random hashing process.

The core of the framework is a new objective function that maximizes the likelihood that post-hashing Hamming distances will respect the user's original preferences. This ensures that the resulting latent vectors are positioned in the space such that they are resilient to the "blurring" effect of random hash projections.

LSH Compatibility

SRPR is designed to be versatile, supporting different hashing schemes:

  • SRPR-SRP: Tailored for Sign Random Projection, which preserves angular similarity (cosine distance).
  • SRPR-L2: Optimized for L2-LSH, which is suitable for Euclidean distance metrics.

Experimental Evaluation

The framework was evaluated using two large-scale, industry-standard datasets:

  • MovieLens 20M: 20 million ratings from approximately 138,000 users.
  • Netflix: Over 100 million ratings from approximately 480,000 users.

The primary metric for retrieval efficiency was nRecall@k, which measures how many of the "true" top-k items (from an exhaustive search) are successfully retrieved using the LSH-based candidate set.

Key Results

Experimental results demonstrate that SRPR consistently outperforms state-of-the-art baselines such as IBPR (Indexable Bayesian Personalized Ranking) and IPMF (Indexable Probabilistic Matrix Factorization).

Comparison of nRecall@k for SRPR variants and baselines on MovieLens 20M and Netflix datasets across different hash code lengths (b).

Key findings include:

  • Superior Retrieval Accuracy: SRPR variants (SRPR-L2 and SRPR-SRP) achieved the highest nRecall@k across various bit lengths (from 4 to 16 bits) and retrieval sizes ($k$).
  • Resilience to Short Codes: The performance gap between SRPR and baselines is most pronounced at shorter code lengths, where LSH variance is typically highest. This allows for faster retrieval without sacrificing quality.
  • No Representation Penalty: Interestingly, SRPR's robust vectors perform as well as standard MF vectors even when no hashing is applied. This indicates that the stochastic robustness constraint enhances the quality of the latent space without introducing negative trade-offs.

Conclusion

SRPR effectively addresses the performance degeneration caused by LSH stochasticity in recommender systems. By making the learning process "LSH-aware," the framework produces latent vectors that are inherently robust to binary quantization. Future work may involve extending this approach to data-dependent hashing schemes or addressing the cold-start problem within the robust ranking framework.

Summary updated

Abstract

Locality Sensitive Hashing (LSH) has become one of the most commonly used approximate nearest neighbor search techniques to avoid the prohibitive cost of scanning through all data points. For recommender systems, LSH achieves efficient recommendation retrieval by encoding user and item vectors into binary hash codes, reducing the cost of exhaustively examining all the item vectors to identify the top-k items. However, conventional matrix factorization models may suffer from performance degeneration caused by randomly-drawn LSH hash functions, directly affecting the ultimate quality of the recommendations. In this paper, we propose a framework named øurmodel, which factors in the stochasticity of LSH hash functions when learning real-valued user and item latent vectors, eventually improving the recommendation accuracy after LSH indexing. Experiments on publicly available datasets show that the proposed framework not only effectively learns user's preferences for prediction, but also achieves high compatibility with LSH stochasticity, producing superior post-LSH indexing performances as compared to state-of-the-art baselines.
BibTeX
@inproceedings{le2020stochastically,
  author = {Dung D. Le and Hady W. Lauw},
  title = {{Stochastically Robust Personalized Ranking for LSH Recommendation Retrieval}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=h84z5e6YrBw9},
}
Figure