# Evaluating Impact of User-Cluster Targeted Attacks in Matrix Factorisation
Recommenders

Sulthana Shams  Trinity College DublinIreland<EMAIL_ADDRESS>and  Douglas Leith
Trinity College DublinIreland<EMAIL_ADDRESS>
(2023)

###### Abstract.

In practice, users of a Recommender System (RS) fall into a few clusters based
on their preferences. In this work, we conduct a systematic study on user-
cluster targeted data poisoning attacks on Matrix Factorisation (MF) based RS,
where an adversary injects fake users with falsely crafted user-item feedback
to promote an item to a specific user cluster. We analyse how user and item
feature matrices change after data poisoning attacks and identify the factors
that influence the effectiveness of the attack on these feature matrices. We
demonstrate that the adversary can easily target specific user clusters with
minimal effort and that some items are more susceptible to attacks than
others. Our theoretical analysis has been validated by the experimental
results obtained from two real-world datasets. Our observations from the study
could serve as a motivating point to design a more robust RS.

Data Poisoning Attacks, Matrix Factorisation, Recommender Systems, User
Cluster Targeted Attacks

††copyright: acmcopyright††journalyear: 2023††doi: XXXXXXX.XXXXXXX††journal:
facmp††ccs: Information Systems Recommender systems

##  1\. Introduction

Recommender Systems (RS) have become increasingly important in recent years
due to the explosion of online data and the need for personalized
recommendations. They help users discover new products, services, or content
based on their interests and past behaviors, leading to increased engagement
and revenue for businesses.

Users in a RS can often be grouped by their interests, and indeed this
observation motivates many advertising strategies (Research and Ads, 2009;
Epasto et al., 2021; Xie and Phoha, 2001). Recent research proposes exploiting
such clustering of users in RS for their ’hiding in the crowd’ privacy
benefits (Checco et al., 2015; Research and Ads, 2009). However, it is well
known that RS are susceptible to data poisoning attacks (Lam and Riedl, 2004;
Patel et al., 2015). Social media platforms have received attention for
discriminatory and predatory targeting of user communities. Introducing false
product reviews and creating fake social media accounts to promote
misinformation are examples of how adversaries use RS to influence users. RS
recommends items by learning user’s preferences and contributes to shaping and
developing new opinions and interests, thus influencing user behavior.
Therefore, selective exposure to misinformation is a significant concern in
RS.

In poisoning attacks, an adversary adds fake profiles with carefully assigned
ratings for selected items and attempts to target an item to promote/demote it
by increasing/decreasing the item’s rating in the system. This study explores
the impact of data poisoning attacks targeting specific user clusters in
Matrix Factorisation (MF) based RS.

Given a RS with $n_{1}$ users and $n_{2}$ items, MF is a popular
recommendation technique that works by decomposing the original sparse user-
item interaction matrix $R\in\mathbb{R}^{n_{1}\times n_{2}}$ into two low-rank
matrices $U\in\mathbb{R}^{d\times n_{1}}$ and $V\in\mathbb{R}^{d\times n_{2}}$
where their row dimension $d$ is typically much less than $n_{1}$ and $n_{2}$
(Koren et al., 2009). This allows us to uncover latent features and the
association between users and items to these latent features in the $d$
dimensional latent space. The two low-rank matrices $U$ and $V$ associate a
user’s inclination towards the latent features and an item’s degree of
membership towards those latent features respectively. Their matrix product
$U^{T}V$ approximates $R$ and predicts the missing entries of the original
sparse matrix. We call $U$ the user-feature matrix and $V$ the item-feature
matrix. When fake ratings are introduced into a RS, the feature matrices $U,V$
undergo changes. It is crucial to analyse the nature and extent of these
changes to conduct further research on the robustness of MF-based RS. Our
study aims to investigate the impact of poisoning attacks on the feature
matrices $U$ and $V$, an aspect that has not been previously investigated in
the literature. In particular, we investigate attacks targeting specific user
groups and how the changes to $U$ and $V$ matrices enable these attacks.

The standard MF approach is to update both $U$ and $V$ matrices when new
ratings enter RS. To investigate how $U$ and $V$ are individually affected by
the attacks and how their behaviors contribute to the propagation of targeted
attacks in the RS, we consider updates to each matrix separately in response
to the newly entered fake ratings (Shams and Leith, 2022), i.e. i) Hold $V$
constant and update $U$ to study the changes to $U$ after attacks, ii) Hold
$U$ constant and update $V$ to study the changes to $V$ after attacks. Our
findings indicate that the impact of the attack is pronounced when $V$ is
updated in response to the introduction of fake ratings.

The effectiveness of attacks on feature matrices can be influenced by the
choice of target items. Most work in the literature (Wu et al., 2021; Fang et
al., 2020, 2018; Huang et al., 2021; Christakopoulou and Banerjee, 2019; Hu et
al., 2019) studies the effect of attacks on randomly chosen target items or on
items with a small number of ratings. In this paper, we take a broader view
and consider various choices of target item to identify the factors
contributing to attack effectiveness on the $U,V$ matrices by analyzing how
these matrices change after an attack on these target items. We conclude that
certain items are more susceptible to attacks than others. Specifically, we
have found that items with a lower number of ratings in the target cluster are
particularly vulnerable. This is because the feature vectors for these items
in matrix $V$ can be easily manipulated, making them more susceptible to
attacks. So the distribution of user and item latent features plays a
significant role in the effectiveness of attacks targeting a user group.

Many recent works approach data poisoning attacks from an optimization
perspective, requiring a high level of knowledge about the RS (Fang et al.,
2020; Christakopoulou and Banerjee, 2019; Lin et al., 2020). For our work, we
revisit more straightforward attack strategies (Lam and Riedl, 2004; Patel et
al., 2015; Mingdan and Li, 2020) involving users rating the target item with a
large rating to promote it and the rest of the items (filler items) with
scores that mimic the rating distribution of the targeted user cluster. We
show that this low-knowledge attack is enough to promote an item in a target
cluster.

Our main contributions are as follows:

  * •

We provide a systematic study of data poisoning attacks targeted at a group of
users and identify the factors contributing to the effectiveness of attacks in
MF-based RS.

  * •

We analyse the individual effects of attacks on latent feature matrices $U$
and $V$ and explore how they contribute to the propagation of targeted attacks
in a MF-based RS. Studies investigating the role of latent feature matrices
are new to the literature.

  * •

We illustrate our findings with real-world datasets and show that a simple
attack strategy using limited knowledge of user preferences suffices to target
a specific user group precisely.

##  2\. Related Work

The benefits of clustering users in RS are discussed in (Checco et al., 2015;
Shams et al., 2021; Yanxiang et al., 2013; Mittal et al., 2010). For example,
(Checco et al., 2015) proposes enhancing privacy by assigning the users to
clusters and providing cluster-wise recommendations rather than for each
individual user and (Shams et al., 2021; Yanxiang et al., 2013) exploits user
clusters for improving cold-start recommendation. Recently Google introduced a
new algorithm (Research and Ads, 2009) which uses such clustering of users.
Known as Federated Learning of Cohorts, or FLoC, it assigns individual
browsers to larger groups of users based on their browsing history to enable
privacy-oriented personal recommendations. FloC allows a form of “hiding in
the crowd” privacy.

The impact of data poisoning attacks where fake users are injected in RS with
carefully crafted user-item interaction has been studied extensively. For
surveys on attack models and the robustness of RS algorithms, see (Lam and
Riedl, 2004; Patel et al., 2015; Mobasher et al., 2007; Mingdan and Li, 2020).
Studies such as (Huang et al., 2021; Li et al., 2016; Fang et al., 2018, 2020)
focus on modelling attacks specific to the type of RS, e.g. (Fang et al.,
2020) studies attacks in MF-based RS by proposing to model fake users similar
to true users who are influential to the recommendations, (Huang et al., 2021;
Fang et al., 2018) propose data poisoning attacks for deep learning based RS
and graph-based RS respectively.

Very few studies explore the impact of data poisoning attacks targeting
specific user clusters in MF-based RS. The closest work to the present paper
is probably (Hu et al., 2019; Christakopoulou and Banerjee, 2019). In
(Christakopoulou and Banerjee, 2019), Generative Adversarial Networks (GAN)
generate fake users whose distribution is close to that of the true users.
They assume that the adversary has knowledge of the recommender’s model and
algorithm and aims at adversarial training of RS to build robust
recommendation models (for other adversarial robustness studies, see
(Christakopoulou and Banerjee, 2019; Xu et al., 2020; Deldjoo et al., 2020)).
In (Hu et al., 2019), they propose to promote an item to a group of users by
injecting fake ratings and social connections in a factorisation-based social
RS. They assume that fake users can quickly establish social connections with
true users and model the attack as a bi-level optimisation problem.

In the above studies, attacks are modeled as an optimisation problem. They
require a good deal of information about the RS to be carried out, i.e. a
rather powerful adversary. However, observations from these studies motivate
us to revisit the more straightforward average-attack strategy and study their
effect on MF-based RS. For example, in (Fang et al., 2018), the attacker
generates fake users using a graph-based RS, and the target RS uses MF. The
differences between their attack and the existing standard attack strategies
are not very large despite the high level of knowledge assumed by the
adversary. Similar observations are made in (Lin et al., 2020), where the
authors study data poisoning attacks on deep learning RS models. They generate
fake profiles by randomly sampling a sub-matrix from real users who have rated
sufficient items to generate fake users close in distribution to the real
users. They compare their attack strategy to standard attack models such as a
random attack, average attack etc, and find that the effectiveness of the
attack is only marginally increased compared to the lower knowledge and
simpler average-attack strategy.

##  3\. User-Cluster Targeted Poisoning Attack

###  3.1. User Cluster Based Recommendation Model

In an MF-based recommender, the user-item rating matrix $R$ is first
factorized approximately as $U^{T}V$, where matrices $U$ and $V$ have
relatively small inner dimension $d$. Each column in matrix $U$ is a length
$d$ weight vector that captures a user’s preferences, and each column in
matrix $V$ is a length $d$ weight vector that captures the characteristics of
one item. The predicted rating matrix given by the inner product $U^{T}V$
gives the individual predicted rating per user per item.

We depart from the usual setup by assuming that users belong to distinct
groups. We have a set $\mathcal{G}$ of user groups, and each user belongs to
one group $g\in\mathcal{G}$ such that users belonging to a group have similar
preferences. In our study, we use $k$-means to cluster columns of matrix $U$
so that users with similar preferences (i.e. weight vectors) are clustered
together. However, other clustering algorithms might also be used, e.g. the
approach in (Checco et al., 2015).

Let $\tilde{U}_{g}\in\mathbb{R}^{d\times 1}$ for $g=1,\cdots,|\mathcal{G}|$ be
the preference vector associated with a group of users and gather these
features to form matrix $\tilde{U}\in\mathbb{R}^{d\times|\mathcal{G}|}$. Each
column in $\tilde{U}$ is a length $d$ weight vector that captures a group’s
preferences. For users belonging to a group $g$ with weight vector
$\tilde{U_{g}}$ and items with weight vectors in $V$, the predicted rating
matrix is the inner product $\tilde{U_{g}}^{T}V$, i.e., users belonging to the
same group have the same predicted rating value per item.

###  3.2. Attack Model

We assume that the adversary knows the cluster-wise mean rating for every item
in the system. This is a reasonable assumption since such cluster-wise
information may be inferred from online databases that publicly display the
average user ratings of items and metadata such as user’s age, gender, etc.
(e.g., movie databases, online shopping databases, etc.).

For the type of attacks that we focus on, there is a _target item_ that the
attacker is interested in promoting in a target cluster and a set of _filler
items_ that are rated to ensure that the fake users preferences share some
similarity to that of the true users in the target cluster. The target item is
given the maximum rating to try to promote it in the system and the filler
items ensure that fake users can correctly enter the targeted group.

##  4\. Study of Attack Effects on Feature Matrices $U$ and $V$

The standard approach to obtain $U,V$ given user-item ratings is to minimize
the sum of squared error over the set of all observed ratings, i.e.

(1)
$\min_{U,V}\sum_{(i,j)\in\mathcal{O}}(R_{i,j}-U_{i}^{T}V_{j})^{2}+\lambda\left(\sum_{i}\lVert
U_{i}\rVert^{2}+\sum_{j}\lVert V_{j}\rVert^{2}\right)$

Where $\mathcal{O}$ is the set of (user, item) rating pairs, $R_{i,j}$ is the
rating of item $j$ by user $i$, $U_{i}$ and $V_{j}$ are the column vectors
that describe the preferences associated to user $i$ and item $j$
respectively; $\lVert.\rVert$ is the Euclidean norm and $\lambda$ is a
regularisation weight. We re-cluster these $U_{i}$ values to obtain matrix
$\tilde{U}$ of group vectors.

When fake users arrive and start rating items, we study changes in $U,V$ by
updating only one of the feature matrices in response to newly entered ratings
and keeping the other constant. In particular, we have the following
approaches to incorporate the new ratings:

  1. (1)

Fix $V$, update $U$:  RS holds $V$ constant and updates $U$ for all users
after the attack. Keeping V constant, the cost function in equation 1, becomes
for every user $i$, a convex function of $V$. The solution to this least
squares problem is

(2) $\displaystyle U_{i}$
$\displaystyle=\left(\sum_{j\in\mathcal{V}(i)}{V_{j}V_{j}^{T}+\lambda
I}\right)^{-1}\sum_{j\in\mathcal{V}(i)}V_{j}R_{i,j}$

