{'fraction_non_alphanumeric': 0.036926994906621394, 'fraction_numerical': 0.013881953460501348, 'mean_word_length': 4.826738434681408, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generating Negative Samples for Sequential Recommendation

To make Sequential Recommendation (SR) successful, recent works focus on designing effective sequential encoders, fusing side information, and mining extra positive self-supervision signals. The strategy of sampling negative items at each time step is less explored. Due to the dynamics of users' interests and model updates during training, considering randomly sampled items from a user's non-interacted item set as negatives can be uninformative. As a result, the model will inaccurately learn user preferences toward items. Identifying informative negatives is challenging because informative negative items are tied with both dynamically changed interests and model parameters (and sampling process should also be efficient). To this end, we propose to Generate Negative Samples (items) for SR (GenNi). A negative item is sampled at each time step based on the current SR model's learned user preferences toward items. An efficient implementation is proposed to further accelerate the generation process, making it scalable to large-scale recommendation tasks. Extensive experiments on four public datasets verify the importance of providing high-quality negative samples for SR and demonstrate the effectiveness and efficiency of GenNi.


INTRODUCTION
The central task of Sequential Recommendation (SR) is to accurately predict the next item that a user is interested in based on her past behaviors (e.g., shopping, clicking, etc.). To achieve this, an effective model must be able to learn accurate user preferences toward massive vocabularies of items at each time step. Benefiting from the expressive power of deep neural networks (e.g., Transformer [30,40]), recent deep SR models including [14,18,19,21,29,35,50] arguably represent the current state-of-the-art.
Due to the high computational cost of computing the exact log likelihood for all items [49], most SR methods are optimized via a Noise Contrastive Estimation (NCE) [9,14,38,50] paradigm, which is an approximation of maximum likelihood estimation (MLE). Training with NCE requires the model to sample negative items to pair with positive items, where the training target is to pull positive items closer to sequences while pushing away negative items. Though existing methods improve SR from many different perspectives, such as exploring the potential of different sequential encoders [13,38,38], leveraging side information [18,46,50] and incorporating additional training tasks [5,6,20,21,28,29,43,50], they rarely look into the impact of those negative items. Instead, they commonly adopt uniform or popularity-biased sampling strategies,  which are either unable to reflect true negative item distributions or sub-optimal for training sequence encoders. Therefore, this paper investigates on the importance of sampling informative negative items for training SR models.
To specifically demonstrate the necessity of sampling informative negative items in sequential recommendation, we illustrate a toy example in Figure 1. When a user purchases a water bottle online, the recommender predicts a bottle holder as her next item because of observed concurrent consumption behavior from others; however, she purchases shoes instead. At this moment, the bottle holder is an informative negative because the SR model made a wrong prediction. After she purchases shoes, the informative negative item changes to sports shirts because the model has observed sequential correlations between shoes and shirts, which however are not the actual next item in this user's sequence. In such scenario, the uniform sampling method would ignore both dynamics and relatedness of negative items as training proceeds, which samples uninformative items, thus contributing little to the optimization. Without dynamically generating informative negative samples, the SR model is unable to improve further, resulting in sub-optimal performance of the sequential recommendation.
Nevertheless, sampling informative negative items for sequential recommendation poses threefold challenges. First, it is non-trivial to characterize the sequential dynamics in sampling informative negative items. DNS [47] proposes a ranking-aware negative sampling scheme, which is devised to optimize static collaborative signals. PinSAGE [45] identifies items of high PageRank scores with respect to positive items as the informative negative items. MCNS [44] introduces a Markov Chain negative sampler for graph representation learning, which only harnesses constant neighbors for sampling. As in the aforementioned example, the informative negative samples change according to users' consumption behaviors. In this sense, ignoring the sequential correlations fails to reveal true negative item distributions. Second, informative negative items are tightly arXiv:2208.03645v1 [cs.IR] 7 Aug 2022 associated with the model. During initial training stages, the model has no ability to classify items, so that all negative candidates are equally informative. As training proceeds, the model is capable of identifying some negative items; therefore, only those 'hard' negative [2,3,34] items are informative and should be sampled to accelerate optimization. As such, we should recognize the current state of models when generating negative samples. Last but not least, it is hard to retain efficiency. Due to the large-scale item corpus and (usually) sparse observed interactions, there are many negative item candidates. Identifying informative negative items from those candidates requires awareness of their contributions to optimization, which is time-consuming. Therefore, it is crucial to efficiently sample informative negative items to preserve the scalability of models.
To this end, we propose to Generate Negative items (GenNi) for SR. At each time step, a negative item is sampled based on the similarity between the current SR model learned user interests and the item embeddings. GenNi adaptively generates negative samples without training an additional generative module except the SR model itself, which reduces computation cost. We develop an efficient algorithm to further improve the computational efficiency by a two-stage sampling strategy, which makes GenNi scalable to large-scale recommendation tasks. A self-adjusted curriculum learning strategy is also proposed to alleviate the human effort of tuning the hyperparameters in GenNi. Though conceptually simple, GenNi greatly improves upon state-of-the-art SR models. Its success shares the same spirit with works in other domains [17,36,44,47,48] where "hard" negatives matter and can be generated via self-adversarial training.
We conduct extensive experiments on four public datasets and observe that SR models can be significantly improved simply by replacing the original negative sampler with GenNi, e.g., the average performance of S 3 -Rec [50] in NDCG@5 is improved 107.66% over four datasets. It shows that negative item sampling is as important as other components to make SR successful. Detailed comparisons with other negative sampling strategies and analyses further validate the superiority of the proposed method.

RELATED WORK 2.1 Sequential Recommendation
Sequential recommendation aims to accurately characterize users' dynamic interests by modeling their past behavior sequences. Early works on SR usually models an item-to-item transaction pattern based on Markov Chains [11,31]. FPMC [33] combines the advantages of Markov Chains and matrix factorization to fuse both sequential patterns and users' general interest. With the recent advances of deep learning, many deep sequential recommendation models are also developed [13,14,35,38]. GRU4Rec [13], Caser [38], and SASRec [14] explore the potential of encoding user sequential behaviors via an RNN, CNN, and Transformer, respectively. FDSA [46], TiSASRec [18] and S 3 -Rec [50] leverage side information (e.g., time-interval, item categories.) for a comprehensive representation. BERT4Rec [35] replaces next-item prediction (NIP) task with a masked-item prediction task [39] to capture contextual information. With the success of contrastive self-supervised learning, several works [21,28,29,43] propose different contrastive SSL paradigms as a complement or a replacement task of NIP for a more comprehensive learning. LSAN [19] also improves SASRec from efficiency serving perspective Nevertheless, most existing works ignore the importance of quality of sampled negative items and view the item randomly sampled from user non-interacted item set or all items in the same training batch as negative items.

Negative Sampling
Word2vec [24] first proposes to sample negative items based on the word frequency distribution proportional to the 3/4 power to train the skip-gram language models. Later works in NLP and Social Networks often follow such setting [8,27,37]. In graph mining, Ro-tatE [36] first proposes to sample negative items based on model's prediction and then MCNS [44] proposes to further improve its efficiency via the Markov Chain based Metropolis-Hastings algorithm. However, these methods only consider neighborhoods of the nodes on graph while ignore the sequential dynamic of the data. Another line of works improves the Sampled Softmax [3,49] to better approximate to the full Softmax. In contrast, our work study the SR methods that trained under NCE framework, which trains a sequential binary classifier to distinguish target and negative items. Several GAN-based [7] methods are proposed for application such as information retrieval [26,41] and graph node embeddings [4]. However, GAN-based methods are often hard to train and the additional training of generator also makes the sampling inefficient for SR models. In recommendation, Bayesian Personalized Ranking [32] first proposes to sample negative items uniformly from user non-interacted items for training factorization machines. Dynamic negative sampling(DNS) [47] develops a ranking-aware negative sampling strategy for improving collaborative filtering based methods. PinSAGE [45] consider items with high PageRank scores as "hard-negative" samples with curriculum learning scheme to train large scale graph neural networks. Despite of their success in their own domain, these methods ignored the importance of the sequential dynamics of users' interests thus are not ideal to be adopt for sequential recommendation.

METHOD
In this section, we first describe the Sequential Recommendation (SR) problem and a general approach to solve the problem with two key ingredients of training a SR model. We then describe our proposed negative item generator, an efficient algorithm as well as a self-adjusted curriculum learning approach to adaptively sample negative items for each user.

Problem Formulation
SR is usually formulated as a next item prediction (NIP) task. Formally, in a recommender system, there is a set of users and items denoted as U and V respectively. Each user ∈ U is associated with a sequence of interacted items sorted in chronological order = [ 1 , . . . , , . . . , | | ] where | | is the number of interacted items and is the item interacted with at step . We denote S as the embedded representation of , where s is the -dimensional embedding of item . In practice, sequences are truncated with maximum length . If the sequence length is larger than , the most recent actions are considered. If the sequence length is smaller (a) A Typical Existing SR Model (b) An SR Model with GenNi (c) Next Negative Item (NNI) Sampler than , "padding" items will be added to the left until the length is [13,14,38]. For each user at time step , the goal of SR is to predict the item that the user would be interested in at step + 1 among the item set V, given her past behavior sequence S 1: .

Training an SR Model with Noise Contrastive Estimation
To train an SR model, a standard learning procedure fits the sequential data following the maximum likelihood estimation principle. Specifically, for each user at position step in a mini-batch B, we want to learn a parametric function that maximize the probability of the target item: where is the partition function that normalizes the score into a probability distribution, and exp(h · s +1 ) is a similarity score of a user's preference toward the target item. Unfortunately, computing this probability as well as its derivatives are infeasible since the (·) term requires summing over all items in V, which is generally of large-scale in sequential recommendation.
Hence, existing methods [14,18,21,43] commonly adopt an approximation via Noise Contrastive Estimiation (NCE) [9]. NCE is based on the reduction of density estimation to probabilistic binary classification. It provides a stable and efficient way to avoid computing (·) while estimating the original goal. The basic idea is to train a binary classifier to discriminate between samples from the positive data distribution and samples from a "noise" (negative sampling) distribution. Specifically, given the encoded user interest h , we view the next item s +1 as its positive item and the sampled negative items from a pre-defined distribution function (·) (e.g., a uniform distribution over all other items in ). We train the SR model with the following loss function: and where ( = 1|h , s +1 ) = (h · s +1 ), is sigmoid function, and s −, +1 is the sampled negative item at + 1. This loss decreases when h · s +1 increases and h · s −, +1 decreases. In other words, optimizing this loss function is equivalent to pulling the sequence embedding h closer to the positive item s +1 whilst pushing away from sampled negative items, thus being contrastive. To make NCE approximate to maximum log-likelihood (Eq 2) closer, one needs to either sample more negative items or improve the quality of the negative sampling distribution (·). Surprisingly, neither of them is paid enough attention by existing methods.
Theorem 1 (Impact of ). Increasing can reduce the mean square error (aka risk) of model estimation and the distribution of negative items (·) become less important when → ∞.
The above theorem shows that is an importance factor of making SR models well trained (proof given in Appendix A). Empirically, naively increasing though trivial, but is not a good choice in recommendation tasks. Because under random sampling, most of the sampled items can be uninformative with the training going on while training time cost is linearly increased. Because of that, existing SR models often keep the default number = 1. Without naively increasing the number of negative items , designing a good negative item distribution function is crucial to make SR models successful. Theorem 2 (Optimal Embeddings). The optimal sequence and item embedding for each user at each time step should satisfy: Theorem 2 indicates that the optimal embeddings are dependent on both data distribution (·) and the negative sampling distribution (·) (proof given in Appendix B.). As such, it is necessary to sample items from true negative sampling distribution, which would otherwise yield sub-optimal results.
The two theorems motivate us to improve sampling process of negative items for sequential recommendation as in following sections. Hereafter, we propose a novel negative item generator as well as a strategy to further improve its efficiency.

Next Negative Item Generator
3.3.1 Principles of an Informative Negative Item Sampler in SR. Theorem 2 implies that in sequential recommendation, the informative negative items dynamically change with the user's interests at time as well as the network parameters . We therefore define the principles of informative negative item sampler for SR as follows: Dynamic: The sampler should be aware of the dynamic of the user's interests at each time step. When a user interacts with a new item, the corresponding informative negative items can also be changed.
Adaptive: The sampler should be adaptive to the model structure as well as its parameters . The sampled item is uninformative if it is easy to be predicted as a negative item [17].
Efficient: The sampler should also be efficient enough to scale to large recommender systems. The sampler can be alternated by tuning the hyperparameter or even training without sampling (Eq. 1) if it is inefficient.

3.3.2
Generating Negative Items via Self-Adversarial Training. Based on the aforementioned principles, we propose to generate negative items based on user's interests and model's current predictions. Specifically, at each time step , a user historical behavior sequence is encoded by a networks: h = ( 1: ) (e.g., Transformer encoder [14,18,21,43]). Then we leverage the current sequential dynamic h and the model's current state (parameterized by ) to generate next informative negative item. The (·) function is defined as follows: whereˆis the estimated model parameters at ℎ learning iterations and controls the difficulty of the sampler. When = 0, the sampler follows a uniform distribution. The larger , the more informative item is more likely to be sampled. We can see that now the (·) function is both dynamic to the changes of user's interests over each time step and also adaptive to the model's learning state over each training iteration . We denote Eq 5 next negative item (NNI) sampler. The sampling strategy shares the same spirit with works in other domains, such as CV, NLP and graph mining [2,17,36,44,47,48] where "hard" negatives matter and can be generated via self-adversarial training. Figure 2 (b)-(c) illustrates this process.
Stage-Two Figure 3: Comparison of the standard Next Negative Item (NNI) sampler and its acceleration.

3.3.3
Acceleration. Although Eq. (5) already defines the negative sampling distribution, it is still inefficient due to the summation over all the items in the denominator part. Hence, we devise a two-stage sampling strategy to further accelerate the sampling procedure. To be more specific, at a certain time step, a negative item is sampled as follows: • Pre-Selection: a small subset of candidate items is pre-selected from V in the first stage. We uniformly select ratio of candidate items denoted as V ′ ⊂ V. • Post-Selection: we use the proposed NNI sampler to further narrow down the nominated items V ′ and serve to the user: With the acceleration, the computation time of negative item generation reduces from the original O (|V |) to O ( · |V |), where ranges from 0 to 1. When ≈ 0, sampling becomes uniform (and Post-Selection is not needed). When = 1, Pre-Selection is no longer needed, which becomes Eq. 5. controls the trade-off between effectiveness and efficiency. Figure 3 illustrates the process. There are two strategies to set : • A fixed value. This strategy is simple and potentially can save the most computation cost. The drawback of having a fixed value is that as training proceeds, the number of informative items become less and less (most of the items are already considered as negatives by the SR model). Having a small value can potentially filter out all the informative items in later training stage, so the model will stop learning. Although, we empirically (in Section 5.4) find that can be small without a large performance drop. • Gradually increasing . An alternative strategy is to gradually increase as training proceeds: where denotes the ℎ training epoch and controls how fast increases. Items sampled from a uniform distribution can be informative in initial stages because the SR model hasn't started to learn. But most of them become uninformative as the training continues. By gradually increasing , informative items can always be sampled while reducing computation cost compared with the full version (fixed = 1.0). See Section 5.4 for more detailed comparisons.

Overall Scheme.
We term the whole negative item generation process described from Section 3.3.1 to Section 3.3.3 as GenNi. The overall training scheme with GenNi for SR model is provided in Algorithm 1. It generates negative items based on the SR model without introducing additional parameters. The proposed acceleration strategy further improves its efficiency so GenNi can be scaled to large-scale recommendation tasks. GenNi is a modelagnostic negative item generator, we apply GenNi to both SASRec and S 3 -Rec, denoted as GenNi SA and GenNi 3 .

Self-Adjusted Curriculum Learning
GenNi introduces to control how often hard negatives are sampled. But we must still manually tune . Curriculum learning [1,17] allows neural networks to begin by understanding easy negative samples followed by hard ones. We further reduce this rule to let the model itself adjust . Specifically, we use the loss value in each batch as the critic to see if the current curriculum is too hard or too easy. When the previous loss is larger than the current one, we increase , otherwise we decrease . In this way, is self-adjusted with the online loss value as feedback, which reduces human effort in choosing the initial (see Section 5.5.1 for more detail).

DISCUSSION 4.1 Time Complexity and Convergence Analysis
The computation costs of GenNi SA and GenNi 3 are similar to SASRec and S 3 -Rec except that our methods use GenNi instead of uniform sampling. The overall computation cost is mainly from Transformer, the feed-forward network and GenNi, which is O ( 2 · + · 2 + · |V | · ). The dominant term is typically O (| | 2 ) from Transformer when is small. Though GenNi requires high computational cost when · |V | are large, however, our proposed acceleration strategy of it ensures faster convergence as well as better performance (see Section 5.3). The proposed two strategies of choosing in Section 3.3.3 also help to balance the effectiveness and efficiency of GenNi. More details regarding convergence analysis are provided in Appendix C.

GenNi for Improving Sequential BPR loss
Though our method is induced from NCE paradigm in SR, GenNi also has the ability to improve other training framework built upon pair-wise ranking loss, e.g., sequential BPR [32]. Previous work [12] justifies that optimizing a recommender model with a BPR loss results in gradient vanishing issue if introducing more than one negative samples. The reason is that after several epochs of training, those uniformly sampled negative items already have lower scores than the target due to their easiness to identify. As a result, gradients towards those negative items gradually diminish. Instead, GenNi generates informative negative items during each epoch of training, which alleviates the gradient vanishing issue of BPR. We conduct experiments to verify this claim in Section 5.5.2.

EXPERIMENTS
In this section, we evaluate the performance of our approaches compared with the state-of-the-art sequential recommenders and justify the benefits of our proposed negative item generator GenNi. We also investigate impacts of the hyper-parameters and conduct the ablation study. A case study is also included to better understand how GenNi improves the training.

Datasets.
We conduct experiments on four datasets: Sports, Beauty, Toys, and Yelp. Sports, Beauty, and Toys are three subcategories of Amazon review data introduced in [23]. Yelp 1 is a dataset for business recommendation. We follow [21,28,43,50] to prepare the datasets. In detail, we only keep the "5-core" datasets, in which all users and items have at least 5 interactions. The statistics of the prepared datasets are summarized in Appnedix D.

Evaluation Metrics.
For a fair comparison, we follow previous works [16,42] to rank the prediction on the whole item set without negative sampling. Performance is evaluated on a variety of Top-K evaluation metrics, including Hit Ratio@ (HR@ ), and Normalized Discounted Cumulative Gain@ (NDCG@ ) where ∈ {5, 10}.

Baselines.
We compare our approach with three groups of representative baselines. (i). SR models with uniform negative samplers including Caser [38], GRU4Rec [13], SASRec [14], and S 3 -Rec [50]. We omit non-sequential models such as BPR-MF [32] and simple item popularity based methods, which are shown weaker than SR methods on these datasets [21,35,50]. (ii). SR models with other negative sampling strategies including DSSRec [21], CL4SRec [43] and MMInfoRec [28]. Different heuristic hard negative mining strategies are also purposed to further improve the quality of negative samples. (iii). Additional negative sampling strategies. In addition, we also includes the popularity-based method [24] from NLP domain that samples negative items based on the power of item frequency ( ) ∝ ( ) , denoted as SASRec pop . Detailed descriptions of these baselines are in Appendix E. We implement two variants of our approaches GenNi SA and GenNi 3 with Pytorch. Our methods consider SASRec and S 3 -Rec as our base models and replace the uniform sampler with our proposed GenNi. Models are optimized by an Adam optimizer [15] with a learning rate of 0.001, 1 = 0.9, 2 = 0.999, and batch size of 256. Early stopping criteria (models stop training if the performance on the validation set doesn't increase for 40 successive epochs) is used during training. For hyper-parameters in GenNi, is tuned from 0 to 6, is tuned from 0.0001 to 1.0 in a exp scale, number of negative items is tuned from 1 to 10. We also provide results using a self-adjusted curriculum learning strategy (See Section 3.4) that reduces the need to tune . All experiments are run on a single Tesla V100 GPU and we report the average results under 4 different random seeds on the test set.
All code shall be released upon publication. Table 1 shows overall recommendation performance of all models on the four datasets. We observe that:

Performance Comparisons
• Our methods GenNi SA and GenNi 3 both consistently outperform existing methods on all datasets by a large margin. The average improvement compared with the best baseline ranges from 6.15% to 49.05%. Specifically, compared with SASRec and S 3 -Rec, our approaches simply replacing their original uniform sampler with GenNi, achieve 96.02% and 107.66% average performance improvements on four datasets over SASRec and S 3 -Rec at NDCG@5, respectively. This observation clearly shows that sampling informative negative items is as important as other components in making SR successful and also demonstrates the effectiveness of our proposed sampler GenNi. • Transformer is an effective way of encoding user sequential dynamic patterns. Compared with GRU4Rec, Caser, SASRec and S 3 -Rec we can see that SASRec and S 3 -Rec that utilize a Transformerbased encoder can consistently achieve better performance compared to CNN/RNN-based encoders: Caser and GRU4Rec. S 3 -Rec performs better than SASRec in most datasets because it fuses additional item attributes during pre-training. However, all these methods sample negative items randomly from user non-interacted item sets, yielding to a sub-optimally trained model. • For different negative sampling strategies, SASRec pop performs slightly better than SASRec, indicating that the popularity-based method can help improve model learning. However, this strategy is static and does not consider the penalization of each user behavior, resulting in a large performance gap compared to GenNi SA . DSSRec, CL4SRec, and MMInfoRec proposes different contrastive self-supervised learning paradigms can outperform other baselines that only train with an NIP objective. This observation demonstratives the effectiveness of contrastive self-supervised learning. These three methods commonly consider items in the whole training batch as negatives, and MMInfoRec also proposes a heuristic hard negative mining strategy with a memory bank to further improve the quality of the samples. Their successes suggest that sample more negative items and hard negative mining also benefits model learning. Although MMInfoRec is the best baseline method, it still performs worse than our approaches. The reason might be twofold. First, considering all items in the training batch as negative items can introduce false-negative samples.
Second, heuristic hard negative mining (e.g., considering user historical interacted items as hard negatives in MMInfoRec) is not adaptive to model parameters. As a result, the sampled hard negatives can gradually become uninformative to the model.

Training Efficiency Comparison
SASRec has proven to be an order of magnitude faster than CNN and RNN-based recommendation methods [14], such as Caser and GRU4Rec. In this section, we evaluate the efficiency of GenNi SA (on the Beauty dataset) by comparing with the most efficient baseline SASRec and the best performing baseline MMInfoRec (See Appendix F for result comparisons on other datasets). We omit the comparisons of GenNi 3 as it has the same computation cost as GenNi SA in its training stage. The only difference is that GenNi 3 requires a pre-training stage to fuse item attributes in the model. Figure 4 shows the performance w.r.t. training (wall-clock) time as well as the computation cost per epoch. We can see that replacing the uniform sampler with GenNi does introduce additional computation cost; for example, SASRec spends 2.44 seconds on model updates for one epoch while GenNi SA ( = 1) requires 6.30s/epoch. However, GenNi SA converges to much higher performance and requires fewer training epochs to converge. What's more, as we reduce to 0.1, GenNi SA ( = 0.1) only needs 2.47 seconds to update the model for one epoch, which is close to SASRec (2.44s/epoch), and still performs better than SASRec. Although MMInfoRec is the best performing baseline, it requires 34.22 seconds on model updates for one epoch. Our method GenNi SA ( = 1.0) and GenNi SA ( = 0.1) are over 5.42 and 13.85 times faster and also perform better than MMInfoRec.

Hyper-parameter Sensitivity
GenNi introduces two hyper-parameters and that controls the difficulty of sampled negatives and the negative item generation computation cost. The number of negative samples is set as = 1, which is the same as the original SASRec's setting for fair comparison. We also study model sensitivity to the number of negative samples , the embedding size, and learning rate.
Impact of the informative of negative items . Figure 5 shows the influence of on model performance over four datasets. We can see that the model performance increases as increases at the beginning, and then the performance reaches a peak. Specifically, when = 2.5, the model performs best on Beauty,while = 4.4, the model performs best on Yelp. Note that when = 0, GenNi becomes a uniform sampler. The large shows that randomly sampled items can be uninformative as training proceeds, while considering items that are currently hard to be correctly classified can further improve the model. Similar observations are found on Sports and Toys. Impact of for accelerating generation. Figure 6 shows model performance w.r.t a fixed value. We interestingly find that there is an elbow point of that balances the effectiveness and efficiency of GenNi well. For example, when = 0.1, it reduces about 90% computation cost of GenNi while the model can still achieve about 95% performance (e.g., NDCG@5) of its original version ( = 1.0) in Beauty. On one hand, it shows the superiority of GenNi, which takes the efficiency of randomly sampling to pre-select a certain portion of items in the first stage and then concentrates on finding informative ones with a slower but more accurate sampling strategy. On the other hand, the decreasing of performance with small also indicates that with the training goes, the number of informative items also decreasing so too small can filter out all these items in pre-selection stage. As introduced in Section 3.3.3, we also report the results that gradually increasing the value via Eq 7 in Table 2. We can see that gradually increasing can achieves the similar effect as of a fixed = 1.0 because the informative items are decreasing along with training goes and can be small while still capture informative items in early training stage. This strategy reduces the computation cost while achieving same effect comparing with a fixed = 1.0. Impact of the number of negative samples . Figure 7 shows the impact of the number of negative samples. We can observe a diminishing return in the performance improvement for both SAS-Rec and GenNi SA . However GenNi SA can consistently outperform SASRec, which further verifies the importance of sampling informative negative items. Note that training with additional negative samples linearly increases the time cost. While GenNi SA can even achieve better performance with only 1 negative sample compared with SASRec that uses 9 negative samples on Beauty and Sports. See Appendix G for additional results on Toys and Yelp, and the sensitivity to the embedding size, and learning rate.

Ablation Study
5.5.1 Benefits of Self-Adjusted Curriculum Learning. As we can see from Figure 5, model performance is sensitive to ; in general, larger benefits model performance. In order to reduce the effort of tuning for GenNi, we also propose a self-adjusted curriculum learning to let the model adjust based on its current performance. Figure 8 shows the sensitivity to the initial . We can see the model performance is less sensitive to the initial value.

5.5.2
GenNi For Improving BPR Loss. As discussed in Section 4.2, training a SR model with sequential BPR loss can have a gradient vanish issue when using additional negative samples ( > 1). In this section, we conduct experiments to show that GenNi can help alleviate such issues. We train SASRec with a sequential BPR loss and replace the uniform sampling strategy used in BPR with GenNi. Table 3 shows comparisons between uniform sampling and GenNi in HR@5 and NDCG@5 (See Appendix H of additional results). We see that SASRec cannot benefit from more negative samples when training with BPR loss because of the gradient vanishing issue. After replacing the uniform sampler with GenNi, the model's performance is improved with more negative samples.

Case Study
We conduct a case study on the Sports dataset [23] to show examples of dynamically changing informative negative items. Figure 9 visualizes the informative items to the SR model. When the user reviews a water bottle, the cup holder is the most informative item; the user reviews earphones instead, and the most informative items changes to a gym bike (etc.). We can also observe that the informative negative distribution is close to uniform initially, and gradually diversifies as training goes.  Figure 9: Visualization of dynamically changed informative negative items to model on the Sports dataset.

CONCLUSION
In this work, we identified the dynamic of informative negative items in sequential recommender systems, because of the dynamic of users' interests, and the updates of model's parameters during training. We propose a negative item generator GenNi to adaptively generative informative negative samples for training sequential recommenders. Extensive studies on four datasets shows that informative negative sampling is crucial of making the sequential recommendation model well-trained and also demonstrates the superiority of GenNi. The detailed analysis also verified the effectiveness and efficiency of GenNi.

A PROOF FOR THEOREM 1
We can derive from the discrete version of NCE theory (See [22] for assumptions that make the conclusion hold) that there exists an integer 0 such that, for a large sample size | |, for any > 0 (number of negative items), for some matrix I −1 . So there exists a constant value such that for any > 0 , the mean square error (MSE) (aka risk) of the parameter estimation is bounded by: As grows, the risk of parameter estimation is decreasing, thus able to improve model performance. Alternatively, reader can follow [25] to calculate the gradient of Eq. 4 in terms of and will see that as → ∞, the gradient of Eq. 4 is approximated to the maximum likelihood gradient (Eq. 1). Eq. 9 also shows that as B and larger and larger, (·) become less and less important as the estimation can be bound by /( | ||B|). Interesting readers can read on [10,22] for a comprehensive review of NCE.

B PROOF FOR THEOREM 2
Proof. The SR model is optimized through the following objective: where s +, +1 and s −, +1 are target and negative items to the user at time . The above equation can be simplied as where ′ s +1 ,h ( = 1) = (s +1 |h ) (s +1 |h )+ (s +1 |h ) and ′′ s +1 ,h ( = 1) = (s +1 |h ) are two Bernoulli distributions, and (·) measures the cross entropy between two distributions. Based on Gibbs inequality, optimized Eq 10 should satisfy that ′ = ′′ for all user interests h toward next predict item s +1 , i.e., So the optimal embeddings should satisfy:

C CONVERGENCE ANALYSIS
An explanation of why GenNi is superior to heuristic samplings such as uniform sampler is that it can help reduces the risk: E[||ˆ− * || 2 ]. From Eq 9 we can see that, as the training goes, the randomly sampled item would most likely has a small (s|h) than (s|h) value, i.e., the model has learnt to classify it as a negative sample, While the deviate in terms of is determined by the smallest value between (s|h) and (s|h). Optimize with small (s|h) in often time interrupted the accurate optimization. With GenNi, the sampled negatives are often has large (s|h) value meaning that the estimation can more accurately approximate to the optimal * .

D DATA INFORMATION
The statistics of four datasets are shown in Table 4.

E BASELINE METHODS
We compare our approach with three groups of representative baselines.
• SR models with uniform negative samplers. GRU4Rec [13], SAS-Rec [14], which encode sequences with CNN, RNN, and Transformer, respectively. S 3 -Rec [50], which builds on SASRec with a pre-training stage to incorporate additional item attributes into the model. We omit non-sequential models such as BPR-MF [32] and simple item popularity based methods, which are weaker than SR methods [21,35,50]. • SR models with other negative sampling strategies. We compare with recent works that add or replace the NIP objective with a contrastive self-supervised learning objective: DSSRec [21], CL4SRec [43] and MMInfoRec [28]. These works follow the contrastive learning paradigm to consider items in a training minibatch as negatives and propose different heuristic hard negative mining strategies to further improve the quality of negative samples. respectively. • Additional negative sampling strategies. we also includes the popularity-based method [24] from NLP domain that samples negative items based on the power of item frequency ( ) ∝ ( ) , denoted as SASRec pop .

F ADDITIONAL EFFICIENCY COMPARISONS
The training cost comparisons among SASRec, MMInfoRec, and GenNi SA over four datasets are reported in Table 5. In summary, the of balances the effectiveness and efficiency of GenNi. Besides, model with GenNi (e.g., GenNi SA ) can achieve better performance than the best baseline MMInfoRec using much less computation resource.

G ADDITIONAL RESULTS ON
HYPER-PARAMETER SENSITIVITY Impact of Impact of on Toys and Yelp are shown in Figure 10. Similar to observations on Beauty and Sports, Models can be further improved by sampling additional negatives while GenNi SA can consistently outperform SASRec. Impact of embedding size and learning rate Model's sensitivity to the embedding size and learning rate are shown in Figure 11. We can see that vary learning rate or embedding size does influence model's final performance, but their impact to SASRec and GenNi SA have a similar trend and GenNi SA can consistently outperform SASRec in all circumstances.   Table 6 shows the additional result comparisons between uniform sampling and GenNi in HR@10 and NDCG@10 with use of BPR loss. We see observe that SASRec cannot benefit from more negative samples when training with BPR loss. While GenNi alleviates the gradient vanishing issue thus the model's performance is stably improved after sampling more negative items.