{'fraction_non_alphanumeric': 0.04054819746440966, 'fraction_numerical': 0.007472200580777675, 'mean_word_length': 4.84466521784125, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ReuseKNN: Neighborhood Reuse for Privacy-Aware Recommendations

User-based KNN recommender systems ( UserKNN ) utilize the rating data of a target user’s 𝑘 nearest neighbors in the recommendation process. This, however, increases the privacy risk of the neighbors since their rating data might be exposed to other users or malicious parties. To reduce this risk, existing work applies differential privacy by adding randomness to the neighbors’ ratings, which reduces the accuracy of UserKNN . In this work, we introduce ReuseKNN , a novel privacy-aware recommender system. The main idea is to identify small but highly reusable neighborhoods so that (i) only a minimal set of users requires protection with differential privacy, and (ii) most users do not need to be protected with differential privacy, since they are only rarely exploited as neighbors. In our experiments on five diverse datasets, we make two key observations: Firstly, ReuseKNN requires significantly smaller neighborhoods, and thus, fewer neighbors need to be protected with differential privacy compared to traditional UserKNN . Secondly, despite the small neighborhoods, ReuseKNN outperforms UserKNN and a fully differentially private approach in terms of accuracy. Overall, ReuseKNN ’s recommendation process leads to significantly less privacy risk for users than in the case of UserKNN . ReuseKNN , to distill the impact of neighborhood reuse on recommendation accuracy and on the percentage of users that need to be protected with differential privacy, and (ii) neighborhood reuse with differential privacy, i.e., ReuseKNN 𝐷𝑃 , to investigate the practical benefit of neighborhood reuse for privacy-aware recommendations. We find that ReuseKNN and ReuseKNN 𝐷𝑃 can substantially reduce the number of users that need to be protected with DP, while outperforming related approaches in terms of accuracy. Also, we highlight that ReuseKNN 𝐷𝑃 effectively mitigates users’ privacy risk, as most users are rarely exploited in the recommendation process. Our work illustrates how to address privacy risks in recommender systems through neighborhood reuse combined with DP.


INTRODUCTION
Recommender systems often rely on collaborative filtering to generate recommendations [40,41]. User-based KNN, i.e., UserKNN, is a variant of collaborative filtering that utilizes the rating data of the nearest neighbors of a target user to process a rating query. A rating query is a request to a recommender system to predict a rating for a target user to a target item.
However, the way how rating queries are processed by UserKNN can increase the privacy risk of users since the estimated rating scores, i.e., recommendations, are generated based on rating data of users that are used as neighbors.
In this regard, existing research [15,70,90] finds that these neighbors are susceptible to multiple privacy risks, such as the inference of their private rating data. To mitigate that privacy risk, several works [34,56,92] use privacy-preserving Fig. 1. Schematic illustration of the privacy risk (i.e., how often a user is used as a neighbor) distribution of traditional UserKNN and the proposed ReuseKNN recommender system. ReuseKNN increases the number of secure users (no differential privacy needed) and decreases the number of vulnerable users (differential privacy needs to be applied) compared to UserKNN. The dashed line illustrates the privacy risk threshold , a hyperparameter for adjusting the maximum privacy risk for a user to be treated as secure.
techniques such as differential privacy (DP) [24,26] to protect users' rating data by adding a degree of randomness to the data. However, the added randomness typically leads to severe drops in recommendation accuracy [12].
To address this problem, we introduce ReuseKNN, a novel privacy-aware recommender system that reduces the number of neighbors to which differential privacy needs to be applied. Intuitively, instead of utilizing new users as neighbors for processing new rating queries, ReuseKNN reuses useful neighbors from past recommendations queries.
Hence, ReuseKNN constructs small but highly reusable neighborhoods for every target user by fostering the neighbors' reusability for many rating queries. With this, as illustrated in Figure 1, ReuseKNN minimizes the set of users that need to be protected with DP -we call them "vulnerable users". Plus, most users do not need to be protected with DP, as their rating data is only rarely used in the recommendation process -we call them "secure users". As shown, we also introduce a privacy risk threshold , i.e., a hyperparameter that allows adjusting the maximum privacy risk for a user to be treated as secure. In this way, we leave it to the recommender system provider to specify what privacy risk is tolerated and which users need to be protected.
We evaluate our approach in a two-stage procedure: (i) neighborhood reuse only, i.e., ReuseKNN, and (ii) neighborhood reuse with DP, i.e., ReuseKNN . In the first stage, ReuseKNN does not use DP at all. With this, we focus on how neighborhood reuse can increase the reusability of neighbors and preserve recommendation accuracy. In the second stage, we combine ReuseKNN with DP, i.e., ReuseKNN , to protect vulnerable users with DP. This allows investigating how ReuseKNN can mitigate all users' privacy risk while generating accurate recommendations. We evaluate ReuseKNN and ReuseKNN on five different datasets, i.e., MovieLens 1M, Douban, LastFM, Ciao, and Goodreads. Plus, we compare ReuseKNN and ReuseKNN to five baselines that utilize DP (e.g., [91]) and the concept of neighborhood reuse in different ways, with respect to recommendation accuracy and users' privacy risk. Additionally, the nature of neighborhood reuse may raise concerns that the generated recommendations are biased towards items preferred by popular users. Thus, we investigate whether our approach is more or less prone to item popularity bias than our baselines.

Manuscript submitted to ACM
Our results indicate that ReuseKNN yields significantly smaller neighborhoods than traditional UserKNN. Despite the smaller neighborhoods, ReuseKNN and ReuseKNN outperform our baselines in terms of recommendation accuracy.
Moreover, ReuseKNN leads to significantly less privacy risk for users than UserKNN with DP. Also, our approach does not increase item popularity bias. Overall, the three main contributions of this paper are as follows: (1) We present a novel ReuseKNN recommender system and compare several neighborhood reuse strategies to substantially foster the reusability of a target user's neighborhood and effectively reduce the number of vulnerable users.
(2) We combine ReuseKNN with DP to realize ReuseKNN and show that ReuseKNN improves recommendation accuracy over DP-based baselines, and at the same time, does not increase item popularity bias.
(3) We show that ReuseKNN leads to significantly less privacy risk, since most users are rarely exploited in the recommendation process and only the remaining users, i.e., vulnerable users, are protected with DP.
Our work illustrates how to address privacy risks in recommender systems through neighborhood reuse combined with DP.

RELATED WORK
We describe two research strands related to our work: (i) studies on the identification and quantification of users' privacy risks in recommender systems and (ii) privacy-aware recommender systems that mitigate users' privacy risks.

Privacy risks in recommender systems
Previous research [10,33,46,74,79] describes many severe privacy risks for users of recommender systems. For example, according to Ramakrishnan et al. [70], the use of neighbors' rating data in the recommendation process can pose a privacy risk to the neighbors. Serendipitous recommendations could reveal unique connections, i.e., sparse relationships [29], between neighbors and items. In this way, the rating data of the neighbors can be uncovered, or the neighbors' identities can be revealed within the recommendation database. Also, Zhang et al. [90] show that it could be possible to identify users whose data was used in the recommendation process. Their results suggest that the effectiveness of their attack depends on the number of generated recommendations. Moreover, Calandrino et al. [15] propose to generate fake users, i.e., sybils, based on limited knowledge of a victim's data. These sybils can isolate the victim that is utilized as a neighbor and compromise its privacy. However, this attack's effectiveness depends on the amount of knowledge of the victim's data [30] and strategies to weaken the attacks' effectiveness exist [56].
Privacy risk metrics. To quantify users' privacy risks in computational systems such as recommender systems, several privacy risk metrics [54,66,68,76,80,83] have been proposed. These metrics often rely on the sensitivity of users' data, i.e., how strong this data puts users' privacy at risk. For example, Chen et al. [19] detect correlations within the dataset to measure if a piece of data could reveal personal information about the users. Srivastava et al. [76] measure the relative sensitivity of a single piece of data compared to the remaining data of a user. Similarly, Domingo-Ferrer [23] relates the overall sensitivity of a user's data to the sensitivity of other users' data. Besides, Liu and Terzi's privacy score [54] weighs the sensitivity with the degree of visibility of a user's data (i.e., how often a user's data is utilized in the recommendation process).
Separation to our work. Evaluating the privacy risk of users based on attacks only measures the privacy risk with respect to the specific attack scenario. Liu and Terzi's metric measures users' privacy risk independent of specific attack Manuscript submitted to ACM scenarios and, thus, allows investigating privacy risk in a recommender system at a more general level. Therefore, in our work, we utilize Liu and Terzi's metric to measure users' privacy risk in a general neighborhood-based recommendation scenario. Furthermore, we assume that all pieces of data are equally sensitive, since sensitivity typically depends on the application and the user's perception of privacy [47,51,61].

