Beyond Random Noise: Insights on Anonymization Strategies from a Latent Bandit Study

In the era of data-driven technologies and applications, privacy-preserving machine learning has emerged as a critical concern, for example, in recommendation-based tasks which heavily rely on sensitive data. Essential steps should be considered to protect such data, especially with the introduction of stricter privacy policies like GDPR (General Data Protection Regulation) (Voigt and Von dem Bussche, 2017) in Europe, which further emphasizes the necessity for enhanced privacy measures. Given the vulnerability of traditional anonymization techniques to adversarial attacks, addressing the risks associated with inadvertently disclosing sensitive data is imperative.

To mitigate the problem, Differential Privacy (DP) has gained widespread acceptance as a fundamental metric for quantifying and ensuring provable privacy (Dwork et al., 2014). However, DP has failed, for example, in federated learning setting (Wang et al., 2021). Other strategies, such as homomorphic encryption, come with increased costs of computation (Hao et al., 2019). Therefore, this study investigates privacy-preserving machine-learning aspects and provides valuable insights into anonymization strategies beyond the conventional use of noise, striking a balance between privacy protection and recommender system performance, exemplified in the context of latent bandits.

To assess the privacy implication of our work, we investigate the potential weaknesses associated with a linkage attack scenario. Our study assumes a susceptibility to privacy breaches due to knowledge sharing among agents. If not adequately mitigated, this weakness can enable potential adversaries to re-identify anonymized records in data via collected auxiliary information. The contributions of this paper can be summarised as follows:

• •

  We demonstrate the susceptibility to attacks of simple additive noise strategies and investigate alternatives with better privacy-performance trade-offs.

• •

  We conduct our experiments using real-world datasets such as CASAS, Endomondo, and Fitbit, highlighting the importance of implementing tailored privatization strategies for each dataset.

• •

  We are the first to explore privacy concerns within a learning setup in the latent bandit context, specifically in a realistic and frequently encountered linkage attack scenario.

• •

  We investigate the popular ADS metric for estimating a dataset’s privacy level, demonstrating a significant mismatch between the metric and the level of de-anonymization in linkage attacks.

The field of privacy-preserving machine learning has witnessed significant advancements in recent years. Techniques such as differential privacy (DP)  (Dwork et al., 2014) and federated learning (FL) (McMahan et al., 2017) have emerged as prominent approaches to safeguard sensitive information while enabling collaborative model training. However, DP has failed, for example, in federated learning setting (Wang et al., 2021). FL assumes non-malicious participants, which is highly unlikely in real-world applications.

Linkage attacks have garnered attention in the context of privacy preservation. These attacks exploit auxiliary information to re-identify individuals within a supposedly anonymized dataset. According to Sweeny (2002), 87% of the US population can be identified by a limited combination of their attributes. They show how seemingly non-sensitive information can be used to re-identify individuals in a dataset. Further, they pioneered research in attribute inference attacks, where an adversary may infer values of privatized attributes from other attributes or datasets. Such attacks have been demonstrated across various domains, including healthcare Sweeney (1997) and social networks Gulyás et al. (2016), underscoring the importance of robust privacy mechanisms. (Shokri et al., 2017) demonstrated that an adversary with access to a black-box model can infer whether a particular data point was used in the training set, the so-called membership inference attack. This type of attack highlights vulnerabilities in the protection of individual privacy. While membership inference attacks have raised awareness about model privacy, they assume a specific threat model and may not generalize to all scenarios.

