# Bridging the Gap Between Information Seeking and Product Search Systems: Q&A
Recommendation for E-commerce

###### Abstract

Consumers on a shopping mission often leverage both product search and
information seeking systems, such as web search engines and Question Answering
(QA) systems, in an iterative process to improve their understanding of
available products and reach a purchase decision. While product search is
useful for shoppers to find the actual products meeting their requirements in
the catalog, information seeking systems can be utilized to answer any
questions they may have to refine those requirements. The recent success of
Large Language Models (LLMs) has opened up an opportunity to bridge the gap
between the two tasks to help customers achieve their goals quickly and
effectively by integrating conversational QA within product search. In this
paper, we propose to recommend users Question-Answer (Q&A) pairs that are
relevant to their product search and can help them make a purchase decision.
We discuss the different aspects of the problem including the requirements and
characteristics of the Q&A pairs, their generation, and the optimization of
the Q&A recommendation task. We highlight the challenges, open problems, and
suggested solutions to encourage future research in this emerging area.

##  1 Introduction

Currently, most shoppers looking to purchase a product online rely on both
e-commerce and information seeking systems. Search engines in online shopping
websites are built on top of a catalog of the available products and are used
by shoppers to explore the different offerings, obtain product specific
information, and finally make a purchase [Sondhi et al., 2018]. Information
seeking systems (mainly web search engines, but more recently also question
answering systems) are used by shoppers to complement their product search.
This is because users often do not have enough knowledge to confidently make a
purchase decision and thus leverage information seeking systems to acquire
relevant knowledge to assist them in their shopping journey [Rowley, 2000;
Branco et al., 2012].

This process, however, is not optimal. First, users that search for products
may not have enough knowledge to ask the right questions in an information
seeking system. Second, an independent information seeking system does not
directly take into account the full context of the user in product search
(e.g., the product detail page that the user is viewing or the set of search
results). For those reasons, as illustrated in Figure 1, users would often
need to frequently switch between the two systems to refine their requirements
and finally reach a purchase decision. This results in a lengthy process
requiring substantial user effort to achieve their shopping goals. Some recent
work has attempted to address these issues by enabling product search systems
to answer informational queries [Chen et al., 2023], but combining these
distinct features in a single interface may not be intuitive for users.

In this opinion paper, we propose a new product search paradigm to bridge the
gap between information seeking and product search systems. Specifically, the
idea is to suggest Q&A pairs to shoppers at different places in a product
search system, as illustrated in Figure 2. This can assist them in acquiring
important purchase-related information with minimal effort. This new direction
is quickly becoming a reality, as exemplified by Amazon’s new Rufus
conversational shopping experience launched in February
2024.111https://www.aboutamazon.com/news/retail/amazon-rufus We discuss the
different aspects of the proposed approach including the characteristics of
the suggested questions and answers, Q&A generation approaches, quality
control, and the optimization of the recommendation task. The paper can serve
as a roadmap for implementing such a system, and highlights the different
challenges and open problems that need to be addressed.

Figure 1: The current online shopping process. Users are switching between
information seeking systems and product search to reach a purchase decision.
The dashed arrow represents our envisioned approach to bridge the gap between
the two systems.
---
Figure 2:  An illustration of the suggested questions interface for the auto-
complete stage.

The rest of the paper is organized as follows. We begin by explaining the
shopping journey of users in online shopping and how it intersects with the
suggested Q&As. Then, we move to discuss the different requirements from the
questions and answers in such a system, generation approaches, and quality
control. We conclude the paper with a discussion about different directions
for addressing the optimization of the recommendation system with user
feedback.

##  2 Q&A and the Shopping Journey

To implement a useful Q&A suggestion system in product search, it is crucial
to understand the shopping journey of online customers and how Q&As can be
integrated in it successfully. Online shopping users start their journey with
a shopping goal which is a set of requirements from a desired product. The
users would then go through several stages that dictate the specificity of
those requirements. In general, users would come with an initial set of
requirement that are expected to narrow down toward the chosen product as they
view different options from the catalog and acquire any necessary knowledge
related to their search. Users in product search would usually be in one of
the following stages:

  1. 1.

Exploration: users are at the beginning of their shopping journey and are
learning about the product space and are refining their requirements.

  2. 2.

Comparison: users have narrowed down their requirements and are comparing
across several products that meet them.

  3. 3.

Final Consideration: users are focused on a small set of products and ask
specific questions about them to make a purchase decision.

Table 1:  Examples of suggested questions in different entry points of a
product search system. Auto-complete
---
Context | “coffee”
Questions | What are the different types of coffee machines?
How to choose a coffee table for your space?
What coffee mugs are in style?
Context | “juicer”
Questions | What features should I look for when buying a juicer?
What are the best juicers for beginners?
What types of juicers are good for leafy greens?
Search Result Page
Context | “coffee machine single cup”
Questions | How do single cup coffee machines work?
What maintenance is required for single-cup coffee machines?
What are the differences between single-cup machines and traditional ones?
Context | “cold press juicer”
Questions | How do cold press juicers compare to centrifugal juicers?
What are the pros and cons of vertical vs. horizontal cold press juicers?
What are some popular brands of cold press juicers?
Product Detail Page
Context | “Amazon Basics Single Cup Coffee Machine”
Questions | Is it easy to clean?
What are the dimensions?
Is the tray adjustable?
Context | “Vertical Cold Press Juicer for Fruits and Vegetables”
Questions | What do customers think about its durability?
Is it noisy?
Are the parts dishwasher safe?

From the system perspective, the different stages correspond to different user
experiences in the product search system which result in different modalities
of Q&A recommendations, as illustrated in Table 1. The first one is auto-
complete Q&A suggestion. Specifically, the idea is to present broad and
exploratory related questions while users type their product search query (see
Figure 2). The second one is Search Result Page (SERP) Q&A suggestion. The
idea here is to suggest questions that are embedded in the SERP. This is
similar to the “People Also Asked” suggested questions in web search engines
[Matias et al., 2017] but would need to include shopping specific questions
that are related to the products being shown. The final modality is product
detail page Q&A suggestion. The idea here is to suggest Q&A pairs that are
relevant to a specific product.

The different entry points, since users encounter them in different stages of
their shopping journey, require different types of Q&As. For example,
questions in the SERP are expected to be broader than those in the product
detail page since users have not yet narrowed down their requirements to a
specific product and are still learning about the different options.
Similarly, questions in the auto-complete modality are expected to be even
broader than SERP questions because the shopping goal of the user at this
stage is unclear to the system.

##  3 Q&A Requirements

Presenting users with the most appropriate questions to their shopping goal
and the specific stage of their shopping journey is crucial for the success of
the Q&A system. First, we note that questions can represent various intents
that can be relevant to different stages in the shopping journey. For example,
a question which asks to compare between two products or product categories
(e.g., “What is the difference between single-cup and traditional coffee
machines?”) can be appropriate for the exploration and comparison stages but
not as much to the detail page of a product. On the other hand, a question
with the intent of learning about an aspect of a product (e.g., “What is the
voltage of this coffee machine?”) is more appropriate once the user narrowed
down their search to very few options. Some of the popular intents include the
following ones.

  * •

Aspect: Seeking information about an aspect of a specific product or a group
of products.

  * •

Comparison: Comparing two or more products, or different aspects of the same
product.

  * •

General Knowledge: Seeking some general knowledge that may help the user
choose the right product.

  * •

Superlative: Asking for the best products on a given aspect.

  * •

How-to: Seeking guidance on how to use a specific product or a group of
products.

  * •

Offer: Various topics like pricing, shipping, return policy, refund policy,
product availability, and warranty.

  * •

Subjective: Seeking opinions of other users.

  * •

Search: Recommendation for products that meet some requirements.

Across the different intents, there can be several common requirements for the
questions in a specific shopping journey stage. A minimal requirement is for
the questions to be relevant to the context (e.g., the query or the product
detail page). The question must also be useful for making a purchase decision
given the current stage of the user. Another important requirement is
specificity. We want to a question to as specific as needed given the user
background and the shopping journey phase. Finally, we want the questions to
be concise by including only the necessary information to users to accommodate
small screens and the short attention span of users.