Privacy-aware recommender systems
Several works [7,9,16,89] mitigate users' privacy risks by applying homomorphic encryption [35] to users' rating data. Here, recommendations are generated based on the encrypted rating data, and thus, users' rating data remains protected in the recommendation process. Homomorphic encryption, however, has high computational complexity. As a remedy, Kikuchi et al. [50] describe a variant of homomorphic encryption with lower privacy guarantees but improved efficiency. Also, Tang et al. [78] apply homomorphic encryption on the rating data of a target users' friends, i.e., a small subset of users, to improve computational efficiency. Besides homomorphic encryption, federated learning [59] is used to lower users' privacy risks [5,9,18,38,53,71]. Specifically, not a user's rating data is utilized in the recommendation process, but parameters of a user's local recommendation model. However, federated learning could be susceptible to attacks aiming to infer user data [65]. Thus, research proposes to learn a user's local model by utilizing only a minimal [6,64] or a user-selected subset of the rating data [20,88]. Moreover, differential privacy (DP) [24,26] and perturbation techniques [55,69] are leveraged for collaborative filtering recommender systems [3,17,34,56,92] with a focus on matrix factorization [13,32,45,60]. These techniques add randomness to users' data to hide the actual data.
Therefore, they face a trade-off between accuracy and privacy (e.g., [12]). To address this trade-off, Xin and Jaakkola [86] assume a moderate number of public users who tolerate disclosing their rating data. With this unprotected rating data, recommendation accuracy can be preserved while the privacy requirements of the remaining users are respected.
Popularity bias. Reusage of the same neighborhood for many rating queries may raise concerns that the generated recommendations are biased towards items of users that prefer popular items. Specifically, with this popularity bias, users receive more recommendations for popular items, and non-popular items receive less exposure than popular items. This disparate, i.e., unfair, treatment of popular and non-popular items has been thoroughly discussed in recent research [49,57,58,62]. In general, privacy and fairness are seen as two fundamental challenges of recommender systems research [22,63]. For example, Dwork et al. [25] and Zemel et al. [87] show that formally, there is a close connection between fairness and DP. However, the sole application of DP is not sufficient to ensure fairness due to correlations within the dataset [27]. Moreover, Ekstrand et al. [27] and Agarwal [4] highlight a trade-off between user privacy and algorithmic fairness. In detail, unfairness, such as, e.g., popularity bias, arises due to the fact that algorithms have difficulties to personalize when applied on data that is protected through DP [8,27]. Overall, related work suggests that DP can severely impact recommendations in different ways, for example, result in popularity bias. Therefore, we believe that it is important to test our approach, i.e., ReuseKNN, for item popularity bias.
Separation to our work. Similar to our work, previous research by Zhu et al. [91] prevents the inference of neighbors' rating data by applying DP to the users' rating data in UserKNN. However, to preserve recommendation accuracy, Zhu et al. vary the degree of randomness that is added to all users' rating data based on the sensitivity of the data.
In contrast, ReuseKNN preserves recommendation accuracy by adding randomness only where it is necessary, i.e., to vulnerable users with a high privacy risk. In the remainder of the paper, we denote one variant of the fully differentially private approach by Zhu et al. Full and use it as a baseline for our experiments.
Manuscript submitted to ACM Fig. 2. Schematic illustration of the recommendation process for three rating queries in Alice's query set for UserKNN and ReuseKNN. For simplicity, we set all users' privacy risk to − 1. Furthermore, a green shaded item indicates that the rating score for this item is estimated for the target user and a red shaded item indicates that the rating score of a neighbor has been utilized for the rating estimation. Traditional UserKNN selects those users as neighbors, that rated the queried item and have the highest similarity-value; in this toy example, those are Bob and Amy. Thus, Bob and Amy are vulnerable and need to be protected with DP. In contrast, ReuseKNN utilizes Tim as neighbor. As such, ReuseKNN substantially increases reusability (5.15 instead of 1.2 and 0.74), at the price of a slightly reduced similarity (0.90 instead of 0.98 and 0.97). This way, only Tim is vulnerable and is the only neighbor that needs to be protected with DP, as Bob and Amy remain unused.

