# Scalable Dynamic Embedding Size Search for Streaming Recommendation

Yunke Qu  The University of QueenslandBrisbaneAustralia<EMAIL_ADDRESS>,
Liang Qu  Southern University of Science and TechnologyShenzhenChina
<EMAIL_ADDRESS>,  Tong Chen  The University of
QueenslandBrisbaneAustralia<EMAIL_ADDRESS>,  Xiangyu Zhao  City
University of Hong KongHong Kong<EMAIL_ADDRESS>,  Quoc Viet Hung Nguyen
Griffith UniversityGold CoastAustralia<EMAIL_ADDRESS>and
Hongzhi Yin  The University of QueenslandBrisbaneAustralia<EMAIL_ADDRESS>
(2024)

###### Abstract.

Recommender systems typically represent users and items by learning their
embeddings, which are usually set to uniform dimensions and dominate the model
parameters. However, real-world recommender systems often operate in streaming
recommendation scenarios, where the number of users and items continues to
grow, leading to substantial storage resource consumption for these
embeddings. Although a few methods attempt to mitigate this by employing
embedding size search strategies to assign different embedding dimensions in
streaming recommendations, they assume that the embedding size grows with the
frequency of users/items, which eventually still exceeds the predefined memory
budget over time. To address this issue, this paper proposes to learn Scalable
Lightweight Embeddings for streaming recommendation, called SCALL, which can
adaptively adjust the embedding sizes of users/items within a given memory
budget over time. Specifically, we propose to sample embedding sizes from a
probabilistic distribution, with the guarantee to meet any predefined memory
budget. By fixing the memory budget, the proposed embedding size sampling
strategy can increase and decrease the embedding sizes in accordance to the
frequency of the corresponding users or items. Furthermore, we develop a
reinforcement learning-based search paradigm that models each state with mean
pooling to keep the length of the state vectors fixed, invariant to the
changing number of users and items. As a result, the proposed method can
provide embedding sizes to unseen users and items. Comprehensive empirical
evaluations on two public datasets affirm the advantageous effectiveness of
our proposed method.

recommender system, reinforcement learning, neural architecture search

††journalyear: 2024††copyright: acmlicensed††conference: Proceedings of the
33rd ACM International Conference on Information and Knowledge Management;
October 21–25, 2024; Boise, ID, USA††booktitle: Proceedings of the 33rd ACM
International Conference on Information and Knowledge Management (CIKM ’24),
October 21–25, 2024, Boise, ID, USA††doi: 10.1145/3627673.3679638††isbn:
979-8-4007-0436-9/24/10††ccs: Information systems Recommender systems

##  1\. Introduction

Recommender Systems are algorithms designed to predict and suggest items or
content that users might find appealing based on their preferences and
behavior (Zhang et al., 2019b; Wang et al., 2021). These systems play a
crucial role in various applications, such as online streaming platforms,
e-commerce websites, and social media, by enhancing user experience and
engagement (Li and Karahanna, 2015; Zhou et al., 2018; Kywe et al., 2012).
However, a significant challenge in the implementation of recommender systems
lies in the embedding tables, which are used to represent users and items in a
low-dimensional embedding vectors of fixed and uniform sizes (Joglekar et al.,
2020). As the number of users and items grows in modern applications, the size
of the embedding tables becomes a performance and memory bottleneck. For
instance, considering Instagram with 2.4 billion monthly active users and 40
billion photos/videos, a conventional embedding table for the users and videos
alone would require over 21,708 GB of memory. Managing and processing large
embedding tables can lead to increased computational complexity, longer
response times, and higher memory requirements, posing a challenge to the
efficient operation of recommender systems in resource-constrained
environments.

Many researchers have delved into mixed-dimension embedding size strategies
aimed at minimizing memory usage while preserving the performance of
recommender systems (Qu et al., 2023; Lyu et al., 2022; Qu et al., 2022; Liang
et al., 2023; Chen et al., 2021; Qu et al., 2024; Liu et al., 2021; Joglekar
et al., 2020). These strategies involve assigning different embedding sizes
based on the characteristics of users and items, such as their interaction
counts. However, these methods are tailored for static and non-streaming
settings and the embedding sizes remain fixed after allotment, which largely
limits their practical utility in streaming settings for two reasons. Firstly,
in streaming environments, where users and items exhibit high dynamism, the
embedding sizes need to be continually adjusted to accommodate the evolving
user and item behavior. For example, the embedding size of a newly released
movie may need to be increased as its frequency rises over time. Maintaining
consistent embedding sizes in such a situation will lead to performance
degradation because it fails to adopt to the changing frequency levels.
Secondly, these methods cannot to assign embedding sizes to newly joined users
or items. As a result, implementing these methods in streaming scenarios
necessitates retraining them from scratch at the onset of each time segment,
introducing significant computational overheads.

In this regard, several embedding size search mechanisms have emerged to
address the challenges of adaptability and efficiency in the evolving
landscape of recommendation applications, particularly in streaming scenarios.
For instance, Liu et al. (Zhao et al., 2020) proposed AutoEmb, a framework
treating the embedding size search as a multi-class classification problem and
utilizing a neural network for soft selection of embedding sizes for users and
items. The final output embedding size may vary according to the input
frequency. Similarly, ESAPN (Liu et al., 2020) and DESS (He et al., 2023)
formulate the problem of embedding size adjustment as a binary classification
problem. They employ external policies to determine whether to enlarge the
embedding size for each user and item as data streams in. However, all of
these frameworks lack precise control over their parameter usage, making it
challenging to set predefined memory budgets that is crucial for resource-
constrained applications. Although BET (Qu et al., 2024) partially addresses
this in static recommendation systems using table-level search, which computes
the embedding sizes for all users and items, it falls short in streaming
settings due to its inability to allocate embedding sizes to newly introduced
users and items.

Another problem with ESAPN and DESS is their limited flexibility in adjusting
the embedding sizes of previous users and items. Unlike AutoEmb, these methods
can only increase embedding sizes for users and items that become more
popular, but they cannot reduce them when frequency wanes. Assigning large
embedding sizes to users or items that were only popular in the past is
unnecessary and inefficient in terms of memory usage. In summary, it is
essential to develop a method for embedding size search in streaming
recommender systems that have the following advantages: (1) Dynamic Sizes: it
can automatically adjust (increase or decrease) embedding sizes to adopt to
the changing frequency in each time segment without the need to retrain, (2)
Controllable Budget: it can easily scale the embedding table to meet any
predefined parameter budget without extra hyperparameter tuning, and (3)
Streaming Friendly: it can be easily implemented in streaming settings without
retraining in each time segment.

To resolve the three challenges, we propose Scalable Lightweight Embeddings
(SCALL) for streaming recommendation systems, an automated embedding size
search policy based on the reinforcement learning algorithm Soft Actor-Critic
(SAC) (Haarnoja et al., 2018). SCALL achieves (1) and (3) by leveraging the
reservoir sampling mechanism of SAC, which enables continual policy learning
without the need for periodic retraining. SCALL samples embedding sizes from a
probabilistic distribution whose parameters are predicted by the policy
network. A controllable memory budget can be effortlessly enforced during the
embedding size sampling process, thus achieving (2). Table 1 provides a brief
comparison between our proposed method and two other state-of-the-art
embedding size search methods, showcasing the superiority of SCALL.

Table 1. Comparison between our method and the most representative state-of-
the-art embedding size search methods.

Benefits | CIESS | BET |  | ESAPN
---
DESS
AutoEmb | SCALL
Dynamic Sizes | ✘ | ✘ | ✘ | ✔ | ✔
Controllable Budget | ✘ | ✔ | ✘ | ✘ | ✔
Streaming Friendly | ✘ | ✘ | ✔ | ✔ | ✔

Since more frequent users and items usually require higher embedding
dimensions, incorporating frequency information into the learning of optimal
embedding sizes has been highlighted in several studies (Zhao et al., 2020;
Liu et al., 2020; Qu et al., 2023, 2024). However, as the number of users and
items increases over time in streaming settings, the size of the state vector
becomes variable. To address this issue, we propose the mean pooling strategy,
which involves sorting and grouping users and items based on their frequency.
Subsequently, we include only the average frequency of each group in each
state, ensuring that the length of the state vector remains fixed regardless
of the varying number of users and items. Additionally, by sampling embedding
sizes from a probabilistic distribution, our proposed method achieves
independence from the fluctuating number of users and items, thereby
fulfilling (3). The contributions of this paper are outlined below:

  * •