As for the answers to the questions, there are also several general
requirements that we need to consider in the context of product search. The
minimal requirement from the answer is to be factually correct. This is a very
important requirement as users are relying on those recommendations when
buying a product and may lose their trust in the system if wrong information
led them to make a wrong purchase decision. Since the answers are within a
product search system, another requirement is for them to be always shopping
related to help users in their shopping journey. For example, if the question
is “What is the difference between espresso and drip coffee?”, the answer may
also recommend related products such as espresso machines. Another important
consideration is for the answer to leverage the right type of information
based on the question intent. For instance, while subjective questions would
mainly rely on customer reviews, product aspect questions would leverage the
product catalog. Finally, similarly to questions, we would like the answers to
be informative but concise.

##  4 Q&A Generation

To obtain the questions and answers for Q&A recommendation, one common
approach used in the previous work relies on query logs to mine popular user
questions [Mitra et al., 2021, 2020]. Then, based on the questions, answers
can be generated using abstractive QA from relevant documents. This approach
has several limitations in the context of product search engines. First, users
in product search engines mainly use keyword queries and do not write fully
formed questions, making approaches that rely on logs not applicable. Second,
product search engines are built on top of product catalogs and do not
typically have easy access to external knowledge.

For those reasons, we propose to use LLMs for the generation of Q&A pairs.
Using LLMs is advantageous for the task since they can generate both the
question and the answer from their internal knowledge [Hämäläinen et al.,
2023; Hartvigsen et al., 2022]. To generate questions that are useful for the
context, we can provide the context information as part of the input (e.g.,
the query, items in the SERP, or the product detail page). LLMs also have good
capability to process long inputs, which means that we can provide it with
different types of data to generate a variety of interesting questions. For
example, for product detail page questions we can use customer reviews, the
product specifications, and relevant external knowledge to generate questions.
Some of these ideas have been explored by Vedula et al. [2024] in the context
of shopping assistants.

Using an LLM, we are also interested in controlling the different aspects of a
question to satisfy the different requirements such as specificity and intent.
While this can be potentially achieved through appropriate prompting, there
can be a limit on the instruction following capability of the model given a
very long prompt. For that reason, one option can be to create different
prompts for the various scenarios to optimize the question generation for
them. For example, we expect the instructions for question generation for SERP
to be different than the ones of the product page. Finally, it is also
important to note that some aspects that are needed to be controlled, such as
intent, are domain specific, making it potentially necessary to further fine-
tune the LLM to follow the instructions successfully.

For answer generation, similarly to the case of questions, a promising
technique would be to use retrieval augmented generation with an LLM. One key
consideration in doing that is to decide which retrieval evidences are
relevant to the specific question. For example, while customer reviews are the
most useful for subjective questions, product aspect questions may benefit the
most from information in the product catalog. Ideally, we can provide all of
the different sources of retrieval to the LLM. This approach, however, may
have some disadvantages such as input length limit, latency, and sensitivity
to noise. An alternative approach can be to leverage different retrieval
sources for different types of questions which would require a question
classification model.

One aspect that is common for both the question and the answer is
personalization. We envision the ideal Q&A system as one that provides
questions and answers that are tailored to the specific user. Specifically, we
would like to propose questions that are a good fit for the user’s background
knowledge and interests. To achieve that, one way would be to leverage
information about past purchases of the user that can be included in a
personalized prompt to generate specific questions and answers for them.

Finally, deploying and maintaining an LLM-based Q&A recommendation system also
poses challenges for high latency and costs associated with the inference of a
large model. Some solutions for that can include caching of the questions,
offline generation for the head of the traffic, and online ranking of offline
generated questions.

##  5 Evaluation and Quality Control

The implementation of mechanisms for quality control of the Q&A feature are
essential for maintaining user trust and ensuring a consistent and helpful
experience at production-scale. One of the main challenges for implementing
such a mechanism is the large scale of possible input contexts which include
the products in the catalog as well as search queries and query prefixes. A
reliable quality control mechanism at this scale can be achieved by using a
combination of human annotations, automatic (LLM-based) evaluation, and online
engagement signals. The quality control should verify two main aspects. First,
the questions should satisfy some minimal requirements to be acceptable.
Second, the questions should be useful to the users, where there can several
degrees of usefulness.

The minimal requirements for questions should be assessed in a point-wise
manner by examining each question independently with either a human annotator
or an LLM. Below are some of the basic requirements that should be considered.

  * •

Relevance: At the minimum, the questions presented should be relevant to the
context in which they are presented. For answers, we would like to ensure that
they are at least relevant to the questions.

  * •

Hallucination-free: It is important to verify that the number of hallucinating
cases is minimal and under a predefined threshold. This is crucial for
maintaining user trust since they are relying on the provided information to
make a purchase decision.

  * •

Style: The questions should be natural sounding and well-formed. Furthermore,
depending on other user experience guidelines, we would like to ensure that
the questions and answers are following a specific style. For example, showing
concise questions in friendly tone can be such a requirement.

  * •

Trust and Safety: At the minimum, we must ensure that we do not generate
questions and answers that contain information that can hurt the trust of the
users, be offensive, or result in actions that are not safe.

For testing the usefulness of questions, the main goal is to find to what
extent the questions and answers can help users to make a purchase decision
given the context in which they are shown. The evaluation of usefulness can be
achieved by leveraging three complementary approaches. First, using online
engagement signals such as clicks or purchases can provide indication for the
usefulness of questions. While this approach directly measures the customer
engagement, it can contain noise and thus can only focus on the head of the
traffic. Furthermore, it can be challenging to factor out other reasons for
the user actions. Another approach would be to rely on LLM annotations. This
approach can be done at scale to increase the testing coverage, but can biased
to the LLM assumptions of what is considered useful. Finally, human
annotations can be used at a smaller scale, but the utility of a question is
subjective and can depend on the knowledge of the annotator, thus requiring
multiple annotators to achieve reliability.

Building a representative evaluation data set is another challenge that needs
to be addressed at production scale. The data set should be constructed
carefully to truthfully represent the product catalog and the query log. Some
factors to consider when sampling the data are the product categories, query
specificity, product popularity, and considering both the head and the tail of
the query log distribution. Ideally, we would want to create two evaluation
data sets. The first one would be a static one which would not change over
time and is useful for validating model and system changes. The second one
would be a dynamic data set which is changing from time to time and can help
assess the influence of seasonal trends, such as holidays and special events.

##  6 Optimizing Engagement with User Feedback Loops

How to optimize the Q&A recommendation system with LLMs is an important aspect
of the system. While this topic has not been investigated extensively due the
recency of LLM-based recommender systems, it is likely to attract growing
interest. For example, Senel et al. [2024] recently investigated how
generative explore-exploit methods could be used to optimize cohort-level user
engagement with LLM-generated content, as measured by click through rates
(CTR). There are several challenges that need to be addressed for the
effective optimization of the Q&A recommendation problem.

First, correctly leveraging users engagement signals is a key factor for the
success of the optimization process. Engagement signals can include various
direct user actions such as question clicks and hovering over the Q&A widget.
Other actions are more indirect and can occur later in the session such as
product purchase or add-to-cart. While these actions can indicate helpfulness
of previous interactions with the Q&A widget, they can also be potentially
attributed to other types of interactions. Ideally, the optimization problem
should correctly balance between the different types of engagement signals
according to the shopping stage of the user and the question type. For
example, clicking on informational questions at an early stage can indicate
very strong engagement even if there is no purchase at the end of the session,
since the customer is still learning about the product space. This can be
achieved through techniques such as multi-objective ranking [Carmel et al.,
2020], feature representation, and implementing specific optimization
mechanisms for the different locations of the Q&A widget (e.g., SERP vs.
detail page).

Another aspect that is needed to be addressed is the specific optimization
methodology. One idea can be to use traditional online approaches like multi-
armed bandit [Slivkins et al., 2019] or learning-to-rank [Liu et al., 2009] to
select the best questions. A major disadvantage of those approaches is that
they cannot directly influence the question and answer generation by the LLM.
This may slow down the question improvement process and is limited in terms of
exploration of new questions. To try to mitigate this problem, another idea
for the optimization would be to guide the LLM in generating questions to
optimize user engagement. For example, for a given context we can provide
examples of questions that resulted in high click-through rate and prompt the
model to generate some new ones. Other more established techniques like RLHF
[Christiano et al., 2017; Ouyang et al., 2022] and DPO [Rafailov et al., 2024]
can be used to this end. For example, we can use engagement data to create
pairwise preferences for optimization. Finally, one can design a hybrid
approach to leverage both the traditional algorithms as well as LLMs. For
example, selecting the important question features based on traditional online
algorithms and providing them to the LLM to guide the generation can be one
approach in this direction.

