# Accelerating Matrix Factorization by Dynamic Pruning for Fast Recommendation

Yining Wu
School of Computer Engineering and Science,
Shanghai University,
Shanghai, 200444, China
<EMAIL_ADDRESS>
& Shengyu Duan (✉)
School of Computer Engineering and Science,
Shanghai University,
Shanghai, 200444, China
<EMAIL_ADDRESS>
&Gaole Sai
College of Integrated Circuits and Optoelectronic Chips,
Shenzhen Technology University,
Shenzhen, 518118, China
<EMAIL_ADDRESS>
&Chenhong Cao
School of Computer Engineering and Science,
Shanghai University,
Shanghai, 200444, China
<EMAIL_ADDRESS>
&Guobing Zou
School of Computer Engineering and Science,
Shanghai University,
Shanghai, 200444, China
<EMAIL_ADDRESS>

###### Abstract

Matrix factorization (MF) is a widely used collaborative filtering (CF)
algorithm for recommendation systems (RSs), due to its high prediction
accuracy, great flexibility and high efficiency in big data processing.
However, with the dramatically increased number of users/items in current RSs,
the computational complexity for training a MF model largely increases. Many
existing works have accelerated MF, by either putting in additional
computational resources or utilizing parallel systems, introducing a large
cost. In this paper, we propose algorithmic methods to accelerate MF, without
inducing any additional computational resources. In specific, we observe fine-
grained structured sparsity in the decomposed feature matrices when
considering a certain threshold. The fine-grained structured sparsity causes a
large amount of unnecessary operations during both matrix multiplication and
latent factor update, increasing the computational time of the MF training
process. Based on the observation, we firstly propose to rearrange the feature
matrices based on joint sparsity, which potentially makes a latent vector with
a smaller index more dense than that with a larger index. The feature matrix
rearrangement is given to limit the error caused by the later performed
pruning process. We then propose to prune the insignificant latent factors by
an early stopping process during both matrix multiplication and latent factor
update. The pruning process is dynamically performed according to the sparsity
of the latent factors for different users/items, to accelerate the process.
The experiments show that our method can achieve 1.2-1.65 speedups, with up to
20.08% error increase, compared with the conventional MF training process. We
also prove the proposed methods are applicable considering different
hyperparameters including optimizer, optimization strategy and initialization
method.

_Keywords_ Recommendation System $\cdot$ Matrix Factorization $\cdot$
Acceleration $\cdot$ Fine-grained Structured Sparsity $\cdot$ Pruning

##  1 Introduction

In the present era of big data, the growing challenge of information overload
emerges the need of information filtering systems to deal with massive data.
Recommendation systems (RSs) are widely applied information filtering systems,
which provide personalized suggestions of items ($e.g.,$ products, content or
services) for certain users, among an overwhelming number of choices. However,
the number of users and items involved in a RS is rapidly increased. For
instance, the commercial mobile application store, Google Play, has over one
billion active users and over one million applications, and the number of
applications has increased by approximately 1.8 million since 2013 [1].
Training such at-scale RSs is evolving to require sufficiently large hardware
resources and computational time. It is necessary to efficiently accelerate
the training process of RSs, with a minimal cost of extra resources.

Typical filtering strategies of RSs include content-based, knowledge-based and
collaborative filtering (CF) methods. Content-based methods have the problems
of over-specialization and the difficulties to generate item-attribute
information, as it is often based on certain business scenarios and manual
extraction. Knowledge-based methods need a clear definition of explicit
recommendation knowledge, introducing a great cost caused by knowledge
acquisition, and the quality of its recommendations largely depends on the
utilized knowledge base and user’s feedback [2, 3, 4, 5]. CF is considered as
the most commonly used method, due to its simplicity for implementation and
high efficiency [6, 7].

CF-based RSs can be classified into two categories: neighborhood-based (also
known as memory- or heuristic-based) methods and model-based methods [8].
Neighborhood-based methods leverage the similarity among multiple users or
multiple items to make recommendations [9]. Nevertheless, Neighborhood-based
methods are less efficient in the situation with a large number of users and
items, because such methods require a huge similarity matrix, the generation
of which takes a large amount of time [10]. Model-based CF typically uses
machine learning (ML) algorithms and users’ historical preferences or ratings
to build a model and make recommendations. There are various methods to build
the models, such as matrix factorization (MF) [11], deep neural networks [12],
Latent Semantic Analysis [13], Support Vector Machines [14] and Bayesian
Clustering [15]. Compared with other methods, matrix factorization has the
advantages of high prediction accuracy, great flexibility and high efficiency
in big data processing [11, 16].

In the MF method, all existing ratings are stored in a rating matrix, which is
normally very sparse, as each user usually interacts with only a small subset
in the overall item universe. MF decomposes the rating matrix by considering
it as the inner product of two low-rank matrices, a user-feature matrix and an
item-feature matrix, to recover the missing values of the rating matrix, in
latent dimension. Singular Value Decomposition (SVD) is one of the MF
algorithms, used in RSs [11]. However, the traditional SVD requires not only
the decomposed matrices to be orthogonal, but also the rating matrix to be
pre-filled, making the prediction accuracy largely affected by human factors
[16, 17]. Some advanced algorithms have been proposed to address the problems
of the conventional SVD, such as FunkSVD [18], BiasSVD [19], SVD++ [19].

The computational complexity for training a MF model largely increases with
more users and items [20]. To improve the training efficiency of MF-based RSs,
many existing works have proposed to parallelize the training process by
Graphic Processing Units or distributed computer systems [21, 22]. However, in
this way, a large investment in terms of hardware resources and power is
required to further accelerate the process, and thus the cost is high. In
addition, we observe the decomposed user-/item-feature matrix exhibits fine-
grained structured sparsity, as we will demonstrate in Section 3.2. This fine-
grained structured sparsity causes a large amount of unnecessary computations
to be involved in the training process of MF, which cannot be avoided if the
process is parallelized.

In this paper, we propose methods to dynamically prune the less significant
features, to largely reduce the amount of unnecessary computations, while
provide similar recommendations as the original MF method, without any
additional hardware resources. The proposed methods are applicable to be
operated on any computational platforms. The contributions of this paper are
as follows:

  1. 1)

Given a certain threshold, we observe the presence of fine-grained structured
sparsity in the decomposed matrices produced by MF, and the overall trend of
sparsity for all latent vectors generally remains during the entire training
process.

  2. 2)

We propose to rearrange the decomposed matrices based on joint sparsity as a
pre-pruning process, to minimize the error caused by pruning.

  3. 3)

We propose a pruning approach, which is dynamically performed during the
training process based on the sparsity of a certain latent dimension, to
accelerate the process considering fine-grained structured sparsity.

The rest of this paper is organized as follows. Section 2 introduces the
typical MF algorithms and the commonly used optimization strategies. In
Section 3, we investigate the overall process of MF-based RSs and demonstrate
the fine-grained structured sparsity in the decomposed feature matrices. Based
on the fine-grained structured sparsity, we propose our pruning strategy, in
Section 4. In Section 5, we provide experimental results, where it can be seen
that our approach can realize 1.16-2.3 speedups with up to 20.08% error
increase. Finally, Section 6 summarizes this paper.

##  2 Background

###  2.1 MF Algorithms

The traditional SVD decomposes a rating matrix by three matrices, where the
inner product of the three matrices is considered to approximate the rating
matrix, as follows:

