Operationalizing the Legal Principle of Data Minimization
for Personalization

Article 5(1)(c) GDPR requires that personal data be ‘adequate, relevant and limited to what is necessary in relation to the purposes for which they are processed.’ Data minimisation is the direct consequence of the legal principle of purpose limitation, which requires that personal data only be processed for specified, explicit and legitimate purposes and not further processed in a manner incompatible with these purposes. While these core data protection principles cannot be examined exhaustively here, it is worth noting that general statements such as ‘improving user experience’ are generally not specific enough to meet the legal threshold of purpose limitation. This raises the question of whether ‘personalization’can be a purpose under the GDPR at all.

According to data minimisation, no more personal data than necessary to achieve the purpose can be processed. The first question to ask is thus whether data such as this studied in our paper is personal data. The Article 4 GDPR embraces a very broad definition of personal data as ‘any information relating to an identified or identifiable natural person.’In the past, movie ratings such as those in the MovieLens 20M dataset (Harper and Konstan, 2016) have been shown to allow for identification through linking of private and public datasets (Narayanan and Shmatikov, 2008). It is thus safe to assume that much of the data used in recommender systems, such as movie ratings, constitutes personal data and is hence subject to the GDPR (where within its geographical scope).

Data minimisation can be broken down into three distinct requirements. First, data must be adequate in relation to the purpose that is pursued. Arguably, adequacy is the most interesting of the three criteria as it may actually (and somewhat counterintuitively) require that more data is processed. It is well established that the omission of certain data can limit the usefulness of a dataset and the accuracy of an analysis done on that dataset. As such, to achieve accurate results, more data may need to be collected. Data minimisation indeed ought to be interpreted in light of the other substantive requirements in Article 5 GDPR such as fairness, transparency and accuracy and there are scenarios, often those involving underrepresented groups, where this can only be achieved through the processing of more personal data.

Second, data ought to be relevant in light of the purpose, meaning that only data that is pertinent for the purpose can be processed. For example, if an e-commerce provider requested users’ date of birth to provide personalised recommendations regarding future purchases, this data is unlikely to be relevant (except where recommendations have an astrological flavor). Relevance thus functions as a safeguard against accumulating data simply for the sake of doing so.

Third, the GDPR requires that data be limited to what is necessary, meaning that controllers ought to identify the minimum amount of personal data required to fulfil the stated purpose. Thus, where similarly robust results can be achieved through the processing of less personal data, the processing of personal data can likely not be accepted as being necessary. Where possible, only anonymised data should be used. However, given the practical limitations of achieving anonymisation, the latter cannot be assumed as a viable alternative to minimisation in many contexts (Finck and Pallas, 2019).

Our focus in this paper is on operationalizing the third requirement of data minimization, namely that of limitation. According to the legal considerations detailed in the previous subsection, generic statements such as ‘improving user experience’ are not specific enough to be used as a purpose of data collection. Thus, we propose to reason about data minimization by tying the purpose to performance metrics. While there are many ways in which this proposition might be operationalized, in this paper, we begin investigating this space with an empirical study of two definitions.

Let $\mathcal{U}$ be a set of users for whom the system needs to minimize the data and let $\mathcal{I}$ be the set of items that a system can recommend. Each user has rated some subset $\mathcal{I}_{u}\subseteq\mathcal{I}$ of items. Let $r_{u}$ be the $|\mathcal{I}|\times 1$ vector of ratings for these items. Of the rated items in $\mathcal{I}_{u}$, in a minimization setting, the system only sees a subset $\tilde{\mathcal{I}}_{u}\subseteq\mathcal{I}_{u}$, referred to as the observational pool for user $u$. Let $\hat{r}_{u}$ be the ratings for these observations. Given $\hat{r}_{u}$, a system generates $\tilde{r}_{u}$, its predicted ratings for $u$. The quality metric for $u$ is defined as $\sigma(\tilde{r}_{u})$.

We run our analyses using (1) the MovieLens 20M dataset (Harper and Konstan, 2016) and (2) the Google Location dataset (He et al., 2017). Because of the space constraints, we report the results using dataset (1), and use dataset (2) for validation, reporting differences in observations where applicable. To properly reason about data minimization, we only select users who have at least 45 ratings in their profile. For efficiency reasons, we further subsample the users, creating (1) a MovieLens dataset containing around 2.5k users, 170k ratings, and 20k unique movies; the mean and median number of ratings in a user profile are 69.5 and 59, respectively, and (2) a Google Location dataset containing around 2.2k users, 185k ratings, and 150k unique items; the mean and median number of ratings in a user profile are 85.2 and 64, respectively.

