Dimension Independent Mixup for Hard Negative Sample in Collaborative Filtering

Collaborative filtering aims to predict user’s preferences based on users’ historical interactions. It has been shown as an effective and powerful tool (Mao et al., 2021; Chae et al., 2018) for RecSys. With implicit feedback, we have a set of users $\mathcal{U}=\{u_{1},u_{2},...,u_{\left|\mathcal{U}\right|}\}$, a set of items $\mathcal{I}=\{i_{1},i_{2},...,i_{\left|\mathcal{I}\right|}\}$, and the observed user-item interactions $\textbf{R}\in\mathbb{R^{\left|\mathcal{U}\right|\times\left|\mathcal{I}\right|}}$, where $R_{u,i}=1$ if user $u$ has interacted with item $i$, or $R_{u,i}=0$ otherwise. Learning from historical interactions, current advanced CF-based methods (Wang et al., 2019; He et al., 2020) learn an encoder function $f(\cdot)$ to map each user/item into a dense vector embedding, i.e., $f(u),f(i)\in\mathbb{R}^{d}$, where $d$ is the dimension of vector embedding. The predicted score from $u$ to $i$ is then calculated as the similarity of two vectors (e.g., dot product similarity, $R_{u,i}=f(u)^{\top}f(i)$). Then these methods rank all items based on the prediction score and select the top $k$ items $\{i_{1},i_{2},...,i_{k}\}$ as recommendation results for each user.

In real-life applications, users can only interact with a limited number of items, which leads to the data sparsity problem (Zheng et al., 2019). To alleviate the problem, the most advanced CF-based models (He et al., 2020; Wu et al., 2021; Zhang et al., 2023) explicitly utilize high-order connections by representing the historical interactions as a user-item bipartite graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\mathcal{U}\cup\mathcal{I}$ and there is an edge $(u,i)\in\mathcal{E}$ between $u$ and $i$ if $R_{u,i}=1$. By utilizing graph neural network (GNN) as the encoder function $f(\cdot)$, these methods learn the representations of user/item embeddings by aggregating information from their neighbors, so that connected nodes in the graph structure tend to have similar embeddings. The operation of a general GNN computation can be expressed as follows:

where $\mathbf{e}_{u}^{(l)}\in\mathbb{R}^{D}$ is $u$’s embedding on the $l$-th layer, $\mathcal{N}_{u}$ is the neighborhoods of $u$, $\mbox{AGG}^{(l)}(\cdot)$ is a function that aggregates neighbors’ embeddings into a single vector for layer $l$, and $\oplus$ combines $u$’s embedding with its neighbor’s information. AGG$(\cdot)$ and $\oplus$ can be simple or complicated functions. Item is calculated in the same way.

After stacking $L$ layer GNN convolution, we can obtain $L$ user/item embedding from different GNN layers. Take the user as an example; we will obtain $(\mathbf{e}_{u}^{(1)},\mathbf{e}_{u}^{(2)},...,\mathbf{e}_{u}^{(L)})$ for each user after the aggregation. $\mathbf{e}_{u}^{(l)}$ encodes the information within $l$-hop neighborhoods, which provides a unique user representation with local influence scope. A pooling function (e.g., attention, mean, sum) is used to combine them together $\mathbf{e}_{u}=\text{Pool}(\mathbf{e}_{u}^{(1)},\mathbf{e}_{u}^{(2)},...,\mathbf{e}_{u}^{(L)})$.

The observed implicit feedback in RecSys only indicates the user’s positive interest. Training with only positive labels would cause the model degradation without the ability to distinguish different items. Thus, the training of CF-based models involves the negative sampling procedure to provide the negative signal. The corresponding training method trains the model to give higher scores to observed interactions while lower scores to negative sampled interactions. The most renowned is pair-wise BPR loss (Rendle et al., 2012):

