TOTALRECALL: A BIDIRECTIONAL CANDIDATES GENERATION FRAMEWORK FOR LARGE SCALE REC-
Year: 2021

Abstract:
Recommender (RS) and Advertising/Marketing Systems (AS) play the key roles in E-commerce companies like Amazon and Alibaba. RS needs to generate thousands of item candidates for each user (u2i), while AS needs to identify thousands or even millions of high-potential users for given items so that the merchant can advertise these items efficiently with limited budget (i2u). This paper proposes an elegant bidirectional candidates generation framework that can serve both purposes all together. Specifically, our framework finds its practical applications on generating millions of users for a large number of items, and the marketing scenarios of small and medium enterprises (SMEs) with cloud-service. Besides, our framework is also superior in these aspects: i). We theoretically show that our modeling objective is equivalent to the modeling objectives of the SOTA algorithms if measured by the metrics of u2i and i2u. ii). Our framework can easily incorporate many DNN-architectures, and achieve SOTA results with the same architecture. iii). We empirically show that our framework can diversify the generated candidates, and ensure fast convergence.

text: Recommender (RS) and Advertising/Marketing Systems (AS) play the key roles in E-commerce companies like Amazon and Alibaba. RS needs to generate thousands of item candidates for each user (u2i), while AS needs to identify thousands or even millions of high-potential users for given items so that the merchant can advertise these items efficiently with limited budget (i2u). This paper proposes an elegant bidirectional candidates generation framework that can serve both purposes all together. Specifically, our framework finds its practical applications on generating millions of users for a large number of items, and the marketing scenarios of small and medium enterprises (SMEs) with cloud-service. Besides, our framework is also superior in these aspects: i). We theoretically show that our modeling objective is equivalent to the modeling objectives of the SOTA algorithms if measured by the metrics of u2i and i2u. ii). Our framework can easily incorporate many DNN-architectures, and achieve SOTA results with the same architecture. iii). We empirically show that our framework can diversify the generated candidates, and ensure fast convergence.

heading: 1 INTRODUCTION
text: In the Internet era, E-commerce companies usually act as a platform to connect both users and merchants. They can collect huge amount of data of users’ behavior on merchants’ items, and utilize the data to serve them better, for example, to build better search/recommender/advertising systems.
When users browse the E-commerce websites/apps, they usually want to buy some desired items, or find something interesting, and that’s what the search engine and recommender system (RS) are built for. Besides, the merchant usually wants to mine the potential users of its items, and then starts a campaign to prompt those users to buy the items. The advertising system has the functionality to help the merchant, and we may call it the potential users mining system (PUMS).
In an industrial large-scale RS, there are usually two stages, the candidates generation (CG) stage and the ranking stage (Covington et al., 2016). CG plays a very import role as it sets the upper bound of the recommender. A single CG method usually lacks diversity, so the industrial CG system usually consists of different subsystems to generate candidate items, for example, i). hot items, ii). items similar to users (Covington et al., 2016; Li et al., 2019), iii). items similar to clicked items (Linden et al., 2003), iv). items clicked by similar users (Wang et al., 2006).
The PUMS has been studied and applied in marketing community for many years (Bult & Wansbeek, 1995; Kim et al., 2005), and recently it is also introduced to social network to attract potential customers of companies (Pennacchiotti & Popescu, 2011; Pang et al., 2013). Similarly in E-commerce companies, it can be used to discover potential customers for merchants, brands and etc. Although it is widely used, people usually treat it as a simple binary classification problem, i.e., to predict whether a given user is the potential user or not. Models like LR, SVM, XGBoost and etc. (Hosmer Jr et al., 2013; Chang & Lin, 2011; Chen & Guestrin, 2016) are usually employed.
In this paper, we unify the two systems in our TotalRecall (TR) framework, and apply it in both large-scale PUMS and marketing scenarios of SMEs with the cloud-service. Our main contributions are listed below:
• Bidirectional Candidates Generation: TR can be trained once and then used to generate candidate items (u2i) and users (i2u) all together without any additional operations. Theoretically we show that it is due to the modeling of joint probability of u and i.
• Achieving SOTA results in both RS and PUMS: We compare to two different algorithms, i.e., Matrix Factorization (MF) with Bernoulli distribution and sequential modeling and MF with Multinomial distribution, and achieve comparable or better results than previous SOTA.
• Equivalence of the algorithms based on Bernoulli and Multinomial distributions: To the best of our knowledge, we are the first to show that modeling the user-item interaction with Bernoulli and Multinomial distributions are equivalent.
• Fast Convergence, and Diversified Candidates: TR converges much faster compared to MF models, up to 16× times. Our experiments show that TR can increase the diversity of the generated candidates.

heading: 2 RELATED WORK

heading: 2.1 RECOMMENDER SYSTEM (RS)
text: RS has been studied for many years, and in the early years, Collaborative Filtering (CF) and its variants (Su & Khoshgoftaar, 2009) are widely adopted. Later its descendant MF (Funk) is proposed to solve the problem more elegantly with higher accuracy, and Probabilistic Matrix Factorization (PMF) (Mnih & Salakhutdinov, 2008) builds a solid theoretic foundation for MF based on probability theory.
Although MF performs very well in many datasets (Rendle et al., 2020), it is usually not adopted in industry. The modern industrial RS can involve up to billions of users and hundreds of millions of items, and consist of multiple stages, e.g., CG and ranking stages (Covington et al., 2016).
Various deep neural networks are adopted to tackle the complicated system, for example, in the CG stage, the problem is formulated as the multi-class classification, and users’ and items’ representations are detached with the two-tower architecture to balance the efficiency and accuracy in online serving (Covington et al., 2016; Li et al., 2019; Cen et al., 2020).
In the ranking stage, the problem is formulated as the binary classification, and various models has been developed: wide & deep model (Cheng et al., 2016) captures explicit and implicit feature crossing, Deep Interest Network (Zhou et al., 2018) and Deep User Perception Network (Ni et al., 2018) utilize attention mechanism (Bahdanau et al. (2014)) to capture users’ short-term interests.

