Year: 2021

Abstract:
Pairwise ranking models have been widely used to address various problems, such as recommendation. The basic idea is to learn the rank of users’ preferred items through separating items into positive samples if user-item interactions exist, and negative samples otherwise. Due to the limited number of observed interactions, pairwise ranking models face serious class-imbalance issue. Our theoretical analysis shows that current sampling-based methods cause the vertex-level imbalance problem, which makes the norm of learned item embeddings towards infinite after a certain training iterations, and consequently results in vanishing gradient and affects the model performance. To this end, we propose VINS, an efficient Vital Negative Sampler, to alleviate the class-imbalance issue for pairwise ranking models optimized by gradient methods. The core of VINS is a bias sampler with reject probability that will tend to accept a negative candidate with a larger popularity than the given positive item. Evaluation results on several real datasets demonstrate that the proposed sampling method speeds up the training procedure 30% to 50% for ranking models ranging from shallow to deep, while maintaining and even improving the quality of ranking results in top-N item recommendation.

heading: 1 INTRODUCTION
text: Offering personalized service to users is outstanding as an important task, for example, ranking the top-N items that a user may like. Solutions to such kind of problems are usually designed on a bipartite graph G = (V,E), where vertex set V = U ∪ I contains user set U and item set I, and E denotes the edge set. Each edge eui ∈ E denotes an observed interaction between user u and item i. Users’ preference on items is modeled by pairwise loss functions with the assumption that items with interactions from a user are of more interest to this user than those without interactions. The loss function thus involves pairwise comparison between an observed (positive) edge eui ∈ E and an unobserved (negative) edge euj /∈ E. The optimization process thus suffers from the classimbalance issue ,because in practical scenario, the number of observed (positive) edges are always much less than the unobserved (negative) ones. The imbalance between eui ∈ E and euj /∈ E can be regarded as the edge-level imbalance issue.
Pioneering works dealing with the class-imbalance problem can be categorized into two main families: using stationary sampling or using dynamic sampling. Approaches in the former family usually start from the edge-level class-imbalance issue through under-sampling negative edges from a pre-defined stationary distribution (Rendle et al., 2009; Rendle and Freudenthaler, 2014), or oversampling positive edges by creating instances through the social connection (Chen et al., 2019). However, they ignore that class-imbalance issue also exists in vertex side because each vertex can appear in both positive and negative edges. Through some basic statistical analysis, we acquire some interesting findings, that is, the vertex degree has positive impact on vertex-level imbalance problem. If we sample negative instances from a stationary distribution, those popularity vertexes with degree greater than average vertex degree are under-sampled as negative samples, while “coldstart” vertexes with degree less than average degree are over-sampled. Moreover, they can’t capture the dynamics of relative ranking order between positive and negative samples, as shown in Figure 1(a) and 1(b). From Figure 1(a) we can see that it’s easy to find an order-violated item for pairwise loss optimization at the initial state, because there are many negative items ranking higher than the positive item. However, as the learning process moves forward, massive number of negative items are distinguished well from the positive item, shown in Figure 1(b). At this time, a large portion of
the negative items are useless for pairwise loss optimization, because they already rank lower than the positive item.
Recently dynamic sampling approaches (Weston et al., 2011; Yuan et al., 2016; Wang et al., 2020) have shown their significant contribution to negative instances selection by considering the hardness of sampling a negative sample. However, existing dynamic methods have several drawbacks: 1) they lack systematically understanding their connection to class-imbalance issue, leading to only sampling candidate from uniform distribution; 2) they have to find a violated negative sample through searching massive candidates, causing high computation complexity (over ten times higher than sampling from stationary distribution).
In this work, we aim at finding clues that can help to design a faster dynamic negative sampler for the personalized ranking task. We find that sampling from uniform distribution can be regarded as a random walk with a transition probability matrix P for arbitrary node pair in a fully connected item-item graph, which is presented in Figure 1(c). Intuitively, nodes (items) are different in their nature (e.g., degree, betweenness). A biased transition matrix P∗ might be more helpful on finding the desired negative items, than a uniform random P , as shown in Figure 1(d). Through theoretical analysis, we find that one of the potential solutions to decode the biased transition process and walking with a biased transition matrix P∗ is to tackle the class-imbalance issue. To achieve this goal, it is essential to first dissect the impact of class-imbalance issue. More specifically, we mainly investigate the three questions: Q1) how the class-imbalance problem is reflected in current sampling-based pairwise ranking approaches? Q2) what is the impact of the imbalance problem on learning optimal pairwise ranking model? Q3) how can we resolve the class-imbalance issue and design a faster dynamic sampling approach to boost ranking quality? We answer the above questions with theoretical analysis in Section 3. The brief summary is, to Q1, if negative instances are sampled from a uniform distribution (e.g., in (Rendle et al., 2009)), vertexes with high degrees are under-sampled as negative samples, while “cold-start” vertexes with low degrees are over-sampled. To Q2, we theoretically show that the class-imbalance issue will result in frequency gathering phenomenon where the learned embeddings of items with close popularity will gather together, and cause gradient vanishment at the output loss. Based on the above insights, for Q3, we propose an efficient Vital Negative Sampler (VINS), which explicitly considers both edge- and vertex-level class-imbalance issue. In summary, our contributions of this work are as follows:
• We indicate out edge- and vertex-level imbalance problem raised in pairwise learning loss, and provide theoretical analysis that the imbalance issue could lead to frequency gathering phenomenon and vanishing gradient at the output loss.
• To address the class-imbalance and vanishing gradient problem, we design an adaptive negative sampling method with a reject probability based on items’ degree differences.
• Thoroughly experimental results demonstrate that the proposed method can speed up the training procedure 30% to 50% for shallow and deep ranking models, compared with the state-of-the-art dynamic sampling methods.