$\displaystyle\boldsymbol{A}_{m\times n}$
$\displaystyle=\boldsymbol{U}_{m\times m}\textstyle\boldmath{\sum}_{m\times
n}\boldsymbol{V}_{n\times n}$ (1) $\displaystyle\approx\boldsymbol{U}_{m\times
k}\textstyle\boldmath{\sum}_{k\times k}\boldsymbol{V}_{k\times n}$

where $\boldsymbol{A}_{m\times n}$ is a matrix with $m$ rows and $n$ columns,
$\boldsymbol{U}_{m\times m}$ and $\boldsymbol{V}_{n\times n}$ are the left and
right singular matrices, respectively, which are both orthogonal matrices,
$\boldmath{\sum}_{m,n}$ is a diagonal matrix, where the diagonal elements are
the singular values, arranged in descending order. In most cases, sum of the
top a few singular values of $\boldmath{\sum}_{m\times n}$ is very close to
the sum of all singular values, so the singular values of the top $k$
$(k<<m,n)$ are often used to approximate the matrix $\boldsymbol{A}_{m\times
n}$ ($i.e.$, truncated SVD), to improve the computational efficiency and
reduce the storage space [17].

The traditional or truncated SVD requires no missing elements in the rating
matrix. However, a practical user-item rating matrix is very sparse as one
user may only interact with a very small subset of all items. A pre-filling
process is therefore needed, but it may induce great data noise. In addition,
the decomposed matrices $\boldsymbol{U}_{m\times k}$ and
$\boldsymbol{V}_{k\times n}$ are required to be orthogonal, and such a
constraint further increases the prediction error.

To further overcome the limitations of truncated SVD, FunkSVD directly
decomposes the original sparse matrix into two dense matrices using only
obtained ratings, by a training process, as shown in Equation (2):

$\boldsymbol{R}_{m\times n}\approx\boldsymbol{P}_{m\times
k}\boldsymbol{Q}_{k\times n}$ (2)

where $\boldsymbol{R}_{m\times n}$ represents the rating matrix, and the value
of $m$ and $n$ depends on the number of users and items, respectively.
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ are user-feature
matrix and item-feature matrix, respectively. FunkSVD projections the
preferences of users and the attributes of items to a $k$-dimension latent
feature space, and minimizes the error between the ratings generated by matrix
multiplication and the actual ratings by gradient descent. The objective
function is as follows:

$\min\limits_{\boldsymbol{P}_{m\times k},\boldsymbol{Q}_{k\times
n}}\sum_{(u,i)\in\boldsymbol{\Omega}}{[(r_{u,i}-\boldsymbol{p}_{u}\boldsymbol{q}_{i})^{2}+\lambda(\|\boldsymbol{p}_{u}\|^{2}+\|\boldsymbol{q}_{i}\|^{2})]}$
(3)

where $\boldsymbol{\Omega}$ denotes the index set of the actual ratings in
$\boldsymbol{R}_{m\times n}$, $r_{u,i}$ ($r_{u,i}\in\boldsymbol{R}_{m\times
n}$) is the actual rating given by the $u$-th user for the $i$-th item,
$\boldsymbol{p}_{u}$ and $\boldsymbol{q}_{i}$ are a row and a column of
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$, respectively,
representing the feature vectors of the $u$-th user and $i$-th item,
respectively, and $\lambda$ is a regularization coefficient to avoid over-
fitting.

Some improvements have been made based on FunkSVD, such as BiasSVD [19] and
SVD++ [19], to provide more accurate recommendations. BiasSVD includes user
bias, item bias and overall score of the training data, considering the
subjective bias of each user and the quality of each item. SVD++ further
includes some parameters to reveal implicit feedback and user’s attribute
information.

It is worth noting, in the rest of this work, we specifically investigate the
training process of FunkSVD and accelerate FunkSVD by using our approaches.
However, the proposed methods are also applicable for BiasSVD and SVD++, as
they have the same training process as FunkSVD.

###  2.2 Optimization Strategies in MF

In order to solve the non-convex optimization problem given in Equation (3),
gradient descent is typically used to iteratively update the feature matrices.
The process is also known as latent factor update. Stochastic Gradient Descent
(SGD) is currently one of the most widely used gradient descent methods [23].
Literally, SGD does not use all samples to calculate the gradient, but
randomly selects a rating at a time to update the corresponding parameters.
For each rating, $r_{u,i}$ ($r_{u,i}\in\boldsymbol{R}_{m\times n}$),
$\boldsymbol{p}_{u}$ and $\boldsymbol{q}_{i}$ are updated as follows:

$\displaystyle e_{u,i}$
$\displaystyle=r_{u,i}-\boldsymbol{p}_{u}\boldsymbol{q}_{i}$ (4)
$\displaystyle\boldsymbol{p}_{u}$
$\displaystyle=\boldsymbol{p}_{u}+\alpha[e_{u,i}\boldsymbol{q}_{i}-\lambda\boldsymbol{p}_{u}]$
(5) $\displaystyle\boldsymbol{q}_{i}$
$\displaystyle=\boldsymbol{q}_{i}+\alpha[e_{u,i}\boldsymbol{p}_{u}-\lambda\boldsymbol{q}_{i}]$
(6)

where $\alpha$ is the learning rate, which needs to be adjusted based on the
given applications, $e_{u,i}$ suggests the error between the predicted rating
and the actual one given by the $u$-th user for the $i$-th item. The above
step is iteratively performed until appropriate $\boldsymbol{P}_{m\times k}$
and $\boldsymbol{Q}_{k\times n}$ are obtained for prediction, making the final
recommendations.

The learning rate of a basic SGD approach is fixed, so it is crucial to set a
reasonable learning rate. A learning rate which is too large or too small
leads to divergence or slow convergence, respectively. Optimizers providing
adaptive learning rates are often necessary as an improvement to SGD. These
optimizers include Adagrad [24], AdaDelta [25], and Adam [26]. Adagrad uses a
different learning rate for each parameter and the learning rates decay
according to the accumulated gradient, introducing large learning rates at the
beginning of the training process and thus fast convergence. AdaDelta is an
extension of Adagrad that uses exponentially weighted average to retain only
the past gradients of a certain window, leading to fast convergence once it
nears the extremes. What’s more, with the addition of an exponentially
weighted average of the update parameters, it eliminates the necessity to set
a global learning rate, which significantly affects the overall prediction
results. Adam combines momentum and Adagrad, alleviating the problem caused by
gradient oscillations. The above mentioned three optimizers have been
practically utilized in many MF-based RSs with high accuracy [27, 28, 29, 30].

##  3 Preliminaries

###  3.1 Overall Process of MF-based RSs

Fig. 1 demonstrates a standard training process when using MF for RSs. An
initialization stage is firstly required, which initializes the user-/item-
feature matrix by filling randomized values. During the MF process, inner
product of the user-feature matrix and the item-feature matrix is produced, to
generate all predicted ratings. The errors are computed according to the
actual ratings and the predicted ones, according to Equation (4), which are
used to update all latent factors of the feature matrices, as given in
Equations (5) and (6). The above steps of MF-process involve a large number of
matrix multiplications, determined by the number of users and items, and are
iteratively performed over many epochs. The MF process is therefore time-
consuming. Recommendations can be made after the MF process is completed,
where the ratings of all non-interacted items are predicted by the inner
product of the feature matrices. The above process is applied in many open-
source libraries for MF and RSs, such as LibMF [31], SVDFeature [32] and
Surprise [33].

