Sketching Dynamic User-Item Interactions forOnline Item Recommendation
Takuya Kitazawa
Graduate School of Information Science and Technology
The University of Tokyo, Japank.takuti@gmail.com
ABSTRACT
Online recommendation techniques such as incremental matrix factorization have been widely studied to capture users’
preferences from real-world dynamic user-item interactions.
These recommenders generally take a model-based approach
which relies on stochastic gradient descent optimization, but
it sometimes shows diﬃculties on hyperparameter optimization and scalability. In order to work around this diﬃculty,
the author considers a completely diﬀerent approach basedon matrix sketching, which is more mathematically tractableand flexible than the existing techniques. More specifically,
this paper proposes a new online item recommender inspiredby a matrix-sketching-based streaming anomaly detection
framework. We discuss its fruitful properties with particularemphasis on the similarities between item recommendation
and anomaly detection. Experimental results demonstraterobustness and flexibility of the proposed framework.

Keywords
Matrix sketching; online learning; implicit feedback

1. INTRODUCTION
On the real-world applications such as online ad and ecommerce, user-item interactions (e.g. click, purchase, rate)
are valuable to capture users’ preferences, and recommendersystems need to tackle an item ranking problem based onsuch users’ implicit feedback. Most importantly, recent studies showed that real-world item recommenders commonly
suﬀer from cold-start persistency, and online updating of arecommendation engine is an eﬀective way to overcome theproblem [3]. However, the state-of-the-art techniques are
not always practical for the following reasons.
First, most online item recommenders take a model-based
approach which can be optimized by stochastic gradient descent, and they usually face the lack of eﬀective ways tofind proper hyperparameters in an incremental fashion. To
give an example of state-of-the-art incremental matrix factorization (iMF) [6] and incremental factorization machines
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.

(iFMs) [3], even if we narrowly find the optima in an initialbatch training step, the best values may show poor compatibility with further unforeseen events. Hence, streaming
algorithms with less, simpler hyperparameters are preferable
in reality.
Moreover, scores computed by the classical item recommenders are unnatural. Since modern recommenders stress“post-processing” such as generating explanation and incorporating into a hybrid recommender, the scores have to beeasily interpretable. However, binary prediction ŷ obtained
from the existing techniques can be less than 0 or greaterthan 1, and incremental MF and FMs compute item scoresby an inelegant heuristic function |1 − ŷ|.
As the example above shows, the current state-of-the-arts
are in some sense inflexible. Therefore, this paper turns
to a diﬀerent direction and seeks a more mathematicallytractable approach to propose a robust, flexible recommenderthat can fully take advantage of intuitive concepts and theoretical guarantees. To the end, we apply an eﬃcient matrix sketching technique to a stream of user-item interactions, and recommend items based on the orthogonal projection. We also discuss how item recommenders resemble
anomaly detectors, because our algorithm relies on a streaming anomaly detection framework. The proposed framework
is a whole new paradigm of looking at item recommendation.

2.

PROBLEM DESCRIPTION

Our goal is to develop a recommender system which works
eﬃciently and eﬀectively in a realistic streaming environment as depicted in Fig. 1.

&'()! *+,-.
!"#

!

!%#

!$#
Figure 1: Online item recommender: (1) recommend a
top-N list to a user, (2) interact with an item (e.g. click, buy,rate), and (3) update parameters based on the interaction.
More specifically, satisfying the following two properties
is a minimum requirement for online item recommenders:
1. Online-updating. Algorithms have to be incremental.
2. Implicit feedback. Explicit rating is not considered.

CHIIR ’17, March 07-11, 2017, Oslo, Norwayc 2017 ACM. ISBN 978-1-4503-4677-1/17/03. . . $15.00⃝
DOI: http://dx.doi.org/10.1145/3020165.3022152

In addition, this paper requires the proposed item recommender to hold the following properties:

3. Feature-expressiveness. Due to users’ rare activity
and dynamically changing user/item properties, modern
recommenders have to use auxiliary information (e.g. time,
demographics) as feature representations.
4. Usability. Hyperparameters and item scores should be
simple; easy-to-choose integer hyperparameters and easily understandable scores are desired to improve feasibility of a recommender.
5. Parallelizability. Modern applications usually stand on
distributed systems, so parallelizing and merging recommendation models are necessary. Furthermore, since apurely online algorithm may not be needed in reality, arecommender needs to flexibly support both of purely online and mini-batch update based on merging.
As the author showed in Sec. 1, the state-of-the-arts [1, 3,
6] are infeasible due to the lack of the above properties.

3. ONLINE ITEM RECOMMENDATION USING MATRIX SKETCHING
This section describes the proposed online item recommendation framework. Sec. 3.1 first states the key ideathat anomaly detection and item recommendation can be
discussed interchangeably, and Sec. 3.2 introduces a stateof-the-art online anomaly detection technique. Finally, thedetails of the proposal are clarified in Sec. 3.3.

3.1 Similarities between Anomaly Detection and
Online Item Recommendation
This paper argues that anomaly detectors can be seen
as an online item recommender, because both of them
deal with a very similar problem. That is, anomaly detectors and item recommenders respectively find dissimilar andsimilar samples from captured patterns of the past events.
Additionally, since both problems tackle dynamic data, theirresearch fields share common challenges. In spite of the obvious similarity, this view has never been explicitly pointed
out in the literature to the best of the author’s knowledge.
It should be noted that anomaly detectors are generally
categorized into outlier and change-point detectors. Bothtypes of anomalies are strongly related to online item recommendation. In terms of outliers, finding suddenly-observed
unforeseen patterns is a similar challenge to making reasonable recommendation for new users and items. At the sametime, change-points can be interpreted as a trend in data
streams; working around with the shifting (i.e., dynamic)
patterns is a crucial challenge for online item recommenders.
Importantly, it is clear that all properties of online item
recommenders described in Section 2 are also necessary foranomaly detectors as follows:
1. Online-updating. Since anomaly detection directly affects to system reliability, anomalies should be detected
as fast as possible by using up-to-date models.
2. Implicit feedback. In a context of anomaly detection,a term “feedback” indicates single data point in a system,and the task is binary prediction to infer whether a data
point is anomaly or not. This setting is exactly sameas implicit-feedback-based recommendation which makes
prediction for a unary target value.
3. Feature-expressiveness. Anomalies are usually detectedby a combination of various factors monitored in a target system. For example, log files provide many diﬀerent
features such as timestamp and the number of requests.

4. Usability. Complex hyperparameters and confusing scores
are not preferred because explanation of detectors’ output is important in practice to make decision.
5. Parallelizability. Modern huge back-end systems arehighly distributed, and data points may come from multiple data streams. Thus, the anomaly detectors shouldbe parallelizable.
Therefore, the author connects the field of anomaly detection with online item recommendation.

3.2

Streaming Anomaly Detection using Matrix Sketching

Sketching is a technique to eﬃciently approximate particular properties of massive data, with strong theoreticalguarantees. Recently, Liberty [4] proposed a matrix sketching technique, frequent directions (FD), and it had been
proved that a huge matrix A ∈ Rm×n (m ≪ n) can be approximated by a tiny sketched matrix B ∈ Rm×ℓ (ℓ < m)
as AAT ≈ BB T . In particular, matrix A and B satisfy thefollowing property:
AAT − BB T ⪰ 0 and ||AAT − BB T || ≤ 2||A||2F /ℓ,where ⪰ 0 indicates that a matrix is positive semidefinite.
Thanks to the above property, orthonormal bases of A canbe eﬃciently approximated by singular value decomposition(SVD) of the much smaller matrix B.
Huang and Kasiviswanathan [2] took advantage of FD’s
fast, iterative sketching algorithm and proposed a streaming
anomaly detection framework. A key idea of their approachis to sketch a series of “normal” vectors to a tiny matrix B.
By the orthogonal projection of a newly observed unit vector
x onto the orthonormal bases Uℓ obtained from SVDℓ (B),an anomaly score can be defined as a = ||(I − Uℓ UℓT )x||;
larger scores indicate that the vector is far from a “normal”
vector space.
Note that, they actually extended discussion about FD to
randomized matrix sketching for computational eﬃciency,
but we now focus on the original FD-based matrix sketchingfor simplicity. It can be easily extended to the randomized
variant in the future.