There has been a growing interest in balancing data privacy and the performance in different Bandits settings to better understand the fundamental trade-off imposed by privacy constraints. Ren et al. (2020) studied multi-armed-bandits where users may not want to share rewards. They study this setting under local differential privacy and proposed algorithms that match the regret lower bound of their setting up to constant factors for a given local differential privacy budget. Their work shows an increase in convergence time and, thus, delayed learning induced by the additional privacy constraint. Malekzadeh et al. (2020) developed a framework for bandit learning in a setting akin to federated learning, where multiple agents share information privately for accelerated learning. Using a clustering approach, their evaluation shows that privatized agents outperform their non-private counterparts in limited data domains while still being competitive when more data is available. These results may suggest a more complicated exploration-exploitation dilemma than in a non-private bandit setting. Privatization may aid or not significantly impact generalization, and algorithms that tailor their choice of action-taking to privatization schemes may achieve superior early-stage performance. As pointed out by Gkountouna et al. (2022), clustering approaches, while preserving data privacy, may negatively impact data utility, thus requiring more targeted instance-specific approaches that target sensitive attributes between records heterogeneously instead of simply clustering records with attributes that are close in value. They provide a privatization algorithm that resists machine-learning-based approaches and thus provides practical applicability in the face of contemporary attack methods. As of the current writing, there is no prior research showcasing privacy considerations exemplified in a latent bandit framework, a gap our work aims to address.

In this section, we describe the recommendation system and the linkage attack scenario. This system aims to provide recommendations to users, such as music, movies, or mobile health interventions. Each user receives recommendations from an agent, a latent bandit instance in our study. The agent estimates the user’s current state, such as an activity, and chooses an item (arm) from a finite set of recommendations. Users change their state in a random manner governed by a transition matrix, and the recommender system needs to adapt to these changes as quickly as possible. More formally, we define an agent as follows.

The Agent: Non-stationary Latent Bandit. The set of arms, corresponding to items to recommend, is $\mathcal{A}=\left[K\right]$. The set of states is denoted as $\mathcal{S}$. We use capitalized letters for all random variables. The non-stationary latent bandit (Hong et al., 2020) is an online learning problem with bandit feedback. That is, only the reward of the chosen arm is revealed to the agent. At every time step $t=1,2,\dots,n$:

1. 1.

   The agent chooses an arm $A_{t}\in\mathcal{A}$ according to its policy, thus acting as a mapping of history $\mathcal{H}_{t}=(A_{1},R_{1},\dots,A_{t-1},R_{t-1})$ to arms in $\mathcal{A}$.

2. 2.

   The environment reveals the reward $R^{A_{t}}\in\mathbb{R}$ according to the joint conditional reward distribution $P(R|A,S;\theta)$, parameterized by $\theta\in\Theta$, where $\Theta$ is the space of plausible reward models. Thus, only if the agent correctly identifies the state of the user, is it able to provide the right recommendation.

The starting state $S_{1}$ comes from a prior distribution $P_{1}(s)$ and changes using a transition kernel $P(S|S_{t-1};\phi)$ with parameters $\phi$ that maps the current state to a distribution over subsequent states. The agent does not change the environment state through its choices, and only the current state determines the distribution over the next states and the rewards.

The mean reward for an arm $A_{t}$ in latent state $S_{t}$ is defined as $\mu{(A_{t},S_{t};\theta)}=\operatorname{\mathbb{E}}_{R\sim P(R|\cdot)}\left[R\right]$ under the model parameters $\theta$. The form of $P(\cdot|A,S;\theta)$ is not restricted and can be arbitrarily complex, but the rewards for a particular arm and state are assumed to be Gaussian distributed with mean $\mu{(A_{t},S_{t};\theta)}$ and variance proxy $\sigma^{2}$. The optimal arm in latent state $S_{t}$ is denoted as $A_{t}^{*}=\mathop{\mathrm{argmax}}_{A\in\mathcal{A}}\mu{(a,S_{t};\theta)}$.

