Discrete Listwise Personalized Ranking for Fast Top-N Recommendation with Implicit Feedback

1 Introduction

Top-N recommendation is a fundamental task across many Internet services, which aims at discovering a short list of items that are likely to be interacted by users. However, it is challenging to rapidly identify top-N items from a large corpus due to the stringent response requirement of Web services. Consequently, a "recall-and-ranking" recommendation architecture is widely adopted in industry [Covington et al., 2016]. That is, a scalable recall model first identifies a relatively small set of candidate items, and then a fully-blown ranking model refines the rank list of candidate items. This work mainly concentrates on the recall model that scales well to a large volume of items.

In the recall stage, embeddings of users and items are often pre-computed via matrix factorization (MF) [Koren et al., 2009] or deep neural networks (DNNs) [Zhang et al., 2019] ;

∗Corresponding author.

after that, candidates generation naturally falls into a similarity search problem, i.e. finding top-N similar items queried by a user based on pre-computed embeddings. However, due to the ever-growing volume of items, similarity search has been a major efficiency bottleneck for top-N recommendation. Fortunately, hashing has been shown as a promising solution to fast similarity search [Wang et al., 2012], the core idea of which is encoding real-valued embeddings into binary codes, so that user-item similarities can be efficiently calculated in a Hamming space by bit operations. During the past decade, a surge of efforts have been made in hashing-based recommendation (HR), most of which learn binary codes from explicit feedback (e.g., ratings) [Zhou and Zha, 2012; Zhang et al., 2014; Zhang et al., 2016; Zhang et al., 2018b; Liu et al., 2019; Wu et al., 2020; Luo et al., 2021; Liu et al., 2021; Hansen et al., 2021]. However, their applicability is limited because explicit feedback is fairly expensive to obtain. Hence a recent trend is to perform hash for recommendation with implicit feedback (such as purchasing and clicking) [Zhang et al., 2017; Zhang et al., 2018a; Zhang et al., 2020; Lian et al., 2021], which formulate their learning tasks as Binary Quadratic Programming (BQP) problems and solve them by Discrete Coordinate Descent (DCD) which is the de facto choice for solving BQP problems [Shen et al., 2015]. We refer to the HR schemes using explicit and implicit feedback as the HRex and the HRim respectively, and the latter is our focus in this work.

However, existing HRim schemes mainly focus on optimizing a pairwise (even a pointwise 1 ) objective, which is suboptimal for personalized ranking. It is well-known that the benchmark metric for ranking quality is Average Precision (AP) (or its generalized variant, Normalized Discounted Cumulative Gain (NDCG), which includes non-binary relevance judgements) 2 [Brown et al., 2020]. However, the core idea of pairwise objective is inconsistent with AP. Illustrated by Figure 1, given two rank lists A and B, A achieves better AP than B (0.7 vs 0.58), but B is with smaller pairwise error than A (2 vs 3). An explanation is that AP imposes larger penalty on the top-ranked negative items, while pairwise loss equally treats all negative items in the rank list.

1 Given implicit feedback, pointwise objective often performs worse than pariwise one in terms of top-N recommendation tasks [Rendle et al., 2009].

In this paper, we propose a novel HRim approach, dubbed Discrete Listwise Personalized Ranking (DLPR), which optimizes AP under discrete constraints for better recall accuracy. Due to the sorting function used by AP, DLPR cannot be formulated as a BQP problem. Consequently, its optimization, e.g. with DCD, is notoriously difficult. To this end, we develop an alternative optimization algorithm that can directly learn binary codes in a relaxed continuous solution space. Theoretical analysis shows that the optimal solution to the relaxed continuous optimization problem is the same as that of the original discrete DLPR problem. Our code and supplementary file are available at https://github.com/LFY123456/DLPR.

Specifically, our contributions are briefly summarized as:

• We propose a novel DLPR model for better preserving the listwise user-item relationship while guaranteeing recommendation efficiency. To the best of our knowledge, this is the first work to perform hashing technique on optimizing AP for top-N recommendation.
• We devise an efficient algorithm for solving DLPR, and its convergence is rigorously guaranteed.
• Extensive experiments on two real-world datasets demonstrate that DLPR consistently outperforms stateof-the-art HRim methods.

2 RelatedWork

In this section, we mainly review related work on HR. For comprehensive reviews of hashing techniques, please refer to [Wang et al., 2016; Wang et al., 2018a].

The first hashing solution to recommendation is proposed by [Zhou and Zha, 2012], named Binary Code for Collaborative Filtering (BCCF), which conducts Iterative Quantization (ITQ) to generate binary codes from rotated real latent representations. To derive compact binary codes, the balanced constraints are imposed on the real latent representations. However, according to [Zhang et al., 2014], hashing only preserves similarity between users and items rather than inner product based preference, leading to the decrease of recommendation accuracy. Thus, they proposed a Preference Preserving Hashing (PPH) method to preserve users' preference over items. These work can be summarized as two-stage method which first learn real-valued latent features for users and items and then perform quantization on them to get hash codes. However, two-stage methods suffer from a large quantization loss according to [Zhang et al., 2016].