heading: 2 RELATED WORK
text: Pairwise comparison usually happens between an observed (positive) and an unobserved (negative) edge, when the interactions between users and items are represented as a bipartite graph. Such an idea results in a serious class-imbalance issue due to the pairwise comparison between a small set of interacted items (positive as minority class) and a very large set of all remaining items (negative as majority class). Pioneering work proposed in (Rendle et al., 2009) presented an under-sampling approach via uniformly sampling a negative edge for a given positive edge. Following the idea in (Rendle et al., 2009), (Zhao et al., 2014) proposed an over-sampling method by employing social theory to create synthetic positive instances. (Ding et al., 2019) augmented pairwise samples with view data. However, these sampling strategies discard a fact that each item has its own properties, e.g., degree, betweenness. (Rendle and Freudenthaler, 2014) considered vertex properties and proposed to sample a negative instance from an exponential function over the order of vertex degree. Despite of the effectiveness and efficiency of sampling from a stationary distribution (e.g., uniform, or power function over vertex popularity), they ignore the impact of relative order between positive and negative samples during the learning processes, as shown in Figure 1(a) and 1(b).
Recently dynamic sampling approaches (Weston et al., 2011; Yuan et al., 2016; Chen et al., 2018) aiming at estimating the rank order of positive samples have shown significant contribution of selecting vital negative instances. As a pioneering work, (Weston et al., 2011) proposed the WARP loss aiming at playing less attention to well-learned positives, but more emphasis on the low-rank ones. However, along with the growing of iterations, sampling a violated negative items become very difficult (Hsiao et al., 2014). WARP inspires lots of recent works to estimate rank-aware weight from a uniform distribution As the state-of-the-art variant of WARP loss, LFM-W (Yuan et al., 2016) advances WARP with a normalization term. However, estimating the rank-aware weight from a uniform distribution makes LFM-W need lots of steps to find a violated sample. Moreover, LFMW might find sub-optimal negative sample without considering the class-imbalance issue. Besides considering ranking order, (Wang et al., 2019) regarded dynamic sampling as a minmax game. VINS also inherits the basic ideas from WARP but modifies the target distribution and proposes to estimate it through an importance sampling method after theoretically investigating the existing class-imbalance issue and its potential influence. LFM-W can be regarded as a special case of the proposed VINS with a proper setting.

heading: 3 CLASS IMBALANCED ANALYSIS
text: Let’s use G = (V,E) to represent a user-item interaction graph, where vertex set V = U ∪ I contains users U and items I, and eui ∈ E denotes an observed interaction (e.g. click, purchase behaviors) between user u and item i. The relationship between user u and item i can be measured by a factorization focused method, known as xui = Pu · Pi, where Pu = f(u|θu) ∈ Rd and Pi = g(i|θi) ∈ Rd are the representation of user u and item i generated by deep neural network f(·) and g(·) with parameters θu and θi, respectively. To learn vertex representation that can be used to accurately infer users’ preferences on items, pairwise ranking approaches usually regard the observed edges eui as positive pairs, and all the other combinations euj ∈ (U × I \ E) as negative ones. Then a set of triplets D = {(u, i, j)|eui ∈ E, euj ∈ (U × I \ E)} can be constructed base on a general assumption that the induced relevance of an observed user-item pair should be larger than the unobserved one, that is, xui > xuj . To model such contrastive relation, one popular solution is to induce pairwise loss function as follows:
L(G) = ∑
(u,i,j)∈D
wui · `uij(xui, xuj), (1)
where `uij(·) can be hinge, logistic or cross entropy function that raises an effective loss for any triplet with incorrect prediction (i.e. xuj > xui) that violates the pairwise assumption. wui is the a weight factor which shows the complexity to discriminate the given comparison sample. The optimization of Equation (1) involves an extreme class-imbalance issue, because in practical scenario, the number of unobserved interactions euj /∈ E (negative) is usually extremely larger than the observed eui ∈ E (positive). The imbalance between eui ∈ E and euj /∈ E in pairwise loss can be regarded as the edge-level imbalance issue. Since the class-imbalance problem is caused by the majority of negative edges, under-sampling majority is a practical solution for it (Rendle et al., 2009; Mikolov et al.,
2013). Let’s take the most popular strategy of under-sampling negative edges as an example. For a given positive edge eui ∈ E, we can sample a negative edge by fixing user u ∈ U , then sample one item j ∈ I, euj /∈ E with replacement from a static distribution π = {π(i), i ∈ I}, where π(i) = dβi , β ∈ [0, 1] denotes a weight function of item degree di. Then we can optimize the objective function in Equation (1) with the constructed pairwise samples D̃ ∈ D. In most of pairwise ranking models, how to select effective pairwise comparison samples plays an indispensable role in boosting the ranking performance. In the following, we’d like to present the challenges raised by the class-imbalance issue on selecting pairwise comparison samples, and how to address these challenges with an adaptive sampling method.

heading: 3.1 VERTEX-LEVEL IMBALANCE FROM SAMPLING (Q1)
text: Under-sampling approach can well solve the edge-level imbalance issue. However, it will introduce vertex-level imbalance issue, which has not been aware of, and initiates our study. Definition 3.1 (Vertex-level Imbalance). A vertex can appear in either positive or negative edges. In our case, item i appears as a positive one for user u, but can be a negative one for other users. Vertex-level imbalance happens when the number of times that a vertex appears in observed edges is extremely smaller or larger than that in the unobserved ones.
Assuming that in each iteration of optimizing Equation (1), we will sample one negative edge for each observed edge eui. With a given graph G with |E| observed edges, item i can only appear in di edges as positive samples. In other words, item i could appear as negative in the other |E|−di edges with probability p(i) when sampling with a static distribution π defined as p(i) = π(i)/ ∑ j∈I π(j). Then, the expected number of times that the item i acts as a negative sample is p(i) · (|E| − di). Afterwards, we define the imbalance value (IV ) of item i as: IV (i) = dip(i)·(|E|−di) = d1−βi · ∑ j∈I π(j) |E|−di . Through theoretical analysis, we find that imbalance value is positively correlated to item degree.
Theorem 3.1. By sampling negative items with a static distribution π = {π(i) = dβi |β ∈ [0, 1], i ∈ I}, for two items with di > dj , the imbalance value of item i is larger than item j.
The complete proof for theorem 3.1 can be found in Appendix A.
The above analysis shows that the degree of the most popular and long-tailed item will determine the upper and lower bound of item imbalance value for a given graph G. As a special case, if β = 0, we have IV (i) = di·|I||E|−di . Let’s set IV (i) = 1, we can see that di = |E| |I|+1 ≈ |E| |I| , which is exact the average item degree. If an item’s degree is larger than the average degree, it will have an imbalance value larger than 1, while for those item with degree lower than average degree, their imbalance value will be smaller than 1. This implies that popular vertexes are under-sampled as negative samples, while “cold-start” vertexes are over-sampled. For different setting of β, the situation will be different. We illustrate the maximum and minimum imbalance value in Figure 2, obtained by the empirically calculated IV (i) from two real datasets with different decay factor β. We can see that a proper choice of decay factor β can reduce the maximum imbalance, meanwhile increase the minimum value.