where $s(u,i)$ is the predicted rating score from $u$ to $i$, and $i^{-}$ is the negative sampled item. The quality of sampled $i^{-}$ critically impacts the model performance. Hard negative samples can effectively assist the model in learning better boundaries between positive and negative items (Ying et al., 2018). In terms of sampling methods, discrete sampling(Rendle et al., 2012; Zhang et al., 2013; Wang et al., 2017; Ying et al., 2018) can be considered as point-wise sampling, which selects negative items from a discrete sample space. Negative sampling based on mixup(Huang et al., 2021; Shi et al., 2022), on the other hand, can be classified as line-wise sampling because this method performs a linear interpolation between two items to obtain a new negative sample along the diagonal line. Both point-wise sampling and line-wise sampling, in fact, do not adequately approximate the positives in the sample space and, therefore, cannot train a more powerful encoder. In this paper, we propose the first area-wise sampling method that greatly extends the sampling area.

The first question to answer in the proposed area-wise negative sampling is how to define the continuous sampling area. The hard boundary definition module is shown in Figure 2(a). It samples a boundary item to define the sampling area. For each interaction $(u,i)$, DINS defines the area by sampling a boundary item $i_{*}$. In each sampling, DINS pre-samples a candidate set $\mathcal{C}=(i_{1},i_{2},...,i_{|\mathcal{C}|})$ to reduce the computation workload as previous researches (Ding et al., 2020b; Zhang et al., 2013). Then DINS selects the item with the highest dot-product with $u$ to define the boundary:

The boundary item $i_{*}$ defines the hard negative area together with the corresponding positive item $i$ in the embedding space. As shown in Figure 1, the hard negative area is defined as the space between $i$ and $i_{*}$. The majority of previous research (Zhang et al., 2013; Ding et al., 2020b; Rendle et al., 2012) samples discrete existing items. While MixGCF (Huang et al., 2021) allows the sampling on continuous space along the diagonal line from $i$ to $i_{*}$, it still leaves the large-volume hard negative area un-explored.

The second question to answer is how to explore the non-diagonal space within the hard negative area and extend the line-wise to area-wise sampling. To achieve this, we propose the novel Dimension Independent Mixup method in Figure 2(b). It enables a dimension independent mix between the boundary item $i_{*}$ and positive item $i$.

A further comparison to the traditional Mixup is shown in Figure 3. Line-wise sampling methods (Huang et al., 2021; Shi et al., 2022) utilize the traditional Mixup to generate a negative item. As shown in Figure 3(a), traditional Mixup synthesizes the negative item via linear interpolation of the positive and boundary items with a unified weight $\alpha$ on all dimensions. With all dimensions having the same linear interpolation, it can only generate a synthetic item falling on the line between the two mixed items in the continuous embedding space. Figure 3(b) shows the proposed Dimension Independent Mixup, which is the core idea to support area-wise negative samples. It mixes the two items dimension independently by calculating specific interpolation weights for different dimensions. It is more flexible and increases the exploration space from a line to the whole hard negative area.

For each interaction $(u,i)$, Section 3.1 samples a boundary item $i_{*}$ to define the sampling area. The mixup for the $d$-th dimension is calculated as:

where $e_{i}^{d}$ is the $d$-th dimension value of $\mathbf{e}_{i}$. $\alpha_{d}$ is the interpolation weight for the $d$-th dimension, which is calculated as :

where $e_{u}^{d}$ is the $d$-th dimension value of $\mathbf{e}_{u}$, and $\beta>0$ is a hyper-parameter to tune the relative weight for the mixup. A larger $\beta$ leads to a smaller $\alpha_{d}$, and $e_{i^{-}}^{d}$ is more similar with positive item. We concatenate the dimensions together to obtain the mixed item:

$\mathbf{e}_{i^{-}}$ is the generated negative item embedding for the interaction $(u,i)$. It can be directly used to calculate the ranking loss in Equation 2. Calculating the mixup weight independently for each dimension extends the exploration area from a line to the whole hard negative area. It greatly improves the final recommendation performance by providing more varied items, as illustrated in Section 4.