APPROACH
In the following, we first describe traditional UserKNN (Section 3.1) and then outline the four neighborhood reuse strategies of our ReuseKNN recommender system (Section 3.2). Finally, we present ReuseKNN , i.e., ReuseKNN with differential privacy (DP) (Section 3.3). Moreover, a summary of the notation used in this paper is given in Table 1.
In Figure 2, we provide a schematic illustration of UserKNN 's and ReuseKNN 's recommendation process based on a simple example. For simplicity, we set all users' privacy risk to − 1. This means that with one additional rating query for which Bob, Amy, or Tim are utilized as neighbors, their privacy risk reaches the privacy risk threshold and thus, DP needs to be applied. To process Alice's rating queries for items and , UserKNN selects Bob and Amy as Table 1. Overview of the notation used in this paper.

Symbol Description
Number of neighbors to process a rating query for target user and target item . Rating queries for target user , i.e., the items in 's test set . R KNN recommender system utilizing neighbors to predict ratings. R ( , ) Estimated rating score for target user and target item by recommender system R .

R ( )
Items with the highest estimated rating score for target user .
, Rating score of user to item . The set of users.
The set of users that rated item .
The set of items.
The set of items rated by user . The set of ratings.

,
The nearest neighbors for target user and target item .
, Neighbors of target user and rated item . The set of neighbors for target user across all rating queries.
( ) The set of neighbors for target user across rating queries.
Similarity score between target user and neighbor . ( | ) Reusability score of candidate neighbor for target user .

(·)
The ranking function that ranks candidate neighbors w.r.t. similarity and reusability. Privacy risk threshold, i.e., the maximal privacy risk for a user to be treated as secure. Differentially privacy mechanism that utilizes plausible deniability. Secure users that do not need to be protected with DP. Vulnerable users that need to be protected with DP. Rating data of secure users. DP-protected rating data of vulnerable users. Significance level used for the statistical tests. Sample standard deviation of variable .
, Sample covariance of variables and .
neighbors, as they have the highest similarity-values across all users that rated the queried items. This causes Bob's and Amy's privacy risk to exceed the privacy risk threshold , which means that both are vulnerable, and, thus, need to be protected with DP. For the rating query for item , again, Amy is utilized in the recommendation process. Since she is already protected with DP, her privacy risk does not increase. This is different to how ReuseKNN processes rating queries. For the rating queries for items , , and , ReuseKNN selects Tim as neighbor, as Tim has a substantially higher reusability-value and only marginally smaller similarity than Bob and Amy. By using Tim for many rating queries, Tim's privacy risk exceeds , and DP is needed to protect Tim.
In summary, in this simple example, UserKNN leads to two vulnerable users, i.e., Bob and Amy, that need to be protected with DP. In contrast, ReuseKNN leads to only one vulnerable user, i.e., Tim, to which DP has to be applied.

UserKNN
Typically, a user-based KNN recommender system R , i.e., UserKNN, generates an estimated rating score for a rating query of a target user and a target item by utilizing the ratings of other users that have rated , i.e., the nearest Manuscript submitted to ACM neighbors , : where ( , ) is a similarity metric (e.g., cosine similarity) between target user and neighbor . For UserKNN, the neighborhood , used for generating recommendations for target user and item , comprises the most similar neighbors: where are all users that have rated and measures the similarity between two users. ReuseKNN differs from traditional UserKNN in exactly this point, i.e., how the neighbors are selected. In contrast to UserKNN, ReuseKNN also incorporates the neighbors' reusability for many rating queries of a target user, in addition to their similarity.

ReuseKNN
The key feature of ReuseKNN is to reuse neighbors from a target user 's previous rating queries to minimize the cardinality of the neighborhood = ∈ , across all rating queries . As illustrated in Figure 1, this means that ReuseKNN decreases the privacy risk of most users, i.e., secure users, and decreases the number of highly reused neighbors, i.e., vulnerable users.
In addition to the similarity, ReuseKNN also considers the extent to which a target user could reuse candidate neighbor as a neighbor for many rating queries, i.e., ( | ). Since both, similarity and reusability scores are differently distributed across their respective numeric ranges, we convert them to ranks. Formally, for a function , i.e., or , it holds that ( ) > ( ) if ( ) > ( ) for users and . In case that ( ) = ( ), we assign both users the same rank, i.e., ( ) = ( ). With this, the neighbors , are selected based on similarity and also, reusability, i.e., their merit in improving privacy. Formally: where are all users that rated item , measures the similarity between two users, and depends on the given neighborhood reuse strategy of ReuseKNN. In case multiple candidate neighbors have equal values for ( ( , )) + ( ( | )) we choose these neighbors at random.
To estimate a candidate neighbor's reusability, ReuseKNN utilizes our four neighborhood reuse strategies given in Figure 3. Implicit strategies create an artificial preference for selecting reusable neighbors by balancing candidate neighbors' similarity and reusability, as given in Equation 3. With explicit strategies, the recommender system prioritizes neighbors from previous rating queries over new neighbors. Hence, the neighborhood is only expanded when the pool of previous neighbors, i.e., the neighborhood, is insufficient to generate a new recommendation. Unpersonalized strategies measure a candidate neighbor's reusability for an average target user, whereas personalized strategies measure the reusability for a specific target user.