heading: 3.2 IMPACT OF CLASS-IMBALANCE (Q2)
text: We next move to the question “what is the impact of the class-imbalance problem on pairwise loss function optimization?”. Before answering this question, we first introduce an imbalanced item theorem inspired by the Popular Item Theorem (Lee and Lin, 2016), which proves that the norm of latent vector of the popular items will be towards infinite after a certain number of iterations. We extend the theorem as follows (with complete proof presented in the Appendix B):
Theorem 3.2. [Imbalanced Item Theorem] Suppose there exists an imbalanced item i with IV (i) 1, such that for all neighbor users u ∈ Ni, xui ≥ xuj for all other observed item j of user u. Furthermore, after certain iterations τ , the representation Pu, u ∈ Ni converges to certain extent. That is, there exists a vector P̂ t in all iteration t > τ , inner-product (P̂ t, P τu ) > 0. Then the norm of Pi of the imbalanced item i will tend to grow to infinity if ∂`uij ∂xui > 0 for all i with xui > xuj .
Frequency gathering phenomenon. The Imbalanced Item Theorem implies that the learned embeddings of items will appear a certain pattern that is closely related to item’s imbalance value. To confirm that, we optimize logistic pairwise loss function by sampling negative samples from a uniform distribution and also by using the proposed method VINS on the experimental data. Since there’s no vertex-level imbalance problem in the user side, the learned user embeddings are independent on the degree information. From Figure 3, we can see that the learned embeddings of items by the uniform sampling approach appear clear frequency gathering phenomenon, where items with similar degree values gather together. The more popular items tend to have larger embedding norms, which matches the statement in the Imbalanced Item Theorem. We further study the embeddings learned by the proposed approach VINS that explicitly considers vertex-level class-imbalance, and find that those bottom items tend to spread across the frequency margins. We also explore a special case β = 1 for sampling from a static distribution π, with which the vertex-level imbalance can be perfectly mitigated. However, comparing with the setting β = 0, it can significantly downgrade the prediction performance, because the learned item embeddings can’t keep their structure role and proximity very well. It suggests that controlling the class-imbalance problem might help to improve the ranking performance, but still need to achieve a trade-off between keeping the graph structures and alleviating the negative impact of class-imbalance problem.
−50 0 50 −75
−50
−25
0
25
50
75 Yelp-Item-Visual-Uni
−50 0 50 −80
−60
−40
−20
0
20
40
60 Yelp-Item-Visual-VINS
−50 −25 0 25 50
−60
−40
−20
0
20
40
60 Yelp-User-Visual-Uni
−50 −25 0 25 50
−60
−40
−20
0
20
40
60
Yelp-User-Visual-VINS
Figure 3: Visualizing the projection of learned embeddings with the classical uniform sampling and the proposed sampler VINS by the T-SNE algorithm into two-dimensional space (colored by vertex degree levels, red–top 25%, blue–bottom 25%, green–the rest).
Gradient Vanishment. Besides the frequency gathering phenomenon, another issue caused by the infinite norm is the gradient vanishment in pairwise loss optimization. Following the under-sampling method described in Section 3, gradient update for model parameters can be carried out for a given pairwise sample (u, i, j). After t > τ iterations, the model parameters θi can be updated with stochastic gradient descent method: θt+1i = θ t i + η · λuij · ∂xui∂θi , where λuij = ∂`uij ∂xui
, and η denotes the learning rate, and ∂xui∂θi represents a gradient backpropagation operation according to the chain rule.
The value of λuij depends on the type of loss function. If we use logistic loss as an instance, `uij(xui, xuj) = lnσ(xui−xuj), where σ(x) is the sigmoid function and λuij = (1−σ(xui−xuj)). According the Imbalanced Item Theorem, the norm of learned embeddings of those imbalanced items will become extremely large. Let’s fold out xui = Pu · Pi = ||Pu|| · ||Pi|| · cos(Pu, Pi). If positive item i suffers from imbalanced issue and has a large norm, i.e., ||Pi|| ||Pj ||, the relevance prediction for user u will be dominated by the norm of item i’s embedding. Then, the induced hinge loss will be very close to zero. While popular items take up a large portion of the observed edges, most of the training samples will have λuij → 0 according to Theorem 3.1 and Theorem 3.2. It suggests that massive number of pairwise samples are meaningless for updating the model, and only a small number of them are valuable. Following the idea in pioneering work (Rendle and
Freudenthaler, 2014), we conduct an empirical study on two experimental data to show the connection between gradient vanishment and item class-imbalance issue. From the results shown in Figure 4, we have the same observation as (Rendle and Freudenthaler, 2014) that gradient magnitude of most of training cases tend to be close to zero, meanwhile we find that items with larger imbalance value tend to have smaller gradient magnitude on average. Connecting to the Theorem 3.1 and Theorem 3.2, we can see that the reason why popular items tend to have smaller gradient magnitude has positive relation to the class-imbalance issue.

heading: 4 VITAL NEGATIVE SAMPLER
text: In this section, we will introduce the proposed method, namely Vital Negative Sampler (VINS). We first introduce RejectSampler which is the key component of VINS, then present VINS.

heading: 4.1 SAMPLING WITH REJECT PROBABILITY (REJECTSAMPLER)
text: Combining Theorem 3.1 and the frequency gathering phenomenon, we find that there exists a positive connection between item degree and the learned embeddings. We thus design a negative sampling approach which tends to sample a negative item j with a larger degree than the positive item i, rather than a negative item with a smaller degree than item i. With such strategy, it’s helpful to control the class-imbalance issue by reducing the imbalance value of popular items, but increase the imbalance value of long-tailed items. More specifically, for a given positive sample eui, we sample a negative item j with reject probability 1 - min{π(j)π(i) , 1}. With this reject probability, we can increase the chances of popular items exposed as negative samples while downgrading the chances of long-tailed items. We can see that the RejectSampler actually equals to a biased random walk as shown in Figure 1(d) to choose the next step with a given transition matrix P ∗, where
P ∗ij = { min{π(j)π(i) , 1} if i 6= j 1− ∑ v 6=i P∗iv if i = j . In fact, RejectSampler can adapt beyond the item degree information to define the reject probability, resulting a different transition matrix P∗. The detail of RejectSampler is illustrated in Algorithm 2 of Appendix C.

heading: 4.2 ADAPTIVE NEGATIVE SAMPLING
text: The RejectSampler can help to alleviate the class-imbalance issue. We next introduce the full VINS approach, which considers the dynamic relative rank position of positive and negative items for finding more informative negative samples avoiding λuij → 0 as much as possible, which is very important for dealing with the mentioned gradient vanishment issue in Section 3.2. Algorithm 3 in Appendix C presents VINS in details. Specifically, to generate a negative sample, RejectSampler is firstly used to sample an item that is not connected to user u (line 5 to 7 in the algorithm). Note that item j sampled from RejectSampler is not guaranteed to be negative for user i. Therefore RejectSampler is re-called if j is connected to u (euj ∈ E). The next step is to evaluate if the sampled item j is a violated one, which satisfies + xuj ≥ xui, where is a margin (line 8 to 13 in the algorithm). In fact, there can be a set of violated negative samples, noted as Vui = {j| + xuj ≥ xui, euj /∈ E}. The hardness of searching a violated negative sample increases when the positive item i is ranked higher. This hardness is reflected as the weight factor wui in Equation (1). For the positive item i with a relative high rank position, we should generate a small weight wui, while give large weights to those lower-ranked ones. We thus define the weight as wui(ri), where ri = ∑ j∈V ui
π(j)I( + xuj ≥ xui) is the rank-aware variable of item i. I(x) is an indicator function. From the definition of ri, we can see that the smaller ri is, the high-rank position of item i is. Previous work (Weston et al., 2011) takes a truncated Harmonic Series function to generate the weight wui(ri) = ∑ri s=1 1 s . We can see that Harmonic Series weighting method needs calculate the summation term for each given estimated rank position, which has the worst complexity O(|I|) for each sample. Inspired by the lower bound of truncated Harmonic Series (shown in Lemma 4.1), we derive a efficient way to calculate the wui(ri) with complexity O(1).
Lemma 4.1. For a given k ∈ N, truncated Harmonic Series ∑2k s=1 1 s ≥ 1 + k 2 . When k = 0, the equality holds.
The complete proof of Lemma 4.1 is described in the Appendix D. According to this lemma, we divide the rank list into k chunks, each of which has size 2k−1 (growing with the chunk number k), and is attached with a weight (i.e. 0.5). For the rank variable ri, we can derive the chunk number based on the Geometric progression formulation, which leads to d∗elog2(ri + 1). Since first chunk has weight 1, we subtract 1 in the definition. More specifically, we define wui(ri) as follows: wui(ri) =
1+0.5·(d∗elog2(ri+1)−1) 1+0.5·(d∗elog2(Z+1)−1) , where 0.5 is the weight for each chunk with size 2k−1, and Z = ∑ i∈I π(i). However, ri = ∑ j∈V ui
π(j) is difficult to attain. We use an item buffer bufferui with size κ to store every sampled negative candidate j. Then, ri can be approximated as ri ≈ b Zmin(K,κ)c, where K is the number of steps to find item j. The final informative negative item j to update model parameters will be selected from the top of the sorted bufferui in descending order based on xuj , as shown in Algorithm 1 of Appendix C. With the selected negative item j by VINS, we can construct pairwise sample (u, i, j) to train the ranking model. The employment of RejectSampler in VINS has two benefits. First, it considers the class-imbalance issue and tends to select the useful negative items than doing randomly, given the fact that items with large imbalance values usually have large norm that makes them difficult to be distinguished from positive items. Second, it reduces the size of negative item candidate set to explore through selecting the useful negative samples to the buffer. More discussion about the characteristics of the proposed method and its connection to previous methods can be found in Appendix E.

heading: 5 EXPERIMENTS
text: In this section, we conduct extensive experiments to answer three research questions: [RQ1] How will the item imbalance value evolve when using different sampling strategies? [RQ2] What are the advantages of VINS, comparing with the state-of-the-art baselines? [RQ3] How VINS can improve the computationally expensive models by sampling the most useful training data?

heading: 5.1 EXPERIMENTAL SETTINGS
text: Datasets and Evaluation Metrics. To validate the proposed sampling method, we use four publicly available datasets, from Yelp Challenge (13th round) 1, Amazon 2 and Steam (Kang and McAuley, 2018). The detailed information about the datasets and the way to obtain the training/testing dataset are reported in Appendix F1. We evaluate all of algorithms by top-N ranking metrics including F1 (Karypis, 2001), NDCG (Weimer et al., 2008).
Recommenders. In this work, we mainly study the state-of-the-art sampling methods in terms of their effectiveness and efficiency. To uncover the features of different samplers, we consider representative factorization models (MF (Rendle et al., 2009) and FPMC (Rendle et al., 2010)) and one state-of-the-art deep model (MARank (Yu et al., 2019)) which can capture users’ temporal dynamic preferences. The details of these recommendation models are described in Appendix F2.
Baselines/Negative Samplers & Pairwise Loss. The baselines include Uni (Rendle et al., 2009) sampling a negative item from uniform distribution, POP (Mikolov et al., 2013) sampling negative items from a given distribution π, relative-order sampling methods, Dynamic Negative Sampling (DNS) (Zhang et al., 2013), LFM-D (Yuan et al., 2016) and LFM-W (Yuan et al., 2016), AOBPR (Rendle and Freudenthaler, 2014), CML (Hsieh et al., 2017), adversarial-like methods (SA) (Sun et al., 2019), PRIS (Lian et al., 2020), and IRGAN (Wang et al., 2017). Since the samplers are independent of the specific recommenders to work with, we take MF as the base model to study their features, then switch to more complicated models (i.e., FPMC, MARank). To keep the consistency of experimental setting for different baselines except IRGAN, we instantiate ranking objective `(·) as pairwise ranking loss (Rendle et al., 2009) for all baselines used in this work. The implementation detail of each method can be found in Appendix F3.