In our experiments, we focus on “difficult” rewards. In essence, the agent will encounter difficulty identifying the current state using only the sequence of received rewards. This will place more importance on estimating a suitable transition matrix for decision-making and show differences in reward between different strategies more clearly. Figure 1 shows an example from the Human Activity Recognition from Continuous Ambient Sensor Data (CASAS) dataset, where a hard reward structure results in significant regret differences between transition matrices. More specifically, what makes the rewards hard is that each state has a single optimal action with $\mu^{*}(\cdot)=2$, while all the other actions have exactly the same reward, namely $\mu(\cdot)=1.05$. For all arms, we set $\sigma=2$. Therefore, once the user switches to the next state, an agent cannot immediately deduce the new state based on the rewards obtained by repeating the previous arm or by random exploration. Knowledge of the expected new state, based on a well-estimated individual transition matrix, is crucial for maximizing reward.

Each user has such a latent bandit agent, personalized for their needs. In our setup, we assume that the true reward distribution $P(\cdot|A,S;\theta)$ is known to the agent, while the transition kernel (transition matrix) $P(S|S_{t-1};\phi)$ is not. The agent needs to estimate the individual matrix based on trial and error. However, users collaborate to improve recommendation quality by sharing anonymized versions of these matrices. At the same time, this opens them to a potential attack by an adversary, which we will describe next.

Sharing transition matrices and the adversary model. The process of sharing information among users is demonstrated in Figure 2, describing the learning setup and the adversary. Distributing transition matrices is handled by a centralized server, which receives requests from all agents and authenticates their identities. The agents form a federation or learning group, and each member shares their anonymized transition matrix, and additional metadata, with the server. This way, a dataset $D$ is formed (A). Once a new agent has been added to the system, it initiates the learning process by asking the server for a suitable transition matrix. The matching is done based on the metadata, a user profile specific to each dataset. This profile is used by the server for measuring similarity across the clients and identifying the most beneficial matrix for the new arrival (B).

The adversary, pretending to be a new user, may communicate with the server, send fake metadata, and receive a transition matrix. An adversary may perform this several times, with different metadata, to obtain different transition matrices. Thus, it is constructing an anonymized version $\hat{D}$ of dataset $D$, containing the transition matrices of potentially all the users in the learning group (C). The adversary follows a similar procedure to the one described by Narayanan and Shmatikov (2008), attempting to match collected auxiliary information (a percentage of cell values) to full transition matrices $\hat{D}$ (D). First, we sample one user’s transition matrix from dataset $D$. From the selected transition matrix, we provide the adversary with auxiliary information that contains the values of a fixed number of cells. We chose those cells uniformly at random. In our experiments, we vary the number of available cells to the adversary. For all runs, the adversary can access an anonymized version $\hat{D}$ of $D$.

We follow a similar procedure to the one described by Narayanan and Shmatikov (2008). First, we sample a transition matrix from database $D$. Then, we provide the adversary with auxiliary information that contains the values of a fixed number of randomly chosen cells from the selected transition matrix. We chose cells uniformly at random. The adversary has access to an anonymized version $\hat{D}$ of $D$. The adversary aims to identify the transition matrix in $\hat{D}$ what the auxiliary information belongs to, thus reconstructing the other cells. The process is demonstrated in figure 2.

As a result, the server must authenticate any new agents before they join the group and share their environment metadata to enable them to leverage the knowledge of other members and avoid starting from scratch, as shown in Figure 4. Once the agent has been added to the system, it can initiate the learning process by obtaining a suitable transition matrix selected by the computing algorithm in the server side based on the new agent’s provided metadata. Additionally, if any change occurs in any agent’s environment, such as adding a new sensor or feature. In that case, the agent can update their metadata and request another transition matrix that is more appropriate for its updated settings.

In certain scenarios, an adversarial entity assumes the role of a new participant seeking to infiltrate the federation with intentions such as uncovering the original data flow among participants, disrupting the entire system, or exploiting it for alternative purposes. Figure 5 outlines the sequence of actions this adversary uses to deceive the system. The adversary endeavors to integrate into the federation under the guise of a regular participant seeking knowledge sharing instead of starting anew in a separate environment.