Due to the large scale of the Q&A system, all optimization approaches can
suffer from data sparsity problems. One implication of this is that it may
take a significant amount of time to obtain sufficient engagement signals that
are representative for a large number of contexts. One idea can be to apply
optimization first on just the head of the traffic and extend it gradually.
Another approach that can be studied would be to use an LLM as a simulated
user to generate synthetic data for the optimization.

##  7 Conclusion

In this opinion paper we described our vision for the Q&A recommendation
problem to improve the experience of users in online shopping. The recent
success of LLMs has opened up the opportunity to address this problem and
bridge the gap between information seeking and product search systems.
Implementing and maintaining such an LLM-based system at production scale
poses different challenges that need to be addressed and require research and
engineering innovations. Those challenges include the controllability of the
Q&A generation, ranking optimization, quality control, and latency. The paper
outlined different ideas to address those problems to encourage the research
on the topic.

## References

  * Branco et al. [2012] Fernando Branco, Monic Sun, and J Miguel Villas-Boas.  Optimal search for product information.  _Management Science_ , 58(11):2037–2056, 2012.
  * Carmel et al. [2020] David Carmel, Elad Haramaty, Arnon Lazerson, and Liane Lewin-Eytan.  Multi-objective ranking optimization for product search using stochastic label aggregation.  In _Proceedings of The Web Conference 2020_ , pages 373–383, 2020.
  * Chen et al. [2023] Zhiyu Chen, Jason Choi, Besnik Fetahu, Oleg Rokhlenko, and Shervin Malmasi.  Generate-then-retrieve: Intent-aware faq retrieval in product search.  In _The 61st Annual Meeting Of The Association For Computational Linguistics_ , 2023.
  * Christiano et al. [2017] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30, 2017.
  * Hämäläinen et al. [2023] Perttu Hämäläinen, Mikke Tavast, and Anton Kunnari.  Evaluating large language models in generating synthetic hci research data: a case study.  In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , pages 1–19, 2023.
  * Hartvigsen et al. [2022] Thomas Hartvigsen, Saadia Gabriel, Hamid Palangi, Maarten Sap, Dipankar Ray, and Ece Kamar.  Toxigen: A large-scale machine-generated dataset for adversarial and implicit hate speech detection.  _arXiv preprint arXiv:2203.09509_ , 2022.
  * Liu et al. [2009] Tie-Yan Liu et al.  Learning to rank for information retrieval.  volume 3, pages 225–331. Now Publishers, Inc., 2009.
  * Matias et al. [2017] Yossi Matias, Dvir Keysar, Gal Chechik, Ziv Bar-Yossef, and Tomer Shmiel.  Generating related questions for search queries, June 13 2017.  US Patent 9,679,027.
  * Mitra et al. [2020] Rajarshee Mitra, Manish Gupta, and Sandipan Dandapat.  Transformer models for recommending related questions in web search.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 2153–2156, 2020.
  * Mitra et al. [2021] Rajarshee Mitra, Rhea Jain, Aditya Srikanth Veerubhotla, and Manish Gupta.  Zero-shot multi-lingual interrogative question generation for” people also ask” at bing.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 3414–3422, 2021.
  * Ouyang et al. [2022] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in neural information processing systems_ , 35:27730–27744, 2022.
  * Rafailov et al. [2024] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn.  Direct preference optimization: Your language model is secretly a reward model.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Rowley [2000] Jennifer Rowley.  Product search in e-shopping: a review and research propositions.  _Journal of consumer marketing_ , 17(1):20–35, 2000.
  * Senel et al. [2024] Lütfi Kerem Senel, Besnik Fetahu, Davis Yoshida, Zhiyu Chen, Giuseppe Castellucci, Nikhita Vedula, Jason Choi, and Shervin Malmasi.  Generative explore-exploit: Training-free optimization of generative recommender systems using llm optimizers.  2024\.
  * Slivkins et al. [2019] Aleksandrs Slivkins et al.  Introduction to multi-armed bandits.  _Foundations and Trends® in Machine Learning_ , 12(1-2):1–286, 2019.
  * Sondhi et al. [2018] Parikshit Sondhi, Mohit Sharma, Pranam Kolari, and ChengXiang Zhai.  A taxonomy of queries for e-commerce search.  In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_, pages 1245–1248, 2018.
  * Vedula et al. [2024] Nikhita Vedula, Oleg Rokhlenko, and Shervin Malmasi.  Question suggestion for conversational shopping assistants using product metadata.  2024\.


# Making Recommender Systems Forget: Learning and Unlearning
for Erasable Recommendation