We pinpoint the practical bottlenecks of current embedding size search methods
for streaming recommender systems, specifically their inability to adaptively
adjust embedding sizes to conform to a predefined parameter budget.

  * •

We introduce SCALL, an innovative reinforcement learning (RL)-based approach
that dynamically allocates parameters to all the users and items with the
guarantee to meet any predefined memory budget in streaming settings,
regardless of the changing number of users and items.

  * •

We improve the table-level search paradigm to accommodate the varying number
of users and items in streaming recommendation systems and use it to improve
search efficiency.

  * •

We conduct comprehensive empirical evaluations on two public datasets and
compare SCALL to various embedding sparsification algorithms, affirming the
advantageous efficacy of SCALL.

##  2\. Relative Work

Before delving into our proposed method, we present the pertinent research
topics to offer an in-depth research context from three perspectives: deep
recommender systems, streaming recommender systems, and embedding size search
in recommendation.

###  2.1. Deep Recommender Systems

Researchers have put forth a variety of deep recommender models aimed at
capturing user-item relations. The initial wave of deep recommender systems is
rooted in Multi-Layer Perceptrons (MLPs) (Cheng et al., 2016; He et al.,
2017). Cheng et al. (Cheng et al., 2016) introduced Wide&Deep, a model that
combines a wide linear model with a deep neural network by computing the
weighted sum of their output to leverage the benefits of both memorization and
generalization. Another example is Neural Collaborative Filtering (He et al.,
2017), which integrates an MLP with matrix factorization to grasp the nuanced
user-item interactions. Beyond MLP-based methods, researchers have explored
graph-based architectures (Wang et al., 2019; He et al., 2020; Yu et al.,
2022). For instance, Neural Graph Collaborative Filtering (Wang et al., 2019)
expands neural collaborative filtering by incorporating graph convolution
networks to model user-item interactions. LightGCN (He et al., 2020)
simplifies NGCF by eliminating self-connections, feature transformations, and
linear activation operations. UltraGCN (Mao et al., 2021) further improves
LightGCN by using a constraint loss to approximate the limit of infinite-layer
graph convolutions. In addition to models that learn from user-item
interactions, other data modalities such as location (Yin et al., 2015; Wang
et al., 2020), sentiment (Wang et al., 2017a), activity level (Zhang et al.,
2024a), text (Li et al., 2023; Zhang et al., 2024b), images (Wang et al.,
2017b), and videos (Lee et al., 2018) have also been exploited for
recommendation.

###  2.2. Streaming Recommender Systems

To adapt to ever-evolving landscape of recommendation applications, online
learning algorithms that update recommendation model as new data streams in
have been studied for streaming recommender systems. For instance, Wang et al.
(Wang et al., 2018b) provided a Stream-centered Probabilistic Matrix
Factorization model. Guo et al. (Guo et al., 2019) proposed a Streaming
Session-based Recommendation Machine to tackle the challenges introduced by
user behaviors and large session data volume in streaming recommendation. Qiu
et al. (Qiu et al., 2020) introduced a novel Global Attributed Graph neural
network model, which learns better session and user representations. Wang et
al. (Wang et al., 2018a) proposed a streaming recommender model to capture
long-term stable and short-term interests. It is further enhanced by an
adaptive negative sampling framework based on Generative Adversarial Nets. To
mitigate the problem of catastrophic forgetting and preserve a sketch of
users’ long-term interests, reservoir sampling techniques have also been
proposed (Zhang et al., 2019a; Chang et al., 2017; Chen et al., 2013; Qiu et
al., 2020). They typically involve storing historical user-item interactions
in a reservoir, where interactions are sampled using various strategies to
update the recommender model. Although these methods can learn user and item
representations from continuous streaming data, they still face memory
efficiency issues which are yet to be addressed.

###  2.3. Embedding Compression in Recommendation

A variety of research endeavors have investigated methods for learning
compressed embeddings, serving as a memory-efficient alternative to
conventional embedding tables in recommender systems, as outlined in (Zheng et
al., 2022; Yin et al., 2024; Tran et al., 2024). Approaches like feature
selection search, as exemplified by (Wang et al., 2022; Luo et al., 2019; Lin
et al., 2022), focus on training models to learn importance scores for
effective filtering of unimportant feature fields. Embedding dimension search
methods, illustrated by (Liu et al., 2021; Qu et al., 2022; Kong et al., 2023;
Qu et al., 2023, 2024), enhance traditional recommender systems by introducing
mixed dimensions for features, departing from uniform sizes. Compositional
embedding methods (Liang et al., 2024, 2023) represents users and items with a
smaller number of embedding vectors (aka. meta-embeddings) to shrink the
embedding size. Elastic embedding (Chen et al., 2021; Zheng et al., 2024)
enable users and items to share embedding blocks. The knowledge distillation
method (Xia et al., 2022, 2023) compresses a model by having a smaller student
model learn from a larger teacher model. SCALL maps each user and item to
their optimal embedding size so it belong to category of embedding dimension
search methods.

Most of the previously mentioned methods offer sparsified embeddings in static
recommendation settings. In the context of streaming recommendation tasks, (He
et al., 2023; Liu et al., 2020; Zhao et al., 2020) dynamically assign
embedding sizes to users and items as data streams in. SCALL is also part of
this category, yet it stands out as the first method that combines the three
aforementioned advantages: dynamic sizes, controllable budget and streaming
friendly.

##  3\. Problem Definition

In this section, we define the task of streaming recommendation and dynamic
embedding size prediction.

We create a new data segments each time we witness $m$ new users and items as
the data streams in. As a result, the entire data stream is partitioned into
$T$ consecutive and mutually exclusive segments arranged in chronological
order: $D_{1},\cdots,D_{T-1},D_{T}$. Subsequently, each segment
$D_{t}\in{D_{1},\cdots,D_{T-1},D_{T}}$ is further bifurcated into two
exclusive parts: the training portion $D_{t}^{tr}$ and the test portion
$D_{t}^{te}$. Building upon this framework, the streaming recommendation task
is framed as follows: given $D_{1}^{tr},\cdots,D_{T-1}^{tr},D_{T}^{tr}$, the
objective is to train a model $G(\cdot)$ to predict the user preferences on
$D_{1}^{te},\cdots,D_{T-1}^{te},D_{T}^{te}$. In each time segment $t$, we also
build a reservoir, denoted as $\mathcal{R}_{t}$, containing historical
interactions that are randomly sampled from $D_{1}\cup...\cup D_{t-2}\cup
D_{t-1}^{tr}$ to mitigate catastrophic forgetting. The reservoir sampling
strategy is the same as in (Guo et al., 2019).

SCALL operates in a streaming setting. It starts by initializing a base
recommender $G_{0}(\cdot)$. The algorithm then iterates through each time
segment of the data stream. In each time segment $t\in[1,T]$ with
$(D_{t}^{tr}\cup D_{t}^{te})$, the embedding size predictor $F(\cdot)$ is
first trained on $D^{tr}_{t-1}$. After the training is completed, $F(\cdot)$
should provide the embedding size for each user and item in $D_{1}\cup...\cup
D_{t-1}\cup D_{t}^{tr}$. After obtaining the embedding sizes from the
embedding size predictor, the base recommender $G_{t-1}(\cdot)$ should adjust
its embedding sizes and update itself to $G_{t}(\cdot)$ on the training
samples $D^{tr}_{t}$. After this update, we evaluate $G_{t}(\cdot)$ on
$D^{te}_{t}$ and report the recommendation quality w.r.t. Recall@20 and
NDCG@20. The algorithm alternates between updating the embedding size
predictor and the base recommender in a coordinated manner. The goal of
embedding size search is to provide embedding sizes to maximize the
recommendation quality on $D^{te}_{t}$ for each time segment $t$. In the
remainder of this paper, we omit the subscript $t$ and denote the base
recommender as $G(\cdot)$ when there is no confusion.

##  4\. Proposed Methodology

Figure 1. An overview of SCALL.