heading: 2.2 POTENTIAL USERS MINING SYSTEM (PUMS)
text: PUMS mines the potential users for given items. The ‘item’ could be anything that users can interact with, for example, an insurance product (Kim & Street, 2004), a company/business (Pennacchiotti & Popescu, 2011; Pang et al., 2013; Lo et al., 2016), a specific information (e.g., tweet) in social medias (Tang et al., 2015; Gui et al., 2019) and even another user (Guy, 2018). These problems are usually treated as binary classification and solved with tools like SVM, LR and etc. for each individual item independently (Hosmer Jr et al., 2013; Chang & Lin, 2011; Chen & Guestrin, 2016).
In the E-commerce company like Amazon, the ‘item’ could be a product, a brand, a product category, a merchant and etc, and the number of the ‘items’ range from thousands to hundreds of millions. It will be impractical to model each item individually, so we usually model the items all together using binary classification similar to Rendle et al. (2020), which will be stated in detail later in Sec. 5.

heading: 2.3 SAMPLED-SOFTMAX AND INFONCE LOSS
text: In the CG stage of RS, sampled-softmax (SSM) loss (Jean et al., 2015) is widely used with different background distributions, such as log-uniform distribution (Powers, 1998), empirical marginal distribution (Yi et al., 2019) and mixed distribution (Yang et al., 2020).
In contrastive learning, InfoNCE loss is proposed in Oord et al. (2018) to learn representations through self-supervision. Later it is widely adopted in CV (Chen et al. (2020)) and NLP (Gao et al. (2021)) and performs very well.
InfoNCE and SSM losses are both trying to solve multi-class classification of very large vocabulary. They both use negative sampling and can be written in the same analytical form:
l = 1 |D| ∑
(x,y)∈D
− log exp(fϑ(x, y)− log pn(y|x)) exp(fϑ(x, y)− log pn(y|x)) + ∑ y′∈Yx exp(fϑ(x, y ′)− log pn(y′|x)) ,
(1) where (x, y) ∈ D is the training data, and usually x is the input features and y is the class, fϑ(x, y) is the output of the neural network parametrized by ϑ, and Yx contains hundreds or thousands of negative samples from background distribution pn(y|x). The main differences are that the pn(y|x) in SSM can be arbitrarily chosen, while in InfoNCE it is the empirical marginal distribution p̂data(y).
Recently, InfoNCE loss is exploited in RS to optimize p(y|x)p(y) instead of p(y|x) for the debiasing purpose, and it can be easily implemented with in-batch negative sampling and features of y can be fully utilized (Zhou et al., 2021).

heading: 3 METHOD

heading: 3.1 PROBLEM DEFINITION
text: In E-commerce companies, when a user u clicked an item i at time t, a record (u, i, t) was logged as the implicit feedback.
Given the raw logs {(u, i, t)}, there are usually two ways to process the data: one is to directly create a user-item interaction matrix Sui with the value su,i = 1 if the (u, i) pair appears in the log (Su & Khoshgoftaar (2009)); the other is to formulate the problem as next-item prediction, i.e., from the raw log we create a dataset D = {(xu,t, yu,t) : t ∈ {1, 2, ..., Tu}|u ∈ {1, 2, ..., N}}, where xu,t = {yu,1:(t−1)} represents u’s clicks prior to t-th click yu,t and Tu is the number of clicks of u (Covington et al. (2016)). We define the click sequence xu,t as the pseudo-user, so we can create a pseudo-user-item interaction matrix from D, and all possible click sequences form the pseudo-user set.
Therefore, they both deal with the 2D interaction matrix Sui, irrespective of whether the u is a real user or pseudo-user or not. In the remaining of the paper, we will not distinguish between user and pseudo-user, and only focus on solving the Sui.
Sui consists of all users as the row and all items as the column, and its entries are either 1 or unknown. Let’s assume all users form the set U = {u1, u2, ..., uM}, and all items form the set I = {i1, i2, ..., iK}. Given a user u ∈ U, we will generate candidate items from the item pool I (RS, u2i), while given an item i ∈ I, we shall find out the potential users out of all users U (PUMS, i2u). The candidates generation of RS and PUMS are of the opposite direction, and traditionally they are solved separately. But essentially they are both trying to estimate some kind of probabilities of the unknown entries in Sui, so we propose to model them jointly.

heading: 3.2 RECOMMENDER SYSTEM
text: In RS, there are usually two types of modeling objectives when dealing with Sui, and we briefly introduce them in the following sections (See App. A.1 for more details).

heading: 3.2.1 GAUSSIAN AND BERNOULLI DISTRIBUTION
text: The u-i interaction score su,i of Sui is treated as the random variable, and assumed to be i.i.d. following a certain distribution, for example, Gaussian (Mnih & Salakhutdinov (2008)) or Bernoulli (Johnson (2014); He et al. (2017); Rendle et al. (2020)) distributions.