Yuyuan Li1 Xiaolin Zheng1 Chaochao Chen1111Contact Author&Junlin Liu1
1Zhejiang University
{11821022, xlzheng, zjuccc<EMAIL_ADDRESS>
###### Abstract

Privacy laws and regulations enforce data-driven systems, e.g., recommender
systems, to erase the data that concern individuals. As machine learning
models potentially memorize the training data, data erasure should also
unlearn the data lineage in models, which raises increasing interest in the
problem of Machine Unlearning (MU). However, existing MU methods cannot be
directly applied into recommendation. The basic idea of most recommender
systems is collaborative filtering, but existing MU methods ignore the
collaborative information across users and items. In this paper, we propose a
general erasable recommendation framework, namely LASER, which consists of
Group module and SeqTrain module. Firstly, Group module partitions users into
balanced groups based on their similarity of collaborative embedding learned
via hypergraph. Then SeqTrain module trains the model sequentially on all
groups with curriculum learning. Both theoretical analysis and experiments on
two real-world datasets demonstrate that LASER can not only achieve efficient
unlearning, but also outperform the state-of-the-art unlearning framework in
terms of model utility.

##  1 Introduction

Recommender Systems (RSs) are typically built by analyzing the data collected
from users, such as users’ ratings on items. Existing regulations, e.g., the
General Data Protection Regulation EU (2014), enforce the ability of erasing
the personal data that concern individuals, which raises the concerns of
privacy in RSs. Due to the fact that machine learning models, which have been
ubiquitously applied in RSs, potentially memorize the training data Bourtoule
et al. (2021). Besides simply deleting the target data, data erasure is also
required to unlearning the data lineage in RS models. In general, it is
beneficial for both users and recommendation platforms to build an erasable RS
that supports unlearning in addition to learning. On the one hand, an erasable
RS can preserve the privacy of users. On the other hand, it can also enhance
recommendation performance by active unlearning. This is because the
performance of RSs is sensitive to the training data which can be easily
polluted by accidental mistakes or poisoned by intentional attack Schafer et
al. (2007).

Figure 1: A schematic view of learning and unlearning in recommendation.

Figure 1 illustrates the schema of learning and unlearning in recommendation.
In the learning process (black arrows), the platform trains recommendation
models with the data collected from users. In the unlearning process (blue
arrows), the platform unlearns the target data lineage according to the
unlearning requests from users. There are basically two types of unlearning
requests, (i) user-wise erasure (E1) which unlearns all of the data from the
user(s), and (ii) data-wise erasure (E2) which unlearns a portion of user
data. In order to evaluate unlearning methods, we summarize three goals of
unlearning, i.e., G1: Unlearn Completeness, G2: Computational Efficiency, and
G3: Model Utility.

Recently, researches have studied the problem of Machine Unlearning (MU) which
aims to unlearn the target data lineage in machine learning models. A
straightforward MU method is retraining the model from scratch on the new
dataset after deleting the target data, which perfectly achieves G1 and G3,
but fails G2. Due to tremendous computational overhead of recommendation
models, efficiency is one of the key concerns for unlearning. To overcome the
issue of inefficiency, two classes of MU methods, i.e., retrain unlearning and
reverse unlearning, have been proposed Bourtoule et al. (2021); Schelter et
al. (2021); Sekhari et al. (2021). Retrain unlearning basically divides the
original dataset into subsets and retrains the model on the target subset(s)
to reduce computational overhead. In contrast, reverse unlearning focuses on
the target data and executes reverse operations.

Unfortunately, the above MU methods cannot be directly applied into
recommendation. The reason is that the basic idea of most RSs is Collaborative
Filtering (CF) Shi et al. (2014), but these MU methods fail to consider the
collaborative information across users and items. On the one hand, retrain
unlearning trains each model on a subset of the original dataset, which means
that each model can only utilize collaborative information within the subset.
Consequently, retrain unlearning reduces total model utility (G3). On the
other hand, reverse unlearning only executes reverse operations on the target
data ignoring the collaborative effect with associated data. Thus, reverse
unlearning cannot unlearn with completeness (G1).

In this paper, we focus on user-wise erasure problem and propose LASER for it.
Following the idea of retrain unlearning, LASER naturally achieves G1.
Specifically, LASER consists of two modules, i.e, Group module and Sequential
Train (SeqTrain) module, which are constructed not only to achieve efficient
unlearning (G2), but also to enhance model utility (G3) by preserving
collaborative information. Firstly, Group module divides the original data
into balanced groups for efficient retraining. These groups are generated
based on user similarity, which is measured by the distance of collaborative
embedding learned via hypergraph. Then, SeqTrain module trains the model on
all groups sequentially to aggregate collaborative information. To further
improve model performance in such a sequential training manner, SeqTrain
module trains the groups in an easy-to-hard order, which imitates the learning
style in human curricula. Our theoretical analysis and empirical study
demonstrate that sequential training can improve the performance of models.
Through these two modules, LASER achieves efficient unlearning and boosts
model utility for CF-based recommendation. We summarize the main contributions
of this paper as follows:

  * •

We focus on user-wise erasure and propose an erasable recommendation framework
(LASER) for CF models.

  * •

We encode the high-order collaborations via hypergraph and propose a balanced
grouping method to enhance unlearning efficiency.

  * •

We propose collaborative cohesion to measure the volume of collaborative
information, as well as the learning difficulty. Our theoretical analysis
reveals that the easy-to-hard learning order improves model utility.

  * •

We conduct extensive experiments on two real-world datasets to demonstrate
that LASER supports efficient unlearning and outperforms the state-of-the-art
unlearning framework in model utility.

##  2 Problem Formulation

###  2.1 Unlearning

The main problem of building an erasable RS is unlearning and we formulate the
process of unlearning as follows: letting $[N]=\\{1,...,N\\}$ denotes a user
set, we assume that the recommendation platform learns a model $\mathcal{M}$
on the dataset $\mathcal{D}=\\{d_{i},i\in[N]\\}$ where $d_{i}$ denotes the
data collected from user $i$. As it is illustrated by blue arrows in Figure 1,
any user $i\in[N]$ can submit an unlearning request $E\subset d_{i}$ to
unlearn the target data. For user-wise erasure, $E=d_{i}$, and typically
$|\mathcal{D}|\gg|E|$. In practice, the unlearning requests are often
submitted sequentially. For conciseness, we assume that the platform processes
a batch of unlearning requests together. Finally, the platform unlearns the
model $\mathcal{M}$ based on request $E$, and produces an unlearned model
$\mathcal{M}_{u}$. Let $\mathcal{M}_{u}^{*}$ denote the model that is
retrained on $\mathcal{D}\backslash E$ from scratch. Although retraining from
scratch is extremely inefficient, $\mathcal{M}_{u}^{*}$ is the ground-truth
unlearned model. Thus, the three goals of unlearning is equivalent to
efficiently producing a model whose distribution is close to that of
$\mathcal{M}_{u}^{*}$.

###  2.2 Goals of Unlearning

G1: Unlearn Completeness. Completely unlearning the target data lineage is one
of the most fundamental goals of unlearning, which means fully erasing the
influence on model parameters and making it impossible to recover.

G2: Unlearn Efficiency. Due to the considerable computational overhead of
practical recommendation models, unlearn efficiency, especially time
efficiency, is an essential goal of unlearning.

G3: Model Utility. Although unlearning too much data lineage will inevitably
reduce the model utility, an adequate unlearning method should achieve
comparable performance with the ground-truth model $\mathcal{M}_{u}^{*}$.

###  2.3 Choice of Recommendation Models

Our proposed LASER can be generalized to most existing CF models. For
conciseness, in this paper, we only consider rating data and choose two well-
known CF models, i.e., Deep Matrix Factorization (DMF) Xue et al. (2017) and
Neural Matrix Factorization (NMF) He et al. (2017). Basically, the two models
decompose the user-item interaction matrix $R$ into two low-rank embedding
matrices, i.e., $\alpha$ and $\beta$, which represent user features and item
features respectively. The two models predict unknown ratings as follows:

$\displaystyle\hat{R}^{\text{DMF}}_{i,j}=\cos\big{(}\sigma(\alpha_{i}),\sigma(\beta_{j})\big{)},$
(1)
$\displaystyle\hat{R}^{\text{NMF}}_{i,j}=\sigma\big{(}F_{\text{GMF}}(i,j)\oplus
F_{\text{MLP}}(i,j)\big{)},$ (2)

where $F_{\text{GMF}}(i,j)=\sigma(\alpha_{i}\odot\beta_{j})$,
$F_{\text{MLP}}(i,j)=\sigma(\alpha_{i}\oplus\beta_{j})$, $\sigma$ denotes
layer operations, $\oplus$ and $\odot$ denote vector concatenation and
element-wise product respectively. Following the original papers, we adopt
normalized binary cross entropy and Adam to train the above models.

##  3 LASER Framework

Generally speaking, LASER follows the idea of retraining unlearning to achieve
G1 and G2, and maintains model utility (G3) by preserving collaborative
information.

Figure 2: Overview of LASER framework.

###  3.1 Overview

Figure 2 illustrates the structure of LASER framework, which consists of Group
module and SeqTrain module. We introduce the learning and unlearning pipelines
as follows:

Learning: As the black arrows show in Figure 2, firstly, Group module divides
$\mathcal{D}$ into disjoint groups based on the similarity of collaborative
embedding. Secondly, SeqTrain module sorts the groups based on the learning
difficulty, then trains the model sequentially in an easy-to-hard order and
finally saves these models. In this way, we can train the model on the whole
dataset to preserve collaborative information.

Unlearning: As the blue arrows show, once an unlearning request $E$ is
received, Group module detects in which group $E$ is located and SeqTrain
module sequentially retrains the model using the previously saved models. In
this way, we can retrain the model efficiently during unlearning.

###  3.2 Group Module

Group module aims to partition a dataset $\mathcal{D}$ into $S$ groups such
that $\bigcap_{i\in[S]}\mathcal{D}_{i}=\emptyset$ and
$\bigcup_{i\in[S]}\mathcal{D}_{i}=\mathcal{D}$. This paper focuses on user-
wise erasure which means the above dataset partition is equivalent to dividing
the user set $[N]$ into $S$ disjoint groups. Partitioning unlabeled data into
groups is a classic unsupervised learning problem named clustering. Thus, a
straightforward idea is to cluster users based on the observed data. There are
two grouping principles, i.e., collaboration and balance, for effective and
efficient unlearning in RSs.

####  3.2.1 Collaboration Principle

##### Motivation

Collaboration is of great importance to enhancing RS model utility. There are
two main challenges in collaborative grouping. Firstly, in the context of RS,
directly clustering users suffers from data sparsity. Since each user only
interacts with few items, most elements of the user rating vector, i.e., each
row of the user-item interaction matrix $R$, are empty. Secondly, the original
$R$ or its corresponding bipartite graph cannot sufficiently represent the
user-item collaboration, especially high-order relations Ji et al. (2020).

##### Method

In order to encode the sparse ratings and enrich the collaborative
information, we learn the hidden collaboration via hypergraph. Figure 3(a)
depicts a traditional bipartite graph where an edge connects two vertices (a
user and an item). However, Figure 3(b) shows the high-order relations of
$u_{1}$ which consists of multiple vertices. Hypergraph is a generalized
structure for relation modeling, in which a hyperedge connects two or more
vertices. Due to this property, hypergraph can sufficiently model the high-
order relations that cannot be directly represented by a traditional graph.

Specifically, we take the following three steps to learn collaborative
embedding: (i) using $R$ to build the corresponding hypergraph; (ii) for each
user, performing random walk to obtain its relations, which transforms the
task to sequence embedding; (iii) applying the sequence embedding technique,
e.g., Word2Vec Church (2017), to learn the collaborative embedding. Due to
page limit, we summarize the above process in Algorithm 1 and present the
details in Appendix A.

(a) User-item bipartite graph

(b) High-order relations

Figure 3: An illustration of an user-item bipartite graph and the high-order
relations of $u_{1}$ where $u$ and $i$ denote user and item respectively.
Algorithm 1 Collaborative Embedding via Hypergraph

Input: User-item interaction matrix: $R$
Parameter: Embedding dimension: $M$
Output: User embedding matrix: $B\in\mathcal{R}^{N\times M}$
Procedure:

1: Build hypergraph: $H=BuildHypergraph(R)$;

2: Sample user sequence: $F=RandWalk(H)$;

3: Generate user embedding: $B=SeqEmbedding(F)$;

####  3.2.2 Balance Principle

##### Motivation

After learning the collaborative embedding, the next step is clustering users
based on their embeddings. However, traditional clustering results in
unbalanced grouping, which means that the user number in each group, i.e.,
group size, varies drastically. We conduct $k$-means Kanungo et al. (2002)
clustering on two real-world datasets and report the result in Appendix B.1.
From it, we observe that the grouping distribution is highly unbalanced. Since
we have no prior knowledge about the distribution of unlearning requests, it
is better to assume that users submit unlearning requests with equal
probability. The balance principle is making the group size evenly distributed
so that it can maximize unlearning efficiency (see Appendix B.2 for
theoretical explanation).

##### Method

To achieve balanced grouping, we propose a general method that can be applied
to most existing clustering algorithms, including but not limited to $k$-means
clustering, label propagation algorithm Wang and Zhang (2007), and Gaussian
mixture models Reynolds (2009). We present the proposed balanced grouping
method in Algorithm 2. To be specific, we set the ceiling size $c_{i}=\lceil
N/S\rceil$ for each group and build a priority list $P$ to store the priority
of each user-group pair (line 3 in Algorithm 2). For example, in $k$-means
clustering, the pair with a smaller Euclidean distance is consider to have a
larger priority. During every grouping iteration, we allocate the user-group
pairs (i) according to their priority, and (ii) if the group has not reached
the ceiling size (line 5-8 in Algorithm 2). We demonstrate balanced $k$-means
(BKM) clustering as an example in Appendix B.3.

Algorithm 2 Balanced Grouping Method

Input: User embedding matrix: $B$, grouping number: $S$, maximal iteration:
$\tau$
Output: Group label of $N$ users:
$\Lambda=(\lambda_{1},..,\lambda_{N}),\lambda_{i}\in[S]$ Procedure:

1: $t=0$, $c_{i}=\lceil N/S\rceil$ for $i\in[S]$, randomly allocate $\Lambda$;

2: while True do

3: $P=ComputeSimilarity(B,\Lambda)$;

4: $P=Sort(P,order=descend)$;

5: for $priority(i,j)$ in $P$ do

6: if $c_{j}>0$ then

7: $\lambda_{i}=j$, $c_{j}=c_{j}-1$;

8: end if

9: end for

10: $t=t+1$;

11: if $t>\tau$ or $\Lambda$ do not change then

12: break;

13: end if

14: end while

###  3.3 SeqTrain Module

Instead of training models on each group in isolation and aggregating them,
SeqTrain module trains the model on the whole dataset to preserve
collaborative information. We achieve this by training the model sequentially
on all groups, and we further study the effect of training order.

####  3.3.1 Training Order

Based on the theory of Curriculum Learning Wang et al. (2021), training order
can make a huge difference in model performance. We regard each group as a
learning task. Then we aim to train the model from easier tasks to harder
ones, which imitates the learning order in human curricula. A task can be
considered as easy if the model has a relatively low loss on it. The loss can
only be obtained either after training or during training. However, we have to
decide the training order before training and cannot regroup the users during
training, which means we have to rely on predefined information to measure the
learning difficulty of each group.

For CF-based recommendation, collaborative information contributes to better
model performance, i.e., lower loss. It is reasonable to use collaborative
information as a difficulty measurer. In order to measure the volume of
collaborative information, we propose the concept of collaborative cohesion,
which calculates the cohesion of a group. The higher the collaborative
cohesion, the easier it is for the recommendation model to learn. The cohesion
is defined by the average similarity, i.e., collaboration, of users within the
group. Formally, the collaborative cohesion $\rho$ is computed as:

$\rho=\frac{\sum_{x,y\in g}sim(x,y)}{|g|},$ (3)

where $g$ denotes a group and $sim(x,y)$ computes the similarity between two
users. In this paper, we set $sim(x,y)=1/dist(x,y)$, where $dist(x,y)$ denotes
Euclidean distance of two users. We will empirically study the validity of
collaborative cohesion as a difficulty measurer in Section 4.5.

####  3.3.2 Theoretical Analysis

Let $\theta$ denote the model parameter vector and $L_{\theta}(g_{i})$ denote
the loss of the model when given the data of $i$-th group. Adopting the widely
used empirical risk minimization framework, we have the empirical loss

$\mathcal{L}(\theta)=\hat{\mathbb{E}}[L_{\theta}]=\frac{1}{S}\sum_{i=1}^{S}L_{\theta}(g_{i}).$
(4)

Minimizing the empirical loss can be regarded as maximizing model utility
Hacohen and Weinshall (2019), which is defined as:

$\displaystyle\mathcal{U}(\theta)=\hat{\mathbb{E}}(U_{\theta})=\frac{1}{S}\sum_{i=1}^{S}U_{\theta}(g_{i})\triangleq\frac{1}{S}\sum_{i=1}^{S}e^{-L_{\theta}(g_{i})}.$
(5)

As collaborative cohesion $\rho$ indicates the learning difficulty of each
group, introducing $\rho$ can be interpreted as providing a Bayesian prior $p$
for model utility.

######  Theorem 1.

Given a Bayesian prior $p$ for the model parameters $\theta$, we have:

$\mathcal{U}_{p}(\theta)=\mathcal{U}(\theta)+\hat{\text{Cov}}[U_{\theta},p].$
(6)

###### Proof.

The proof can be found in Appendix C. ∎

Theorem 2 reveals that as long as $\hat{\text{Cov}}[U_{\theta},p]>0$, SeqTrain
module can improve the original model utility from $\mathcal{U}(\theta)$ to
$\mathcal{U}_{p}(\theta)$. Our empirical study in Section 4.5 shows that
$\rho$ is positively related to $U_{\theta}$ which confirms that collaborative
cohesion is a proper difficult measurer.

##  4 Experiments

###  4.1 Dataset

We evaluate LASER on two publicly accessible datasets: MovieLens 1M
(ML)222https://grouplens.org/datasets/movielens/ and Amazon Digital Music
(AM)333http://jmcauley.ucsd.edu/data/amazon/. The ML and AM datasets are
widely used to evaluate CF algorithms Harper and Konstan (2015); He and
McAuley (2016). We filter out the users and items that have less than 5
interactions. We use 90% of ratings for training and the rest for testing.
Table 1 summarizes the statistics of two datasets.

Dataset | User # | Item # | Rating # | Sparsity
---|---|---|---|---
ML | 6,040 | 3,706 | 1,000,209 | 95.532%
AM | 478,235 | 266,414 | 836,006 | 99.999%
Table 1: Summary of datasets.

(a) ML

(b) AM

Figure 4: Comparison results of running time.

(a) DMF - learn (b) NMF - learn (c) DMF - rand@5 (d) NMF - rand@5

(e) DMF - top@5 (f) NMF - top@5 (g) DMF - learn (h) NMF - learn

(i) DMF - rand@5 (j) NMF - rand@5 (k) DMF - top@5 (l) NMF - top@5

Figure 5: NDCG@10 and HR@10 results for utility (G3) study and ablation study
(Group module) on ML dataset with std under 1e-3.

(a) DMF - learn (b) NMF - learn (c) DMF - rand@5 (d) NMF - rand@5

(e) DMF - top@5 (f) NMF - top@5 (g) DMF - learn (h) NMF - learn

(i) DMF - rand@5 (j) NMF - rand@5 (k) DMF - top@5 (l) NMF - top@5

Figure 6: NDCG@10 and HR@10 results for utility (G3) study and ablation study
(Group module) on AM dataset with std under 1e-3.

###  4.2 Experimental Settings

We test our proposed framework on two well-known CF models, i.e., DMF Xue et
al. (2017) and NMF He et al. (2017). Specifically, we set learning rate to
0.001, total training epochs $T$ = 50 for ML dataset and 20 for AM dataset.
The dimension of user (item) embedding matrix is 16 and network structures in
both DMF and NMF are set as two layers (64, 32). We initialize the model
parameters with a Gaussian distribution $\mathcal{N}(0,0.01^{2})$. All
unlearning methods for comparison are listed as follows:

Retrain: Retraining from scratch, i.e., $\mathcal{M}_{u}^{*}$.

C-SISA: We modify the State-Of-The-Art (SOTA) unlearning framework, i.e., SISA
Bourtoule et al. (2021), to fit recommendation setting. Since the original
SISA trains one model on each user group in isolation, it can only learn the
user embeddings within the group. Thus, one has to concatenate fragmentary
user embedding matrices to obtain the final user embedding matrix $\alpha$. We
name this method as Concatenated-SISA and C-SISA for short.

L-Rand: LASER via balanced random grouping.

L-BKM: LASER via BKM with rating data.

L-CBKM: LASER via BKM with collaborative embedding.

All models and algorithms are implemented with Python 3.8 and PyTorch 1.9. We
run all experiments on the same Ubuntu 20.04 LTS System server with 48-core
CPU (Intel Xeon Gold 5118, 2.3GHz), 256GB RAM and NVIDIA GeForce RTX 3090 GPU.
We ran all models for 10 times and report the means and standard deviations
(std).

###  4.3 Computational Efficiency (G2)

We evaluate the efficiency by computing the running time of three methods,
i.e., Retrain, C-SISA, and L-CBKM (on behalf of LASER). Note that we only
report the time of unlearning, because the main problem of an erasable RS is
unlearning and the three methods are theoretically similar in learning time.
We randomly unlearn 5% of users in the last group for each dataset. In order
to fully exploit the efficiency of C-SISA, we run each model in parallel for
C-SISA. As DMF and NMF cost comparable training time, we report the running
time of DMF in Figure 4 for conciseness. We can observe consistent results in
both datasets, i.e., (i) our proposed L-CBKM achieves almost comparable
running time with paralleled C-SISA, and (ii) C-SISA and L-CBKM cost less
unlearning time as the number of groups increases. The results show the
efficiency of LASER, especially when the group size is large which usually
comes with utility loss, as we will report later.

(a) ML-NDCG@10 (b) ML-HR@10 (c) AM-NDCG@10 (d) AM-HR@10

Figure 7: Results of ablation study (SeqTrain module), where (a), (b), (c),
and (d) share the same legend.

(a) ML

(b) AM

Figure 8: Validation of collaborative cohesion.

###  4.4 Model Utility (G3)

We use two common metrics, i.e., Normalized Discounted Cumulative Gain (NDCG)
and Hit Ratio (HR), to evaluate the performance of CF models He et al. (2015);
Xue et al. (2017). We truncate the ranked list at 10 for both metrics and
report NDCG@10 and HR@10 during both learning and unlearning processes. In
order to fully study the effect of unlearning, we define two types of user-
wise unlearning request, i.e., rand@$K$ and top@$K$, which denote unlearning
$K\%$ random users and the top $K\%$ users (w.r.t. the number of ratings),
respectively. We vary $K$ in $\\{2.5,5\\}$ for both datasets.

We compare LASER (L-Rand, L-BKM and L-CBKM) with the SOTA MU framework C-SISA,
and report the results in Figure 5 and 6, where we vary grouping number $S$ in
$\\{1,2,4,8,16\\}$ and set $K$ to $5$. From them, we observe that (i) even if
the users are randomly grouped (L-Rand), LASER outperforms C-SISA in all
testing cases, which means that, in the context of recommendation, LASER can
enhance performance by preserving collaborative information, (ii) the
difference between Retrain and other testing methods tends to be stable as $S$
increases, which indicates that LASER is robust with large grouping numbers,
and (iii) good performance in the learning process leads to good performance
in the unlearning process. Due to page limit, we report the results with
$K=2.5$ in Appendix D.1.

###  4.5 Ablation Study

####  4.5.1 Group Module

We compare the effectiveness of different grouping methods (Rand, BKM, and
CBKM) and report the results in Figure 5 and 6. For DMF, CBKM outperforms
other grouping methods in most of testing cases, while BKM achieves similar
performance with Rand, because it cannot properly group the users with the
sparse data. For NMF, the results are consist with DMF, except that all
grouping methods achieve similar performance when $S=16$. This is probably
because NMF’s strong learning ability helps it to better capture user feature
when $S$ is large, which weakens the effect of different grouping methods
Rendle et al. (2020); Xu et al. (2021). Additionally, to further compare the
effect of sparse data and collaborative embedding, we report their
collaborative cohesion $\rho$ in Appendix D.2. In summary, CBKM groups users
effectively in most cases on both datasets.

####  4.5.2 SeqTrain Module

In order to study the influence of the SeqTrain module, we verify (i) the
effectiveness of training order, and (ii) the validity of collaborative
cohesion.

##### Training Order

We compare our proposed SeqTrain (easy-to-hard) with anti-SeqTrain (hard-to-
easy) which trains all groups in a reverse order. We set $S$ to 8 and $K$ to
$5$ for both datasets. Figure 7 clearly shows that SeqTrain outperforms anti-
SeqTrain in all testing cases, which verifies the effectiveness of our
proposed SeqTrain module.

##### Collaborative Cohesion

We verify the validity of $\rho$ by studying the relation between testing loss
and $\rho$. We set $S$ to 8, sort the groups in descending order according to
$\rho$, and train DMF on each group from scratch for $T$ epochs. We report the
testing loss in Figure 8. From it, we see that the loss generally grows with
the order of groups, which means that $\rho$ is negatively related with
testing loss. That is, the larger the collaborative cohesion, the easier the
model can be trained. In other words, $\rho$ is a valid difficulty measurer
which is positively related with model utility. The result of NMF is
consistent with DMF, which is reported in Appendix D.3.

##  5 Related Work

##### Retrain Unlearning

This approach retrains the model on $D\backslash E$ in efficient ways, rather
than from scratch. Cao and Yang Cao and Yang (2015) firstly formed the task of
MU and proposed a statistical query learning based unlearning framework. The
basic idea is to transform training samples into a reduced number of
summations. Thus, the models can retrain more efficiently on these summations.
Ginart et al. Ginart et al. (2019) proposed efficient unlearning algorithms
for $k$-means clustering with bounds of unlearning time complexity. Lately,
Bourtoule et al. Bourtoule et al. (2021) proposed a general unlearning
framework, i.e., SISA, for most of existing machine learning models. SISA
divides the dataset into several disjoint subsets and trains one model on each
subset. Finally, SISA aggregates all models via majority vote. When SISA
receives an unlearning request, it only needs to retrain a subset of data.

##### Reverse Unlearning

This approach aims to withdraw the target data lineage from a learned model
through reverse operations on $E$. Baumhauer, Schöttle, and Zeppelzauer
Baumhauer et al. (2020) applied linear filtration on corresponding parameters
to unlearn the entire class for logit-based classification. Sekhari et al.
Sekhari et al. (2021) focused on convex loss and proposed an unlearning
algorithm based on reverse gradient operations with theoretical guarantee.

##  6 Conclusion

In this paper, we propose an erasable recommendation (LASER) framework which
consists of Group module and SeqTrain module. The Group module partitions
users into balanced groups according to their collaborative embedding. The
SeqTrain module sequentially trains all groups in an easy-to-hard learning
order with collaborative cohesion as the difficulty measurer. Our theoretical
analysis reveals that SeqTrain module can improve model utility. Extensive
experiments on two real-world recommendation datasets demonstrate that LASER
can not only achieve efficient unlearning, but also outperform the state-of-
the-art unlearning models in terms of model utility.

##  Appendix A Collaboration Embedding via Hypergraph

There are three steps to learn collaborative embedding via hypergraph, i.e.,
hypergraph building, random walk to sample user sequence, and user sequence
embedding. In this section, we first introduce the preliminaries of
hypergraph, then present the details of the above three steps.

###  A.1 Preliminary of Hypergraph

Agarwal et al. Agarwal et al. (2006) showed that the hypergraph with edge-
independent vertex weight can be reduced to either clique graph or star graph.
In order to sufficiently represent the high-order relations in recommendation,
we learn collaborative embedding via the hypergraph with edge-dependent vertex
weight Chitra and Raphael (2019). For conciseness, we refer to ‘hypergraph
with edge-dependent vertex weight’ as ‘hypergraph’ in the rest of this paper.

A hypergraph can be formulated as
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\,\mathcal{W}\\}$, where $\mathcal{V}$
denotes the vertex set $\\{v_{i}\\}$, $\mathcal{E}$ denotes the hyperedge set
$\\{e_{i}\\}$ ($e_{i}\in 2^{\mathcal{V}}$), and $\mathcal{W}$ denotes the
weight set $\\{w(i,j)|\text{for\enspace}\forall i,j\text{\enspace
that\enspace}e_{i}\in\mathcal{E},v_{j}\in e_{i}\\}$.