Feature matrix random intialization Feature matrix multiplication Latent
factor update The last epoch done? Prediction ($i.e.$, feature matrix
multiplication) yesnoMF process Figure 1: Overall process of MF-based RSs.

We conduct a preliminary experiment using LibMF, to investigate the proportion
of time spent on MF-process stage, by giving different number of epochs. We
perform MF-based recommendations on four datasets, MovieLens 100K [34], Amazon
Appliances [35], Book-Crossings [36] and Jester [37], of which the detailed
information is provided in Table 1.

Table 1: Experimental datasets Dataset | # users | # items | # ratings (training) | # ratings (testing) | Rating scale
---|---|---|---|---|---
MovieLens 100K | 943 | 1682 | 90570 | 9430 | 1-5
Appliances | 30252 | 515650 | 482221 | 120556 | 1-5
Book-Crossings | 105284 | 340554 | 919823 | 229956 | 0-10
Jester | 73418 | 100 | 3308968 | 827242 | -10.0-10.0

Figure 2 shows that the proportion of time spent in the MF-process stage
gradually increases as the number of epochs increases. When the number of
epochs is greater than 10, 64.31%-99.26% of the overall time is taken to
perform the MF process, while the training of a practical RS often requires
hundreds of epochs, causing an even greater proportion of the total time to
perform MF. According to Figure 1, a MF epoch is generally consist of matrix
multiplication and latent factor update, so we propose to accelerate both
steps by dynamic pruning, as will be described in Section 4, leading to a fast
training process for MF-based RSs.

110203040255075100Number of epochsPercentage of time (%)MovieLens
100KAppliancesBook-CrossingsJester Figure 2: Proportion of time for MF in the
overall process.

###  3.2 Fine-grained Structured Sparsity in MF-based RSs

Sparse matrices are commonly found in the applications of ML algorithms
including MF [38]. In CF-based RSs, sparsity often indicates the density of
the user-item rating matrix, revealing the interactions of users for different
items. The number of users and items is extremely large, and each user has
only rated a limited number of items, resulting in a very sparse rating
matrix. Data sparsity of the rating matrix is inevitable. In this paper, we
don’t discuss the sparsity of the rating matrix, instead we observe there
exist a large number of insignificant features, which are close to zero, in
the decomposed user-/item-feature matrices, indicating certain latent vectors
of the feature matrices may contain more insignificant elements, as we will
explain it as follows.

We firstly perform MF on the dataset, MovieLens 100K. We assume the rating
matrix as $\boldsymbol{R}_{m\times n}$, which is decomposed into the user-
feature matrix $\boldsymbol{P}_{m\times k}$ and the item-feature matrix
$\boldsymbol{Q}_{k\times n}$. We denote $m$, $n$ and $k$ as the number of
users, items and latent vectors, respectively. Figure 3 demonstrates parts of
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ by setting $k$
as 30, after 25 training epochs. The insignificant elements are defined by the
elements with their absolute values less than a threshold, 0.06, in such a
case. Fine-grained structured sparsity can be observed according to Figure 3:
insignificant elements are irregularly allocated in $\boldsymbol{P}_{m\times
k}$ and $\boldsymbol{Q}_{k\times n}$, and some latent vectors exhibit higher
sparsity than the rest, in both matrices. These partially sparse dimensions
cannot be deleted through feature selection, as it may cause great errors.
However, as the insignificant elements are very close to zero, they generally
do not contribute to the overall results when calculating the inner product of
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$, causing
unnecessary computations and additional computational time.

insignificantsignificant

(a)

(b)

Figure 3: Fine-grained structured sparsity of (a). $\boldsymbol{P}_{m\times
k}$, and (b). $\boldsymbol{Q}_{k\times n}$.

It might be argued that the fine-grained structured sparsity of
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ can be
eliminated by properly selecting the number of latent vectors, $k$. By
definition, $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ are
more dense by reducing the value of $k$, as the latent factors tend to be
larger. On the other hand, as the value of $k$ increases, elements of
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ become smaller,
causing greater sparsity. Nevertheless, the suitable value of $k$ is often
determined by empirical study in practice, to ensure the greatest prediction
accuracy. In Figure 4, we provide the mean absolute errors (MAEs) between the
predicted and actual ratings given by certain users for all items of MovieLens
100K, when $k$ increases. MAE also indicates the degree of fit of the model
when predicting the ratings for certain users: lower MAE suggests the
predicted ratings are more accurate, and thus the model is better fitted. As
can be noticed from Figure 4, the prediction accuracy for some users ($e.g.$,
Uid 21) is significantly increased, as $k$ increases, but for other users, the
prediction accuracy generally remains unchanged ($e.g.$, Uid 6 and 33), or
tends to decrease ($e.g.$, Uid 24). This can be expected, because the
preferences of some users might be more predictable than the rest, so a model
with a certain value of $k$ tends to be better fitted when predicting the
ratings of these users. Increasing the value of $k$ can theoretically improve
the prediction accuracy for those users, whose intentions are less
predictable, but it may introduce more insignificant latent factors in the
latent factor dimensions of other users or items, causing fine-grained
structured sparsity in $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$. As the predictability of different users or
items is certainly different, we conclude this fine-grained structured
sparsity in $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ is
unavoidable.

1030507090$0.5$$0.6$$0.7$$0.8$Number of latent vectorsMAEUid 21Uid 24Uid 33Uid
6 Figure 4: MAE between predicted and actual ratings for different number of
latent vectors $k$.

##  4 Dynamic Pruning for Accelerated MF

###  4.1 Overall Procedure

During the training process of a MF model, the sparsity of each latent vector
of matrices $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ may
vary with the number of epochs. Figure 5 shows the sparsity of all latent
vectors in both feature matrices, after 10, 20 and 30 training epochs using
MovieLens 100K, where $k$ is set to be 30, and a feature is considered to be
insignificant if its absolute value is less than 0.06. It can be seen that the
sparsity of each latent vector tends to decrease with more training epochs, as
the percentage of the insignificant elements generally decreases in both
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$. However, the
overall trends of the sparsity of all latent vectors generally hold: certain
latent vectors exhibit higher sparsity than the rest, during the entire
training process. In this paper, we exploit the above observation to
accelerate the training process of MF, as follows.

$0$$10$$20$$30$$0$$10$$20$Latent vector index Percentage of
---
insignificant elements (%)
Epoch 1Epoch 5Epoch 30 (a)

$0$$10$$20$$30$$0$$10$$20$$30$Latent vector index Percentage of
---
insignificant elements (%)
Epoch 1Epoch 5Epoch 30 (b)

Figure 5: Sparsity of all latent factors after different numbers of epoch. (a)
$\boldsymbol{P}_{m\times k}$. (b) $\boldsymbol{Q}_{k\times n}$.

The overall procedure of the proposed methods is given, in Figure 6. As can be
seen, the proposed methods can be implemented with a standard MF training
process. Considering the fine-grained structured sparsity of the feature
matrices, we firstly propose to rearrange $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ into more coarse-grained structures, based on the
sparsity of both matrices and a given threshold value for the later pruning
process. The above step only needs to be performed once after the first
training epoch, because the overall trends of the sparsity of all latent
vectors would hold during the entire training process, as demonstrated in
Figure 5. Therefore, the more coarse-grained structured sparsity, introduced
by the matrix rearrangement, can be preserved during the entire training
process. We then propose to perform coarse-grained pruning for the
insignificant features, to accelerate both matrix multiplications and latent
factor update. As the sparsity of each latent vector in
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ is different,
the pruning process is dynamically facilitated when calculating with the
latent factors of different users/items. We provide the detailed descriptions
of the proposed methods in Sections 4.2-4.4.