heading: 3.2.2 MULTINOMIAL DISTRIBUTION
text: Here the modeling objective is the random variable su, defined as the interacting item of u. For example, given the total number of interactions Nu = ∑ i∈I su,i of u, su is assumed to be sampled from a multinomial distribution Mult(Nu,pu), where pu is a K-dimensional vector whose elements are the probability and sum to 1 (Liang et al., 2018). Although not explicitly stated in many papers (Covington et al., 2016; Yi et al., 2019; Li et al., 2019; Cen et al., 2020), the multinomial distribution is actually assumed.
The modeling objectives in Sec. 3.2.1 and 3.2.2 are quite different, as the former is su,i and the latter is su. In MF, we usually model su,i, while in the sequential modeling of the CG stage in industry, we model su. Later in Sec. 3.5, we will show that modeling su and su,i can be theoretically equivalent, and it is verified by the experiments in Sec. 4.1 and 5. However, modeling su can boost the converging speed a lot.

heading: 3.3 POTENTIAL USERS MINING SYSTEM
text: The PUMS seems to be the twin system of RS, and similarly we could also define two modeling objectives su,i and si, where si denotes the user who interacts with the item i. su,i and si are assumed to follow Bernoulli and Multinomial distributions respectively. In Sec. 5 we will compare the two methods.

heading: 3.4 TOTALRECALL: UNIFICATION OF RS AND PUMS
text: Motivated by Sec. 3.2 and 3.3, we propose to model the two systems jointly. Specifically, the optimization objectives su and si in Sec. 3.2.2 and 3.3 are formulated in one framework and optimized together. Later we show that by properly choosing the model architecture and loss function, we are treating u and i equally and modeling the joint probability.

heading: 3.4.1 MODEL ARCHITECTURE
text: We choose the classical two-tower architecture (Huang et al., 2013; Covington et al., 2016; Rendle et al., 2020) for two reasons: one is that users and items can be treated equivalently, and the other is
that no feature crossing occurs before the final logits (See Fig. 1). So users’ and items’ embeddings can be inferred separately, and then approximate nearest neighbor (ANN) (Liu et al., 2004) search algorithm can be applied in online serving.
The output of two towers are d-dimensional vectors u = fθ(u) ∈ Rd and i = gθ(i) ∈ Rd, where θ is the model parameter. The dot product ⟨u|i⟩, or the function of it is used as the sufficient statistics of the probability distributions defined in Sec. 3.2 and 3.3 (Check App. A.1 for details). We find that l2-normalizing u and i and then rescaling the dot product by the temperature τ will lead to better and robust results:
ϕθ(u, i) = 1
τ ⟨u|i⟩ ||u||2||i||2 . (2)

heading: 3.4.2 LOSS FUNCTION
text: We propose the Bi-InfoNCE loss:
l = 1 |Su,i| ∑ u∈U,i∈I,su,i=1 − log exp(ϕθ(u, i)− log q(i)) exp(ϕθ(u, i)− log q(i)) + ∑ i′∈Iu exp(ϕθ(u, i ′)− log q(i′))
− log exp(ϕθ(u, i)− log q̂(u)) exp(ϕθ(u, i)− log q̂(u)) + ∑ u′∈Ui exp(ϕθ(u ′, i)− log q̂(u′))
,
(3)
where Iu ⊂ I and Ui ⊂ U contain hundreds or thousands of in-batch negative samples, and q(i) and q̂(u) are empirical marginal distribution calculated using the training data Sui. It can be shown that optimizing this loss will make ϕθ(u, i) converge to log p̂data(u, i) (See App. A.3 for details.).
If we only optimize the first part of Eq. 3, ϕθ(u, i) will converge to log p̂data(i|u), and optimizing only the second part will let ϕθ(u, i) converge to log p̂data(u|i). We refer to the two cases as UniInfoNCE losses.

heading: 3.5 EQUIVALENCE BETWEEN MODELING WITH BERNOULLI AND MULTINOMIAL DISTRIBUTIONS
text: As discussed in the previous sections, we can use both Bernoulli and Multinomial distributions to model the same user-item interaction matrix Sui, and usually their results are comparable in both RS and PUMS (See Sec. 4.1 and 5).
The apparent connection between the two algorithms motivates us to explore their relations, and we prove that they are theoretically equivalent on modeling the user-item interaction matrix. Specifically, different negative sampling methods of Bernoulli distribution correspond to different objectives modeled with Multinomial distributions.
For example, in MF with Bernoulli distribution (MFb), we could have 5 different negative sampling methods, i.e., for a given positive (u, i) pair, we sample the negative pairs in these ways: 1). ‘MFb [0:8]’1, we randomly sample 8 is from the item set I, and construct 8 negative pairs with the given u; 2). ‘MFb [8:0]’, we sample 8 us from the user set U, and construct 8 negative pairs with the given i; 3). ‘MFb [4:4]’, we sample 4 us and 4 is, and construct 8 negative pairs with the given i and u respectively; 4). similar to 3), but the negative samples are doubled; 5). ‘MFb [8]’, we sample 8 (u, i) pairs uniformly from the M ×K pairs with i ∈ I and u ∈ U as the negative pairs.
We prove that 1) is equivalent to modeling p(i|u), 2) to p(u|i), 3) and 4) to p(u,i)p(u)p(i) , and 5) to p(u, i). The details can be found in App. A.4.

