Diversification of Complementary Item Recommendations with
User Preference in Online Grocery
Luyi Ma

Nimesh Sinha

Jason H.D. Cho

WalmartLabs
Sunnyvale, California
Luyi.Ma@walmartlabs.com

WalmartLabs
Sunnyvale, California
Nimesh.Sinha@walmartlabs.com

WalmartLabs
Sunnyvale, California
hcho@walmartlabs.com

Sushant Kumar

Kannan Achan

WalmartLabs
Sunnyvale, California
skumar4@walmartlabs.com

WalmartLabs
Sunnyvale, California
kachan@walmartlabs.com

ABSTRACTCCS CONCEPTS

Complementary item recommendations play an important role insurfacing the relevant items to the customers in online grocery
platform. Many research works focus on improving the recommendations through post-processing techniques such as user-item-level
personalization and diversification of recommendations. In online
grocery, complementary recommendations can fall into two types,
cross-domain and within-domain. Cross-domain complementary
recommendations refer to products that belong to two distinct
categories, for instance, for query item hot dog bun, steak andbarbecue sauce are cross-domain complementary items. On theother hand, for the same query item, chicken sausage and beefsausage form within-domain complementary recommendations
as they are from delicatessen. Although diversification of recommendations can promote cross-domain complementary recommendations, it can’t capture the within-domain complementary recommendations. Within-domain complementary recommendations
can not be replaced by similarity. Users also show their preferences on cross-domain or within-domain complementary items
during online shopping, which can be indicated by their shopping
behavior. However, many user-item-level personalization methods
can’t explicitly model the preference of users on cross-domain andwithin-domain complementary recommendations. To stress therequirement of modeling cross-domain and within-domain complementary recommendations with personalization, we propose ourre-ranking solution to provide fine-grained control of diversification on the complementary recommendations. We use transaction
history to estimate users’ preference for the level of diversity in thecomplementary recommendations and combine it to our re-ranking
solution. We demonstrate the effectiveness of our re-ranking algorithm on the publicly available Instacart dataset.

• Information systems → Information retrieval diversity; Similarity measures.

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
© 2018 Association for Computing Machinery.
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
https://doi.org/10.1145/1122445.1122456

KEYWORDS
Recommender systems, Diversity, Similarity, Re-ranking
ACM Reference Format:
Luyi Ma, Nimesh Sinha, Jason H.D. Cho, Sushant Kumar, and Kannan Achan.
2018. Diversification of Complementary Item Recommendations with User
Preference in Online Grocery. In ,. ACM, New York, NY, USA, 6 pages.
https://doi.org/10.1145/1122445.1122456

1

INTRODUCTION

Recommender system is an essential part of e-commerce business.
Recommending relevant items to customers make their experience
more comfortable, hassle-free, and time-saving. Online grocery platforms also have wide variety of recommendation systems placedat various sections of their websites to improve customer journey.
One such important section is complementary recommendations,where the customers can select different items from a recommendation pool. Complementary recommendations, in particular, show
products that customers frequently co-purchase. However, there
is no real definition of complementary items in online grocery. A
large number of items like bread, cereal, sugar, fruits, coffee, etc
can be complementary recommendations for the query item milk.
In online grocery, items from both within-domain and crossdomain are bought as complementary recommendations. Domain
can be defined in terms of any taxonomy hierarchy level in grocery.
In our case, we have defined domain as department level for thegrocery items. Cross-domain recommendations refer to the items
which belong to different and diverse departments, while withindomain recommendations refer to the items which belong to thesimilar departments. Note that the all the recommendations either
they are coming from cross-domain or within-domain are complementary to the query item. For example, suppose the query item
is tortilla chips, which has salsa dip, guacamole dip, and soft drink
as its complementary recommendations. A customer can buy salsa
dip and guacamole dip together from the recommendations which
are from within-domain or similar departments, while another customer can buy salsa dip and soft drink together which are fromcross-domain or different departments. All the three items - salsa