Feature matrix random intialization Feature matrix multiplication Latent
factor update The last epoch done? Prediction ($i.e.$, feature matrix
multiplication) yesMF process The first epoch? The second epoch? Threshold
determination Feature matrix rearrangement Latent factor pruning
noyesnoyesnoProposed methods Figure 6: Overall procedure of the proposed
methods.

###  4.2 Determination of Threshold Value for Pruning

A threshold value is required to determine significant/insignificant latent
factors in $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$. A
higher threshold suggests a higher pruning rate, where more latent factors
will be considered as insignificant and thus pruned later. By definition, the
higher the pruning rate is, the more computational time will be reduced to
provide better acceleration, but the greater errors will be induced. As the
exact values of the latent factors may greatly vary among different
applications, we propose to determine the threshold value based on a given
pruning rate.

In Figure 7, we demonstrate the distributions of all latent factors in both
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$, after training
with 1 and 30 epochs on MovieLens 100K and Jester. In each case, the latent
factors exhibit a normal-like distribution, which can be used to compute the
threshold value for a certain pruning rate.

(a)  (b)  (c)  (d)

Figure 7: Distributions of all latent factors, after training with 1 and 30
epochs. (a) MovieLens 100K, $\boldsymbol{P}_{m\times k}$. (b) MovieLens 100K,
$\boldsymbol{Q}_{k\times n}$. (c) Jester, $\boldsymbol{P}_{m\times k}$. (d)
Jester, $\boldsymbol{Q}_{k\times n}$.

Here we assume that the given pruning rate is $p$, to determine a suitable
threshold value $T$. We assume the feature matrices obey a normal distribution
with the mean value and the standard deviation as $\mu$ and $\sigma$,
respectively, which can be measured once the feature matrices are firstly
produced just after one training epoch. We define the cumulative distribution
function of a standard normal distribution as $\phi(x)$. In order to determine
$T$, which makes $p$ around latent factors locating in the range between $-T$
and $T$ and thus being pruned after the first epoch, we provide Equation (7)
as follows:

$\displaystyle T=\sigma x+\mu$ (7)

where $x$ is a parameter satisfying Equation (8), which can be determined by
searching it in a standard normal table.

$\displaystyle\phi(x)-\phi(-x-2\mu/\sigma)=p$ (8)

The detailed explanation and derivation of Equations (7) and (8) are provided,
in the Appendix.

The process to determine $T$ is thereby as follows:

  1. 1)

Find $x$ that satisfies Equation (8) in a standard normal distribution;

  2. 2)

Statistically measure $\mu$ and $\sigma$ for all latent factors of the two
feature matrices and calculate $T$, according to Equation (7).

It is worth noting the threshold value is determined by using the above method
only once, just after the first training epoch, rather than in each epoch,
because the overall distributions of all latent factors do not significantly
change after the first epoch, as shown in Figure 7. Figure 8 demonstrates the
sparsity of both $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$
after different training epochs on different datasets. As can be seen,
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ tend to be less
sparse in each case, which is consistent as the results shown in Figure 5.
Therefore, a fewer latent factors are considered to be insignificant and will
be pruned later, once a threshold is determined after the first epoch. We
consider the threshold determined by $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ after the first epoch as a pessimistic value,
leading to the most insignificant latent factors to be pruned and thus the
greatest reduction for computational time. Although this may induce additional
error, one can adjust the pruning rate to trade off between computational time
and accuracy.

$0$$10$$20$$30$$20$$30$$40$$50$Number of epochs Percentage of
---
insignificant elements (%)
MoiveLens 100KAppliancesBook-CrossingsJester (a)

$0$$10$$20$$30$$20$$30$$40$$50$Latent vector index Percentage of
---
insignificant elements (%)
MoiveLens 100KAppliancesBook-CrossingsJester (b)

Figure 8: Sparsity after different training epochs. (a)
$\boldsymbol{P}_{m\times k}$. (b) $\boldsymbol{Q}_{k\times n}$.

###  4.3 Feature Matrix Rearrangement based on Joint Sparsity

Once the threshold values to determine the insignificant latent factors are
properly selected, the sparsity of $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ can be evaluated to rearrange both matrices. As
the inner product of $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times
n}$ is computed during each training epoch, the unnecessary multiplications
are determined considering the insignificant latent factors in both
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$. An unnecessary
multiplication indicates there is at least one latent factor of the two is
insignificant. Therefore, for certain threshold values, $T_{p}$ and $T_{q}$,
for $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$,
respectively, we give the definition of joint sparsity for the $k$-th latent
vectors, denoted by $JS_{k}$, in Equation (9).

$\displaystyle JS_{k}$
$\displaystyle=prob(\lvert\boldsymbol{P}_{\\{1:m\\},k}\lvert<T_{p}\cap\lvert\boldsymbol{Q}_{k,\\{1:n\\}}\lvert<T_{q})$
(9) $\displaystyle=prob(\lvert\boldsymbol{P}_{\\{1:m\\},k}\lvert<T_{p})\times
p(\lvert\boldsymbol{Q}_{k,\\{1:n\\}}\lvert<T_{q})$ (10)

where $\boldsymbol{P}_{\\{1:m\\},k}$ and $\boldsymbol{Q}_{k,\\{1:n\\}}$
represent the $k$-th latent vectors of $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$, respectively,
$prob(\lvert\boldsymbol{P}_{\\{1:m\\},k}\lvert<T_{p})$ and
$prob(\lvert\boldsymbol{Q}_{k,\\{1:n\\}}\lvert<T_{q})$ are the probabilities
that the factors of $\boldsymbol{P}_{\\{1:m\\},k}$ and
$\boldsymbol{Q}_{k,\\{1:n\\}}$, respectively, are considered as insignificant.
Here we assume $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$
are independent, so $JS_{k}$ can be computed using Equation (10).

We provide Algorithm 1 to rearrange $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ based on $JS_{k}$, which potentially makes a
column/row with a smaller index more dense than that with a larger index. By
performing Algorithm 1, the rearranged $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ satisfy Equation (11).

$\forall k_{1},k_{2}\in[1,k]\land k_{1}<k_{2}:JS_{k_{1}}<JS_{k_{2}}$ (11)

ALGORITHM 1: Feature matrix rearrangement based on joint sparsity
---
Input: $\boldsymbol{P}_{m\times
k}=\\{\boldsymbol{P}_{\\{1:m\\},1},\boldsymbol{P}_{\\{1:m\\},2},...,\boldsymbol{P}_{\\{1:m\\},k}\\}$,
$\boldsymbol{Q}^{\top}_{k\times
n}=\\{\boldsymbol{Q}_{\\{1:n\\},1},\boldsymbol{Q}_{\\{1:n\\},2},...,\boldsymbol{Q}_{\\{1:n\\},k}\\}$,
$T_{p}$, $T_{q}$
Output: rearranged $\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times
n}$
1: for $i$ = {1,…,$k$} do
2: calculate $JS_{i}$ according to Equation (10)
3: end for
4: for $i$ = {1,…,$k$-1} do
5: for $j$ = {2,…,$k$} do
6: if $JS_{i}<JS_{j}$
7: swap $\boldsymbol{P}_{\\{1:m\\},i}$/$\boldsymbol{Q}_{\\{1:n\\},i}$ with
$\boldsymbol{P}_{\\{1:m\\},j}$/$\boldsymbol{Q}_{\\{1:n\\},j}$
in $\boldsymbol{P}_{m\times k}$/$\boldsymbol{Q}_{k\times n}$
8: end if
9: end for
10: end for