heading: 3.6 MOTIVATION AND PRACTICAL APPLICATIONS OF TR
text: TR is developed to solve two practical problems: one is the large-scale potential users mining, and the other is the marketing in SMEs.
1This sampling method is actually used in MFb in RS by Rendle et al. (2020)
For example, we have 1 billion users and 10,000 items, and we need to mine the top 1 million users for each of the items. This problem can be easily solved with TR: we infer the users’ and items’ embeddings with TR, and then apply the ANN search to find the top 10 items for each user. Now we have 10 billion (u, i) pairs and their similarity scores, and we just pick the top 1 million for each item based on the same scores. This method also indirectly ensures that each person will receive at most 10 advertisement messages.
This can only be achieved if we model the joint probability p(u, i). We also list some alternative methods to solve the problem in App. A.5, but they are either not good in terms of accuracy or not practical in terms of computation and storage costs, efficiency, risk and maintainability. TR has been deployed in our production environment to serve this purpose.
In the marketing scenario of SMEs, two strategies are widely adopted: i). SMEs pick some specific groups of users, and then choose the top products for each user and send the personalized campaign messages. This can be regarded as the RS. ii). SMEs have some new or special products and want to find the target users. This is the PUMS.
The two marketing requirements can be completed either with two separate models or with the unified model TR. Due to the limited computation and storage budgets, and the shortage of talents, TR is the best choice for them. Actually, TR is already implemented in one of our cloud-service products for SMEs.

heading: 4 EXPERIMENTS: RS
text: As stated in Sec. 3.2, two types of modeling objective are well studied in literature, and usually they use different datasets and baselines. So we compare our results with them separately using different datasets. The details of the datasets and processing methods can be found in App. A.6.

heading: 4.1 MF WITH BERNOULLI DISTRIBUTION
text: We compare TR to MFb in Rendle et al. (2020), as described in Sec. 3.2.1. Our implementation of MFb is a bit different from Rendle et al. (2020): we implement it using tensorflow (Abadi et al., 2016) with Adam optimizer (Kingma & Ba, 2014).
We tried L2 regularization but failed to obtain the results reported by Rendle et al. (2020). We also tried dropout (Srivastava et al., 2014), but it was unstable and need to be re-tuned for different dimensions d. Finally we find that the ϕθ(u, i) defined in Eq. 2 can actually act as a kind of regularization, so we use it rather than the one defined by Eq. (2) in Rendle et al. (2020).
We use Movielens-1m and Pinterest datasets, and the evaluation metrics are HiteRate@10 and NDCG@10. MFb and TR have the same two-tower architecture and same number of parameters, and the key differences are the training data and the optimizing objectives: MFb uses explicit negative sampling, i.e., MFb [0:8], and optimize the binary cross-entropy loss, and TR uses implicit in-batch negative sampling and Bi-InfoNCE loss.
The results are shown in Tab. 1. In general, MFb and TR are comparable, and this is consistent with our theory in Sec. 3.5, because they are both modeling p(i|u) or p(u, i) ultimately. Besides, the diversity of TR is also larger than MFb as shown in Fig. 3. (Check App. A.6.1 for more details.)
When measuring the training efficiency, TR converges to the optima up 16× times faster than MFb (See Fig. 3 in Appendix). We attribute it to two reasons: i). For MFb [0:8] used here, 9 processed samples will consist of only 1 positive samples on average. While in Bi-InfoNCE (or Uni-InfoNCE / SSM), 9 processed samples are all positive samples. ii). For MFb, each sample is either positive or negative, and the binary-cross-entropy loss allows it to compare with itself only. In TR, Bi-InfoNCE (or Uni-InfoNCE / SSM) loss will compare each sample with all the other samples in the batch.
Bearing in mind that MFb and Bi/Uni-InfoNCE can theoretically converge to the same optimum, the qualitative explanation can provide some intuitive understandings of the fast convergence. The fast converging speed makes it more practical to use TR in industrial applications with huge amount of data.

heading: 4.2 SEQUENTIAL MODELING WITH MULTINOMIAL DISTRIBUTION
text: We compare TR to the sequential modeling with Multinomial distribution, as described in Sec. 3.2.2. This modeling method is usually used in the CG stage of industrial large-scale RS, because it can deal with huge amount of data very efficiently, and yield good results.
For simplicity, we use the popular Youtube DNN (Covington et al., 2016) implemented by Cen et al. (2020) as the backbone architecture of TR. Other complicated architectures can be easily incorporated into TR framework.
We use the same datasets as Cen et al. (2020) for a fair comparison, i.e., Amazon books data 2 and Taobao click data in Tianchi competition 3. The data is split into train, validation and test data. The training data is usually processed as next-item prediction as in Sec. 3.1, and we extend it into next-n-item prediction, i.e., instead of predicting only the next item, we predict all the next n items. The results are shown in Tab. 2. More results are shown in Fig. 4 and 5 in Appendix.
Our experiments show that proper regularization using l2-normalization and the scaling parameter τ can greatly improve the results, as it confines ϕθ(u, i) inside [−1/τ, 1/τ ]. Better training data due to next-n-prediction can also improve the results, because it alters the distribution of the training data so that it gets close to the test data (See Fig. 6 in Appendix).
Besides, we have three observations. i). Comparable results: TR’s result is comparable to the SOTA results from SSM and Uin-InfoNCE. This shows that the modeling objectives p(u, i) and
2http://jmcauley.ucsd.edu/data/amazon/index.html 3https://tianchi.aliyun.com/dataset/dataDetail?dataId=649&userId=1
p(i|u) perform similarly if measured by the metrics for u2i candidate generation. ii). Improved diversity: We try SSM with different background distributions, and compare with Uni-InfoNCE and Bi-InfoNCE, and find that Bi-InfoNCE gives better overall diversity as measured by the related metrics (See Fig. 4 in Appendix). We don’t have a rigorous explanation and would like to leave it for the future study. iii). Faster convergence: Compared to SSM or Uni-InfoNCE without l2normalization, adding l2-normalization or using Bi-InfoNCE will make the models learn faster (See Fig. 4 in Appendix). This is because l2-normalization will restrict the vector space that u and i could explore, and Bi-InfoNCE utilizes the data more efficiently compared to Uni-InfoNCE, i.e., the utilization rate is doubled.