where $\mathcal{V}(i)=\\{j:(i,j)\in\mathcal{O}\\}$ is the set of items rated
by user $i$. Then re-cluster the $U_{i}$ values to obtain an updated matrix
$\tilde{U}$ of group vectors.

  2. (2)

Fix $U$, update $V$:  RS holds $U$ constant and updates $V$ after the attack.

(3) $\displaystyle V_{j}$
$\displaystyle=\left(\sum_{i\in\mathcal{U}(j)}{U_{i}U_{i}^{T}+\lambda
I}\right)^{-1}\sum_{i\in\mathcal{U}(j)}U_{i}R_{i,j}$

where $\mathcal{U}(j)=\\{i:(i,j)\in\mathcal{O}\\}$ is the set of users rating
item $j$.

###  4.1. Fix $V$, Update $U$

It can be seen from equation 2 that user vector $U_{i}$ depends on the item
vector $V_{j}$ and rating value $R_{i,j}$ of all items $j\in\mathcal{V}(i)$
rated by user $i$. For any existing true user $i$ in RS, the addition of fake
users neither changes the set $\mathcal{V}(i)$ of items rated nor $R_{i,j}$
and $V_{j}$ of items in $\mathcal{V}(i)$. So the weight vector $U_{i}$ is
unchanged after an update provided $V$ is kept constant.

Let $U_{f}$ be the feature vector of a fake user $f$ entering the RS. $U_{f}$
is generated based on the set of items $\mathcal{V}(f)$ rated by the fake user
and the ratings given to these. After generating $U_{i}$ values for all users
(now includes fake users as well), the cluster-feature weights $\tilde{U}$ are
updated using k-means. We also warm start the $k$-means clustering with the
initial centers before the attack instead of using a random cluster center
initialization. This allows us to focus on regrouping due to adding fake users
and avoid spurious group membership changes due to randomness in the initial
conditions.

####  4.1.1. Impact of Attack on Target Cluster Weight Vector $\tilde{U}_{t}$

The new cluster center is the arithmetic mean of all user weights in the
cluster. When fake users successfully enter the target cluster $t$ by
generating feature vectors $U_{f}$ that are close to $\tilde{U}_{t}$, we
update the cluster center to reflect the presence of these new users. The
updated $\tilde{U}_{t}$ is the mean of the feature vectors of the existing
true users and the newly added fake users. Therefore the predicted rating of
target item $j^{*}$ in the target cluster given by
$\tilde{U}_{t}^{T}V_{j^{*}}$ changes. Therefore, the effect of the attack on
item $j^{*}$, in this case, is determined by the changes to the cluster center
$\tilde{U}_{t}$ resulting from the inclusion of fake user weights. Based on
this understanding, we expect the relative number of true users ($n$) and fake
users ($m$) in the target cluster to play an essential role in the
effectiveness of the attack. If $n>>m$, then the impact of fake users on the
arithmetic mean $\tilde{U}_{t}$ is small.

####  4.1.2. Impact of Attack on Non-Target Items and Non-Target Clusters

The inner product $\tilde{U_{t}}^{T}V$ gives the predicted rating for all
items in the target cluster. Specifically, we expect that, in the target
cluster, items similar to $j^{*}$ (i.e: item feature vectors $V_{j}$ and
$V_{j^{*}}$ have high correlation) will show a more significant change in the
predicted ratings. In contrast, other items will show a lower change in the
predicted ratings.

Recall that any true user’s feature vector remains unchanged after injecting
fake users in RS. So we expect non-target cluster center $\tilde{U}_{g}$ for
$g\in\mathcal{G}\setminus\\{t\\}$ to be unchanged if all fake users correctly
enter target cluster $t$. Thus, keeping $V$ constant will isolate the attack
effects on the target cluster alone if all fake users enter the target
cluster.

####

Surprisingly, our analysis shows us that the injection of fake ratings has no
effect on the user vector $U_{i}$ of all true users $i$ in the RS (when $V$ is
kept constant). Also, the number of true users in target cluster $t$ relative
to the number of fake users determines the attack’s effect on $\tilde{U}_{t}$.
It is $V_{j^{*}}$ that changes in response to injected fake ratings. Further,
the post-attack changes are influenced by the number of true ratings to item
$j^{*}$ from the target cluster rather than the total number of true users in
the target cluster. We will study this in detail in the next section.

###  4.2. Fix $U$, Update $V$

It can be seen from equation 3 that a target item vector $V_{j*}$ depends on
user vector $U_{i}$ and rating $R_{i,j^{*}}$ of all users $i$ in set
$\mathcal{U}(j^{*})$ who provide rating to the item $j^{*}$. $V_{j^{*}}$
remains unaffected by the number of users in a cluster unless they also
provide a rating to item $j^{*}$.

Let a fake user $f$ enter RS targeting item $j^{*}$. This implies that the set
$\mathcal{U}(j^{*})$ of users now also contains the fake users. Following
this, fake user feature vector $U_{f}$ and rating $R_{f,j^{*}}$ are also used
to determine $V_{j^{*}}$. Therefore, target item vector $V_{j^{*}}$ will show
significant changes after the attack when many fake users enter RS.

####  4.2.1. Impact of Attack on Target Item Vector $V_{j^{*}}$

Let $\hat{V_{j^{*}}}$ be the updated $V_{j^{*}}$ after attack. Given the
$k^{th}$ item-feature of $V_{j^{*}}$ represented by $v^{j^{*}}_{k}$ and
$k^{th}$ user-feature of $\tilde{U}_{t}$ represented by $u^{t}_{k}$, the
change in target item predicted rating in the target cluster after the attack,
for this setup, is

$\tilde{U_{t}}^{T}\hat{V}_{j^{*}}-\tilde{U_{t}}^{T}V_{j^{*}}=\sum_{k=1}^{d}u^{t}_{k}(\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k})$

The change in predicted rating will increase when
$\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}=\gamma u^{t}_{k}$ for a positive constant
$\gamma$. This is because, the inner product will then become
$\sum_{k=1}^{d}u^{t}_{k}(\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k})=\sum_{k=1}^{d}\gamma(u^{t}_{k})^{2}$.
We can see that, as $\gamma$ increases, product terms in the inner product
become larger and positive, increasing the change in the predicted rating of
the target item. Specifically, we define the following setup to study the
transformation of $V_{j^{*}}$. We noted from equation 3 that updating
$V_{j^{*}}$ after the attack requires the $U_{i}$ values corresponding to all
users who have provided ratings, i.e., true users and newly added $m$ fake
users. Since users in a group have similar preferences, we set the $U_{i}$
values of true users to their corresponding cluster weight vector for this
study. Given vector $U_{f}\in\mathbb{R}^{d\times 1}$ associated with fake user
$f$ capturing the fake user’s preferences, we gather these vectors together to
form matrix $X\in\mathbb{R}^{d\times m}$. To improve the predicted rating of
the target item in the target cluster $t$, columns in the $X$ matrix must be
closer to $\tilde{U}_{t}$ than to other cluster feature vectors. For maximum
changes to $V_{j^{*}}$, which corresponds to the maximum change in the
predicted rating of the target item, we set $U_{f}$ equal to $\tilde{U}_{t}$
in our analysis. We re-write equation 3 such that after adding a block of $m$
fake users, we can formulate updates to $V_{j^{*}}$ recursively.

###### Theorem 1 (Proof in Appendix).

Given $\hat{V_{j^{*}}}$ is the updated $V_{j^{*}}$ after attack. Let a block
of $m$ fake users with feature vectors in $X\in\mathbb{R}^{d\times m}$ and
target item fake ratings vector $y\in\mathcal{R}^{m\times 1}$ enter RS. Given
$A^{-1}=\left(\sum_{i\in\mathcal{U}(j^{*})}U_{i}U_{i}^{T}+\lambda
I\right)^{-1}$ for set of all true users $\mathcal{U}(j^{*})$ rating item
$j^{*}$ and $K=\left(I+X^{T}A^{-1}X\right)^{-1}\left(y-X^{T}V_{j^{*}}\right)$,
we can write,

(4) $\displaystyle\hat{V_{j*}}-V_{j*}$ $\displaystyle=m\times
K\times\left(A^{-1}\tilde{U}_{t}\right)$

#### Analysis of Vector $V_{j^{*}}$ Update Mechanism

Using equation 4, for any $k^{th}$ item-feature of $V_{j^{*}}$ given by
$v^{j^{*}}_{k}$ and $k^{th}$ user-feature of $\tilde{U}_{t}$ given by
$u^{t}_{k}$, we can write the updated $k^{th}$ item-feature
$\hat{v}^{j^{*}}_{k}$ of $\hat{V}_{j^{*}}$ as

(5) $\displaystyle\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}$ $\displaystyle=m\times
K\left(a_{kk}u^{t}_{k}+\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}\right)$

where $a_{kk}$ represents the diagonal and $a_{ki}\text{ for }\\{i\mid i\neq
k\text{ and }i\in 1,2,\cdots,d\\}$ represents non-diagonal elements in the
$k^{th}$ row of matrix $A^{-1}$. We can clearly observe from equation 5 that
$\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}$ is not a simple scaling of $u^{t}_{k}$ due
to the presence of the second summation term. Therefore the transformation to
any feature $v_{k}$ depends on the matrix $A^{-1}$ and target cluster-feature
vector $\tilde{U}_{t}$.

We know that $A^{-1}$ is a Positive Definite (PD) matrix. 111See Appendix C.1
Thus all diagonal elements $a_{kk}$ are positive.222See Lemma 4 in Appendix
From this we can say that the term $a_{kk}u^{t}_{k}$ always has the sign of
$u^{t}_{k}$ or in other words scales $u^{t}_{k}$. Equation 5 reduces to a
simple scaling of $u^{t}_{k}$ only when $A^{-1}$ is a positive diagonal matrix
causing the non-diagonal terms in any row of $A^{-1}$ to be zero i.e. the
summation term $\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}$ in equation 5 becomes
zero giving $\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}=m\times K\times a_{kk}\times
u^{t}_{k}$.

Let’s take a closer look at the possible behaviors of equation 5 for any
$k^{th}$ feature in item vector $V_{j}$. We know that $m,K$ are positive
constants. So the overall sign and magnitude of the update is determined by
the behaviour of term $a_{kk}u^{t}_{k}+\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}$.
We noted how $a_{kk}u^{t}_{k}$ is a term always having the sign of
$u^{t}_{k}$, effectively acting as a scaling of $u^{t}_{k}$. Depending on the
sign and magnitude of the term $\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}$
relative to $a_{kk}u^{t}_{k}$, we can have the following behaviours:

  * •

case 1: if $sgn(a_{kk}u^{t}_{k})=sgn(\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i})$:
then the update factor in equation 5 is similar to scaling $u^{t}_{k}$. i.e we
could say $\hat{v}_{k}-v_{k}=\gamma u^{t}_{k}$ where $\gamma$ is a positive
constant.

  * •

case 2: if $sgn(a_{kk}u^{t}_{k})\neq sgn(\sum_{i=1,i\neq
k}^{d}a_{ki}u^{t}_{i})$: then,

    * –

case 2a): $|a_{kk}u^{t}_{k}|>|\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}|$ then
here too the update factor in equation 5 is similar to scaling of $u^{t}_{k}$.
i.e. we could say $\hat{v}_{k}-v_{k}=\gamma u^{t}_{k}$ where $\gamma$ is a
positive constant.

    * –

case 2b): $|a_{kk}u^{t}_{k}|<|\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}|$, then
here the update factor is such that it shifts opposite to $sgn(u^{t}_{k})$.

    * –

case 2c): $|a_{kk}u^{t}_{k}|=|\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}|$, then
$\hat{v}_{k}-v_{k}=m\times K\times 0=0$ implying
$\hat{v}^{j^{*}}_{k}=v^{j^{*}}_{k}$, thus no change in the feature $k$ after
attack.

In particular, when target item true rating distribution possess certain
structures, we have the following key observations regarding the relative
signs and magnitudes of $a_{kk}u^{t}_{k}$ and $\sum_{i=1,i\neq
k}^{d}a_{ki}u^{t}_{i}$. Further we show that equation 5 is convergent under
certain conditions.

#### 1) $|a_{kk}u^{t}_{k}|$ reduces as the number of true ratings to target
item increases:

If we look at the term
$A^{-1}=(\sum_{i\in\mathcal{U}(j^{*})}U_{i}U_{i}^{T}+\lambda I)^{-1}$, we can
write using Sherman-Morrison-Woodbury identity 333See Definition 2 in Appendix
that for every new true user $\hat{i}$ with feature vector $U_{\hat{i}}$
providing ratings to item $j^{*}$, the inverse is updated such that

$\hat{A}^{-1}=(A+U_{\hat{i}}U_{\hat{i}}^{T})^{-1}=A^{-1}-\frac{A^{-1}U_{\hat{i}}U_{\hat{i}}^{T}A^{-1}}{1+U_{\hat{i}}A^{-1}U_{\hat{i}}^{T}}$

From lemma 5 444See Lemma 5 in Appendix, the diagonal elements of updated
inverse $\hat{A}^{-1}$ is always less than or equal to the diagonal elements
of $A^{-1}$. This implies that as more true user provides ratings, diagonal
values of $A^{-1}$ decrease. i.e., term $|a_{kk}u^{t}_{k}|$ reduces as the
number of true ratings to the target item increases.