The process begins with the adversary sending authentication requests, aiming to gain the server’s trust. Once this trust is established, the adversary is admitted into the system. Subsequently, the adversary initiates requests for a transition matrix, providing the requisite metadata. Simultaneously, this fraudulent participant allocates time to accumulate publicly available auxiliary information within the system concerning other participants. This acquired information can potentially be leveraged to extract sensitive data from the transition matrix about other participants. The adversary maintains a repository for this information, which can be continually updated.

To maximize the acquisition of the transition matrix, the adversary alters their identity and environmental settings, repeating the steps mentioned earlier until their objectives are met.

Additive noise and lossy compression. In this paper, we investigate two popular methods for directly changing the values within individual transition matrices. The first method adds noise to sensitive information via a Laplace mechanism. For noise addition, we formally define the noisy version of the transition matrix as

where $Z$ is a random draw from a Laplace distribution with mean $0$ and $\epsilon$ variance, and $\mathbf{w}$ represents the weight of the added noise to individual cells and can be chosen arbitrarily.

The second method is truncated singular value decomposition (tSVD), widely used for matrix approximation. By considering only the top-$k$ eigenvalues, tSVD compresses the information in the transition matrix while preserving essential information for approximate reconstruction. Specifically, tSVD solves the problem of approximating the transition matrix $\mathbf{r}$ with another matrix $\tilde{\mathbf{r}}$ by minimizing the Frobenius norm $||\mathbf{r}-\tilde{\mathbf{r}}||_{F}$ subject to the constraint that $\operatorname{rank}(\tilde{\mathbf{r}})$ is equal to $k$ Markovsky (2008). Importantly, tSVD also offers the benefit of removing identifying information. Cells, including those corresponding to unique user characteristics, are not reconstructed accurately if they do not affect the Frobenius norm significantly during optimization, increasing the difficulty of identifying users based on these cells.

Aggregation strategies. Besides adding noise to individual records, we investigate different methods of aggregating transition matrices across users before providing them to the agent for decision-making. We specifically focus on averaging methods, that is, calculating elementwise means of the transition matrices of several users. Averaging has the effect of hiding user-specific information, thus making linkage attacks harder. We explore three methods: nearest neighbor (NN), cluster average (Cluster average), and global average (Average). Further, we investigate some variants for the experiments. Specifically, we evaluate the impact (in terms of regret performance and privacy) of choosing a “more distant” transition matrix using the second nearest neighbor (Second NN). For clustering, we analyze the performance gain against the weakening of anonymization by doubling (2x Cluster average) and tripling (3x Cluster average) the number of clusters; more clusters mean fewer users per cluster, and, thus, more accurate transition matrix reconstructions.

We more formally define the cluster strategy as follows. Given records $r=\{\mathbf{r_{1}},\mathbf{r_{2}},\dots,\mathbf{r_{N}}\}\in\mathbb{R}_{\geq 0}^{d\times d}$ and $c$ clusters $\{c_{1},c_{2},\dots,c_{C}\}\in\mathbb{Z}^{+}$, we assign each record $i$ to one cluster $\pi(i)\in\{1,2,\dots,C\}$. We denote $|c_{\pi(i)}|$ as the cardinality (number of users) of cluster $c_{\pi(i)}$ of record (user) $i$. With slight abuse of notation, we abbreviate $|c_{\pi(i)}|$ as $|c_{i}|$.

The similarity between users for the nearest neighbor and clustering computations is not based on the values of the cells in the transition matrices but rather on user profiles (metadata) since, in real-world applications, the transition matrix of new users is unknown, at least initially. We compute a user profile for each dataset that approximately encapsulates the user’s behavior. We describe the details in the Experimental setup section.

Regret. For the performance metric, we use regret, the most common metric in bandit learning, defined as follows. For a fixed latent state sequence $s_{1:n}\in\mathcal{S}^{n}$, the expected n-step regret is defined as