3.3

Sketching User-Item Interactions

This paper proposes a novel online item recommender inspired by the matrix-sketching-based anomaly detector. In
short, for a set of users U and items I, recommendation andupdate are done as Alg. 1 and Alg. 2, respectively. Here, mis the number of dimensions of a feature vector which represents an observed user-item interaction, and sketch size ℓ isa small integer. B is initialized by O ∈ Rm×ℓ . Meanwhile,Fig. 2 illustrates the whole procedure.
First, Alg. 1 follows a concept of anomaly scores introduced in [2]. When we have the orthonormal bases Uℓ derived from the past user-item interactions, the length of theorthogonal projection of a vector x′ui onto Uℓ (i.e. item
score) represents how much the vector is similar to the past
events; items which take smaller scores are more likely to berecommended.
Next, Alg. 2 updates a sketched matrix B as described in[4]. Since ℓ is a small integer, SVDℓ (B) can be eﬃciently
computed, and the procedure works well as an online algorithm. Tracking Uℓ is also important to compute scores in
the recommendation step.

./012*!*# .,%"*0&&%,,
23./012"!,# ()'%"0&'(#)('%/ % !
$%&'()'

839+!"# !"#$%&'(#)*+*,&#"()-.,%"$ % & ' "# "#( )!)*+ % ,$-./)+0 ,"#456# -70+'#!11 ('%/,!-# ,2%'&3*.!40'%

Figure 2: Overview of our new online item recommendation framework. In Alg. 1, (1) a recommender first createsa matrix X for the user-item pairs, and (2) top-N recommendation is launched based on the orthogonal projection. If (3) auser interacts with an item, Alg. 2 constructs a vector x′ui and (4) updates the orthonormal bases Uℓ by matrix sketching.
Algorithm 1 Recommend to a user u ∈ U ((1) in Fig. 1)
Input: Uℓ ∈ Rm×ℓ , Set of target items I ′ ⊆ I,
Recommendation size N
1: Create feature vectors xui ∈ Rm for every i ∈ I ′2: Normalize x′ui ← xui /∥x[ ui ∥]
3: Create a matrix X ← x′u1 , · · · , x′ui , · · · , x′u|I ′ |()′
4: A ← I − Uℓ UℓT X ∈ Rm×|I |5: Compute scores ai ← ∥A(:,i) ∥ for each column of A
6: Sort items i ∈ I ′ by ai in an ascending order
7: return Top-N items

Algorithm 2 Update for an interaction between u ∈ U andi ∈ I ((3) in Fig. 1)
Input: B ∈ Rm×ℓ
1: Create xui ∈ Rm for an observed (u, i) interaction
2: Normalize x′ui ← xui /∥xui ∥3: j ← index of the leftmost all-zero column in B
4: B(:,j) ← x′ui
5: [Uℓ , Σℓ , Vℓ ] (← SVDℓ (B)
)
√
√
√
2
6: Σ̂ℓ ← diagσ12 − σℓ2 , σ22 − σℓ2 , . . . , σℓ−1
− σℓ2 , 0
7: B ← Uℓ Σ̂ℓ8: return B, Uℓ

4.

EVALUATION

4.1

Experimental Setup