We further extend DINS to better support graph neural network (GNN) based collaborative filtering methods (He et al., 2020; Yang et al., 2021). These methods are shown to be effective by explicitly considering the high-order connections and encode user/item high-order neighborhood information into dense vectors. The output of different GNN layers encodes neighborhoods within different hops. Regarding the negative sample, MixGCF (Huang et al., 2021) also proves to be effective when considering different hops of neighborhoods. To utilize the high-order information, DINS samples negative items based on each dense vector extracted by different GNN layers and utilizes a pooling module to obtain the final negative item embedding.

When we utilize GNN as the encoder model $f(\cdot)$, we can obtain one dense embedding from each GNN layer to encode the corresponding neighborhoods’ information. After $L$ layers GNN encoding on the user-item bipartite graph $\mathcal{G}$, we obtain $L$ dense representations for each user $u$ and item $i$:

Following Section 3.1 and Section 3.2, we synthesize a negative item embedding $\mathbf{e}_{i^{-}}^{(l)}$ based on $\mathbf{e}_{u}^{(l)}$ and $\mathbf{e}_{i^{-}}^{(l)}$. Then we obtain the final negative sample via a Pooling function:

where the Pool can be any function pools multiple tensors into a single tensor. For simplicity, we test mean pooling and concatenation functon for all datasets.

The training process of DINS is illustrated step by step in Algorithm 1. The time complexity for each sampling process comes from the three proposed modules. Hard Boundary Definition module takes $O(MD)$, where $M$ is the candidate set budget and $D$ is the dimension size. Dimension Independent Mixup module takes $O(D)$. Thus, the time complexity without considering multi-hop neighbors is $O(MD)$. When considering the multi-hop neighbors, DINS needs an extra sampling procedure for each GNN layer. The total time complexity is then $O(LMD)$, where $L$ is the number of GNN layers. To be noted that, the time complexity is the same as MixGCF, but DINS extends to a much larger exploration space.

We report the overall performance of the six baselines on the three backbones in Table 2. We can have the following observations:

• •

  DINS outperforms all baselines by a large margin on three datasets across three encoders and accomplishes remarkable improvements over the second-best baseline, especially on the Amazon and Alibaba datasets which improved Recall@20 by 23%, and 36.1%, respectively. This further demonstrates the effectiveness of area-wise sampling, as it enhances the performance of not only GNN-based encoders but also non-GNN-based encoders.

• •

  In most cases, the line-wise sampling method (MixGCF) is better than the rest point-wise sampling methods. It shows the advantage of extending exploration space from points to lines.

• •

  DINS exhibits greater improvement on the two datasets of lower density (Alibaba and Amazon), ranging from 8.0% to 36.1%. This highlights DINS’s ability to explore the continuous embedding space and effectively enhance performance on sparse datasets.

In this section, we conduct an ablation study of the three modules of DINS on LightGCN by building $3$ variants. A is built by removing the Hard Boundary Definition module, where we randomly sample a boundary item from the candidate set. B is built by replacing the dimension independent mixup module with the traditional mixup. C is built by removing the multi-hop pooling module by only considering the negative item for the first layer aggregation. Corresponding experimental results are presented in Figure 4. We can have the following observations:

• •

  DINS always performs the best. Removing any module would have a negative effect on the performance. It reveals each part of DINS contributes to the performance.

• •

  Removing the Hard Boundary Definition module (Variant A) results in a substantial drop in performance across the datasets, indicating the importance of maintaining an optimal size for the negative sampling region. A too-small region may lead to the loss of valuable feature information from the negative samples. At the same time, a too-large region hampers the effective fusion of information from the positive samples.

• •

  Compared with the other two modules, changing the dimension independent mixup module to the traditional mixup (Variant B) has a relatively small performance drop. It shows the mixup technique is already powerful by generating negative items in the continuous space. The proposed dimension independent mixup further enhances the improvement, especially on the Alibaba.

• •

  Removing the multi-hop pooling module has a great impact on the performance. It reveals the importance of considering high-order information during the negative sampling procedure. This observation aligns with the finding of MixGCF (Huang et al., 2021).