We analyze data minimization properties for two fundamental classes of recommendation algorithms - neighborhood-based (k-nearest-neighbors) and matrix-factorization-based (SVD) (Funk, 2006), both as implemented in the Surprise library (Hug, 2017).

We measure the quality of recommendations using: RMSE (comparing the differences between the predicted and true ratings for all items in the test set and thus assuming a user consumes the whole recommendation set) and NDCG (measuring the quality of the top results with a logarithmic discounting factor for errors in lower ranking positions (Järvelin and Kekäläinen, 2002)). In our experiments, we set $k=10$.

We explore data minimization in the context of a system that begins with extensive data collection for a starting set of users. This may be gathered in-house or from a representative market not subject to data minimization constraints. While there will be situations where seed data is unavailable, we leave that for future work.

To simulate this situation, we randomly split the full dataset into two parts: the system data $D_{S}$ ($70\%$ of all users), and the minimization data $D_{M}$ ($30\%$ of all users). Users are randomly assigned to one of these groups. For minimizing users in $D_{M}$, we further randomly split their ratings into candidate ($70\%$ of all ratings) and test data ($30\%$ of all ratings). Different minimization strategies will select different subsets of each user’s candidate data for use by the system. Recommendations generated based on the selected data from the candidate user data are evaluated using the remaining test data.

Data is selected from the candidate user data using a chosen minimization strategy and a minimization parameter $n$ (the number of items to select). We run experiments for $n=\{1,3,7,15,100\}$.

When minimizing data, we select a subset of user candidate items to present to the recommendation algorithm. While approaches with similar problem structure have used greedy algorithms modeling the information-theoretic utility of data (Krause and Horvitz, 2010), greedy algorithms are less practical in a data minimization scenario. Since utility of data is tied to a specific recommendation performance metric rather than modeled as information gain, the submodularity and monotonicity properties upon which guarantees on greedy algorithms are based do not necessarily hold. Moreover greedy selection is costly in terms of runtime, since the recommendation algorithm needs to be run for every possible selection. This section presents the selection strategies we study in this paper.

Tables 1 and 2, as well as Figure 1 present the performance of the k-NN and SVD recommendation algorithms for various minimization strategies and intensity (parameter $n$ denotes the number of items from observational pools that were shown to the recommendation algorithm). The numbers show the RMSE and NDCG values of the minimized recommendations, averaged over all minimizing users.

For both recommendation algorithms, we observe that the recommendation quality decreases as we present the algorithm with less data to base personalized recommendations on. We attribute the few exceptions (e.g., the increase of RMSE between n=3 and n=7) to the inherent noisiness of data and effects of sampling strategies.

We would like to highlight two observations. First, the overall loss incurred by minimization is relatively low when compared to the variation of error across users — see Figure 1 for a visualization of sorted error values for all users in the minimization dataset for random minimization strategies. It is important not to overinterpret these results based on measures like RMSE, though. Ratings in recommendation datasets are often relatively homogenous in terms of absolute values: In the MovieLens dataset, for instance, they vary between $0.5$ and $5$ in $0.5$ increments. Moreover, most users abstain from using extreme values in their ratings: In our system data, out of $10$ different values in the rating scale, the three most used rating values of $3,3.5,$ and $4$, make $61\%$ of all ratings.

Second, the distribution of error in the population remains the same even when the recommendations are based on minimized data. We observe that the shapes of the error value curves are similar for different minimization methods beyond random (effects similar to those in Figure 1). We exclude additional plots for lack of space.

We find that SVD is more robust to data minimization according to both quality measures. In case of RMSE, metric differences between the Full strategy and any other strategy and minimization parameter $n$ are lower for SVD than for kNN. This observation also holds for NDCG; moreover, the differences in NDCG between the performance of SVD on full data and minimized data are not significant (under a two-tailed t-test and $p<0.01$ with the Bonferroni correction). Note that the SVD robustness result is partly explained by our experimental protocol—the minimized observed data of each test user is ’folded in’ into the matrix one user at a time. While this approach is more computationally expensive than folding in all test users at once, the resulting decomposition is computed for a matrix where only one row is different from the full data condition. On top of that, the NDCG measure is not sensitive to differences in predicted rating values as long as the predicted ranking of items remains the same (which is likely to happen when the decomposed matrix is similar to the full data matrix). The lower minimization robustness of kNN can furthermore be explained by the fact that user similarities are computed over rating sets joint with other system users ($I_{u}\cap I_{v}$, see 3.2), and minimization thus leads to computing predictions over noisier neighbour sets.