heading: 5 EXPERIMENTS: PUMS
text: In E-commerce, there are usually two practical scenarios of i2u candidates generation: one is to mine the potential users for a single item, and the other is to find users for a group of similar items. Because the marketing staff or some merchants regularly pick a group of similar items, and set the specific campaigns to advertise them.
Previously, the problem is usually formulated as the binary classification for each individual case, but it is not generally applicable because the number of items or groups could be quite large, and it is impractical to build so many models.
One solution is to merge all the binary classification models into one, just like MFb in Sec. 3.2.1 and 3.3. The other is our TR framework.

heading: 5.1 DATASET AND EVALUATION METRICS
text: We use Movielens-1m because it is also used in MFb of RS, and it can be used to mine the potential users of both the single item and the group of similar items.
Movielens-1m records 6040 users and 3706 movies. The data is split into training, validation and test data, and we use the validation data to select the proper model configurations. The final results are reported on the test data.
We use precision@10 and recall@10 to evaluate the accuracy of different algorithms, i.e., we mine the top 10 users for a single item or a group of items, and then evaluate the precision and recall. We count the distinct users of the overall results to measure the diversity. (See App. A.7 for details about the dataset and metrics.)

heading: 5.2 POTENTIAL USERS OF A SINGLE ITEM
text: We first select movies which have been watched by at least 50 users, and it results in 2514 movies. For each of these movies, we randomly pick 1% of its users to form the valid and test datasets, with half of the movies as the validation data and the other half as the test data (See App. A.7.). The remaining data is used to train the model, and the validation data is for selecting the best hyperparameters, and the results are reported on the test data.
The results are shown in Tab. 3. ‘TR [Bi-InfoNCE]’ achieves the best results in terms of the accuracy and diversity. High diversity implies that the advertisements can reach more users, even the nonactive users, thus alleviate the advertising fatigue.
Besides, TR uses the same training data and model configurations for both RS and PUMS, and achieves comparable in both cases. The learned u/i representations can be applied to the two systems without any additional modifications. In contrast, MFb’s modeling objective (Eq. 4) seems to treat u and i equally, but the outcomes depend highly on the negative sampling methods (See Tab. 3). This is consistent with our theoretical analysis in Sec. 3.5.
Last but not least, TR learns 16× times faster than MFb (See Fig. 7 in Appendix). The reason is the same as in Sec. 4.1.
Our study of mining potential users of a group of items can be found in App. A.7.2.

heading: 6 CONCLUSION
text: In this paper, CF and the sequential modeling (i.e., next-item prediction) of RS, and PUMS are abstracted into a unified u-i interaction matrix Sui, and thus are treated equivalently as deriving some probabilities for the unknown entries from the known entries of Sui. We also show their connections and differences based on probability theory.
We prove that modeling p(su,i = 0/1|u, i) with different sampling methods can be equivalent to modeling p(i|u), p(u|i), p(u, i) and p(u,i)p(u)p(i) .
We propose the TR framework to solve u2i and i2u CG all together. In TR, u and i are treated equally, and the joint probability p(u, i) is actually derived, instead of the conditional probability p(i|u) or p(u|i). Therefore, the learned representations of u and i in TR can be used in both u2i and i2u CG.
Our extensive experiments show that TR can achieve comparable results in each domain measured by the metrics for either u2i or i2u candidates generation. TR learns 16× times faster than MFb. Besides, TR generates diversified candidates.
In the future, we plan to study the vector space of TR in depth, and try to unify different objects and users into one space, for example, products, merchants, brands, categories of products. In such a space, everything is linked, and candidates generation can be applied on any pair of objects.

heading: A APPENDIX

heading: A.1 DISTRIBUTIONS
text: In Sec. 3.1 we define the interaction matrix Sui, and it has the known entries with value 1 and unknown entries. Here we define a corresponding matrix P of the same shape, and its entries are the probabilities estimated by a certain algorithm.
In Sec. 3.2.1, the corresponding probability matrix PMF is defined as follows:
pu,i := p(su,i = 1|u, i), (4) where ∑ su,i∈{0,1} p(su,i|u, i) = 1.
Here we can assume su,i follows Gaussian distribution: su,i ∼ N(ϕ(u, i), σ̂2), or Bernoulli distribution: su,i ∼ B(σ(ϕ(u, i))), where σ(·) is the sigmoid function.
In Sec. 3.2.2, for a given user u, su ∼ Mult(Nu,pu), where pu = (pu1, pu2, ..., puK)T is a Kdimensional vector. The probability matrix Pu2i is defined with the same pui = p(i|u). pui is modeled as
pui = expϕθ(u, i)∑ j∈I expϕθ(u, j) . (5)
In Sec. 3.3 of PUMS, we can define the specific PMF and Pi2u in a similar manner. For example, we use si to denote the user who will interact with the item i, and si ∼ Mult(Ni,pi), where pi = (p1i, p2i, ..., pMi)
T is a M -dimensional vector. Pi2u is defined with the same pui = p(u|i), and it is modeled as
pui = expϕθ(u, i)∑ v∈U expϕθ(v, i) . (6)