Implicit Neighborhood Reuse.
In the following, we discuss two strategies to increase the reusability of a target user's neighbors based on implicit neighborhood reuse.
Unpersonalized neighborhood reuse: Expect. The more users rated an item, the more likely it is that a random target user will query a rating estimation for this item. Following this intuition, Expect promotes candidate neighbors that rated  Fig. 3. Overview of our four neighborhood reuse strategies. For every strategy, there also exists a variant that protects vulnerable users with DP (in green). Implicit strategies create an artificial preference towards reusable neighbors, whereas explicit strategies only expand the neighborhood, if the neighborhood is insufficient to generate a new recommendation. Unpersonalized strategies measure a candidate neighbor's reusability for an average target user, whereas personalized strategies measure the candidate neighbor's reusability for a specific target user. many popular items and penalizes candidate neighbors that either rated only a few items or a lot of unpopular items.
For Expect, the reusability score of candidate neighbor is defined by: where is the target user, are the items rated, are the users that rated an item , and is the set of all users. In this case, ( ) is the summed-up popularity of 's rated items and measures the expected number of a random user's rating queries for which could be used as a neighbor. This means that the reusability of a candidate neighbor is estimated for an average user and not for a specific target user (i.e., unpersonalized).
Personalized neighborhood reuse: Gain. In contrast to unpersonalized neighborhood reuse, Gain measures a candidate neighbor's reusability for a specific target user. In detail, Gain quantifies how many of a target user's ratings a candidate neighbor could have covered in the past, i.e., how many ratings the target user could have gained from the candidate neighbor. Thus, Gain gives the fraction of a target user 's rated items, for which a candidate neighbor could have served as a neighbor: where are the items rated by and are the items rated by . In contrast to our unpersonalized Expect strategy, Gain's reusability score depends on a specific target user (i.e., personalized).

Explicit Neighborhood
Reuse. Explicit neighborhood reuse strategies extend our implicit neighborhood reuse strategies by prioritizing previous neighbors over new neighbors. This extension results in two explicit neighborhood reuse strategies: Expect+Reuse (unpersonalized), and Gain+Reuse (personalized).
Specifically, explicit neighborhood reuse strategies only expand a user's neighborhood if it comprises too few neighbors to generate a recommendation. More formally, if neighbors are necessary to generate an estimated rating score for an item and the neighborhood of , i.e., = ∈ , , among all rating queries , already includes at least neighbors that rated , i.e., | , | ≥ , then ReuseKNN does not add any new neighbors and selects those users as neighbors that are already in , : If too few neighbors could be reused for the rating query for item , i.e., | , | < , then only the minimal required number of new neighbors ′ = max{ − | , |, 0} is added by using the ( | ) definition of either our Expect (cf. Equation 4) or Gain (cf. Equation 5) strategy. Formally: where are all users that rated item . In this way, only ′ new neighbors are selected as in implicit neighborhood reuse strategies, i.e., by balancing similarity and reusability (cf. Equation 3).

ReuseKNN
ReuseKNN leads to a minimal number of highly reused neighbors, i.e., vulnerable users, with a privacy risk that exceeds the privacy risk threshold . ReuseKNN addresses this high privacy risk of vulnerable users by adding DP to our neighborhood reuse strategies in Figure 3. Specifically, for a rating query for user and item , a privacy mechanism is applied to the ratings for of vulnerable users that are used as neighbors, i.e.,˜= { ( , ) : ∈ , ∩ }. In this way (see Equation 8), ReuseKNN utilizes real ratings of secure users , i.e., = { , : ∈ , }, plus the modified ratings˜of vulnerable users, to generate the estimated rating score R ( , ).
In detail, privacy mechanism utilizes randomized responses [36,84] to achieve DP [26]. With this, intuitively, neighbors can plausibly deny that their real rating was used in the recommendation process. Privacy mechanism flips a fair coin and if the coin is heads, the vulnerable neighbor's real rating is utilized in the recommendation process.
If the coin is tails, flips a second fair coin to decide whether to utilize the vulnerable neighbor's real rating or a random rating drawn from a uniform distribution over the range of ratings. With this, an attacker is unaware whether the utilized rating is real, or random, which leads to the privacy-guarantees within the DP-framework [26].

EXPERIMENTAL SETUP
We utilize a two-stage evaluation procedure to compare and evaluate the four neighborhood reuse strategies of (i) ReuseKNN, and (ii) ReuseKNN (cf. Figure 3): Neighborhood reuse only: ReuseKNN. In the first stage, we evaluate ReuseKNN without protecting vulnerable neighbors with DP in order to better understand the advantages and disadvantages of different neighborhood reuse strategies.
Hence, we compare Expect, Gain, Expect+Reuse, and Gain+Reuse, and with this, we distill the impact of neighborhood reuse for recommendations.
Neighborhood reuse with DP: ReuseKNN . In the second stage, we combine ReuseKNN with DP to protect vulnerable users, i.e., ReuseKNN , and compare the neighborhood reuse strategies Expect , Gain , Expect+Reuse , and Gain+Reuse . With this, we investigate how ReuseKNN can address the trade-off between accuracy and privacy. For ReuseKNN , i.e., neighborhood reuse with DP, we use three DP baselines: (1) UserKNN : A variant of UserKNN without neighborhood reuse, but DP is applied only to vulnerable users -in contrast to Full [91], where it is applied to all users. The privacy threshold is set to the same value as in the case of our ReuseKNN variants (see Section 4.5).
(2) UserKNN+Reuse : Explicit neighborhood reuse is combined with UserKNN . Neighbors from previous rating queries are prioritized over new neighbors. DP is applied to only vulnerable users. Please see Section 4.5 for the exact values per dataset.
(3) Full : Fully differentially private UserKNN without neighborhood reuse, based on [91]. DP is applied to all users -in contrast to UserKNN , where it is applied only to vulnerable users. This corresponds to = 0.
In addition to our three DP baselines, we use our non-DP UserKNN to evaluate ReuseKNN . With this, we can compare ReuseKNN to two contrastive baselines: Full , which protects all users with DP, and UserKNN, which does not protect any user with DP.