#### 2) $sgn(a_{ki}u^{t}_{i})$ relative to $sgn(a_{kk}u^{t}_{k})$:

By lemma 10 555See Lemma 10 in Appendix, we have that if true ratings to item
$j^{*}$ come exclusively from target cluster users, each term
$a_{ki}u^{t}_{i}$ in the summation has a sign opposite to
$sgn(a_{kk}u^{t}_{k})$. Conversely, if the source of true ratings is not
exclusive to the target cluster, then the sign of each term $a_{ki}u^{t}_{i}$
in the summation does not depend exclusively on $sgn(a_{kk}u^{t}_{k})$ and may
not all be the same.

#### 3) Convergence of $A^{-1}\tilde{U}_{t}$

Suppose item $j^{*}$ received a large number of true ratings from true users
in RS. Will $V_{j^{*}}$ prove difficult to change after the attack? From case
$2c$, we can see that magnitude of updates to the item vector after an attack
is reduced only if $A^{-1}\tilde{U}_{t}$ approaches zero vector. In
particular, we have

###### Theorem 2 (Proof in Appendix).

Given $A^{-1}$, let $N$ true ratings be received by target item such that
$A^{-1}$ updates to $\hat{A}^{-1}$. Then column vector
$\hat{A}^{-1}\tilde{U}_{t}$ is guaranteed to converge to zero vector as $N$
approaches infinity only if the $N$ ratings come from the target cluster. For
increasing true ratings from any non-target cluster, convergence to zero is
not guaranteed.

Thus if fewer users from the target cluster provide ratings to item $j^{*}$,
then irrespective of the number of ratings from non-target clusters,
$V_{j^{*}}$ may not be immune to changes from attack. So we expect the
effectiveness of the attack to depend on the number and cluster-wise
distribution of true ratings to the target item. $V_{j^{*}}$ is guaranteed to
be protected from attack only when the target cluster provides a large number
of true ratings to the item $j^{*}$.

####  4.2.2. Impact of Attack on Non-Target Clusters and Non-Target Items:

From our analysis of equation 3, we expect that non-target items in a cluster
will not be affected after an attack. This is because the target item’s
$V_{j^{*}}$ is updated independent of $V_{j}$ for all items $j\neq j^{*}$,
thus changes to $V_{j^{*}}$ after the attack does not affect any $V_{j}$.
Attack effects leak to non-target item vectors only via changes to
$\tilde{U_{t}}$ as discussed in section 4.1.2. But, since $\tilde{U}$ is kept
constant, post-attack changes are only isolated to the target item.

The predicted rating of target item $j^{*}$ across all clusters is calculated
by $\tilde{U}^{T}V_{j^{*}}$. Thus item vector $V_{j^{*}}$ is common to all the
cluster weight vectors in $\tilde{U}$. This implies that changes to the item
vector affect all clusters. For example, suppose true users have $U=[1,-1]$ or
$U=[-1,1]$. i.e. the first set of users like items with $V=[1,0]$ and dislike
items with $V=[0,1]$, but the second set of users are the opposite. Then an
attack against the first set of true users keeping $U=[1,-1]$ constant to
increase the rating of an item with $V=[0,1]$ may be performed by shifting
$V=[0,1]$ to $V[1,0]$. Then such a shift, while it increases the rating in
users with $U=[1,-1]$, would decrease the rating in group $U=[-1,1]$.

But based on observations from real-world datasets in section 6, cluster
weight vectors are rarely so simple and opposite in preference values. In
fact, with higher $d$ dimensional feature space, the cluster preference
vectors enjoy correlation. For example, in table 1a, features $k=0,3,4,5,6,7$
have the same sign across all clusters. Similar observations can be made for
the Goodreads dataset in table 1b for features $k=0,2,4,6,8,9$. Thus these
features of clusters are positively correlated. In table 1b, feature $k=1$ has
a negative sign in cluster $2$ but is positive in all non-target clusters.
Thus this feature is negatively correlated with corresponding features of
clusters $g=0,1,3$. Similarly, many such features exist in both datasets, with
opposite signs between clusters.

g/k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
0 | 0.54 | 0.06 | 0.03 | 0.06 | 0.63 | -0.43 | 0.29 | -0.25 | 0.45 | -0.01
1 | 0.45 | -0.16 | 0.25 | 0.29 | 0.88 | -0.09 | 0.29 | -0.21 | -0.22 | -0.11
2 | 0.71 | 0.61 | -0.13 | 0.08 | 0.63 | -0.04 | 0.18 | -0.01 | -0.12 | -0.13
3 | 0.30 | -0.08 | -0.46 | 0.20 | 0.81 | -0.36 | 0.60 | -0.04 | -0.17 | -0.34

(a) ML

g/k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
0 | -0.14 | 0.28 | -0.18 | 0.26 | -0.53 | -0.17 | -0.35 | 0.03 | -0.15 | -0.63
1 | -0.24 | 0.47 | -0.14 | 0.29 | -0.08 | -0.09 | -0.48 | 0.04 | -0.57 | -0.26
2 | -0.11 | -0.22 | -0.47 | 0.42 | -0.53 | -0.19 | -0.47 | 0.26 | -0.30 | -0.10
3 | -0.06 | 0.21 | -0.16 | -0.16 | -0.61 | 0.11 | -0.67 | -0.10 | -0.19 | -0.14

(b) GR

Table 1. Cluster-Weight Values for $d=10$ features against $|G|=4$ clusters
for Movielens (ML) and Goodreads (GR) datasets

We expect that in such correlated clusters, after attack, the effect leaks to
non-target clusters as well. While the relative change in rating increases in
the target cluster, for non-target clusters, the relative change in rating may
increase or decrease after attack depending on their weight vector
$\tilde{U}_{g}$ and correlation with updated target item vector
$\hat{V}_{j^{*}}$.

##  5\. Experiment Evaluation Set-up

To illustrate our findings discussed in previous sections, we describe the
experimental set-up and report the results in section 6.

###  5.1. Datasets

We evaluate the effectiveness of the attack on the MovieLens dataset (943
users rating 1682 movies, contains 100000 ratings from 1-5), widely used in
literature for evaluating RS under attack, and the Goodreads 10K dataset
(53,424 people rating 10,000 books, 5.9M ratings from 1-5). We take a dense
subset of the Goodreads dataset (since MF is computationally expensive for
large datasets), obtained by selecting the top 1000 users who have provided
the most ratings and the top 1682 items rated by these users. This provides us
with 1000 users and 1682 items.

####  5.1.1.  Synthetic User Generation

We evaluate by generating synthetic users using Movielens and Goodreads as a
baseline where, by construction, the setup considered in this section is
intentionally tightly controlled so that we can vary one aspect at a time and
study its impact.

From the original R matrix of the two datasets considered, calculate $U,V$,
and cluster $U$ using k-means to get group membership of all users. For users
in each group, calculate the empirical distribution of the ratings for each
item. Using this mean and variance of the item ratings for a group $g$,
generate the required number of users per group by drawing a vector of random
ratings for items, i.e., for item $j$ generate a random variable with the
probability of each rating being given by the empirical distribution
previously calculated for group $g$, item $j$. Notably, we generate ratings so
that the proportion of ratings from group $g$ for each item $j$ matches that
in the original Movielens and Goodreads dataset. For example, if an item $j$
received ratings from $10\%$ of the users from cluster $g$ in the original
dataset and if we generated $1000$ users per cluster, then we ensure that the
item $j$ also receives ratings from $10\%$ of users from cluster $g$ ($=100$
ratings) in this generated dataset. For a target item, the number and
distribution of ratings per group are completely controlled while leaving the
distribution of ratings for other items much the same as before. This also has
the advantage that we can easily generate large numbers of new users cleanly
and reproducibly.

For our study, we generate $4$ clusters (results are similar for any number of
clusters chosen, but a cluster size of 4 gives a larger sample set of target
items with required empirical mean in a target cluster) with latent feature
space of dimension $d=10$ and a number of items of $1682$ for both datasets.
Note that there must be at least $250$ users per cluster. This is because too
few users cause fewer ratings to be generated per cluster according to our
set-up described. Lack of sufficient ratings per cluster causes the centers of
the generated clusters to shift from the original centers. This may cause the
membership of generated users to change. So unless mentioned otherwise, for
all our simulation studies, we fix the cluster-wise population to be $250$ per
cluster. The results reported are the average of over $50$ such datasets
generated randomly as described using Movielens and Goodreads as the baseline.

###  5.2. Threat Model

####  5.2.1. Target Item

The target item is given the maximum rating to try to promote it in the
system. Specifically, in our experiments, we randomly sample an item from a
set of items with an empirical mean rating $\leq 3$ and treat it as the target
item. The number and distribution of ratings per cluster are completely
controlled for the chosen target item, as detailed in Section 5.1.1. We thus
evaluate our results for different target items based on the number of true
ratings it has.

####  5.2.2. Filler Items

The filler items are chosen to aid fake users in correctly entering the target
cluster. We rate filler items such that the columns in the $U$ matrix
corresponding to the fake users are closer to those of users in the target
cluster than those in others. Randomly choosing items may risk the fake user
falling into a non-target cluster. So we choose those that are likely to be
favored by the users of the target group. Thus we choose so-called
distinguisher items (Shams et al., 2021) as filler items. Specifically, we
choose distinguisher items identified in a cluster with i) mean rating very
different and higher from other clusters and ii) the ratings tend to be
consistent/reliable, i.e., the variance is small. These ’popular’ items in the
target cluster can make fake user profiles more realistic and representative
of the target cluster user’s preferences. Also, too low a number of filler
items makes it difficult for fake users to enter the target cluster correctly.
So, we fix the number of filler items to be the minimum number of items rated
by true users in the generated data set. The ratings for these filler items
are sampled from the Gaussian distribution using the cluster-wise mean rating
and a small standard deviation.

In Figure 1 we see the percentage of fake users entering the target cluster
for our choice of distinguisher filler items. We can observe $>=90\%$ of fake
users correctly entering the target cluster. Thus the fake users simulate the
preferences of target cluster users accurately.

(a) g=0 (b) g=1 (c) g=2 (d) g=3 (e) g=0 (f) g=1 (g) g=2

(h) g=3

Figure 1. Plot showing the percentage of fake users entering per cluster when
targeting each cluster $g$ for ML and GR Datasets respectively using
distinguisher filler items

###  5.3. Performance Metric

We use the change in the rating of the target item relative to the maximum
deviation possible as our evaluation metric.

(6) $\displaystyle\text{Relative Change in
Rating}_{g}=\frac{\mu_{f}(g,i)-\mu_{o}(g,i)}{|5-\mu_{o}(g,i)|}$

Where $\mu_{f}(u,i)$ is the predicted rating of target item $i$ of a user in
cluster $g$ after the attack, $\mu_{o}(g,i)$ is the predicted rating of the
target item $i$ of a user in cluster $g$ before the attack and 5 is the
maximum rating that can be given to the target item in the datasets that we
consider.

We note that it is common in the literature to measure the effectiveness of an
attack using either Hit-Rate (HR@N), i.e., the fraction of normal users whose
top-N recommendation lists contain the target item, or Prediction Shift (PS),
i.e., the difference in the rating of the item before and after the attack
indicating by how much the rating has increased after the attack. While the PS
metric illustrates whether an attack has the intended effect of increasing
rating, it does not measure the attack’s power. Thus many studies use HR@N to
measure the effectiveness of the attack.

However, in a cluster-based RS, the top $N$ list is common to all users in a
cluster. Further, the items in the top $N$ list are RS dependent varying over
many factors, such as the threshold rating considered above which it may be
put in a recommended list, and the percentage of users who already interacted
with that item in the cluster. Since our study considers different target
items based on the number of true ratings they received, the standard Hit-
Ratio is not an ideal evaluation method for us. 666However, we report results
for a slightly modified hit-rate definition as an additional result in
Appendix

Equation (6) gives the shift in predicted rating relative to the maximum
deviation possible after an attack. It therefore directly measures the power
of attack on clusters.

###  5.4. Visualising Results

In each study, we average our results over 50 generated datasets and attack
each of these to allow us to study variability in the effectiveness of the
attack. We then use the mean and standard deviation to visualize the relative
change in the rating of the target item after the attack. We show the results
when the adversary targets cluster 2. Results when targeting other clusters
are similar and so not reported separately.

##  6\. Performance Illustration with Data

Recalculate $U,V$ for the generated user-item ratings in each iteration. This
becomes the baseline $U,V$ against which we measure the changes after the
attack. Inject fake users and perform update approaches $1$ and $2$
respectively as discussed in Section 4. Recall we use a warm start approach
when performing updates to $U,V$ and for k-means clustering.

###  6.1. Fix $V$, update $\tilde{U}$

Before we proceed to show the results illustrating our findings, let us
briefly recall our key observations of approach $1$ from Section 4.1:

  * •

Relative number of true and fake users plays a role in the effectiveness of
the attack. Increasing the number of true users in the target cluster reduces
changes to $\tilde{U}_{t}$ and subsequently the effect of targeted attacks.

  * •

The effect of the attack is isolated to the target cluster when all fake users
correctly enter the target cluster. Also, changes to $\tilde{U}_{t}$ result in
’leakage’ of attack to non-target items. The effect of the attack is expected
to be pronounced in items highly correlated to the target item.