heading: A.2 LOSS FUNCTIONS
text: In this paper, we focus on Bernoulli and Multinomial distributions, because they usually lead to better results than Gaussian distribution (He et al. (2017); Rendle et al. (2020)). Following the maximum likelihood estimation (MLE) principle, the loss for Bernoulli distribution is:
l = − 1 |D| ∑ u∈U,i∈I,(u,i)∈D su,i log σ(ϕθ(u, i)) + (1− su,i) log(1− σ(ϕθ(u, i))), (7)
where su,i ∈ {0, 1}, and su,i = 1 are the positive entries in Sui, and su,i = 0 are negative samples randomly sampled from the entries in Sui, and D is the training dataset consist of all the positive and randomly sampled negative samples.
The loss for Multinomial distribution is softmax-cross-entropy loss (Liang et al., 2018):
l = 1 |Su,i| ∑ u∈U,i∈I,su,i=1 − log expϕθ(u, i)∑ i′∈I expϕθ(u, i ′) , (8)
where |Su,i| is the sum of the entries in Sui. In practice, the vocabulary I can be very large so that calculating the partition function∑
i′∈I expϕθ(u, i ′) becomes impractical. SSM and InfoNCE loss can be used to solve this problem:
l = 1 |Su,i| ∑ u∈U,i∈I,su,i=1 − log exp(ϕθ(u, i)− log pn(i|u)) exp(ϕθ(u, i)− log pn(i|u)) + ∑ i′∈Iu exp(ϕθ(u, i ′)− log pn(i′|u)) , (9) where Iu ⊂ I contains hundreds or thousands of negative samples, and pn(i|u) is a predefined background distribution. It has been shown that optimizing Eq. 9 will make ϕθ(u, i) converge to log p̂data(i|u) (Jean et al., 2015; Oord et al., 2018).

heading: A.3 BI-INFONCE LOSS
text: Here we prove that ϕθ(u, i) in Eq. 3 converges to log p̂data(u, i).
In Eq. 3, in the optimum of the first part, following the proof by Jean et al. (2015); Oord et al. (2018), we have exp(ϕθ(u,i))qi ∝ p̂data(i|u) qi , so we can assume:
ϕθ(u, i) = log p̂data(i|u) + f(u) = log p̂data(u, i)− log p̂data(u) + f(u) for a given u and any i. Similarly, in the optimum of the second part, ϕθ(u, i) = log p̂data(u, i) − log p̂data(i) + g(i) for a given i and any u.
Thus, for any u and i, this will always hold: − log p̂data(u) + f(u) ≡ − log p̂data(i) + g(i), so it must be some constant. Then we have ϕθ(u, i) = log p̂data(u, i) + C, where C is some constant that is independent of u and i. And when ϕθ(u, i) converges to log p̂data(u, i), both parts in Eq. 3 can reach their optima.

heading: A.4 EQUIVALENCE BETWEEN BERNOULLI AND MULTINOMIAL DISTRIBUTIONS ON MODELING THE USER-ITEM INTERACTION MATRIX
text: Here we show that by properly choosing the training data distribution, ϕθ(u, i) in Eq. 2 is actually approaching the conditional distribution p(i|u) or p(u|i), or joint distribution p(u, i), or p(u,i)p(u)p(i) .
Our derivation is inspired by Noise Contrastive Estimation (Gutmann & Hyvärinen, 2010).
In the modeling with Bernoulli distribution, we have two sets of samples, X and Y. X is the set of positive samples and Y is the set of negative samples randomly sampled based on a certain distribution pn(·). Assume X = {x1,x2, ...,xL} contains L samples, and Y = {y1,y2, ...,yT } contains T samples, and Z = X∪Y = {z1, z2, ...,zL+T } contains all the L+T samples. Here xl := (u, i), yt := (u, i) and zj := (u, i), where u ∈ U and i ∈ I. We assign each sample zj a binary class Cj : Cj = 1 if zj comes from X, and Cj = 0 if zj is from Y.
We assume the joint probability of positive samples in X is parameterized by θ is pmodel(u, i; θ) = pmodel(z; θ). So we have the conditional probabilities:
p(z|C = 1; θ) = pmodel(z; θ) p(z|C = 0; θ) = pn(z). (10)
The posterior probabilities are:
p(C = 1|z; θ) = pmodel(z; θ)P (C = 1) pmodel(z; θ)P (C = 1) + pn(z)P (C = 0) = 1 1 + exp(−G(z; θ)) , (11)
where
G(z; θ) = log pmodel(z; θ)P (C = 1)
pn(z)P (C = 0) , (12)
and we also have p(C = 0|z; θ) = 1
1 + exp(G(z; θ)) .
So the log-likelihood is:
l(θ) = L+T∑ j=1 Cj logP (Cj = 1|zj ; θ) + (1− Cj) logP (Cj = 0|zj ; θ).
Through optimizing the binary classification using samples in Z and the corresponding binary classes C, we are actually recovering the MF with Bernoulli distribution defined in Sec. 3.2.1. The dot product ϕθ(u, i) will converge to G(z; θ) in Eq. 12:
ϕθ(u, i) → log pmodel(z; θ)P (C = 1)
pn(z)P (C = 0) . (13)
Different negative sampling strategies will lead to very different optimal ϕθ(u, i). For example, if we randomly sample n items for each positive (u, i) pair to form negative samples with the u, then we have pn(z) = pn(u, i) = p̂data(u) · 1/K, where p̂data(u) is the empirical marginal probability of the positive samples. Substitute pn(z) into Eq. 13, we have
ϕθ(u, i) ≈ log pmodel(u, i; θ)
p̂data(u) + C ≈ log pmodel(i|u; θ) + C.
Similarly, if we randomly sample n users for each positive (u, i) pair to form negative samples with the i, then ϕθ(u, i) will converge to the conditional probability log pmodel(u|i; θ). For each positive (u, i) pair, if we randomly sample n items to form negative samples with the u, and also n users to form negative samples with the i, then ϕθ(u, i) will converge to the point-wise mutual information log pmodel(u,i;θ)pmodel(u;θ)pmodel(i;θ) .
And if the negative samples are randomly sampled uniformly from all users and items globally, then ϕθ(u, i) will converge to the joint probability log pmodel(u, i; θ).
Therefore, we show that MF with Bernoulli distribution and Multinomial distribution can be equivalent if we choose the proper negative sampling methods.