Ma, et al.
dip, guacamole dip, and soft drink are complementary to the query
item tortilla chips, but the recommendation pool in itself can have a
mixture of such within-domain and cross-domain complementary
items. It depends on the user intent to buy within-domain or crossdomain recommendations together.
Most of the recommendation systems optimize on accuracy anddiversity. It is not surprising, then, that a lot of researchers focus
on both personalization to improve recommendation relevance foreach individual user, and diversification to boost novelty. Diversification can promote the cross-domain complementary recommendations, but we need personalization to control the degree ofdiversification. Balancing out diversification and personalization
is a delicate task. Without careful calibration, one can overshadow
within-domain complementary recommendations (too much diversification), and vice versa.
To address these challenges, we utilize existing complementary
recommendations and deploy re-ranking strategy to balance out
within-domain and cross-domain recommendations. We further
combine user behavior to guide the diversification process. Some
users may prefer more within-domain recommendations, and viceversa.
We use re-ranking strategy based on Determinantal Point Process (DPP), combining the cross-domain and wihin-domain reranking with user intent to maintain the balance between the crossdomain and within-domain complementary recommendations. We
perform the re-ranking on top of complementary recommendation
pool because we want to ensure complementary relationship between the query item and recommended items. We also combine theuser behavior by utilizing their historical shopping pattern to model
the preferential balance between within-domain and cross-domain
complementary recommendations.

2

RELATED WORKS

Many past research works have focused on applying personalization in the recommendation systems. These works focus on modeling user preference to increase accuracy of the recommendations
and give better customer experience. Techniques like matrix factorization and collaborative filtering have been widely used [13][1]. Many research works focus on the complementary items byinferring item-item relations [3]. These complementary items havebeen personalized using both item relations and user preferences[17]. In online grocery platform, models like triple2vec have beenused to personalize the complementary recommendations using(item, item, user) triplets [6] [14].
For a long time, there was not much importance given to diversity in the recommendations as it is challenging to achieve both
high accuracy and diversity at the same time. This is called as accuracy diversity dilemma [9]. Novelty and diversity of items havebeen improved by penalizing accuracy [5]. Diversity has also been
captured in entropy regularizer [12]. Post-processing methods fordiversity have been proposed to improve the personalized recommendations generated by collaborative filtering [2]. Determinantal
Point Process (DPP) has been used for making personalized diversified recommendations. DPP model are elegant probabilistic models
which have a lot of applications. [8]. It has been incorporated with atunable parameter allowing the users to smoothly control the levelof diversity in recommendations and also, applied to large scale
scenarios with faster inference [15]. Deep reinforcement learning
has utilized DPP to promote diversity to generate diverse, while
relevant item recommendations. DPP kernel matrix is maintainedfor each user, which is constructed from two parts: a fixed similarity
matrix capturing item-item similarity, and the relevance of items
dynamically learnt through an actor-critic reinforcement learning
framework [10].
Most of the existing works revolve around tackling the challengesof personalization, and diversity in complementary recommendations. They don’t give much stress on maintaining the delicate
balance between within-domain and cross-domain complementary items. Our proposed method focuses on combined re-ranking
strategy for within-domain and cross-domain complementary recommendations including user intent.

3

MODEL

In this section, we first revisit the skip-gram-based embedding learning framework [14] and generating the item embedding used fordiversification. Then, we propose our algorithm under the settingof DPP to tackle both cross-domain and within-domain complementary recommendations. We estimate the user intent of cross-domain
and within-domain complementary item recommendation based ontransaction data and combine it with our DPP-based algorithm toprovide complementary item recommendation with user preference(personalization).

3.1

Background: Skip-gram-based Item
Embedding and triple2vec