where the expectation is taken over the agent’s randomness in arm choice. We consider the Bayes regret, computing the n-step regret as an expectation over latent state randomness, defined as $\mathcal{BR}(n;\theta;\phi)=\operatorname{\mathbb{E}}_{S_{1:n}\sim\phi}[\mathcal{R}(n,\phi,S_{1:n})|\theta,\phi]$.

Probability of de-anonymization. In the following, we define whether a data record is successfully de-anonymized given auxiliary information depending on the performance of the scoreboard algorithm Narayanan and Shmatikov (2008). Scoreboard is a generic algorithm based on nearest-neighbor matching. The principal procedure, with some modifications, is as follows:

1. 1.

   Compute the score $\operatorname{Score}(aux,\mathbf{r}^{\prime})$ according to the average similarity of attributes between the candidate record $\mathbf{r}^{\prime}\in\hat{D}$ and the auxiliary information as

   $$\operatorname{Score}(aux,\mathbf{r}^{\prime})=\frac{1}{|\sup(aux)|}\sum_{i\in\sup(aux)}\operatorname{Sim}(aux_{i},\mathbf{r}^{\prime}_{i}).$$

   The support on auxiliary information $aux$ is denoted as $\sup(aux)$ and corresponds to the cells available to the adversary for comparison. Only the cells in $aux$ are used to compute the similarity to records in $\hat{D}$.

2. 2.

   Compute the matching set $D^{\prime}$ as $D^{\prime}=\{\mathbf{r}^{\prime}\in\hat{D}:\operatorname{Score}(aux,\mathbf{r}^{\prime})=\max_{\mathbf{r}^{\prime}\in\hat{D}}{\operatorname{Score}(aux,\mathbf{r}^{\prime})}\}$.

3. 3.

   Sample uniformly a candidate record from $D^{\prime}$.

In this paper, $\operatorname{Sim}(\cdot)$ computes $L_{1}$ distance, with some fixed constant $\alpha$, between cells in $aux$ and the corresponding cells in a candidate record in $\hat{D}$ as $\operatorname{Sim}(aux_{i},\mathbf{r}^{\prime}_{i})=(aux_{i}-\mathbf{r}^{\prime}_{i})<\alpha$.

The probability of de-anonymization for a dataset $D$ is computed as

where $N$ is the number of records (one record per user) in the dataset. The probability of de-anonymization is, in other words, the average number of records $r^{\prime}$ correctly matched with the corresponding record $r$ using $aux$.

To interpret our experimental results correctly, it is important to note that, for clustering strategies, we only share the average transition matrix of a cluster, not the transition matrices of individual users. Thus, $\hat{D}$ constitutes a set of cluster averages. Users of the same cluster have the same cluster average in $\hat{D}$, plus some possible noise individual to each user. As a result, the adversary can only hope to match the auxiliary information to a cluster as a whole. To calculate the probability of de-anonymization, we consider the success rate of matching the auxiliary information to a particular cluster, as well as the size of the cluster. For instance, if a cluster has five users, the probability of de-anonymization is $0.2$ for a correct match and $0$ otherwise. More formally, the level of de-anonymization using an aggregate transition matrix is denoted (interpreting $\mathbf{r}_{i}$ and $\mathbf{r}_{i}^{\prime}$ now as cluster averages instead of the transition matrix of a particular user) as

ADS privacy is a popular metric for estimating the level of privacy provided in a dataset. It is a metric used to minimize a corresponding loss in ADS-GAN, maximizing privacy intelligently while retaining performance in downstream tasks using the anonymized dataset Yoon et al. (2020). In this study, we investigate if the metric accurately captures the probability of de-anonymization via linkage attacks. We compute the ADS metric for different Laplace noise levels and the number of cells of auxiliary information available to the adversary across three datasets. ADS privacy is defined as