heading: 5.2 ITEM IMBALANCE VALUE EVALUATION (RQ1)
text: To evaluate the item imbalance value when applying different sampling methods, we count the number of appearance in positive and negative samples for each item. Then we track the evolution of
1https://www.yelp.com/dataset/challenge 2http://jmcauley.ucsd.edu/data/amazon/
the maximum and minimum imbalance value. Due to the characteristics of adversarial-like methods themselves such as SA, PRIS, IRGAN, it’s difficult to catch the evolution of items’ imbalance value. Therefore, we discard them and focus on the other methods. It is expected that non-uniform sampling methods can downgrade the maximum but increase the minimum imbalance value comparing with the UNI method. From the results shown in Figure 5 (results on other two datsets can be found in Figure 9 of Appendix F4), we can find that most of baselines reach the expectation. Combining with the overall performance shown in Table 1, we can see that all of the methods outperform the UNI method. From this point of view, alleviating the class-imbalance issue has positive effect on the performance of learned model. It’s also consistent with theoretical analysis in previous sections. It’s easy to understand that POP method reaches the expectation, because we already have empirical analysis result in Figure 2. However, dynamic sampling methods like DNS, LFM-W did not have a clear statement on sampling from a non-uniform distribution. If we connect this finding with the logic relation between class-imbalance issue and imbalanced item theorem, it could provide an important clue to understand that bias to items with larger prediction value will tend to sample imbalanced items. The proposed method VINS does not ideally increase the minimum class-imbalance value in Steam data. However, VINS keeps imbalance value larger than the other methods except POP, and with the help of adaptive sampling strategy, VINS achieves better performance than the baselines from the results shown in Table 1. From this point of view, alleviating the class-imbalance issue has positive effect on the performance of learned model. It’s also consistent with our theoretical analysis in previous sections.