2 Given binary judgements, NDCG is almost the same with AP, except that they utilize different discount functions.

Direct binary codes learning is becoming popular in order to decrease quantization loss, called One-stage Learning (OL). In detail, OL strategy first formulates learning objectives as BQP problems and then solved by DCD. To learn informative and compact codes, balanced and de-correlated constraints are imposed on discrete optimization process [Zhang et al., 2016]. A few fellow-up studies along this line learn binary codes for fast recommendation [Liu et al., 2019; Wu et al., 2020; Luo et al., 2021; Liu et al., 2021; Hansen et al., 2021]. Note that these methods are deployed in explicit scenarios, i.e., HRex methods, where explicit feedbacks are expensive to obtain. Hence, some studies turn to optimize pointwise or pairwise loss in implicit scenarios aiming to achieve better top-N recommendation accuracy, which give birth to HRim methods [Zhang et al., 2017; Zhang et al., 2018a; Zhang et al., 2020; Lian et al., 2021]. However, the learning objective of HRim shows the inconsistency with evaluation criterion AP which is the benchmark metric for ranking quality. Thus, current HRim methods are still sub-optimal for top-N recommendation.

3 Preliminaries

Throughout this paper, we use bold uppercase and lowercase letters as matrices and vectors, respectively. All of vectors in this paper denote column vectors. Non-bold letters represent scalars. We denote tr(·) as the trace of a matrix. In this work, we focus on optimizing AP under discrete constraints based on matrix factorization (MF) for top-N recommendation.

Let Y ∈ {0, 1}m×n denote the implicit feedback matrix, where the element yui indicates whether user u has interacted with item i (1) or not (0). MF associates each user and item with a real-valued vector of latent features. Supposing pu ∈ Rf and qi ∈ Rf are the uth user vector and the ith item vector, respectively, MF estimates the interaction ˆ yui as the inner product of pu and qi:

Based on user u's preference over the items, then we can generate a recommendation list πˆyu = sort(ˆyu) by sorting the items in a descending order according to their predicted scores ˆyu. Then, the AP score of the list is defined as:

where πˆyu (k) denotes the item at rank k.

4 Discrete Listwise Personalized Ranking

We first present the learning objective of DLPR and then describe its detailed optimization process, which is the key technical difficulty of this paper. Finally, we give the convergence analysis of our proposed DLPR algorithm.

4.1 Model Formulation

In this paper, we are interested in hashing users and items into binary codes for fast recommendation, where user-item similarity calculation can be efficiently conducted in Hamming space. Denote B = [b1, b2, · · · , bm] ∈ {±1}f×m and D = [d1, d2, · · · , dn] ∈ {±1}f×n respectively as f-length user and item hash codes, the Hamming similarity between bu and di is defined as:

Substituting Eq.(3) into Eq.(2), the objective of our proposed method can be formulated as:

Due to discrete constraints, optimizing Eq.(4) is a highly challenging task as illustrated in Section 1. Thus, we introduce a new learning objective that allows DLPR to be solved in a computationally tractable way. The basic idea is to transform Eq.(4) into a solvable concave optimization problem with the relaxed continuous solution space. As we know, the optimal solution of a concave function is necessarily located at a boundary of the convex set [Rockafellar, 1997].

To achieve this, we first relax the discrete solution space DB := {B : B ∈ {-1, 1}f×m} and DD := {D : D ∈ {-1, 1}f×n } to its convex hull PB := {B : B ∈ [-1, 1]f×m} and PD := {D : D ∈ [-1, 1]f×n } respectively. Thus the objective function is continuous while nondifferentiable since the computation of AP relies on the sorting operator. Therefore, we replace the sorting function by a softmax function inspired by [Grover et al., 2019] to smooth the sorting operator which enable direct optimization of AP.

Proposition 1. Denote s = [s1, s2, · · · , sl]T be a real-valued score vector of length l and As be the matrix of absolute pairwise differences of the elements of s such that As[i, j] = |si - sj|. Let πs be the permutation of sorting s in a descending order. Then the permutation matrix Z(πs) can be represented as follows:

Proof. See A.1 in supplementary file.

Since the argmax operation is non-differentiable which prohibits the direct use of Eq.(5) for gradient computation. Instead, we replace the argmax operator with softmax to obtain a continuous relaxation ˜Z(πs,τ) . In particular, the ith row of ˜Z(πs,τ) is given by:

where τ > 0 is a temperature parameter, which controls the approximation degree between softmax operation and argmax operation. Substituting ˜Z(πs,τ) i into Eq.(4), the objective function of DLPR can be formulated as:

Specifically, there is a subtle connection between the true AP and its smooth version ˜ AP , described by Proposition 2.

Proposition 2. The ˜ AP is approximately equal to the AP, and the proximity between them depends on the value of τ . If τ → 0+, the˜ AP is a tight approximation to AP, vice versa.

It is worth noting that our model is deployed in the continuous space and directly learn optimal discrete solution based on thought that the optimal solution of a concave function is necessarily located at a boundary of the convex set. More importantly, theoretical proofs show that the optimal discrete solution to Eq.(7) is exactly that of original discrete problem.

4.2 Optimization

We employ alternating optimization strategy to solve two subproblems for DLPR model in Eq.(7), taking turns to update each of B and D, given the other fixed. Next, we elaborate on how to solve each of the subproblems.

B-subproblem

In this subproblem, we aim to optimize B with fixed D. Specifically, we propose to use Graduated NonConvexity and Concavity Procedure (GNCCP) [Liu and Qiao, 2014; Wang et al., 2018b] which obtains optimal discrete solution from the continuous vector space, to approximately solve the subproblem as follows:

Actually, Eq.(8) realizes the convex and concave relaxation of Eq.(7) by knobbing the parameter ζ. With the decreasing of ζ from 1 to -1, implying that the objective function Lζ(B) becomes gradually from tr(BT B) to L(B) (graduated nonconvexity) and finally to -tr(BT B) (graduated concavity). For each currently fixed ζ, Lζ(B) can be minimized by the Frank-Wolfe algorithm [Marguerite Frank, 1956], using the minimum of the previous Lζ(B) as the starting point. In detail, we update B according to:

where the gradient ∇Lζ(B) takes the form:

And the linear programming problem in Eq.(9) can be solved based on the following rule: B∗ = -sgn(∇Lζ(B)). Next, we conduct linear search to find an update direction to optimize B until it converges. Then iteratively, given the optimization step d, we find a local minimum of Lζ-d(B) given a local minimum of Lζ(B) by performing a local optimization of Lζ-d(B) starting from the local minimum of Lζ(B). Repeating this iterative process for d small enough, we obtain a path of solutions {B∗ (ζ)} where B∗ (ζ) is a local minimum of Lζ(B) for all ζ ∈ [-1, 1]. We finally output B∗ (ζ ∗ ) ∈ D as an approximate solution of Eq.(7), where B∗ (ζ ∗ ) is the local minimum of Lζ ∗(B) and ζ ∗ makes the function Lζ ∗(B) become a concave function.

Proposition 3. The optimal solution B∗ (ζ ∗ ) of L in Eq.(8) is exact that of the original discrete problem of Eq.(4), where ζ ∗ makes the objective Lζ ∗(B) become a concave function.

Proof. See A.3 in supplementary file.

D-subproblem

In this subproblem, we update D with fixed B by solving the following problem:

For the conciseness, we do not give the derivation of the updating rule which could be derived in a similar way just like in B-subproblem.

4.3 Algorithmic Analysis

The convergence of the proposed DLPR model is guaranteed by the following proposition.

Proposition 4. (Convergence of DLPRmodel). The sequence {B(ζ),D(ζ)} monotonically decreases the objective function L of Eq.(7); the objective function has a lower bound; the solution sequence {B(ζ), D(ζ)} converges.

Proof. See A.4 in supplementary file.

5 Experiments

5.1 Experimental Settings

Datasets

Two real-world datasets are used in our experiments, namely CiteULike and Amazon, where the Amazon Book dataset is converted into implicit feedback by treating ratings of higher than each user's average score as "like" preference. In addition, we filter users who have less than 10 interactions due to extreme sparsity. Table 1 summarizes the filtered datasets.

Baselines

We compare DLPR with four state-of-the-art HR methods:

• DCF [Zhang et al., 2016] is a canonical one-stage HRex method whose objective function is rating prediction instead of personalized items ranking.
• DPR [Zhang et al., 2017] is an HRim method which optimizes a surrogate AUC loss.
• DRMF [Zhang et al., 2018a] is an HRim method which optimizes the quadratic upper bound of logistic loss based on pairwise preferences, and introduce self-paced learning to optimization procedure.
• DMF [Lian et al., 2021] is an HRim method which optimizes quadratic upper bound of logistic loss.

To verify whether each component adopted by DLPR is useful or not, several variants of DLPR are included:

• DLPR-MQ (Median Quantization) conducts median quantization on the real-valued representations learned by LPR which is the real-valued version of DLPR.
• DLPR-PL (Pairwise Loss) replaces AP loss with pairwise loss. Remaining components are same as DLPR.
• DLPR-PL-OL (One-stage Learning) is a further degenerated version of DLPR-PL, which adopts one-stage method to learn hash codes by optimizing pairwise loss.