Algorithm 1 only needs to be executed once after the first epoch, because the
overall trends of the sparsity of all latent vectors generally hold during the
entire MF training process, as has been explained in Section 4.1.

We provide Figure 9 as an example to rearrange two feature matrices,
$\boldsymbol{P}_{7\times 8}$ and $\boldsymbol{Q}_{8\times 7}$, by using
Algorithm 1. As can be seen, the insignificant latent factors are originally
irregularly allocated in $\boldsymbol{P}_{7\times 8}$ and
$\boldsymbol{Q}_{8\times 7}$. The joint sparsity for each latent vector is
computed according to Equation (10), and given in Figure 9 (a). By performing
Algorithm 1, $\boldsymbol{P}_{7\times 8}$ and $\boldsymbol{Q}_{8\times 7}$ are
rearranged to ensure the joint sparsity in an ascending order, as illustrated
in Figure 9 (b). It can be noticed from Figure 9 (b) that more significant
latent factors appear in the first a few columns/rows of
$\boldsymbol{P}_{7\times 8}$/$\boldsymbol{Q}_{8\times 7}$, after the
rearrangement.

insignificantsignificant

(a)

(b)

Figure 9: An example of feature matrix rearrangement. (a) Original matrices.
(b) Rearranged matrices.

###  4.4 Dynamic Pruning for Fast Matrix Multiplication and Latent Factor
Update

Matrix multiplication of $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ is conducted during each MF training epoch. Dot
product of each row and column of $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$ is involved during a standard matrix
multiplication, which is typically performed starting from the elements with
small indices. After rearranging the feature matrices using Algorithm 1, the
columns or rows with smaller indices, of $\boldsymbol{P}_{m\times k}$ or
$\boldsymbol{Q}_{k\times n}$, respectively, tend to be less sparse, as has
been explained in Section 4.3. Therefore, for the multiplication of certain
vectors, $\boldsymbol{p}_{u}$ ($\boldsymbol{p}_{u}\in\boldsymbol{P}_{m\times
k}$) and $\boldsymbol{q}_{i}$ ($\boldsymbol{q}_{i}\in\boldsymbol{Q}_{k\times
n}$), we can expect the multiplication of the significant latent factors is
potentially performed earlier than that of the insignificant ones. We thereby
propose Algorithm 2 to mostly prune those insignificant latent factors,
leading to fast matrix multiplication. According to Algorithm 2, for each row-
by-column multiplication, latent factors of the row vector,
$\boldsymbol{p}_{u}$, are multiplied by the corresponding ones of the column
vector, $\boldsymbol{q}_{i}$, till the first insignificant latent factor
appears, in either $\boldsymbol{p}_{u}$ or $\boldsymbol{q}_{i}$, leading to
early stopping to reduce the computational time. We expect the latent factors
that are pruned minimally contribute to the row-by-column multiplication
result, because they are more likely to be insignificant in the rearranged
feature matrices. The amount of error caused by the early stopping process is
thereby limited.

ALGORITHM 2: Fast and approximate matrix multiplication by early stopping
---
Input: $\boldsymbol{p}_{u}$, $\boldsymbol{q}_{i}$, $T_{p}$, $T_{q}$, where
$\boldsymbol{p}_{u}\in\boldsymbol{P}_{m\times k}$,
$\boldsymbol{q}_{i}\in\boldsymbol{Q}_{k\times n}$,
$u\in[1,m]$, $i\in[1,n]$
Output: $\boldsymbol{p}_{u}.\boldsymbol{q}_{i}$, which is the predicted rating
of the $i$-th user
for the $j$-th item
1: $\boldsymbol{p}_{u}.\boldsymbol{q}_{i}=0$
2: for $t$ = {1,…,$k$} do
3: if ($|p_{u,t}|<T_{p}$) or ($|q_{t,i}|<T_{q}$) do /* where the $p_{u,t}$
and $q_{t,i}$ is the t-th element of $\boldsymbol{p}_{u}$ and
$\boldsymbol{q}_{i}$, respectively*/
4: break
5: else
$\boldsymbol{p}_{u}.\boldsymbol{q}_{i}=\boldsymbol{p}_{u}.\boldsymbol{q}_{i}+p_{u,t}.q_{t,i}$
6: end if
7: end for

Through Algorithm 2, the dot product of each row and column of
$\boldsymbol{P}_{m\times k}$ and $\boldsymbol{Q}_{k\times n}$ can be
approximately obtained, reducing the computational time to calculate $e_{u,i}$
of Equation (4). $e_{u,i}$ is then used to update the feature vectors of
certain users and items by gradient descent, as given in Equations (5) and
(6). We provide Algorithm 3 to mostly prune the insignificant latent factors
from the update process. According to Section 3.2, the optimal number of
latent dimensions for each user and item are different. When all feature
vectors have the same size, it might cause overfitting for the feature vectors
of some users and items. Therefore, in Algorithm 3, we propose not to update
the insignificant elements of the feature matrices, which not only reduces the
overall computational time by eliminating the update process of some latent
factors, but prevents overfitting to ensure high prediction accuracy.

ALGORITHM 3: Accelerated gradient descent by pruning
---
Input: $\boldsymbol{p}_{u}$, $\boldsymbol{q}_{i}$, $T_{p}$, $T_{q}$, where
$\boldsymbol{p}_{u}\in\boldsymbol{P}_{m\times k}$,
$\boldsymbol{q}_{i}\in\boldsymbol{Q}_{k\times n}$,
$u\in[1,m]$, $i\in[1,n]$
Output: $\boldsymbol{p}_{u}$ and $\boldsymbol{q}_{i}$ that have been updated
1: for $t$ = {1,…,$k$} do
2: if ($|p_{u,t}|<T_{p}$) or ($|q_{t,i}|<T_{q}$) do /* where the $p_{u,t}$
and $q_{t,i}$ is the t-th element of $\boldsymbol{p}_{u}$ and
$\boldsymbol{q}_{i}$, respectively*/
3: break
4: else update $p_{u,t}$ and $q_{t,i}$
5: end if
6: end for

The overall pruning process is provided, in Figure 10. By definition, the
previous feature matrix rearrangement ensures the latent factors that are
pruned in both matrix multiplication and latent factor update generally
insignificant to affect the overall results, reducing the amount of error
increase induced by pruning. The pruning process is performed for all existing
ratings in each training epoch, except the first epoch, as the feature
matrices are rearranged during the second epoch. As the sparsity of each user
and item feature vectors of $\boldsymbol{P}_{m\times k}$ and
$\boldsymbol{Q}_{k\times n}$, respectively, is different, and the sparsity
keeps changed during all training epochs, the pruning process is dynamically
performed, based on the actual sparsity of certain users or items and of
certain epochs.