heading: 5.3 RANKING PERFORMANCE (RQ2)
text: Table 1 summarizes the ranking performance of different sampling methods when applied to optimizing the same objective function. Dynamic sampling methods LFM-W and VINS significantly outperform the other baselines with a clear margin. While, the proposed sampler VINS is superior to the state-of-the-art method LFM-W. In terms of negative candidate selection, LFM-W depends on uniform distribution without any knowledge about the item property, while VINS selects the negative candidates with reject probability depending on item degree distribution. Ideally VINS can be more easier to obtain a violated negative sample than LFM-W according to Theorem 3.1 and 3.2. The experimental results validate the effectiveness of VINS which selects the negative candidates with reject probability motivated by class-imbalance issue.
5.4 TIME COMPLEXITY ANALYSIS (RQ2)
From Table 2, we can see that as the data scale up in size, all samplers will need more time. Especially, LFM-W needs over 10x more time comparing with stationary sampling methods, while VINS is more efficient than LFM-W. The average number of steps to find a violated negative sample is the key for the time complexity analysis. As discussed in Section 1, time complexity of dynamic sampling approaches like LFMW and VINS heavily depends on the search of a proper negative sample from massive trials. To further investigate the sampling process, we use the buffer technology for both methods to show the connection between the model performance convergence
and maximum steps to sample a violated item. The original LFM-W did not define a buffer, we set the maximum of sampling trials for LFM-W to 1024. The results shown in Table 5 of Appendix F4 demonstrate that VINS can converge to stable performance with less trials for each positive sample, while LFM-W needs a larger buffer with at least 1024 slots. From the results shown in Table 4 of Appendix F4, we can see that VINS can converge to the better solution than LFM-W, meanwhile needs only a small number of trials to find a violated item. This leads to over 30% training time saved comparing to LFM-W, shown in Table 2.

heading: 5.5 PERFORMANCE ON COMPUTATIONALLY EXPENSIVE METHODS (RQ3)
text: By far, we only apply the dynamic sampling methods on a linear recommendation model (MF). It is also interesting to evaluate their performance on more complicated models, for example FPMC and MARank, for next-item prediction. From the experimental results shown in Figure 6 we can find that VINS can save more training time (from 50% to 60%) than LFM-W ranging from shallow model FPMC to deep attentive model MARank, while reaching the best recommendation performance shown in Figure 7 and 10 (Appendix F4). This significant acceleration of recommendation model
training verifies that VINS is an effective dynamic negative sampling method. Especially for deep neural models training, VINS is a promising tool to select the most useful negative samples for achieving both significant reduction of training time and improvement of inference capability.

heading: 6 CONCLUSIONS
text: In this work, we systematically study the class-imbalance problem in pairwise ranking optimization for recommendation tasks. We indicate out the edge- and vertex-level imbalance problem, and show its connection to sampling a negative item from static distribution. To tackle the challenges raised by the class-imbalance problem, we propose a two-phase sampling approach to alleviate the imbalance issue by tending to sample a negative item with a larger degree and close prediction score to the given positive sample. We conduct thorough experiments to show that the biased sampling method with reject probability can help to find violated samples more efficiently, meanwhile having a competitive or even better performance with state-of-the-art methods.

heading: 7 REPRODUCIBILITY STATEMENT
text: The detailed information about the reproducibility is presented in Appendix F3. The way to obtain the experimental data can be found in Appendix F1. The pseudo-code of the proposed algorithm can be found in Appendix C.

heading: A. PROOF FOR THEOREM 3.1
text: Proof. With the given user-item graph G, both ∑ j∈I π(j) and |E| are constant. Let’s define a function f(x) = x 1−β ·c1 c2−x , where c1 = ∑ j∈I π(j) and c2 = |E|. Then we can have first-order derivative∇f(x) > 0, which means IV (i) > IV (j) if di > dj .