heading: A.5 MOTIVATION AND PRACTICAL APPLICATIONS OF TR
text: For the example of mining potential users given 1 billion users and 10,000 items, we list all the alternative methods that we can think of:
1. For each item, we create the training sample, and then train a binary classification model, and finally predict for the 1 billion users and pick the top 1 million. We need to repeat 10,000 times.
2. By emulating the RS, we model p(u|i) and obtain the embeddings of users and items, and then apply the ANN search (e.g., Faiss) to find the top 1 million users for each item. This method has a serious defect: ANN has high accuracy if we retrieve the top hundreds or thousands of candidates, but its accuracy and efficiency drops dramatically if we extend the range to millions. So, this method is not practical.
3. Also, we model p(u|i) and obtain the embeddings of users and items, and then do a brute force search: we calculate the similarity score of all the users and items, which is the Cartesian product of 1 billion users and 10,000 items, i.e., 10 trillion, and then we pick the top 1 million users for each item. It’s very inefficient and consume huge number of resources.
4. We build two models for p(i|u) and p(u|i) respectively. Then we use the embeddings of p(i|u) and apply the ANN search to find the top 10 items for each user. Now we have 10 billion u-i pairs, and we use the embeddings from p(u|i) to calculate the similarity score of the u-i pairs, and finally pick the top 1 million for each item.
TR has just one less model than the last alternative and one less step, but in practice, it is problematic to maintain two correlated models, especially when they are very large. Two models usually imply that the calculation is doubled, the storage is doubled, and the risk and instability are doubled.
To conclude, TR is the best choice that can balance the accuracy, efficiency, risk and maintainability in practice.

heading: A.6 EXPERIMENT RESULTS: RS
text: A.6.1 MF WITH BERNOULLI DISTRIBUTION
We compare to MF in Rendle et al. (2020) using the same datasets: binarized Movielens-1m (Harper & Konstan, 2015) and a dataset from Pinterest (Geng et al., 2015).

heading: Train and Evaluation Configurations
text: For each user, the last item is held out as the test set, and the second last is held out as the validation set, and the remaining as the training set. We use the validation set and training set to select the best hyper-parameters, and then re-train the model using both training and validation sets.
During evaluation, each user has his own candidates pool, and it consists of the withheld item (i.e., the ground-truth) and 99 sampled negative items. These methods will score the 100 items and rank them by the score.
The hyper-parameters τ and batch-size are chosen using the validation data. For Movielens-1m, we use τ = 0.125, batch-size = 4096 for MFb, and τ = 0.111, batch-size = 512 for TR. For Pinterest, we use τ = 0.143, batch-size = 8192 for MFb, and τ = 0.167, batch-size = 8192 for TR. We have d ∈ {16, 32, 64, 96, 128, 196} for a comprehensive comparison.

heading: Evaluation Metrics
text: Two evaluation metrics are employed to measure the performance of top-N ranked items:
HitRate@N = 1 |U| ∑ u∈U δ(|Îu,N ∩ Iu| > 0), (14)
where Îu,N denotes the top-N ranked items for u, Iu is the set of testing items, and δ(·) is the indicator function.
NDCG@N = 1 |U| ∑ u∈U
1
log(1 + ru) , (15)
where ru is the rank of the withheld item in the top-N items for u.

heading: Results
text: The performance of different methods is shown in Fig. 2. In general, MF with Bernoulli distribution and Multinomial distribution are comparable, which is consistent with our theory in Sec. 3.5.
The comparison of the converging speeds is shown in Fig. 3. We can see that modeling with Multinomial distribution is much better than Bernoulli distribution.

heading: A.6.2 SEQUENTIAL MODELING WITH MULTINOMIAL DISTRIBUTION
text: We compare to the models implemented in ComiRec (Cen et al., 2020). ComiRec provides the codes and two preprocessed datasets: Amazon books data (Ni et al., 2019) and Taobao click data (Zhu et al., 2018). So we use the same datasets and evaluation metrics for a fair comparison.

heading: Metrics and Comparing Methods
text: We use HitRate@N and Recall@N to measure the accuracy. HitRate@N is defined in Eq. 14, and Recall@N is defined below:
Recall@N = 1 |U| ∑ u∈U |Îu,N ∩ Iu| |Iu| . (16)
Metrics ‘Distinct items@N ’ counts the distinct items of all users’ top-N recommended list, and ‘Distinct cates@N ’ counts the distinct categories of these items. They measure the diversity of the recommendation results.
The comparing methods include the following:
• MostPopular recommends the most popular items to all users. • YouTube DNN (Covington et al., 2016) is a simple and very efficient neural network model
adopted in the CG stage of the large-scale industrial RS. • ComiRec-SA & ComiRec-DR (Cen et al., 2020) use self-attention (Vaswani et al., 2017)
or dynamic routing (Sabour et al., 2017) to explicitly incorporate users’ diverse interests in the model’s architecture to increase accuracy and diversity.