Evaluation Criteria
We test our approach using the following evaluation criteria and metrics (see Table 2 for an overview): For every rating query of a target user , neighbors are required to generate the recommendation. In the worst case, no neighbors from previous rating queries can be reused. Thus, after queries, | | = min{ · , | | − 1} for being the set of all users. In the best case, reuses the same neighbors for all queries, i.e., | | = . To quantify how many of 's neighbors are reused, we measure the size of 's neighborhood after rating queries: where ( ) is 's set of neighbors after rating queries. With that, we test how well the neighborhood reuse strategies of ReuseKNN, i.e., neighborhood reuse only, can reuse a target user's neighbors for many rating queries.

Neighborhood
Reliability. As discussed earlier, our ReuseKNN recommender system limits the growth of a target user's neighborhood. However, this utilization of fewer neighbors across many rating queries might impact the accuracy of recommendations. Therefore, we test if a target user's neighborhood includes neighbors that are beneficial for recommendation accuracy, i.e., "reliable" neighbors. As several works suggest, one important characteristic of these reliable neighbors is the number of co-rated items with the target user [2,40,67]. Thus, we measure the average number of co-rated items between a target user and its neighbors ∈ after rating queries: where are the items rated by target user and are the items rated by neighbor . With this, we test how reliable the neighborhoods are for generating accurate recommendations.

Accuracy.
To quantify the accuracy of a target user's recommendations, we rely on the widely-used mean absolute error metric (MAE) [85]. According to [40,41], the number of neighbors has an impact on the recommendation accuracy. Thus, we test the accuracy of 's recommendations for ∈ {5, 10, 15, 20, 25, 30}. Therefore, MAE@ ( ) quantifies the accuracy of 's recommendations when neighbors are used to generate a recommendation. More formally: where the predicted rating score R ( , ) is compared to the real rating scores , ∈ in 's test set. We note that the items for which comprises ratings are the ones that are in 's set of rating queries . We use the MAE@ ( ) metric for evaluating both, ReuseKNN, i.e., neighborhood reuse only, and ReuseKNN , i.e., neighborhood reuse with DP.

Privacy Risk.
Liu and Terzi [54] provide a framework to measure a user's privacy risk in computational systems such as recommender systems based on the visibility of the user's data. In our work, we relate this visibility to how often a user's rating data was utilized in the recommendation process. As such, our PrivacyRisk@ ( ) metric counts for how many rating queries a user was used as a neighbor. Similar to MAE@ ( ), we also relate 's privacy risk to the number of neighbors used to generate recommendations. Formally: where is the set of all users, is the set of items for which user queries estimated ratings, and 1 , ( ) is the indicator function of user being in 's set of neighbors , for an item .
Percentage of Vulnerable Users. As mentioned earlier, the main goal of neighborhood reuse is to reduce the number of users that need to be protected with DP. Our PrivacyRisk@ definition allows us to identify these vulnerable users , i.e., the set of users whose privacy risk exceeds the adjustable privacy risk threshold given by: where is the set of all users. Thus, the percentage of vulnerable users relates to what fraction of users DP has to be applied to (i.e., | |/| |). We use this metric to evaluate ReuseKNN, i.e., neighborhood reuse only.
Privacy Risk When DP is Applied. We apply DP to a user 's data if PrivacyRisk@ ( ) > (cf. Section 3.3). In practice, the privacy risk of protected neighbors can not increase any further. To account for this, we set the upper limit of a user 's privacy risk when DP is applied to , i.e., We use PrivacyRisk @ to measure the users' privacy risk when neighborhood reuse is combined with DP, i.e., ReuseKNN .

Item Popularity Bias.
One might be concerned that reusing the same set of neighbors for many rating queries could lead to using only users as neighbors who have rated many popular items, which could result in more positive estimated rating scores for popular items. To test for this item popularity bias, we analyze all items for which the recommender system estimates high rating scores. In the remainder of this work, we refer to these items as "top items". For a recommender system model R and neighbors, a user 's set of top items is given by: , where are the items in 's query set. In our case, we set = 10.
Positivity-Popularity Correlation. To study if ReuseKNN exhibits a pattern in which higher estimated rating scores are given to popular items, we follow the methodology of Kowald et al. [52]. Specifically, we correlate an item's popularity with the number of times the item occurs in users' set of positive items: where 1 R ( ) ( ) indicates whether item is in user 's set of top items R ( ). Plus, the popularity of item is given by: ItemPop(i) = | |/| |, where is the set of all users and are the users that rated . We compute the Pearson correlation coefficient [11] between the two variables ItemFreq + and ItemPop to identify item popularity bias: where ItemFreq + @ ,ItemPop@ is the sample covariance between ItemFreq + @ and ItemPop@ . Furthermore, the sample standard deviations are given by ItemFreq + @ and ItemPop@ .
Item Coverage. In addition to evaluating the correlation between an item's estimated rating score and its popularity, we also measure for what fraction of the item catalog the recommender system is able to estimate high rating scores. For this, we use the Item Space Coverage metric [42,48,75] given by: where is the number of neighbors, is the set of items, is the set of users, and R ( ) is the set of top items for user . This way, we can test whether parts of the item catalog always receive low estimated rating scores. We use Table 3. Descriptive statistics of our five datasets. | | is the number of users, | | is the number of items, | | is the number of ratings, | |/ | | is the rating-to-user ratio, | |/ | | is the user-to-item ratio, and Density is given by | |/( | | | |).
All five datasets exhibit different properties, as illustrated in Table 3. Overall, our datasets cover (i) the movie, music, and book domain, (ii) implicit and explicit feedback, and (iii) different descriptive statistics. Moreover, we utilize datasets used in both, recommender systems and information retrieval research [53].

Evaluation Protocol & Statistical Tests
We perform all experiments using 5-fold cross-validation, and randomly split all folds into 80% training sets and 20% test sets . The ratings in are used to train the recommendation algorithms, and the ratings in represent the rating queries used for evaluation. Also, we perform several statistical tests to measure the significance of our results. Specifically, after close inspection of our results, we resort to the Mann-Whitney-U-Test. For our query-based metrics Neighbors@ and CoRatings@ , we evaluate significance for all rating queries ∈ [1; 100] when utilizing = 10 neighbors. For other metrics, i.e., MAE@ , PrivacyRisk @ , PP-Corr@ , and Coverage@ , we evaluate significance after all queries have been processed by the recommender system. Again, here, we utilize = 10 neighbors to generate recommendations. Importantly, we only report statistical significance if we observe significance for each of our five folds.