where $\mathbbm{1}$ is the indicator function, $k_{i}=\min_{\mathbf{r}_{i}\in\mathcal{D}\setminus\mathbf{r_{j}}}||\mathbf{w}\cdot(\mathbf{r}_{i}-\mathbf{r}_{j})||$, and $\hat{k}_{i}=\min_{\mathbf{\hat{r}}_{j}\in\mathcal{\mathcal{\hat{D}}}}||\mathbf{w}\cdot(\mathbf{r}_{i}-\mathbf{\hat{r}}_{j})||$.

One typically uses the measure 3 to assess whether synthetic records (created by adding noise to the original transition matrices) differ sufficiently from the original records. It is based on the concept of $\epsilon$-identifiability, which means that the probability of a synthetic observation being closer to the original observation than another original observation is less than $\epsilon$. The value of $\epsilon$ determines the proportion of users that synthetic observations cannot identify because they differ enough from the real observations. Specifically, if the proportion of unidentifiable users is $\geq 1-\epsilon$, the synthetic observations provide sufficient privacy protection. When $\epsilon$ equals 0, the data is perfectly non-identifiable (Yoon et al., 2020).

Model-based Thompson Sampling (mTS). We selected Model-based Thompson Sampling (mTS) as the recommendation algorithm, a posterior sampling technique demonstrating state-of-the-art performance in the latent bandit setting according to previous research (Galozy and Nowaczyk, 2023; Hong et al., 2020). mTS uses a posterior update rule and selects an arm based on its probability of being optimal given the history $\mathcal{H}_{t}$, which is expressed as $\mathbb{P}(A_{t}=a|\mathcal{H}_{t})=\mathbb{P}(A^{*}_{t}=a|\mathcal{H}_{t})$. To select an arm, mTS samples a state $B_{t}\in\mathcal{S}$ from its posterior distribution over the belief state $P_{t}(s)$ and chooses the arm $A_{t}$ with the highest mean reward given the sampled $B_{t}$, as $A_{t}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\mu(a,B_{t};\theta)$. After the reward $R_{t}$ is received for the chosen arm, the posterior of the belief state $P_{t+1}$ is formed using the Bayes rule. The algorithm’s pseudo-code is shown in Algorithm 1. In our experiments, mTS has access to the reward predictor $P(R_{t}|A_{t},S_{t};\theta)$, a reasonable assumption given that we may use prior collected data to construct the predictor. The available data allow mTS to quickly provide good recommendations without learning from scratch (Hong et al., 2020).

We did not investigate contemporary end-to-end learning schemes, such as generative models like ADS-GAN (Yoon et al., 2020) that promise to be effective data anonymization techniques. These methods might alleviate some of the concerns raised in this paper. Still, as mentioned above, these end-to-end learners often rely on objective functions that are not well aligned with common attack patterns, and thus have yet to prove effective in real-world scenarios.

Our analysis is limited to a fairly simple scoreboard algorithm for deanonymization. There may exist better algorithms with stronger deanonymization capabilities. Our research illustrated that even a simple method can lead to a significant overestimation of the level of privacy, which would only increase with more sophisticated algorithms.

Furthermore, we did not examine machine learning contexts other than bandits, such as supervised or unsupervised learning. Nevertheless, results and findings from this research are expected to transfer directly to these settings as well, since they ultimately concern data privacy irrespective of how the data is used or what specific models are trained. It is not clear to what extent privacy would be compromised in specific settings, but the general trend we observe holds.

In this paper, we conducted experiments to evaluate the effectiveness of different privitization strategies, using a latent bandit setting. Our findings show that random noise added to individual records may not be a satisfactory solution for the privacy-performance trade-off. Instead, aggregations generally provide a better balance between ensuring privacy and maintaining performance for downstream tasks. There seems to be no single technique that solves the trade-off the best for a given desired level of privacy. Further, we found that one-size-fits-all metrics optimized for privacy, like the ADS-GAN metric, do not correspond well to the probability of de-anonymization in linkage attacks. Our paper highlights the need to evaluate privatization techniques on actual attack scenarios commonly employed in the real world, especially considering the abundance of useful auxiliary information collected in the wild that may render such techniques less effective.