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.
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).
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