Parameter Settings
Our approach relies on two adjustable hyperparameters, i.e., (i) the number of neighbors used for generating UserKNN 's privacy risk distribution, which is given by its maximal second derivative (see Figure 1).
This way, we assume that only the tail's small privacy risk is tolerable and give an example of how can be defined by the recommender system provider. Also, is the same for all users. This leads to the following values for = 10:

RESULTS & DISCUSSION
We structure our results into two parts: (i) neighborhood reuse only (ReuseKNN ), and (ii) neighborhood reuse with DP (ReuseKNN ).

ReuseKNN
In this section, we present our evaluation results for ReuseKNN, i.e., neighborhood reuse only. However, for Ciao, we find that multiple rating queries are needed to generate a reusable neighborhood. For Gain applied to the Ciao dataset, we do not observe significant differences. In contrast, our remaining neighborhood strategies tend to yield significantly smaller neighborhoods for a few rating queries. We attribute this to the on average small user profiles in Ciao (cf. Table 3). Reusable neighbors are scarce and thus, ReuseKNN cannot reduce the neighborhood size as effectively as in the case of the other datasets.

Neighborhood Growth.
Interestingly, for all datasets, our explicit neighborhood reuse strategies generate smaller neighborhoods than their implicit counterparts. We underline that explicit neighborhood reuse prioritizes neighbors from previous rating queries over new neighbors and, thus, limits the neighborhood size more strictly than implicit neighborhood reuse.

Neighborhood
Reliability. Similar to the neighborhood growth in Figure 4, Figure 5 illustrates the average number of co-rated items between the target user and its neighbors after querying rating queries. For all our five datasets, all our neighborhood reuse strategies can substantially increase the co-ratings over traditional UserKNN. A one-tailed Mann-Whitney-U-Test ( = 0.01) shows that all our neighborhood reuse strategies generate neighborhoods with significantly more co-ratings with the target user than UserKNN for ∈ [2; 100] rating queries. This indicates that ReuseKNN generates neighborhoods that comprise less, but more reliable neighbors than in case of traditional UserKNN, which can foster recommendation accuracy [2,40,67].
However, for Ciao, our neighborhood reuse strategies tend to generate significantly more reliable neighborhoods for only a few rating queries. As in our neighborhood growth experiment, we attribute this to the small user profiles in Ciao, which makes neighborhood reuse less effective due to the scarcity of reusable neighbors.
Moreover, for all datasets, explicit neighborhood reuse strategies generate more reliable neighborhoods than implicit neighborhood reuse strategies. We suppose that this is caused by the small neighborhoods that are generated by explicit neighborhood reuse strategies (see Section 5.1.1). Specifically, the smaller the neighborhood, the easier it is to identify reliable neighbors with a large rating overlap with the target user. Figure 6, we compare ReuseKNN to traditional UserKNN in terms of recommendation accuracy.

Accuracy. In
Here, we find that our neighborhood reuse strategies can generate more accurate recommendations than UserKNN. This shows that reusing neighbors that have already been used in the past for calculating meaningful recommendations, also leads to meaningful (accurate) recommendations in the future.
Specifically, for ML 1M, Douban, and LastFM, a one-tailed Mann-Whitney-U-Test ( = 0.01) indicates that all our neighborhood reuse strategies significantly increase recommendation accuracy for a model with = 10 neighbors. Due to personalization, Gain and Gain+Reuse perform best across most datasets.
For LastFM, the unpersonalized neighborhood reuse strategies Expect and Expect+Reuse outperform our personalized neighborhood reuse strategies Gain and Gain+Reuse. We attribute this to LastFM's small user-to-item ratio as compared to the other datasets (cf. Table 3). This makes it hard to identify neighbors, similar to an item-cold start scenario [72].
Concretely, in the case of personalized neighborhood reuse, selecting reusable neighbors for a specific target user reduces the pool of potential neighbors per item to a personalized subset and leads to a worse performance compared to unpersonalized neighborhood reuse. In contrast, our unpersonalized neighborhood reuse strategies allow using the entire pool of potential neighbors and thus achieve a higher recommendation accuracy for LastFM.
In the case of our least dense datasets Ciao and Goodreads, we observe that our personalized neighborhood reuse strategies Gain and Gain+Reuse can handle these datasets better than our unpersonalized neighborhood reuse strategies Expect and Expect+Reuse. Our personalized neighborhood reuse strategies select neighbors, whose rating data could Manuscript submitted to ACM have been used by the target user in the past (cf. Equation 5). This way, Gain and Gain+Reuse create a neighborhood for a given target user with sufficient rating data even in sparse datasets.
Plus, we highlight that Gain and Gain+Reuse significantly increase recommendation accuracy for Goodreads, despite the dataset's low density. In the case of Ciao, a two-tailed Mann-Whitney-U-Test ( = 0.01) reveals no significant differences between our neighborhood reuse strategies and UserKNN for = 10, which suggests that all our neighborhood reuse strategies can preserve recommendation accuracy. As shown in Figure 4 before, neighborhood reuse is less effective for Ciao due to the small user profiles. Thus, it makes sense that the recommendation accuracy cannot be improved as effectively as for the remaining datasets.

Percentage of Vulnerable Users.
In Table 4 For Ciao, our neighborhood reuse strategies achieve only minor improvements over UserKNN. The reason is that UserKNN already yields a small percentage of vulnerable users and as such, ReuseKNN leads to only small improvements.
Additionally, our previous findings show that the effect of neighborhood reuse on Ciao is smaller than on the remaining datasets due to the small average user profile size (cf. Table 3). This leads to a lack of reusable neighbors and, thus, also limits the effect neighborhood reuse has on the percentage of vulnerable users.