We consider three types of time-stamped datasets, Click,
ML100k and ML1M. Click is a synthetic dataset which contains randomly generated users’ impressions for five ad variants, following to a rule-based procedure introduced in [1].
ML100k is binalized MovieLens 100k data; only 5-starredrating events were extracted like [6]. ML1M is also binalizedversion of the MovieLens 1M data which behaves similarly toML100k, but larger than that. Each time-stamped dataset
was separated into three parts: 20% for batch training, 10%
for batch validation and 70% for incremental evaluation. Details of this evaluation procedure are explained in [3, 6].
Similarly to [3], xui was flexibly designed by concatenating as much as possible user, item and contextual featuresinstead of the user-item 2-dimensional data. As a result,m = 55 for Click, and m = 73 for ML100k and ML1M. We
also examine the following baselines:• Popularity is a non-personalized recommender which always recommends the most popular items as a reference.
• iMF1 [6] is an incremental variant of MF. This method
only uses the user-item 2-dimensional data.
• iFMs2 [3] are an incremental version of FMs. One-hotencoded user/item IDs are incorporated into xui .

4.2
Matrix sketching holds attractive properties [2, 4], andhence our online item recommender satisfies usability. Clearly,
item scores are always in a [0.0, 1.0] range as shown in
Alg. 1. In addition, we only have one simple hyperparameterℓ thanks to discussions about error bounds on FD; setting avery tiny integer to ℓ is suﬃcient. For instance,
Huang and√
Kasiviswanathan [2] simply used ℓ = m as a reasonablechoice.
In terms of parallelizability, Liberty [4] showed that, for
distributed sketch matrices B1 and B2 , they are successfully
mergeable by just sketching B ′ = [B1 , B2 ] ∈ Rm×2ℓ to B ∈Rm×ℓ . This fact also suggests that FD works well both onpurely online and mini-batch fashion; more than one vectors
can be sketched at once.
It should be noticed that a user-item interaction is represented by a feature vector xui in our framework. The simplest representation is concatenating quantitative variables
and one-hot-encoded categorical variables just like FMs [5],and pairwise feature representation as demonstrated in [1]is also available. In either case, the vectors can represent
not only user (item) features but also contextual variables
which describe a set of circumstances.

Results and Discussions

The author first examined whether our framework Sketch
outperforms state-of-the-art personalized recommenders,iMF√
and iFMs. We set ℓ = 1 for Click and ℓ = m = 8 forML100k and ML1M, and compared the results on recall@N
and mean percentile rank (MPR) as shown in Table 1. On
the Click data, Sketch showed the best accuracy both on recall@1 and MPR. In case of the MovieLens datasets, while
recall@10 was worse than iFMs on the smaller 100k data,
Sketch became much better than iFMs on the larger 1M
data. This results indicate that complex hyperparameters of
iFMs were rapidly unfitted as a result of online update, andSketch demonstrated more robust results as we expected. It
should be noted that, even though the accuracy of iMF was
consistently poor, its running time was much faster than thefeature-based recommenders. Here is a trade-oﬀ between accuracy and eﬃciency.
Remarkably, the popularity-based recommender was thebest on the MovieLens data. Thus, using item scores as apart of personalized/non-personalized hybrid recommenders1

λ = 0.01, η = 0.002, k = 40 for ML100k and ML1M, and λ = 0.01,
η = 0.0003, k = 2 for Click.
2
λ0 = 2.0, λw = 8.0, λVk = 16.0, η = 0.004, k = 40 for ML100k and
ML1M, and λ0 = λw = λVk = 0.01, η = 0.00006, k = 2 for ClickPopularity

Percentage of items

50

iMF

50

iFMs

50

Sketch (ours)

50

40

40

40

40

30

30

30

30

20

20

20

20

10

10

10

10

0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.900.0

gap (can be threshold)

0
50

100

150

200

250

300

350

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0
0.0

0.2

0.4

0.6

0.8

1.0

Top-1 score

Figure 3: Distributions of top-1 item scores for each method on ML100k. Top-N largest-scored items are recommended in Popularity, and the other methods recommend top-N smallest-scored items.

45

0.24

40

0.22

35

0.20

30

0.18

25

1

2

3

4

5

sketch size ℓ

6

7

0.6
0.4

Popularity
iMF
iFMs
Sketch (ours)