###  A.2 Hypergraph Building

In order to build a hypergraph, we need association rules to connect a
hypergraph with the original bipartite graph which is equivalent to the user-
item interaction matrix. There are three rules for building vertex, hyperedge,
and weight respectively.

##### Vertex Building Rule

We define each user as a vertex in hypergraph, which means $|\mathcal{V}|=N$.

######  Definition 1 (User’s $l$-order reachable neighbors).

In a user-item bipartite graph, $user_{i}(user_{j})$ is $user_{j}(user_{i})$’s
l-order reachable neighbor if there exists a sequence of adjacent vertices,
i.e., path, between $user_{i}$ and $user_{j}$, and the number of vertices in
this path is smaller than $l$.

##### Hyperedge Building Rule

We define the user’s $l$-order reachable neighbors, which is represented as a
hyperedge in hypergraph, to model the high-order relations. Correspondingly,
the users, i.e., neighbors, within the neighborhood are vertices that
connected by this hyperedge. Following Ji et al. (2020), we set $l=4$ in this
paper.

##### Weight Building Rule

We define $w(i,j)$ as the average rating of $user_{j}$ within $user_{i}$’s
$l$-order reachable neighbors.

###  A.3 Random Walk

Algorithm 3 Random Walk on Hypergraph

Input: Hypergraph: $\mathcal{G}$, walk repetition: $rep$, walk depth: $dep$
Output: User sequences: $F\in\mathbb{R}^{(N\cdot rep)\times dep}$
Procedure:

1: for $v_{i}$ in $\mathcal{V}$ do

2: for $j$ in $[rep]$ do

3: Start a user sequence with $v_{i}$, $v_{i,1}=v_{i}$;

4: for $k$ in $[dep]$ do

5: Select a hyperedge $e$ containing $v_{i,k}$ with probability proportional
to $|e|$;

6: Select a vertex $v$ from $e$ with probability proportional to $w(e,v)$;

7: Add $v$ into user sequence, $v_{i,k+1}=v$;

8: end for

9: Complete the user sequence and add it to $F$;

10: end for

11: end for

A random walk on a hypergraph is typically defined as follows Chitra and
Raphael (2019). We modify the traditional random walk to suit recommendation
setting and present it in Algorithm 3. Our proposed random walker migrates
back and forth between vertices and hyperedge to sample user sequences. From a
vertex, the walker choose a hyperedge based on its size, i.e., number of
vertices it connects (line 5 in Algorithm 3). From a hyperedge, the walker
choose a vertex based on its associated weight (line 6 in Algorithm 3).

Obviously, walk repetition and walk depth are two hyper-parameters in random
walk. According to our empirical study, we set walk repetition as 4 and walk
depth as 8 in this paper.

###  A.4 Sequence Embedding

After random walk, we have $N\cdot rep$ user sequences. Regarding the sequence
of users as the sentence of words, we can apply sequence embedding techniques
in natural language processing field to learn the collaborative embedding. In
this paper, we apply the widely used Word2Vec Church (2017) to learn the
embedding from sampled user sequences. The choice of sequence embedding
techniques is not a focus of this paper, please refer to the original paper
for more details.

