Trading Hard Negatives and True Negatives: A Debiased Contrastive Collaborative Filtering Approach

1 Introduction

Collaborative Filtering (CF) [Pan et al., 2008] is a standard approach to deal with implicit feedback (e.g., click, watch, purchase, etc.) in recommender systems, wherein observed user-item interactions are assigned with positive labels, and the rest are unlabeled. A common practice in CF methods is to uniformly draw negative instances from the unlabeled portion, a.k.a. negative sampling [Chen et al., 2017], and then use both positive and negative instances for training, as has been adopted by existing point-wise [Mnih and Salakhutdinov, 2008] or pair-wise [Rendle et al., 2009] approaches. However, this CF paradigm is considered as insufficient to provide informative and reliable training signals. Hence, enormous efforts have been made for improving the quality of negative instances for CF-based recommendation.

∗This work was supported by the National Key R&D Program of China [2020YFB1707903]; the National Natural Science Foundation of China [61872238, 61972254], the Shanghai Municipal Science and Technology Major Project [2021SHZDZX0102], and the Tencent Rhino-Bird Renewed Research Program. Xiaofeng Gao is the corresponding author.

Particularly, hard negative mining has shown to be an effective approach, which aims to exploit negative user-item pairs whose embeddings are close yet expected to be far apart [Wu et al., 2017; Park and Chang, 2019], as a means to provide informative training signals. A line of works [Rendle and Freudenthaler, 2014; Chen et al., 2017] fallen into this category attempt to replace the uniform negative sampling distribution by some predefined surrogates, based on certain prior knowledge such as that more frequent items constitutes better negatives [Wu et al., 2019a; Chen et al., 2017]. In contrast, another line of works [Rendle and Freudenthaler, 2014; Park and Chang, 2019] seek to adaptively mine negatives by carefully examining relevance score of user-item pairs, which are generally more effective but often require sophisticated training techniques such as generative adversarial network [Park and Chang, 2019], reinforcement learning [Ding et al., 2019] and bi-level optimization [Shu et al., 2019]. This leads to the first trade-off between efficiency and effectiveness.

On the other hand, the soundness of these works resides on a problematic assumption that "all unlabeled interactions are true negative instances", which is against the actual setting where unlabeled user-item pairs may potentially become positive instances, once the item is exposed to the user. These instances are termed as false negatives. The incorporation of false negatives would provide erroneous supervised signals for training and seriously degrade the performance [Hern´andez-Lobato et al., 2014]. While it may sound attractive to identify and remove these instances, it is challenging to distinguish hard negatives and false negatives, given that both of them have large relevance scores in appearance and auxiliary information is often not available. Few works attempt to address this issue, especially in the context of negative mining for CF. This presents the second trade-off between informative negatives and reliable negatives.

Towards navigating these trade-offs, we propose a new framework named as Hardness-Aware Debiased Contrastive Collaborative Filtering (HDCCF). Specifically, a contrastive loss function is devised in place of conventional point-wise and pair-wise objectives, which will be shown by gradient analysis that can automatically and adaptively concentrate on optimizing hard negatives by contrasting with peers, notably, without relying on complex training tricks. We also devise an efficient sampling strategy that implicitly explores negative instances by incorporating item frequency information, without actually conducting negative sampling. On top of the new hardness-aware objective, we further propose a principled method to eliminate the risk of false negatives. Needless to explicitly distinguish hard and false negatives, this is achieved by directly debiasing the objective, such that its expectation is strictly equivalent to the ideal loss function that resembles sampling under true negative distribution.

There are also several additional novel designs in our framework: 1) It considers both negative users and items to avoid the case where all negative items are relatively discriminative for a specific user, and vice versa; 2) Two auxiliary contrastive losses are introduced to model user-user and itemitem relationship, which could help to obtain more meaningful user and item representations; 3) A neural modulated mechanism is designed that takes a user's diverse preference on different items into account in the loss function. We validate the effectiveness of HDCCF by comparison experiments and ablation studies. The results demonstrate the superiority of HDCCF as well as the effectiveness of its components.

2 ProposedModel

Notations. Let U and I denote a set of users and items, Iu (resp. I ′u ) denote a set of items that user u has (resp. has not) interacted with, Ui (resp. U ′ i ) denote a set of users that item i have (resp. not) interacted with. Observed interaction data are represented by a set of user-item pairs D = {(u, i)}. Unobserved user-item pairs are denoted as D′ = U × I - D. For user u ∈ U, our goal is to recommend a fix-sized set of ordered items Xu ⊂ I ′u .