By observing the data, it can be seen that the area of negative sampling can neither be too large nor too small. According to Equation 4, if the area is too small, the hard negative item is synthesized too close to the positive items and thus the features of the negatives will be lost, while if the area is too far, the features of the positive items cannot be incorporated into the hard negative items at all.

In this section, we focus on how the hyper-parameters ($\beta$, $M$) and the boundary item selection method actually affect DINS.

To answer RQ4: Does DINS really support area-wise hard negative sampling? we conduct a case study for readers to understand the sampling principle behind DINS. Experiments are conducted on the Yelp2018 dataset with LightGCN as the backbone recommender. We train the model with RNS, MixGCF, and DINS for $60$ epochs. For a fixed user-item interaction, we store the embedding of the positive item and the sampled negative item by different sampling methods in each iteration. Then we obtain the averaged positive item representation by mean pooling over all the collected positive item embedding. Then we concatenate the averaged positive item and all collected negative items embedding together and visualize the distribution via t-SNE (Van der Maaten and Hinton, 2008). For better visualization, we move the positive item to the center of the visualization by subtracting all the reduced $2$-d embedding from the reduced positive item embedding.

The visualization is shown in Figure 7. We draw a circle (with a radius represented by $R$) to show the farthest sampled negative item. We can have three observations:

• •

  The RNS sampling method samples varied negative items that are far from the positive item. It exhibits the characteristic of the point-wise negative sampling method. It samples other existing items that are restricted in the upper-left corner area based on currently learned embedding.

• •

  The MixGCF method, as expected for the line-wise sampling method, exhibits line-style negative sampling results. It is due to the traditional Mixup method that generates a linear interpolation of two embeddings with the same weight on all dimensions.

• •

  DINS shows the characteristics of the area-wise sampling method. We can observe the sampled negative items spans across the whole circle, which gives a sufficient exploration of the embedding space. At the same time, the sample radius of DINS is only $0.22$, which is the smallest among the three methods. It shows DINS samples the hard negatives for assist model training.

Recent years have witnessed the rapid development of the emerging direction of GNN-based recommender systems (He et al., 2020; Peng et al., 2022; Wang et al., 2019; Ying et al., 2018; van den Berg et al., 2017; Yang et al., 2021, 2022; Wang et al., 2022; Yang et al., 2023b) where the user-item interactions are presented as a bipartite graph, and graph neural network methods are employed to learn the representation of each node via exploring structure information. For example, Pinsage (Ying et al., 2018) samples neighborhoods according to the visit counts of a node through a random-walk sampling approach. GC-MC (van den Berg et al., 2017) proposes a graph auto-encoder framework to construct the node representation by directly aggregating the information of its neighbors. NGCF (Wang et al., 2019) captures high-order connectivities by stacking multiple embedding propagation layers and utilizes the combination of different layers’ output for the rating prediction. Compared with NGCF, LightGCN (He et al., 2020) achieves better training efficiency and generation capability by removing the feature transformation and nonlinear activation function. Finally, SVD-GCN (Peng et al., 2022) further simplifies LightGCN by replacing neighborhood aggregation with exploiting K-largest singular vectors for the close relation between GCN-based and low-rank methods.

Negative sampling methods in RecSys have gained significant attention due to their ability to accelerate training and greatly enhance model performance, which can be categorized into the following groups. Static Sampler usually selects negatives from items that the user has not interacted with yet, based on a pre-defined distribution, like uniformity distribution (He et al., 2020; Wang et al., 2019; Rendle et al., 2012) or popularity distribution (Chen et al., 2017b). Hard Negative Sampler techniques choose negative items with the highest scores from the current recommender (Zhang et al., 2013; Shi et al., 2022). There are some mixup-based methods (Huang et al., 2021; Lai et al., 2023) generate new negative items by performing mix operations. GAN-based methods like IRGAN(Wang et al., 2017) and AdvIR(Park and Chang, 2019) use adversarial learning to generate negative items and improve robustness. Auxiliary-based Samplers leverage additional information, such as the knowledge graph in KGPolicy(Wang et al., 2020) or Personalized PageRank scores in PinSage(Ying et al., 2018), to sample hard negative instances.