In a nutshell, SCALL comprises two key components that work alternately: a
pre-trained base recommender $G(\cdot)$ parameterized by $\Theta$, and a
reinforcement learning-based embedding size predictor $F(\cdot)$ parameterized
by $\Phi$. Figure 1 illustrates the workflow of SCALL. In each time segment
$t\in[1,T]$, $F(\cdot)$ computes actions that determine the portion of
parameters allocated to the users and the parameters of the distributions from
which we sample embedding sizes. A fresh base recommender is initialized and
adjusts its user/item embedding sizes and tunes its parameters using the
training samples from the previous segment $D_{t-1}^{tr}$ with early stopping.
Then the base recommender is evaluated on a held-out test set $D_{t-1}^{te}$
w.r.t. Recall@20 and NDCG@20. Based on early stopping Recall@20 and NDCG@20
scores, the embedding size predictor $F(\cdot)$ is revised, and thus the
embedding size selection is updated for subsequent iterations. The following
sections elucidate the design of SCALL.

###  4.1. Base Recommender with Adjustable Embedding Sizes

We denote the set of all users as $\mathcal{U}$ and the set of all items
$\mathcal{V}$. The recommender’s embedding table maps each user or item to
embedding vectors $\mathbf{e}_{n}\in\mathbb{R}^{d_{max}}$, where
$n\in\mathcal{U}\cup\mathcal{V}$ and $d_{max}$ is the full embedding size. The
vertical concatenation of the embedding vectors for all users and items
results in the embedding table
$\mathbf{E}\in\mathbb{R}^{(|\mathcal{U}|+|\mathcal{V}|)\times d_{max}}$.
Following the common practice for embedding sparsification in (Liu et al.,
2021; Lyu et al., 2022; Qu et al., 2023, 2024), we adjust the embedding sizes
through a binary mask matrix
$\mathbf{M}\in\\{0,1\\}^{(|\mathcal{U}|+|\mathcal{V}|)\times d_{max}}$, where
each row $\mathbf{m}_{n}\in\mathbf{M}$ is a binary mask vector for user/item
$n$, where a proposed embedding size $d_{n}$ sets the first $d_{n}$ elements
to ones and the subsequent $d_{max}-d_{n}$ elements to zeros:

(1) $\mathbf{m}_{n}[s]=\begin{cases}1&\text{for }1\leq s\leq d_{n}\\\
0&\text{for
}d_{n}<s<d_{max}\end{cases},\;\;\;\;n\in\mathcal{U}\cup\mathcal{V}.$

The embedding table is adjusted during look-up via element-wise multiplication
with the binary mask matrix $\mathbf{M}$, i.e.,
$\mathbf{e}_{n}=(\mathbf{E}\odot\mathbf{M})_{n}$. $\mathbf{M}$ is iteratively
updated based on actions given by the policy network. During deployment, only
the heavily sparsified embedding table
$\mathbf{E}_{sparse}=\mathbf{E}\odot\mathbf{M}$ is stored, where sparse matrix
storage techniques (Virtanen et al., 2020; Sedaghati et al., 2015) handle
zero-valued entries efficiently. The recommender model $G(\cdot)$ computes the
pairwise user-item similarity $\hat{y}_{uv}$ using sparse embedding vectors:

(2)
$\hat{y}_{uv}=G(\mathbf{e}_{u},\mathbf{e}_{v}),\;\;\;\;u\in\mathcal{U},v\in\mathcal{V}.$

For optimization, the Bayesian Personalized Ranking loss of the base
recommender $G(\cdot)$ on training samples $D^{tr}$ (Rendle et al., 2009) is
adopted:

(3)
$\mathcal{L}_{BPR}(G(\cdot)|D^{tr})=\sum_{(u,v,v^{\prime})\in\mathcal{D}^{tr}}-\ln\sigma(\hat{y}_{uv}-\hat{y}_{uv^{\prime}})+\eta\|\Theta\|_{2}^{2},$

where $(u,v,v^{\prime})$ denotes user $u$’s preference for item $v$ to
$v^{\prime}$, $\Theta$ is the parameter of $G(\cdot)$, and
$\eta\|\Theta\|_{2}^{2}$ provides regularization. The goal is to each user and
item to their optimal embedding size under a strict memory budget with a fixed
mean embedding size: or with a fixed number of parameters, expressed in the
overall objective:

(4)
$\min_{\Theta,\Phi}\mathcal{L}_{BPR}\;\;\;\text{s.t.}\;\frac{\|\mathbf{M}\|_{1,1}}{(|\mathcal{U}|+|\mathcal{V}|)}\leq
c$

where $\|\mathbf{M}\|_{1,1}$ represents the number of ones in the binary mask,
$c$ is the desired mean embedding size over all users and items, and $B$ is
the desired number of parameters. Alternatively, we can also fix the total
number of parameters to $B$:

(5)
$\min_{\Theta,\Phi}\mathcal{L}_{BPR}\;\;\;\text{s.t.}\;\|\mathbf{M}\|_{1,1}\leq
B$

With fixed $c$, the total number of parameters can be calculated as follows:

(6) $B=c(|\mathcal{U}|+|\mathcal{V}|)$

###  4.2. Mixed Embedding Size Search with Reinforcement Learning

####  4.2.1. Environment

The base recommender is the environment. It returns the top-$k$ items for each
user given their embedding sizes.

Figure 2. The total parameters are allocated to to 3 users and 3 items in this
example. The size of each circle corresponds to the number of parameters, with
a larger circle indicating a higher parameter count.

####  4.2.2. Action

We allocate $wB$ parameters to the users and $(1-w)B$ to the items, where
$w\in(0,1)$ denotes the portion of parameters assigned to the users. The users
are sorted in descending order of their frequency in
$D^{tr}_{t}\cup\mathcal{R}_{t}$. If two users or items have equal frequency,
preference is given to the one that appears earlier in the sorted list. Let
$\boldsymbol{p}^{U}$ and $\boldsymbol{p}^{V}$ represent the percentage of
parameters assigned to each user and item. Inspired by the use of Power Law
distribution to model income distribution, we adopt two Power Law
distributions, parameterized by
$\alpha^{U},\alpha^{V}\in(\alpha_{min},\alpha_{max})$ to separately sample
values for $\boldsymbol{p}^{U}$ and $\boldsymbol{p}^{V}$. We can adjust the
fairness of parameter allocation by adjusting the values of $\alpha^{U}$ and
$\alpha^{V}$. The parameters are uniformly shared by each user/item when
$\alpha^{U}$ and $\alpha_{V}$ approach to $\alpha_{max}$; when $\alpha^{U}$
and $\alpha_{V}$ approach to $\alpha_{min}$, the parameters tend to be
assigned to the most frequent user/items. In other words, parameter assignment
to each user and item is modeled by a mixture model, where each component is a
Power Law distribution: $\text{powerlaw}(\alpha)=\alpha x^{\alpha-1}$:

$\displaystyle\boldsymbol{q}^{U}\sim\text{powerlaw}(\alpha^{U});\;\;\;\boldsymbol{q}^{V}\sim\text{powerlaw}(\alpha^{V})$

Subsequently, the distributions are normalized to ensure that the sum of
elements in each distribution is equal to 1:

$\boldsymbol{p}^{U}=\frac{\boldsymbol{q}^{U}}{\sum_{u\in|\mathcal{U}|}\boldsymbol{q}_{u}^{U}};\;\;\;\boldsymbol{p}^{V}=\frac{\boldsymbol{q}^{V}}{\sum_{v\in|\mathcal{V}|}\boldsymbol{q}_{v}^{V}}$

Notably, we separate the users and items when sampling their embedding sizes
to accommodate the distributional difference in the user and item frequencies.
Given a fixed total parameter count, the embedding sizes $\boldsymbol{n}^{U}$
for each user and $\boldsymbol{n}^{V}$ for each item can be easily calculated
as follows:

$\boldsymbol{n}^{U}=\lfloor
wB\boldsymbol{p}^{U}\rfloor;\;\;\;\boldsymbol{n}^{V}=\lfloor(1-w)B\boldsymbol{p}^{V}\rfloor$

Figure 2 illustrates this parameter allocation process. Clearly, once we
decide the values for $w$, $\alpha^{U}$ and $\alpha^{V}$, we can easily derive
the embedding size for every user and item. Therefore, we formulate each
action as:

(7) $a=(w,\alpha^{U},\alpha^{V})$

####  4.2.3. State

The input state $s$ is vital in the decision-making process of the policy
network by capturing relevant information. Prior research, such as (Zhao et
al., 2020; Liu et al., 2020), has highlighted the effectiveness of integrating
factors like frequency and contextual details like reward. Following the same
design, we integrate the previous reward $r$ in the state.

Figure 3. Mean pooling is used to achieve fixed-length vectors incorporating
frequency information. The users or items in this example are divided into 5
groups.