2.1 Hardness-Aware Contrastive CF

For an observed instance (u, i) ∈ D, we uniformly sample S negative items (resp. users) that have no observed interaction with user u (resp. item i), denoted as N - u ⊂ I ′u (resp. N - i ⊂ U ′ i ), where S is the negative sampling number. Then, the user-item contrastive loss Lu-i is defined as

where f : (u, i) → R is a similarity measure which outputs the relevance score of user u and item i, and τ ∈ R+ is a scalar temperature parameter (omitted in the following for brevity). The F u (resp. F i ) in Eqn. (1) is called negative score for user u (resp. item i), and is formulated as

where both (u, i-) and (u-, i) are unobserved (i.e., unlabeled) instances.

Hardness-Aware Property by Gradient Analysis. To explain the efficacy of the above contrastive loss formulation for hard negative mining, we peer into its gradients with respect to observed and unobserved instances for analysis. Denote the probability of an unobserved instance (u′ , i′ ) being recognized as positive by

Then, the gradients with respect to the relevance score of observed and unobserved instances are computed as

These equations reveal two properties [Wang and Liu, 2021]:

1. For each individual unobserved instance (u′ , i′ ), the gradient is proportional to P(u′ , i′ ) and thus is also proportional to ef(u′ ,i′ )/τ ;
2. The gradient for observed instance is equal to the sum of gradients for all unobserved instances.

These properties have several implications in the context of hard negative mining in CF. First, according to the first property, a harder negative instance with larger relevance score has larger magnitude of gradients, which indicates the loss function could automatically concentrates on optimizing harder negative instances. The hardness level for each negative instance is adaptively updated for each iteration, and could be controlled by tuning temperature τ . Second, the gradient is re-scaled by the sum of relevance scores of peer negative instances, which indicates the hardness for each negative instance is relative to the hardness of peer negatives in the loss function, distinguishing us from pair-wise loss functions. Third, according to the second property, the gradients of negative instances, whose sum is determined by ∂Lu-i/∂f (u, i), are distributed over each negative instance, and thus are not sensitive to label noise, which is known as a limitation of BPR loss. Fourth, by considering two types of negative instances for every (u, i) in Eqn. (1) (i.e., negative items and users), we could jointly mine negative instances from two facets and avoid the case when all negative items (resp. users) are easily discriminative for an individual user (resp. item).

User-User and Item-Item Relations. Besides modeling user-item interactions, we further extend the advantage of negative mining to neighbored users (i.e. a pair of users (u, u′ ) that have interactions with the same item) and neighbored items [Sarwar et al., 2001; Kabbur et al., 2013] by proposing two auxiliary contrastive losses. We uniformly sample P positive items (resp. users) for user u (resp. item i), denoted as N + u (resp. N + i ), where P is the positive neighbor sampling number. The auxiliary loss function Lu-u is formulated as:

where N - u and N - i are the same as those used in Eqn.(1), and Li-i could be defined in the same way. Then, the final loss function L is the weighted sum of three terms:

where λu and λi are weights to balance the importance for each type of relation.

Neural Modulated Similarity Model. For the similarity function f(u, i), one could use dot-product [Koren et al., 2009], Euclidean distance [Hsieh et al., 2017] or parameterize it with neural network [He et al., 2017]. Particularly in this paper, we propose to use the following neural modulated similarity model:

where pu, qi ∈ Rd are user and item embeddings, and mui ∈ Rd+ is a modulating vector for element-wise scaling, which is computed by

where eu, ei ∈ Rd are user and item latent factors, ⊙ denotes Hadamard product, ∥ denotes vector concatenation, and g : R3d → Rd is a neural network. The key insight is that using a fixed user embedding may fail to represent one's diverse preference on distinct items in the loss function (items may also have multiple attributes that could attract a user), especially in our case where the objective incorporate more candidates of items. To mitigate this issue, our design could capture a user's varying preferences by allowing more flexible representations, which could improve the discrimination ability of the model, empirically verified by ablation studies.

2.2 Sampling Strategy

