NEAT: A Label Noise-resistant Complementary Item Recommender System with Trustworthy Evaluation

Embedding-based CIRS are most popular in recent work of CIRS. They treat each item as a vector in the embedding space and estimate the complementary relationship based on the distance between item vectors. The first embedding-based method for CIRS was proposed in [11], which models the co-purchase of items by the similarity between the embeddings of the co-purchased items under the effective training paradigm of Skip-gram with Negative Sample (SGNS) [12]. Wan et. al. extended [11] by incorporating user behavior into the modeling of the item-level complementary relationship with the user and item embeddings learned jointly [6]. Besides of modeling the item embeddings with co-purchase data using SGNS, co-purchase data are also represented as item graphs in [1] [2] [3] and identifying the complementary relationships between items are treated as the link prediction tasks between item nodes. They use the co-purchase records as labels for link predictions based on the distance between item embeddings. To further improve the complementary recommendations, different types of auxiliary data are incorporated into the modeling. Multi-modal data of items such as item descriptions and images are also included in [13] to learn the multi-modal representations of items. The distance between vector embeddings of two co-purchased items in each modal’s embedding space is minimized for complementarity measurement. Xu et al. in [14] considers the last $l$ purchased items as the context to learn the attention-based encoder and represents the complementary relationship via the inner product between encoded item embeddings. This work is reduced to the Item2Vec model in [11] without the context of the last $l$ items in the history. Although the P-companion model in [7] pre-processes the co-purchase labels by removing co-view data and leverage the product-type information to improve the diversity, it still models the complementary relationship via the distance between item embeddings without addressing the noise in the data by parameters. Despite of various auxiliary information such as graph structure, multi-modal data source, shopping context and product taxonomy, all these models are trying to build item embeddings in co-purchase space, and model the co-purchase data using the similarity or distance between the co-purchased items. Hence, these models will suffer from the noisy labels for learning complementary relations.

In addition to the item-level complementary recommendation models, many in-basket recommendation models try to address the complete-the-basekt tasks. For example, BasConv [15] leverages the heterogeneous graph embeddings to perform the in-basket recommendations; multiple intents in the same basket are modeled in [16] to the in-basket recommendation. Although these models capture the co-purchase pattern in the same basket to complete the basket, items in the same basket might not be complementary, for instance, a basket containing both grocery shopping and the household shopping. Even the items with the same shopping intent like grocery shopping might not be complementary. The goal of the in-basket recommendations focuses on completing the basket which cover various types of recommendations such as re-purchase, popular items and user preference in addition to co-purchases and complementary items. Hence, in-basket recommendation is out of the scope of the discussion in this paper.

Gaussian embedding [8] has been applied in recommender system in recent years, e.g., Gaussian embeddings for collaborative filtering [17] and convolutional Gaussian embeddings for personalized item recommendations [18]. They mainly use the Gaussian embeddings to address the different confidences of user/item representations introduced by the lack of user/item information or contradictions between user/item behaviors (e.g., item ratings and reviews by users). However, these methods were not designed for CIRS and hence not applicable to address the unique challenges from CIRS.

Let $v$ denote an item from the item set $\mathcal{V}$ and $b$ denote a transaction (a set of purchased items) from the transactions set $\mathcal{B}$ where $b=\{v_{1},v_{2},...\}$. A tuple $(v_{i},v_{j})$, $v_{i}\neq v_{j}$, from the same transaction $b$ can be considered as a pair of co-purchased items (i.e., a co-purchase record). To further distinguish the role of co-purchased items during training, inference and evaluation, we treat the first item in an item pair $(v_{i},v_{j})$ as the query item $q$ and the second item as the recommendation of $q$.

Learning the complementary relationship with the co-purchase data as labels could suffer from the label noisy, as co-purchased items are not necessarily complementary items. Previous CIRS models simply treat the co-purchased items as the positive label of complementary relationships and fit them by the distance between item embeddings in the embedding space. Formally, given a pair of co-purchased items $(q,v)$, they try to maximize the density of a particular normal distribution at zero: $\mathcal{N}\left(0;\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v},\mbox{\boldmath$\Sigma$}_{zero}\right)\propto-\left(\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v}\right)^{T}\left(\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v}\right)$, where $\mbox{\boldmath$\Sigma$}_{zero}$ is zero and $\mu$ is the item embeddings, to bring the item embedding ($\mbox{\boldmath$\mu$}_{q},\mbox{\boldmath$\mu$}_{v}$) closer in the embedding space. Because these models do not consider the noise in the co-purchase labels, the distance between item embeddings is hardly reflecting the complementary relationship, even it might be a good approximation for co-purchases.