As described in Sec. 3.1, we run the the same experiments with two different datsets, using the Google Location dataset for validation. We observe the same trends in terms of the performance of different minimization strategies. One major difference in the results is that we observe similar robustness to minimization for KNN and SVD recommendations. We attribute this fact to the key difference between the two datasets—in Google Location dataset item ratings are sparser (20k vs. 150k unique items for a similar total number of users) thus minimization is less likely lead to overall change in similarities to other users.

Figure 2 shows the error variation when the data is sorted only by the error value of the Full method - other error values correspond to users at the ranking positions determined by the sorting for Full. Note that the data plotted here is exactly the same as the data in Figure 1 — only the sorting differs. These results suggest that, while the distribution of error in the population across users remains largely similar irrespective of recommendation algorithm or minimization strategy (see Figure 1), errors incurred to individuals can be substantial. We observe this behavior for all tested minimization methods and recommendation algorithms, although the per-user variations are lower when minimizing for SVD recommendations.

This finding suggests that, for a fixed quality threshold, data can be less effectively minimized if the loss requirement applies to every individual as opposed to the population on average.

Since the error is not uniformly distributed, we dive deeper to try to understand which users are most impacted. The following sections analyze a number of user characteristics and their correlations with error deltas.

We investigate whether the minimization errors (the difference in the quality metric when comparing the recommendations over minimized profiles and the recommendations over full profiles) are correlated with different user characteristics. For each user, we consider the following characteristics (measured over the user’s full profile, before minimization): (1) Number of ratings, (2) Average value of the ratings in a user’s profile, (3) Average popularity of items in a user’s profile (measured as the number of users in the system data who have rated a given item), (4) Profile diversity measured by the number of genres the movies in a user’s profile belong to, (5) Average similarity to all users in the system data, (6) Average similarity to the 30 most similar users in the system data.

In this paper, we have identified a lack of a homogeneous interpretation of the GDPR’s purpose limitation and data minimization principles in the domain of personalization systems. We argue that these systems do not necessarily need to collect user data, but that they do so in order to improve the quality of the results. Thus, we propose two performance-based interpretations of the data minimization principle that tie the limitations of data collection to quality metrics. The first interpretation focuses on the global average algorithm performance, while the second focuses on the local per-user minimum performance.

We found SVD (FunkSVD with user and item biases) to be more robust to minimization than kNN user-user collaborative filtering across different minimization strategies. Among the minimization strategies, we found the random strategy to perform well, likely due to the fact that it preserves average user characteristics. However, for each recommendation algorithm, it is possible to find strategies that perform better or worse than random.

While the results suggest global data minimization can be quite successful (in some cases we can withhold as much as 90% of the user data incurring RMSE loss as low as 0.025), we show that quality difference can be substantial for individual users. Furthermore, our analysis with Ordinal Least Squares regression shows that the variation in individual-level error is not well explained by standard user features. The complex interaction between the individual-level error and recommendation algorithms, minimization strategies, system data, and individual data, require further study, also from a legal perspective. Indeed, further research should evaluate the desirability of both approaches, considering that, on the one hand, the GDPR requires that each data processing operation be examined on its own merits, yet on the other purpose limitation or data protection by design and by default ought to be evaluated from a global perspective.

Based on our observations about varying user-level errors, it is plausible that data minimization hurts marginalized groups, in particular if those groups form a minority of the data—the members of majority population will be well served with just a few features (because there is sufficient statistical support), while minority populations will need to provide more features to get service of comparable quality. A scenario like this would further harm marginalized populations through decreased data protection.

Furthermore, our analysis assumes service providers have a collection of background data to base personalization on (purchased or collected from markets that are not legally obliged to data minimization). Companies might also need personal data to develop new services. In this work, we did not consider such provider costs.

While this paper enhances our understanding of what performance-based data minimization means in practice, a number of challenges emerge. Practical minimization mechanisms would not be able to measure quality loss directly, nor easily adapt selection mechanisms to each user if necessary without access to candidate user data. To support minimization, we need to design new protocols for user-system interaction, and new learning mechanisms that select data while respecting specific minimization requirements. Last but not least, further interdisciplinary work with the legal community is necessary to develop data minimization interpretations that are verifiable and viable, both legally and computationally.