However, we cannot directly incorporate the frequency of every user and item
in the state since the number of users and items varies in each data segment.
To keep the length of the state fixed, after normalizing the user interaction
counts to the range of (0, 1) using minmax normalization, we sort the users in
descending order of their frequency and divide them into $L$ groups. Then we
calculate the mean frequency of each group and include it in the state. This
practice is inspired by the mean pooling operation in Convolution Neural
Networks. Figure 3 provides an illustration of this process. The same
operation is conducted on the item interaction counts. The resulting pooled
user and item frequency is denoted as $\boldsymbol{f}^{U}$ and
$\boldsymbol{f}^{V}$.

Likewise, the resulting embedding sizes $\boldsymbol{n}$ cannot be included in
the state as contextual information due to their varying length. In light of
this challenge, we only include the range of $\boldsymbol{n}^{U}$ and
$\boldsymbol{n}^{V}$, normalized by $d_{max}-d_{min}$, to measure their
dispersion:

$h^{U}=\frac{\text{max}(\boldsymbol{n}^{U})-\text{min}(\boldsymbol{n}^{U})}{d_{max}-d_{min}};\;\;\;h^{V}=\frac{\text{max}(\boldsymbol{n}^{V})-\text{min}(\boldsymbol{n}^{V})}{d_{max}-d_{min}}$

It is worth noting that variance or standard deviation cannot be used here
because they are sensitive to the scale of the data. Although $\alpha^{U}$ or
$\alpha^{V}$ can measure the statistical dispersion of $\boldsymbol{n}$, they
are not suitable for use here because they are invariant of the data scale,
which can be exemplified by the case of $\boldsymbol{n}_{1}=[128,64,64]$,
$\boldsymbol{n}_{2}=[2,1,1]$ $\boldsymbol{n}_{3}=[1,1,1]$. With the use of
$\alpha^{U/V}$, $\boldsymbol{n}_{1}$ and $\boldsymbol{n}_{2}$ will be deemed
as equivalent, while in reality $\boldsymbol{n}_{2}$ makes little difference
from $\boldsymbol{n}_{3}$ in affecting the performance of the base recommender
when they are used as embedding sizes.

Moreover, to capture the characteristics of the data segment, the mean
user/item embeddings (denoted as $\boldsymbol{m}^{U},\boldsymbol{m}^{V}$) and
the user number to item number ratio
$\frac{|\mathcal{U}|}{|\mathcal{U}|+|\mathcal{V}|}$ are also included by the
state. The mean embeddings are calculated as follows:

$\boldsymbol{m}^{U}=\frac{\sum_{u\in\mathcal{U}}(\mathbf{E}\odot\mathbf{M})_{u}}{|\mathcal{U}|};\;\;\;\boldsymbol{m}^{V}=\frac{\sum_{v\in\mathcal{V}}(\mathbf{E}\odot\mathbf{M})_{v}}{|\mathcal{V}|}$

Similar to the computation of $\boldsymbol{f}^{U}$ and $\boldsymbol{f}^{V}$,
we take the mean of the user and item embedding sizes because their vector
length is independent of the number of users and items.

In summary, our method constructs the state $s$ as follows:

(8)
$s=(\boldsymbol{f}^{U},\boldsymbol{f}^{V},r,\frac{|\mathcal{U}|}{|\mathcal{U}|+|\mathcal{V}|},h^{U},h^{V},\boldsymbol{m}^{U},\boldsymbol{m}^{V})$

####  4.2.4. Reward

In each iteration, the base recommender dynamically adjusts its embedding
sizes based on the action $a$. Subsequently, a reward $r$ is generated to
provide feedback to the current policy and guide the following embedding size
allocations. Aligned with our objective equations Eq.(4) and Eq. (6), the
reward needs to effectively capture the recommendation quality. Building on
the findings in (White et al., 2021), which highlight the effectiveness of
accuracy with early stopping as a performance predictor in neural architecture
search, we utilize Recall@20 and NDCG@20 with early stopping to formulate the
reward. Specifically, a fresh base recommender is initialized for fine-tuning
before its recommendation quality is evaluated. We initialize a new
recommender and do not inherit any pre-trained embeddings so that the previous
embedding sizes do not have any influence on the ongoing embedding size
search. The agent will have the tendency to preserve the previous embedding
sizes if we directly fine-tune a trained base recommender. Hence, we define
the following reward for an action $a$ in time segment $t$:

(9)
$r\propto\frac{\text{eval}(G^{\prime}_{t,j}|\mathcal{D}^{te}_{t})}{\text{eval}(G_{t,j}|\mathcal{D}^{te}_{t})},$

where $r$ is further normalized to fall within the range of $(0,10)$,
$G_{t,j}$ represents the snapshot of the base recommender that is updated on
$D^{tr}_{t}$ at the $j$-th step, $G^{\prime}_{t,j}$ represents the newly
initialized base recommender after being fine-tuned on $D^{tr}_{t}$ for $j$
steps, $\text{eval}(\cdot|\mathcal{D}_{t}^{te})$ is a recommendation quality
measure on the test set $\mathcal{D}_{t}^{te}$. It is constructed as an
ensemble of Recall@20 and NDCG@20, which are both common recommendation
metrics (He et al., 2020; Rendle et al., 2009):

(10)
$\text{eval}(\cdot)=\sum_{u\in\mathcal{U}}\frac{\text{Recall@}20_{u}+\text{NDCG@}20_{u}}{2|\mathcal{U}|}$

$G_{1,j}$ is obtained by training a freshly initialized recommender on
$D_{1}^{tr}$ with fixed and uniform sizes.

Importantly, Recall@20 and NDCG@20 scores are not directly comparable across
different time segments due to the inherent variability in data
characteristics. Therefore, instead of using
$\text{eval}(G^{\prime}_{t,j}|\mathcal{D}^{te}_{t})$ as the reward, we compare
it to $\text{eval}(G_{t,j}|\mathcal{D}^{te}_{t})$ to reflect the performance
gain/loss. This scaling ensures comparability across each time segment,
allowing it to reflect performance fluctuations with respect to the
performance before the embedding size adjustment.

####  4.2.5. Actor and Critic

SCALL adopts the actor-critic paradigm in reinforcement learning. We employ
Soft Actor-Critic (SAC) (Haarnoja et al., 2018) as the reinforcement learning
backbone. SAC consists of an actor network $\pi(\cdot)$ and a critic network
$Q(\cdot)$. In each iteration, the actor network $\pi(\cdot)$ maps current
state $s$ to an action $a$:

(11) $\displaystyle a=\pi(s)$

To approximate the quality (Q-value) of an action $a$ taken at state $s$, we
employ a critic network denoted as $Q(\cdot)$. The critic networks are updated
using transition tuples stored in the replay buffer $\mathcal{Z}$. The
complete pseudo-code of SCALL is presented in Algorithm 1.

Algorithm 1 SCALL

1:Initialize replay buffer $\mathcal{Z}$;

2:Initialize base recommender $G_{0}(\cdot)$;

3:for $t=1,\cdots,T$ do

4: if t ¿ 1 then

5: for $i=0,\cdots,N$ do

6: /* Update embedding size predictor */

7: Get last time segment of data $(D^{tr}_{t-1}\cup D^{te}_{t-1})$;

8: Obtain $a_{i}\leftarrow$ Eq.(11) and temporarily update $\mathbf{M}$;

9: Tune the newly initialized $G^{\prime}_{t-1}(\cdot)$ on $D^{tr}_{t-1}$;

10: Calculate reward $r_{i}\\!\\!\leftarrow\\!$ Eq.(9)

11: Get subsequent state $s’\\!\\!\leftarrow\\!$ Eq.(8);

12: Update buffer
$\mathcal{Z}\leftarrow\mathcal{Z}\cup(s_{i},a_{i},r_{i},s^{\prime}_{i})$;

13: Randomly sample a batch of transitions from $\mathcal{Z}$;

14: Update $Q(\cdot)$ and $\\!\pi(\cdot)$ as in SAC (Haarnoja et al., 2018);

15: end for

16: end if

17: /* Update base recommender */

18: Get current time segment of data $(D^{tr}_{t}\cup D^{te}_{t})$;

19: if t = 1 then

20: Update $\mathbf{M}$ with fixed and uniform sizes;

21: else:

22: Obtain action $a\leftarrow$ Eq.(11) and permanently update $\mathbf{M}$;