Summary.
Overall, we find that ReuseKNN can significantly reduce the size of target users' neighborhoods by neighborhood reuse. In particular, explicit neighborhood reuse yields smaller neighborhoods than implicit neighborhood reuse, since it prioritizes neighbors from previous rating queries over new neighbors and as such, limits the size of a target user's neighborhood more strictly than implicit neighborhood reuse.
Despite the much smaller neighborhoods, ReuseKNN identifies neighbors that have many more co-rated items with the target user than in the case of UserKNN. As related work shows, these reliable neighbors can be crucial for recommendation accuracy [2,40,67].
Based on the much smaller but more reliable neighborhoods, ReuseKNN can generate recommendations with significantly higher accuracy than traditional UserKNN. However, for sparse datasets, personalized neighborhood reuse seems to be a better solution than unpersonalized neighborhood reuse. UserKNN . Similar to our previous results without DP, our neighborhood reuse strategies can preserve or even improve recommendation accuracy. This shows that reducing the number of users to which DP has to be applied can help to increase recommendation accuracy.
Plus, ReuseKNN can substantially reduce the percentage of vulnerable users with high privacy risk. In general, our Except neighborhood reuse method yields the least vulnerable users.

ReuseKNN
Next, we present our results on ReuseKNN , i.e., neighborhood reuse with DP.

Accuracy. For
ReuseKNN, we showed that our neighborhood reuse strategies can preserve, and in many cases significantly improve, the recommendation accuracy over traditional UserKNN. However, in the following, we discuss whether these findings also hold for a combination of ReuseKNN and DP, i.e., ReuseKNN .
In Figure 7, we compare ReuseKNN 's recommendation accuracy to UserKNN 's. Similar to the non-DP experiment shown in Figure 6, our neighborhood reuse strategies can generate more accurate recommendations than UserKNN .
For ML 1M and LastFM, a one-tailed Mann-Whitney-U-Test ( = 0.01) indicates that all our neighborhood reuse strategies significantly increase recommendation accuracy for a model with = 10 neighbors. Additionally, for ML 1M, Gain and Gain+Reuse perform better than our non-DP baseline UserKNN.
Moreover, we observe that LastFM is highly sensitive to the incorporation of DP, since the mean absolute error magnitudes differ substantially between our non-DP experiment in Figure 6 and our DP experiment in Figure 7.
In line with our previous results on non-DP ReuseKNN, also ReuseKNN 's unpersonalized neighborhood reuse strategies Except and Except+Reuse cannot increase recommendation accuracy for Ciao and Goodreads, which are our two sparsest datasets. However, our personalized neighborhood reuse strategies Gain and Gain+Reuse generate recommendations with significantly higher accuracy for Goodreads. For Ciao, no significant differences are . Logarithm (base 10) of the privacy risk averaged over all users. All our neighborhood reuse strategies yield lower privacy risk than UserKNN . This is due to the fact that ReuseKNN reduces the percentage of users with a privacy risk of (i.e., vulnerables) and simultaneously, decreases the privacy risk of the remaining users (i.e., secures). Overall, we find that our unpersonalized neighborhood reuse strategies Expect and Expect+Reuse achieve the best user privacy.
found according to a two-tailed Mann-Whitney-U-Test ( = 0.01). Thus, Gain and Gain+Reuse can preserve recommendation accuracy.
For Douban, we observe no significant differences between our neighborhood reuse strategies and UserKNN . We found empirically that for Douban, UserKNN and ReuseKNN utilize more rating data from vulnerable users, than in case of our remaining datasets. Thus, we measure the fraction of rating data, each user contributes to the dataset, i.e., | |/| |, where are all users' ratings and are user 's ratings. We find that for Douban, the 5% of users with the largest user profiles contribute substantially more ratings to the dataset than for our other datasets, i.e., 0.0008 (ML 1M), 0.0022 (Douban), 0.0012 (LastFM), 0.0009 (Ciao), and 0.0003 (Goodreads). This suggests that in the case of Douban, the recommendation process more often utilizes these users due to their abundance of rating data. This, however, makes these users more vulnerable. Therefore, we suppose that this strong utilization of DP-protected rating data from vulnerable users leads to no significant differences in accuracy between UserKNN and ReuseKNN .
We additionally compare ReuseKNN to Full . Our results suggest that our personalized reuse strategies Gain and Gain+Reuse generate recommendations with significantly higher accuracy, while Except and Except+Reuse show no significant differences. Thus, all our neighborhood reuse strategies can preserve recommendation accuracy for this dataset.

Privacy Risk
When DP is Applied. In ReuseKNN , vulnerable users with high privacy risk are protected with DP and as such, their privacy risk is set to the privacy risk threshold as realized with our PrivacyRisk metric. Moreover, secure users' privacy risk is also reduced since they are rarely exploited as neighbors in the recommendation process (cf. Figure 1). Additionally, a one-tailed Mann-Whitney-U-Test ( = 0.01) reveals that for ML 1M, Douban, Ciao, and Goodreads, these differences are significant. Thus, for secure users, Expect yields a substantially smaller privacy risk than UserKNN .

Positivity-Popularity Correlation.
We test for item popularity bias in ReuseKNN 's recommendations by measuring the Pearson correlation between an item's popularity and its occurrences in users' sets of top items, i.e., the items with the highest estimated rating score (see Table 5).
For ML 1M, Douban, LastFM, and Ciao, the non-DP baseline UserKNN yields weaker popularity bias than all baselines and neighborhood reuse strategies that use DP. This fits well to related research [27] that argues that popularity bias can arise due to the recommender system's inability to personalize recommendations when DP is applied to user data. However, for ML 1M, Douban, LastFM, and Goodreads, our neighborhood reuse strategies can generate less popularity-biased recommendations than our DP-baseline UserKNN . For ML 1M, Douban, and Goodreads, this difference is also statistically significant according to a one-tailed z-test on the z-transformed correlation coefficient [28,43,93] as indicated by ** ( = 0.01). We investigate this in more detail and find that the neighbors identified by ReuseKNN have on average a larger user profile size (i.e., more distinct items) than the neighbors identified by UserKNN . As shown by related work on item popularity bias in recommender systems (e.g., [1,52]), users with a larger user profile size tend to consume less popular items, which leads to less popularity bias.
However, for Ciao, no notable differences can be observed. We again attribute this to the small number of ratings per user in this dataset (cf. Table 3). With this, neighborhood reuse is less effective and consequently, has only a small impact on the generation of recommendations. Thus, for our Ciao dataset, neighborhood reuse has no effect on item popularity bias.