0.2
0.0
1

2

3

4

5

recall@10

0.26

recall

0.8
50

45

0.12

0.030

44

0.10

0.025

43

0.020

42

0.015

41

0.02

0.010

40

0.00

1

2

3

4

5

6

7

8

sketch size ℓrecommendation size

(ml-at)0.08

recall55

0.28(ml-ell)

0.035

1.0

MPR [%]

recall@1

0.30(click-at)

60

recallMPR

MPR [%](click-ell)

0.32

0.06
0.04

2

4

6

8

10

recommendation size

Figure 4: Relationship between accuracy and √hyperparameters. Higher recall@N and lower MPR are better on the
y-axis. (click-ell): Diﬀerent sketch size √from 1 to m = 7 on Click. (click-at): Diﬀerent recommendation size on Click.
(ml-ell): Diﬀerent sketch size from 1 to m = 8 on ML100k. (ml-at): Diﬀerent recommendation size on ML100k.

Table 1: Overall accuracy and running time. The best
personalized recommender’s accuracy is written in bold.
Method recall@N
MPR [%]
Avg. time [sec.]recommend
updateClick (@1)
Popular0.22089
37.62505––
iMF
0.27251
50.27011
0.00002 0.00003
iFMs
0.2961234.07363
0.00321 0.00026
Sketch
0.30092 27.29092
0.00190 0.00066
ML100k (@10)
Popular0.10538
17.10795––
iMF
0.0231840.91159
0.00017 0.00003
iFMs
0.03349 27.51833
0.02388 0.00142
Sketch
0.0300540.72182
0.00650 0.00039
ML1M (@10)
Popular0.08454
12.14989––
iMF
0.01249
42.18032
0.00061 0.00003
iFMs
0.01379 27.84364
0.30973 0.00605
Sketch
0.02451
37.67139
0.01626 0.00044

might be a requirement for getting more reasonable results.
In that sense, we are now interested in distribution of item
scores as illustrated in Fig. 3. Unlike the other methods,
Sketch showed a gap between 0.0 and 0.2. We can infer thatthe items placed where score < 0.1 are particularly close toa space spanned by Uℓ , and thresholding the scores leads ahybrid recommender. On the other hand, unnatural scoresof iMF and iFMs are not suggestive.
Finally, by using Click and ML100k, Fig. 4 demonstrates

accuracy of the various ℓ and cut-oﬀ @N to discuss limitations of the proposal. One thing we can observe is thatlarger ℓ does not always lead higher accuracy as shown in(ml-ell). Even though attractive properties of the sketching technique help us to find promising ℓ, extra eﬀort might
be necessary to achieve the best accuracy.

5.

CONCLUSION

This paper has proposed a matrix-sketching-based online
item recommender. The matrix sketching technique has
made the proposed framework highly usable and robust. In
the future, parallelizability need to be evaluated in a realistic parallel environment, and scalability and eﬃciency
should be improved from a practical point of view.

6.

REFERENCES[1] M. Aharon et al. OFF-Set: One-pass Factorization of
Feature Sets for Online Recommendation in Persistent Cold
Start Settings. In Proc. of RecSys 2013, pages 375–378, Oct.
2013.
[2] H. Huang and S. P. Kasiviswanathan. Streaming Anomaly
Detection Using Randomized Matrix Sketching. PVLDB,
9(3):192–203, Nov. 2015.
[3] T. Kitazawa. Incremental Factorization Machines for
Persistently Cold-Starting Online Item Recommendation.
arXiv:1607.02858 [cs.LG], July 2016.
[4] E. Liberty. Simple and Deterministic Matrix Sketching. In
Proc. of KDD 2013, pages 581–588, Aug. 2013.
[5] S. Rendle. Factorization Machines with libFM. ACM TIST,
3(3), May 2012.
[6] J. Vinagre et al. Fast Incremental Matrix Factorization for
Recommendation with Positive-only Feedback. In Proc. of
UMAP 2014, pages 459–470, July 2014.