23: end if

24: Permanently update $G_{t-1}(\cdot)$ to $G_{t}(\cdot)$ on $D^{tr}_{t}$;

25: Evaluate $G_{t}(\cdot)$ on $D^{te}_{t}$ w.r.t. Recall@20 and NDCG@20;

26:end for

Table 2. Performance of all methods on Yelp and Amazon-Book with mean
embedding size set to 64, 32, and 16. The best results are highlighted.
Recall@20 and NDCG@20 are abbreviated to R@20 and N@20 in this and all the
subsequent tables for simplicity. All our results are statistically
significant with $p<0.02$.

| Yelp | Amazon-Book
---|---|---
Method | c = 16 | c = 32 | c = 64 | c = 16 | c = 32 | c = 64
R@20 | N@20 | R@20 | N@20 | R@20 | N@20 | R@20 | N@20 | R@20 | N@20 | R@20 | N@20
ES | 0.0468 | 0.0253 | 0.0524 | 0.0281 | 0.0571 | 0.0303 | 0.0411 | 0.0229 | 0.0478 | 0.0265 | 0.0497 | 0.0279
MR | 0.0453 | 0.0243 | 0.0488 | 0.0260 | 0.0526 | 0.0281 | 0.0376 | 0.0208 | 0.0416 | 0.0229 | 0.0452 | 0.0249
CIESS | 0.0536 | 0.0295 | 0.0564 | 0.0309 | 0.0585 | 0.0319 | 0.0419 | 0.0235 | 0.0484 | 0.0274 | 0.0520 | 0.0293
BET | 0.0542 | 0.0297 | 0.0581 | 0.0318 | 0.0596 | 0.0324 | 0.0431 | 0.0243 | 0.0501 | 0.0282 | 0.0529 | 0.0300
SCALL | 0.0560 | 0.0305 | 0.0604 | 0.0329 | 0.0623 | 0.0335 | 0.0461 | 0.0258 | 0.0516 | 0.0290 | 0.0554 | 0.0310
| c | R@20 | N@20 | c | R@20 | N@20
ESAPN | 84 | 0.0592 | 0.0323 | 78 | 0.0529 | 0.0299
DESS | 39 | 0.0586 | 0.0318 | 46 | 0.0503 | 0.0285
AutoEmb | 74 | 0.0560 | 0.0307 | 65 | 0.0489 | 0.0277

Table 3. Performance of all methods on Yelp and Amazon-Book with the parameter
budget set to 10MB and 5MB. The best results are highlighted. All our results
are statistically significant with $p<0.03$.

| Yelp | Amazon-Book
---|---|---
Method | B = 5MB | B = 10MB | B = 5MB | B = 10MB
R@20 | N@20 | R@20 | N@20 | R@20 | N@20 | R@20 | N@20
ES | 0.0474 | 0.0256 | 0.0520 | 0.0279 | 0.0417 | 0.0231 | 0.0475 | 0.0263
MR | 0.0386 | 0.0210 | 0.0496 | 0.0270 | 0.0312 | 0.0175 | 0.0356 | 0.0196
CIESS | 0.0502 | 0.0278 | 0.0538 | 0.0296 | 0.0414 | 0.0233 | 0.0483 | 0.0274
BET | 0.0524 | 0.0289 | 0.0557 | 0.0204 | 0.0439 | 0.0248 | 0.0495 | 0.0280
SCALL | 0.0545 | 0.0300 | 0.0579 | 0.0316 | 0.0462 | 0.0259 | 0.0515 | 0.0291
| B | R@20 | N@20 | B | R@20 | N@20
ESAPN | 9.29MB | 0.0539 | 0.0300 | 8.12MB | 0.0442 | 0.0248
DESS | 7.66MB | 0.0520 | 0.0287 | 6.30MB | 0.0450 | 0.0252
AutoEmb | 7.98MB | 0.0505 | 0.0278 | 9.76MB | 0.0458 | 0.0258

##  5\. Experiments

In this section, we elucidate our experimental analysis on SCALL. Through the
experiments, we seek to answer the following research questions:

  * •

RQ1: how does SCALL perform compared to ES and other embedding size search
methods in streaming settings without the need to be retrained?

  * •

RQ2: Can SCALL enforce any predefined memory budget during embedding size
search?

  * •

RQ3: Can SCALL dynamically adjust embedding sizes for users and items?

  * •

RQ4: How does the reservoir size $\gamma$ impact the performance?

  * •

RQ5: Which probabilistic distribution yields the best performance?

###  5.1. Baseline Methods

To verify the superiority of the proposed method, we compare SCALL against
several embedding size search algorithms that can be classified into three
groups: fixed embedding size (i.e., ES), static methods (i.e., MR, CIESS and
BET) and dynamic methods (i.e., ESAPN, DESS, AutoEmb and SCALL) for streaming
recommendation. In static methods, the user and item embedding sizes remain
fixed. We retrain them from scratch in every data segment so they are
comparable to dynamic methods, which adjusts the embedding sizes in each time
segment. The baseline methods are listed below:

  * •

CIESS (Qu et al., 2023): An TD3-based embedding size search algorithm that
chooses the embedding sizes from a continuous domain.

  * •

BET (Qu et al., 2024): A neural architecture search method that samples
numerous table-level candidate embedding sizes and selects the best action
using a DeepSets-based fitness predictor.

  * •

AutoEmb (Zhao et al., 2020): A differentiable framework that can automatically
adjust embedding sizes based on user/item popularity in a streaming setting.

  * •

ESAPN (Liu et al., 2020): A reinforcement learning-based embedding size search
algorithm that performs hard selection on embedding sizes based on memory
complexity and recommendation performance.

  * •

DESS (He et al., 2023): A non-stationary LinUCB-based method with a sublinear
regret upper bound and solves the problem of embedding size search by
minimizing the cumulative regret.

  * •

Equal Sizes (ES): ES assigns equal embedding sizes for all users and items.

  * •

Mixed and Random (MR): MR samples random embedding sizes from a uniform
distribution.

###  5.2. Datasets and Evaluation Protocols

The proposed and baseline method undergo evaluation on two real-world
datasets: Amazon-Book (Ni et al., 2019) and Yelp (Wang et al., 2019), both of
which contain user ratings. We apply 30-core and 10-core processing on the two
datasets, respectively. All the remaining interactions are treated as positive
and are sorted in chronological order. After processing, the former dataset
comprises 5,076,971 interactions involving 66,351 users and 57,270 items,
while the latter involves 2,762,098 interactions between 99,011 users and
56,441 items. A new data segment is created whenever there are 15,000 users or
items are introduced (i.e., $m=15,000$). We partition each data segment into
80% for training and 20% for testing, ensuring that the training data precedes
the test data chronologically. As a result, 10 data segments are created for
the Yelp dataset and 8 data segments are created for the Amazon-Book dataset.

We employ Recall@20 and NDCG@20 as evaluation metrics. The final performance
of each embedding sparsification method is evaluated using the mean Recall@20
and NDCG@20 scores over every data segment.

We also test SCALL under two scenarios - fixed mean embedding sizes and fixed
numbers of parameters. In the first scenario, we set the mean embedding size
$c$ to 16, 32, and 64. In second scenario, the number of parameters $B$ is set
to 1,250,000 and 2,500,000, corresponding to 5MB and 10MB memory. It is worth
pointing out that memory budgets larger than 10MB (e.g., 15MB) are likely to
cause the mean embedding size to exceed 256, which is the full embedding size
in our setting, and is thus unnecessary. However, as AutoEmb, ESAPN and DESS
are not explicitly designed for precise control over embedding sparsity and
prioritize performance, this section solely presents their performance linked
to the final embedding tables after pruning.

###  5.3. Implementation Details

In SCALL, we iteratively tune the base recommender to search for the optimal
embedding sizes. Once the policy network converges, we train the base
recommender till it converges. LightGCN (He et al., 2020) is employed as the
base recommender. During the training and tuning phases, we utilize a batch
size of 10,000. The base recommender is updated 200 times each time it is
tuned. During the training phase, learning rate decay is applied. The initial
learning rate is set to 0.03 and decays every 200 training steps, with 0.95
decay rate. The minimum learning rate set to 0.001. The full embedding size
$d_{max}$ is 256 and the minimal embedding size $d_{min}$ is 1. Early stopping
is integrated into the training phase, with evaluation occurring every 200
steps of updates and an early stopping patience of 3.