heading: B. PROOF OF THEOREM 3.2
text: Proof. Given latent space with d dimensions, there exists d - 1 mutually orthogonal vectors ~c2,~c3, · · · ,~cd and ~c1 = P̂ τ . Let ∆+i (t) = ∑ u∈Ni ∂`uij ∂xui P tu denote the gradients received when
item i acted as a positive sample, and ∆−i (t) = − ∑ u∈N−i ∂`uij ∂xui
P tu denote the gradients received when acting as a negative sample. It’s noted that if item i has a large imbalance value, the size of |Ni| is usually |N−i |, and vice versa. Then for any iteration n > τ , the embedding of item i is updated with gradient descent method as:
Pni = P τ i + η ∑ n≥t>τ (∆+i (t) + ∆ − i (t))
Then we can perform coordinate axis transform on P ti and P t u to c1, · · · , cd.
⇒ Pni = α1i~c1 + · · ·+ αdi~cd
+ η ∑
n≥t>τ ∑ u∈Ni ∂`uij ∂xui (t)(β1u~c1 + · · ·+ βdu~cd)
− η ∑
n≥t>τ ∑ u∈N−i ∂`uij ∂xui (t)(γ1u~c1 + · · ·+ γdu~cd)
Now we have P τi = α 1 i~c1 + · · · + αdi~cd and P tu = β1u~c1 + · · · + βdu~cd, ∂`uij ∂xui
(t) > 0, β1u > 0 as inner-product < P tu,~c1 > = < P t u, P̂ τ u >, and all other variables ∈ R.
⇒ Pni = α1i~c1 + · · ·+ αdi~cd + ∑ n≥t>τ λ1(t)~c1 + · · ·+ λd~cd,
where λk(t) = η (∑ u∈Ni ∂`uij ∂xui (t)βku − ∑ u∈N−i ∂`uij ∂xui (t)γku )
for k ∈ [1, d]. Since coordinates ~c1,~c2, · · · ,~cd are manually orthogonal.
⇒ lim n→∞ ||Pni ||2 = lim t→∞
(α1i + ∑
n≥t>τ
λ1(t)) 2||~c1||2 + · · ·
+ (αdi + ∑
n≥t>τ
λd(t)) 2||~cd||2
≥ lim n→∞
(α1i + ∑
n≥t>τ
λ1(t)) 2||~c1||2
≥ lim n→∞ (α1i + (n− τ) ·minn≥t>τλ1(t))2||~c1||2
And we have λ1(t) = η ( ∑ u∈Ni ∂`uij ∂xui (t)β1u − ∑ u∈N−i ∂`uij ∂xui (t)γ1u ) ,
where ∂`uij ∂xui (t)β1u > 0
For imbalanced items, the value of λ1(t) will be dominated by the size of Ni and N−i . If an imbalanced item with a very large imbalance value, then we could have λ1(t) > 0 with a relative high probability. Then we have lim
n→∞ (α1i + (n− τ) ·minn≥t>τλ1(t))2||~c||2 =∞.

heading: C. PSEUDOCODE
text: The detailed implementation of the proposed method VINS and its key component RejectSampler can be found in Algorithm 1 and 2, respectively.
Algorithm 1: VINS 1 Input: G = (V,E), max step κ, positive pair (u, i), max shot s, margin 2 Output: negative item j, and wui(ri) 3 selectedj = −1, maxj = −inf 4 for K ← 1 to κ do 5 do 6 j = RejectSampler(i, s,π) 7 while euj ∈ E; 8 xuji = xuj + − xui 9 if xuj > maxj then
10 maxj = xuj 11 selectedj = j
12 if xuji > 0 then 13 break;
14 ri = b Zmin(K,κ)c; 15 return selectedj , wui(ri);
Algorithm 2: REJECTSAMPLER 1 Input: item i, max shot s, weight distribution π 2 Output: selected item j 3 selectedj = -1, maxij = -1 4 for iter ← 1 to s do 5 j = randint(Z); 6 // in case of the extreme popular item i 7 if π(j) > maxi deg then 8 maxij = π(j); 9 selectedj = j;
10 reject ratio = 1 - min {π(j)π(i) , 1}; 11 if random.uniform() > reject ratio then 12 selectedj = j; 13 break;
14 return selectedj ;

heading: D. PROOF FOR LEMMA 4.1
text: Proof. 2k∑ s=1 1 s = 1 + 1 2 + 1 3 + 1 4 + 1 5 + 1 6 + 1 7 + 1 8 + · · ·+ 1 2k
≥ 1 + 1 2︸︷︷︸ 1 +( 1 4 + 1 4︸ ︷︷ ︸ 21 ) + (4× 1 8︸ ︷︷ ︸ 22
) · · · ( 2 k−1
2× 2k−1︸ ︷︷ ︸ 2k−1 )
≥ 1 + k 2

heading: E. DISCUSSION ON VINS

heading: E1. COMPLEXITY DISCUSSION
text: The most computationally expensive part of the proposed VINS model is the relative-order sampling procedure (line 4 to 13 in Algorithm 3). As discussed previously, finding a violated sample needs iterative comparison of the prediction value between a positive item and a negative item candidate. For each negative sample, the computation complexity is O(d), where d is the embedding size. Assume that the average number of steps to obtain a violated negative item is h′ and the maximum number of chances to reject a sampled item from the RejectSampler is s, then the time complexity of VINS will beO(|E| ·(d+s) ·h′). Usually, s d can be a very small number. Therefore, comparing the proposed approach with the state-of-the-art dynamic sampling method (Yuan et al., 2016), the time complexity difference will be the average number of steps h′ to find a violated item. From the experimental analysis, we find that the proposed RejectSampler significantly speeds up searching a violated sample.