We first illustrate the attack’s impact when the target cluster’s true user
size is increased relative to the fake user size in Section 6.1.1. We then
proceed to illustrate the leakage effect of attack to non-target items and
clusters in Section 6.1.2.

####  6.1.1. Varying Ratio of True Users (n) to Fake Users (m) in Target
Cluster:

In this experiment, we compare the relative change in target item predicted
rating in the target cluster for varying values of ratio $\frac{n}{m}$. We fix
the number of target-item true ratings per cluster throughout the experiment
to focus only on changes to $\tilde{U}_{t}$ due to cluster true user
population size. This ensures that any noise due to rating distribution is
avoided.

To illustrate, we fix a cluster-wise true user population of $250-250-n-250$
(i.e. $250$ users per non-target cluster and $n$ users in target cluster), and
a target item rating distribution of $5-5-5-5$ (i.e. $5$ ratings per cluster).
Then, we vary the ratio of the number of true users to fake users
($\frac{n}{m}$) in the target cluster. We increase the values from
$\frac{n}{m}=0.5$ to $2.5$ for both datasets. Figure 2 reports the mean and
standard error of change in the target item’s predicted rating when cluster 2
is targeted against the increasing ratio of $\frac{n}{m}$. As expected, it
shows decreasing relative change in predicted rating as the ratio increase
from $0.5$ to $2.5$ for both Movielens and Goodreads dataset. This is because
when $\frac{n}{m}<1$, the presence of a higher number of fake user weights
compared to true user weights makes it easier for fake users to shift the
cluster weight $\tilde{U}_{t}$. Thus, we conclude that as the number of true
users in the target cluster increases relative to the number of fake users, it
becomes harder to attack the item.

####  6.1.2. Effect of Attack on Non-Target Items and Non-Target Clusters

Figure 3, gives the correlation of each item with the target item v/s the
change in the predicted rating of that item in the target cluster. We can see
a linear relationship indicating that the effect of the attack on non-target
items in the target cluster depends on the correlation between non-target item
vector $V_{j}$ and target item vector $V_{j^{*}}$.

The effect of the attack is not expected to be visible in non-target clusters
since almost all fake users enter target cluster $t$. In Figure 4, we take the
case of $\frac{n}{m}=0.5$ and cluster-wise user distribution $250-250-n-250$
which gave the maximum change in predicted rating for the target item in
Figure 2 and show the cluster wise change in the target item predicted rating
when cluster 2 is targeted. As predicted, we can see that non-target clusters
$0,1,3$ show negligible change in predicted rating after the attack for both
datasets. The results are similar for any attack size or cluster population
size. Keeping $V$ constant results in the attack effects being isolated to the
target cluster alone (when all fake users enter the target cluster).

(a) Movielens (b) Goodreads

Figure 2. Plot comparing the change in predicted rating in target cluster
against the increasing ratio of true users $(n)$ to fake users $(m)$ in the
target cluster ($\frac{n}{m}$)

(a) Movielens (b) Goodreads

Figure 3. Plot comparing the change in the predicted rating of an item in the
target cluster against correlation values between the target item and the
other items

(a) Movielens (b) Goodreads

Figure 4. Plot comparing the change in the predicted rating of the target item
across clusters when cluster 2 is targeted

###  6.2. Fix $\tilde{U}$, update $V$

Before we go ahead and show the results illustrating our findings, let us
briefly recall our key observations of approach $2$.

  1. (1)

Increasing true ratings to target items from the target cluster guarantees a
reduction of the effect of the attack in the target cluster while increasing
true ratings from non-target clusters offers no guaranteed protection from
attack.

  2. (2)

Attacks against users in a target cluster may ’leak’ and affect users in other
clusters. The attack may increase or decrease change in predicted rating in
other clusters depending on their correlation with the target item feature
vector after the attack. This shows that the $V$ vector propagates the effect
of the attack to all non-target clusters. This contrasts the case when $V$ is
kept constant, causing the attack to be isolated to the cluster where the fake
users are present.

  3. (3)

Simply increasing the true user population ($n$) relative to the fake user
population ($m$) does not reduce the change in the target item predicted
rating in the target cluster after the attack. This is in contrast to when we
update $U$ (keeping $V$ constant), where increasing $n$ relative to $m$
reduces the effect of the attack.

First, in Section 6.2.1, we show that increasing true ratings from the target
cluster reduce the attack’s impact as predicted. Then, we study the attack
when the target item is rated by no users in the target cluster but by users
in other clusters in Section 6.2.2. For both experiments, we also illustrate
the mechanism of how $a_{kk}u^{t}_{k}$ and $\sum_{i=1,i\neq
k}^{d}a_{ki}u^{t}_{i}$ of equation 5 work to result in the observed output.
Finally, in Section 6.2.3, we show that increasing the number of true users in
the target cluster does not reduce the impact of the attack on $V_{j^{*}}$.

####  6.2.1. Varying Ratio of True Ratings ($N_{t}$) to Fake Ratings ($N_{f}$)
in Target Cluster

We consider attacks when the target item has received true ratings in the
target cluster but no ratings in the non-targeted clusters. As discussed in
previous sections, we expect that increasing true ratings from the target
cluster will reduce the attack’s impact. Particularly, we study the effect of
attack with increasing true ratings $N_{t}$ from the target cluster given
$N_{f}$ fake ratings. To illustrate, we increase values for
$\frac{N_{t}}{N_{f}}$ from $0.05\text{ to }2.5$ for $N_{f}=100$ fake ratings
and treat it as the target item. We note that the results presented show a
similar trend for any choice of increasing ratio.

#### Results:

Figure 5 reports mean and error plots comparing the change in the predicted
rating of the target item in target cluster 2 after the attack versus the
ratio $\frac{N_{t}}{N_{f}}$. It can be seen from both figures 5(a) and 5(b)
that an item with $\frac{N_{t}}{N_{f}}=0.05$ shows the largest mean shift in
predicted rating after the attack compared to an item with
$\frac{N_{t}}{N_{f}}=2.5$ in the target cluster. i.e., it is harder to change
the predicted rating of the target item after the attack as the number of true
ratings $N_{t}$ received by the target item increases in the target cluster.

#### Illustration of Update Mechanism:

Let us walk through the update mechanism here. Specifically, in this
particular case, since all true ratings come exclusively from the target
cluster, as discussed in Section 4.2, lemma 4 case (1) predicts equation 5 to
be such that each term in $\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}$ always has a
sign opposite to $sgn(a_{kk}u^{t}_{k})$. Also, recall that as the true ratings
$N_{t}$ increase, diagonal term $a_{kk}$ decreases.

For $\frac{N_{t}}{N_{f}}=0.05$ i.e. when number of true ratings $N_{t}$ is
least, diagonal values $a_{kk}$ are higher such that all features follow
mechanism of case $2a:|a_{kk}u^{t}_{k}|>|\sum_{i=1,i\neq
k}^{d}a_{ki}u^{t}_{i}|$, thus updates to feature $v_{k}$ is similar to scaling
of $u^{t}_{k}$. Table 2a reports $\hat{v}_{k}-v_{k}$ update values for each
feature $k$ of the target item vector for both datasets. Let us focus on
$|\hat{v}_{k}-v_{k}|$ corresponding to large $|u^{t}_{k}|$ in both
datasets.777 Recall with $\tilde{U}_{t}$ constant, change in rating after
attack is given by
$\tilde{U_{t}}^{T}\hat{V}_{j^{*}}-\tilde{U_{t}}^{T}V_{j^{*}}=\sum_{k=1}^{d}u^{t}_{k}(\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k})$.
Note $\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}$ corresponding to a large
$|u^{t}_{k}|$ will contribute more to change in rating than
$\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}$ corresponding to a lower $|u^{t}_{k}|$
since such low $|u^{t}_{k}|$ will down-weight
$\hat{v}^{j^{*}}_{k}-v^{j^{*}}_{k}$ values. From the table, we can see that
$|\hat{v}_{k}-v_{k}|$ corresponding to $k=0,1,4$ in ML and $k=2,3,4,6$ in GR
result in large values contributing more to the inner product
$\tilde{U}_{t}^{T}\hat{V}_{j^{*}}$ resulting in the higher relative change in
rating values for $\frac{N_{t}}{N_{f}}=0.05$.

As the true ratings $N_{t}$ increases when ratio $\frac{N_{t}}{N_{f}}$
increases from $0.05$ to $2.5$, diagonal term $a_{kk}$ decreases, bringing
down $|a_{kk}u^{t}_{k}|$ causing the gap between the two terms
$|a_{kk}u^{t}_{k}|$ and $|\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}|$ to reduce.
Thus $|\hat{v}_{k}-v_{k}|$ will tend to smaller values. From table 2a, we note
all feature’s $|\hat{v}_{k}-v_{k}|$ decreasing to smaller values for
$\frac{N_{t}}{N_{f}}=2.5$. A similar reduction in magnitude can be observed
for the Goodreads dataset. This translates as the effect of attack decreasing
for increasing ratio as illustrated by Figure 5.

#### Leakage of Attack to Non-Target Clusters:

To see the effect of attack leakage to non-target clusters, Figure 6 further
breaks down the change in rating by the user clusters when cluster 2 is
targeted in Movielens and Goodreads dataset. It can be seen from Figure 6 that
the non-target clusters also show a positive change in the predicted rating.
888We note that there may be target items that, after transformation, result
in leakage such that non-target clusters show a negative relative change in
rating. But we do not find an item that may illustrate such behavior here.
This is because, for our experiments, we choose randomly from a set of target
items that has a reliable empirical mean $\leq 3$. Such behavior may be found
for a larger set of representative target items or in other datasets. The
attack, therefore, effectively fails to be focused on the target cluster.

$\frac{N_{t}}{N_{f}}$ | k=0 | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 | k=9
---|---|---|---|---|---|---|---|---|---|---
ML : $\tilde{U}_{2}$ | 0.71 | 0.61 | -0.13 | 0.08 | 0.63 | -0.04 | 0.18 | -0.01 | -0.12 | -0.13
0.05 | 1.15 | 0.99 | -0.23 | 0.15 | 1.03 | -0.07 | 0.29 | -0.02 | -0.20 | -0.20
2.5 | 0.28 | 0.23 | -0.05 | 0.04 | 0.28 | -0.05 | 0.07 | -0.03 | -0.05 | -0.06
GR : $\tilde{U}_{2}$ | -0.11 | -0.22 | -0.47 | 0.42 | -0.53 | -0.19 | -0.47 | 0.26 | -0.30 | -0.10
0.05 | -0.21 | -0.43 | -0.90 | 0.81 | -1.04 | -0.37 | -0.90 | 0.51 | -0.60 | -0.22
2.5 | -0.05 | -0.10 | -0.22 | 0.20 | -0.28 | -0.07 | -0.21 | 0.15 | -0.13 | -0.009

(a) True rating distribution $0-0-N_{t}-0$

$\frac{N_{t}}{N_{f}}$ | k=0 | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 | k=9
---|---|---|---|---|---|---|---|---|---|---
ML : $\tilde{U}_{2}$ | 0.71 | 0.61 | -0.13 | 0.08 | 0.63 | -0.04 | 0.18 | -0.01 | -0.12 | -0.13
0.05 | 1.43 | 2.45 | -0.35 | -0.16 | 0.23 | 0.72 | -0.47 | 0.45 | -0.64 | -0.11
2.5 | 1.34 | 2.45 | -0.35 | -0.16 | 0.12 | 0.80 | -0.47 | 0.49 | -0.71 | -0.10
GR : $\tilde{U}_{2}$ | -0.11 | -0.22 | -0.47 | 0.42 | -0.53 | -0.19 | -0.47 | 0.26 | -0.30 | -0.10
0.05 | -0.02 | -1.84 | -1.40 | 1.26 | -0.75 | -0.55 | -0.45 | 1.08 | -0.44 | 0.83
2.5 | -0.01 | -1.90 | -1.37 | 1.21 | -0.56 | -0.49 | -0.40 | 1.09 | -0.47 | 1.06

(b) True rating distribution $N_{t}-N_{t}-0-N_{t}$

Table 2. Target cluster 2 feature vector and target item update vector
$\hat{v^{j^{*}}_{k}}-v^{j^{*}}_{k}$ values for Movielens and Goodreads Dataset
for $d=10$ features

(a)  (b)

Figure 5. Mean and Error plot comparing the relative change in predicted
rating of target cluster 2 against increasing ratio $\frac{N_{t}}{N_{f}}$ in
the target cluster

(a)  (b)

Figure 6. Mean and Error plot comparing the relative change in predicted
rating across clusters when targeting cluster 2 for $\frac{N_{t}}{N_{f}}=0.05$
in target cluster

####  6.2.2.  Varying Ratio of True Ratings $(N_{t})$ to Fake Ratings
$(N_{f})$ in Non-Target Clusters

We now consider attacks when the target item has received true ratings in non-
target clusters but no ratings in the targeted cluster. Particularly, we study
the effect of attack with increasing true ratings $N_{t}$ from each non-target
cluster given $N_{f}$ fake ratings. To illustrate, we increase values of
$\frac{N_{t}}{N_{f}}$ per non-target cluster from $0.05$ to $2.5$ given
$N_{f}=100$ fake ratings. Since no true ratings come from the target cluster,
by theorem 2, increasing total true ratings may not reduce the attack’s impact
in the target cluster.

#### Results:

Figure 7 reports the measured mean change in the target item’s predicted
rating in the targeted cluster against increasing $\frac{N_{t}}{N_{f}}$. It
can be seen that the decreasing trend is much slower (almost negligible)
compared to what was reported in Section 6.2.1, signifying that even with a
larger absolute number of true ratings compared to the previous case, the
attack is effective in the target cluster. i.e., the large overall number of
true ratings fails to protect users in the targeted cluster as presumed.

#### Illustration of Update Mechanism:

Let us look at the update mechanism here. Since true ratings are not
exclusively from the target cluster, as predicted by lemma 10 case (2),
equation 5 is such that terms $a_{ki}u^{t}_{i}$ in summation do not have the
same signs. This reduces the overall magnitude of term $\sum_{i=1,i\neq
k}^{d}a_{ki}u^{t}_{i}$ compared to last section where all the terms in the
summation had the same sign. Thus even though diagonal terms $a_{kk}$ show a
decreasing trend with increasing $N_{t}$, the behavior of summation terms may
cause $|a_{kk}u^{t}_{k}|>|\sum_{i=1,i\neq k}^{d}a_{ki}u^{t}_{i}|$ even at
higher ratios for some features, resulting in the reported greater relative
change in predicted rating at these ratios. For example, note in table 2b how
feature $v^{j^{*}}_{k}$ especially corresponding to larger magnitude
$u^{t}_{k}$ ($k=0,1,4$ in ML and $k=2,3,4,6$ in GR), result in large magnitude
of $\hat{v}^{j^{*}}_{k}$ despite increasing ratio. This contrasts our
observation from table 2a.

#### Leakage of Attack to Non-Target Clusters:

Similar to in Section 6.2.1, we expect to see leakage effect in non-target
clusters. This is illustrated by Figure 8 which breaks down the change in
rating by clusters when cluster 2 is targeted in Movielens and Goodreads
datasets. You can see that the attack’s impact on non-targeted clusters is
lower here than suggested by Figure 6. This is because compared to the last
section where all positively correlated features across clusters underwent
case $2a$ mechanism, due to properties of $A^{-1}$ here,
$\hat{v^{j^{*}}_{k}}-v^{j^{*}}_{k}$ corresponding to many positively
correlated cluster features (e.g.: $k=3,5,6,7$ in ML and $k=9$ in GR) undergo
case $2b$ mechanism causing a shift in directions dissimilar to not only
$u^{t}_{k}$ but all corresponding $k^{th}$ features across non-target clusters
$g\in\mathcal{G}\setminus{t}$.

Thus in these two datasets, the properties of $U,V$ values are such that
unless true ratings also come from the target cluster, it is tough to reduce
the effect of attack within the target cluster.

(a) Movielens (b) Goodreads

Figure 7. Mean and Error plot comparing the relative change in the predicted
rating of target cluster 2 against increasing ratio $\frac{N_{t}}{N_{f}}$ per
non-target cluster

(a) Movielens (b) Goodreads

Figure 8. Mean and Error plot comparing the relative change in predicted
rating across clusters against ratio $\frac{N_{t}}{N_{f}}=0.05$ per non-target
cluster.

####  6.2.3. Varying Ratio of True Users (n) to Fake Users (m) in Target
Cluster

In this section, we investigate the impact of the target cluster’s true user
size $(n)$ relative to the fake user size $(m)$ on the effectiveness of the
attack.

For this experiment, we fix the distribution of ratings as
$\frac{N_{t}}{N_{f}}=0.05$ and $N_{f}=m=100$ similar to in Section 6.2.1 since
it resulted in the maximum change in relative rating in Figure 5. Then we
increase the ratio of $\frac{n}{m}$ from $2.5$ to $10$. Figure 9 reports the
mean and standard error of change in the target item’s predicted rating when
cluster 2 is targeted against increasing values of $\frac{n}{m}$. We can see
how the increasing target cluster size does not affect the attack’s impact.
The relative change in predicted rating after the attack remains almost the
same as expected.

(a)  (b)

Figure 9. Mean and Error plot comparing the relative change in the predicted
rating of target cluster 2 against increasing target cluster size $n$

###  6.3. Discussion

The objective of the targeted attack study on MF-based RS is to gain a better
understanding of how attacks propagate and how the individual behaviors of
feature matrices $U$ and $V$ contribute to this propagation. By holding one
feature matrix constant and updating the other, we isolated the effects of
attacks on each matrix and observed how these effects translate to the
targeted promotion of items in RS. We can use the observations outlined to
make updates to RS more robust.

We concluded how $U_{i}$ values corresponding to all true users $i$ in a RS
are unaffected by the injection of fake ratings when only matrix $U$ is
updated to incorporate the new ratings in RS, keeping $V$ constant. The group
feature vector $\tilde{U}_{t}$ of the target group $t$ is affected due to the
presence of fake users in the target group after the attack. This effect on
$\tilde{U_{t}}$ decreases when the number of true users in the target cluster
increases. Based on these observations, one possible defense mechanism to RS
might be introducing dummy users into any low populated cluster $g$ with their
$U_{i}$ vectors set close to cluster center $\tilde{U}_{g}$. This may help
reduce the impact of an attack by making it harder for injected fake users to
shift $\tilde{U}_{g}$ while not affecting the predicted ratings of the
cluster. Our observations also raise the possibility of monitoring attacks in
MF-based RS by isolating compromised user clusters. We noted how attack
effects are isolated to clusters with fake user presence when $V$ is kept
constant. Therefore, updates to latent feature matrices need not be performed
frequently together. Updating matrix $V$ less frequently and updating only the
$U$ matrix when new users enter would help monitor for suspicious behaviors in
item-predicted ratings across user groups.

We find that the target item vector $V_{j^{*}}$ is more sensitive to the
injection of fake ratings. It is the compromised $V_{j^{*}}$ that leaks attack
effects to all the clusters (even when the clusters do not contain the
presence of fake users). To protect the columns of $V$ matrix from possible
attacks, increasing true ratings to items provides a way. Therefore, providing
dummy ratings to items rated less frequently in a cluster might provide
immunity against malicious changes to its item vector.

##  7\. Conclusion

This paper studied the effect of user-cluster targeted data poisoning attacks
on an MF-based RS by evaluating the changes after the attack on user and item
feature matrices $U,V$. We analysed the mechanism of how $U$ and $V$ matrices
change after the injection of fake ratings and how these changes help
propagate targeted attacks. We also illustrated our findings using two real-
world datasets. We further showed that the effectiveness of an attack on a
target item’s feature vector is influenced by the distribution of the number
of ratings received by the target item. We find that items with fewer ratings
in the target cluster are more susceptible to attack.

We conclude that a simple attack with limited knowledge of user preferences
suffices to target a specific user cluster precisely. For our future work, we
want to use these observations to research different defensive approaches in
MF-based RS that are simple yet effective and can be easily used in existing
systems.

###### Acknowledgements.

This work was supported by Science Foundation Ireland (SFI) under grant
16/IA/4610

## References

  * (1)
  * Checco et al. (2015) Alessandro Checco, Giuseppe Bianchi, and Doug Leith. 2015\.  BLC: Private Matrix Factorization Recommenders via Automatic Group Learning.  https://doi.org/10.48550/ARXIV.1509.05789
  * Christakopoulou and Banerjee (2019) Konstantina Christakopoulou and Arindam Banerjee. 2019.  Adversarial Attacks on an Oblivious Recommender. In _Proceedings of the 13th ACM Conference on Recommender Systems_ (Copenhagen, Denmark) _(RecSys ’19)_. Association for Computing Machinery, New York, NY, USA, 322–330.  https://doi.org/10.1145/3298689.3347031
  * Deldjoo et al. (2020) Yashar Deldjoo, Tommaso Di Noia, and Felice Antonio Merra. 2020\.  _Adversarial Machine Learning in Recommender Systems (AML-RecSys)_.  Association for Computing Machinery, New York, NY, USA, 869–872.  https://doi.org/10.1145/3336191.3371877
  * Epasto et al. (2021) Alessandro Epasto, Andrés Muñoz Medina, Steven Avery, Yijian Bai, Robert Busa-Fekete, CJ Carey, Ya Gao, David Guthrie, Subham Ghosh, James Ioannidis, Junyi Jiao, Jakub Lacki, Jason Lee, Arne Mauser, Brian Milch, Vahab Mirrokni, Deepak Ravichandran, Wei Shi, Max Spero, Yunting Sun, Umar Syed, Sergei Vassilvitskii, and Shuo Wang. 2021.  Clustering for Private Interest-Based Advertising. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ (Virtual Event, Singapore) _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 2802–2810.  https://doi.org/10.1145/3447548.3467180
  * Fang et al. (2020) Minghong Fang, Neil Zhenqiang Gong, and Jia Liu. 2020\.  _Influence Function Based Data Poisoning Attacks to Top-N Recommender Systems_.  Association for Computing Machinery, New York, NY, USA, 3019–3025.  https://doi-org.elib.tcd.ie/10.1145/3366423.3380072
  * Fang et al. (2018) Minghong Fang, Guolei Yang, Neil Zhenqiang Gong, and Jia Liu. 2018.  Poisoning Attacks to Graph-Based Recommender Systems.  _Proceedings of the 34th Annual Computer Security Applications Conference_ (Dec 2018).  https://doi.org/10.1145/3274694.3274706
  * Hu et al. (2019) Rui Hu, Yuanxiong Guo, Miao Pan, and Yanmin Gong. 2019\.  Targeted Poisoning Attacks on Social Recommender Systems. In _2019 IEEE Global Communications Conference (GLOBECOM)_. 1–6.  https://doi.org/10.1109/GLOBECOM38437.2019.9013539
  * Huang et al. (2021) Hai Huang, Jiaming Mu, Neil Zhenqiang Gong, Qi Li, Bin Liu, and Mingwei Xu. 2021\.  Data Poisoning Attacks to Deep Learning Based Recommender Systems.  _Proceedings 2021 Network and Distributed System Security Symposium_ (2021).  https://doi.org/10.14722/ndss.2021.24525
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009\.  Matrix Factorization Techniques for Recommender Systems.  _Computer_ 42, 8 (2009), 30–37.  https://doi.org/10.1109/MC.2009.263
  * Lam and Riedl (2004) Shyong K. Lam and John Riedl. 2004.  Shilling Recommender Systems for Fun and Profit. In _Proceedings of the 13th International Conference on World Wide Web_ (New York, NY, USA) _(WWW ’04)_. Association for Computing Machinery, New York, NY, USA, 393–402.  https://doi.org/10.1145/988672.988726
  * Li et al. (2016) Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. 2016\.  Data Poisoning Attacks on Factorization-Based Collaborative Filtering. In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ (Barcelona, Spain) _(NIPS’16)_. Curran Associates Inc., Red Hook, NY, USA, 1893–1901.
  * Lin et al. (2020) Chen Lin, Si Chen, Hui Li, Yanghua Xiao, Lianyun Li, and Qian Yang. 2020\.  Attacking recommender systems with augmented user profiles. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 855–864.
  * Mingdan and Li (2020) Si Mingdan and Qingshan Li. 2020.  Shilling attacks against collaborative recommender systems: a review.  _Artificial Intelligence Review_ 53 (01 2020).  https://doi.org/10.1007/s10462-018-9655-x
  * Mittal et al. (2010) Namita Mittal, Richi Nayak, M.C. Govil, and K.C. Jain. 2010\.  Recommender System Framework Using Clustering and Collaborative Filtering. In _2010 3rd International Conference on Emerging Trends in Engineering and Technology_. 555–558.  https://doi.org/10.1109/ICETET.2010.121
  * Mobasher et al. (2007) Bamshad Mobasher, Robin Burke, Runa Bhaumik, and Chad Williams. 2007.  Toward trustworthy recommender systems.  _ACM Transactions on Internet Technology_ 7 (10 2007), 23–es.  https://doi.org/10.1145/1278366.1278372
  * Patel et al. (2015) Krupa Patel, AmitThakkar, Chandni Shah, and Kamlesh Makvana. 2015\.  A State Of Art Survey on Shilling Attack in Collaborative Filtering Based Recommendation System.
  * Research and Ads (2009) Google Research and Ads. 2009.  Evaluation of Cohort Algorithms for the FloC API.  https://github.com/google/ads-privacy/blob/master/proposals/FLoC/FLOC-Whitepaper-Google.pdf
  * Shams et al. (2021) Sulthana Shams, Daron Anderson, and Douglas Leith. 2021\.  _Cluster-Based Bandits: Fast Cold-Start for Recommender System New Users_.  Association for Computing Machinery, New York, NY, USA, 1613–1616.  https://doi.org/10.1145/3404835.3463033
  * Shams and Leith (2022) Sulthana Shams and Douglas J. Leith. 2022.  Improving Resistance of Matrix Factorization Recommenders To Data Poisoning Attacks. In _2022 Cyber Research Conference - Ireland (Cyber-RCI)_. 1–4.  https://doi.org/10.1109/Cyber-RCI55324.2022.10032671
  * Wu et al. (2021) Chenwang Wu, Defu Lian, Yong Ge, Zhihao Zhu, Enhong Chen, and Senchao Yuan. 2021\.  _Fight Fire with Fire: Towards Robust Recommender Systems via Adversarial Poisoning Training_.  Association for Computing Machinery, New York, NY, USA, 1074–1083.  https://doi-org.elib.tcd.ie/10.1145/3404835.3462914
  * Xie and Phoha (2001) Yunjuan Xie and Vir V. Phoha. 2001.  Web User Clustering from Access Log Using Belief Function. In _Proceedings of the 1st International Conference on Knowledge Capture_ (Victoria, British Columbia, Canada) _(K-CAP ’01)_. Association for Computing Machinery, New York, NY, USA, 202–208.  https://doi.org/10.1145/500737.500768
  * Xu et al. (2020) Yangjun Xu, Liang Chen, Fenfang Xie, Weibo Hu, Jieming Zhu, Chuan Chen, and Zibin Zheng. 2020.  Directional Adversarial Training for Recommender Systems.. In _ECAI_. 553–560.
  * Yanxiang et al. (2013) Ling Yanxiang, Guo Deke, Cai Fei, and Chen Honghui. 2013\.  User-based Clustering with Top-N Recommendation on Cold-Start Problem. In _2013 Third International Conference on Intelligent System Design and Engineering Applications_. 1585–1589.  https://doi.org/10.1109/ISDEA.2012.381