The sampling approach mentioned in last subsection samples S negative users/items and P positive users/items for each target observed user-item pair. Suppose the batch size is M, there are additional 2M × (S + P ) (where M ≈ S, S ≫ P ) users/items to be sampled for each iteration besides target user-item pairs, which is impractical when scaling the training. Alternatively, we adopt a sampling strategy that uses the positive users (resp. items) from other observed instances in the same mini-batch as the negative users (resp. items) for the target instance. Formally,

where N - uk and N - ik are multi-sets, which allow multiple appearances of the same item or user in the set. In this way, the negative instance number is enlarged from S to P × (M - 1) with lower sampling overhead (from 2M × (S + P) to 2M × P). We also highlight that such sampling strategy is free of explicit negative sampling.

Frequency-Aware Properties. To further shed lights on HDCCF's hard negative mining capability and its relation with frequency-based sampling methods, we investigate on: for a specific positive user-item interaction (u, i) in a minibatch, 1) the number of times a negative item i′ (resp. u′ ) appears in user-item contrastive loss, denoted as nu-i i′ (resp. nu-i u′ ) and 2) the number of times a negative item i′ (resp. u′ ) appears in auxiliary contrastive losses, denoted as ni-i i′ (resp. nu-u u′ ).

Proposition 1. The expectation of nu-i i′ is proportional to the number of times this item appears in interaction dataset D, i.e., nu-i i′ ∝ |Ui′ |. This property holds true for user u′ in Lu-i. Formally we have

where the observed interaction (u, i) is sampled from D with distribution po (u, i), and the neighbored item i+ is sampled from Iu with distribution pou (i+).

Proposition 2. The expectation of ni-i i′ is also proportional to |Iu′ |. This property holds true for user u′ in user-user contrastive loss Lu-u. Formally we have

The proof of these propositions is shown in the appendix. As an observation, both E[nu-i i′ ] and E[ni-i i′ ] are proportional to |Ui′ |, which indicates that such sampling strategy is essentially frequency-aware, which enforces the loss function to concentrate on more frequent (popular) items. Since popular items are treated as harder negative instances [Chen et al., 2017; Wu et al., 2019a], such sampling strategy implicitly agrees with the negative mining efficacy of HDCCF.

2.3 Debiased Contrastive Loss

As mentioned before, a user-item pair (u, i-) that we regard as a negative instance is potentially a positive interaction (i.e., false negative instance). The existence of false negative instance could introduce bias in the training signals, and hence may cause sub-optimal results. Particularly, in our case, there are two types of false negative instances: 1) The user-item pair is an observed instance, i.e., (u, i-) ∈ D; 2) Though (u, i-) is unobserved, the interaction will occur once i- is exposed to u. In a similar spirit with [Robinson et al., 2021] that considers a simpler case (without the first type of false negatives and user-user/item-item losses) in the general contrastive learning setting, we propose to eliminate the effects of false negatives by first formulating the expected loss function and then devising unbiased versions of Eqn. (1) and Eqn. (5) without violating their hardness-aware properties.

Formulation of Expected Loss Function. Our analysis mainly focus on the user side for brevity, while the same also applies to the item side. Given an item i, suppose a negative user u- is drawn from U ′ i with a negative sampling distribution pi(u-), i.e., a uniform distribution. Drawing from this distribution may either yield a false negative instance or a real negative instance. Suppose their probabilities are ω+ u and ωu (i.e., 1 - ω+ u ) respectively. To investigate on the formulation of expected loss function, we denote p+i (u-) (resp. p-i (u-)) as the sampling distribution for false (resp. real) negative instance, which are unknown for us. The marginalization of the negative sampling distribution induces a decomposition form pi(u′ ) = ω+ u ·p+i (u′ )+ωu ·p-i (u′ ). Reorganizing it yields the following expression for real negative sampling distribution

Equipped with these notations, we can formulate the ideal optimization objective for Lu-i as

where Q is constant to facilitate the analysis. By comparison between the original formulation of optimization objective in Eqn. (1) and the expected objective in Eqn. (13), we immediately notice the bias essentially stems from the underlying negative sampling distribution. Eliminating the effects of false negatives boils down to approximating the ideal optimization objective using biased observations in datasets. This is challenging due to the existence of two types of false negatives as stated before, and the intractability of the real negative sampling distribution.

Modification of Eqn.(1) Toward eliminating the effects of false negatives, we proceed to modify both formulations of Eqn. (1) and Eqn. (5) such that they agree with the ideal optimization objective. Specifically, the debiased user-item contrastive loss can be formulated as:

where ˜ F u (N - i ,N + i ) and ˜ F i (N - u ,N + u ) are debiased negative scores for negative users and negative items respectively, and the former one is defined as:

where πu 0 (u-, i), πu 1 (u+, i) ∈ R are constants w.r.t. |N - i |, |N + i | and ω+ u . Their exact formulations will be given in the appendix. By replacing u by i, we can get ˜ F i (u, i, N - i ,N + i ) in the same way.

Theorem 1. Equation. (14) is an unbiased estimation of the ideal user-item contrastive loss where negative instances are drawn from the real negative distributions p-i and p-u .

The proof is shown in appendix. To prevent negative values in the logarithm, we can constrain the negative scores to be greater than its theoretical lower bound in practice

Modification of Eqn.(5) In the similar spirit, we develop unbiased formulations for user-user and item-item contrastive losses Lu-u and Li-i in the following forms

Du-u is a set of observed neighbored users. By replacing u by i, we can get ˜ Li-i in the same way.

3 RelatedWorks

Negative mining plays an important role in CF approaches, with significant influences on the recommendation performance [Chen et al., 2017; Rendle et al., 2009]. A highquality negative instance should satisfy: 1) It should be hard for model to discriminate, so as to provide useful information for training [Wu et al., 2017]; 2) It should be a reliable negative instance sampled from the distribution of true negatives, rather than those erroneously recognized as negatives [Hern´andez-Lobato et al., 2014]. Most existing works on hard negative mining [Ding et al., 2019; Ding et al., 2018; Park and Chang, 2019] either learns the sampling distribution with a separate model, or generates negative instances with adversarial training. Despite of the promising results, they often require complex designs, architectures, or side information such as user's "view" behavior which is not always available [Ding et al., 2018]. Besides, the risk of false negative instances are overlooked in these works. Deviating from those works, we devise a hardness-aware loss function that can automatically detect hard and reliable negatives.

Existing optimization objectives in CF approaches could be roughly categorized into point-wise [Mnih and Salakhutdinov, 2007], pair-wise [Rendle et al., 2009] and list-wise [Wu et al., 2018]. The most relevant approaches are based on listwise, which also consider multiple instances in the loss function. However, state-of-the-art list-wise approach [Wu et al., 2018] based on a permutation probability only optimize the upper bound rather than the original negative log-likelihood. Another related work in CF [Chen et al., 2020] that is also free of negative sampling essentially relies on a pair-wise objective with predefined frequency-based weight. Collaborative filtering has been extensively studied in other recommendation situations, e.g., social recommendation [Ma et al., 2008; Wu et al., 2019b], sequential recommendation [Kang and McAuley, 2018; Wu et al., 2021], multi-task learning [Ma et al., 2018; Yang et al., 2022], etc. While our paper mainly focuses on the general setting where only the user-item interactions are assumed as input, the proposed methodology can be trivially extended to other cases to incorporate more information.

4 Experiments

Datasets. We perform extensive experiments on three publicly accessible datasets from various domains with different sparsities. MovieLens [Harper and Konstan, 2015] is a widely adopted benchmark dataset for collaborative filtering. We use two versions, namely MovieLens(ML)-100K and MovieLens(ML)-1M. Yelp is a dataset of user ratings on businesses, and we use the filtered subset created by [He et al., 2016] for evaluation. Gowalla [Cho et al., 2011] is collected from a popular location-based social network, which contains users' check-in history with time spanning from February 2009 to October 2010. Each user's interactions are sorted by the timestamps ascendingly. Then the testing data (resp. validation data) comprise the last (resp. second to last) interacted item of each user, while the remaining are used as training data. The statistics of filtered datasets are given in Table 2.

Evaluation Protocol and Metrics. Following [He et al., 2017; Tay et al., 2018; Rendle et al., 2009], we adopt the leave one out protocol for model evaluation. We evaluate the ranking performance of the proposed model based on two widely used metrics: Hit Ratio at K (HR@K), and Normalized Discounted Cumulative Gain at K (NDCG@K).

Competitors. We consider nine baseline models for collaborative filtering, including four classic collaborative filtering models (PMF [Koren et al., 2009], BPR [Rendle et al., 2009], SVD++ [Koren, 2008], NeuMF [He et al., 2017]), a nonsampling approach ENMF [Chen et al., 2020] and two hard negative mining methods (IRGAN [Wang et al., 2017], SDGAR [Jin et al., 2020]).

4.1 Performance Comparison