To address the label noise issue for learning complementary relationship, as aforementioned, we model the co-purchase data as a Gaussian distribution, where the mean is the co-purchases from the true complementary, and the variance is the co-purchase from the noise. In order to do so, we consider each item $v\in\mathcal{V}$ as a Gaussian embedding $\mathcal{N}\left(x;\mbox{\boldmath$\mu$}_{v},\mbox{\boldmath$\Sigma$}_{v}\right)$, where $\mbox{\boldmath$\mu$}_{v}\in\mathbb{R}^{d}$ is the mean vector and $\mbox{\boldmath$\Sigma$}_{v}\in\mathbb{R}^{d\times d}$ is the covariacne matrix in the $d$-dimensional embedding space, which models the variation in the co-purchase behavior of $v$. While the inner product between vectors of two items is used to model their complementary relationship from the co-purchase record in the literature [6][11], we compute the expected likelihood [9] as the inner product of two Gaussian embeddings [8] to parameterize the Gaussian distribution of complementary relationships. Given an item pair $(q,v)$, the expected likelihood between their Gaussian embeddings is defined in Equation III-B, which is the probability density of a Gaussian distribution at zero, $\mathcal{N}\left(0;\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v},\mbox{\boldmath$\Sigma$}_{q}+\mbox{\boldmath$\Sigma$}_{v}\right)$.

Hence, $\mathcal{N}\left(x;\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v},\mbox{\boldmath$\Sigma$}_{q}+\mbox{\boldmath$\Sigma$}_{v}\right)$ denotes the Gaussian distribution of the co-purchase data between $(q,v)$, where the mean is the difference between two items mean vectors in complementary space and the covariance matrix combines the variance of each individual items. The probability density at zero, $\mathcal{N}\left(0;\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v},\mbox{\boldmath$\Sigma$}_{q}+\mbox{\boldmath$\Sigma$}_{v}\right)$, represents the likelihood of observing a co-purchase record of $(q,v)$ when considering both their complementary relationship ($\mbox{\boldmath$\mu$}_{q}-\mbox{\boldmath$\mu$}_{v}$) and variations of purchase behaviors ($\mbox{\boldmath$\Sigma$}_{q}+\mbox{\boldmath$\Sigma$}_{v}$).

To illustrate the benefit of representing both co-purchase data and items embeddings as Gaussian distributions, let’s consider an example from our daily shopping: milk, cereal and chips, in a 1-dimensional embedding space in Figure 1. In Figure 1-(a), milk has the largest variance among three items because it is usually a must-buy for many customers and very likely to be co-purchased with other items without complementary relationships. Cereal has the smallest variance due to its stable co-purchase behavior with milk. The variance of chips is intermediate because it has some stable combinations such as chips dips while users might also buy them individually as a snack before checkout, which makes it variance relatively larger. In Figure 1-(b), we show the Gaussian distribution of their complementary relationship and highlight the their probability density at zero by the point $A$ for (milk, chips) and the point $B$ for (milk, cereal) when milk serves as the query item. Because the difference of variances, the Gaussian distribution of the co-purchase for (milk, cereal) shows less variance than that for (milk, chips). Even though the observed co-purchase records between milk and chips might be more than those between milk and cereal, our model can still capture the correct order of complementary relationships by comparing $|\mathbf{\mu}_{milk}-\mathbf{\mu}_{cereal}|$ and $|\mathbf{\mu}_{milk}-\mathbf{\mu}_{chips}|$. However, previous methods using item embeddings might result differently due to the directly fit for co-purchase frequency.

We follow the paradigm of Skip-gram with Negative Sampling (SGNS) and generate the negative sample $v^{\prime}$ which is not co-purchased with $q$. Following the margin-based loss [8], we construct a max-margin loss function with the margin $\gamma$ in Equation 2:

where

Existing works on CIRS such as [6] show that user information will help improve the learning of item-to-item relationship in a collaborative way by introducing the user embedding to the Item2Vec [11] model. Our model can be extended easily with user information. Specially, we adapt the advantage of modeling the cohesion of each (item, item, user) triplet and modify the BPR loss [19] to model user-item relationship by minimizing the loss function 3 and 4, where $\sigma(\cdot)$ is the sigmoid function and $q^{\prime},v^{\prime}$ represent the negative samples that are not purchased. These loss functions can be combined together with $\mathcal{L}_{item}(q,v,v^{\prime})$ to form a new loss function $\mathcal{L}_{item}(q,v,v^{\prime}|u)=\mathcal{L}_{item}(q,v,v^{\prime})+\mathcal{L}_{BPR}(u,q,q^{\prime})+\mathcal{L}_{BPR}(u,v,v^{\prime})$.

Depending on whether we consider $\mathcal{L}_{item}(q,v,v^{\prime})$ or $\mathcal{L}_{item}(q,v,v^{\prime}|u)$ for a given co-purchase record $(q,v)$, the final objective function $\mathcal{L}$ can be written in Equation 5, where $S$ denotes the sampled records for training and $\mathcal{L}_{item}$ could be $\mathcal{L}_{item}(q,v,v^{\prime})$ or $\mathcal{L}_{item}(q,v,v^{\prime}|u)$. We optimize $\mathcal{L}$ by mini-batch Stochastic Gradient Descent.