##  Appendix A Properties Of Positive Definite/ Semi-Definite Matrices

###### Definition 1.

A matrix $M$ is called Positive Semi-Definite (PSD) if it is symmetric and its
eigen values are non-negative. If the eigen values are positive, they are
called Positive Definite (PD) Matrices. Equivalently, we can say that if the
matrix $M$ is symmetric and satisfies $x^{T}Mx>=0$ for a non-zero vector $x$,
then $M$ is PSD and if $M$ is symmetric and satisfies $x^{T}Mx>0$ for a non-
zero vector $x$, then $M$ is PD.

###### Lemma 1.

Any $n\times n$ matrix of the form $M=BB^{T}$ is PSD for any $n\times m$
matrix $B$.

###### Proof 1.

By definition 1, for matrix $M$ to be PSD, we require that it be

  * •

Symmetric i.e. $M^{T}=M$

  * •

$x^{T}Mx>=0$ for any non-zero vector $x\in\mathbb{R}^{n}$

We have $M^{T}=(BB^{T})^{T}=BB^{T}=M$ by the property of transpose
$(AB)^{T}=B^{T}A^{T}$ and

Also $x^{T}Mx=x^{T}BB^{T}x=x^{T}B(x^{T}B)^{T}$. Define $y=x^{T}B$ such that

$x^{T}Mx=x^{T}B(x^{T}B)^{T}=yy^{T}=\sum_{i=1}^{m}y_{i}^{2}\geq 0$

Thus $M=BB^{T}$ is a Positive Semi-Definite Matrix.

###### Lemma 2.

Let $A$ be a PSD matrix, and $B$ be a PD matrix. Then their sum $A+B$ is a PD
Matrix.

###### Proof 2.

By definition 1, for any non-zero vector $x$, the quadratic form $xAx^{T}>=0$
if $A$ is a PSD matrix and $xAx^{T}>0$ if $A$ is a PD matrix. So a matrix
defined as the sum of a PSD matrix $A$ and a PD matrix $B$ satisfies

$x(A+B)x^{T}=xAx^{T}+xBx^{T}>0$

making the resulting matrix PD.

###### Lemma 3.

Let $M$ be a PSD matrix, then its inverse $M^{-1}$ is also a PSD.

###### Proof 3.

By definition 1, given matrix $M$ is PD, then it satisfies the following
properties

  * •

Symmetric i.e. $M^{T}=M$

  * •

and has positive eigenvalues

We can write $(M^{-1})^{T}=M^{-1}$ (since $M$ is invertible and satisfies
property $(M^{-1})^{T}=(M^{T})^{-1}$). Also, we know that eigenvalues of
$M^{-1}$ are inverse of the eigen values of $M$. Since, by definition,
eigenvalues of $M$ are positive, eigen values of $M^{-1}$ are also positive.
Therefore, $M^{-1}$ is also PSD.

###### Lemma 4.

If the matrix $M$ is PD, then all diagonal elements of $M$ are positive.

###### Proof 4.

The proof follows by considering the property $x^{T}Mx>0$ for any PD Matrix
$M$. If we set $x$ to be the standard basis vector with $x_{k}=1$ and
$x_{i}=0$ for all $i\neq k$, then $x^{T}Mx=M_{kk}>0$, which means that all the
entries in the diagonal of $M$ are positive.

##  Appendix B Sherman-Morrison Formula

Given $M$ is a square $n\times n$ matrix whose inverse matrix we know, for the
simple case of a rank-1 perturbation to $M$, Sherman–Morrison formula provides
a method to find the updated rank-1 change to the inverse.

###### Definition 2.

Given $M$ is a square $n\times n$ matrix whose inverse matrix we know, $u$ and
$v$ are $n\times 1$ column vectors defining the perturbation to matrix $M$
such that $u_{i}v_{j}^{T}$ is added to $M_{i,j}$, then we can find the inverse
of the modified $M$ by Sherman-Morrison formula

$(M+uv^{T})^{-1}=M^{-1}-\frac{M^{-1}uv^{T}M^{-1}}{1+v^{T}M^{-1}u}$

For a generalised rank-$k$ perturbation to $M$, the updated inverse is given
by the following formula.

###### Definition 3.

Given $M$ is a square $n\times n$ matrix whose inverse matrix we know, $U$ and
$V$ are $n\times k$ matrices defining rank $k$ perturbation to matrix $M$,
then we can find the inverse of the modified $M$

$(M+UV^{T})^{-1}=M^{-1}-M^{-1}U(I_{k}+V^{T}M^{-1}U)^{-1}V^{T}M^{-1}$

###### Lemma 5.

if $M^{-1}$ is a PSD matrix and $\hat{M}=M+uu^{T}$ for non-zero
$u\in\mathbb{R}^{n\times 1}$, then diagonal elements of $\hat{M}^{-1}$ is less
than or equal to the diagonal elements of matrix $M^{-1}$.

###### Proof 5.

We can find the inverse of $\hat{M}$ by Sherman-Morrison formula

$(M+uu^{T})^{-1}=M^{-1}-\frac{M^{-1}uu^{T}M^{-1}}{1+u^{T}M^{-1}u}$

From the expression we note that the numerator of the subtracting term
$(M^{-1}u)(u^{T}M^{-1})$ is the product of a matrix and its transpose
$((M^{-1}u)(M^{-1}u)^{T})$, so $M^{-1}uu^{T}M^{-1}$ is PSD matrix by lemma 1
and therefore has positive diagonal values by lemma 4. Since $M^{-1}$ is a PSD
matrix and the quadratic form $u^{T}M^{-1}u>=0$ for any non-zero vector $u$,
the denominator of subtracting term is always positive. So we can say that the
diagonal elements of the subtracting term are $>=0$. Then we can conclude that
the diagonal elements of updated inverse is less than or equal to the diagonal
elements of matrix $M^{-1}$.

##  Appendix C Proofs

###  C.1. Deriving Recursive Updates to $V_{j}$

####  C.1.1. Proof of Theorem 1

###### Proof 6.

For simplicity, let $\Lambda$ gather together the feature vectors $U_{i}$ of
all users $i$ who rated target item $j^{*}$ such that
$\Lambda\Lambda^{T}=\sum_{i\in\mathcal{U}(j^{*})}U_{i}U_{i}^{T}$ and let $r$
be a column vector of ratings received by the target item from these true
users. We can write equation 3 as,

$V_{j^{*}}=(\Lambda\Lambda^{T}+\lambda I)^{-1}\Lambda r=A^{-1}\Lambda r$

where $A=\Lambda\Lambda^{T}+\lambda I$. After the block of fake users enter,
we write $\hat{U}=[\Lambda,X]$ and
$\hat{U}\hat{U}^{T}=\Lambda\Lambda^{T}+XX^{T}$. Also
$\hat{r}=\begin{bmatrix}r\\\ y\end{bmatrix}$ and
$\hat{A}^{-1}=(\hat{U}\hat{U}^{T}+\lambda I)^{-1}=(A+XX^{T})^{-1}$. We now
calculate the updated $\hat{V_{j^{*}}}$. We know that,

$\displaystyle\hat{V_{j^{*}}}$
$\displaystyle=\hat{A}^{-1}\hat{U}\hat{r}=\hat{A}^{-1}\left(\Lambda
r+Xy\right)=\left(A+XX^{T}\right)^{-1}\left(\Lambda r+Xy\right)$ Applying
Sherman Morrison/Woodbury formula to the inverse (see Definition 2)
$\displaystyle=\left(A^{-1}-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}A^{-1}\right)\left(\Lambda
r+Xy\right)$ $\displaystyle=A^{-1}\Lambda
r-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}A^{-1}\Lambda
r+A^{-1}Xy-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}A^{-1}Xy$
$\displaystyle\text{We have, }V_{j^{*}}=A^{-1}\Lambda r\text{. substituting
for $A^{-1}\Lambda r$ and rearranging, we get, }$
$\displaystyle=V_{j^{*}}-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}V_{j^{*}}+A^{-1}X\left(I-\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}A^{-1}X\right)y$
$\displaystyle\text{Substituting
}I=(I+X^{T}A^{-1}X)^{-1}(I+X^{T}A^{-1}X)\text{ inside third term, we get,}$
$\displaystyle\begin{split}&=V_{j^{*}}-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}V_{j^{*}}+\\\
&A^{-1}X\left(\left(I+X^{T}A^{-1}X\right)^{-1}\left(I+X^{T}A^{-1}X\right)-\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}A^{-1}X\right)y\end{split}$
$\displaystyle=V_{j^{*}}-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}V_{j^{*}}+A^{-1}X\left(\left(I+X^{T}A^{-1}X\right)^{-1}\left(I+X^{T}A^{-1}X-X^{T}A^{-1}X\right)\right)y$
$\displaystyle=V_{j^{*}}-A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}X^{T}V_{j^{*}}+A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}y$
$\displaystyle=V_{j^{*}}+A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}\left(y-X^{T}V_{j^{*}}\right)$

Finally, we have,

(7) $\displaystyle\hat{V_{j^{*}}}-V_{j^{*}}$
$\displaystyle=A^{-1}X\left(I+X^{T}A^{-1}X\right)^{-1}\left(y-X^{T}V_{j^{*}}\right)$

Here we have three terms $a=A^{-1}X$, $b=\left(I+X^{T}A^{-1}X\right)^{-1}$ and
$c=\left(y-X^{T}V_{j^{*}}\right)$. Using Lemma $6,7,8,9,10$ (next section) we
re-write equation 7 as

$\displaystyle\hat{V_{j*}}-V_{j*}$ $\displaystyle=m\times
K\times\left(A^{-1}\tilde{U}_{t}\right)$

where $K=bc$ and $m,K$ are positive constants.

###  C.2. Re-writing Equation 7

If we look at the term $A^{-1}=(\Lambda\Lambda^{T}+\lambda I)^{-1}$ in
equation 7, since $\Lambda\Lambda^{T}$ is a multiplication of a matrix with
its transpose, it is positive semi-definite (PSD) matrix, and $\lambda I$ is a
positive definite (PD) matrix. 999See Definition 1 and Lemma 1 in Appendix A
Then $(\Lambda\Lambda^{T}+\lambda I)$ is a PD matrix 101010See Lemma 2 in
Appendix A. Since the inverse of a PD matrix is also PD, $A^{-1}$ is a PD
matrix. 111111See Lemma 3 in Appendix A Because $A^{-1}$ is a PD matrix and
since columns of $X$ are identical to $\tilde{U}_{t}$, by lemma C.2 we can say
that term $X^{T}A^{-1}X$ in $b$ results in an $\mathbb{R}^{n\times n}$ matrix
with identical values for all the elements.

Lemma Let $M=X^{T}A^{-1}X$ and $x_{i},x_{j}\in\mathbb{R}^{d\times 1}$ be the
$i^{th}$ and $j^{th}$ column in $X$. Given $x_{i}=x_{j}=\tilde{U}_{t}$ and
$A^{-1}$ is a PD matrix, then $(m)_{ij}=x_{i}^{T}A^{-1}x_{j}$ is a positive
constant.

###### Proof 7.

$\displaystyle(m)_{ij}=x_{i}^{T}A^{-1}x_{j}$
$\displaystyle=\tilde{U}_{t}^{T}A^{-1}\tilde{U}_{t}$

We know by Definition 1 that pre-multiplying and post-multiplying a PD matrix
by the same vector takes a quadratic form and always results in a positive
number provided the multiplying vector is non-zero.

So $X^{T}A^{-1}X$ results in a matrix with all elements having identical
values. By lemma 6 the inverse of $I+X^{T}A^{-1}X$ results in a matrix with
all diagonal elements having identical values and the non-diagonal elements
having identical values.

###### Lemma 6.

For any matrix $M\in\mathbb{R}^{n\times n}$ with identical elements, the
inverse of $I+M$ results in a matrix with all diagonal elements having
identical values and the non-diagonal elements having identical values.

###### Proof 8.

For any $M\in\mathbb{R}^{n\times n}$ with identical elements, we can write
$\left(I+M\right)^{-1}=\left(I+ec^{T}\right)$, for $M=ec^{T}$ where
$e=[1,1,1,\cdots,1]^{T}$ and $c$ is a column of $M$. Applying Sherman-Morrison
formula, we get

$\left(I+M\right)^{-1}=I-\frac{M}{1+c^{T}e}$

Note that the denominator is a positive constant. So we can say that the
resulting matrix will have all diagonal elements the same and all non-diagonal
values the same.