When training the policy network, $\alpha_{max}$ and $\alpha_{min}$ are set to
30 and 0.1 for Power Law distributions, $10\times 10^{-5}$ and $10\times
10^{-6}$ for normal distributions, 100 and 30 for Pareto distributions. The
user and item interaction counts are each divided into $L=256$ groups when we
calculate $\boldsymbol{f}^{U}$ and $\boldsymbol{f}^{V}$. Both the actor and
critic networks are MLPs with one hidden layer and the hidden size is set to
512. 8 transition tuples are sampled from the replay buffer in each iteration.

###  5.4. Overall Performance Comparison

Table 2 and Table 3 present the Recall@20 and NDCG@20 scores obtained from
various embedding sparsification methods with fixed mean embedding sizes and
fixed numbers of parameters, respectively. Additionally, we conduct paired
Student’s $t$-tests between SCALL and the best-performing baseline method in
each setting. As shown in both tables, across sparsity levels
($c\in\\{16,32,64\\}$ and $B\in\\{5\text{MB},10\text{MB}\\}$), SCALL
consistently outperforms the baselines with adjustable sparsity ratios (i.e.,
ES, MR, BET, and CIESS) in all settings. MR has the worst performance in all
settings. Notably, as shown by Table 2, at a higher sparsification level,
SCALL with $c=64$ surpasses ESAPN, DESS and AutoEmb with higher memory usage
on both datasets, which proves the superiority of SCALL. Table 3 also shows
that, although using more parameters ($B>5\text{MB}$), ESAPN, DESS and AutoEmb
do not outperform SCALL with $B=5\text{MB}$. The associated $p$-values, all
below 0.05, provide statistical significance, indicating that the advantageous
efficacy of SCALL results are not random and thus answering RQ1. Tables 2 and
3 further demonstrate that, unlike ESAPN, DESS and AutoEmb, SCALL can enforce
any memory budget, thus addressing RQ2. It’s worth noting that, through tuning
the scaling coefficient in its reward function, CIESS also achieves memory
budget enforcement (Qu et al., 2023), but this approach is often impractical
in real-world implementations.

It is important to highlight that while CIESS and BET demonstrate respectable
performance across various settings, their lack of compatibility with
streaming recommendation settings entails initialization and training from
scratch in each data segment. Consequently, the associated computational costs
render them impractical for large-scale recommendation applications.

###  5.5. Model Component Analysis

####  5.5.1. User-item Separation

As described in section 4.2.2, we separate users from items and sample their
embedding sizes from different distributions due to their distributional
difference. To verify the performance benefits stemming from this design
choice, we conduct an experiment where we aggregate users and items into a
unified set of $L$ groups, ordered by descending frequency in
$D_{t}^{tr}\cup\mathcal{R}$. We also sample the embedding sizes from one
single Power Law distribution parameterized by $\alpha$. The state and action
are simplified as follows:

$\displaystyle s$
$\displaystyle=(\boldsymbol{f},r,\frac{|\mathcal{U}|}{|\mathcal{U}|+|\mathcal{V}|},\boldsymbol{m}^{U},\boldsymbol{m}^{V})$
(12) $\displaystyle a$ $\displaystyle=\alpha,$

where $\boldsymbol{f}$ contains the sorted normalized frequency for all users
and items. The mean embedding size $c$ is 32. We refer to this simplified
version of SCALL as Dummy and compare its performance against the standard
version, which maintains user item separation. The results, presented in Table
5, demonstrate the efficacy of separately grouping users and items in
enhancing performance.

####  5.5.2. State Information

As outlined in Section 4.2.3, the state representation incorporates
information about the statistical dispersion of resulting embedding sizes,
encapsulated in their normalized range denoted as $h^{U}$ and $h^{V}$ in each
state. Additionally, to capture the latent information within each data
segment and determine the corresponding embedding sizes, we calculate the mean
user embedding vectors $\boldsymbol{m}^{U}$ across all users and the mean item
embedding vectors $\boldsymbol{m}^{V}$ across all items. To assess the impact
of $h^{U}$ and $h^{V}$ on the final recommendation quality, we exclude them
from the state representation and report the Recall@20 and NDCG@20 scores.
Similarly, we omit $\boldsymbol{m}^{U}$ and $\boldsymbol{m}^{V}$ from the
state representation before algorithm execution and report the same metrics.
We set the mean embedding size $c$ to 32. The results are displayed in Table
4. By comparing these results with the performance of the standard version of
SCALL, we conclude that removing any of these components results in a
degradation of performance.

Table 4. Performance of different variations of SCALL after one of the state
components is removed.

| Yelp | Amazon-Book
---|---|---
| Variation
---
R@20 | N@20 | R@20 | N@20
w/o $\boldsymbol{m}^{U/V}$ | 0.0594 | 0.0324 | 0.0510 | 0.0286
w/o $h^{U/V}$ | 0.0589 | 0.0323 | 0.0507 | 0.0284
Dummy | 0.0501 | 0.0268 | 0.0387 | 0.0217

Table 5. Performance metrics of SCALL variations adopting different
distributions.

| Yelp | Amazon-Book
---|---|---
Distribution | R@20 | N@20 | R@20 | N@20
Pareto | 0.0602 | 0.0325 | 0.0512 | 0.0287
Normal | 0.0602 | 0.0329 | 0.0504 | 0.0285
Power Law | 0.0604 | 0.0329 | 0.0516 | 0.0290

###  5.6. Analysis of Hyperparameters

In this section, we examine the impact of fundamental hyperparameters within
SCALL w.r.t. their influence on Recall@20 and NDCG@20.

####  5.6.1. Reservoir Size $\gamma$

Figure 4. Sensitivity analysis of $\gamma$ w.r.t. Recall@20 and NDCG@20 on the
Yelp and Amazon-Book dataset.

During time segment $t$, the base recommender undergoes training on the
combined dataset $D^{tr}_{t}\cup\mathcal{R}_{t}$, where $\mathcal{R}_{t}$
represents a reservoir containing historical user-item interactions sampled
from $D_{1}\cup...\cup D_{t-2}\cup D_{t-1}$. The reservoir’s size is
determined as $\gamma|D^{tr}_{t}|$, where $|D^{tr}_{t}|$ represents the number
of interactions in $D^{tr}_{t}$. Users and items are sorted based on their
frequency in $D^{tr}_{t}\cup\mathcal{R}_{t}$, allowing for the adjustment of
the influence that past records exert on the current embedding size search. To
answer RQ4, we explore the impact of different $\gamma$ values from
$\\{0.1,0.2,0.3,0.4,0.5\\}$ on Recall@20 and NDCG@20 scores to investigate how
the reservoir size affects recommendation performance. The mean embedding size
$c$ is set to 32. The results, depicted in Figure 4, reveal that SCALL
achieves optimal performance when $\gamma$ is set to $0.1$ for Amazon-Book.
The performance of SCALL is generally insensitive to the setting of $\gamma$
on the Yelp dataset, showcasing no significant difference with varying values
of $\gamma$.

####  5.6.2. Choice of Distributions

As outlined in Section 4.2.2, the distribution of parameters among user and
item groups is determined by sampling values from two Power Law distributions.
To answer RQ5, we replace the Power Law distributions with truncated normal
distributions and Pareto distributions, which are commonly used to model
social income and wealth distribution. Similar to the Power Law distributions,
both types of distributions are parameterized by $\alpha_{U}$ and
$\alpha_{V}$, which is bounded by $(\alpha_{min},\alpha_{max})$. For the
normal distributions, they are bounded within $(0,1)$. The normal distribution
for the users has mean of $\frac{1}{|\mathcal{U}|}$ and the one for the items
has mean of $\frac{1}{|\mathcal{V}|}$. Their scales are set to $\alpha^{U}$
and $\alpha^{V}$. The Pareto distributions are parameterized by $\alpha^{U}$
and $\alpha^{V}$. The fairness of parameter allocation can be adjusted by
adjusting the values of $\alpha^{U}$ and $\alpha^{V}$. The parameters tend be
to distributed evenly or to the most frequent users and items when
$\alpha^{U}$ and $\alpha^{V}$ approach one of the two extremes. The mean
embedding size $c$ is set to 32. The performance comparison presented in Table
5 indicates that SCALL is generally insensitive to the choice of
distributions, with Power Law and Pareto distributions achieving slightly
better performance.

###  5.7. Case Study of User Embedding Sizes