To recommend complementary items, we extract the item Gaussian embeddings and treat the mean vector of each item as its representation under complementary relation. To mitigate the impact of the vector magnitude when computing the distance between mean vectors for ranking and comparison, we follow Item2Vec [11] and Triple2Vec [6] and use the cosine similarity between two items’ mean vectors to represent the relevance of the complementary relationship.

For the publicly available dataset of raw transactions, we consider Instacart dataset (INS) published by [20]. The date of each order in this dateset is not provided but the sequence of transactions by each user is available. Items in each transaction are sorted by their purchase orders and the item-types are also provided in Instacart by the aisles. Instacart dataset has 134 aisles from 21 departments and 3.3 million transactions, which is small compared with the real-world applications with more item-types and larger volume of transactions. We use the default train (INS-T) and test (INS-E) split provided by Instacart dataset. To further study the model performance, we collect a proprietary dataset (WMT) with a larger scale from Walmart e-Commerce platform (www.walmart.com) following the same format of Instacart, where the sequence order of transactions are kept and the order of purchases in the same sequence is also preserved. For WMT dataset, we randomly sample $15.2$ million transactions from the past 6-month history data and keep the latest $1.2$ million transactions as our test dataset (WMT-E). The rest of $14$ million transactions are used for training (WMT-T). Similar to INS dataset, we collect the item categories based on the taxonomy of Walmart platform. Co-purchase records are created from INS and WMT dataset respectively to serve model training and label generation for evaluation. Table III summarizes the statistics of the INS and WMT datasets.

We follow the steps in III-A to collect all the co-purchase records for training from the training set. To improve the quality of labels for model training, we remove labels selected in the previous steps where two items are from the same aisles (for INS dataset) or the same category (for WMT dataset) to remove similar items. This is similar to the strategy used in [7] when co-view data are not available because items from the same aisle or category are similar and are likely to be co-viewed for substitution.

For evaluation, we create the trustworthy labels following Section IV under different p-value = $\{0.05,0.01,0.001\}$. We conduct the experiments on these unique labels for evaluation. As we mentioned previously, even these labels are with high quality, it is not practical to be used for training purpose, due to the limited coverage in item space. Table IV summarizes the number of unique labels of the INS and WMT datasets.

To evaluate the ability to surface complementary recommendations from the noisy co-purchase data, we firstly generate the recall set by taking the top-$K$ most co-purchased items for the query item in the training data, rather than a sampled item set in which each ground truth item in the test set is paired with a few (e.g., 100) randomly sampled negative items [22][23][24][25]. We report the average score over the co-purchase records for HR@$K$ and NDCG@$K$, $K=\{1,3,5,10,20\}$.

Our model can be extended with user embeddings to model the complementary relationship from the user-item-level co-purchase data. To study the extensibility of our model and the influence of involving user embeddings, we compute HR@$K$ and NDCG@$K$ for NEAT and NEAT+bpr, $K=\{1,3,5,10,20\}$. The results are summarized in Tables IX-XIV. We can see that both NEAT and NEAT+bpr perform similarly but NEAT+bpr outperforms NEAT in most cases when: (1) $K$ becomes larger or (2) number of items increases from INS dataset to WMT dataset. This indicates that including user-item-level signals improves the model performance especially when the number of items is large.

We conduct experiments on NEAT with different margins $\gamma=\{0.1,0.2,0.5,1.0,2.0\}$ on the three label sets of INS dataset and WMT dataset respectively. We report HR@$K$ and NDCG@$K$ for evaluation with $K=\{5,10,20\}$ and summarize the results in Figure 3 and 4. The results indicate that the model is in favor of a larger margin.

To test whether the Gaussian embedding of items could capture the variation of items in their co-purchase, we focus on three items, Whole Milk, Cereal and Organic Tortilla Chips in INS dataset, and study the relationship between item Gaussian embeddings and complementary relationships when Whole Milk becomes the query item. On one hand, the cosine similarity of $\mbox{\boldmath${\mu}$}_{\text{{Whole Milk}}}$ and $\mbox{\boldmath${\mu}$}_{\text{{Cereal}}}$ is larger then that of $\mbox{\boldmath${\mu}$}_{\text{{Whole Milk}}}$ and $\mbox{\boldmath${\mu}$}_{\text{{Organic Tortilla Chips}}}$, which aligns with the expectation of stronger complementary relationship between Whole Milk and Cereal. On the other hand, the query item Whole Milk which has higher popularity than Cereal and Organic Tortilla Chips in INS dataset also shows higher variation (indicated by the determinant of the spherical covariance matrix). In particular, the $\det(\mbox{\boldmath$\Sigma$}_{\text{{Whole Milk}}})$ is 30 times larger than $\det(\mbox{\boldmath$\Sigma$}_{\text{{Cereal}}})$ and is 547 times larger than $\det(\mbox{\boldmath$\Sigma$}_{\text{{Organic Tortilla Chips}}})$. This also aligns with our expectation of their variation since Whole milk (35633 purchases) is more popular than Cereal (12184 purchases) and Organic Tortilla Chips (13776 purchases) in INS dataset and hence more likely to form irrelevant co-purchases.