Evaluation Protocols

To evaluate the performance of our method, we adopt the leave-one-out evaluation, which has been widely used in literature [Zhang et al., 2017; He et al., 2017]. We exploit four widely-used metrics in ranking evaluation: Mean Average Precision (MAP), Normalized Discounted Cumulative Gain (NDCG), Recall and Mean Reciprocal Rank (MRR).

Parameter Settings

We employ grid search for parameters tuning and best results are reported. We test the temperature parameter τ in the range of {10-1 , 100 , · · · , 103 } and the optimization step d in the range of {0.01, 0.02, 0.05, 0.1, 0.2}. For baselines, we use the original implementation as released by the authors.

5.2 Comparison with State of the Arts

We first compare DLPR with the four baselines on the two datasets, and the corresponding quantitative results are shown in Figure 2 and Table 2. Specifically, several observations are drawn from the experimental results:

• Overall, listwise HRim method (DLPR) and pairwise HRim methods (DRMF and DPR) consistently outperform pointwise HR methods (DCF, DMF). Such an observation illustrates the importance of listwise and pairwise loss for binary codes learning in implicit scenarios. Between the two pointwise HR methods, DMF consistently outperforms DCF. That's because DMF learns

hash codes by optimizing logistic loss which is closer to the ranking task than squared loss DCF optimizes. In addition, we find DCF shows worse recommendation performance on CiteULike, which is due to the fact that CiteULike is an implicit dataset while DCF learns hash codes by optimizing squared loss.

• DLPR demonstrates consistent improvements over stateof-the-art pairwise HRim methods (DRMF and DPR) on two datasets in terms of MAP@K. The performance improvements are attributed to the benefits of joint effect of the proposed smooth AP loss and the corresponding optimization algorithm. Meanwhile, DLPR also obtains higher MRR and Recall@10 than the two pairwise methods, which verifies the fact optimizing more information metric, like AP, can boost the performance of the less informative metrics, such as Recall and MRR [Li et al., 2021]. In addition, our method achieves significant performance improvement on NDCG@10 since NDCG is similar with AP and optimizing AP is actually optimizing NDCG. By comparing DRMF and DPR, we find

DPR shows better performance than DRMF since DPR directly optimizes surrogate AUC objective.

5.3 Ablation Experiments

We further compare DLPR with its three degenerated variants (i.e., DLPR-PL, DLPR-MQ and DLPR-PL-OL) for demonstrating the effectiveness of key components adopted by DLPR. Figure 3 and Table 2 respectively show MAP@K, NDCG@10, Recall@10 and MRR of such four methods.

Effect of the Smooth AP Loss

Comparing DLPR with DLPR-PL, which are solved based on the same optimization algorithm, we find that DLPR significantly outperforms DLPR-PL. It verifies that the proposed AP loss is beneficial in binary codes learning. Moreover, it is surprising that DLPR-MQ achieves much better performance than DLPR-PL-OL. Note that DLPR-MQ performs crude median quantization to obtain hash codes, while DLPR-PL-OL does that via the one-stage learning method. It again confirms that the importance of the consistency between learning objective and evaluation criterion for recommendation.

Effect of the Alternating Optimization Strategy

Comparing DLPR-PL with DLPR-PL-OL, which are with the same objective, we observe that DLPR-PL consistently outperforms DLPR-PL-OL. It verifies the superiority of our proposed optimization strategy over the popular one-stage learning paradigm that is widely used in HR. In contrast with one-stage learning, the proposed optimization strategy can directly obtain the discrete solution in the continuous vector space, which is helpful to enhance the representation ability of DLPR. Besides, we also find a large performance gap between DLPR and DLPR-MQ, which further demonstrates the superiority of our proposed optimization strategy over the traditional two-stage learning technique.

We also conduct efficiency comparison between DLPR and its real-valued version to show the superiority of our method, whose details are shown in B.1 of the supplementary file.

6 Conclusion and FutureWork

Motivated by the fact that current HRim schemes fail to align the learning objective with AP metric, we proposed DLPR that is the first personalized ranking method to optimize AP

under discrete constraints. Specifically, DLPR directly learns binary codes in a relaxed continuous solution space, and we provide an analysis to verify that the optimal solution of the relaxed continuous optimization problem is same as that of the original discrete problem. Extensive experiments verify the superiority of DLPR over several competitive baselines.

To make use of the representation ability of deep neural networks, [Wang et al., 2020] sought the approximate solution to discrete optimization problem within the deep learning framework. Towards this line, we will explore the discrete listwise deep recommendation models to further improve the performance of HRim techniques.

Acknowledgements

This work was supported by the Fundamental Research Funds for the Central Universities (No. 2021YJS038), the National Nature Science Foundation of China (No. 62076021) and the Beijing Municipal Natural Science Foundation (No. 4202060).