heading: E2. CONNECTION TO EXISTING APPROACHES
text: Most of negative sampling approaches assume that the negative items follow a pre-defined distribution Q(j). According to the strategies to obtain a negative item, we can summarize the main kinds of negative samplers into three categories: user-independent, user-dependent, edge-dependent. The proposed approach (VINS) can be regarded as a general version of several methods by controlling the setting of hyper-parameters {κ, β}.
• user-independent: As the representatives, UNI (Rendle et al., 2009) and POP (Mikolov et al., 2013) initialize the Q(j) as a static distribution π. VINS can actually implement these two methods by setting κ = 1, β = 0 for UNI, and κ = 1, β ∈ [0, 1] for POP.
• user-dependent: This type of methods usually define a conditional distribution Q(j|u) which can capture the dynamics of learning procedure to some extent. Sampling from the exact distribution Q(j|u) will cost massive number of time in large-scale item database. Most of methods turn to defining a sub-optimal distribution based on a small number of candidate set. For example, DNS (Zhang et al., 2013) greedily selects the item with the largest predicted score xuj from the candidate set. Self-adversarial (SA) (Sun et al., 2019) method first sample candidates from uniform distribution, then calculate the weight of candidate through a softmax(xuj) distribution. Similar idea can be found in more recent proposed method PRIS (Lian et al., 2020). While, PRIS tries to select a negative sample from the distribution Q(j|u) through a importance sampling approach. By borrowing ideas from GAN, IRGAN (Wang et al., 2017) propose a two-agent minmax games, where generator G aborbs knowledge from discriminator, then selects negative samples from QG(j|u) = softmax(xuj) to update discriminator. From the view of distribution alignment, the generator actually attempts to learn distribution from the discriminator by taking Reinforcement Learning (RL) as the workhorse. However, RL methods usually need lots of training cases to update their policy, and sampling according to the policy distribution relies on the exact distribution QG(j|u) over the whole item set, which makes IRGAN become very slow to converge and difficult to tune the model. Moreover, the generator might have a distribution which could delay from the discriminator, which can lead to unqualified negative samples produced by the generator.
• edge-dependent: The methods mentioned above do not consider a fact that the ranking position of positive item i evolves as the learning procedure move forwards, in other words, the informative negative item set also changes. The edge-dependent methods aim at selecting informative negatives from distribution Q(j|u, i). As an initial study, Weston et al. (Weston et al., 2011) proposed the WARP loss by designing a rank-aware distribution ri = ∑ j∈V ui
I( + xuj ≥ xui). However, it’s impossible to get the exact ri for every single training sample (u,i) during the training stage. Fortunately the negative item j can be obtained through estimating a geometric distribution P (X = k) parameterized with p = riZ . There’re many works that are based on WARP and all of them follow the same idea as WARP to estimate the P (X = k) from a uniform distribution. VINS also inherits the basic ideas from WARP but modifies the target distribution as ri = ∑ j∈V ui
π(j)I( + xuj ≥ xui), and proposes to estimate it through an importance sampling method after theoretically investigating the existing class-imbalance issue and its potential influence. As the state-of-the-art variant of WARP loss, LFM-W advances WARP with a normalization
term. However, estimating the geometric distribution from a uniform distribution makes LFM-W need lots of steps to find a violated sample. Moreover, LFM-W might find sub-optimal negative sample without considering the class-imbalance issue. LFM-W can be equivalent to VINS by setting β = 0 and replacing the weight function wui(ri) as a truncated Harmonic Series function, i.e. wui(ri) = ∑drie z=1 1 z .

heading: E3. RANK ESTIMATION BIAS DISCUSSION
text: Let Pr(X = k) = p(1 − p)k−1 denote geometric distribution with parameter p, and {X1, X2, · · · , Xn|Xi ∈ N} to be the observations. The optimized estimation of p by maximizing the likelihood function will be p̂ = 1/X , where X = ∑n i=1Xi/n. Now we can obtain the expectation over the estimated parameter, i.e. E[p̂] = E[1/X]. When estimating the rank-aware variable ri, we usually conduct single experiment, that is n = 1. In Lemma 7.1, we demonstrate that it lead to a biased estimation of the true rank position. Fortunately, we find that the estimation error will become smaller as the positive sample get better and better ranking position as the learning procedure move forwards. Lemma 7.1. For special case n = 1, E[p̂] will be larger than p, which means p̂ is not an unbiased estimation.
Proof.
E[p̂] = E[1/X1] = ∞∑ k=1 1 k p(1− p)k−1
= p+ ∞∑ k=2 1 k p(1− p)k−1
(2)
for p ∈ (0, 1) in this case, the above sum term is strictly positive.
Since we can get the estimated rank position as r̂i = p̂i · Z. To save computational cost, we usually run one time i.e., n = 1 to estimate the mass variable in dynamic sampling approach. Under this scheme, the estimation expectation E[r̂i] = E[p̂ · Z] = E[Z/X1]. If we fold out this equation, we can get the following induction:
E[ Z
X1 ] = Z ∞∑ k=1 1 k p(1− p)k−1
= ri + ∞∑ k=2 ri k (1− ri Z )k−1 > ri
(3)
where ri = Z · p denotes ground truth value. Let h(ri) = ri + ∑∞ k=2 ri k (1 − ri Z )
k−1 represent a function of ri. It’s very hard to analyze the gradients of function h(·). However, we need answer what’s the exact estimation bias as the change of idea ranking ri. To answer this question, we turn to analyze a ratio function ψ(ri) = (h(ri)− ri)/ri = ∑∞ k=2 1 k (1− ri Z )
k−1. Comparing to directly analyzing original function h(ri), ψ(ri) is a monotone decreasing function. Based on the feature, we empirically illustrate the change of estimation bias ratio and the rank variable ri. From Figure 8 we can see that as the item ranks higher, the estimation error will be smaller.

heading: E4. FALSE NEGATIVE ISSUE
text: With the given partial knowledge, in particular only implicit feedback from users, it’s very difficult to discriminate false negative and true negative items. It has become a common challenge for designing a negative sampler (Ding et al., 2020). In this paper, we do not focus on studying how to overcome the “false negative issue”, but the proposed adaptive strategy could have a mechanism to avoid to push “false negative” item far away from the users. According to definition of weight wui(ri), the more difficult to sample a violated negative item, the smaller weight (wui(ri) → 0) it is, which suggests that the rank position of positive item i is learned well. For this item i, even the sampled item is a false negative, it will get a very small gradient (almost zero gradient) to move away from the target user. We’d like to leave this challenge for future work.

