Learning to Hash for Recommendation: A Survey

Fangyuan Luo, Yankai Chen, Jun Wu, Tong Li, Philip S. Yu, Xue Liu · 2024

Read Learning to Hash for Recommendation: A Survey by Fangyuan Luo, Yankai Chen, Jun Wu, Tong Li, Philip S. Yu, Xue Liu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03875.txt.

Introduction

Fangyuan Luo and co-authors survey hashing methods for recommendation, a trick that keeps giant platforms fast. Recommender systems must search millions of users and items in a blink, and storing full profiles is heavy. Learning to hash compresses each profile into a short binary code, so matching becomes a quick code comparison.

The survey first lays out the standard two-tower setup used at the recall stage and the two main ways of searching with codes. It then sorts the field by what the codes are trained to do, how they are optimized, and where they are used. Common scoring methods for accuracy and speed are gathered as well. The authors close with the field's open limits and promising next steps, and they point readers to a public index of the methods covered.

Catalog record

CREATORFangyuan Luo, Yankai Chen, Jun Wu, Tong Li, Philip S. Yu, Xue Liu
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03875

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning to Hash for Recommendation: A Survey Fangyuan Luo, Yankai Chen, Jun Wu, Tong Li, Philip S. Yu, Xue Liu Abstract . With the explosive growth of users and items, Recommender Systems are facing unprecedented challenges in terms of retrieval efficiency and storage overhead. Learning to Hash techniques have emerged as a promising solution to these issues by encoding high-dimensional data into compact hash codes. As a result, hashing-based recommendation methods (HashRec) have garnered growing attention for enabling large-scale and efficient recommendation services. This survey provides a comprehensive overview of state-of-the-art HashRec algorithms. Specifically, we begin by introducing the common two-tower architecture used in the recall stage and by detailing two predominant hash search strategies. Then, we categorize existing works into a three-tier taxonomy based on: (i) learning objectives, (ii) optimization strategies, and (iii) recommendation scenarios. Additionally, we summarize widely adopted evaluation metrics for assessing both the effectiveness and efficiency of HashRec algorithms. Finally, we discuss current limitations in the field and outline promising directions for future research. We index these HashRec methods at the repository https://github.com/Luo-Fangyuan/HashRec . DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Information systems Recommender systems 1. Introduction Recommender Systems (RS) ( Zhang et al., 2019 ; Alhijawi and Kilani, 2020 ) play an important role in helping users find relevant and personalized items, which can significantly alleviate the information overload issue. The core idea is to discover a short list of items that are likely to be interacted by users, which is widely applied in modern Internet services, e.g., E-commerce platforms (Taobao ( Gong et al., 2020 ) , Amazon ( Linden et al., 2003 ) ), video-sharing platforms (Kuaishou ( Chang et al., 2023 ) , TikTok ( Zannettou et al., 2024 ) ), social media (Weibo ( Alsini et al., 2021 ) , RED ( Liu et al., 2024 ) ), and so on. With the rapid growth of users and items 1 1 1 Take the Wechat platform as an example, there are 1385 million monthly active users at the end of 2024. Data source from link . , it is challenging to rapidly identify a small number of items from a large item corpus due to stringent response requirements of Internet services. Therefore, the “recall-and-ranking” recommendation architecture has garnered widespread adoption ( Covington et al., 2016 ) , which is shown in Fig. 1 . Specifically, the recall model first takes users’ history as input, and retrieves hundreds of candidate items that are broadly relevant to the user with high precision. Subsequently, the ranking model leverages rich user and item features to compute a preference score for each candidate item. This process produces a finely-tailored list of several dozen recommendations by their preference scores. In contrast, the ranking model only need to score hundreds of candidate items, while the recall model must evaluate and score every item in the entire item corpus. Given the sheer volume of users and items during the recall stage, efficiency has become an urgent problem that needs to be solved immediately ( Paun, 2020 ) . Figure 1. The architecture of industry recommender systems, which includes recall and ranking phase. Specifically, the recall model retrieves hundreds of candidate items from millions of item corpus, and the ranking model presents a list which contains dozens of items sorted in descending order of preference scores. It is obvious that the recall model suffers from serious efficiency issue. To address this issue, the two-tower recall model is widely adopted to balance accuracy and efficiency ( Covington et al., 2016 ) . It consists of a user tower and an item tower. Specifically, the user tower is responsible for producing the real-valued representations (a.k.a. embedding) of users, while the item tower is tasked with generating the real-valued representations of items. In the offline phase, the two-tower recall model generates real-valued representations for both users and items by leveraging historical interactions, content features, and side information. After training, the real-valued representations are stored in the database. In the online phase, the target user’s representation can be directly picked up according to his/her unique ID when he/she logs into the platform. And then, the similarity between the target user and items can be calculated by inner product or cosine similarity of their embeddings. In this sense, the recall can be regarded as a similarity search problem, i.e., finding items similar to the target user. Although the inference cost can be reduced by precomputing the representations, the computational complexity remains high. Given m users and n items, the computational complexity for generating K preferred items for all users is \mathcal{O}(mnf+mnlogK) ( Zhang et al., 2016a ; Lian et al., 2017 ; Zhang et al., 2018a ; Tan et al., 2020 ) , where f is the dimension of the real-valued representations. Therefore, these methods are still computationally expensive and lead to low-efficiency issues when either m or n is large. Intuitive results can be observed from Fig. 2 . As the number of items increases, the storage cost and inference time increase dramatically, based on their real-valued representations. Figure 2. Comparisons on inference time (the left panel) and storage cost (the right panel) between bit operations (hash codes) and floating-point calculation (real-valued) varying the number of items. The experiments are conducted by randomly generating hash codes and real-valued vectors with a length of 64 on 10^{3} users and 10^{3} - 10^{7} items, and we report the average results over 10 repetitions. One promising solution for improving efficiency is Learning to Hash (L2H), whose core idea is mapping data points in the vector space into Hamming space, and then the real-valued representations can be replaced by compact hash codes (a.k.a binary codes). L2H methods have been intensively studied in many fields, such as Computer Vision (CV), telecommunication, computer graphics, etc., for several decades ( Knuth, 1998 ) . Existing L2H methods can be categorized into two types: data-independent and data-dependent. As a representative of data-independent method, Locality-Sensitive Hashing (LSH) has attracted widespread attention ( Gionis et al., 1999 ) . The key component of LSH is a hash function, which generate identical code for nearby data points in the original vector space with high probability. Therefore, a lot of researchers have devoted efforts to designing random hash functions that satisfy the locality sensitivity property for various distance measures ( Broder, 1997 ; Broder et al., 1997 ; Charikar, 2002 ; Datar et al., 2004 ; Motwani et al., 2007 ; O’Donnell et al., 2014 ; Dasgupta et al., 2011 ) . Other researchers develop better search schemes ( Gan et al., 2012 ; Lv et al., 2007 ) , or provide a similarity estimator with small variance ( Li et al., 2006a ; Ji et al., 2012 ; Li et al., 2012 ; Ji et al., 2013 ) , or design faster computation of hash functions ( Li et al., 2006b ; Shrivastava and Li, 2014 ) . Although LSH can provide asymptotic theoretical properties leading to performance guarantees, they are suffering from long encoding problem. To this end, some researchers suggest leveraging machine learning techniques to produce more effective hash codes ( Cayton and Dasgupta, 2007 ) . Their goal is

Read the complete text