Figure 5. Case study on the interaction counts (left) and embedding sizes
(right) of four users from the Yelp dataset.

To gain insight into how the embedding size varies for specific users or items
across different time segments, we focus on four users: user 1546, user 2250,
user 3211 and user 10120. We execute the algorithm on the Yelp dataset with
the mean embedding size set to 32. Then we generate plots illustrating their
interaction counts, which represents their frequency, and corresponding
embedding sizes. Each of these users represents a distinct user profile. Users
are represented in the plots only after their initial appearance in the
dataset. User 1546 consistently maintains high frequency across all segments.
In contrast, user 3211 remains unpopular throughout all segments. User 10120
initially starts with low frequency in the first four segments but experiences
a steady increase in frequency over the subsequent six segments. Conversely,
user 2250 experiences a rise in frequency from the second to the first time
segment, followed decline in the subsequent three segments and a slight rise
over the seventh and the eighth segments.

As depicted in Figure 5, all four users initially start with large embedding
sizes despite their significant differences in frequency. This phenomenon
arises because the number of users is relatively small in the initial
segments, allowing each user to receive a relatively generous allocation of
embedding sizes. However, user 2250 and user 3211 are still given the smallest
embedding size, reflecting its lower frequency compared to the others.

Over time, the embedding size of user 1546 remains consistently large due to
its sustained frequency. In contrast, the embedding sizes of users 3211 and
10120 begin to lag behind user 1546 in the first three segments, reflecting
their lower frequency. However, while user 10120 initially follows a similar
trend as user 3211, its embedding size quickly catches up after the third
segment due to an increase in frequency. The embedding size of user 2250
increases in the second segment and decreases in the following three segments,
which is consistent with the trend of its frequency. This frequency later
experiences a slight rise in the seventh and eighth segments, leading to an
increase in its embedding size. Comparing the embedding sizes of user 10120
and user 1546 after the fourth segment, we find they share the same embedding
size although user 1546 is much more frequent. This reveals that SCALL
effectively prevents any individual user from receiving an excessive number of
parameters by capping the embedding size of highly frequent users. This
conclusion is reinforced by examining the frequency and embedding size
patterns of users 1546 and 2250 in the seventh and eighth segments.

Furthermore, despite user 3211 having equal frequency to user 2250 in the last
two segments, its embedding size is slightly larger. This discrepancy arises
because SCALL prioritizes newer users or items when they have the same
frequency. Consequently, user 3211, being a newer addition to the dataset
compared to user 2250, receives a larger embedding size allotment.

In conclusion, SCALL is able to dynamically adjust the embedding sizes of
users and items according to their changing frequency across different data
segments, which answers RQ3.

##  6\. Conclusion and Future Research

Recommender Systems face a significant challenge in the form of the memory
bottleneck resulting from uniform embedding sizes for all users and items.
Existing dynamic embedding size strategies aim to minimize memory footprint
but do not have any fixed constraint on the parameter budget. To address these
issues, we proposed SCALL, an automated policy that dynamically adjusts
embedding sizes for each user and item and ensures adherence to a predefined
budget. The experimental results on the Yelp and Amazon-Book datasets verified
the advantageous efficacy of SCALL. However, performing embedding size
assignment based on the user and item frequency is biased against the users
and items with low frequency. Moving forward, we will concentrate on fair
embedding size allocation that overcomes such frequency bias.

## Acknowledgment

This work is supported by Australian Research Council under the streams of
Future Fellowship (Grant No. FT210100624), Linkage Project (Grant No.
LP230200892), Discovery Early Career Researcher Award (Grants No.
DE230101033), Discovery Project (Grants No. DP240101108 and No. DP240101814).