Now we have term $b$. Next, we proceed to evaluate the term $c$. Term
$c=y-X^{T}V_{j^{*}}$ says how much of target item fake rating vector $y$ with
all its value equal to the highest rating $5$ can be explained by the existing
weight vector $V_{j^{*}}$. If $V_{j^{*}}$ before the attack can explain the
vector $y$ then term $c$ will be a zero vector and equation 7 results in
$\hat{V_{j^{*}}}=V_{j^{*}}$ as is to be expected i.e. there is no point in
attacking an item that already has the maximum rating in the target cluster.
By lemma 7, term $c$ results in a column vector containing identical values in
each row. In particular, we have,

###### Lemma 7.

Given a column vector $y\in\mathbb{R}^{m\times 1}$ with constant values, all
rows of column vector $c$ result in an identical positive constant.

###### Proof 9.

We know that any $i^{th}$ column in $X$ can be written as
$x_{i}=\tilde{U}_{t}$. Then we can write for any $i^{th}$ row of term
$c=y-X^{T}V_{j^{*}}$

$\displaystyle y_{i}-x_{i}^{T}V_{j^{*}}$
$\displaystyle=y_{i}-\tilde{U}_{t}^{T}V_{j^{*}}$

$\tilde{U}_{t}^{T}V_{j^{*}}$ is the predicted rating of item $j^{*}$ in
cluster $t$ before attack and is a constant for all users belonging to cluster
$t$. Also $y_{i}=5$ in our set-up, thus rows of $y-X^{T}V_{j^{*}}$ will result
in the same non-zero positive value.

Now that we have terms $b,c$, we proceed to find the values of the column
vector resulting from the product of terms $b$ and $c$.

###### Lemma 8.

Given $m\times m$ matrix $b=(I+X^{T}A^{-1}X)^{-1}$ and $m\times 1$ matrix
$c=y-X^{T}V_{j^{*}}$, the $m\times 1$ column vector resulting from their
product has same value for all rows.

###### Proof 10.

We can write $bc$ as

$\displaystyle bc$
$\displaystyle=b(y-X^{T}V_{j^{*}})=by-b(X^{T}V_{j^{*}})=by-b\left([\tilde{U}_{t},\tilde{U}_{t},\cdots,\tilde{U}_{t}]^{T}V_{j^{*}}\right)$
We have
$[\tilde{U}_{t},\tilde{U}_{t},\cdots,\tilde{U}_{t}]^{T}V_{j^{*}}=[\tilde{U}_{t}^{T}V_{j^{*}},\tilde{U}_{t}^{T}V_{j^{*}},\cdots,\tilde{U}_{t}^{T}V_{j^{*}}]^{T}$
So we can write $\displaystyle bc$
$\displaystyle=by-b[\tilde{U}_{t}^{T}V_{j^{*}},\tilde{U}_{t}^{T}V_{j^{*}},\cdots,\tilde{U}_{t}^{T}V_{j^{*}}]^{T}$
Using lemma C.2, $b$ is a matrix with all diagonal values identical and all
non-diagonal values identical and we know $\tilde{U}_{t}^{T}V_{j^{*}}$ is a
constant. $\displaystyle bc$ $\displaystyle=[K,K,\cdots,K]^{T}\text{ for
positive constant $K$}$

Now we have $\hat{V}_{j^{*}}-V_{j^{*}}=A^{-1}X(bc)$ where
$bc=[K,K,\cdots,K]^{T}$ for positive constant $K$. From lemma 9, computing the
product $X(bc)$ results in a $\mathbb{R}^{d\times 1}$ vector with values as
$m\times K\times\tilde{U}_{t}$.

###### Lemma 9.

Given $X\in\mathbb{R}^{d\times m}$ with $i^{th}$ column vector $x_{i}$ as
$\tilde{U}_{t}$ and $bc=[K,K,\cdots,K]^{T}$, we can write $X(bc)=m\times
K\times\tilde{U}_{t}$.

###### Proof 11.

We can write $X(bc)$ as, $\displaystyle X(bc)$
$\displaystyle=[x_{1},x_{2},\cdots,x_{m}][K,K,\cdots,K]^{T}$ Using
$x_{i}=\tilde{U}_{t}$ where
$\tilde{U}_{t}=[u^{t}_{1},u^{t}_{2},\cdots,u^{t}_{d}]^{T}$
$\displaystyle=\begin{bmatrix}u^{t}_{1}&u^{t}_{1}&\cdots,&u^{t}_{1}\\\
u^{t}_{2}&u^{t}_{2}&\cdots,&u^{t}_{2}\\\ \vdots\\\
u^{t}_{d}&u^{t}_{d}&\cdots,&u^{t}_{d}\end{bmatrix}\begin{bmatrix}K\\\ K\\\
\vdots\\\
K\end{bmatrix}=\begin{bmatrix}u^{t}_{1}K+u^{t}_{1}K+\cdots+u^{t}_{1}K\\\
u^{t}_{2}K+u^{t}_{2}K+\cdots+u^{t}_{2}K\\\ \vdots\\\
u^{t}_{d}K+u^{t}_{d}K+\cdots+u^{t}_{d}K\end{bmatrix}$
$\displaystyle=[mKu^{t}_{1},mKu^{t}_{2},\cdots,mKu^{t}_{d}]^{T}=m\times
K\times\tilde{U}_{t}$

Equation 7 can now be written as $\hat{V_{j^{*}}}-V_{j^{*}}=m\times
K\times\left(A^{-1}\tilde{U}_{t}\right)$

###  C.3. Proof of Lemma 10

###### Definition 4.

Any matrix $M\in\mathbb{R}^{d\times n}$ with identical columns will satisfy
$MM^{T}=nmm^{T}$ where $m$ is a column of $M$. Similarly we can write
$\sum_{i\in\mathcal{U}(j)}U_{i}U_{i}^{T}=n\tilde{U}_{g}\tilde{U}_{g}^{T}$ if
the set of $n$ users in $\mathcal{U}(j)$ belong to same cluster $g$ with
weight vector $\tilde{U}_{g}$

###### Lemma 10.

Given a target item $j^{*}$ such that
$A^{-1}=\left(\sum_{i\in\mathcal{U}(j^{*})}{U_{i}U_{i}^{T}+\lambda
I}\right)^{-1}$ where $\mathcal{U}(j^{*})$ is the set of $n$ users who rated
item $j^{*}$. Let a block of fake users with feature vectors in
$X\in\mathbb{R}^{d\times m}$ enter to increase the predicted rating of item
$j^{*}$ in a cluster $t$ with
$X=[\tilde{U}_{t},\tilde{U}_{t},\cdots,\tilde{U}_{t}]$ where
$\tilde{U}_{t}=[u^{t}_{1},u^{t}_{2},\cdots,u^{t}_{d}]^{T}$, then
1) If the $n$ users belong to target cluster $t$, all terms $a_{ki}u^{t}_{i}$
of any row $k$ of matrix $A^{-1}\tilde{U}_{t}$ (equation 5) will have the same
sign and the sign will be opposite to $sgn(a_{kk}u^{t}_{k})$.
2) If the $n$ users are not exclusive to the target cluster, all terms
$a_{ki}u^{t}_{i}$ of any row $k$ of the matrix $A^{-1}\tilde{U}_{t}$ (
equation 5) need not have the same sign and the sign does not depend
exclusively on $sgn(a_{kk}u^{t}_{k})$.

###### Proof 12.

Let target item be rated by all users belonging to target cluster. By
Definition 4, we have,

$A^{-1}=\left(\sum_{i\in\mathcal{U}(j^{*})}{U_{i}U_{i}^{T}+\lambda
I}\right)^{-1}=(\lambda
I+n\tilde{U}_{t}\tilde{U}_{t}^{T})^{-1}=\frac{1}{n}\left(\frac{\lambda}{n}I+\tilde{U}_{t}\tilde{U}_{t}^{T}\right)^{-1}$

To find $A^{-1}$, we apply Sherman-Morrison formula (see Definition 2) to the
inverse term

$\displaystyle\left(\frac{\lambda}{n}I+\tilde{U}_{t}\tilde{U}_{t}^{T}\right)^{-1}$
$\displaystyle=\frac{n}{\lambda}I-\frac{\frac{n}{\lambda}I\tilde{U}_{t}\tilde{U}_{t}^{T}\frac{n}{\lambda}I}{1+\tilde{U}_{t}^{T}\frac{n}{\lambda}I\tilde{U}_{t}}=\frac{n}{\lambda}I-\frac{\left(\frac{n}{\lambda}\right)^{2}\tilde{U}_{t}\tilde{U}_{t}^{T}}{1+\frac{n}{\lambda}\tilde{U}_{t}^{T}\tilde{U}_{t}}=\frac{n}{\lambda}I-\frac{\frac{n}{\lambda}\tilde{U}_{t}\tilde{U}_{t}^{T}}{\frac{\lambda}{n}+\tilde{U}_{t}^{T}\tilde{U}_{t}}$
$\displaystyle=\frac{n}{\lambda}I-\frac{\frac{n}{\lambda}{\tilde{U}_{t}\tilde{U}_{t}^{T}}}{C}\text{
where denominator $C=\frac{\lambda}{n}+\tilde{U}_{t}^{T}\tilde{U}_{t}$ is a
positive constant}$

Then we can write $A^{-1}$ as

$\displaystyle A^{-1}$
$\displaystyle=\frac{1}{n}\left(\frac{\lambda}{n}I+\tilde{U}_{t}\tilde{U}_{t}^{T}\right)^{-1}=\frac{1}{\lambda}\left(I-\frac{\tilde{U}_{t}\tilde{U}_{t}^{T}}{C}\right)$

Case 1: Now that we have matrix $A^{-1}$ for the case when true users come
exclusively from the target cluster, we calculate $A^{-1}\tilde{U}_{t}$,

$\displaystyle A^{-1}\tilde{U}_{t}$
$\displaystyle=\frac{1}{\lambda}\begin{bmatrix}1-\frac{(u^{t}_{1})^{2}}{C}&-\frac{u^{t}_{1}u^{t}_{2}}{C}&\cdots&-\frac{u^{t}_{1}u^{t}_{d}}{C}\\\
-\frac{u^{t}_{2}u^{t}_{1}}{C}&1-\frac{(u^{t}_{2})^{2}}{C}&\cdots&-\frac{u^{t}_{2}u^{t}_{d}}{C}\\\
\vdots\\\
-\frac{u^{t}_{d}u^{t}_{1}}{C}&-\frac{u^{t}_{d}u^{t}_{2}}{C}&\cdots&1-\frac{(u^{t}_{d})^{2}}{C}\end{bmatrix}\begin{bmatrix}u^{t}_{1}\\\
u^{t}_{2}\\\ \vdots\\\
u^{t}_{d}\end{bmatrix}=\frac{1}{\lambda}\begin{bmatrix}u^{t}_{1}\left(1-\frac{(u^{t}_{1})^{2}}{C}\right)+\sum_{i=1,i\neq
1}^{d}-u^{t}_{1}\frac{(u^{t}_{i})^{2}}{C}\\\
u^{t}_{2}\left(1-\frac{(u^{t}_{2})^{2}}{C}\right)+\sum_{i=1,i\neq
2}^{d}-u^{t}_{2}\frac{(u^{t}_{i})^{2}}{C}\\\ \vdots\\\
u^{t}_{d}\left(1-\frac{(u^{t}_{d})^{2}}{C}\right)+\sum_{i=1,i\neq
d}^{d}-u^{t}_{d}\frac{(u^{t}_{i})^{2}}{C}\\\ \end{bmatrix}$

Recall equation 5 that gives the $k^{th}$ row of $A^{-1}\tilde{U}_{t}$. Here
the $k^{th}$ row $a_{kk}u^{t}_{k}+\sum_{i=1,i\neq
k}^{d}a_{ki}u^{t}_{i}=u^{t}_{k}\left(1-\frac{(u^{t}_{k})^{2}}{C}\right)+\sum_{i=1,i\neq
k}^{d}-u^{t}_{k}\frac{(u^{t}_{k})^{2}}{C}$. Note that the first term
$u^{t}_{k}\left(1-\frac{(u^{t}_{k})^{2}}{C}\right)$ has the sign of
$u^{t}_{k}$ since $\frac{(u^{t}_{k})^{2}}{C}<1$. Consider the terms in the
summation i.e. $a_{ki}u^{t}_{i}=-u^{t}_{k}\frac{(u^{t}_{i})^{2}}{C}$. Here
$\frac{(u^{t}_{i})^{2}}{C}$ is positive because the numerator is a square and
the denominator is a positive constant. So each term
$-u^{t}_{k}\frac{(u^{t}_{i})^{2}}{C}$ has sign $-sgn(u^{t}_{k})$ or in other
words opposite to the sign of the first term. Therefore, for case $1$, all
terms $a_{ki}u^{t}_{i}$ of any row $k$ of the matrix $A^{-1}\tilde{U}_{t}$
(equation 5) has the same sign and the sign is opposite to
$sgn(a_{kk}u^{t}_{k})$.

Case 2: Following similar steps, $A^{-1}\tilde{U}_{t}$ when true ratings come
exclusively from any cluster $g\neq t$ and for
$C=\frac{\lambda}{n}+\tilde{U}_{g}^{T}\tilde{U}_{g}$ is given by.