We report experiment results of HDCCF and other comparative models in Tab. 1. As we can see, the proposed HDCCF consistently outperforms other comparative methods and achieve state-of-the-art results w.r.t. different metrics throughout three dataset. Specifically, HDCCF on average achieves 4.08% improvement for HR@10, 7.61% improvement for NDCG@10 and 6.21% improvement for NDCG@50. The results demonstrate that HDCCF is a powerful approach for recommendation in implicit feedback. There are some other findings. First, four classic methods (i.e., PMF, BPR, SVD++, NeuMF) have the worst performance, which implies the important role of negative mining on promising recommendation performance. Second, SVD++ has better performance than PMF on average since it considers user neighbor information while PMF fails to do so, which also justifies the design of our auxiliary losses. Third, HDCCF outperforms adversarial hard negative mining methods, which demonstrate the effectiveness of HDCCF for mining reliable and hard negative instances with more simple and flexible designs.

4.2 Ablation Study

We conduct a series of ablation studies to investigate the necessities of some key components in our model and how these components contribute to the overall results.

Debiased Contrastive Losses. We compare the performance of HDCCF and five variants of it with simplified loss functions by removing or replacing the contrastive losses. Specifically, we have two findings in Fig. 2. First, our HDCCF consistently outperforms the variants of HDCCF which remove ˜ Li-i (w/o-I), ˜ Lu-u (w/o-U) and both auxiliary contrastive losses (w/o-U&I), respectively. This is because ˜ Li-i and ˜ Lu-u can take the advantage of hard negative mining to fully exploit the relations of neighbored users and items. Second, the variant of HDCCF that only preserves the user-item contrastive loss (w/o-U&I) also consistently outperforms the variant that replaces the contrastive loss by BPR loss (BPR+). This result validates that the good recommendation attributes to the proposed loss functions rather than other model designs. Third, HDCCF outperforms the biased variant by a large margin, which demonstrate the importance of removing false negative instances especially in our case where false negatives could be either observed or unobserved.

Modulated Similarity Model. We compare HDCCF with a variant with a fixed modulating vector, i.e., an all-ones modulating vector. Specifically, we visualize the distributions of user-item relevance scores (which are normalized to range 0 to 100) for two models on ML-100K dataset in Fig. 3. As shown in the figure, the modulated similarity model pushes the upper bound of negative instances' relevance scores to the left, and the lower bound of positive instances' relevance scores to the right (which is more significant than the former one). Consequently, the intersecting interval (which is filled with red shade in the figure) of our modulated similarity model is considerably smaller than the unmodulated variant. This empirical result conforms to the conjecture that the modulation mechanism is helpful to distinguish positive interactions against negative instances by using a more flexible user and item representations.

4.3 Hyper-parameter Analysis

Impact of BiasCorrectionProbabilities. Two bias correction probabilities ω+ i and ω+ u are introduced in Sec.2.3 and denote the probabilities that items and users sampled from

10

unobserved data are true negative samples. It is intractable to derive the precise values of ω+ i and ω+ u , and they are different across datasets. Therefore, we treat them as hyper-parameters in implementation and here study how these parameters affect the recommendation performance. Figure 4(a)-(d) show HR@10 and NDCG@10 of HDCCF with ω+ i and ω+ u varying from 0 to 0.2 and other hyper-parameters unchanged. As we can see, a certain range of values for ω+ i and ω+ u can correct the sampling bias, while out-of-range ω+ i and ω+ u will harm the recommendation performance.

Impact of Positive Neighbor Sampling Number. For our neighbor sampling strategy, P is the hyper-parameter denoting the number of positive user (or item) neighbors for each interaction in the batch. Intuitively, larger P brings higher time and space costs, but improves the stability of training process. To validate this conjecture, we study how P affects the recommendation performance. Figure 4(e)-(f) show the performance of HDCCF with P varying from 1 to 6 and other hyper-parameters unchanged. As we can see, larger P can bring up improvements for recommendation performance, since it can reduce the variance brought by sampling over observed interactions (which helps to stabilize the training process and alleviate over-fitting) and improve the hard negative mining ability by contrasting with more instances.

5 Conclusion

In this paper, we propose hardness-aware debiased contrastive collaborative filtering framework, which resolves the dilemma of hard negative mining and the reliability of negative instances. Comprehensive experiments and ablation studies on three real-world datasets demonstrate the effectiveness of our framework.