heading: F. EXPERIMENTAL SETTING AND ANALYSIS

heading: F1. DATASETS
text: The detailed statistics of the employed datasets can be found in Table 3. Following the processing in (Tang and Wang, 2018; He and McAuley, 2016), we discard inactive users and items with fewer than 10 feedbacks since cold-start recommendation usually is regarded as a separate issue in the literature (He and McAuley, 2016; Rendle et al., 2010). For each dataset, we convert star-rating into binary feedback regardless of the specific rating values since we care more about the applications without explicit user feedbacks like ratings (He et al., 2017a; 2016). We split all datasets into training and testing set by holding out the last 20% review behaviors of each user into the testing set, the rest as the training data.

heading: F2. RECOMMENDERS
text: • Matrix Factorization (MF) (Rendle et al., 2009): This method uses a basic matrix factorization model as the scoring function. It can be regarded as a shallow neural network with a single hidden layer which takes user and item one-hot vector as input (He et al., 2017b).
• Factorizing Personalized Markov Chains (FPMC) (Rendle et al., 2010): It’s a method that combines the MF and factorized Markov Chain over item sequence for next-item prediction.
• MARank (Yu et al., 2019): It incorporates both individual- and union-level item relation into a deep multi-order attentive encoder, instead of only using factorized item transition probability.

heading: F3. REPRODUCIBILITY
text: All methods are optimized with Adam and implemented in Tensorflow with a GeForce GTX 1080Ti GPU. We share the parameter setting of the optimizer for all baselines and experiments in this work, with default learning rate η = 0.001. We use grid search to examine the hyper-parameters, including the embedding size from {16, 64, 128}, λ from {0.0005, 0.001, 0.005, 0.01}. Different baselines have their own hyper-parameters. For decay factor β in POP sampler, the search space includes {0.25, 0.5, 0.75, 1}. Both CML and DNS need a number of negative candidates. In this work, a small number e.g., 10 or 20 gives good enough results as suggested by the authors (Zhang et al., 2013; Hsieh et al., 2017). LFM-D needs two hyper-parameters, the number of negative candidates, and the expected sampling position. For the first one, it is the same as DNS, but usually needs a little larger number, e.g., 20 in this work. The expected sampling position can be obtained by multiplying the number of negative candidates with a ratio factor ρ. The search space for ρ was {0.01, 0.05, 0.1, 0.5}, and ρ = 0.1 gives the best results. AOBPR also needs to set the ratio factor ρ, and produces best results with ρ = 0.1. LFM-W only has a margin parameter besides the optimizer parameters and regularization term. This parameter actually varies as the type of employed optimizer and the validation model. We search the best choice from {1, 2, 3, 4} for both LFM-W and VINS. For VINS, we need to search the best choice for buffer size κ and decay factor β. In this work, we find that κ = 64 or 128 is good enough according to the analysis results. In terms of IRGAN, we implement this method with the published code 3 and suggested setting. In self-adversarial method (SA) 4, the discriminator and generator are the same prediction model. It creates an adversarial item by aggregating a number of negative items. In this work, we tried different settings from {64, 128, 256}, and select the best value i.e. 256. We follow the suggested setting by the authors to set up PRIS (Lian et al., 2020).

heading: F4. EXPERIMENTAL ANALYSIS
text: Due to the limited space in the main content, we will present additional experimental analysis results in this section. More specifically, we can find the changes of maximum/minimum imbalance value for the other two data in Figure 9. In Table 4 and 5, we can find the the comparison results between VINS and the best baseline LFM-W to show that the proposed method VINS is superior to LFM-W in terms of both efficiency and effectiveness. Figure 10 summarizes the additional ranking performance on the other two datasets.

Review summaries:
For pair-wise learning-to-rank problems, it often suffers from class imbalance problem when constructing training data where negative class examples are much more frequent then positive class examples. Negative example sampling is an important differentiator on training and classifier performance. this paper proposed a method on negative class sampling by considering the degree of vertexes. It proposed a rejection function in order to sample with higher probability from high degree vertex instead of using edge level random sampling. It provided both theoretical analysis and experiments on real world datasets to demonstrate the effectiveness on the proposed sampling approach.

This paper investigates personalized ranking from implicit feedback where we leverage a set of positively labeled data (for which interactions exist such as clicking, purchase etc) and use all the items with no explicit feedback as negative instances and aim to learn a ranking model for recommendation. The idea is to minimize a loss over triplets (u,i, j) over users, a positively labeled instance and a negatively labeled instance to learn the embeddings for items and users.   The main observation in this paper is that in addition to known unbalancedness issue on edge level (proportion of positive instance to negative instance), the existing methods also suffer from vertex-level imbalance problem due to fact that due to sampling, the number of times an item appears as positive and negative is disproportionate. In particular,  popular items with degree (positiveness) greater than average item degree are under-sampled as negative samples, while cold-start items with degree less than average degree are over-sampled as negative instances. This in turn makes the norm of learned embeddings for popular items towards infinite after a certain training iterations. This issue even occurs if one utilizes an under-sampling/oversampling to solve the edge-level imbalance issue. The observations are supported both theoretically and empirically. 

This paper proposes to improve the negative sampling process for training pairwise ranking models in personalized recommender systems. Negative sampling plays an important role in the above application, as it can largely impact the model performance in terms of both training efficiency and recommendation accuracy. Authors first analyze the vertex-level imbalance problem that exists in current sampling-based methods, i.e., popular items are unevenly sampled w.r.t. their chances as positive and negative. They observe that this may cause the imbalanced distribution of embedding norms between popular and long-tailed items, which can possibly harm the training efficacy and efficiency. To cope with this problem, this paper proposes a simple but effective negative sampling method. The core idea is to choose a negative candidate with larger popularity than the given positive item. To maintain sample quality, the dynamic relative rank position of positive and negative items is also considered, which has already proven to be useful in previous works. Specifically, the proposed VINS method is achieved through a bias sampler with reject probability, which cooperates with an item buffer to enable efficient sampling of informative instances. Empirical results on several real-world datasets demonstrate its superiority on both efficiency and effectiveness.