Row vector $\boldsymbol{p}_{u}$, Column vector $\boldsymbol{q}_{i}$, $j$=1
$p_{u}$ or $q_{i}$ insignificant? Predicted rating += $p_{u}*q_{i}$ Vector
multiplication done? $j$ += 1 $j$=1 nonoyesyes $p_{u}$ or $q_{i}$
insignificant? Update $p_{u}$ and $q_{i}$ All factor updated? $j$ += 1 Next
row/column nonoyesyesMatrix multiplication with pruningLatent factor update
with pruning Figure 10: Overall dynamic pruning process.

##  5 Results

###  5.1 Experimental Setup

We conduct experiments on the four datasets, including MovieLens 100K, Amazon
Appliances, Book-Crossings, and Jester, of which the details are given in
Table 1. For each dataset, we randomly select 80% and 20% of all ratings as
the training and test sets, respectively.

Our experiments are conducted based on the open-source RS framework LibMF
[31], which implements FunkSVD as the MF algorithm and Adagrad as the
optimizer to update the latent factors. Before the first epoch, we initialize
all latent factors by a normal distribution. We specifically investigate the
impact of different hyperparameters from the above mentioned ones, to the
performance of our proposed methods, in Section 5.3. The experiments are
performed on a machine with Intel i5-12500H 2.5GHz processors. We openly
provide all source code of this work at https://github.com/Git-SmSun/DP-MF.

We evaluate the performance of the proposed methods by MAE, percentage MAE
($P_{MAE}$) and speedup, given in Equations (12)-(14), respectively.

$\displaystyle
MAE=\frac{1}{N}\sum_{r_{u,i}\in\boldsymbol{R}}|r_{u,i}-r^{\prime}_{u,i}|$ (12)
$\displaystyle P_{MAE}=\frac{MAE_{acc}-MAE_{org}}{MAE_{org}}\times 100\%$ (13)

where $N$ is the number of actual ratings in the test set, $\boldsymbol{R}$ is
the rating matrix, $r_{u,i}$ and $r^{\prime}_{u,i}$ are the actual and
predicted ratings, respectively, given by the $u$-th user for the $i$-th item,
$MAE_{org}$ and $MAE_{acc}$ are the MAE produced by the conventional and
accelerated training process, respectively.

$Speedup=\frac{t_{org}}{t_{acc}}$ (14)

where ${t_{org}}$ and ${t_{acc}}$ are the total runtime when not using and
using the proposed methods for acceleration, respectively. The runtime is
measured including the time of initialization, MF process and prediction, as
introduced in Section 4.1.

###  5.2 Speedup and Prediction Accuracy

We firstly set the number of latent factor dimensions, $k$, as 50, and measure
the speedups and MAE of all datasets, in Figure 11. As can be seen from Figure
11, the proposed methods realize 1.2-1.62 speedups, based on the given pruning
rate on different dataset. The runtime of the conventional training process is
measured by setting the pruning rate as 0, so that no latent factors are
eliminated. Generally, by setting a greater pruning rate, our methods tend to
provide a greater speedup, compared with the conventional training process,
because more latent factors are pruned to reduce more computational time. By
definition, the time complexity of SVD algorithms, including FunkSVD, is
$O(n^{3})$ [39]. The time complexity of the MF algorithm accelerated by our
proposed methods is also $O(n^{3})$, but the total computational time can be
theoretically reduced proportionally with the given pruning rate. However,
according to the experimental results, the speedup is not linearly increased
when the pruning rate becomes larger. This is because the proposed matrix
rearrangement is based on the joint sparsity of the feature matrices, so some
significant elements may have even larger indices than some insignificant
ones, and thus are eliminated by the pruning process. In addition, according
to Figure 7, the feature matrices generally follow a normal distribution with
its mean value close to 0, for different datasets and trained with different
number of epochs. Thereby, a similar proportion of all latent factors would be
considered as insignificant and are pruned, considering the relatively close
threshold values determined by different pruning rates, so increasing the
pruning rate may not significantly improve the speedup. Here we suggest to use
the pruning rate as a parameter for our methods to trade off between speedup
and prediction accuracy, rather than adjusting it to realize a certain
speedup.

0.02.55.07.5$P_{MAE}$ (%)$P_{MAE}$00.050.10.150.20.250.31.01.21.4Pruning
rateSpeedupSpeedup (a)

051015$P_{MAE}$ (%)$P_{MAE}$00.050.10.150.20.250.31.01.21.4Pruning
rateSpeedupSpeedup (b)

0-2-4-6$P_{MAE}$ (%)$P_{MAE}$00.050.10.150.20.250.31.01.21.4Pruning
rateSpeedupSpeedup (c)

01020$P_{MAE}$ (%)$P_{MAE}$00.050.10.150.20.250.31.01.21.41.6Pruning
rateSpeedupSpeedup (d)

Figure 11: Speedups and MAE when giving different pruning rate. (a) MovieLens
100K. (b) Appliances. (c) Book-Crossings. (d) Jester.

According to Figure 11, greater errors are caused by the proposed methods,
which can be expected because some latent factors are pruned, leading to
approximate computation in the training process. Our approaches increase the
MAE by up to 20.08%. However, one can always select different pruning rates to
properly trade off between prediction accuracy and speedup. It is mostly
noticeable the overall error is even decreased by using our methods, for Book-
Crossings shown in Figure 11(c). It might be because $k$, given as 50, is too
big to make the MF model fitting such a dataset. Our approaches, pruning some
of the latent factors, thereby cause better fitting in this case. This result
indicates our methods even help to prevent overfitting, when a large number of
latent factor dimensions is inappropriately selected.

We then measure the runtime of the conventional process and the accelerated
process using our methods, by setting different $k$, in Figure 12. Here we set
the pruning rate as 0.3 for our methods. As shown in Figure 12, the proposed
methods only slightly reduce the overall computational time, when $k$ is small
($e.g.$, 20). This is because the feature matrices are more dense in a small
latent factor dimension. An increased gap between the runtime of the
conventional process and that of the accelerated process can be observed,
suggesting a more dramatic speedup realized by the proposed approaches, when
$k$ is increased, because more latent factors become insignificant and thus
would be pruned by our methods.

In practice, $k$ is often empirically determined. In this paper, we do not
discuss how a suitable value of $k$ is determined. However, as we have
explained in Section 3.2, the fact that some users are less predictable and
thus need a larger model for prediction, always remains. A more steady
increase of the runtime can be observed by using our methods, when $k$ is
increased, so a RS can be designed with less considering the cost of longer
computational time caused by larger $k$.

20406080100$0.4$$0.6$$0.8$Number of latent vectorsRuntime
(second)ConventionalAccelerated (a)

20406080100$3$$4$$5$$6$Number of latent vectorsRuntime
(second)ConventionalAccelerated (b)

20406080100$6$$8$$10$Number of latent vectorsRuntime
(second)ConventionalAccelerated (c)

20406080100$15$$20$$25$$30$Number of latent vectorsRuntime
(second)ConventionalAccelerated (d)

Figure 12: Runtime when giving different number of latent factor dimensions.
(a) MovieLens 100K. (b) Appliances. (c) Book-Crossings. (d) Jester.

###  5.3 Impact of Hyperparameters

Some hyperparameters of a MF-based RS might be selected according to the
specific applications. Here we specifically investigate how a different
learning rate, optimization strategy and initialization method can affect the
speedup and prediction accuracy of our methods.