## References

  * (1)
  * Chang et al. (2017) Shiyu Chang, Yang Zhang, Jiliang Tang, Dawei Yin, Yi Chang, Mark A. Hasegawa-Johnson, and Thomas S. Huang. 2017.  Streaming Recommender Systems. In _WWW_. 381–389.
  * Chen et al. (2013) Chen Chen, Hongzhi Yin, Junjie Yao, and Bin Cui. 2013.  TeRec: a temporal recommender system over tweet stream.  _VLDB_ 6, 12 (2013), 1254–1257.
  * Chen et al. (2021) Tong Chen, Hongzhi Yin, Yujia Zheng, Zi Huang, Yang Wang, and Meng Wang. 2021.  Learning Elastic Embeddings for Customizing On-Device Recommenders. In _KDD_. 138–147.
  * Cheng et al. (2016) Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. 2016\.  Wide & deep learning for recommender systems. In _Proceedings of the 1st workshop on deep learning for recommender systems_. 7–10.
  * Guo et al. (2019) Lei Guo, Hongzhi Yin, Qinyong Wang, Tong Chen, Alexander Zhou, and Nguyen Quoc Viet Hung. 2019.  Streaming Session-Based Recommendation. In _KDD_. 1569–1577.
  * Haarnoja et al. (2018) Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. 2018.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In _ICML_. 1861–1870.
  * He et al. (2023) Bowei He, Xu He, Renrui Zhang, Yingxue Zhang, Ruiming Tang, and Chen Ma. 2023.  Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender System. In _CIKM_. 741–750.
  * He et al. (2020) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020.  Lightgcn: Simplifying and powering graph convolution network for recommendation. In _SIGIR_. 639–648.
  * He et al. (2017) Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017.  Neural collaborative filtering. In _WWW_. 173–182.
  * Joglekar et al. (2020) Manas R Joglekar, Cong Li, Mei Chen, Taibai Xu, Xiaoming Wang, Jay K Adams, Pranav Khaitan, Jiahui Liu, and Quoc V Le. 2020.  Neural input search for large scale recommendation models. In _KDD_. 2387–2397.
  * Kong et al. (2023) Shuming Kong, Weiyu Cheng, Yanyan Shen, and Linpeng Huang. 2023.  AutoSrh: An Embedding Dimensionality Search Framework for Tabular Data Prediction.  _TKDE_ 35, 7 (2023), 6673–6686.
  * Kywe et al. (2012) Su Mon Kywe, Ee-Peng Lim, and Feida Zhu. 2012.  A survey of recommender systems in twitter. In _International Conference on Social Informatics_. 420–433.
  * Lee et al. (2018) Joonseok Lee, Sami Abu-El-Haija, Balakrishnan Varadarajan, and Apostol Natsev. 2018.  Collaborative deep metric learning for video understanding. In _KDD_. 481–490.
  * Li et al. (2023) Jiacheng Li, Ming Wang, Jin Li, Jinmiao Fu, Xin Shen, Jingbo Shang, and Julian McAuley. 2023.  Text Is All You Need: Learning Language Representations for Sequential Recommendation. In _KDD_. 1258–1267.
  * Li and Karahanna (2015) Siyuan Li and Elena Karahanna. 2015.  Online Recommendation Systems in a B2C E-Commerce Context: A Review and Future Directions.  _Journal of the Association for Information Systems_ 16, 2 (2015), 72–107.
  * Liang et al. (2024) Xurong Liang, Tong Chen, Lizhen Cui, Yang Wang, Meng Wang, and Hongzhi Yin. 2024.  Lightweight Embeddings for Graph Collaborative Filtering. In _SIGIR_. 1296–1306.
  * Liang et al. (2023) Xurong Liang, Tong Chen, Quoc Viet Hung Nguyen, Jianxin Li, and Hongzhi Yin. 2023.  Learning Compact Compositional Embeddings via Regularized Pruning for Recommendation. In _ICDM_. 378–387.
  * Lin et al. (2022) Weilin Lin, Xiangyu Zhao, Yejing Wang, and Xian Xu, Tong ad Wu. 2022.  AdaFS: Adaptive Feature Selection in Deep Recommender System. In _KDD_. 3309–3317.
  * Liu et al. (2020) Haochen Liu, Xiangyu Zhao, Chong Wang, Xiaobing Liu, and Jiliang Tang. 2020.  Automated embedding size search in deep recommender systems. In _SIGIR_. 2307–2316.
  * Liu et al. (2021) Siyi Liu, Chen Gao, Yihong Chen, Depeng Jin, and Yong Li. 2021.  Learnable Embedding sizes for Recommender Systems. In _ICLR_.
  * Luo et al. (2019) Yuanfei Luo, Mengshuo Wang, Hao Zhou, Quanming Yao, Wei-Wei Tu, Yuqiang Chen, Wenyuan Dai, and Qiang Yang. 2019.  Autocross: Automatic feature crossing for tabular data in real-world applications. In _KDD_. 1936–1945.
  * Lyu et al. (2022) Fuyuan Lyu, Xing Tang, Hong Zhu, Huifeng Guo, Yingxue Zhang, Ruiming Tang, and Xue Liu. 2022.  OptEmbed: Learning Optimal Embedding Table for Click-through Rate Prediction. In _CIKM_. 1399–1409.
  * Mao et al. (2021) Kelong Mao, Jieming Zhu, Xi Xiao, Biao Lu, Zhaowei Wang, and Xiuqiang He. 2021.  UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation. In _CIKM_. 1253–1262.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. 188–197.
  * Qiu et al. (2020) Ruihong Qiu, Hongzhi Yin, Zi Huang, and Tong Chen. 2020.  GAG: Global Attributed Graph Neural Network for Streaming Session-Based Recommendation. In _SIGIR_. 669–678.
  * Qu et al. (2022) Liang Qu, Yonghong Ye, Ningzhi Tang, Lixin Zhang, Yuhui Shi, and Hongzhi Yin. 2022.  Single-Shot Embedding Dimension Search in Recommender System. In _SIGIR_. 513–522.
  * Qu et al. (2024) Yunke Qu, Tong Chen, Quoc Viet Hung Nguyen, and Hongzhi Yin. 2024.  Budgeted Embedding Table For Recommender Systems. In _WSDM_. 557–566.
  * Qu et al. (2023) Yunke Qu, Tong Chen, Xiangyu Zhao, Lizhen Cui, Kai Zheng, and Hongzhi Yin. 2023.  Continuous Input Embedding Size Search For Recommender Systems. In _SIGIR_. 708–717.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian Personalized Ranking from Implicit Feedback. In _Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence_. 452–461.
  * Sedaghati et al. (2015) Naser Sedaghati, Te Mu, Louis-Noel Pouchet, Srinivasan Parthasarathy, and P Sadayappan. 2015.  Automatic selection of sparse matrix representation on GPUs. In _ACM International Conference on Supercomputing_. 99–108.
  * Tran et al. (2024) Hung Vinh Tran, Tong Chen, Quoc Viet Hung Nguyen, Zi Huang, Lizhen Cui, and Hongzhi Yin. 2024.  A Thorough Performance Benchmarking on Lightweight Embedding-based Recommender Systems.  arXiv:2406.17335
  * Virtanen et al. (2020) Pauli Virtanen et al. 2020\.  SciPy 1.0: fundamental algorithms for scientific computing in Python.  _Nature Methods_ 17, 3 (2020), 261–272.
  * Wang et al. (2017a) Hao Wang, Yanmei Fu, Qinyong Wang, Hongzhi Yin, Changying Du, and Hui Xiong. 2017a.  A Location-Sentiment-Aware Recommender System for Both Home-Town and Out-of-Town Users. In _KDD_. 1135–1143.
  * Wang et al. (2020) Qinyong Wang, Hongzhi Yin, Tong Chen, Zi Huang, Hao Wang, Yanchang Zhao, and Nguyen Quoc Viet Hung. 2020.  Next Point-of-Interest Recommendation on Resource-Constrained Mobile Devices. In _WWW_. 906–916.
  * Wang et al. (2018a) Qinyong Wang, Hongzhi Yin, Zhiting Hu, Defu Lian, Hao Wang, and Zi Huang. 2018a.  Neural Memory Streaming Recommender Networks with Adversarial Training. In _KDD_. 2467–2475.
  * Wang et al. (2021) Shoujin Wang, Longbing Cao, Yan Wang, Quan Z Sheng, Mehmet A Orgun, and Defu Lian. 2021.  A survey on session-based recommender systems.  _ACM Computing Surveys (CSUR)_ 54, 7 (2021), 1–38.
  * Wang et al. (2017b) Suhang Wang, Yilin Wang, Jiliang Tang, Kai Shu, Suhas Ranganath, and Huan Liu. 2017b.  What Your Images Reveal: Exploiting Visual Contents for Point-of-Interest Recommendation. In _WWW_. 391–400.
  * Wang et al. (2018b) Weiqing Wang, Hongzhi Yin, Zi Huang, Qinyong Wang, Xingzhong Du, and Quoc Viet Hung Nguyen. 2018b.  Streaming Ranking Based Recommender Systems. In _SIGIR_. 525–534.
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019.  Neural graph collaborative filtering. In _SIGIR_. 165–174.
  * Wang et al. (2022) Yejing Wang, Xiangyu Zhao, Tong Xu, and Xian Wu. 2022.  AutoField: Automating Feature Selection in Deep Recommender Systems. In _WWW_. 1977–1986.
  * White et al. (2021) Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. 2021.  How Powerful are Performance Predictors in Neural Architecture Search?. In _Advances in Neural Information Processing Systems_. 28454–28469.
  * Xia et al. (2022) Xin Xia, Hongzhi Yin, Junliang Yu, Qinyong Wang, Guandong Xu, and Quoc Viet Hung Nguyen. 2022.  On-Device Next-Item Recommendation with Self-Supervised Knowledge Distillation. In _SIGIR_. 546–555.
  * Xia et al. (2023) Xin Xia, Junliang Yu, Qinyong Wang, Chaoqun Yang, Nguyen Quoc Viet Hung, and Hongzhi Yin. 2023.  Efficient On-Device Session-Based Recommendation.  _ACM Trans. Inf. Syst._ 41, 4 (2023), 24 pages.
  * Yin et al. (2015) Hongzhi Yin, Bin Cui, Zi Huang, Weiqing Wang, Xian Wu, and Xiaofang Zhou. 2015.  Joint Modeling of Users’ Interests and Mobility Patterns for Point-of-Interest Recommendation. In _Proceedings of the 23rd ACM International Conference on Multimedia_. 819–822.
  * Yin et al. (2024) Hongzhi Yin, Liang Qu, Tong Chen, Wei Yuan, Ruiqi Zheng, Jing Long, Xin Xia, Yuhui Shi, and Chengqi Zhang. 2024.  On-Device Recommender Systems: A Comprehensive Survey.  arXiv:2401.11441
  * Yu et al. (2022) Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoc Viet Hung Nguyen. 2022.  Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation. In _SIGIR_. 1294–1303.
  * Zhang et al. (2024a) Changshuo Zhang, Sirui Chen, Xiao Zhang, Sunhao Dai, Weijie Yu, and Jun Xu. 2024a.  Reinforcing Long-Term Performance in Recommender Systems with User-Oriented Exploration Policy. In _SIGIR_. 1850–1860.
  * Zhang et al. (2024b) Changshuo Zhang, Teng Shi, Xiao Zhang, Yanping Zheng, Ruobing Xie, Qi Liu, Jun Xu, and Ji-Rong Wen. 2024b.  QAGCF: Graph Collaborative Filtering for Q&A Recommendation.  arXiv:2406.04828
  * Zhang et al. (2019a) Lingling Zhang, Hong Jiang, Fang Wang, Dan Feng, and Yanwen Xie. 2019a.  T-Sample: A Dual Reservoir-Based Sampling Method for Characterizing Large Graph Streams. In _ICDE_. 1674–1677.
  * Zhang et al. (2019b) Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. 2019b.  Deep learning based recommender system: A survey and new perspectives.  _ACM Computing Surveys (CSUR)_ 52, 1 (2019), 1–38.
  * Zhao et al. (2020) Xiangyu Zhao, Chong Wang, Ming Chen, Xudong Zheng, Xiaobing Liu, and Jiliang Tang. 2020.  AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations. In _ICDM_. 896–905.
  * Zheng et al. (2024) Ruiqi Zheng, Liang Qu, Tong Chen, Kai Zheng, Yuhui Shi, and Hongzhi Yin. 2024.  Personalized Elastic Embedding Learning for On-Device Recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ 36 (2024), 3363–3375.
  * Zheng et al. (2022) Ruiqi Zheng, Liang Qu, Bin Cui, Yuhui Shi, and Hongzhi Yin. 2022.  AutoML for Deep Recommender Systems: A Survey.  _ACM Transactions on Information Systems_ 101 (2022), 1–38.
  * Zhou et al. (2018) Meizi Zhou, Zhuoye Ding, Jiliang Tang, and Dawei Yin. 2018.  Micro Behaviors: A New Perspective in E-Commerce Recommender Systems. In _ICDM_. 727–735.