heading: Results
text: The results evaluated by the above metrics can be found in Fig. 4. We can see that their HitRate and Recall are comparable, and this is consistent with our theory in Sec. 3.5. The diversity of TR with Bi-InfoNCE is much better than other methods.
The performance of next-n-prediction are shown in Fig. 5. We investigate the KL Divergence of the marginal distributions of train and test data in Fig. 6, and show that the performance gain in Amazon data may be due to the reduced discrepancy between the train and test data.
In Taobao data, the discrepancy gets larger when we increase n, and in experiments the accuracy does not increase.

heading: A.7 EXPERIMENT RESULTS: PUMS
text: There are different ways of creating the validation and test datasets, such as randomly picking 10 users for each chosen item or each group of items.
Here we choose to holdout 1% users for the practical reason: usually we mine the potential users based on the historical behaviors and then deliver advertisement to them in the future, and the implicit assumption is that the distribution of the future is close to the past, i.e., popular items in the

heading: KL Divergence
text: past will be bought by more users in the future, and vice versa. So we holdout validation and test datasets in accordance with the overall distribution to emulate the practical scenario.

heading: A.7.1 POTENTIAL USERS OF A SINGLE ITEM
text: We create the training, validation and test data as described in Sec. 5.2. The statistics of the resulting datasets is shown in Tab. 4.

heading: The Metrics
text: Our evaluation metrics of accuracy are Precision@N and Recall@N :
Precision@N = 1
Itest ∑ i∈Itest |Ûi,N ∩ Ui| N ,
where Ûi,N denotes the top-N ranked users for i and Ui is the set of users for the testing item i.
Recall@N = 1
Itest ∑ i∈Itest |Ûi,N ∩ Ui| |Ui| .
We count the distinct users of all the test items to measure the diversity.

heading: Results of Converging Speed
text: The comparison of the converging speed can be found in Fig. 7. Similar to the results in Fig. 3 of RS, TR is much faster than MF with Bernoulli distribution.

heading: A.7.2 POTENTIAL USERS OF A GROUP OF ITEMS
text: For a given genre, we define the popularity of its movies in this way: we first rank the movies based on the number of users who have watched them, and then we pick the top/middle/bottom 10% movies as different groups. So we obtained 54 groups from 18 genres.
In practice, movies of different genres and different popularity will behave very differently, e.g., precision and recall of popular Action movies and unpopular Western movies will differ a lot. Movie-
lens have 18 genres, and we divide the movies of the same genre into 3 categories based on their popularity, so we can split the chosen movies into 54 groups.
Given a group and its affined items, we define its potential users this way: if a user interacts with one or more items in the group (excluding the items he has interacted previously), then he will be the potential users of the group. For example, given the group G = {i1, i2, i3} and the user u1, if u1 has interacted with i1 in the historical data, then we cannot pick him as the potential user; if in the future data, u1 interact with i2 or i3, then he will be regarded as the potential user of G.
Different groups have different number of movies, e.g., the group ‘Drama-top10%’ contains 93 movies, while ‘Documentary top10%’ has only 3 movies, and their precision and recall will also differ a lot. We report the averaged precision and recall over all groups in Tab. 5.
For small datasets like movie-lens-1m, the model generates the potential users of a group this way: for each item in the group, we first calculate ϕθ(u, i) of Eq. 2, and then the score p̂TR(u, i) = exp(ϕθ(u, i)) for TR and p̂MF(u, i) = σ(ϕθ(u, i))4 for MFb, with respect to the candidate users. Thus each candidate user will have several scores, and then we aggregate the scores to obtain a match score between the user and the group, and finally pick the top-k users. The aggregation methods could be max, mean or sum.
In Tab. 5, ‘MFb [0:8]’ and ‘TR [Uni-InfoNCE u2i]’ are specifically for u2i CG of RS, so they give the worst results here. Models tailored for i2u (‘MFb [8:0]’ and ‘TR [Uni-InfoNCE i2u]’) and the general model for bidirectional CG (‘TR [Bi-InfoNCE’) perform much better.
The aggregation methods also affect the accuracy, and mean > max > sum. If a user has scores with many items of the group, the sum could be high even if individual scores are low, and this also implies that the user has few interactions with the items of the group in the historical data. So it would not be suitable that sum ranks this user high. In contrast, mean and max will not have this problem, and mean considers more scores than just the max one and gives best results.
4σ(·) is the sigmoid function.

Review summaries:
This paper proposes to address candidate generations of users and items for recommender and advertising systems simultaneously by a single proposed model. The proposed model provides two ideas for existing two-tower recommendation models: it introduces a normalization of the score function and a bidirectional version of the InfoNCE loss. This paper evaluated the proposed method through several experiments. 

This paper jointly considers the problems of recommender systems (RS) and advertising systems (AS) as it is a coin’s two sides. The key is to model the joint probability of (user, item) instead of conditional probabilities (user | item) and (item | user) independently. The proposed model adapts an existing large-vocabulary loss function to the optimization objective. Experiments on real-world datasets are conducted to compare with both Matrix Factorization and Sequential Modeling methods.

This paper proposes a method for both user2item and item2user candidates generation in recommender systems. The main idea is to employ infoNCE loss for optimizing the two tower model. To achieve bidirectional candidates generation, the authors propose to do negative sampling in batch from both user side and item side, and use the Bi-InfoNCE loss for optimization.

This work proposes a bidirectional candidate generation framework for both recommender system (which provides items for a user) and advertising system (which provides users for an item). Specifically, the authors conduct a Bi-InfoNCE loss on the classical two-tower architecture to jointly learn both user and item representations. The Bi-InfoNCE loss considers each (u, i) pair as a positive instance, and selects both users and items as negative instances in InfoNCE. In experiments, the authors find that the proposed TR model outperforms MF in both recommender system and advertising system datasets.