For the learning rate, we conduct experiments by setting the learning rates as
0.05, 0.1, 0.15, 0.2 and 0.25. For the optimization strategy, we implement
twin learners strategy [27] into LibMF. The twin learners strategy allows some
latent factors having a greater learning rate by not updating them in the
first epoch and updating them normally afterwards, to alleviate the problem
that the learning rate only dramatically changes in the first a few epochs,
leading to local optimal. For the initialization method, we further initialize
all latent factors by a uniform distribution, instead of using a normal
distribution, before the first training epoch.

We demonstrate the speedups when using our methods with different
hyperparameters, in Figures 13 (a), (c) and (e), where the pruning rate is set
to be 0.3. According to Figure 13 (a), a greater speedup can be realized by
our methods when a larger learning rate is used. We provide the explanation as
follows. According to Figure 7, the overall distribution of the latent factors
becomes flatter with a larger deviation, as the number of epoch increases. It
can be expected that the overall distribution of the latent factors would also
become flatter, when increasing the learning rate, as training process would
be converged more quickly. Therefore, after the first epoch, our methods would
lead to a larger threshold value, given the same pruning rate, when the
learning rate is larger, causing more latent factors to be pruned in the
subsequent iterations and resulting in a greater speedup. According to Figure
13 (a), a greater than 1.2 speedup can be realized by our methods in each
case, indicating our methods are applicable when setting different learning
rate. Furthermore, Since our methods can achieve high speedup at different
learning rates, our methods are also applicable to other optimizers with
adaptive learning rate like Adadelta and Adam. According to Figures 13 (c) and
(e), the speedups realized by our methods are generally independent of the
optimization strategies and initialization methods.

As shown in Figures 13 (b), (d) and (f), the errors caused by our methods may
vary when using different hyperparameters, but the $P_{MAE}$ is generally less
than 20% in each case. Furthermore, $P_{MAE}$ is mostly affected by dataset,
instead of the hyperparameters, as the $P_{MAE}$ caused by different
hyperparameters for a certain dataset is relatively similar, according to
Figures 13 (b), (d) and (f). For instance, greater $P_{MAE}$ can be observed
for Appliances and Jester, compared with that for MovieLens and Book-
Crossings, in all the cases considering certain learning rates, optimization
strategies and initialization methods.

The above results suggest the performance, such as speedup and error, might be
affected when using our methods for different datasets, but the difference is
mostly caused by the dataset itself, rather than the selection of certain
hyperparameters, Thus, our methods are applicable considering different
hyperparameters.

MovieLensAppliances Book-
---
Crossings
Jester$0$$0.5$$1$$1.5$SpeedupLearning rate: 0.05Learning rate: 0.1Learning
rate: 0.15Learning rate: 0.2Learning rate: 0.25 (a)

MovieLensAppliances Book-
---
Crossings
Jester$0$$10$$20$$P_{MAE}$ (%)Learning rate: 0.05Learning rate: 0.1Learning
rate: 0.15Learning rate: 0.2Learning rate: 0.25 (b)

MovieLensAppliances Book-
---
Crossings
Jester$0$$0.5$$1$$1.5$SpeedupTwin learnersNo twin learners (c)

MovieLensAppliances Book-
---
Crossings
Jester$0$$10$$20$$P_{MAE}$ (%)Twin learnersNo twin learners (d)

MovieLensAppliances Book-
---
Crossings
Jester$0$$0.5$$1$$1.5$SpeedupUniform distributionNormal distribution (e)

MovieLensAppliances Book-
---
Crossings
Jester$0$$10$$P_{MAE}$ (%)Uniform distributionNormal distribution (f)

Figure 13: Speedups and $P_{MAE}$ when using our methods with different
hyperparameters. (a) Speedups for different learning rates. (b) $P_{MAE}$ for
different learning rates. (c) Speedups for different optimization strategies.
(d) $P_{MAE}$ for different optimization strategies. (e) Speedups for
different initialization methods. (f) $P_{MAE}$ for different initialization
methods.

##  6 Conclusions

This paper proposes some methods to accelerate the training process of MF-
based RSs. During the MF process, feature matrix multiplication and latent
factor update are iteratively performed. However, we observe fine-grained
structured sparsity in the decomposed feature matrices, which is inevitable
because of the predictability for different users or items. The fine-grained
structured sparsity causes a large amount of unnecessary operations induced by
irregularly located insignificant latent factors, increasing the computational
time of both feature matrix multiplication and latent factor update. To
address this problem, we firstly propose to rearrange the feature matrices
based on joint sparsity, to make a latent vector with a smaller index
potentially more dense than that with a larger index in the feature matrices.
The feature matrix rearrangement is performed as pre-pruning process, to
reduce the error caused by the later pruning process. We further propose to
dynamically prune the most insignificant latent factors from both matrix
multiplication and gradient descent, during each epoch, to accelerate the
training process. The experimental results show our methods can realize
1.2-1.65 speedups, with up to 20.08% error increase, compared with the
conventional MF training process. We show the speedup can be further increased
if a larger latent factor dimension is applied in the RS. In addition, we
prove that our methods are applicable to be implemented in MF-based RSs
considering different hyperparameters, including learning rate, optimization
strategy and initialization method. Finally, we highlight our methods, unlike
all the existing techniques, which accelerate MF by putting in extra
computational resources and parallel computing, can reduce the computational
time of MF without any additional hardware resources.

##  Appendix A Appendix

Here we provide the detailed derivation of Equations (7) and (8), which
determine a threshold value according to a given pruning rate. Based on the
assumption that the original feature matrix follows normal distribution, we
define $p$ as a given pruning rate, $F(x)$ as the cumulative distribution
function of a feature matrix, $\mu$ and $\sigma$ as the mean and standard
deviation from $F(x)$, respectively, and $\phi(x)$ as the cumulative
distribution function of a standard Gaussian distribution.

The objective is to find a threshold $T$ ($T>0$) to meet the condition that
the proportion of the elements located in the range between $-T$ and $T$ in
$F(x)$ is $p$, as:

$\displaystyle F(T)-F(-T)=p$ (15)

The value of $T$ that satisfies Equation (15) can be determined, by firstly
converting $F(x)$ into $\phi(x)$ and then searching the standard normal table.
In such a case, we assume $-T$ and $T$ in $F(x)$ are relocated in $\phi(x)$
as, $x_{1}$ and $x_{2}$, respectively. According to the conversion from a
Gaussion distribution to a standard one, we provide Equations (16) and (17)

$\displaystyle x_{1}=(-T-\mu)/\sigma$ (16) $\displaystyle
x_{2}=(T-\mu)/\sigma$ (17)

where $x_{1}$ and $x_{2}$ satisfy Equations (18) and (19) and Equation (19) is
derived from Equations (16) and (17).

$\displaystyle\phi(x_{2})-\phi(x_{1})=p$ (18) $\displaystyle
x_{1}+x_{2}=-2\mu/\sigma$ (19)

According to Equations (18) and (19), $x_{2}$ would satisfy Equation (20), so
it can be easily found from the standard normal table.

$\displaystyle\phi(x_{2})-\phi(-x_{2}-2\mu/\sigma)=p$ (20)

Finally, once $x_{2}$ are determined, according to Equation (17), $T$ is
calculated as Equation (21), as follows:

$\displaystyle T=\sigma x_{2}+\mu$ (21)

