ImplicitSLIM and How it Improves Embedding-based Collaborative Filtering
Authors: Ilya Shenbin
Sergey Nikolenko
Venue: ICLR 2024 poster (2024)
Keywords: collaborative filtering
representation learning
Primary area: representation learning for computer vision, audio, language, and other modalities

Abstract: We present ImplicitSLIM, a novel unsupervised learning approach for sparse high-dimensional data, with applications to collaborative filtering. Sparse linear methods (SLIM) and their variations show outstanding performance, but they are memory-intensive and hard to scale. ImplicitSLIM improves embedding-based models by extracting embeddings from SLIM-like models in a computationally cheap and memory-efficient way, without explicit learning of heavy SLIM-like models. We show that ImplicitSLIM improves performance and speeds up convergence for both state of the art and classical collaborative filtering methods. The source code for ImplicitSLIM, related models, and applications is available at https://github.com/ilya-shenbin/ImplicitSLIM.

Published as a conference paper at ICLR 2024
IMPLICITSLIM AND How IT IMPROVES EMBEDDING-BASEI COLLABORATIVE FILTERING
Ilya Shenbin & Sergey Nikolenko
St. Petersburg Department of the Steklov Mathematical Institute of the RAS
St. Petersburg, Russia
i 11ya. wwwnsheenng.. g com, bergey@logic..poee raa..ar.. ru
ABSTRACT
We present ImpliciSSLIM, novel unsupervised learning approach for sparse high-dimensional data, with applications to collaborative filtering. Sparse linear methods (SLIM) and their variations show outstanding performance, but they are memory-intensive and hard to scale. ImplicitSLIM improves ambedding-basee models by extracting embeddings from SLIM-like models in computationally cheap and memory-efficient way, without explicit learning of heavy SLIM-like models. We show that ImplicitSLIM improves performance and speeds up con- vergence for both state of the art and classical collaborative filtering methods. The source code for ImplicitSL.IM, IM, related models, and applications is available at lhttps://gitthb com ilya shenbin/ wttphheninnnmmiiiiiieiiie ImplicitSLIM
INTRODUCTION
Learnable embeddings are core part of many collaborative filtering (CF) models. Often they are introduced and learned explicitly: e.g., matrix factorization (MF) models express feedback
product of two embedding matrices (Mnih & Salakhutdinov 2007 Bell et al., 2007), autoencoders map user feedback embeddings via neural networks other parameterized functions (Sedhain) et al. 2015 Liang et al. 2018 Lobel et al. 2019; Shenbin et al. [2020; Mirvakhabova et al. 2020).
while graph convolutional networks (GCN) (Wang et al. [219 He al. (2020) perform diffusion process between user and item embeddings starting from some initial values. In this work, we propose an approach able to improve wide variety of collaborative filtering models with learnable
embeddings.
Item-itent methods, including kNN-based approaches (Sarwar et al., 2001) and sparse linear meth- ods (SLIM) (Ning& & Karypis 2011 are making predictions based on item-item similarity. Previous research shows that the item-item weight matrix learned by SLIM-like models can become part of other collaborative filtering models; e.g., RecWalk uses it transition probability matrix (Niko-) lakopoulos Karypis 2019). In this work, we reuse the item-item weight matrix in order to enrich embedding- models with information approach stems from nonlinear dimensionality reduction methods (e.g., VAEs) applied to collabo- rative filtering (Shenbin al. 2020). We consider a group of manifold learning methods that aim to preserve the structure of data in the embedding space, that is, they force embeddings of similar objects to be similar. A related idea has already been used in collaborative filtering models, e.g. by Rao et al. (2015).
item-item interactions. Another motivation for
We propose an upproach called ImplicitSLIM that performs nonlinear unsupervised learning of em- beddings that can be further used for making recommendations. The name ImplicitSLIM means that allows to extract useful data from SI.I-likke models without explicitly training SLIM itself and does not refer to models with explicit or implicit feedback (however, we consider only the case of implicit feedback). ImplicitSLIM learns item or user embeddings with closed form solutions that do not require computationally intensive operations. The resulting embeddings can be used for initial- ization or regularization of item and/or user embeddings for a wide variety of other methods, from matrix factorization to autoencoder- bassed approaches and models based on graph convolutional net- works, and also for RNN- or Transformer-based sequential models. In most cases, we find that Implici(SI.IM IM improves the final recommendation results, often very significantly. By adding Im-

---

Published as a conference paper at ICLR 2024
Pli to nonlinear VAEs such as Rec (Shenbin al., 2020) and H+ Vamp(Gatted (Kim & Sub 2019). we have been able to improve state of the art results on the MovieLens-2001 -2M and Netflix
Prize datasets.
Our method builds upon two known approaches. First, we consider locally linear embeddings (LLE) (Roweis & Saul 2000), nonlinear manifold learning method which is surprisingly well suited for our idea. LLE consists of two linear steps. The first step is very similar to SLIM, that is, it learns the weights for optimal reconstruction of data samples from their nearest neighbours, and on the second step low-dimensional embeddings are extracted from learned weights. In ImpliciSLLMM, we modify this procedure as follows: first, extracted embeddings are obtained given some prior embeddings, that is, we turn LLE into a procedure that consistently improves embeddings; second, we compress the two-step procedure into a single step without explicit computation of the intermediate weight matrix, which significantly reduces the costs in both computation and memory. Another approach that we use in our method is EASE (Steck) 2019). It is a slightly simplified case of SLIM with a closed form solution. A later empirical study by Steck et al. (2020) showed that features of SLIM that are dropped in EASE do not significantly improve performance in case of a large number of users. In this work, consider ImplicisSLIM based only on EASE, but we note upfront that the proposed approach could also be based on some other variations of SLIM with a closed-form solution, e.g., full-rank DLAE EDLAE (Steck 2020). Although the proposed method learns low-dimensional embeddings, we do not aim to construct a low-rank approximation of SLIM, as do, e.g., Jin et al. (22TT and Kabbur et al. (2013), but aim improve other existing models with SLIM.
Below, Section shows the necessary background, Section 3 develops ImplicitSLIM, Section Linte-
grates it into various collaborative filtering models, Section S our experimental evaluation, Section 7 reviews related work, and Section [ concludes the paper.
introduces the baselines and presents
2 PRELIMINARIES
In this section we describe the approaches that provide the background and motivation for Implic- iSLIM; for survey of other related work see Section 7 Consider an implicit feedback matrix X E {0, 1]UXI, where X., = 1 the u-th user positively interacted with (liked, watched etc.) the i-th item (movie, good etc.) and X
otherwise, and U and I are the numbers of users and items respectively. For low-rank models, we denote the embedding dimension by L.
Sparse Linear Methods (SLIM) is family of item-based approaches originally proposed by Ning & Karypis (201T) and further extended by [Christakopoulou & Karypis (2014 2016); Steck et al. (2020), and Steck 2020). The core idea of SLIM is learn to reconstruct user feedback for given item as a linear combination of feedback from the same user for other items. We focus on Emburrassingly Shallow Autoencoders (EASE) (Steck (219)), special case of SLIM that, critically for our approach, admits a closed form solution. EASE can be trained by solving the following optimization task:
B = argming
X
XB
12 + BI
s.t. diag B = 0,
where || ||5 is the Frobenius norm and diag B is the diagonal of B; the constraint forbids the trivial solution B- Problem (1) can be solved exactly with Lagrange multipliers, getting
B B= I- P diagMat(1 @ diag P),
+ XI)-1 diagMat(xx) is a diagonal matrix with vector x on the diagonal, a vector of ones, and denotes element-wise division; see /tteck (2019) for detailed derivations. SLIM has impressive performance but quadratic space complexity and nearly cubic time complexity. Elements of B that are close to zero can be zeroed, which leads to a highly sparse matrix and can partially solve the memory issue, but it will not reduce memory costs during training.
where P def x
Locally Linear Embeddings (LLE) is nonlinear dimensionality reduction method (Roweis & Saul, 2000 (Saul& & Roweis 2003 Chojnacki & Brooks 2009, Ghojogh et al.) (202)). For consis- tency, we introduce LLE in modified notation; Appendix A.I links it to the original. We denote the i-th data sample as X.; and the set of indices for nearest neighbors the i-th sample by NN()). LLE
works in two steps. First, it finds the matrix of local coordinate vectors B as
B argming Σ, IX::: Σ SEE
X,,B,ell s.t. B11=1,
(3)
2

---

Published as a conference paper at ICLR 2024
where B,, j NN(I). The matrix B is invariant to scaling, orthogonal transformations, and translations data samples; note that translation invariance is a result the sum-to-one constraint.
On the second step, LLE finds the embedding matrix V given the sparse matrix B:
= argminy ||V - VBI
s.t.
VV = mI,
=1=0.
(4)
The first constraint forbids the zero solution; the second removes the translational degree of freedom.
Regularization of embeddings plays important role for collaborative filtering models, could be performed with uninformative priors on embeddings (Mnih & Salakbutdinov (007). context infor- mation MccAuley & Leskovee, 2013 Ling al. (014). information item-item interactions to regularize item embeddings (or, symmetrically. user embeddings). Liang et al.) (2016) and Nguyen et al. (2017) learn matrix factorization embeddings jointly with item embeddings obtained from the cooccurrence matrix with a word2vec-like approach. Rao et al. (2015) use graph regularization, minimizing the distance between item embeddings that similar according to given adjacency matrix A, ie.. optimizing the following penalty function:
RerApHrEG (Q) = tr (QLQT) = =,,, AuyIQ. Quy 12
(5)
where L is the graph Laplacian matrix corresponding to adjacency matrix À and Q is the L Lx / item embedding matrix. We will return regularization of item embeddings in Section 4
PROPOSED APPROACH
3.1
SLIM AS LLE
Consider the first step of LLE defined in (1,2.... {i);;; we can rewrite as
3). We propose to use the neighborhood function NN(1)
B argming
X - XB
s.t. B B diag B = O.
Due to this choice the neighborhood function, we obtain a simpler closed-form solution for this optimization problem (compared to the general solution from LLE), which will make it possible to perform the main trick in Section 3.2 Moreover, now this problem very similar to the EASE optimization task (I. but with an additional constraint that columns of B sum one and without Frobenius norm regularizer on B. The latter was claimed to be an important feature of SLIM (Steck) 2 similar regularizer was proposed by the authors of LLE (Saul & Roweis 2003). Therefore, propose bring it back, computing B follows:
B argming |X XBI A| s.t. B 1, diag B 0.
(6)
form of LLE and shown that EASE can be considered as the first step LLE without the sum-to-one con- straint. Now we can extract item embeddings with LLE using first step inspired by EASE: (i) first compute B with (6) using EASE with the sum-to-one constraint, then (ii) find the embeddings by solving 4). We call this approach SLIM-LLE. The same procedure with the transposed feedback matrix X will extract user embeddings instead of item embeddings. However, SLIM-LLE is com- putationally intensive, not memory efficient, and cannot use available embeddings as priors. In what follows, we fix these drawbacks.
See Appendix A.2 for the solution of this optimization task. Thus, have introduced
3.2 IMPLICISSIMM
We revisit the second step of LLE (4) Suppose that want obtain embeddings close to a given matrix of item embeddings Q. Instead of (4) we introduce the following unconstrained optimization problem:
argminy V
VB + all(V Q)
where a is a nonnegative regularization coefficient and A an auxiliary weight matrix whose key purpose will be exposed at the end of this subsection. As will below, this problem has
3

---

Published as a conference paper at ICLR 2024
unique nonzero solution, hence constraints from the second step of LLE are not necessary here. The sum-to-one constraint the first step of LLE (3) implicitly ensures the sum-to-zero constraint the second step of LLE (4. but have redefined the second step (7) an unconstrained optimization problem, so now there is no technical need in the sum-to-one constraint; it also provides translational invariance, but we do not have good reason why it could be useful here. Hence drop the sum- to-one constraint to obtain a simpler closed form solution for the first step, i.c., we use the EASE problem T directly as the first step of LLE (Appendix E.2 examines this choice empirically). The ultimate reason for dropping the sum-to-one constraint is that the resulting form of the first step will allow us to avoid explicitly calculating the matrix B, we will show below in this section.
We can now find closed form solution for 7
-= ==aQA A (B I I) + AA
(8)
Now we can substitute here the first step solution which further (drastically) simplifies the calculations. Recall from (2) that B
PD where Dp def diagMat P). i.e., Dp is
equal to P with zeroed non non-diagonal elements. Also recall that der ( + introduced in (1. so P is symmetric. Therefore,
AI)-1, where À was
V = -QQAAA (PD A AA)
We now see that 7 actually has unique nonzero solution if P is full-rank, which is true from (T) is positive. To compute it, we have to invert I x I matrices twice, which is the main computational bottleneck here. Using the Woodbury matrix identity, we rewrite 9 as
V aQA (R-I-R-'AT (a -I+ AR ARR AR-1).
(10)
where R is introduced abbreviate the formulas and is defined
R del 2P, i.e., R- (x
( AI).
(11)
The most troublesome multiplier here is Dp: we approximate it as (see Appendix A.3 for deriva- tions)
Dp ~ D = diagMat(1 @ diag(X X x
(12)
Assuming A is L x I matrix with L I, and using the approximation shown above, avoid the inversion of I x matrices in (TO) by reducing it to inverting I. x L matrices. Moreover, we can avoid even storing and multiplying
matrices with closer look (10). First, we expand the
brackets in 10 and (1). and calculate AR which we denote as F def AR
AX XD X X + AAD, T x AAX XD
AAD22
(13)
Now we can rewrite 10P as
= aQA T F FA (a- -I FA FAA)-FFF)
(14)
= =QQA (F (I- (I aFA ()
In (13) and [4). any intermediate result is at most an L x max(U, I) matrix, which makes Implic- itSLI much more computationally and memory efficient than explicit computation of (2) and (8). Now we are dealing only with matrices of moderate size, whose number of elements depends lin- early on the number of items or users in the worst case, except for the sparse feedback matrix X. Note that have introduced the auxiliary weight matrix A in (7) and then assumed that it is an x matrix with L < 1, but we still have not specified the matrix A. We propose to set equal to Q, so the regularizer IVQ QQ } from (7) could be considered as approximate pairwise distance. Appendix E.2 compares it empirically with a more natural-looking regularizer V QI?
Overall, in this section we have motivated and introduced ImplicitSLIM, method inspired by SLIM and LLE; we have shown how it can be derived and efficiently implemented. We also showed a predecessor of ImplicitSI JM, SLIM-LLE, which is special case of L.L..
4

---

Published as a conference paper at ICLR 2024
4 IMPLICITSLIM WITH OTHER MODELS
4.1 GENERAL SCENARIO
ImplicisSI.IM is not standalone approach. Below, we show how emheddings obtained with Implic- iSLIM can be applied to existing models. First, the item embeddings matrix Q of given model SLIM-LLE. Since ImplicitSLIM itself requires an embed-
can be initialized with ImplicisSLIM ding matrix as input, which could be initialized either randomly (e.g., from the standard normal distribution), with the output of ImplicisSLIM/SLIIM IM-LLE (improving the embeddings iteratively), or with an external model. Moreover, when we are training a collaborative filtering model we can send its embeddings matrix Q to Implici(SL.IM and replace it with the result (V in Section 3.2) immediately before the update of Q (not necessarily every update). This procedure may be less stable than minimizing the distance between Q and ImplicitSLIM output but requires fewer calls to ImplicitSLIM.
4.2 SLIM REGULARIZATION
In this section we first briefly suspend the discussion of ImplicitSL.IM to introduce and motivate the SLIM regularizer, and then show how we can take advantage of in an efficient way via Implicit- SLIM. Inspired by LLE, specifically by its second step (4). define the SLIM regularizer as
SSLIM REG (Q) = 1Q QBI 1Q. O.,
(15)
where B is the item-item similarity matrix from SLIM. This penalty function forces each item embedding to be close to the linear combination of other embeddings with coefficients learned by SLIM. Unfortunately, using this regularizer could be computationally costly and, moreover, it needs
precomputed matrix B, which takes away scalability. We emphasize that Slumred is equal to the graph regularizer
5) for certain matrices B, e.g. for one obtained from SLIM with the sum-to-one constraint (6); see Appendix (..nndxxxAA4eee for details.
Let fer O Q) be the loss function of some collaborative filtering model, where Q is the embedding matrix and θ represents other model parameters. Adding the SLIM regularizer, we get the following loss function:
Cer+ REG (9, Q) = (.. Q) + RLL Q)
(16)
We propose to optimize the resulting loss function by alternating optimization of both terms. In order to perform this optimization, we relax SLIMRRG as
PRELAXED CF SLIM REG (O, Q. V) f.r((,rr00000o Q) + SSLIMRE (V) +a d(Q, V),
where d(Q.V) is the distance between two embedding matrices Q and such that Les+ + SLIM REG ( Q) = AXEL SLIM REG (9, Q, Q). Now we can update the loss function w.r.t. (9, Q)
and V alternately. Let d( ( V) = (IV - Q) T i then
Q)A which is the same as V is equal to the embeddings extracted with ImplicitSLIM. This means that we can compute V efficiently and even without an explicit computation of B by using the results of Section 3.2
V argminy
CRELAXED REG (9, Q V) argminy II VB
EXPERIMENTAL EVALUATION
For experiments, we follow the basic evaluation setup by Liang al. (2018). We test the pro- posed approaches on three datasets: Movielens-20Md (Harper & Konstan 2015). Netflix Prize 2 Datase [Bennett al. 2007). and Million Songs Datase (Bertii-Mahieuxx et al. 2011). com- paring models in terms of the ranking metrics Recall@k and NDCG@K. Experiments are con- ducted in the strong generalization setting (Marlin 2004): users in the training, validation, and test
wwwpeeettt//iieeeeneeeeeee http://milTiomaaggaaaee...
5

---

Published as a conference paper at ICLR 2024
subsets are disjoint. We also perform additional benchmarking in the setup by He et al. on Yelp2018 (Wang et al. 2019) and MovieLLns-IMM (Harper & Konstan 2015) datasets. There datasets split into train/test subsets along the ratings, I.c., according to the weak generalization setting. Moreover, we test our approach in the setup by Sun et al. (2019) on the Moviel /M and Moviel datasets discussed above. Here the last and the penultimate feedback of every user are used as test and validation data respectively, while the remaining feedback is used as training data. In this setting, sampled metries are employed in order to speed up computation. The choice of these three setups is determined by the models to which we apply the proposed method. In order to achieve fair comparison of the results, we inherited dataset splits, metrics, and evaluation strategies from the corresponding setups.
(2020)
We have selected a number of different models as baselines: (1) matrix factorization (MF); we con- sider MF trained with ALS with uniform weights (Hu et al. 2008), which is a simple and compu- tationally efficient baseline, and also weighted matrix factorization (WMF) (Hu al,, (008) trained with eALS (He et al.] 2016); (2) MF augmented with regularization based on item-item interac- tions; here we selected CoFactor (Liang et al.) 2016), which combines MF and word2vec, and GRALS (Rao et al., 2015) that employs graph regularization; (3) linear models; have chosen full-rank models SLIM (Ning & Karypis| 2011) and EASE (Steck) 2019) and a low-rank model PLRec (Sedhain et al., 20T6) (we use only I-Linear-FLow); (4) nonlinear autoencoders; here consider the shallow autoencoder CDAE (Wu et al., (016), variational autoencoder MultVAE (Liang ct al.) 2018), and its successors: RaCT (obell et al. 2019), Vec (Shenbin et al., 2220). and H+ #+Vanp(Gated) (Kim & Suh 2019). Details on the implementation and evaluation of baselines are
provided in Appendix B
ImplicisSLIM is not a standalone approach; thus, we have chosen several downstream models to evaluate it. As MF and PLRec are simple and lightweight models, we used them as downstream models for extended experiments with ImplicitSLIM and SLIM-LLE. There are lots of ways to uti- lize embeddings from ImplicitSI.IM in downstream models, but for the experimental section we have selected several that are most demonstrative and effective. Apart from MF evaluation in its vanilla form, we use the following setups for MF as a downstream model: (1) ImplicitSLIM init+reg, where item embeddings are regularized by ImplicitSLIM and initialized by ImplicitSLIM that gets sample from the standard normal distribution as input: (2) SLIM-LLE init and ImplicitSLIM init, where item embeddings are initialized respectively by SLIM-LLE and by applying ImplicitSLIM repeatedly several times; in both cases, the corresponding loss function is minimized to obtain user embeddings at the validation/test stage only, i.e., there no training phase, only hyperparameter search; We use similar setups for PI PlRec-based experiments. PLRee has two item embedding ma- trices, W and Q: the first one is fixed, and the latter is learnable. When using PLRec with setups defined above, initialization applies only to W: it is meaningless to initialize Q since we have a closed form solution for Q; on the other hand, regularization applied only to Q since W is fixed. Other differences are that the SLIM-LLE init setup applied to PLRec has training phase which a single update of Q and in ImplicitSLIM init+reg is initialized by applying ImplicitSLIM repeatedly.
We also have applied Implici(SLIM to other methods. WMF hard to scale, so we tested it only with small embedding dimensions in the ImplicitSL.IM init+reg setup. Among nonlinear autoencoders we selected the most successful ones, namely RecVAE and H+ Vamp(Gated), to evaluate them with ImplicisSLIM as regularizer. Unlike MF and PLRec, these models are trained using stochastic gra- dient descent (SGD), so we need a different scenario of applying ImplicitSLIM.. Namely, we have found that the best performing procedure for models of this kind is to feed current item embeddings to ImpliciaSLIM and update them with the resulting embeddings.
We did not apply ImplicitSL CoFactor and GRALS since both have their own regularization techniques that utilize item-item interaction. We also did not apply ImplicitSI.I to SLIM and EASE since our approach can be applied to embedding- based models only.
In addition, we consider UltraGCN (Mao et al., 2021). which is state of the art GCN-influenced embedding-based model according to Zhu et al. (2022). It has trainable embeddings for both users and items, and the same users are considered in both train and test time. This allows us to ap- ply ImplicitSLIM not only for item embeddings but also for user embeddings. In both cases we

---

Published as a conference paper at ICLR 2024
MF MovieLens-20M
MF Netflix Prize Dataset
MF Million Songs Dataset
0.42
0.39
0.35
0.25
0.36
0.38
0.35
0.15
126
1024 2048 4096
64
126
1024 2048 4096
64
126
1024
2048 4096
PLRec MovieLens-20M
PLRec Netflix Prize Dataset
PLRec Million Songs D Dataset
0.35
0.42
0.30
0.41
0.25
0.40
0.36
0.20
0.39
128
256
512
1024 2048
4096
64
128
256
512
1024
2048
4096
64
128
256
512
1024 2048 4096
vanilla
ImplicitSUM init
ImpliCASLIM init
SLIM-LLE init
Figure I: ImplicitSLIM and SLIM-LLE applied to MF and PLRec (setups defined Section 5 the X-axis shows embedding dimensions, the Y-axis shows NDCG@ @ 100.
0.06
0.46
Yelp 2018
ML 200
0.45
0.04
0.44
0.03
UltraCN
0.42
0.43
RecVAE
UltrAGNN ImpliciSSLIM
0.41
Rec VAE + ImpliciSSLIM
0.01
0.40
20
40
60
80
100
20
40
60
80
100
0.41
0.40
Netfix
0.39
0.38
H+ Vamp (Gated) ImplicitSI.IM
0.37
0.36
50
100
150
200
250
300
Figure 2: Sample convergence plots for state of the art models with ImpicitSLIM: the X-axis shows training epochs; Y-axis, NDCG@20 metric on Yelp2018, NDCG@ 100 metric on other datasets.
update embeddings in several epochs, similarly nonlinear autoencoders. We also consider BERT4Rec (Sun et al.) (019) as a popular sequential model with strong performance. See Ap- pendix D for detailed description experimental setups and pseudocode.
RESULTS
Figure [ presents the results of applying ImplicitSLIM and its variations to matrix factorization (MF) and PLRec for different embedding dimensions (X-axis), Using ImplicisSL/M for both initial- ization and regularization yields the best results in most cases. More interestingly, initialization by ImplicitSLIM shows nearly equivalent performance, which means that embeddings obtained with ImplicitSLIM are good enough to have update them with alternating least squares. Thus, Im- PM is not only more computationally efficient than other models but also performs better in terms of prediction scores. The performance SLIM-LLE varies greatly depending on the dataset and downstream model, and in some outperforms ImpLicitSLIM, but it lacks scalability (results shown for SLIM-LLE are limited embedding dimensions due to high computational costs).
Table shows that MF and PLRec regularized by ImplicitSLIM are approaching EASE in perfor- mance, especially in high dimensions, but are computationally cheaper and more memory efffore-effccient in most cases. Fig, shows when ImplicitSLIM is preferable in terms of wall clock time and mem- ory usage compared to vanilla MF and EASE (see Appendix [E.I for running time details). Note, however, that EASE has only one hyperparameter while Implici(ST.I and MF together have five.

---

Published as a conference paper at ICLR 2024
Table 1: Experimental results. The best results are highlighted in bold.
Movieleens-20M
Netflix Prize Dataset
Million Songs Dataset
Model
Recall
Recall @50
NDCG
Recall
Recall
NDCG
Recall @20
Recall @50
NDCG
@20
@ 100
@20
@50
@ 100
100
Matrix factorization
MF
0.367
0.498
0.399
0.335
0.422
0.369
0.258
0.353
0.314
+mplicitSLM
0.392
0.524
0.423
0.362
0.445
0.390
0.309
0.403
0.366
WMF
0.362
0.495
0.389
0.321
0.402
0.349
HmplicitSLIM
0.372
0.502
0.400
0.326
0.409
0.365
Matrix factorization with item embeddings regularization
CoFactor GRALS
0.369
0.499
0.394
0.327
0.406
0.357
0.376
0.505
0.401
0.335
0.416
0.365
0.201
0.275
0.245
Linear regression
SLIM EASE
0.370
0.495
0.401
0.347
0.428
0.379
0.391
0.521
0.420
0.362
0.445
0.393
0.333
0.428
0.389
PLRec
0.394
0.527
0.426
0.357
0.441
0.390
0.286
0.383
0.344
+ImpliciSLII
0.391
0.522
0.423
0.358
0.440
0.390
0.310
0.406
0.364
Nonlinear autoencoders
CDAE
0.391
0.523
0.418
0.343
0.428
0.376
0.188
0.283
0.237
Mul(VA
0.395
0.537
0.426
0.351
0.444
0.386
0.266
0.364
0.316
RaCT
0.403
0.543
0.434
0.357
0.450
0.392
0.268
0.364
0.319
ReeVAE
0.414
0.553
0.442
0.361
0.452
0.394
0.276
0.374
0.326
+IpliciSLIM
0.419
0,559
0.447
0.365
0.455
0.398
0.291
0.391
0.342
H+ Vamp(Gated)
0.413
0.551
0.445
0.377
0.463
0.407
0.289
0.381
0.342
+ +IplicitSLLIM
0.417
0,555
0.450
0.378
0.464
0.410
0.292
0.386
0.347
Table 2: Experimental results for GCN-based models.
Yelp2018
MovieL 1M
Model
Recall
NDCG@20
Recall@21
NDCG@2 20
LightGCN
0.0649
0.0530
0.2576
0.2427
UltrGGN
0.0683
0.0561
0.2787
0.2642
UltraGCN ImplicitSLIM (users)
0.0689
0.0568
0.2778
0.2648
UltraGCN IMpLici(SLIM (items)
0.0692
0.0573
0.2790
0.2659
Table 3: Experimental results for BERT4Rec.
MovieLens- MM
MovieLens-225
# epochs
Model
Recall @S
Recall @ 10
NDCG
Recall
Recall
NDCG
@ 10
@S
@10
@ 10
BERT4Rec
0.612 0.660
0.729
0.511
0.895
0.952
0.780
30
BERT4Rec ImplicisSLIM
0.765
0.549
0.904
0.959
0.789
BERT4Rec
0.645
0.758
0.545
0.901
0.953
0.790
200
BERT4Rec ImplicitSLIM
0.671
0.771
0.564
0.910
0.961
0.798
Table I also shows that ImplicitSLIM significantly improves performance (by the one-tailed test at the 95% confidence level) compared to all corresponding baselines except H+ Vamp(Gatte) on the Netflix Prize dataset in terms of Recall@k. Another valuable result is that deep models trained with ImplicitSLIM need about half as much time to achieve the best scores of deep models trained as is. By combining ImplicitSLIM with nonlinear variational autoencoders, RecVAE and H+ +I+Vamp(Gater we have been able to improve over state of the art results on the MovieLens-201 20M and Neffli Prize datasets. Note that ImplicitSLIM together with RecVAE (or H+ H+Vamp(Gated) performs better these datasets than both Rec VAE and H+ Vamp((Gated and EASE. Rec VAE with ImplicitSLIM per- forms par with improved MF the Million Songs Dataset, but with much smaller embedding
8

---

Published as a conference paper at ICLR 2024
dimension. Figure 2 shows sample convergence plots of UltraGCN and Rec with and without ImpliciSSLIM for three select cases; periodic drops on the plots correspond to epochs when item embeddings were updated with ImplicisSLII.
In our experiments, using user embeddings from ImpliciSSLMM has not led to performance improve- ments, but this may be due to the strong generalization setting employed in most experiments.
Further, we have applied ImplicisSLIM to UltraGCN (Mao et al., 2021), a state-of-ther the-art art GCN- based model, in the setup by He et al. (2020). Table shows that we have succeeded in improving the performance by applying ImplicitSLIM to user embeddings, although ImplicitSLIM applied to item embeddings shows significantly larger improvement. We note that both Implici(SI.IM and GCN-related models rely significantly on the diffusion of embeddings, so it is actually a bit sur- prising (albeit very encouraging) that ImplicitSLIM has been able to improve the performance of UltraGCN. Finally, we have applied ImplicisSLIM to BERT4Rea (Sun et al. 2019). sequential model. Table shows that although ImplicitSLIM does not take order into account, it can still be useful for sequential models. Namely, ImplicitSLIM allows BERT4Rec to achieve its best results in significantly fewer iterations, which is important for such heavy-weight models, and also im- proves its final performance. Appendix [ detailed evaluation of specific models, runtime statistics, influence of ImplicitSLIM on unpopular items, convergence plots etc.
shows our evaluation study in more details, including
7 RELATED WORK
Matrix factorization (MF) Mnih & Salakhutdinov 2007: Bell et al. 2007: Koren & Bell 2011)
standard but still competitive CF baseline. Simple but high-performing alternative approaches include Sparse Linear Methods (SLIM) (see Section 2) they are difficult to scale so there exist low-rank variations such as factored item similarity models (FISM) (Kabbur et al.) 2013). Other approaches reduce the problem to low-dimensional regression (Sedhain et al. (016)) (see Section and perform low-dimensional decompositions of SLIM-like models (Jin et al. 202I). Nonlinear generalizations include autoencoder-based models that learn to map user feedback to user embed- dings instead of learning the embedding matrix explicitly. Early approaches used shallow autoen- coders (Sedhain et al. [015 Ww et al., 2016), and recently variational autoencoders have led to better models (Liang et al. 2018; Lobel et al. 2019: Kim & Suh 2019 Shenbin et al.) 2020 Mir- vakhabova et al. 2020). LRR (Jin al. 2021 appears be the model most similar ours; first computes the item-item similarity matrix and then performs its low-rank approximation, avoiding explicit computation of the similarity matrix by reducing the inversion of large matrix comput- ing top eigenvectors; we reduce it to inverting a low-dimensional matrix. However, ImplicisSLIM has different motivation than LRR and different usage. Graph convolutional networks (GCN) are relatively new in collaborative filtering; NFCF (Wang et al.) 2019) and LightGCN (He et al., 2020) were computationally heavy, and recent approaches such as GF-CF (Shen et al. 2021) and UltraGCN (Mao et al. 2021) improved both performance and computational efficiency. Related approaches that regularize embeddings based on item-item interactions are discussed in Section 4 Dimensionality reduction methods can be either linear (c.g., PCA) nonlinear, e.g., LLE (Roweis) & Saul, 2000) Ghojogh et al.] 2020) and ISOMAP (Tenenbaum et al.) /0000/ Modern nonlinear dimensionality reduction with VAES (Kingma & Welling 2014) has been successfully applied to collaborative filtering, but in a different way than the use of LLE in this work.
CONCLUSION
In this work, we have presented ImpliciaSLIIM, novel approach based on the EASE and LLE models that can be used to initialize and/or regularize item and user embeddings for collaborative filtering models. We have shown that ImpliciSSLIM can improve many existing models in terms of both per- formance and computational efficiency. We have applied Implici(SLLM to MF, autoencoder-basel and graph-based models, and in most cases shown consistent improvements over the corresponding basic versions, achieving new state of the art results classical datasets when applied to nonlinear autoencoder-bart based models. We propose ImplicitSLIM as generic approach able to improve many collaborative filtering models.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
All datasets used in our paper are publicly available, either together with scripts that split datasets into train/validation/esst subsets (MovieLLes-220M, Netflix Prize Dataset, and Million Songs Dataset) or already available divided into train/test subsets (Yelp2018 and Movielens- IM). Source code for the implementation of Implici(SLLIM sufficient to reproduce the most impor- tant results of this paper is submitted as supplementary materials. The source code available www.sshhehbbniieeee http:/yyyaasaoniiimm/mmmoiiiii11 Furthermore, pseu- docode of downstream methods is presented in Appendix D The hyperparameter search process is described in Appendix C and all necessary derivations are presented in Appendix A
on GitHub: https: / github.
ACKNOWLEDGMENTS
This work performed at the Saint Petersburg Leonhard Euler International Mathematical In- stitute and supported by the Ministry of Science and Higher Education of the Russian Federation (Agreement no. 075-15-2022-289, dated 06/04/2022).
REFERENCES
Robert Bell, Yehuda Koren, and Chris Volinsky. Modeling relationships at multiple scales to improve accuracy of large recommender systems. In Proceedings the 1 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 95-104, 2007.
James Bennett, Stan Lanning, al. The netflix prize. In Proceedings of KDD cup and workshop. volume 2007, pp. 35. New York, 2007.
Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011), I), 2011.
Wojciech Chojnacki and Michael Brooks. A note on the locally linear embedding algorithm. International Journal of Pattern Recognition and Artificial Intelligence, 23(08): 1752, 2009.
Evangelia Christakopoulou and George Karypis. Hoslim: Higher-order sparse linear method for top- recommender systems. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 38 49. Springer, 2014.
Evangelia Christakopoulou and George Karypis. Local item-item models for top-n recommendation. In Proceedings of the 10th ACM Conference on Recommender Systems, pp. 67-74, 2016.
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley. Locally linear embedding and its variants: Tutorial and survey, arXiv preprint arXiv:2011. 2020.
Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
Xiangnan He, Hanwang Zhang, Min-Yen Ven Kan, and Tat-Seng Chua. Fast matrix factorization for online recommendation with implicit feedback. In Proceedings of the 39th International ACM SIGIR conference on Research and Development Information Retrieval, pp. 549-558, 2016.
Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pp. 639 648, 2020.
Yifan Hu, Yehuda Koren, and Chris Volinsky. Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE international conference on data mining, pp. 263-272. Icee, 2008
Ruoming Jin, Dong Li, Jing Gao, Zhi Liu, Li Chen, and Yang Zhou. Towards better understanding of linear models for recommendation. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 776-785, 2021.
10

---

Published as a conference paper at ICLR 2024
Santosh Kabbur, Xia Ning, and George Karypis. Fism: factored item similarity models for top-n recommender systems. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 659-667, 2013.
Daeryong Kim and Bongwon Suh. Enhancing vaes for collaborative filtering: flexible priors & gating mechanisms. In Proceedings of the 13th ACM Conference Recommender Systems, pp- 403-407, 2019.
Diederik P. Kingma and Max Welling. Auto- encoding variational bayes. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14- 16, 2014, Conference Track Proceedings, 2014,
abs/1312. 2////311.61111 6114
Ychuda Koren and Robert M. Bell. Advances in collaborative filtering. In Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor (eds.), Recommender Systems Handbook, pp. 145- 186. Springer, 2011. ISBN 978-0-387-858192 reference/ rrchncc//rrh/eee
URL http:://bb.p..ni-tteeeee html #KorenB11
de/db/
rsh2011 Dtteerence/rsh/rs220111
Dawen Liang. Jaan Altosaar, Laurent Charlin, and David M Blei. Factorization meets the item embedding: Regularizing matrix factorization with item co-occurrence. In Proceedings of the 10th ACM conference on recommender systems, pp. 59-66, 2016.
Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara. Variational autoencoders for collaborative filtering. In Proceedings of the 2018 world wide web conference, pp. 689-698, 2018.
Guang Ling, Michael R Lyu, and Irwin King. Ratings meet reviews, combined approach to rec- ommend. In Proceedings of the 8th ACM Conference on Recommender systems, pp. 105-112, 2014.
Sam Lobel, Chunyuan Li, Jianfeng Gao, and Lawrence Carin. Ract: Toward amortized ranking- critical training for collaborative filtering. In International Conference on Learning Representa- tions, 2019.
Kelong Mao, Jieming Zhu, Xi Xiao, Biao Lu, Zhaowei Wang, and Xiuqiang He. Ultragen: Ultra
simplification of graph convolutional networks for recommendation. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 1253-1262 2021.
Benjamin Marlin. Collaborative fillerin A machine learning perspective. University of Toronto Toronto, 2004.
Julian McAuley and Jure Leskovec. Hidden factors and hidden topics: understanding rating dimen- sions with review text. In Proceedings the 7th ACM conference on Recommender systems, pp. 165-172, 2013.
Leyla Mirvakhabova, Evgeny Frolov, Valentin Khrulkov, Ivan Oseledets, and Alexander Tuzhilin. Performance of hyperbolic geometry models on top-n recommendation tasks. In Fourleenth ACM Conference on Recommender Systems, pp. 527-532, 2020.
Andriy Mnih and Russ R Salakhutdinov. Probabilistic matrix factorization. Advances in neural information processing systems, 20, 2007.
ThaiBinh Nguyen, Kenro Aihara, and Atsuhiro Takasu. Collaborative item embedding model for implicit feedback data. In International Conference on Web Engineering, pp. 336-348. Springer, 2017.
Athanasios N Nikolakopoulos and George Karypis. Reewalk: Nearly uncoupled random walks for top-n recommendation. Proceedings of the twelfth ACM international conference on web search and data mining, pp. 150-158, 2019.
Xia Ning and George Karypis. Slim: Sparse linear methods for top-n recommender systems. In 2011 IEEE 11th International Conference on Data Mining, pp. 497-506. IEFF, 2011.
11

---

Published as a conference paper at ICLR 2024
Fernando Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014. URL http:///s...aaaaaoooooo/////aaaa
Aleksandr Petrov and Craig Macdonald. A systematic review and replicability study of bert4rec for sequential recommendation. In Proceedings of the 16th ACM Conference on Recommender Systems, pp. 436-444, 2022.
Nikhil Rao, Hsiang-Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. Advances in neural information processing systems, 28, 2015.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500):2323-22256 2000.
Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International Conference on World Wide Web, WWW '01, pp. 285-295, New York, NY, USA, 2001. Association for Computing Machin- ery. ISBN 1581 133480. doi: 10. 00.1145/3112003372777 URL URLattps://aa..ooo////
371920. 372071
Lawrence Saul and Sam Roweis. Think globally, fit locally: unsupervised learning of low dimensional manifolds. Journal of machine learning research, 4(Jun):119-155 2003.
Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. Autorec: Autoencoders meet collaborative filtering. In Proceedings of the 24th international conference on World Wide Web, pp. 111-112, 2015.
Suvash Sedhain, Hung Bui, Jaya Kawale, Nikos Vlassis, Branislav Kveton, Aditya Krishna Menon, Trung Bui, and Scott Sanner. Practical linear models for large-scale one-class collaborative filter- ing. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp. 3854-3888888 3860, 2016.
Yifei Shen, Yongji Wu, Yao Zhang, Caihua Shan, Jun Zhang, B Khaled Letaief, and Dongsheng Li. How powerful is graph convolution for recommendation? Proceedings of the 30th ACM International Conference Information Knowledge Management, pp. 1619-1629, 2021.
lya Shenbin, Anton Alekseev, Elena Tutubalina, Valentin Malykh, and Sergey Nikolenko. Recvae: A new variational autoencoder for top-n recommendations with implicit feedback. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 528-536, 2020.
Harald Steck. Embarrassingly shallow autoencoders for sparse data. In The World Wide Web Con- ference, pp. 3051-325177 2019.
Harald Steck. Autoencoders that don't overfit towards the identity. Advances in Neural Information Processing Systems, 33:19598-19608. 2020.
Harald Steck, Maria Dimakopoulou, Nickolai Riabov, and Tony Jebara. Admm slim: Sparse recom- mendations for many users. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 555-563, 2020.
Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequen- tial recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM international conference on information and knowledge managemeni, pp. 1441- 1450, 2019.
Joshua B Tenenbaum, Vin de Silva, and John C LLagford. A global geometric framework for nonlinear dimensionality reduction. science, 290055500:2319-2333, 2000.
Xiang Wang. Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collaborative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pp. 165-174, 2019.
12

---

Published as a conference paper at ICLR 2024
Yao Wu, Christopher DuBois, Alice X Zheng, and Martin Ester. Collaborative denoising auto- encoders for top-n recommender systems. In Proceedings of the ninth ACM internationaa confer- ence on web search and data mining, pp. 153-162, 2016.
Daniel Zelazo and Mathias Bürger. On the definiteness of the weighted laplacian and its connection to effective resistance. In 53rd IEEE Conference on Decision and Control, pp. 2895-2900. IEEE, 2014.
Jieming Zhu, Kelong Mao, Quanyu Dai, Liangeai Su, Rong Ma, Jinyang Liu, Guohao Cai, Zhicheng Dou, Xi Xiao, and Rui Zhang. Bars: Towards open benchmarking for recommender systems. arXiv preprint arXiv:2205.0960 0.0666, 2022.
13

---

Published as a conference paper at ICLR 2024
A PROOFS AND DERIVATIONS
A.1 DEFINITION OF LLE
In this section we introduce LLE it was done in the original works by Roweis & Saul (2000);
Saul & Roweis (003). We denote by D,, the i-th data sample, by W. its local coordinate Vector, and by NN(1) the indices for nearest neighbors of the i-th data sample; the number of data samples. The first step find the matrix W:
2
W argminw Σ D:
E
W.y
s.t.
Σ W
(17)
JENN(S)
2
where Wiy = j & NN(I). On the second step, LLE finds the embedding matrix Y given the sparse matrix W:
Y argminy E
Yi. W.,
(18)
s.t. Y.YY. =I, ΣY =0
Denoting D = XT, W B and Y
V rewrite 17 and (8) in this notation
B argmini Σ
X.:
Σ
X.yBji
BB 1,
(19)
jENN(()
argminy Σ
V.i -E V. jz
(20)
s.t. Σ V.VVV =I,
Vv==0
Rewriting formulas 19 and 20 in matrix form whenever possible, we derive and respec-
tively.
A.2 DERIVATION OF SLIM-LLE
To get the item-item interaction matrix from the first step
B argming X X-BB + B|
s.t. B = 1, diag B = O,
(21)
we have to solve the following system of linear equations:
ØB (IX - XBI A||B| + 2n diag (B) + 2k 2B" 1)) 0.
T = 1,
(22)
diag B = 0.
The solution is
B p (1((1))T)
p P1(P1)")
diagMat 10 diag
(10diag
1TP1
17P1
where p def
X X -I
14

---

Published as a conference paper at ICLR 2024
A.3 DIAGONAL OF THE INVERSE OF A MATRIX
We begin by representing the inverse of a matrix A as an infinite sum derived from the Neumann series:
30 A-
Σ
I A)
(23)
==0
We note that B-1 D- D-1 (BD-1) -1 where D def diagMat(ding B), and substi-
tute
BD into 23 to obtain
B B- D
[I - 1-BD-1)"
(24)
We now approximate B with the first two terms the Neumann series:
B ~ D-1 (I+ (I - BD-
Since we need only diag B-1 rather than the full matrix B-1, we simplify the result to -1
diag
2 diag(
D (I+ - BD- = 2D dDag(D-'BD>>) = D-1
Next we show that the series
converges:
Σ
BD
S Σ
1--DD"II""
m=
n=U
As we defined earlier, Bij
X,J + A = jl. X E (0, (0,1)UX, > 0. and Dij =
X., 2) [ = j]. where
[.] the indicator function. Then
|| I-BD
BD 1|1 max
Σ
= /| (BD )())
[ = /] X, X -1
max
X,j +1
([i= = 51 X x X.j
max
X,, + A
Σ Ligf X
(1 - 1111)XT,,,
max
max
Xoj
X.j
Thus, if > (I 1 2) max, (X]
(x.)
X then I- BD
||1 < 1, and the series in 24 converges.
A.4 LLE AND GRAPH REGULARIZATION
We can represent the SLIM regularizer 15 graph regularizer 5
QQ QBI - ||Q(I
B) tr (Qa B)(I Q") der tr (QLQ²).
Here L is positive semi-definite matrix since a Gram matrix. However, in general i is not graph Laplacian matrix.
Assuming that B 1 1 and diag B 0, we get
L = (I
- -
(I 8
Since L is also a symmetric matrix, the sum of any row or column equal zero. As result, there exists such an adjacency matrix Á that L is the corresponding graph Laplacian matrix, and
(iagMat(diag(L)) i.
15

---

Published as a conference paper at ICLR 2024
Algorithm 1: Pseudocode for vanilla matrix factorization
Data: dataset X, number of iterations hyperparameters Tp. rg
Result: item embeddings matrix Q
Q < standart Gaussian noise;
for i f- 1 to k do
P - argminp LMP(Xiraine (Erainn Qp Q argmitio LMF MMIr(Xrrint P,Tg);
evaluate X vvlldd TpTp):
current validation score < the best validation score then break;
end end
Note that some values in Á could be negative; while is uncommon consider a graph Laplacian matrix for a graph with negative weight edges, such matrices have been introduced in some papers, in particular by Zelazo & Bürger (2014). Fortunately, even despite the presence of negative values in the adjacency matrix the graph regularizer is still equal to the weighted sum of pairwise distances (5)
As result, we claim that the SLIM regularizer with matrix B taken from SLIM-LLE is equal to the graph regularizer. Unfortunately, this equality does not hold for the matrix B taken from EASE
B
ADDITIONAL DETAILS ON BASELINES
B.1 MATRIX FACTORIZATION
The MF model used in our experiments is defined by the following loss function:
LMF Q) = -X-
Q -
[P Qll
(25)
where LR-XU the user embeddings matrix, Q LxI the item embeddings matrix, and rp and ry are regularization coefficients. LMF [P, Q) can be optimized with alternating least squares (ALS).
We used c5L$5 setting, so that the model would be comparable to others.
implementation of WMF, but had to adapt it to the strong generalization
For MF and WMF, we can easily obtain embeddings of held-out users from validation/test sets in the same way we update user embeddings during training using the closed form solution for user embeddings given fixed item embeddings and held-out validation/test feedback matrix.
B.2 MATRIX FACTORIZATION WITH ITEM EMBEDDINGS REGULARIZATION
CoFactor was evaluated in a different setup in the original papers, so we had to re-evaluate it. We publicly available implementation of CoFacto but similarly eALS we have had to adapt to the strong generalization setting.
Since there is publicly available implementation of GRALS, have implemented it indepen- X dently. We use the cooccurrence matrix X X as the adjacency matrix with diagonal elements zeroed. Following the experimental results of of et al, (2020), use the symmetrically normalized graph Laplacian. Graph regularization was applied to item embeddings only to be consistent with other experiments.
In order to update item embeddings in GRALS we have to solve the Sylvester equation, which requires us to compute the eigenvectors of large matrix on every step of the ALS algorithm. To avoid this computation, we propose to update item embeddings using gradient descent with optimal step size search, which just slightly hurts performance terms of ranking metries while being much more computationally efficient.
16

---

Published as a conference paper at ICLR 2024
Algorithm 2: Pseudocode for the vanilla PLRec
Data: dataset X, hyperparameter Tg
Result: item embeddings matrix Q W < initialize using SVD;
Q C argming LPLREC (T.Rec(Xeratte (Xtrain; W,rg);
evaluate(X vaiii ini T,Tp):
B.3 LINEAR MODELS
We use SLIM (Ning& & Karypis 2011) and EASE Steck 2019) as baselines, taking the scores of SLIM from (Liang a 2018), and scores of EASE from (Steck) 2019).
For our experiments we have reimplemented PLRec, we consider the following objective function:
CPLREC Q) = | Xw Ql + +rll1Q
(26)
There two item embedding matrices in this model: W projects ratings into low- dimensional space and Q maps user embeddings to predicted user ratings. Matrix W is assumed to be initialized by the SVD item embeddings matrix, and is fixed during training.
We have found that normalizing the columns of X before projecting into a low-dimensional space significantly improves the performance. Specifically, in our experiments replaced W in (26) with N T, where N is a diagonal matrix with N = [X..ITT where n is a parameter to be tuned during cross-validation.
B.4 NONLINEAR AUTOENCODERS
We consider several nonlinear autoencoders as baselines: CDAE (Wu et al. 2016), MultVAE (Liang et al. 2018), RaCT (Lobel al. 2019). RecVAE (Shenbin et al. 2020), and H+ H+Vamp(Gated (Kim & Suh 2019). Scores for these models were taken from the corresponding papers, except for CDAE where took them from (Liang al. 2018). Also, scores of H+ Vamp(Gated) Million Song Dataset were not published in original paper, so we get the scores ourselves using original imple- mentation of this model.
C HYPERPARAMETER SEARCH
We use the BayesianOptiinzzation library (Nogueira) 2014) for hyperparameter search. At every step of Bayesian optimization, evaluate the model with the current set of hyperparameters. When the hyperparameter search procedure ends, we select the set of hyperparameters that maximizes the validation score; then we use the selected set of hyperparameters evaluate the model test data.
Learning a large number of models is time-consuming for models with high-dimensional embed- dings. In order speed it up. we start hyperparameter search with low-dimensional embeddings. When we terminate the search procedure for the current dimensionality, we increase the dimen- sionality and begin new hyperparameter search, but begin evaluate the model on the set of hyperparameters that was chosen best at the previous dimensionality. This narrows down the search in larger dimensions and can find sufficiently good hyperparameters much faster, especially for heavyweight models.
We perform at least 200 steps of Bayesian optimization for every model, with the exception of most heavyweight models, for which introduce additional external restriction of ten hour limit per model.
The heaviest setup for training MF and PLRec is SLIM-LLE init. Unlike the others, it requires huge matrix inversions and computation of eigenvectors for the smallest eigenvalues. As a result, computational costs for this setting much higher, especially when the dimensionality of embed- dings is large. Hence we have limited the evaluation of this setup on the Million Song Dataset with embedding dimensions equal to 1024 and lower. Additionally, we have precomputed LLF.-LLM
17

---

Published as a conference paper at ICLR 2024
Algorithm 3: Pseudocode for ImplicitSLIM init+reg matrix factorization
Data: dataset X, number of iterations hyperparameters Tp. Ng. Sg. X,
Result: item embeddings matrix Q Q < standart Gaussian noise: for i +- 1 to k do
< ImplicisSLIM(X.. Ltrain train Q A, a);
if then
Q + V; end
P f- argminp LMF-IMMLCTTSIIM (rraain yn Q Tp)i
Q argminio LMF IMM-INMPICTSSLIM (X (xrainn P Ta. 8q);
evaluate( iaaiid Q,
current validation score < the best validation score then break;
end end
Algorithm 4: Pseudocode for ImplicitSLIM init matrix factorization
Data: dataset X, number of iterations k. hyperparameters Tp. A. at
Result: item embeddings matrix Q
Q < standart Gaussian noise;
for + to k do
Q ImplicisSLIM(XX train Q, X, a);; evaluate( Q Tp):
if current validation score the best validation score then break;
end end
Algorithm 5: Pseudocode for SLIM-LLE init matrix factorization
Data: dataset X, number of iterations lt, hyperparameters rp. X, Result: item embeddings matrix Q
Q SLIM-LLE(X traim A);
OvaluateXX,,at Q,Tp):
embeddings for various values of À logarithmic grid with step 0.1, and we have not computed embeddings for other values of À during hyperparameter tuning.
D ADDITIONAL DETAILS ON IMPLICITSLIM WITH OTHER MODELS
D.1 IMPLICITSLIM WITH MATRIX FACTORIZATION AND PLREC
We have evaluated ImplicisSLIM in application to matrix factorization and PLRec. To describe these setups in detail, we present the pseudocode for all them. We define the loss function for ImplicitSLIM init+reg follows:
LMF IMPLICISI.IM (P, Q V) X P P 8q V Q1 + r IP| + Q
(27)
Regularizer s, V
Q
? is used instead of s,l((V Q)Q || to get a closed form solution.
In order to present Algorithm 6 first define the Lpt REC- REcc-TMMLIISSLLN loss as
CPLREC- MMPEICIMLLIIIIIII (Q V) XW X +
& Q11
18

---

Published as a conference paper at ICLR 2024
Algorithm 6: Pseudocode for ImplicitSLIM init+reg PLRec
Data: dataset X, number of iterations hyperparameters Tg. Sq. X, a
Result: item embeddings matrix Q
V < standart Gaussian noise:
for i + 1 to k do
ImplicisSLIMi X train V, A, a);
V orthogonallier(V;
W V:
Q argminq LPLREC-MPPICITSLIM (Ereeins W, V, Tg:
evaluate Vallid, Q,Tp):
current validation score < the best validation score then break;
end end
Algorithm 7: Pseudocode for SLIM-LLE init PLRec
Data: dataset X, hyperparameters Tgp À
Result: item embeddings matrix Q
W + SLIM-LLE(X crain. A);
Q argminl LPIREE (PIRec(Xtrasn, W,ry);
evaluate(X (a.iiee vai 1,rp):
Algorithms in this section return only item embedding matrices since we are working in the strong generalization setting; the user embedding matrix is not required for further evaluations.
In the main text, we approximated the user-item interactions matrix X with low-rank matrix PTQ Q- In our experiments we also used the matrix P Q 3++11 1bbb instead, i.e., employed a bias vector. Using a bias vector has led to better results in some experiments. For both matrix factorization and PLRec, estimate b using maximum likelihood, and in both cases set b, the mean value of elements of vector X
In Section it proposed to set A equal to Q. Since embeddings of unpopular items could be noisy, we propose to first set equal to Q but then zero out columns A that correspond to unpopular items; threshold of item popularity here becomes another hyperparameter.
D.2 IMPLICITSLIM WITH VAE, GCN AND BERT4REC
The most successful of these models, namely RecVAE and H+ H+VampGGated), have also been evalu- ated with additional regularization via ImplicitSLLM. For this purpose, we used the original imple- mentations of RecVAH and H+ Vamp(Gated [ and integrated ImplicitSI.IM into them follows: the item embeddings matrices from both encoder and decoder are updated with ImplicitSI.IM once every several epochs (every 10 epochs for Rec,AE, every 15 epochs for H+Vamp(Gated)); addi- tionally, the dimension of embeddings has been increased to 400 for Rec VAE; the rest the setup taken from original implementations.
According to Zhu et al. (022), GF-CF (Shen et al. 202 and UltraGCN (Mao et al. of-the-art art GCN- ifffuneleedeed models. However, GF-CF has trainable embeddings,
2021) are state-
apply
ImplicisSLIM to UltraGCN only. Unlike models we have mentioned above, UltraGCN is based on different setup. It has trainable embeddings for both users and items, and the same users considered in both train and test time. That allows us to apply ImplicitSIIMM not only for item embeddings but also for user embeddings (using its official implementation (.) In both cases update embeddings once in several epochs, similarly to nonlinear autoencoders.
19

---

Published as a conference paper at ICLR 2024
Table 4: INN scores of embeddings obtained with different methods.
Embedding dimensionality
10
100
Standard Gaussian noise
0.423
0.423
SVD SLIM-LLE
0.634
0.695
0.661
0.713
ImpliciSLII
0.630
0.704
MF
0.620
0.693
MF + ImplicisSLIM
0.636
0.692
Rec
0.667
0.760
RecVAE + ImpliciASIIM
0.688
0.758
In order to show that Implici(SI.I can be useful not only for collaborative filtering models in their classical form, we have also applied it to sequence-based recommendations. We have chosen BERT4Rec (Shen et al. 2021] as one of the most popular sequential model with strong performance. To perform our experiments we took its unofficial implementation" since the results shown by Shen al. (202T) fail to reproduce with the official implementation, according experiments performed by Petrov & Macdonald 2022). Item embedding matrices are updating during training every two epochs for the MovieLens- IM dataset and every 20 epochs for the MovieLens-2004 20M, similarly to nonlinear autoencoders.
experiments, ImplicitSI.IM regularization (namely minimizing the distance be- tween the current embedding matrix and the one updated by ImplicitSIIM) does not improve the performance of VAEs and GCNs compared to the approach proposed above. According our in- tuition, it happens because embeddings updated by ImplicitSLIM become out of date after several stochastic gradient decent updates of current embedding vectors. Moreover, this form of Implicit- SLIM application is more computationally expensive.
According
D.3 EVALUATION EMBEDDINGS WITH INN
In additional to our evaluation of ImplicitSLIM on the collaborative filtering downstream task, we have also evaluated extracted embeddings employing contextual information. Items from the MovieLens-2OM. dataset have genre labels, where some items could have several labels and others might have none. Items without labels were excluded for this experiment.
We evaluate the embeddings using popular way to evaluate visualization methods based on the assumption that similar items should have similar labels. define it as follows:
[Q.; and its nearest neighbor have at least one common label]]
where [-] is the indicator function and Q- is the embedding vector of the ith item. Results presented in Table[4 For the sake of a fair comparison, labels were not used either when learning the embeddings or tuning the hyperparameters. We use the same hyperparameters as for experiments shown in Table
E ADDITIONAL DETAILS ON RESULTS
E. RUNTIME
Table 5 shows runtime comparison of ImplicitSLIM and its variation with explicit computation of the matrix B (that includes Step 1 and Step 2). The runtime of ImplicitSLIM significantly depends on the dimensionality of the embedding matrix, thus we have measured for different dimensions. As http:s/s/.hthhaocc///////otttttr
see, using ImplicirSLIM instead of straightforward calculations drastically reduces com- putational time.
20

---

Published as a conference paper at ICLR 2024
Table Runtime of embedding extraction procedures, seconds.
ImplicitSI.M
Step 1
Step 2
8
64
128
256
512
1024
2048
4096
ML-20M Netflix
48.7
53.3
0.37
0.7
1.4
2.6
5.1
12.0
31.1
67.4
78.1
1.7
3.4
6.6
12.1
23.0
52.0
133.2
MSD
389.9
452.9
1.4
2.5
7.7
17.5
32.7
64.5
132.0
Table 6: Evaluation high, mid, and low popularity items, NDCG@ 100 scores
Dataset Items poplarity
Moviel_ens-20M
Netflix Prize Dataset medium
high
medium
low
high
low
MF
0.392
0.097
0.036
0.366
0.092
0.057
MF ImpliciSSLIM
0.416
0.110
0.040
0.383
0.138
0.089
RecVAE
0.444
0.192
0.092
0.402
0.209
0.157
Rec ImplicitSLIM
0.449
0.180
0.086
0.405
0.213
0.165
Fig. shows convergence plots for matrix factorization (MF), MF with ImplicitSLIM init (we call it MF ImplicisSLIM here for short), and EASE. Since EASE is not iterative model, its plot is presented as single point. We also note that MF + Implici(SLIM reaches its best scores in one iterations in these experiments. We show individual plots for MF and MF Implici(SI.IM with different embedding dimensionality. As a result, Figure 3 shows that MF + ImplicitSLIM obtains better results than MF in terms of both metric scores and wall clock time. Moreover, MF ImplicitSLIM is also competitive with EASE: while it obtains slightly lower scores in the quality metric, it contains much fewer parameters and needs less time train most cases.
F.2 EVALUATION OF APPROXIMATIONS
To make ImpliciSSLIM efficient in both computation time and memory, have made several ap- proximations and simplifications:
(a) the constraint in (6) is dropped:
(b) diagonal of the inverted matrix is approximated with (12):
(c) [[V - QQQ || is used in instead of ||V QlI
We have compared the performance of ImplicitSLIM and its explicit version where approxima- tions (a-c) are not used, using MF and RecVAE as base models on the MovieLens-20M and Net- flix datasets. In all cases the difference in results was negligible, so they are not shown in Table 1, which validates the efficiency approximations ImplicitSLIM. We note, however, that the almost identical optimal scores were achieved at different hyperparameter values.
E.3 EVALUATION ON UNPOPULAR ITEMS
We divided the items into groups of the same size: very popular, with medium popularity, and with low popularity, and then evaluated several methods each of these groups. According the results shown in Table 6) ImplicisSLIM generally boosts the performance for items with low and medium popularity more significantly than for very popular items. There one exception, however: RecVAE evaluated on MovieLens-20ke In our opinion, this is an effect of zeroing out columns in matrix A that correspond unpopular items, as we describe it in Appendix D.I which hurts the performance for unpopular items in this case.
21

---

Published as a conference paper at ICLR 2024
MovieLens-2OM
0.420
1024
2048
4096
512
0.415
256
0.410
128
0.405
0.400
512
64
0.395
256
0.390
0.385
128
10
20
40
60
Netflix Prize Dataset
0.39
4096
2048
1024
0.38
512
256
0.37
128
256
0.36
128
0.35
64
64
20
40
60
80
100
120
140
Million Songs Dataset
4096
0.35
20,48
1024
0.30
512
256
0.25
512
256
128
128
0.20
644
64
50
100
150
200
250
300
350
400
EASE
ImplicitSLIM
MF
Figure 3: Convergence plots for MF, MF ImplicisSLIM, and EASE; the X-axis shows wall-clock time is seconds, the Y-axis shows NDCG@ 100; MF and MF ImplicitSLIM have been evaluated with different embedding dimensions shown in the figure.
22


Reviews:
[{"review_id": "O144kcava6", "reviewer": "Reviewer_uknn", "summary": "This paper proposed a method named implictSLIM that can be integrated with other embedding-based methods.", "questions": "Please refer to the above comments.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n-\tThe approaches addresses the memory-intensive and scalability issues of SLIM-like models in collaborative filtering.\n-\tThe authors provided various experiments on publicly available benchmark datasets \n-\tSource code is also provided \n-\tMany appendices were given for more explanation", "weaknesses": "Weaknesses:\n\n-\tIn Section 3 Proposed Approach, the authors should explain more on the formular choices when developing ImplicitSLIM. For example, why do we use LLE, but use the neighbourhood of NN(i) = {1,2,…,I} \\ {i} to make it ‘global’ (Section 3.1)? Why do we drop the sum-to-one constraint (Section 3.2) (the authors did mention they have no good reasons, but why)? In my opinion, Section 3 is very important and the authors should provide deeper explanations and discussions about this. Otherwise it’s very hard to convince the readers.\n-\tIn the first paragraph after Figure 2, the authors mentioned that “In addition, ALS applied to MF regularized by …. about 5x faster”, I may missed it but where do we find the ‘5x faster’ comparison? \n-\tIn Figure 1, why ImplicitSLIM init + SLIM reg and SLIM-LLE init cannot have results with > 500 embedding dimension? Could we please add an appendix on the ‘high computational costs’?\n-\tIn Section 4.1, in the last sentence, the authors mentioned that “this procedure may be less stable … fewer calls to ImplicitSLIM”. Why is that?\n-\tIn Table 1, the performance results are not really impressive. For example, in the Appendix E.1, the authors mentioned that “Moreover, ImplicitSLIM is also faster than EASE… could replace EASE in some cases due to lower computational time and comparable performance.”. Please explain which cases? \n-\tIn Appendix E.3, Table 5, why RecVAE + ImplicitSLIM cannot perform better than RecVAE? \n-\tReferences should be sorted as the current version is hard to follow (minor)\n\nOverall, more works need to be done.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9fzfeihlpV", "reviewer": "Reviewer_EMBd", "summary": "This paper proposes a novel unsupervised learning approach for sparse high-dimensional data. The method learns local structure of data (embeddings) in the embedding space where the embeddings of similar objects to be similar.", "questions": "This paper is too theoretical than any other submissions on NeurIPS and ICLR. I hardly follow the content.", "limitations": "", "rating": 3, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper learns embeddings with closed form solutions.\nGood Experimental study.", "weaknesses": "- This paper is very theoretical and hard to follow the formulas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g2UudUcJXY", "reviewer": "Reviewer_Fj6S", "summary": "The paper introduces ImplicitSLIM, an approach leveraging insights from established linear models such as EASE and LLE. The authors advocate its use for initializing and regularizing item and user embeddings across various collaborative filtering architectures. ImplicitSLIM streamlines the process of extracting embeddings, exhibits robust generalization capabilities, and accelerates convergence of the downstream models. As a comparatively lightweight and effective solution, it has the potential to become a valuable tool in representation learning for collaborative filtering, contributing to both theoretical understanding and practical implementation. \n\nThe text is well-written and easy to follow. The presentation of the approach is transparent and mathematically sound. The obtained results are convincing and demonstrate the advantages of the proposed solution. I'd vote to accept the paper.", "questions": "There's a promise to provide empirical comparison with more natural-looking regularizer in Appendix E.2. However, not much information is provided there. The promise creates an expectation that there will be a more substantial comparative data with numbers and graphs. Is it planned to be provided?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- mathematically sound approach with a closed-form solution\n- showcases practical efficiency in the standard collaborative filtering task\n- good generalization capabilities", "weaknesses": "- not a standalone approach which makes training less straightforward\n- applicable to embedding-based models only\n- the source code is not provided", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HglXjYZmBS", "reviewer": "Reviewer_dkLJ", "summary": "This paper focuses on an influencial autoencoder-based collaborative filtering model SLIM and draws inspiration from its optimization objective and correspondingly proposes ImplicitSLIM. ImplicitSLIM combines the advantages of SLIM's objective function and Locally Linear Embeddings. ImplicitSLIM also introduces a novel regularization item and an initialization method for embedding-based collaborative filtering models. Experimental results are presented to demonstrate the effectiveness of the proposed model.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "+ The authors propose a novel and general method that enhances performance of embedding-based CF models, which has practical significance.\n+ The theoretical analysis of existing works on autoencoder-based models is persuasive and easy to follow. The paper provides a clear and insightful review of existing methods from an optimization perspective.\n+ ImplicitSLIM is well-motivated and presents a novel solution for embedding-based CF.\n+ The paper is generally well-written, ensuring readability and clarity.", "weaknesses": "- The paper introduces various settings for ImplicitSLIM, but it would be beneficial to analyze and summarize the computational complexity of different variants respectively to provide a clearer understanding of their efficiency.\n- The paper could benefit from more detailed experimental studies on the influence of hyperparameters. Given the presence of multiple regularization and optimization items in the method, it would be more illustrative to have the model performance w.r.t. different parameter settings.\n- Although ImplicitSLIM has shown competitive performance against traditional linear encoders, it shows limitted improvement on deeper models like UltraGCN and RecVAE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)