Item Coverage.
In addition, we also evaluate if ReuseKNN can estimate high rating scores only for a limited set of items. In Table 6, we present the percentage of items from the entire item catalog that occur within users' sets of top items.
For ML 1M, Douban, Ciao, and Goodreads, our neighborhood reuse strategies cover larger parts of the item catalog than traditional UserKNN . This means that many items can receive high estimated rating scores. Specifically, Expect yields the highest item coverage values across our neighborhood reuse strategies.
In case of LastFM, we observe that all our neighborhood reuse strategies estimate high estimated rating scores for fewer items than UserKNN . However, we underline that the item coverage values for LastFM are negatively correlated with our accuracy results in Figure 7. This indicates that for LastFM, there is a trade-off between recommendation accuracy and item coverage, similar to the well-known trade-off between precision and recall [14,73].
However, it is noteworthy that for most datasets, Full yields the highest item coverage and our non-DP baseline UserKNN yields the lowest item coverage. This makes sense, since Full protects all rating data with DP and thus, the estimated rating scores are more random than for the remaining approaches. Consequently, this leads to more randomized recommendations, and thus, to high item coverage [31].

Summary.
Overall, our results are in line with the previously presented results for our non-DP ReuseKNN. Through neighborhood reuse, and thus, reducing the number of users that need to be protected with DP, recommendation accuracy can be preserved, and in many cases even significantly improved over UserKNN .
Also, we underline that all our neighborhood reuse strategies used in ReuseKNN lead to significantly smaller privacy risk than UserKNN . In particular, our unpersonalized neighborhood reuse method Except performs best in increasing user privacy. This shows that the combination of neighborhood reuse and DP provides higher privacy than UserKNN . This provides evidence that ReuseKNN does not increase item popularity bias.

Discussion
We find that ReuseKNN can preserve recommendation accuracy and, in many cases, even improve recommendation accuracy over UserKNN . At the same time, ReuseKNN leads to significantly smaller privacy risk than UserKNN , due to the small number of neighbors to which DP has to be applied. Besides, ReuseKNN does not increase item popularity bias over traditional UserKNN .
In Table 7, we illustrate a condensed summary of experimental results for all our evaluated approaches, i.e., UserKNN and ReuseKNN, UserKNN , ReuseKNN , and Full . Specifically, we present the accuracy (i.e., MAE@ ) and average privacy risk (i.e., PrivacyRisk @ ) values for a model with = 10 neighbors.
Overall, we can observe that non-DP UserKNN results in low MAE, but high privacy risk values. This shows that approaches without DP sacrifice a user's privacy for recommendation accuracy. However, our neighborhood reuse strategies with DP provide a less serious trade-off between recommendation accuracy and privacy.
Thus, in the following, we discuss advantages and disadvantages of our neighborhood reuse strategies for our five datasets. Across all our neighborhood reuse strategies, in general, personalized neighborhood reuse (i.e., Gain and Gain+Reuse ) provides the best recommendation accuracy. Plus, unpersonalized neighborhood reuse (i.e., Expect and Expect+Reuse ) yields the lowest privacy risk. For Douban and LastFM, Expect performs best in both, accuracy and privacy risk. Thus, in this case, Expect is well suited to provide accurate and private recommendations. For ML 1M, Ciao, and Goodreads, no neighborhood reuse strategy provides the best result in both categories. Thus, it depends on the recommender system service provider to decide what strategy could be utilized.

CONCLUSION
In this work, we investigate the efficacy of neighborhood reuse for privacy-aware recommendations in user-based KNN recommender systems. We discuss our approach in a two-stage evaluation procedure: (i) neighborhood reuse only, i.e., ReuseKNN, to distill the impact of neighborhood reuse on recommendation accuracy and on the percentage of users that need to be protected with differential privacy, and (ii) neighborhood reuse with differential privacy, i.e., ReuseKNN , to investigate the practical benefit of neighborhood reuse for privacy-aware recommendations. We find that ReuseKNN and ReuseKNN can substantially reduce the number of users that need to be protected with DP, while outperforming related approaches in terms of accuracy. Also, we highlight that ReuseKNN effectively mitigates users' privacy risk, as most users are rarely exploited in the recommendation process. Our work illustrates how to address privacy risks in recommender systems through neighborhood reuse combined with DP.
Limitations. We recognize the following limitations of our approach: To quantify the privacy risk, we assume that all pieces of data are equally sensitive. In reality, disclosing a particular piece of information could pose a different level of privacy risk than disclosing another piece of information [47,51,61]. Also, our experiments quantify how well ReuseKNN can predict ratings for target user-item pairs, i.e., rating prediction. A logical next step would be to move from a rating prediction task to a ranking-based recommendation task, i.e., top-recommendation, i.e., top-n recommendations [77]. Furthermore, we focused on a single family of recommendation algorithms, i.e., user-based KNN, because our main goal was not to beat state-of-the-art recommendation algorithms but to illustrate the benefit of a neighbor reuse concept for differentially private recommendations. Moreover, Dacrema et al. [21] showed that many modern recommendation algorithms, e.g., deep learning, can be outperformed by traditional algorithms such as user-based KNN. This means that this type of algorithm is still very relevant for the recommender systems community.
Future Work. In this work, we have focused on rating prediction and recommendation accuracy. For our future work, we plan to evaluate our approach in a top-recommendation task, and in terms of beyond-accuracy performance metrics (e.g., diversity). Also, while we evaluated our approach using five datasets of three different recommendation domains (movies, books, and music), future work will consider additional, more sensitive domains, such as, medicine, finance, insurance, or recruiting. Finally, we plan to evaluate our ReuseKNN approach for different user groups that differ in their inclination to popular content, e.g., using the dataset provided in our previous research on fairness in music recommender systems [52]. With this, we can study the impact of neighbor reuse and differential privacy on an individual user's preference towards long-tail items. Hence, our long-term plan is to investigate the interaction between privacy and fairness, two important aspects of trustworthy recommender systems.