##  Appendix B Balanced Grouping Method

###  B.1 Unbalanced Phenomenon

Figure 9: Distributions of group size (user number within the group) via
$k$-means clustering on two datasets, i.e., MovieLens 1M (ML) and Amazon
Digital Music (AM), with $k=2,4,8,16$.

We conduct $k$-means clustering on two real-world datasets with $k=2,4,8,16$
and report the result in Figure 9. We find that the grouping distributions are
highly unbalanced on both datasets.

###  B.2 Efficiency Analysis

We use $c_{i}$ to denote the training time cost of $i$-th group which is in
proportion to the group size. Our proposed LASER adopts a sequential training
manner, therefore the retraining time cost from $i$-th group is
$\sum_{j=i}^{S}c_{j}$. Since we assume that users submit unlearning requests
with equal probability, the probability of a request locating in $i$-th group
is $c_{i}/Z$ where $Z=\sum_{i}c_{i}$. Thus, the expectation of retraining time
cost can be written as:

$\mathbb{E}(C)=\sum_{i=1}^{S}\Big{(}(\sum_{j=i}^{S}c_{j})c_{i}/Z\Big{)}.$ (7)

We prove that $\mathbb{E}(C)$ reaches the minimum when $c_{i}=Z/n$, which
means balanced grouping can maximize the unlearning efficiency.

###### Proof.

Based on Multinomial Theorem, we can rewrite (7) as:

$\displaystyle\mathbb{E}(C)$
$\displaystyle=\frac{1}{2Z}\Big{(}(\sum_{i=1}^{n}c_{i})^{2}+\sum_{i=1}^{n}c_{i}^{2}\Big{)}$
$\displaystyle=\frac{1}{2Z}\Big{(}Z^{2}+\sum_{i=1}^{n}c_{i}^{2}\Big{)}.$ (8)

According to Cauchy-Schwarz Inequality Bhatia and Davis (1995), for $n$ random
variables $x_{i},y_{i}$, we have:

$\sum_{i=1}^{n}x_{i}^{2}\sum_{i=1}^{n}y_{i}^{2}\geq(\sum_{i=1}^{n}x_{i}y_{i})^{2}.$
(9)

Setting $y_{i}=1$ for all $i$, we can get a lower bound of $\sum_{i}x_{i}^{2}$
as:

$\sum_{i=1}^{n}x_{i}^{2}\geq\frac{(\sum_{i=1}^{n}x_{i})^{2}}{n}.$ (10)

Taking it into (B.2), we have:

$\mathbb{E}(C)\geq\frac{Z}{2}(1+\frac{1}{n})$ (11)

We can easily compute that setting $c_{i}=Z/n$ achieves this lower bound of
$\mathbb{E}(C)$. ∎

###  B.3 Balanced $k$-means Clustering

Our proposed balanced grouping method (Algorithm 2) can be applied to a wide
range of clustering algorithms. We take balanced $k$-means clustering as an
example and present the details in Algorithm 4.

Algorithm 4 $ComputeSimilarity$ ($k$-means version)

Input: User embedding matrix: $B$, group label: $\Lambda$
Output: Priority list $P$
Procedure:

1: $P=:$ empty list;

2: compute $N$ centroids with respect to $\Lambda$;

3: for $(i,j)$ in all user-centroid pairs do

4: append $dist(i,j)$ to $P$;

5: end for

##  Appendix C Proof of Theorem 2

######  Theorem 2.

Given a Bayesian prior $p$ for the model parameters $\theta$, we have:

$\mathcal{U}_{p}(\theta)=\mathcal{U}(\theta)+\hat{\text{Cov}}[U_{\theta},p].$
(12)

##### Recall

Let $\theta$ denotes the model parameter vector and $L_{\theta}(g_{i})$
denotes the loss of the model of $i$-th group. Adopting empirical risk
minimization framework, we have the empirical loss

$\displaystyle\mathcal{L}(\theta)=\hat{\mathbb{E}}[L_{\theta}]=\frac{1}{S}\sum_{i=1}^{S}L_{\theta}(g_{i}),\enspace\theta^{*}=\underset{\theta}{\operatorname{\arg\min}}\mathcal{L}(\theta).$
(13)