## References

  * [1] Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al.  Wide & deep learning for recommender systems.  In Proceedings of the 1st workshop on deep learning for recommender systems, pages 7–10, 2016.
  * [2] Gediminas Adomavicius and Alexander Tuzhilin.  Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions.  IEEE transactions on knowledge and data engineering, 17(6):734–749, 2005.
  * [3] Yolanda Blanco-Fernández, José J Pazos-Arias, Alberto Gil-Solla, Manuel Ramos-Cabrer, Martín López-Nores, Jorge García-Duque, Ana Fernández-Vilas, Rebeca P Díaz-Redondo, and Jesús Bermejo-Munoz.  A flexible semantic inference methodology to reason about user preferences in knowledge-based recommender systems.  Knowledge-Based Systems, 21(4):305–320, 2008.
  * [4] John K Tarus, Zhendong Niu, and Ghulam Mustafa.  Knowledge-based recommendation: a review of ontology-based recommender systems for e-learning.  Artificial intelligence review, 50:21–48, 2018.
  * [5] Jiahao Liang.  An overview of recommender systems and its next generation: Context-aware recommender systems.  In 2021 International Conference on Signal Processing and Machine Learning (CONF-SPML), pages 33–36. IEEE, 2021.
  * [6] David Goldberg, David Nichols, Brian M Oki, and Douglas Terry.  Using collaborative filtering to weave an information tapestry.  Communications of the ACM, 35(12):61–70, 1992.
  * [7] Dong-Kyu Chae, Jung Ah Shin, and Sang-Wook Kim.  Collaborative adversarial autoencoders: An effective collaborative filtering model under the gan framework.  IEEE Access, 7:37650–37663, 2019.
  * [8] Francesco Ricci, Lior Rokach, and Bracha Shapira.  Introduction to recommender systems handbook.  In Recommender systems handbook, pages 1–35. Springer, 2010.
  * [9] Zhe Yang, Bing Wu, Kan Zheng, Xianbin Wang, and Lei Lei.  A survey of collaborative filtering-based recommender systems for mobile internet applications.  IEEE Access, 4:3273–3287, 2016.
  * [10] Alexandra Vultureanu-Albişi and Costin Bădică.  Recommender systems: an explainable ai perspective.  In 2021 International Conference on INnovations in Intelligent SysTems and Applications (INISTA), pages 1–6. IEEE, 2021.
  * [11] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  Computer, 42(8):30–37, 2009.
  * [12] Ruslan Salakhutdinov, Andriy Mnih, and Geoffrey Hinton.  Restricted boltzmann machines for collaborative filtering.  In Proceedings of the 24th international conference on Machine learning, pages 791–798, 2007.
  * [13] Thomas Hofmann.  Collaborative filtering via gaussian probabilistic latent semantic analysis.  In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 259–266, 2003.
  * [14] Miha Grčar, Blaž Fortuna, Dunja Mladenič, and Marko Grobelnik.  kNN versus SVM in the collaborative filtering framework.  In Data Science and Classification, pages 251–260. Springer, 2006\.
  * [15] John S Breese, David Heckerman, and Carl Kadie.  Empirical analysis of predictive algorithms for collaborative filtering.  arXiv preprint arXiv:1301.7363, 2013.
  * [16] Enyue Yang, Yunfeng Huang, Feng Liang, Weike Pan, and Zhong Ming.  FCMF: Federated collective matrix factorization for heterogeneous collaborative filtering.  Knowledge-Based Systems, 220:106946, 2021.
  * [17] Charu C Aggarwal et al.  Recommender systems, volume 1.  Springer, 2016.
  * [18] Simon Funk.  Netflix Update: Try This at Home, 2006.
  * [19] Yehuda Koren.  Factorization meets the neighborhood: a multifaceted collaborative filtering model.  In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 426–434, 2008.
  * [20] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974–983, 2018.
  * [21] Wei-Sheng Chin, Yong Zhuang, Yu-Chin Juan, and Chih-Jen Lin.  A fast parallel stochastic gradient method for matrix factorization in shared memory systems.  ACM Transactions on Intelligent Systems and Technology (TIST), 6(1):1–24, 2015.
  * [22] Xiaolong Xie, Wei Tan, Liana L Fong, and Yun Liang.  CuMF_SGD: Parallelized stochastic gradient descent for matrix factorization on GPUs.  In Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing, pages 79–92, 2017.
  * [23] Léon Bottou.  Large-scale machine learning with stochastic gradient descent.  In Proceedings of COMPSTAT’2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, pages 177–186. Springer, 2010.
  * [24] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research, 12(7), 2011.
  * [25] Matthew D Zeiler.  Adadelta: an adaptive learning rate method.  arXiv preprint arXiv:1212.5701, 2012.
  * [26] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [27] Wei-Sheng Chin, Yong Zhuang, Yu-Chin Juan, and Chih-Jen Lin.  A learning-rate schedule for stochastic gradient methods to matrix factorization.  In Advances in Knowledge Discovery and Data Mining: 19th Pacific-Asia Conference, PAKDD 2015, Ho Chi Minh City, Vietnam, May 19-22, 2015, Proceedings, Part I 19, pages 442–455. Springer, 2015.
  * [28] Yue Xiaochen and Liu Qicheng.  Parallel algorithm of improved FunkSVD based on GPU.  IEEE Access, 10:26002–26010, 2022.
  * [29] Feng Wei, Hao Guo, Shaoyin Cheng, and Fan Jiang.  AALRSMF: An adaptive learning rate schedule for matrix factorization.  In Web Technologies and Applications: 18th Asia-Pacific Web Conference, APWeb 2016, Suzhou, China, September 23-25, 2016. Proceedings, Part II, pages 410–413. Springer, 2016.
  * [30] Pu Chen and Hung-Hsuan Chen.  Accelerating matrix factorization by overparameterization.  In DeLTA, pages 89–97, 2020.
  * [31] Wei-Sheng Chin, Bo-Wen Yuan, Meng-Yuan Yang, Yong Zhuang, Yu-Chin Juan, and Chih-Jen Lin.  LIBMF: A library for parallel matrix factorization in shared-memory systems.  J. Mach. Learn. Res., 17(1):2971–2975, 2016.
  * [32] Tianqi Chen, Weinan Zhang, Qiuxia Lu, Kailong Chen, Zhao Zheng, and Yong Yu.  SVDFeature: a toolkit for feature-based collaborative filtering.  The Journal of Machine Learning Research, 13(1):3619–3622, 2012\.
  * [33] Nicolas Hug.  Surprise: A python library for recommender systems.  Journal of Open Source Software, 5(52):2174, 2020.
  * [34] 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.
  * [35] Jianmo Ni, Jiacheng Li, and Julian McAuley.  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), pages 188–197, 2019.
  * [36] Cai-Nicolas Ziegler, Sean M McNee, Joseph A Konstan, and Georg Lausen.  Improving recommendation lists through topic diversification.  In Proceedings of the 14th international conference on World Wide Web, pages 22–32, 2005.
  * [37] Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins.  Eigentaste: A constant time collaborative filtering algorithm.  information retrieval, 4:133–151, 2001.
  * [38] Jérémie Dona and Patrick Gallinari.  Differentiable feature selection, a reparameterization approach.  In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings, Part III 21, pages 414–429. Springer, 2021.
  * [39] Shijie Wang, Guiling Sun, and Yangyang Li.  SVD++ recommendation algorithm based on backtracking.  Information, 11(7), 2020.