$\displaystyle\hat{A}^{-1}\tilde{U}_{t}$
$\displaystyle=\frac{1}{\lambda}\begin{bmatrix}1-\frac{(u^{g}_{1})^{2}}{C}&-\frac{u^{g}_{1}u^{g}_{2}}{C}&\cdots&-\frac{u^{g}_{1}u^{g}_{d}}{C}\\\
-\frac{u^{g}_{2}u^{g}_{1}}{C}&1-\frac{(u^{g}_{2})^{2}}{C}&\cdots&-\frac{u^{g}_{2}u^{g}_{d}}{C}\\\
\vdots\\\
-\frac{u^{g}_{d}u^{g}_{1}}{C}&-\frac{u^{g}_{d}u^{g}_{2}}{C}&\cdots&1-\frac{(u^{g}_{d})^{2}}{C}\end{bmatrix}\begin{bmatrix}u^{t}_{1}\\\
u^{t}_{2}\\\ \vdots\\\
u^{t}_{d}\end{bmatrix}=\frac{1}{\lambda}\begin{bmatrix}u^{t}_{1}\left(1-\frac{(u^{g}_{1})^{2}}{C}\right)+\sum_{i=1,i\neq
1}^{d}-u^{t}_{i}\frac{u^{g}_{1}u^{g}_{i}}{C}\\\
u^{t}_{2}\left(1-\frac{(u^{g}_{2})^{2}}{C}\right)+\sum_{i=1,i\neq
2}^{d}-u^{t}_{i}\frac{u^{g}_{2}u^{g}_{i}}{C}\\\ \vdots\\\
u^{t}_{d}\left(1-\frac{(u^{g}_{d})^{2}}{C}\right)+\sum_{i=1,i\neq
d}^{d}-u^{t}_{i}\frac{u^{g}_{2}u^{g}_{i}}{C}\\\ \end{bmatrix}$

Similar to previous case, first term in $k^{th}$ row of $A^{-1}\tilde{U}_{t}$
has the sign of $u^{t}_{k}$. The terms in summation
$a_{ki}u^{g}_{i}=-u^{t}_{i}\frac{u^{g}_{k}u^{g}_{i}}{C}$, has its sign depend
on $sgn(u^{t}_{i}u^{g}_{k}u^{g}_{i})$. So unlike case 1, term
$a_{ki}u^{g}_{i}$ may have any sign.

#### When true ratings come from a combination of clusters:

Consider a simple extension where $n_{1}$ users of target cluster $t$ and
$n_{2}$ users of cluster $g$ provide ratings. Given $n_{1}+n_{2}=n$, we have,

$\displaystyle A^{-1}$ $\displaystyle=(\lambda
I+n_{1}\tilde{U}_{t}\tilde{U}_{t}^{T}+n_{2}\tilde{U}_{g}\tilde{U}_{g}^{T})^{-1}=(M+n_{2}\tilde{U}_{g}\tilde{U}_{g}^{T})^{-1}$
$\displaystyle=M^{-1}-\frac{M^{-1}\tilde{U}_{g}\tilde{U}_{g}^{T}M^{-1}}{\frac{1}{n_{2}}+\tilde{U}_{g}^{T}M^{-1}\tilde{U}_{g}}\text{
where $M^{-1}=\left(\lambda I+n_{1}\tilde{U}_{t}\tilde{U}_{t}^{T}\right)^{-1}$
(given in case $1$)}$

Caclulating $A^{-1}\tilde{U}_{t}$

$\displaystyle A^{-1}\tilde{U}_{t}$
$\displaystyle=M^{-1}\tilde{U}_{t}-\frac{M^{-1}\tilde{U}_{g}\tilde{U}_{g}^{T}M^{-1}\tilde{U}_{t}}{\frac{1}{n_{2}}+\tilde{U}_{g}^{T}M^{-1}\tilde{U}_{g}}=M^{-1}(\tilde{U}_{t}-\beta\tilde{U}_{g})\text{
where constant
$\beta=\frac{\tilde{U}_{g}^{T}M^{-1}\tilde{U}_{t}}{\frac{1}{n_{2}}+\tilde{U}_{g}^{T}M^{-1}\tilde{U}_{g}}$}$
$\displaystyle=\frac{1}{\lambda}\begin{bmatrix}(u^{t}_{1}-\beta
u^{g}_{1})\left(1-\frac{(u^{t}_{1})^{2}}{C}\right)+\sum_{i=1,i\neq
1}^{d}-\frac{-u^{t}_{1}u^{t}_{i}}{C}(u^{t}_{i}-\beta u^{g}_{i})\\\
(u^{t}_{2}-\beta
u^{g}_{2})\left(1-\frac{(u^{t}_{2})^{2}}{C}\right)+\sum_{i=1,i\neq
2}^{d}-\frac{-u^{t}_{2}u^{t}_{i}}{C}(u^{t}_{i}-\beta u^{g}_{i})\\\ \vdots\\\
(u^{t}_{d}-\beta
u^{g}_{d})\left(1-\frac{(u^{t}_{d})^{2}}{C}\right)+\sum_{i=1,i\neq
d}^{d}-\frac{-u^{t}_{d}u^{t}_{i}}{C}(u^{t}_{i}-\beta u^{g}_{i})\\\
\end{bmatrix}$

For any row $k$ in the resultant matrix, while the first term will have
$sgn(u^{t}_{k}-\beta u^{g}_{k})$, each term in the summation given by
$\frac{-u^{t}_{k}u^{t}_{i}}{C}(u^{t}_{i}-\beta u^{g}_{i})$ has its sign
depending on many factors. Similarly, we can extend the analysis to true
ratings coming from any combination of clusters by finding the inverse
recursively per cluster rating block using the Sherman-Morrison update.

Thus with the exception of case 1, for any combination of cluster-wise
distribution of true ratings, all terms $a_{ki}u^{t}_{i}$ of any row $k$ of
the matrix $A^{-1}\tilde{U}_{t}$ ( equation 5) need not have the same sign and
the sign does not depend exclusively on $sgn(a_{kk}u^{t}_{k})$.

###  C.4. Proof of Theorem 2

###### Proof 13.

Given $A^{-1}$, let $N$ users from target cluster provide ratings. Then for
$\epsilon>0$ and $N\geq\frac{1}{\epsilon}$, we update the inverse by Sherman-
Morrison formula (Definition 2)

$\displaystyle\hat{A}^{-1}$
$\displaystyle=(A+N\tilde{U}_{t}\tilde{U}_{t}^{T})^{-1}=A^{-1}-\frac{A^{-1}\tilde{U}_{t}\tilde{U}_{t}^{T}A^{-1}}{\frac{1}{N}+\tilde{U}_{t}^{T}A^{-1}\tilde{U}_{t}}\leq
A^{-1}-\frac{A^{-1}\tilde{U}_{t}\tilde{U}_{t}^{T}A^{-1}}{\epsilon+\tilde{U}_{t}^{T}A^{-1}\tilde{U}_{t}}$

Now that we have $\hat{A}^{-1}$, we calculate $\hat{A}^{-1}\tilde{U}_{t}$ of
equation 4.

$\displaystyle\hat{A}^{-1}\tilde{U}_{t}$
$\displaystyle\leq\left(A^{-1}-\frac{A^{-1}\tilde{U}_{t}\tilde{U}_{t}^{T}A^{-1}}{\epsilon+\tilde{U}_{t}^{T}A^{-1}\tilde{U}_{t}}\right)\tilde{U}_{t}=\left(\frac{\epsilon
A^{-1}\tilde{U}_{t}}{\epsilon+\tilde{U}_{t}^{T}A^{-1}\tilde{U}_{t}}\right)$

We see that as $N\to\infty$, $\epsilon\to 0$ causing
$\hat{A}^{-1}\tilde{U}_{t}$ to converge to zero vector.

Now suppose, instead of the target cluster, users from any non-target cluster
$g$ provide the $N$ ratings; then we have

$\displaystyle\hat{A}^{-1}\tilde{U}_{t}$
$\displaystyle\leq\left(A^{-1}-\frac{A^{-1}\tilde{U}_{g}\tilde{U}_{g}^{T}A^{-1}}{\epsilon+\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{g}}\right)\tilde{U}_{t}=\left(A^{-1}\tilde{U}_{t}-\frac{A^{-1}\tilde{U}_{g}(\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{t})}{\epsilon+\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{g}}\right)=\left(\epsilon
A^{-1}\tilde{U}_{t}+C_{1}A^{-1}\tilde{U}_{t}-C_{2}A^{-1}\tilde{U}_{g}\right)$

where constants
$C_{1}=\frac{\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{g}}{\epsilon+\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{g}}$
and
$C_{2}=\frac{\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{t}}{\epsilon+\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{g}}$.
As $C_{1},C_{2}$ are non-zero constants with $sgn(C_{1})$ as positive and
$sgn(C_{2})$ depending on $sgn(\tilde{U}_{g}^{T}A^{-1}\tilde{U}_{t})$,
$\hat{A}^{-1}\tilde{U}_{t}$ might not converge to a zero vector.

##  Appendix D Additional Experimental Results

We look at a slightly modified hit-rate definition, defining an item to belong
to the recommended list if it has a predicted rating $>=4$. If the target item
after the attack satisfies this condition, we consider it a ’Hit.’ i.e, it may
be more likely for the target item to be now recommended to users of the
target cluster. We measure the Average Hits after the attack for the target
item and show the results when the adversary targets cluster 2. Results when
targeting other clusters are similar and so are not reported separately.

###  D.1. Fix $V$, Update $U$

From table 3, Average-Hits over all the target items calculated is $0$ for
both datasets for increasing ratios of $\frac{n}{m}$, indicating that the
attack is not able to push the rating high enough to be included in the
recommended list of items. i.e, the results of the attack here, do not
increase the predicted rating to $\geq 4$. This supports our results in the
main paper (figure 2), where the maximum mean relative change in rating
observed for $\frac{n}{m}=0.5$ was $<0.30$ i.e. for both datasets, predicted
rating increases only up to $30\%$ of maximum deviation possible.

$\frac{n}{m}$/Avg Hits | Before | After
---|---|---
$0.5$ | 0 | 0
$1.2$ | 0 | 0
$2.0$ | 0 | 0
(a) Movielens

$\frac{n}{m}$/Avg Hits | Before | After
---|---|---
$0.5$ | 0 | 0
$1.2$ | 0 | 0
$2.0$ | 0 | 0
(b) Goodreads

Table 3. Average Hits for Movielens dataset and Goodreads dataset reported
when target cluster is $t=2$ for the cluster-wise distribution of true users
$250-250-n-250$

###  D.2. Fix $U$, Update $V$

#### Varying Ratio of Target Item True Ratings ($N_{t}$) to Fake Ratings
($N_{f}$) in Target Cluster

Table 4 reports the average hits for the target item for increasing $N_{t}$
from the target cluster given $N_{f}$ fake ratings. We can see how the average
hit is highest for $\frac{N_{t}}{N_{f}}=0.05,0.5,1$ and drops to zero
afterward. This is in agreement with the observations from figure 5, where
$\frac{N_{t}}{N_{f}}=0.05,0.5,1$ showed a significant mean shift in the
predicted rating $>=0.5$ after the attack compared to the mean shift in the
predicted rating $<0.4$ for $\frac{N_{t}}{N_{f}}>1$. Therefore, the attack
increases the predicted rating to $\geq 4$, raising the chances of being
recommended to users of the target cluster, for decreasing
$\frac{N_{t}}{N_{f}}$.

$\frac{N_{t}}{N_{f}}$/Avg Hits | Before | After
---|---|---
$0.05$ | 0 | 1
$0.5$ | 0 | 1
$1$ | 0 | 1
$1.75$ | 0 | 0
$2.5$ | 0 | 0
(a) Movielens

$\frac{N_{t}}{N_{f}}$/Avg Hits | Before | After
---|---|---
$0.05$ | 0 | 1
$0.5$ | 0 | 1
$1$ | 0 | 1
$1.75$ | 0 | 0
$2.5$ | 0 | 0
(b) Goodreads

Table 4. Average Hits for Movielens dataset and Goodreads dataset reported
when target cluster is $t=2$ for the rating distribution of type
$0-0-N_{t}-0$.

####  Varying Ratio of Target Item True Ratings ($N_{t}$) to Fake Ratings
($N_{f}$) in Non-Target Clusters

Table 5 reports the average hits for target item for each dataset. We can see
how the average hit remains high for increasing $\frac{N_{t}}{N_{f}}$. This
agrees with the observations from figure 7, where increasing
$\frac{N_{t}}{N_{f}}$ showed larger mean shift in predicted rating of $>0.95$
after the attack increasing the predicted rating to $\geq 4$, thus raising the
chances of being recommended to users of target cluster.

$\frac{N_{t}}{N_{f}}$/Avg Hits | Before | After
---|---|---
$0.05$ | 0 | 1
$0.5$ | 0 | 1
$1$ | 0 | 1
$1.75$ | 0 | 1
$2.5$ | 0 | 1
(a) Movielens

$\frac{N_{t}}{N_{f}}$/Avg Hits | Before | After
---|---|---
$0.05$ | 0 | 1
$0.5$ | 0 | 1
$1$ | 0 | 1
$1.75$ | 0 | 1
$2.5$ | 0 | 1
(b) Goodreads

Table 5. Average Hits for Movielens dataset and Goodreads dataset reported
when target cluster is $t=2$ for the rating distribution of type
$N_{t}-N_{t}-0-N_{t}$.