Minimizing the empirical loss can be regarded as maximizing model utility
Hacohen and Weinshall (2019), which is defined as:

$\displaystyle\mathcal{U}(\theta)$
$\displaystyle=\hat{\mathbb{E}}(U_{\theta})=\frac{1}{S}\sum_{i=1}^{S}U_{\theta}(g_{i})\triangleq\frac{1}{S}\sum_{i=1}^{S}e^{-L_{\theta}(g_{i})},$
$\displaystyle\theta^{*}$
$\displaystyle=\underset{\theta}{\operatorname{\arg\max}}\hskip
2.84526pt\mathcal{U}(\theta).$ (14)

###### Proof.

With the help of the Bayesian prior $p$, we can formulate (C) as:

$\displaystyle\mathcal{U}_{p}(\theta)$
$\displaystyle=\hat{\mathbb{E}}_{p}[U_{\theta}]=\sum_{i=1}^{S}U_{\theta}(g_{i})p_{i}=\sum_{i=1}^{S}e^{-L_{\theta}(g_{i})}p_{i},$
$\displaystyle\enspace\theta^{*}$
$\displaystyle=\underset{\theta}{\operatorname{\arg\max}}\hskip
2.84526pt\mathcal{U}_{p}(\theta),$ (15)

where $p_{i}$ denotes the prior probability of $i$-th group. As $U_{\theta}$
and $p$ are two random variables in $\mathcal{U}_{p}(\theta)$, we can rewrite
(C) as follows:

$\displaystyle\mathcal{U}_{p}(\theta)$
$\displaystyle=S\hat{\mathbb{E}}[U_{\theta}]\hat{\mathbb{E}}[p]+\sum_{i=1}^{S}(U_{\theta}(g_{i})-\hat{\mathbb{E}}[U_{\theta}])(p_{i}-\hat{\mathbb{E}}[p])$
$\displaystyle=\mathcal{U}(\theta)+\hat{\text{Cov}}[U_{\theta},p].$ (16)

∎

##  Appendix D More Empirical Results

###  D.1 Utility (G3)

We report the results of utility metrics with two unlearning request types
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>in Figure 10 and Figure 11. We observe that the results
are consistent with that of rand@5 and top@5.

(a) DMF -<EMAIL_ADDRESS>(b) NMF -<EMAIL_ADDRESS>(c) DMF -<EMAIL_ADDRESS>(d) NMF -<EMAIL_ADDRESS>
Figure 10: NDCG@10 and HR@10 results for ML dataset with std under 1e-3.

(a) DMF -<EMAIL_ADDRESS>(b) NMF -<EMAIL_ADDRESS>(c) DMF -<EMAIL_ADDRESS>(d) NMF -<EMAIL_ADDRESS>
Figure 11: NDCG@10 and HR@10 results for AM dataset with std under 1e-3.

###  D.2 Comparison of Sparse Data and Collaborative Embedding

(a) ML (b) AM

Figure 12: Comparison of sparse data and collaborative embedding.

We compare the effect of sparse data (BKM) and collaborative embedding (CBKM)
in terms of collaborative cohesionand report the result in Figure 12. We find
that our proposed collaborative embedding can achieve much higher
collaborative cohesionthan the original sparse data.

###  D.3 Verification of Collaborative Cohesion

To verify the validity of $\rho$, we report the testing loss of NMF in Figure
8. We observe the consistent results with DMF.

(a) ML

(b) AM

Figure 13: Validation of collaborative cohesion.

## References

  * Agarwal et al. (2006) Sameer Agarwal, Kristin Branson, and Serge Belongie.  Higher order learning with graphs.  In Proceedings of the 23rd international conference on Machine learning (ICML), pages 17–24, 2006.
  * Baumhauer et al. (2020) Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer.  Machine unlearning: Linear filtration for logit-based classifiers.  arXiv preprint arXiv:2002.02730, 2020.
  * Bhatia and Davis (1995) Rajendra Bhatia and Chandler Davis.  A cauchy-schwarz inequality for operators with applications.  Linear Algebra Appl, 223:119–129, 1995.
  * Bourtoule et al. (2021) Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In Proceedings in the 42nd IEEE Symposium on Security and Privacy (SP), 2021.
  * Cao and Yang (2015) Yinzhi Cao and Junfeng Yang.  Towards making systems forget with machine unlearning.  In Proceedings in the 36th IEEE Symposium on Security and Privacy (SP), pages 463–480, 2015.
  * Chitra and Raphael (2019) Uthsav Chitra and Benjamin Raphael.  Random walks on hypergraphs with edge-dependent vertex weights.  In International Conference on Machine Learning (ICML), pages 1172–1181, 2019.
  * Church (2017) Kenneth Ward Church.  Word2vec.  Natural Language Engineering, 23(1):155–162, 2017.
  * EU (2014) Council EU.  Council regulation (eu) on 2012/0011.  Website, 2014.  https://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX:52012PC0011.
  * Ginart et al. (2019) Tony Ginart, Melody Guan, Gerg Valiant, and James Zou.  Making ai forget you: Data deletion in machine learning.  In Advances in 32nd Neural Information Processing Systems (NeurIPS), 2019.
  * Hacohen and Weinshall (2019) Guy Hacohen and Daphna Weinshall.  On the power of curriculum learning in training deep networks.  In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 2535–2544, 2019.
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  Acm Transactions on Interactive Intelligent Systems (TIIS), 5(4):1–19, 2015.
  * He and McAuley (2016) Ruining He and Julian McAuley.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering.  In proceedings of the 25th International Conference on World Wide Web (WWW), pages 507–517, 2016.
  * He et al. (2015) Xiangnan He, Tao Chen, Min-Yen Kan, and Xiao Chen.  Trirank: Review-aware explainable recommendation by modeling aspects.  In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM), pages 1661–1670, 2015.
  * He et al. (2017) Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua.  Neural collaborative filtering.  In Proceedings of the 26th International Conference on World Wide Web (WWW), pages 173–182, 2017.
  * Ji et al. (2020) Shuyi Ji, Yifan Feng, Rongrong Ji, Xibin Zhao, Wanwan Tang, and Yue Gao.  Dual channel hypergraph collaborative filtering.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2020–2029, 2020.
  * Kanungo et al. (2002) Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu.  An efficient k-means clustering algorithm: Analysis and implementation.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 24(7):881–892, 2002.
  * Rendle et al. (2020) Steffen Rendle, Walid Krichene, Li Zhang, and John Anderson.  Neural collaborative filtering vs. matrix factorization revisited.  In Fourteenth ACM Conference on Recommender Systems, pages 240–248, 2020.
  * Reynolds (2009) Douglas A Reynolds.  Gaussian mixture models.  Encyclopedia of biometrics, 741:659–663, 2009.
  * Schafer et al. (2007) J Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen.  Collaborative filtering recommender systems.  In The adaptive web, pages 291–324. Springer, 2007.
  * Schelter et al. (2021) Sebastian Schelter, Stefan Grafberger, and Ted Dunning.  Hedgecut: Maintaining randomised trees for low-latency machine unlearning.  In Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data, pages 1545–1557, 2021.
  * Sekhari et al. (2021) Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh.  Remember what you want to forget: Algorithms for machine unlearning.  In Advances in 34th Neural Information Processing Systems (NeurIPS), 2021.
  * Shi et al. (2014) Yue Shi, Martha Larson, and Alan Hanjalic.  Collaborative filtering beyond the user-item matrix: A survey of the state of the art and future challenges.  ACM Computing Surveys (CSUR), 47(1):1–45, 2014.
  * Wang and Zhang (2007) Fei Wang and Changshui Zhang.  Label propagation through linear neighborhoods.  IEEE Transactions on Knowledge and Data Engineering, 20(1):55–67, 2007.
  * Wang et al. (2021) Xin Wang, Yudong Chen, and Wenwu Zhu.  A survey on curriculum learning.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021.
  * Xu et al. (2021) Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan.  Rethinking neural vs. matrix-factorization collaborative filtering: the theoretical perspectives.  In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 11514–11524, 2021.
  * Xue et al. (2017) Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen.  Deep matrix factorization models for recommender systems.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), volume 17, pages 3203–3209, 2017.