A Simple and Debiased Sampling Method for Personalized Ranking
Authors: Lu Yu
Shichao Pei
Chuxu Zhang
Xiangliang Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: personalized ranking
class-imbalance
negative sampling
deep learning

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 \emph{\underline{Vi}tal \underline{N}egative \underline{S}ampler}, 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. 

Under review as a conference paper at ICLR 2022
A SIMPLE AND DEBIASED SAMPLING METHOD FOR PERSONALIZED RANKING
Anonymous authors Paper under double-blind review
ABSTRACT
Pairwise ranking models have been widely used to address various problems, such as recommendation. The basic idea 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 flas--ibalance issue. Our theoretical anal- ysis shows that current sampling-basd -ased 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, efficient Vital Negative Sampler, to alleviate the class-imbalance issue for pairwise ranking mod- els optimized by gradient methods. The core of VINS 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 demon- strate 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.
INTRODUCTION
Offering personalized service 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 U I contains user set U and item set I, and E denotes the edge set. Each edge eus E E' denotes an observed interaction between user u and item í. Users' preference on items is modeled by pairwise loss functions with the assumption that items with interactions from user are of more interest to this user than those without interactions. The loss function thus involves pairwise comparison between an observed (positive) edge Cui E E and unobserved (negative) edge euj & E. The optimization process thus suffers from the class- imbalance issue bbecaus in practical scenario, the number of observed (positive) edges are always much less than the unobserved (negative) ones. The imbalance between eut 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 fam- ilies: using stationary sampling or using dynamic sampling. Approaches in the former family usu- ally start from the edge-level class-imbalance issue through under-sampling negative edges from pre-defined stationary distribution (Rendle et al.) 2009 Rendle and Freudenthaler (2014), or over- sampling positive edges by creating instances through the social connection (Chen al. 2019). However, they ignore that class-imbblance issue also exists in vertex side because each vertex can appear both positive and negative edges. Through some basic statistical analysis, we acquire some interesting findings. that is, the vertex degree has positive impact on verter-level imbalance problem. If we sample negative instances from a stationary distribution, those popularity vertexes with degree greater than average vertex degree are under-sample as negative samples, while "cold- start" 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 Iaa) and [[b.. From Figure (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 distinguished well from the positive item, shown in Figure bb) At this time, large portion of

---

Under review as a conference paper at ICLR 2022
items list
itemss list
20% useful negative items
uniform random walk
biased random walk
top
posiive Rem
90% useful negative items
after iterations
80% useless negative Items
positive hom
bottom
(c)
(d)
Figure I: Illustration of finding useful negative items for pairwise loss optimization: (a) is the initial stage of optimization when it's easy to get one negative item; (b) shows that useful negative items more difficult to get the learning process moves forwards: (c) sampling negative items from uniform distribution equals to do unbiased random walk on fully connected item-item graph; (d) presents alternative solution depending on a bias random walk.
the negative items are useless for pairwise loss optimization, because they already rank lower than the positive item.
Recently dynamic sampling approaches (Weston al. 2011 Yuan 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 sam- pling candidate from uniform distribution; 2) they have to find 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 faster dynamic negative sampler for the personalized ranking task. We find that sampling from uniform distribution can be regarded as a random walk with transition probability matrix P for arbitrary node pair in a fully connected item-item graph, which is presented Figure [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 [d). Through theo- retical analysis, and walking with a biased transition matrix P is to tackle the class-imbos imbalance issue. To achieve this goal, it is essential to first dissect the impact of dlas-iibbllance 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 faster dynamic sampling approach boost ranking quality? We answer the above ques- tions 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. (009)), 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 phe- nomenon 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:
find that one of the potential solutions to decode the biased transition process
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 phe- nomenon and vanishing gradient at the output loss.
To address the inss-immaaaace and vanishing gradient problem, we design an adaptive negative sampling method with 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 offe--of-the-an the-art art dynamic sampling methods.
2

---

Under review as a conference paper at ICLR 2022
2 RELATED WORK
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 very large set of all remaining items (negative as majority class). Pioneering work proposed in (Rendle et al.] (009) 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 fact that each item has its own properties, e.g., degree, betweenness. (Rendle and Freudenthaler 2014) considered vertex properties and pro- posed to sample 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 aa) and bb).
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 select- ing vital negative instances. As a pioncering work. (Weston 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 violated negative items become very dif- ficult (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 uniform distribution makes LFM-W need lots of steps to find a violated sample. Morcover, LFM- W 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 proper setting.
3 CLASS IMBALANCED ANALYSIS
Let's use G == (V, to represent a user-item interaction graph, where vertex set V = UU contains users U and items I, and for E denotes an observed interaction (egg. click, purchase behaviors) between user and item i. The relationship between user u and item i can be measured by a factorization focused method, known as Tui Pa P,, where Pa = f(u(O=) E Rd and P. giil0.) E IRd are the representation of user and item generated by deep neural network f() and g(-) with parameters 02 and 0,, 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 E (U x I E) as negative ones. Then set of triplets D- {(u, j, jeeus E E, euj E (U x 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, zus Tuj. To model such contrastive relation, one popular solution is to induce pairwise loss function as follows:
L(G) =
Σ Wui (Tuis Tuy), (u,jj)ED
(I)
where (-) can be hinge, logistic or cross entropy function that raises an effective loss for any triplet with incorrect prediction (i.e. Zuj > Taii) that violates the pairwise assumption. Wai is the a weight factor which shows the complexity to discriminate the given comparison sample. The optimization of Equation (1) involves extreme dlass-imbalance issue, because in practical scenario, the number of unobserved interactions Eaj & E (negative) is usually extremely larger than the observed cus E E (positive). The imbalance between eut 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 practical solution for it (Rendle et al. 2009 Mikolov et al.
3

---

Under review as a conference paper at ICLR 2022
2013). Let's take the most popular strategy of under-sampling negative edges example. For given positive edge eus E E. we can sample a negative edge by fixing user u E U. then sample one item j E I, Cuj E' with replacement from static distribution
{ I}. where x(i)
3 E [0, 1] denotes a weight function of item degree d4. Then we can optimize the objective function in Equation (1) with the constructed pairwise samples Î E 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 address these challenges with an adaptive sampling method.
3.1 VERTEX-LEVEL IMBALANCE FROM SAMPLING (Q1)
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). 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 negative one for other users. Vertex-level imbalance happens when the number of times that a vertex appears in observed edges extremely smaller or larger than that in the unobserved ones.
Assuming that in each iteration of optimizing Equation ( we will sample negative edge for each observed edge eui. With a given graph G with [ا] 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] d, edges
with probability p(i) when sampling with a static distribution π defined as p(i) x1)/ Σ jEl T( Then, the expected number of times that the item acts as negative sample is p(i) ( d.). Af-
terwards, we define the imbalance value (LV) of item as: (i) p(()-([P] d,j
d
d Sier x()) [F|-d,
Through theoretical analysis, we find that imbalance value positively correlated to item degree.
Theorem 3.1. By sampling negative items with a static distribution for two items with d: > dj. the imbalance value of item i is larger than item j.
{x(i)= = d 1],
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 given graph G. As special case, [ O, we have (V)
Vertex Imbalance Value
MoronadePe
100
Max Imbulannce Value
Yelp
-d Let's set [V = 1,
d.-
we can see that d: = l/+11
[E| ~
[E| which is exact the aver- [Z]
0.6
age item degree. If an item's '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 pop- ular vertexes are under-sampled as negative samples, while "cold-start" vertexes are over-sampled. For different setting of B, the situation will be different. We illustrate the maxi- mum and minimum imbalance value in Figure[] obtained by the empirically calculated (i) from different decay factor B. We can see that a proper choice of decay factor / can reduce the maximum imbalance, mean- while increase the minimum value.
40-
20-
0.2
0.0
0.0
0.8
1.0
Figure 2: Maximum (solid line) and minimum (dash line) imbal- ance value along with different de- cay parameter 3 on Yelp and Ama- zon Movies& Tv datasets.
real datasets with
3.2 IMPACT OF CLASS-IBBALANCE (Q2)
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 follows (with complete proof presented in the Appendix B):
4

---

Under review as a conference paper at ICLR 2022
Theorem 3.2. [Imbalanced Item Theorem] Suppose there exists imbalanced item i with (V 1. such that for all neighbor users u E N₁ Zui 2 Zuj for all other observed item j of user u. Furthermore, after certain iterations т. the representation Pus u E N₁ converges certain extent. That is, there exists vector pt in all iteration > т, inner-praduct (Pt, P.) 0. Then the norm of P: of the imbalanced item will tend to grow to infinity if 8u.u
D6 > for all i with Tui Fuj.
Frequency gathering phenomenon. The Imbalanced Item Theorem implies that the learned embeddings of items will appear certain pattern that closely related 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 's no vertex-leve imbalance problem in the user side, the learned user embeddings are inde- pendent on the degree information. From Figure 33 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 3 = 1 for sampling from a static distribution π, with which the vertex-level imbalance can be perfectly mitigated. However, comparing with the setting 3 O, it can significantly downgrade the prediction performance, because the learned item embeddings can't keep their structure role and proximity very well. suggests that controlling the the ranking performance, but still need to achieve trade-off between keeping the graph structures and alleviating the negative impact of class-imbalance problem.
problem might help to improve
Yelp-ttan-Vaau Vinua
Yelp-Jber Vieus -WOS
40
23-
70-
-55
-20-
-50
-00
80
-50
-30
25
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- 25%, green-the 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
Movies&iTy
Yolp
0.6
4poch-1
spoch-2
4poch-3
spach-3
apoch.5
spach-5
spoch-13
cpach-10
gradient update for model parameters can be carried out for a given pairwise sample (u, ().. 0.1
opoch:20
epach-20
spoch-50
epach-50
0.1
After t > T iterations, the model parameters Og can be updated with stochastic gradient de- scent method: 0++1 0 Ai
0.0
rankindox
Figure 4: Illustration to show the connection be-
30.
tween class- -tas-iimalannee and gradient vanishment. The rank index stands for the ranking position of imbalance value (IV) in ascending order. We use average gradient magnitude À as the y-axis.
ac;
where XN; Jzw. and 77 denotes the learning ōrus rate, and 89, represents a gradient backprop- agation operation according the chain rule, The value of Ai depends on the type of loss function. If we use logistic loss as an instance, City (Z Faj) = In -ujj), where (zz) is the sigmoid function and AN; = =11- (x Zuji) )). According the Imbalanced Item Theorem, the norm of learned embeddings of those imbalanced items will become extremely large. Let's fold out Tai = Pa P: P.ll| ||P:|| cos(Pa. P.). If positive item suffers from imbalanced issue and has a large norm, i.e., | > [|P the relevance prediction for user 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 XY₁ + 0 according gests that massive number of pairwise samples are meaningless for updating the model, and only small number of them are valuable. Following the idea in pioneering work (Rendle and
3.1 and Theorem 3.2 It sug-
5

---

Under review as a conference paper at ICLR 2022
Freudenthaler 2014). we conduct empirical study on two experimental data to show the connec- tion between gradient vanishment and item class -ias--imal issue. From the results shown in Figure
4 we have the same observation (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 and and The- orem 3.2, we can see that the reason why popular items tend to have smaller gradient magnitude has positive relation to the class class-imbalance issue.
4 VITAL NEGATIVE SAMPLER
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.
4.1 SAMPLING WITH REJECT PROBABILITY (REJECTSAMPLER)
Combining Theorem 3.1 and the frequency gathering phenomenon, we find that there exists positive connection between item degree and the learned embeddings. We thus design a negative sampling approach which tends to sample 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 cais we sample negative item j with reject probability - min mi/) 1}. With this reject probability, .(()
we can increase the chances of popular items exposed as negative samples while downgrading the chances of long-tailes tailed items. We can see that the RejectSampler actually equals to a biased random ([d to choose the next step with given transition matrix P*, where
walk as shown in Figure
min (1) m()), 1-
1} if i +
P
In fact, RejectSampler can adapt beyond the item degree
P if i i=j
information to define the reject probability, resulting a different transition matrix Pt, The detail of RejectSampler is illustrated in Algorithm of Appendix C.
4.2 ADAPTIVE NEGATIVE SAMPLING
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 X - 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 in the algorithm). Note
firstly used to sample an item that not connected to user u (line that item j sampled from RejectSumpler is not guaranteed to be negative for user i. Therefore RejectSampler re-called if j is connected to u (euj E F.). The next step is to evaluate the sampled item is a violated one, which satisfies + Tuj 2 Tui, where is margin (line 8 to 13 in the algorithm). In fact, there can be a set of violated negative samples, noted as V."" = {ile + Taj 2 Tuis Cuj & E}. The hardness of searching violated negative sample increases when the positive item i is ranked higher. This hardness is reflected as the weight factor was in Equation (I]. For the positive item with relative high rank position, should generate small weight Wais while give large weights to those lower-ranked ones. We thus define the weight as (r:().). where r; = Ejevy =()I[(e Fuj Fui) is the rank-aware variable of item T(x:) is indicator function. From the definition of ra. we can see that the smaller ri is, the high-rank position item i is. Previous work (Weston et al.] (011)) takes truncated Harmonic Series function to generate the weight was(r,) (r;) - : 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 [ for each sample. Inspired by the lower bound of truncated Harmonic Series (shown in Lemma 4. we
derive efficient way to calculate the (rx(rx) with complexity O(1).
Lemma 4.1. For a given l E N, truncated Harmonic Series Σne 2 1+ 5. When = 0, the equality holds.

---

Under review as a conference paper at ICLR 2022
The complete proof of Lemma 4.1 is described in the Appendix D. According to this lemma, divide the rank list into k chunks, each of which has size 2 (growing with the chunk number k), and is attached with weight (i.e. 0.5). For the rank variable r,, we can derive the chunk number based on the Geometric progression formulation, which leads to [* [=][og2(r; + +1). Since first chunk has weight 1, we subtract 1 in the definition. More specifically, we define (ri(r,) as 1+0.5-( (ao.a--([ooogrrrr. (oga(ry-1)-1)
where 0.5 is the weight for each chunk with size 2 and Z EiEs m()). However, T; = Σeev.- T()) is difficult to attain. We use an item buffer fer with size x to store every sampled negative candidate j. Then, r4 can be approximated as -msn(K.n]. 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 bu fer in descending order based on Tuj. shown in Algorithm| of of Appendix C. With the selected negative item by VINS, we can construct pairwise sample (u. 2. to train the ranking model. The employment of RejectSampler in VINS has two benefits. First, it considers the class- dass-imbalaane 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 the buf ser. More discussion about the characteristics of the proposed method and its connection to previous methods can be found in Appendix E.
follows: (us(r;) = 1+0.6-([+ ([~ [ogg (2+1))))
LL L (
rr R
5 EXPERIMENTS
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?
5.1 EXPERIMENTAL. SETTINGS
Datasets and Evaluation Metries. To validate the proposed sampling method, we use four publicly available datasets, from Yelp Challenge (13th round) Amazon and Steam (Kang and McAuley, 2018). The detailed information about the datasets and the way 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, consider representative factorization models (MF (Rendle et al.) 2009) and FPMC (Rendle et al. 2010)
and one satee-of-thh-aat 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 nega- tive items from a given distribution π,, relative-order sampling methods, Dynamic Negative Sam- pling (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. (207)). Since the sam- plers 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 E(-) 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.
5.2 ITEM IMBALANCE VALUE EVALUATION (RQ1)
To evaluate the item imbalance value when applying different sampling methods, count the num- ber of appearance in positive and negative samples for each item. Then we track the evolution of
7

---

Under review as a conference paper at ICLR 2022
NoviesSTV
Novie:STV
Yelp
55-
011
815
P32
01g
0.8
pmp
0.6
LYN0
UH00
LTM-3
JMC
12M
VW55
0.0
0.0
150
50
100
350
Figure 5: Evolution of maximum/minimmmm imbalance value of different sampling methods. Table I: Ranking performance when using different sampling methods with MF as the recommender for top-10 recommendation. The best marked with underline, the second best is marked by *
Method
Sampler
Yelp
To
Vinyl
Steam
F1
NDCG@
Fl
NDCG@ 10
F
NDCG@10
NDCG@
Item-KNN
0.0155
0.0205
0.0178
0.0258
0.0191
0.0261
0.0296
0.0409
Uni
0.0135
0.0168
0.0146
0.0186
0.0195
0,0249
0.0338
0.0457
POP
0.0129
0.0161
0.0179
0.0232
0.0229
0.0301
0.0333
0.0472
AOBPR
0.0140
0.0173
0.0153
0.0197
0.0211
0.0278
0.0834
0,0463
CML
0.0177
0.0216
0.0133
0.0179
0.0205
0.0276
0.0239
0.0317
MF
PRIS
0.0158
0.02.0
0.0184
0.0239
0.0252
0.0351
0.0374
0.0502
SA
0.0161
0.0199
0.0159
0.0206
0,0243
0,0326
0.0347
0.0483
IRGAN
0.0188
0.0235
0.0206
0.0269
0.0263
0.0348
0.0358
0.05 12
DNS
*0.0197
*0.0247
+0.0211
*0.0276
*0.0275
e0.0366
0.0398
0.0551
LFM-D
0.0187
0.0234
0.0204
0.0267
0.0269
0.0354
*0,0406
*0006
LFM-W
0.0202
0.0255
0.0236
0.0313
0.0301
0.0401
0.0414
0.0569
VINS (ours)
0.0222
0,0281
0.0245
0.0326
0.0310
0,0410
0,0429
0.0594
Improvement
ours vs
9.9%
10.2%
3.81%
4.15%
2.99%
2.24%
3.62%
4.39%
ours vs second
12.7%
13.7%
16.1%
18.1%
12.7%
12.0%
5.66%
5.88%
the maximum and minimum imbalance value. Due 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 expected that non-uniform sam- pling methods can downgrade the maximum but increase the minimum imbalance value comparing (results with the UNI method. From the results shown Figure (resultss on other two datsets can be found in Figure of Appendix F4), we can find that most of baselines reach the expectation. Combining with the overall performance shown in Table [ 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 previous sections. It's easy understand that POP method reaches the expectation, because already have empir- ical analysis result in Figure 2 However, dynamic sampling methods like DNS, LFM-W 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 im- balanced items. The proposed method VINS does not ideally increase the minimum class-imbalane value 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 From this point of view, alleviating the class-imbs iaas-imbaee issue has positive effect on the performance of learned model. It's also consistent with our theoreti- cal analysis previous sections.
5.3 RANKING PERFORMANCE (RQ2)
Table T summarizes the ranking performance of different sampling methods when applicd to opti- mizing 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 the state-of-the-at 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 nega- tive candidates with reject probability depending on item degree distribution. Ideally VINS can be more easier to obtain a violated negative sample than LFM-W W according to Theorem [. 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)
8

---

Under review as a conference paper at ICLR 2022
Yolp
Stoan
Time (m))
Auceogg Tere (n))
Aeeooa Time 0e)
MMC
UNI
VINB
LFNW
LFM-
ViN
LFM-W
Figure 6: Time complexity with the growth of model complexity.
From Table 2 we can see that as the data scale up in size, all samplers will need more time. Especially, LFM-W W needs over 10x more time comparing with stationary sam- pling methods, while VINS is more effi- cient 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 ! time complexity of dynamic sampling approaches like LFM- W 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 be- tween the model performance convergence and maximum steps sample violated item. The original LFM-W W did not define buffer, we set the maximum of sampling trials for LFM-W to 1024. The results shown in Ta Appendix F4 demonstrate that VINS can converge 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 the better solution than LFM-W. meanwhile needs only small number of trials to find a violated item. This leads to over 30% training time saved comparing to LFM-W. W. shown in Table 2
Table 2: Time complexity comparison with different data scale in terms of average running time per epoch in minutes and ratio to the simplest method "Uni".
Sampler Steam (smallesti) CD&& Vinyl Movics&Tv Yelp (largest) Uni
0.07 (Ix)
0.1 (1x)
0.16 (1x)
0.47 (Ix)
(1.28x)
0.13 (1.3x)
0.2 (1.25x)
0.58 (1.23x)
AOBPR
0.05 (0.71x)
0.23 (2.3x)
(2x)
1,98 (4.21x)
0.33 (4.71k)
0.33 (3.3x)
(3.1x)
(2.61x)
PRIS
1.12 (16x)
[1.38 (13.8x)
2200 (12.9k)
6,25 (13.3x)
0.48 (6.85x)
0.66 (6.6x)
[0.92 [0.92 (5.75x)
2.76 (5.87x)
IRGAN
3.85 (55x)
|4.54 (45.4x)
5.6 (35x)
23.4 (49.8x)
DNS
0.28 (4x)
(4.4x)
0.72 (4.5x)
2.1 (4.46x)
LFM-D
0.38 (5.42x)
0.49 (4.9x)
1.1 (6.87))
1,86 (3.95x)
LFM-W
0.35 (5x)
11.58 (15.8x)
(10.3x)
4.78 (10.1x)
VINS
0.25 (3.57x)
|1.08 (10.8x)
1.12 (6.37x) 3.05 (6.48x)
5.5 PERFORMANCE ON COMPUTATIONALIY EXPENSIVE METHODS (RQ3)
By far, we only apply the dynamic sampling methods
linear recommendation model
1525
3.53
(MF). It is also interesting to evaluate their per- formance on more complicated models, for ex- ample FPMC and MARank, for next-item pre- diction. From the experimental results shown in Figure 6 we can find that VINS can save more training time (from 50% to 60%) than &
2
gasss
5003
LF14
VG
UPWAY Movieah:
VNN
MovieakTe
LFM-W ranging from shallow model FPMC to 401 deep attentive model MARank, while reaching the best recommendation performance shown in Figure 7 and 10 (Appendix F4). This sig- nificant 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 select the most useful negative samples for achieving both significant reduction of training time and improvement of inference capability.
0.81
VHS
(P
VNS
Ranking performance on F1/NDCG metric of shallow and deep models.
Figure
CONCLUSIONS
In this work, we systematically study the hlas-iimbalance 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 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 -h-he-rrt methods.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
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.
REFERENCES
Jiawei Chen, Can Wang, Sheng Zhou, Qihao Shi, Yan Feng, and Chun Chen. 2019. Samwalker: Social recommendation with informative sampling strategy. In The World Wide Web Conference (WWW). 228-239.
Long Chen, Fajie Yuan, Joemon M Jose, and Weinan Zhang. 2018. Improving negative sampling for word representation using self-embedded features. In Proceedings of the Eleventh ACM Inter- national Conference on Web Search and Data Mining (WSDM). 9077
Jingtao Ding, Yuhan Quan, Quanming Yao, Yong Li, and Depeng Jin. 2020. In Advances in Neural Information Processing Systems (NeurIPS). 1094-1105.
Jingtao Ding, Guanghui Yu, Xiangnan He, Fuli Feng, Yong Li, and Depeng Jin. 2019. Sampler de- sign for bayesian personalized ranking by leveraging view data. IEEE Transactions on Knowledge and Data Engineering (TKDE) (2019).
Ruining He, Wang-Cheng Kang, and Julian McAuley. 2017a. Translation- based Recommendation. In Proceedings of the eleventh ACM Conference on Recommender Systems (RecSys). 161-169
Ruining He and Julian McAuley. 2016. Fusing similarity models with markov chains for sparse quential recommendation. In Proceedings of IEEE 16th International Conference on Data Mining (ICDM). 191-200.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017b. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web. 173-182.
Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. 2016. Fast matrix factoriza- tion for online recommendation with implicit feedback. In Proceedings of the 39th International Conference on Research and Development Information Retrieval (SIGIR). 549-558.
Ko-Jen Hsiao, Alex Kulesza, and Alfred Hero. 2014. Social Collaborative Retrieval. In Proceedings of the Seventh ACM International Conference Web Search and Data Mining (WSDM). 293- 302.
Cheng- Kang Hsieh, Longqi Yang, Yin Cui, Tsung-Yr Yi Lin, Serge Belongie, and Deborah Estrin. 2017. Collaborative metric learning. In Proceedings of the 26th International Conference on World Wide Web (WWW). 193-201.
Wang-Cheng Kang and Julian McAuley. 2018. Self-attentive sequential recommendation. In Pro- ceedings of the 2018 IEEE International Conference on Data Mining (ICDM). 197-206.
George Karypis. 2001. Evaluation of Item-Based Top-N Recommendation Algorithms. In Pro- ceedings of the 10th ACM on Conference on Information and Knowledge Management (CIKM). 247-254.
Guang-He Lee and Shou-De Lin. 2016. LambdaMF: Learning Nonsmooth Ranking Functions in Matrix Factorization Using Lambda. In Proceedings of the 2016 IEEE International Conference on Data Mining (ICDM). 823-828.
Defu Lian, Qi Liu, and Enhong Chen. 2020. Personalized Ranking with Importance Sampling, In Proceedings of The Web Conference 2020. 1093-1103.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg Corrado. and Jeffrey Dean. 2013. Distributed Rep- resentations of Words and Phrases and Their Compositionallty. In Proceedings of the Advances in Neural Information Processing Systems (NeurlPS). 3111-3119.
10

---

Under review as a conference paper at ICLR 2022
Steffen Rendle and Christoph Freudenthaler. 2014. Improving Pairwise Learning for Item Recom- mendation from Implicit Feedback. In Proceddings of the Seventh ACM International Conference on Web Search and Data mining (WSDM). 273-282
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian Personalized Ranking from Implicit Feedback. In Proceedings of the Twenty-Fiftt Con- ference on Uncertainty in Artificial Intelligence (UAI). 452-461.
Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt- Schmidt-Thieme. 2010. Factorizing personal- ized markov chains for next-basket recommendation. In Proceedings of the 19th international conference on World Wide Web (WWW). 1--20...
Zhiqing Sun, Zong Deng, Jian- Yun Nie, and Jian Tang. 2019. RotatE: Knowledge Graph Em- bedding by Relational Rotation in Complex Space. In Proceedings of the Seventh International Conference on Learning Representations (ICLR).
Jiaxi Tang and Ke Wang. 2018. Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Dining (WSDM). 565-573
Bo Wang, Minghui Qiu, Xisen Wang. Yaliang Li, Yu Gong, Xiaoyi Zeng, Jun Huang, Bo Zheng, Deng Cai, and Jingren Zhou. 2019. A Minimax Game for Instance Based Selective Transfer Learning. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 43.
Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. 2017. Irgan: A minimax game for unifying generative and discriminative information retrieval models. In Proceedings of the 40th International ACM SIGIR conference on Research and Development Information Retrieval (SIGIR). 315-524.
Xiang Wang, Yaokun Xu, Xiangnan Hc, Yixin Cao, Meng Wang, and Tat-Seng Chua. 2020. Rein- forced negative sampling over knowledge graph for recommendation. In Proceedings of The Web Conference (WWW). 99-109.
Markus Weimer, Alexandros Karatzoglou, Quoc Viet Le, and Alex Smola. 2008. COFIRANK Max- imum Margin Matrix Factorization for Collaborative Ranking. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS). 1593-1600.
Jason Weston, Samy Bengio, and Nicolas Usunier. 2011. WSABIE: Scaling Up to Large Vocabu- lary Image Annotation. In Proceedings of the Twenty-Secome International Joint Conference on Artificial Intelligence (ICCAI). 2764-2770.
Lu Yu, Chuxu Zhang, Shangsong Liang, and Xiangliang Zhang. 2019. Multi-order Attentive Rank- ing Model for Sequential Recommendation. In Proceedings of the Thirty-Thirl AAAI Conference Artificial Intelligence (AAAI). 5709-5716.
Fajie Yuan, Guibing Guo, Joemon M. Jose, Long Chen, Haitao Yu, and Weinan Zhang. 2016. LambdaFM: Learning Optimal Ranking with Factorization Machines Using Lambda Surrogates. In Proceedings of the 25th ACM International Conference on Information and Knowledge Man- agement (CIKM). 227-236.
Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. 2013. Optimizing Top-n Collaborative Filter- ing via Dynamic Negative Item Sampling. In Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval (SIGIR). 785-788.
Tong Zhao, Julian McAuley, and Irwin King. 2014. Leveraging Social Connections to Improve Personalized Ranking for Collaborative Filtering. In Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM). 261-270.
11

---

Under review as a conference paper at ICLR 2022
APPENDIX
A. PROOF FOR THEOREM 3.1
Proof. With the given user-item graph G, both Ejer T(i) and [ are constant. Let's define
function fx) = x' where C₁ = Djer T(j) and C2 = |EL. Then we can have first-order
derivative fz(2) > 0, which means (1( > [V d, > dz.
B. PROOF THEOREM 3.2
Proof. Given latent space with d dimensions, there exists d - 1 mutually orthogonal vectors De pl denote the gradients received when ,3 "., , Ea and ह = pT. Let (1) EnENs Uzue item acted as positive sample, and (t) = EmEN, 8 P denote the gradients received when acting
negative sample. It's noted that if item has large imbalance value, the size of [W]] is usually >> [W and vice versa. Then for any iteration n > т, the embedding item i is updated with gradient descent method as:
P +1
E (77)) 4257
Then perform coordinate axis transform on P and Pt 01,"" "0," Ca.
+ P. a +
+
aa
de
+ Σ Σ
(t)( .... +...+
Frm
n #2t> uEN,
de, (t)(1 + ...- (itbal
n Σ
Σ
azu
WEAT
Now have P7 = a + ... + a and Ps 3. + ... + f. az.. (t) 0, 8 > 0 as
a
inner-product < Pt ē > < P.. Pr >, and all other variables E R.
= P. = a ã + + Ca + Σ (ttt + AsEa,
where (t(t) = n <<EEEN
da.. (t)
ac
EmEN;
D6 (t))t for k E [1. Since coordinates druc
E2,02... Ca are manually orthogonal.
lim n-000
12
lim (a. + 41000
Σ ((11))1111 +...
(a
Σ #20>
2 lim (a)
Σ (1))))1111
n n-000
#20T
> lim (at + (n ()) minn +00
And we have
(t) = 7 Σ
(t)
Σ
(t))))
arus
WeN,
uENT
D6% (1) >
where
Dr...
For imbalanced items, the value of (t) will be dominated by the size of N, and N, If an imbalanced item with a very large imbalance value, then we could have A1 > 0 with a relative high probability. Then we have lim (a. + (n - -T) min (1) = xc.
22000
12

---

Under review as a conference paper at ICLR 2022
C. PSEUDOCODE
The detailed implementation of the proposed method VINS and its key component RejectSampler can be found in Algorithm| aannd respectively.
Algorithm 1: VINS
Input: G (V, E). max step R. positive pair (u, i), max shot s, margin e Output: negative item j. and (ri)
selected; 1, maz, = inf
for K t 1 to n. do
do
j RejedlSumpler(i. 8, R)
while Eaj E E;
Tusi Zuf + Fui Uuj > maa, then
mazj Tuj selected, jj
11
12
Taji > 0 then break;
14 T3
min(K.a) 15 return selected,, (ri(F:);
Algorithm 2: REJECTSAMPLER
Input: item max shot s, weight distribution Output: selected item j selected, = -I, mari, =-1
for iter t to do
j= randint(Z): // in case of the extreme popular item
(T) > mari_deg then
mazi, T(j);
selected, J;
reject ratio 1 min (5))
x())= 1}:
11
random. (atiloommmnfffrm((( > reject ratio then
selected, jj;
13
break;
14 return selecledj;
D. PROOF FOR LEMMA 4.1
Proof.
2
1
1
1
+
+ 6
+
7
8
1
2*
21 1
+
(4 x
2
2 2
2
22
26-1
k
2 1+
13

---

Under review as a conference paper at ICLR 2022
E. DISCUSSION ON VINS
EI. COMPLEXITY DISCUSSION
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 negative item candidate. For each negative sample, the computation complexity (d), where is the embedding size. Assume that the average number of steps to obtain 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 be O (d+ s)-h). Usually, s < d can be 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 violated item. From the experimental analysis, we find that the proposed RejectSampler significantly speeds up searching a violated sample.
E2. CONNECTION TO EXISTING APPROACHES
Most of negative sampling approaches assume that the negative items follow pre-defined distribu- tion Q(). 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 seper-parameters {x, B).
user-independent: As the representatives, UNI (Rendle et al. 2009) and POP (Mikolov et al.) 2013) initialize the (i) as a static distribution л. VINS can actually implement these two meth- ods by setting k = 1, B = 0 for UNI, and x = 1, e [0, 1] for POP.
user-dependent: This type of methods usually define conditional distribution Q(]u)) which can capture the dynamics of learning procedure to some extent. Sampling from the exact distribu- tion Qiilu) 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 ex- ample, DNS (Zhang et al., 2013) greedily selects the item with the largest predicted score Tuj from the candidate set. vell-adversarial (SA) (Sun et al. 2019) method first sample candidates from uniform distribution, then calculate the weight of candidate through a softmax(z..)) distribu- tion. Similar idea can be found in more recent proposed method PRIS (Lian et al., 2020). While, PRIS tries to select negative sample from the distribution Q(iuu) through a importance sam- pling 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 Qu(ilu) sof softmaz(Iaa) 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 train- ing cases to update their policy, and sampling according to the policy distribution relies on the exact distribution QG(jlu) uu) over the whole item set, which makes IRGAN become very slow to converge and difficult to tune the model. Moreover, the generator might have distribution which could delay from the discriminator, which can lead to unqualified negative samples produced by the generator.
rdge-deeendent. 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 nega- tives from distribution Qu]u,, i). As an initial study, Weston et al. (Weston et al.) the WARP loss by designing a rank-aware distribution r; = ΣjEV" I[E + Tuj 2 Tus). How- ever, it's impossible to get the exact r; for every single training sample (u,i) during the training stage. Fortunately the negative item j can be obtained through estimating a geometric distribu- tion P(X = k) parameterized with = 3. There re many works that are based on WARP and all of them follow the same idea as WARP estimate the P(X = k) from uniform dis- tribution. VINS also inherits the basic ideas from WARP but modifies the target distribution as r; = EE x {])][(c + Zuj 2 Tus), and proposes to estimate it through an importance sampling method after theoretically investigating the existing class-imbalance issue and its potential influ- ence. As the ta- variant of WARP loss, L.M-W advances WARP with normalization
2011) proposed
14

---

Under review as a conference paper at ICLR 2022
term. However, estimating the geometric distribution from uniform distribution makes LFM-W W need lots of steps to find a violated sample. Moreover, LFM-W might find sub-optimal negative sample without considering the clas--mmbllance issue. LFM-W can be equivalent to VINS by setting / = 0 and replacing the weight function Wus(Fi) as a truncated Harmonic Series function, i.e. Wus(r;) Σ 2
E3. RANK ESTIMATION BIAS DISCUSSION
Let Pr(X = == p(1 p)* denote geometric distribution with parameter p. and NJ to be the observations. The optimized estimation of p by maximiz- ing the likelihood function will be ğ 1/X, where X Ei=1 X:/n. Now we can obtain the expectation over the estimated parameter, i.e. Elp] = E X When estimating the rank-aware variable Tr, we usually conduct single experiment, that is = 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 the positive sample get better and better ranking position the learning procedure move forwards.
Lemma 7.1. For special case n = 1, Elp] will be larger than p. which means P is not an unbiased estimation.
Proof.
90
1
Eli] E[1/X1]
Σ
p
p)
K:
km1
(2)
+
p(1 - p)
2=
for p E (0 in this case, the above sum term is strictly positive.
Since we can get the estimated rank position as A; = p. Z. To save computational cost, we usually estimate the mass variable in dynamic sampling approach. Under this
one time i.c., n scheme, the estimation expectation ElA:] = Elp Z] = E|Z/X,]. If we fold out this equation, we
can get the following induction:
F
=
p( p) k-1
X1
1=1
26
= rs
Ti
11-
(1
k- >
where = Z denotes ground truth value. Let h(r:) = + 2 (1- represent function of r;- It's very hard analyze the gradients of function h(.). However, we need answer what's 's the exact estimation bias as the change of idea ranking ri. To answer this question, we turn to analyze ratio function (rrs)) (h(r:) rt)/r, = - (1 2 )-1 Comparing to directly analyzing original function h(r:), (rx))
monotone decreasing function. Based on the feature, we empirically illustrate the change of estimation bias ratio and the rank variable r,. From Figure
can that as the item ranks higher, the estimation eтror will be smaller.
E4. FALSE NEGATIVE ISSUE
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 w.. (r:), the more difficult to sample a violated negative item, the smaller weight (ra)(rs) - 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 leave this challenge for future work.
15

---

Under review as a conference paper at ICLR 2022
Z=500
2=1000
(2,4.5)
3.4.8)
Estimation Blas Ratio
(10,3.0)
(20,3.0)
(30,2.0)
Estimation
(60.2.0)
(102,1.0)
(204.1.0)
(209.0.5)
(418,0.5)
(412.0.1)
(824,0.1)
0
100
200
300
400
500
200
400
600
800
1000
Rank Variable
Rank Variable
Z=2000
Z=20000
Estimation Ratio
5.
(6.4.8)
K
Estimation Blas Rato
(51,5.0]
4
(40,3.0)
(397,330)
(120,2.0)
(1191.200
(407,1.0)
(4064,1.0)
(835.0.5)
(8344.0.5)
(1648,0.1)
(16478,0.1)
0
500
1000
1500
2000
5000
10000
15000
20000
Variable fi
Figure 8: The evolution of estimated rank variable (r:).
Table 3: Statistical information of the datasets.
Data
#Users
#ltems
#Observation
Sparsity
Yelp
113,917
93,850
3,181,432
99.97%
Movies&Tv
40,928
51,509
1,163,413
99.94%
CD& Vinyl 26,876
66,820
770,188
99.95%
Steam
20,074
12,438
648,202
99.74%
F. EXPERIMENTAL SETTING AND ANALYSIS
F1. DATASETS
The detailed statistics of the employed datasets can be found in Table 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-se start recommendation usually is regarded
a separate issue in the literature (He and McAuley 2016 Rendle et al.) (010). For each dataset, we convert star-rating into binary feedback regardless 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.
F2. RECOMMENDERS
Matrix Factorization (MF) (Rendle et al. 2009): This method uses a basic matrix factorization model the scoring function. It can be regarded shallow neural network with single hidden layer which takes user and item one-hot vector as input (He et al. 20176).
Factorizing Personalized Markov Chains (FPMC) (Rendle et al. 2010): It's method that combines the MF and factorized Markov Chain over item sequence 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.
16

---

Under review as a conference paper at ICLR 2022
F3. REPRODUCIBILITY
All methods are optimized with Adam and implemented in Tensorflow with a GeForee GTX 1080Ti GPU. We share the parameter setting of the optimizer for all baselines and experiments in this work, with default learning rate 1) = 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 Syper-parameete
For decay factor 8 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, small number e.g.. 10 or 20 gives good enough results as suggested by the authors (Zhang et al. 2013 Hsieh et a 2017). LFM-D needs two syper-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 p. The search space for was {0.01, 0.05, 0.1, 0.5), and p 0.1 gives the best results. AOBPR also needs to set the ratio factor p. and produces best results with 0.1. LFM-W only has 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 W and VINS. For VINS, we need to search the best choice for buffer size i and decay factor J. In this work, we find that = 64 or 128 is good enough according to the analysis results. In terms of IRGAN, implement this method with the published code P and suggested setting. In self-adversarial method [ the diseriminator and generator are the same prediction model. It creates 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 iee. 256. We follow the suggested setting by the authors set up (Lian et al., 2020).
PRIS
CDsSVing!
Steam
CDsAViny!
Steam
Inbilance S.
un
17.5
un!
pop
0.5-
unl
p1p
0.55
un
pop
pop
15.0-
dis
415
dec
12.5
0.3
aspp
6.35
actp:
10.0
6.15
13
75
5.
0.1
130
255
163
0.3
600
teaetons
Figure 9: Evolution of maximum/minimuun imbalance value of different sampling methods.
F4. EXPERIMENTAL ANALYSIS
Due to the limited space in the main content, we will present additional experimental analysis re- sults in this section. More specifically, we can find the changes of maximun/mininum imbalance value for the other two data in Figure 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 summarizee the additional ranking performance on the other two datasets.
REFERENCES
Jiawei Chen, Can Wang, Sheng Zhou, Qihao Shi, Yan Feng, and Chun Chen. 2019. Samwalker: Social recommendation with informative sampling strategy. In The World Wide Web Conference (WWW). 228-239.
Long Chen, Fajie Yuan, Joemon M Jose, and Weinan Zhang. 2018 Improving negative sampling for word representation using self-embedded features. In Proceedings of the Eleventh ACM Inter- national Conference Web Search and Data Mining (WSDM). 107
Jingtao Ding, Yuhan Quan, Quanming Yao. Yong Li, and Depeng Jin. 2020. In Advances in Neural Information Processing Systems (NeurIPS). 1094-1105.
17

---

Under review as a conference paper at ICLR 2022
Table Time complexity analysis: number of average steps h find a negative sample by LFM-W and VINS. The term behind + stands for the standard variance.
Epoch
20
150
Yelp
LFM-W
10.24:26.4
17.0=
52.2
19.8
59.4
21.5+ 63.2
21.7+66.2
VINS
8.7.
11.81 17.4
14.61: 19.7
16.2121.0
16.3121.0
Mo
LFM-W
3,2+8.0
6.5+224.7
12.0+42.7
18.4+60.9
19.0+62.9
VINS
3.417.6
6.2.112.2
9.8116.1
14.9120.0
16.2.120.7
CDnyVinyl
LFM-W
3.115.11
10.0.140.6
17.1458.2
28.5483.3
29.3
VINS
388=10.1
7.9
1288+88.8
21.4+23.2
23.4++3.9
Steam
LFM-W
3,215.7
4.128.8
5.01111
6.2116.0
6.3716.7
VINS
2.845.6
3.5+7.0
4.3+8.4
5.449.8
1.8+
Table 5: Performances with different buffer size.
Buffer Size
16
32
64
128
1024
Yelp-F1@ 10
LFM-W
0.0138
0.0164
0.0180
0.0189
0.0197
0.0202
VINS
0.0169
0.0185
0.0205
0.0222
0.0225
0.0223
Yclp-NDCG@II 10
LFM-W
0.0185
0.0204
0.0224
0.0238
0.0251
0.0255
VINS
0,0209
0.0234
0.0253
0.0281
0.0284
0.0281
Movies&Tv-FF @ 10
LFM-W
0.0193
0.0215
0.0223
0.0228
0.0232
0.0236
VINS
0.0222
0.0228
0.0235
0.0245
0.0243
0.0246
Movies&Tv-NDCGGe
10
LFM-W
0.0252
0.0279
0.0295
0.0301
0.0305
0.0313
VINS
0.029
0.0302
0.0308
0.0326
0.0325
0.0326
CD& Vinyl-FF
10
LFM-W
0.0249
0.0270
0.0278
0.0296
0.0298
0.0301
VINS
0.0270
0.0285
0.0296 0.0310
0.0311
0.0312
CDs& Vinyl-NDCGGee 10
LFM-W
0.0328
0.0352
0.0365
0.0392
0.0398
0.0401
VINS
0.0361
0.0376
0.0397
0,0402
0.041
0.0412
Steam-F1 10
L.M--W
0.0389
0.0399
0.0404
0.0408
0.0409
0.0414
VINS
0.0408
0.04188
0.0426
0.0429
0.0430
0.0428
Stcam-NDCG@n
10
LFM-W
0.0533
0.0547
0.0552
0.0566
0.0568
0.0569
VINS
0.0567
0.0588
0.0603
0.0601
0.0601
0.0603
CDsAVerl
CDstites
Steam
Zaan
0.34
005
0.05
0.23
0.54
0.22
031
0.00
0.83
0.03
0.00
Figure 10: Ranking performance on FI/NDCG metric of shallow and deep models.
18

---

Under review as a conference paper at ICLR 2022
Jingtao Ding, Guanghui Yu, Xiangnan He, Fuli Feng, Yong Li, and Depeng Jin. 2019. Sampler de- sign for bayesian personalized ranking by leveraging view data. IEEE Transactions on Knowledge and Data Engineering (TKDE) (2019).
Ruining He, Wang- LoangCheng Kang, and Julian McAuley. 2017a. Cranslation-base Recommendation. In Proceedings of the eleventh ACM Conference on Recommender Systems (RecSys). 161-169.
Ruining He and Julian McAuley. 2016. Fusing similarity models with markov chains for sparse se- quential recommendation. In Proceedings of IEEE 16th International Conference on Data Mining (ICDM). 191-200.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017b, Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web. 173-182.
Xiangnan He, Hanwang Zhang, Min- Yen Kan, and Tat-Seng Chua. 2016. Fast matrix factoriza- tion for online recommendation with implicit feedback. In Proceedings of the 39th International Conference on Research and Development in Information Retrieval (SIGIR). 549-558.
Ko-Jen Hsiao, Alex Kulesza, and Alfred Hero. 2014. Social Collaborative Retrieval. In Proceedings of the Seventh ACM International Conference on Web Search and Data Mining (WSDM). 293- 302.
Cheng- Kang Hsieh, Longqi Yang, Yin Cui, Tsung- Yi Lin, Serge Belongie, and Deborah Estrin. 2017. Collaborative metric learning. In Proceedings of the 26th International Conference on World Wide Web (WWW). 193-201.
Wang-Cheng Kang and Julian McAuley. 2018. Self-attentive sequential recommendation. In Pro- ceedings of the 2018 IEEE International Conference on Data Mining (ICDM). 197-206.
George Karypis. 2001. Evaluation of Bem-Based Top-N Recommendation Algorithms. In Pro-
ceedings of the 10th ACM on Conference on Information and Knowledge Management (CIKM). 247-254.
Guang-He Lee and Shou-De Lin. 2016. LambdaMF: Learning Nonsmooth Ranking Functions in Matrix Factorization Using Lambda. In Proceedings of the 2016 IEEE International Conference on Data Mining (ICDM). 823 828.
Defu Lian, Qi Liu, and Enhong Chen. 2020. Personalized Ranking with Importance Sampling. In Proceedings of The Web Conference 2020. 1093-1103.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Distributed Rep- resentations of Words and Phrases and Their Compositionality. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS). 3111-3119.
Steffen Rendle and Christoph Freudenthaler. 2014. Improving Pairwise Learning for Item Recom- mendation from Implicit Feedback. In Proceedings of the Seventh ACM International Conference on Web Search and Data mining (WSDM). 273-282.
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme 2009. BPR: Bayesian Personalized Ranking from Implicit Feedback. In Proceedings of the Twenty- Con- ference on Uncertainty in Artificial Intelligence ( (UAI). 452-461.
Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt-Thieme 2010. Factorizing personal- ized markov chains for next-basket recommendation. In Proceedings of the 19th international conference on World Wide Web (WWW). 81 1-200.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. 2019. RotatE: Knowledge Graph Em- bedding by Relational Rotation in Complex Space. In Proceedings of the Seventh International Conference on Learning Representations (ICLR).
Jiaxi Tang and Ke Wang. 2018. Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding. Proceedings of the Eleventh ACM International Conference on Web Search and Data Dining (WSDM). 573-
19

---

Under review as a conference paper at ICLR 2022
Bo Wang, Minghui Qiu, Xisen Wang, Yaliang Li, Yu Gong, Xiaoyi Zeng, Jun Huang, Bo Zheng, Deng Cai, and Jingren Zhou. 2019. Minimax Game for Instance Based Selective Transfer Learning. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 33-43.
Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. 2017. Irgan: A minimax game for unifying generative and discriminative information retrieval models. In Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval (SIGIR). 515-524.
Xiang Wang, Yaokun Xu, Xiangnan He, Yixin Cao, Meng Wang, and Tat-Seng Chua. 2020. Rein- forced negative sampling over knowledge graph for recommendation. In Proceedings of The Web Conference (WWW). 99-109.
Markus Weimer, Alexandros Karatzoglou, Quoc Viet Le, and Alex Smola. 2008. COFIRANK Max- imum Margin Matrix Factorization for Collaborative Ranking. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 1593-1600.
Jason Weston, Samy Bengio, and Nicolas Usunier. 2011. WSABIE: Scaling Up to Large Vocabu- lary Image Annotation. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (ICCAI). 2764-2770.
Lu Yu, Chuxu Zhang, Shangsong Liang, and Xiangliang Zhang. 2019. Multi-order Attentive Rank- ing Model for Sequential Recommendation. In Proceedings of the Thirty- AAAI Conference on Artificial Intelligence (AAAI). 5709-5716.
Fajie Yuan, Guibing Guo, Joemon M. Jose, Long Chen, Haitao Yu, and Weinan Zhang. 2016. LambdaFM: Learning Optimal Ranking with Factorization Machines Using Lambda Surrogates. In Proceedings of the 25th ACM International Conference on Information and Knowledge Man- agement (CIKM). 227-236.
Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. 2013. Optimizing Top-n Collaborative Filter- ing via Dynamic Negative Item Sampling. In Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval (SIGIR). 785-788.
Tong Zhao, Julian McAuley, and Irwin King. 2014. Leveraging Social Connections to Improve Personalized Ranking for Collaborative Filtering. In Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM), 261-270.
20


Reviews:
[{"review_id": "khJVYsaTgiZ", "reviewer": "Reviewer_zgRr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strength:\n1. This work formalizes the class-imbalance problem existing in the contrastive learning loss for recommendation task and gives a simple but effective solution.\n2. The theoretical analysis provided by the authors can well support the claims.\n3. Sufficient experiment results demonstrate the superiority of the proposed method.\n\nweakness:\n1. The proposed method seems to be specialized in recommendation problems.\n2. The presentation can be further improved with more discussion of the main content. \n\nLearning from class-imbalance data has been sufficiently explored during the last few years. However, most of them focus on the imbalance issue caused by the number of labels but discard the same problem existing in the contrastive learning methods. This work attempts to explore the imbalance issue when we optimize the recommender with the help of contrastive loss. We usually extract a contrastive training example with the assumption that the predicted similarity of a pair of nodes in the observed edge (positive) should have larger than the unobserved (negative) one. It's noted that the nodes can appear in both positive and negative edges, and node frequency usually follows a long-tail distribution. Because of that, there exists a significant class-imbalance bias in the contrastive learning method for the recommendation task. As far as I know, this problem has been insufficiently studied. In this work, a completed theoretical analysis is given to reveal an interesting finding that the imbalance degree has a positive relation to the item degree and can lead to the infinite norm of item embeddings, in particular those suffering from the class-imbalance problem. Along with this observation, the authors propose a debiased negative sampling method that can adaptively re-weight the loss according to the ranking position of imbalanced items. The proposed approach defines a conditional probability depending on both the given user and positive items. However, it's usually difficult to obtain an effective hard negative sample from the given probability due to the large size of the item database. In order to deal with this problem, the proposed method combines a biased random walk towards the popular items and an adaptive filtering criterion for efficiently retrieving qualified hard negative samples. Thorough experimental results demonstrate the superiority of the proposed method in real-world data. Overall, this work is clearly presented with sufficient discussion and details for further reproducibility.\n\nconcerns:\n1. The proposed method seems to greedily select items with a large prediction score. While those items might be the true positive. Could you please give a justification about how to deal with the false negative issue?\n\n2. Is the re-weighting method an essential choice? what if we remove the weight?\n\n3. Could you provide more details on why RejectSampler depends on a biased random walk?\n\n", "summary_of_the_paper": "This is an interesting and solid paper that theoretically demonstrates the connection between a long-tail distribution and the essentiality of hard negative sampling, proposes a simple yet effective negative sampling method, and conducts sufficient experiments. ", "summary_of_the_review": "This work gives sufficient theoretical analysis about the class-imbalance problem and provides a simple but effective debiasing method to advance the optimization performance for item recommendation tasks. Sufficient experiments are provided. Overall, it's an interesting, solid and well-organized paper studying an important problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dsF9PSJ6gP0", "reviewer": "Reviewer_1zJH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. the paper studies an important topic on negative sampling for the learning-to-rank problem \n2. the proposed method is based on an intuitive analysis on the vertex level imbalance sampling instead of commonly used edge level sampling. \n3. It provided both theoretical analysis and experiments on real world datasets to demonstrate the effectiveness on the proposed sampling approach.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is marginally innovative. The method it proposed is intuitive and clear. However, it is unclear if the proposed methods is applicable to any form of learning-to-rank problems or it is tied to certain learning-to-rank models, such as MF. It would be very useful to clarify the how generic the proposed sampling approach is applicable explicitly. For the learn-2-rank models mentioned in the paper,  I would recommend it for a poster paper, the writing can also be improved by directly citing the models used in the experiments instead of listing them in appendix. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RYxjn_6NYuZ", "reviewer": "Reviewer_A9Ak", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To overcome vertex-level imbalance issue, the authors propose a two-phase sampling approach dubbed as Vital Negative Sampler (VINS), by sampling a negative item with a larger degree (to explicit positive connection between item degree and the learned embeddings) and close prediction score to the given positive sample (to leverage relative rank position of positive and negative items for finding more informative negative samples). \n\n\nThe paper is well-written and the authors supported the claims made with theoretical and empirical analysis. However there few key issues that prevents me from giving it a high-score and makes me to lean toward rejection:\n\n(1) While the mentioned issues totally make sense and it is appreciated that authors conducted experiments to provide intuition, but in objective (1) the regularization terms are dropped. Focusing on Imbalanced Item Theorem that indicates the embedding of popular items becomes extremely large, but I was left wondering if this issue can not be alleviated via regularization. Note that the number of times the embedding of an item  will be regularized is proportional to the number of times it is sampled, which possibly avoids embedding explosion as claimed. Even more interesting, if we adaptively pick the regularization parameter for each item proportional to its degree, it might resolve the issue.\n\n(2) While the proposed two-stage sampling idea looks interesting, in my opinion it looks incremental and lacks enough novelty. For example this is simply the hard negative sampling in contrastive learning or even utilizing a dynamic weighted loss based on the loss of current model on each negative sample (note that here we can sample a batch of negative samples and avoid the computation burden of VINS). \n\n(3) The proposed idea can be considered as a sampling variant of ranking with accuracy at top (push-norm) where we try to push as many as possible negative samples below positive items by changing the pairwise ranking loss into a push-norm based loss. It would be interesting to discuss the proposed idea in context of this line of research\n\nRudin, C. (2009). The P-Norm Push: A Simple Convex Ranking Algorithm that Concentrates at the Top of the List. Journal of Machine Learning Research, 10, 2233-2271.\n\nLi, Nan, Rong Jin, and Zhi-Hua Zhou. \"Top Rank Optimization in Linear Time.\" NIPS. 2014.", "summary_of_the_paper": "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. \n\nThe 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.\n", "summary_of_the_review": "Overall, I like the observations made and the proposed sampling idea, but due to issues discussed above I found the contribution incremental and leaning towards rejection.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "GVBIHMp0lBX", "reviewer": "Reviewer_QcpY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.\tThis paper focuses on an important and practical problem in training pairwise ranking models for recommender systems.\n2.\tThe proposed method is simple but effective, which satisfies the requirements for a suitable negative sampling method.\n\nWeakness:\n1.\tThe novelty of this paper is limited. First, the analysis of the vertex-level imbalance problem is not new, which is a reformulation of the observations in previous works [Rendle and Freudenthaler, 2014; Ding et al., 2019]. Second, the designed negative sampler uses reject sampling to increase the chance of popular items, which is similar to the proposed one in PRIS [Lian et al., 2020].\n2.\tThe paper overclaims on its ability of debiasing sampling. The “debiased” term in the paper title is confusing.\n3.\tThe methodology detail is unclear in Sec. 4.2. The proposed design that improves sampling efficiency seems interesting but the corresponding description is hard to follow given the limited space.\n4.\tSpace complexity of the proposed VINS should also be analyzed and compared in empirical studies, given that each (u, i) corresponds to a $buffer_{ui}$.\n5.\tExperiment results are not convincing enough to demonstrate the superiority of VINS on effectiveness and efficiency.\n-\tFor effectiveness, the performance comparison in Table 1 is unfair. VINS sets different sample weights $W_{ui}$ in the training process, while most compared baselines like DNS, AOBPR, SA, PRIS set all sample weights as 1. \n-\tFor efficiency, Table 2 should also include the theoretical analysis for contrast.\n", "summary_of_the_paper": "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.\nAuthors 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.\nTo 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.\nEmpirical results on several real-world datasets demonstrate its superiority on both efficiency and effectiveness. ", "summary_of_the_review": "As mentioned in the weakness, the limitations on novelty, methodology design, and conducted experiments prohibit its acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers remained concerned about the overall novelty of the paper, finding the contributions somewhat incremental. The authors are encouraged to better substantiate design choices that they make, to improve the overall presentation, and to contrast with the works/line of research brought up by the reviewers.
Decision: Reject