As mentioned before, skip-gram based methods for item embedding leverage the item co-occurrence signal. Models for complementary item recommendations like [11], [3] exactly use the item
co-occurrence signal to model item complementarity. triple2vecin [14] introduced the cohesion of (𝑖𝑡𝑒𝑚, 𝑖𝑡𝑒𝑚, 𝑢𝑠𝑒𝑟 ) triplets whichreflect co-purchase of two items by the same user in the same basket. This technique improves the performance of complementary
item recommendations and triple2vec achieves the state-of-the-art
performance. As we focus on the post-processing of the recommendations, we decide to leverage the item representations learned bytriple2vec to generate item pools for down-stream applications.
In triple2vec, triplets of {(𝑞, 𝑟, 𝑢) | 𝑞 ∈ 𝑉 , 𝑟 ∈ 𝑉 , 𝑢 ∈ 𝑈 } represents user-item and item-item relationships where 𝑉 is the set ofitems and 𝑈 is the set of users. Here, 𝑞 and 𝑟 are two items purchased by the user 𝑢 in the same basket. Particularly, we refer 𝑞 to
the query item and 𝑟 to the recommended item. The relationship between 𝑞 and 𝑟 can be viewed in the way that 𝑟 is the recommended
complementary item for the query item 𝑞. The cohesion of (𝑞, 𝑟, 𝑢)
in triple2vec is computed by Eq. 1, where 𝑓𝑞 , 𝑔𝑟 are two sets ofrepresentations for items (𝑞, 𝑟 ) and ℎ𝑢 is the user embedding.
𝑥z}|{𝑠𝑞,𝑟,𝑢 = 𝑓𝑞𝑇 𝑔𝑟 + 𝑓𝑞𝑇 ℎ𝑢 + 𝑔𝑇𝑟 ℎ𝑢| {z }(1)𝑦𝑥 and 𝑦 in Eq. 1 indicate the item-to-item complementarity anduser-to-item compatibility respectively. The loss function L in Eq.

Diversification of Complementary Item Recommendations with User Preference in Online Grocery
2 computes the likelihood of all possible triplets T and is optimized
to learn representations of items and users.
Õ(log 𝑝 (𝑟 |𝑞, 𝑢) + log 𝑝 (𝑞|𝑟, 𝑢) + log 𝑝 (𝑢 |𝑞, 𝑟 )) (2)L=𝑞,𝑟,𝑢 ∈ T
exp(𝑞,𝑟,𝑢)exp(𝑞,𝑟,𝑢)𝑟

𝑞

in a greedy approach. Eq. 5 shows how to greedily select the next
candidate item 𝑗 which is added to the existing growing subset
𝑌𝑔 ⊆ 𝑍 built from the previous iterations. After the current iteration,Ð𝑌𝑔 grows and 𝑌𝑔 B 𝑌𝑔 { 𝑗 } 3 .

Here, 𝑝 (𝑟 |𝑞, 𝑢) = Í ′ exp(𝑞,𝑟 ′,𝑢) , 𝑝 (𝑞|𝑟, 𝑢) = Í ′ exp(𝑞′,𝑟,𝑢) and 𝑝 (𝑢 |𝑞, 𝑟 ) =Í exp(𝑞,𝑟,𝑢) ′ .
𝑢 ′ exp(𝑞,𝑟,𝑢 )We leverage triple2vec to learn item representations and generate item pools of complementary recommendations for downstream processes. To recall the item pool of complementary recommendations, we consider the inner product score 𝑓𝑞𝑇 𝑔𝑟 for two items
𝑞, 𝑟 . For each query item 𝑞, we select a pool of items 𝑅 = {𝑟 1, ..., 𝑟𝑚 }with the highest score of 𝑓𝑞𝑇 𝑔𝑟 .

3.2

𝑗 = arg max𝑖 ∈𝑍 \𝑌𝑔 log det(L𝑌𝑔 Ð {𝑖 } ) − log det(L𝑌𝑔 )When 𝑍 becomes the item pools for complementary recommendations 𝑅 = {𝑟 1, ..., 𝑟𝑚 } recalled by the item representations (i.e.,
item embedding learned by triple2vec), a DPP on 𝑅 maximizes
the P (𝑌 ) and diversifies the recommendations by selecting 𝑟𝑖 from
𝑅 iteratively. Now the kernel matrix L could be initialized by the
item-to-item similarity matrix based on the item embedding. In ourwork, we adapt DPP and FG-MAP, with L defined in Eq. 6.

Recommendation Diversification andDeterminantal Point Process

L=

Improving diversity of recommendations benefits the recommendersystems because it introduces novelty and better topic coverage[18]. Many works in diversification follow the setting of bi-criterion
optimization problem which balances the relevance (between thequery and recalled elements) and diversity [16]. Particularly, diversity can be further divided into two types, (1) individual diversity
1 and (2) aggregate diversity 2 [16]. We focus on the individual
diversity in this work to adjust the diversity of complementary
recommendations given a user’s intent.
The determinantal point process (DPP) is a probabilistic model
which is good at modeling repulsion. The recent work [4] applies
DPP on diversification of item recommendations and develop fast
greedy MAP inference to generate diversified recommendations.
Our work is based on DPP with the fast greedy MAP inference in[4]. Thus, we introduce details of DPP and the fast greedy MAP
inference following the notation in [4]. For the rest of our paper,
we denote the fast greedy MAP inference as FG-MAP.
Formally, a DPP on a discrete set 𝑍 = {1, 2, ..., 𝑀 } is a probability
measure P on 2 |𝑍 | number of subsets of 𝑍 , where |𝑍 | is the numberof elements in 𝑍 . Because the empty set is also a subset of 𝑍 , when
P doesn’t give zero probability to the empty set, there exists asquare, positive semidefinite (PSD) and real matrix L ∈ R𝑀×𝑀
which satisfies Eq. 3 for each subset 𝑌 ⊆ 𝑍 .
P (𝑌 ) ∝ det(L𝑌 ), L𝑌 ∈ R |𝑌 |× |𝑌 |(3)

L serves as a kernel matrix indexed by the elements in 𝑍 and det(L𝑌 )is the determinant of sub-matrix extracted from L based on elements
in 𝑌 . Eq. 3 indicates that the probability of a subset 𝑌 is proportional
to the determinant of the corresponding sub-matrix of the PSD
kernel. The MAP inference of the aforementioned DPP P on 𝑍 isdefined in Eq. 4.
𝑌𝑚𝑎𝑝 = arg max L𝑌
(4)
𝑌 ⊆𝑍

Unlike other inference on DPP, the MAP inference of DPP is NPhard. The algorithm FG-MAP approximates the MAP inference(5)

1 + 𝐻𝑇 𝐻, 𝐻 ≡ {𝑔𝑟𝑖 |𝑟𝑖 ∈ 𝑅}
2

(6)

𝐻 is a sub-matrix of the item embedding for the item pools 𝑅 recalledby the triple2vec model. 𝑔𝑟𝑖 is normalized embedding of item 𝑟𝑖
and the value of 𝐻 𝑇 𝐻 is shifted to ensure L is PSD. We only use
one set of item embedding from triple2vec model to computeitem similarity as the distance between 𝑓𝑞 and 𝑔𝑟 from two sets ofembedding represents the complementarity of (𝑞, 𝑟 ).

3.3

Cross-domain and Within-domain
Complementary Item Recommendation by
DPP with User Intent

As we mentioned in Session 1, complementary recommendations
in online grocery can fall into two types, (1) cross-domain and (2)within-domain. Cross-domain complementary recommendations
refers to products that belong to two distinct categories, for instance, steak and barbecue sauce, given the query item of hot dog
bun. Chicken sausage and beef sausage, on the other hand form
within-domain complementary recommendations as they are fromdelicatessen The within-domain complementary recommendations
can not be covered by similar item recommendations and also not
explicitly covered by existing complementary models like [14] [3].
Cross-domain Complementary Recommendations. The cross-domain
complementary recommendations can be achieved by increasing
the diversity in the complementary recommendations 𝑅 recalled
by a complementary item recommendation model, i.e., triple2vec.
We first generate 𝑅 to ensure complementary recommendations
and then re-rank items in 𝑅 to surface more diverse but relevant
items to the top. If we don’t conduct diversification within thepool of pre-selected complementary items, the diversification logic
could easily bias irrelevant items. We can re-rank the items in 𝑅 by
modifying FG-MAP into bi-criterion optimization. Specifically, we
1+𝑓 𝑇 𝑔𝑟

1 Individual diversity refers to the diversity of recommendations for a given user, or𝑞𝑖
consider the score 𝑆𝑞,𝑟𝑖 =for complementarity of (𝑞, 𝑟𝑖 ),2
where 𝑓𝑞 and 𝑔𝑟𝑖 are normalized item embedding. Eq. 7 shows theindividual diversity focuses on the problem of how to maximize item novelty in faceof already recommended ones when generating the recommendation list.
2 Aggregate diversity refers to the diversity of recommendations across all users, oraggregate diversity can be viewed as a problem of how to improve the ability of arecommender system to recommend long-tail items.

3 For more details of the Fast Greedy MAP inference algorithm, please refer to [4].

Ma, et al.
modified objective function for diversification re-rank.
𝑟 𝑗 = arg max𝑟𝑖 ∈𝑅\𝑅𝑑

𝛼𝑆𝑞,𝑟𝑖|{z}
complementarity+ (1 − 𝛼) log det(L𝑅𝑑 +[𝑟𝑖 ] ) − log det(L𝑅𝑑 )|{z}
increment of diversification(7)
At 𝑡-th iteration, 𝑅𝑡,𝑑 B 𝑅𝑡 −1,𝑑 + [𝑟 𝑗 ] where 𝑅0,𝑑 = [] and 𝑅𝑡 −1,𝑑 +[𝑟 𝑗 ] means the newly selected recommendation 𝑟 𝑗 by the diversification re-rank is inserted at the end of the current item list 𝑅𝑡 −1,𝑑 .
The weight 𝛼 controls the amount of diversity introduced to the reranked item list. Each selected item 𝑟 𝑗 can maximize the combined
score of diversity and complementarity. The re-ranked item list 𝑅𝑑
will surface more diversified recommendation to the top comparedwith the original item list 𝑅 in which items are simply sorted by
the score 𝑆𝑞,𝑟𝑖 in descending order.
Within-domain Complementary Recommendations. The withindomain complementary recommendations is different from thecross-domain complementary recommendations. We need to surface more items which are related to the query items but under
the same topic instead of diverse results. For example, assume aquery item Milk has a list of recommendations 𝑅 = {Eggs, Cheese,
Bread, Margarine, Banana, Sausage, Yogurt, Cereal}. If we want tostress the within-domain complementary recommendations, there-ranked recommendations could be 𝑅𝑠 = {Eggs, Cheese, Margarine, Yogurt, Banana, Bread, Sausage, Cereal} 4 . We encourage
more homogeneousness in the within-domain complementary recommendations. 𝑅𝑠 surfaces more items under the Dairy & Eggs
domain such as Cheese, Yogurt. The within-domain complementary recommendations can be promoted by similarity of items in
the recall set of complementary recommendations. Unlike diversification for cross-domain complementary recommendations which
is diverging the item relationship, boosting within-domain complementary recommendations by similarity is more stable. We canmind candidate items in a bigger recall set. Formally, we recall extra
complementary items 𝑅𝑥 = {𝑟𝑚+1, ..., 𝑟𝑛 } and insert them at theend of 𝑅. The new item list becomes 𝑅 + 𝑅𝑥 . To force the similarity
between recommendations, we modify the kernel L in DPP by Eq.
8 and apply DPP on the new dissimilarity matrix L ′L ′ = 1 + diag(L) − L(8), where diag(L) is a diagonal matrix with all entries in the main
diagonal equal to the diagonal of L and 1 is a square matrix withall entries equal to 1. Plug L ′ into Eq. 7, and we can have a new
re-ranking logic on the extended item pool 𝑅 + 𝑅𝑥 , shown in Eq. 9 .
𝑟ℎ = arg max𝑟𝑖 ∈ (𝑅+𝑅𝑥 )\𝑅𝑠

𝛽𝑆𝑞,𝑟𝑖|{z}Here, the parameter 𝛽 is used to control the degree of similarity
between recommendations. At 𝑡-th iteration of Eq. 9, 𝑅𝑡,𝑠 B 𝑅𝑡 −1,𝑠 +[𝑟ℎ ] where 𝑅0,𝑠 = [].
Both Eq. 7 and 9 can be optimized by the FG-MAP algorithm
mentioned in [4] 5User Intent Modeling. Only having cross-domain and withindomain re-ranking strategies is not enough because we need tofigure out when to use cross-domain re-ranking and when to use
within-domain re-ranking. We leverage the heuristic that users who
prefer cross-domain complementary recommendations for a query
item might add more diverse items during the next-𝑘 purchases
while users who prefer within-domain complementary recommendations for a query item might add less diverse items during thenext-𝑘 purchases.
Formally, given a query item 𝑞 at time 𝑡 and a list of next-𝑘
items 𝐵𝑞 = {𝑏𝑡 +1, ..., 𝑏𝑡 +𝑘 } purchased by the user 𝑢, we leverage thetaxonomy information 𝑡𝑎𝑥 (·) 6 to estimate how much diversity theuser 𝑢 prefers. Let 𝐵𝑇 ,𝑞 = {𝑡𝑎𝑥 (𝑏𝑡 +1 ), ..., 𝑡𝑎𝑥 (𝑏𝑡 +𝑘 )} be the list of
departments of the next-𝑘 items purchased by the user and |𝐵𝑇 ,𝑞 |be the number of unique elements in 𝐵𝑇 ,𝑞 . We can compute an
estimation of degree of diversity for the query item 𝑞 and the user
𝑢 in Eq. 10.
|𝐵𝑇 ,𝑞 |𝑧𝑢,𝑞 =(10)𝑘
However, the score 𝑧𝑢,𝑞 is at user-item level and not stable due tothe sparsity issue. We then extend it to a score at user-department
level to reduce the sparsity, shown in Eq. 11, where 𝑑𝑒𝑝𝑡𝑖 is thedepartment 𝑖 and the score 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 is an average of score 𝑧𝑢,𝑞 for
any query items satisfying 𝑡𝑎𝑥 (𝑞) = 𝑑𝑒𝑝𝑡𝑖 .

𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 =

1
𝑁

𝑁
Õ

𝑧𝑢,𝑞

(11)

{𝑞 |𝑡𝑎𝑥 (𝑞)=𝑑𝑒𝑝𝑡𝑖 }We can use a threshold 𝑇 ∈ [0, 1] to binarize 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 learnt fromthe training data. If 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 < 𝑇 , the user 𝑢 prefers the more converged scope of complementary items for the query items under
the department 𝑑𝑒𝑝𝑡𝑖 , otherwise, the user 𝑢 might prefer more diversified complementary items because 𝑢 tends to add items fromdifferent departments during the next-𝑘 purchases. We can combine
the score 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 with the re-ranking strategies of cross-domain
and within-domain complementary recommendation to develop
a dynamic re-ranking algorithms (shown in Algorithm 1) It provides either cross-domain re-ranking strategy or within-domain
re-ranking strategy based on the user intent on a certain department
𝑑𝑒𝑝𝑡𝑖 of the query item 𝑞.
We add 𝑧 0 as a default value for cold departments of query items
which are not seen in the history. 𝑧 0 could be initialized by theaverage of all 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 .

complementarity 4 EVALUATION+ (1 − 𝛽) log det(L ′𝑅𝑠 +[𝑟𝑖 ] ) − log det(L ′𝑅𝑠 )In this section, we evaluate our proposed solution on the publicly|{z}available Instacart Dataset [7]. We also conduct a parameter analysis
increment of similarity between recommendationsof re-ranking performance with different 𝑇 .
(9)4 The diversification re-rank aforementioned could result in 𝑅𝑑

Cheese, Bread, Sausage, Cereal, Margarine, Yogurt}= {Eggs, Banana,

5 The algorithm 1 in [4] .
6 𝑡𝑎𝑥 ( ·) returns the department of the input item.

Diversification of Complementary Item Recommendations with User Preference in Online Grocery
Algorithm 1 Dynamic Re-ranking of Complementary Recommendation with User Intent
Require: 𝑢, 𝑞, 𝑅, 𝑅𝑥 , 𝛼, 𝛽, 𝑇 , 𝑧 0 , 𝑘;
Ensure:1: 𝑅𝑜𝑢𝑡 = []2: 𝑑𝑒𝑝𝑡𝑖 = 𝑡𝑎𝑥 (𝑞)3: if 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 available then4:
use 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖
5: else6:
𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 = 𝑧 0
7: end if
8: if 𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 > 𝑇 thenuse 𝑅, 𝛼 to compute 𝑅𝑑 by Eq. 7 and FG-MAP with 𝑘 itera9:
tions (cross-domain)
10:
𝑅𝑜𝑢𝑡 B 𝑅𝑑
11: else12:
use 𝑅 + 𝑅𝑥 , 𝛽 compute 𝑅𝑠 by Eq. 9 and FG-MAP with 𝑘iterations (within-domain)
13:
𝑅𝑜𝑢𝑡 B 𝑅𝑠
14: end if
15: return 𝑅𝑜𝑢𝑡 as the re-ranked complementary recommendations for 𝑢 and 𝑞

4.1

Evaluation Setting

The Instacart dataset [7] has 49,677 distinct items, 134 distinct
aisles, 21 distinct departments and 206,209 distinct users. We train
triple2vec model on the Instacart training dataset, with embedding dimension of 100, batch size of 128, initial learning rate of
0.05 and Stochastic Gradient Descent optimizer. We also compute𝑧𝑢,𝑑𝑒𝑝𝑡𝑖 for each pair of (𝑢, 𝑑𝑒𝑝𝑡𝑖 ) for the next-5 purchase (𝑘 = 5
in Eq. 10). When evaluating the re-ranking strategies, we compare results before and after the re-rank. Given a query item 𝑞, auser 𝑢 and recommendations 𝑅, 𝑅𝑥 generated by triple2vec model,
we compute the Hit-Rate@5 and Normalized Discounted Cumulative Gain (NDCG@5) for raw complementary recommendation 𝑅
and the re-ranked complementary recommendations by (1) crossdomain, (2) within-domain and (3) combined strategy with user
intent, on the task of next-item prediction. The reason why wefocus on next-5 purchase is because the user intent might last
for a short period and we want to study the impact of two different complementary recommendations in the top recommendations. If we consider bigger 𝑘, it is likely to introduce diversity
for recommendations. Here, we define 𝑅 = {𝑟 1, 𝑟 2, 𝑟 3, 𝑟 4, 𝑟 5 } and𝑅𝑥 = {𝑟 6, 𝑟 7, 𝑟 8, 𝑟 9, 𝑡 10 } to cooperate the metrics of Hit-Rate@5 and
NDCG@5. To use cross-domain re-ranking only, we set 𝑇 to be
0. Similarly, we use 𝑇 = 1 to force within-domain re-ranking. To
further understand the trade-off between cross-domain re-ranking
and within-domain re-ranking, we evaluate the combined strategy
with 𝑇 ∈ {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}. We use 𝛼 = 𝛽 = 0.01
for evaluations.

4.2

Evaluation Results

We evaluate our re-ranking strategies on the Instacart evaluation dataset and the detailed results are shown in Table 1. The
cross-domain re-ranking strategy improves the Hit-Rate@5 andTable 1: Detailed Results of Next-Item Prediction

raw recommendation
T = 0 (cross-domain)
T = 0.1
T = 0.2
T = 0.3
T = 0.4
T = 0.5
T = 0.6
T = 0.7
T = 0.8
T = 0.9
T = 1 (within-domain)

Hit-Rate@5

NDCG@50.055810.055810.056120.05625
0.056120.05558
0.05388
0.05259
0.05261
0.05261
0.05261
0.05261

0.032160.03379
0.03380
0.03377
0.03371
0.033180.032140.03133
0.031280.03127
0.03127
0.03127

NDCG@5 compared with the raw recommendations, while only
using within-domain re-ranking strategy reduces the performance.
Combining both re-ranking strategies together with a proper 𝑇
improves the overall performance. Particularly, 𝑇 = 0.2 achieves
the best Hit-Rate@5 with and 𝑇 = 0.1 achieves the best NDCG@5.
This result is reasonable because 𝑇 = 0.2 means on average users
purchase next 5 items under the same department. The evaluation result show better performance for covering users who preferwithin-domain recommendations.
Note that, pure within-domain re-ranking reduces both HitRate@5 and NDCG@5. It might be because only showing complementary recommendations in a narrow scope is likely to missusers’ interests. If a user is not interested in the first recommended
item, this user will be likely not interested in the following recommendations because they are similar. Cross-domain re-ranking
improves this by surfacing different complementary items to thetop. Now the re-ranked recommendations are more likely to match
this user’s interests. Combining these two strategies together actually covers the requirements of cross-domain and within-domain
complementary recommendations. Those users who prefer withindomain recommendations are now covered by the within-domain
re-ranked strategy.
Our result shows that combining cross-domain and within-domain
re-ranking strategies improves the overall performance, which indicates simple diversification of recommendations could be further
improved by fine-grained re-ranking.

5

CONCLUSION AND FUTURE WORK

We focus on the re-ranking of complementary recommendations in
Online Grocery and point out the (1) cross-domain and (2) withindomain requirements in complementary recommendations. To fulfill these two requirements, we propose a re-ranking solution basedon DPP on the raw complementary recommendations by combining cross-domain and within-domain re-rankings dynamically. We
demonstrate the effectiveness of our solution on the publicly available Instacart dataset.

Ma, et al.
There is scope of future work in the following directions: (1) abetter estimation or representation of the users’ intent on crossdomain and within-domain strategy, (2) applying techniques suchas reinforcement learning or multi-armed bandit.

May 10-14, 2005. ACM, 22–32. https://doi.org/10.1145/1060745.1060754

REFERENCES[1] Mohamed Hussein Abdi, George Onyango Okeyo, and Ronald Waweru Mwangi.
2018. Matrix Factorization Techniques for Context-Aware Collaborative Filtering
Recommender Systems: A Survey. Computer and Information Science 11, 2 (2018),
1–10. https://doi.org/10.5539/cis.v11n2p1[2] Gediminas Adomavicius and YoungOk Kwon. 2012. Improving Aggregate Recommendation Diversity Using Ranking-Based Techniques. IEEE Trans. Knowl.
Data Eng. 24, 5 (2012), 896–911. https://doi.org/10.1109/TKDE.2011.15[3] Oren Barkan and Noam Koenigstein. 2016. Item2vec: Neural Item Embedding
for Collaborative Filtering. In Proceedings of the Poster Track of the 10th ACM
Conference on Recommender Systems (RecSys 2016), Boston, USA, September 17,
2016 (CEUR Workshop Proceedings), Vol. 1688. CEUR-WS.org. http://ceur-ws.org/
Vol-1688/paper-13.pdf[4] Laming Chen, Guoxin Zhang, and Eric Zhou. 2018. Fast Greedy MAP
Inference for Determinantal Point Process to Improve Recommendation
Diversity. In Advances in Neural Information Processing Systems 31: Annual
Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8
December 2018, Montréal, Canada. 5627–5638. http://papers.nips.cc/paper/
7805-fast-greedy-map-inference-for-determinantal-point-process-to-improve-recommendation-diversity[5] Jorge Díez, David Martínez-Rego, Amparo Alonso-Betanzos, Oscar Luaces, andAntonio Bahamonde. 2019. Optimizing novelty and diversity in recommendations.
Prog. Artif. Intell. 8, 1 (2019), 101–109. https://doi.org/10.1007/s13748-018-0158-4[6] Valeria Fionda and Giuseppe Pirrò. 2019. Triple2Vec: Learning Triple Embeddings
from Knowledge Graphs. CoRR abs/1905.11691 (2019). arXiv:1905.11691 http://arxiv.org/abs/1905.11691[7] The instacart online grocery shopping dataset 2017. Accessed on Dec. 2017.
https://www.instacart.com/datasets/grocery-shopping-2017.
[8] Alex Kulesza and Ben Taskar. 2012. Determinantal point processes for machinelearning. CoRR abs/1207.6083 (2012). arXiv:1207.6083 http://arxiv.org/abs/1207.
6083[9] Jian-Guo Liu, Kerui Shi, and Qiang Guo. 2012. Solving the accuracy-diversity
dilemma via directed random walks. CoRR abs/1201.6278 (2012). arXiv:1201.6278
http://arxiv.org/abs/1201.6278[10] Yong Liu, Yinan Zhang, Qiong Wu, Chunyan Miao, Lizhen Cui, Binqiang Zhao,
Yin Zhao, and Lu Guan. 2019. Diversity-Promoting Deep Reinforcement Learning
for Interactive Recommendation. CoRR abs/1903.07826 (2019). arXiv:1903.07826
http://arxiv.org/abs/1903.07826[11] Julian J. McAuley, Rahul Pandey, and Jure Leskovec. 2015. Inferring Networks of Substitutable and Complementary Products. In Proceedings of the21th ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, Sydney, NSW, Australia, August 10-13, 2015. ACM, 785–794. https://doi.org/10.1145/2783258.2783381[12] Lijing Qin and Xiaoyan Zhu. 2013. Promoting Diversity in Recommendation
by Entropy Regularizer. In IJCAI 2013, Proceedings of the 23rd International Joint
Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. IJCAI/AAAI,
2698–2704. http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6511[13] Panagiotis Symeonidis and Andreas Zioupos. 2016. Matrix and Tensor Factorization Techniques for Recommender Systems. Springer. https://doi.org/10.1007/
978-3-319-41357-0[14] Mengting Wan, Di Wang, Jie Liu, Paul Bennett, and Julian J. McAuley. 2018. Representing and Recommending Shopping Baskets with Complementarity, Compatibility and Loyalty. In Proceedings of the 27th ACM International Conference on
Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26,
2018. ACM, 1133–1142. https://doi.org/10.1145/3269206.3271786[15] Mark Wilhelm, Ajith Ramanathan, Alexander Bonomo, Sagar Jain, Ed H. Chi, andJennifer Gillenwater. 2018. Practical Diversified Recommendations on YouTube
with Determinantal Point Processes. In Proceedings of the 27th ACM International
Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy,
October 22-26, 2018. ACM, 2165–2173. https://doi.org/10.1145/3269206.3272018[16] Qiong Wu, Yong Liu, Chunyan Miao, Yin Zhao, Lu Guan, and Haihong Tang.
2019. Recent Advances in Diversified Recommendation. CoRR abs/1905.06589(2019). arXiv:1905.06589 http://arxiv.org/abs/1905.06589[17] Yin Zhang, Haokai Lu, Wei Niu, and James Caverlee. 2018. Quality-aware neuralcomplementary item recommendation. In Proceedings of the 12th ACM Conference
on Recommender Systems, RecSys 2018, Vancouver, BC, Canada, October 2-7, 2018,
Sole Pera, Michael D. Ekstrand, Xavier Amatriain, and John O’Donovan (Eds.).
ACM, 77–85. https://doi.org/10.1145/3240323.3240368[18] Cai-Nicolas Ziegler, Sean M. McNee, Joseph A. Konstan, and Georg Lausen. 2005.
Improving recommendation lists through topic diversification. In Proceedings ofthe 14th international conference on World Wide Web, WWW 2005, Chiba, Japan,