Evaluating of Machine Unlearning: Robustness Verification Without Prior Modifications

Machine Learning as a Service (MLaaS) primarily involves two key entities: the data provider and the model provider. The data provider submits their data to the model provider, who then uses this data for model training. We denote the dataset of the data provider as $\mathcal{D}=\left\{\left(\mathbf{x}_{1},y_{1}\right),\left(\mathbf{x}_{2},y_{2}\right),...,\left(\mathbf{x}_{n},y_{n}\right)\right\}\subseteq\mathbb{R}^{d}\times\mathbb{R}$, where each sample $\mathbf{x}_{i}\in\mathcal{X}$ is a $d$-dimensional vector, $y_{i}\in\mathcal{Y}$ is the corresponding label, and $n$ is the size of $\mathcal{D}$. Let $\mathcal{A}$ be a (randomized) learning algorithm that trains on $\mathcal{D}$ and outputs a model $M$. The model $M$ is given by $M=\mathcal{A}(\mathcal{D})$, where $M\in\mathcal{H}$ and $\mathcal{H}$ is the hypothesis space. After the training process, data providers may wish to unlearn specific samples from the trained model and submit an unlearning request. Let $\mathcal{D}_{u}\subset\mathcal{D}$ represent the subset of the training dataset that the data provider wishes to unlearn. The complement of this subset, $\mathcal{D}_{r}=\mathcal{D}_{u}^{\complement}=\mathcal{D}\setminus\mathcal{D}_{u}$, represents the data that the provider wishes to retain.

After the machine unlearning process, a verification procedure $\mathcal{V}(\cdot)$ is employed to determine whether the requested samples have been successfully unlearned from the model. Typically, data providers lack the capability to perform this verification independently. For example, verification schemes based on MIAs often require the training of attack models using multiple shadow models, which can be too resource-intensive for data providers. Consequently, verification operations in MLaaS are usually conducted by a trusted third party. With the assistance of this trusted third party, a distinguishable check $\mathcal{V}(\cdot)$ will be conducted to ensure that $\mathcal{V}\left(M,\mathcal{D}_{u}\right)\neq\mathcal{V}\left(M_{u},\mathcal{D}_{u}\right)$.

Designing an effective and efficient verification scheme for machine unlearning is difficult. As discussed in Section II-A2, verification schemes based on accuracy, theoretical analysis and distribution similarity have consistently proven ineffective in [1, 38]. In this Section, we further highlight the critical limitations of attack-based verification schemes to illustrate the novelty of our scheme. Figure 1 illustrates the main ideas of commonly used attack-based verification schemes.

As shown in Figure 1, attack-based unlearning verification schemes typically involve three roles, including data provider, model provider and one trusted third party. Data provider first pre-selects a subset of triggers $\mathcal{D}_{u}$ before model training. For example, in schemes based on data pollution and backdoor attacks, triggers are often generated by a trusted third party [7, 35, 8]. In MIAs-based verification schemes, data providers directly select partial training samples as those triggers [11, 12, 13, 14]. Based on those triggers, the verification process can be summary as the following steps:

• •

  Trigger Integration: Triggers $\mathcal{D}_{u}$, either generated from a trusted third party or selected directly from the data provider’s own dataset, are added to the training dataset. The model is then trained on this combined dataset.

• •

  Initial Prediction: The data provider sends the verification request to the trusted third party, and the trusted third party queries the model’s prediction for these triggers. The model provider returns the predictions $O(\mathcal{D}_{u})$. Existing attack-based verification scheme outputs the verification result $\mathcal{V}(O(\mathcal{D}_{u}))$ for $\mathcal{D}_{u}$ based on $O(\mathcal{D}_{u})$.

• •

  Unlearning Request: The data provider submits an unlearning request for those triggers $\mathcal{D}_{u}$.

• •

  Post-Unlearning Prediction: The data provider and the trusted third party repeat the steps in the initial prediction phase and output the verification result $\mathcal{V}(O(\mathcal{D}_{u})^{\prime})$.

• •

  Verification: By comparing the returned predictions before and after unlearning, $\mathcal{V}(O(\mathcal{D}_{u}))$ and $\mathcal{V}(O(\mathcal{D}_{u})^{\prime})$ respectively, the data provider determines if the model has undergone the unlearning process.

However, those attack-based machine unlearning verification schemes mainly have the following limitations:

• •

  Sample-Level Modification before Model Training: Ensuring effective verification often requires incorporating a large number of modified samples, such as backdoored samples, which increases computational costs.

• •

  Support Only a Small, Predefined Subset of Samples: Some schemes use pre-embedded patterns for verification, like backdoor triggers, limiting the process to only those samples. This means the number of verifications must be considered before training, and once these samples are used up, no further verification is possible.

• •

  Lacking Robustness Verification: These schemes focus solely on verifying the unlearning process immediately and lack robustness, meaning the model cannot be fine-tuned or pruned for new demands after unlearning.

• •

  Model Performance Degradation and Security Risks: Verification schemes based on data pollution and backdoor attacks rely on poisoned samples, inheriting the drawbacks of poisoning methods. This can harm model performance and introduce security risks, limiting their adoption for verification.

In MLaaS, there are two main roles: data providers and model providers. Data providers also act as verifiers of unlearning, while model providers are responsible for executing it. The data provider shares its dataset with the model provider, who trains a model using a learning algorithm. After training, beyond making regular predictions, the data provider can submit unlearning requests to remove their data from the model. However, model providers may not always be fully trustworthy in performing unlearning, either because this process is time-consuming, or large-scale unlearning requests could negatively impact model performance [8, 35]. The background and goals of data providers are as follows:

• •

  Background: Data providers only have the ability to upload their training data or send prediction, unlearning requests to the model providers.

• •

  Goal: After submitting the unlearning request, data providers want to confirm whether their data has been truly unlearned from the model.

Meanwhile, the background and goals of model providers are as follows:

• •

  Background: Model provider can collect training data from the data provider and train the model.

• •

  Goal: After receiving the unlearning requests from data provider, model providers prefer to avoid executing unlearning as much as possible to protect their own interests.

This paper proposes a method for data providers to verify whether their samples have been successfully unlearned from the trained model. Specifically, we have four aims related to machine unlearning verification.

• •

  No Pre-defined Modifications: Develop a verification scheme that enables data providers to confirm the execution of the unlearning process without depending on any pre-defined sample-level modifications.

• •

  More Sample Coverage: Design a scheme supporting unlearning verification for nearly all samples involved in the training process.

• •

  Robustness Verification: Address the need for robustness by supporting immediate post-unlearning verification and enabling verification in scenarios where the model undergoes further changes after unlearning (e.g., further fine-tuning or model pruning).

• •

  Preserving Model Usability: Ensure that the verification scheme does not negatively impact: model performance, security, and training efficiency.

We assume that the data provider conducts verification with the help of a trusted third party. This assumption reflects real-world MLaaS scenarios where data providers often lack the capability to independently verify the unlearning processes [8]. The trusted third party is granted access to the trained model for verification purposes upon receiving unlearning requests. Additionally, we assume that the model provider may carry out further model modifications (e.g., fine-tuning and pruning) after executing the unlearning process.

Current unlearning verification schemes typically depend on additional information to verify the unlearning process, such as pre-embedded backdoors [8, 35]. However, these schemes become ineffective if this additional information is disrupted during subsequent model fine-tuning or pruning. Therefore, it is crucial to verify the unlearning process only using the model itself and investigate if the information can still be recovered from the model parameters post-unlearning.

In this paper, we propose a robustness verification scheme without prior modifications, named UnlearnGuard, which verifies machine unlearning based only on the model and possesses robustness properties. As illustrated in Figure 2, UnlearnGuard directly verifies the unlearning process by examining whether the model parameters contain information about the unlearning samples. Before and after unlearning, the data provider sends a verification request about $\mathbf{x}_{u}$ to trusted third party. The trusted third party ask model from model provider and attempts to recover $\mathbf{x}_{u}$ from it. Based on two recovery results, the data provider can determine if the data was truly unlearned. Our approach distinguishes UnlearnGuard from the scheme illustrated in Figure 1 as UnlearnGuard relies only on the model itself rather than any prior sample-level modifications.

We describe our scheme based on the following two subsections: unlearning verification process and sample recovery process. In Section IV-B, we introduce the main workflow of our entire unlearning verification process, which includes the pre-unlearning process and the post-unlearning process, encompassing all steps shown in Figure 2. Next, in Section IV-C, we explain how to recover actual unlearning samples from the model, which is the most important part of our scheme and supports the workflow of Section IV-B.

In this section, we will describe the whole workflow of our unlearning verification process, including three steps.

In the previous section, we explained the process of verifying unlearning, mainly based on comparing the recovery results before and after unlearning. This section describes how to recover actual training samples encoded within a trained model, leveraging implicit bias and date reconstruction.

We begin by studying simple models before advancing to the analysis of more complex deep models in Section IV-D. Let $D=\left\{\left(\mathbf{x}_{i},y_{i}\right)\right\}_{i=1}^{n}\subseteq\mathbb{R}^{d}\times\{-1,1\}$ be a binary classification training dataset. Consider a neural network $M(\boldsymbol{\theta};\cdot)$: $\mathbb{R}^{d}\rightarrow\mathbb{R}$ parameterized by $\boldsymbol{\theta}\in\mathbb{R}^{p}$. For a given loss function $\ell:\mathbb{R}\rightarrow\mathbb{R}$, the empirical loss of $M(\boldsymbol{\theta};\cdot)$ on the dataset $D$ is given by: $\mathcal{L}(\boldsymbol{\theta}):=\sum_{i=1}^{n}\ell\left(y_{i}M\left(\boldsymbol{\theta};\mathbf{x}_{i}\right)\right)$. Let us consider the logistic loss, also known as binary cross-entropy, which is defined as $\ell(q)=\log\left(1+e^{-q}\right)$.

Directly recovering samples from the above-defined model poses significant challenges. To address this, we reformulate model training problem into a maximum margin problem based on the implicit bias theory discussed by Ji et al. [26] and Lyu et al. [27], which simplifies the process of recovering samples from the model.

Theorem 1 (Paraphrased from Ji et al. [26], Lyu et al. [27]): Consider a homogeneous neural network $M(\boldsymbol{\theta};\cdot)$. When minimizing the logistic loss over a binary classification dataset $\left\{\left(\mathbf{x}_{i},y_{i}\right)\right\}_{i=1}^{n}$ using gradient flow, and assuming there exists a time $t_{0}$ such that $\mathcal{L}\left(\boldsymbol{\theta}\left(t_{0}\right)\right)<1$, then, gradient flow converges in direction to a first-order stationary point of the following maximum-margin problem:

In this theorem, homogeneous networks are defined with respect to their parameters $\boldsymbol{\theta}$. Specifically, a network $M$ is considered homogeneous if there exists $L>0$ such that for any $\alpha>0$, $\boldsymbol{\theta}$ and $\mathbf{x}$, the relationship $M(\alpha\boldsymbol{\theta};\mathbf{x})=\alpha^{L}M(\boldsymbol{\theta};\mathbf{x})$ holds. This means that scaling the parameters by any factor $\alpha>0$ results in scaling the outputs by $\alpha^{L}$. Gradient flow is said to converge in the direction to $\tilde{\boldsymbol{\theta}}$ if $\lim_{t\rightarrow\infty}\frac{\boldsymbol{\theta}(t)}{\|\boldsymbol{\theta}(t)\|}=\frac{\tilde{\boldsymbol{\theta}}}{\|\boldsymbol{\boldsymbol{\theta}}\|}$, where $\boldsymbol{\theta}(t)$ is the parameter vector at time $t$. $\mathcal{L}\left(\theta\left(t_{0}\right)\right)<1$ means that there exists time $t_{0}$ at which the network classifies all the samples correctly.

This theorem describes how optimization algorithms, such as gradient descent, tend to converge to specific solutions that can be formalized as Karush-Kuhn-Tucker (KKT) conditions, enabling data reconstruction from the model using those conditions [28]. The reconstruction loss can be defined as following. Derivation details can be found in Section IV-D.

where $m$ denotes the cardinality of the sample set to be reconstructed, typically set to $m\geq 2n$ in their experimental setting. The loss $L_{\text{stationary }}$ represents the stationarity condition satisfied by the parameters at the KKT point, while $L_{\lambda}$ represents the dual feasibility condition. $L_{\text{additional}}$ denotes some supplementary constraints predicated on image attributes, such as ensuring pixel values remain between $[0,1]$.

Using the above $L_{\text{reconstruct }}$ can recover the actual sample from the model, which is our main purpose. However, only using this loss to reconstruct samples exhibits limitations in the context of partial verification. Specifically, it is constrained to reconstructing only those training samples that almost lie on the decision boundary margin. Consequently, when employed to verify the unlearning process, its efficacy is limited to a subset of samples—those situated on the margin. To expand the scope of reconstruction, we introduce a novel loss term, denoted as the prior information loss, $L_{\text{prior}}$.

The introduction of this new loss term aims to incorporate classification information pertaining to the samples targeted for recovery. Let $\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}$ represent the samples recovered based on the aforementioned scheme. Our objective is to ensure that the subsequently recovered samples $\left\{\hat{\mathbf{x}_{i}}\right\}_{i=1}^{m}$ exhibit greater similarity to their counterparts in the training data space:

Specifically, we aim to maximize $M_{y_{i}}(\hat{\mathbf{x}_{i}};\boldsymbol{\theta})$ assigned to the predicted class for each sample $\hat{\mathbf{x}_{i}}$ by minimizing its negative absolute value. It is noteworthy that this optimization process does not utilize the original labels. Instead, it optimizes the model’s output confidence (logits) for samples $\left\{\hat{\mathbf{x}_{i}}\right\}_{i=1}^{m}$, aligning with our hypothesis of implementing unlearning verification using only the model parameters.

Finally, we define our recovery loss as:

where we eliminate the $L_{\text{additional}}$ loss term and incorporate $L_{\text{prior}}$ to enhance the fidelity of recovered samples.

To mitigate excessive deviation of the newly recovered samples $\left\{\hat{\mathbf{x}_{i}}\right\}_{i=1}^{m}$ from $\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}$ in the data space, we introduce a projection function, project_to_bounds, applied after each optimization epoch. This function constrains the pixel values of $\left\{\hat{\mathbf{x}_{i}}\right\}_{i=1}^{m}$ to within the range $[\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}-\epsilon,\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}+\epsilon]$. Our recovery algorithm is shown in Algorithm 2.

In lines 1-3, we initially optimize $\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}$ and $\left\{\lambda_{i}\right\}_{i=1}^{m}$ utilizing the loss $L_{\text{reconstruct}}=\alpha_{1}L_{\text{stationary }}+\alpha_{2}L_{\lambda}$. This preliminary phase ensures that $\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}$ achieves a basic level of recovery. Subsequently, we proceed to optimize $\left\{\mathbf{x}_{i}\right\}_{i=1}^{m}$ further to recover samples $\left\{\hat{\mathbf{x}_{i}}\right\}_{i=1}^{m}$ using the augmented loss function (lines 5-8). At each optimization epoch, we project the recovered samples onto a constrained space (line 8). This ensures they remain within a specified range of the pre-recovered samples while capturing more essential features required for effective unlearning verification.

Our machine unlearning verification scheme builds upon existing works [27, 26, 28, 29], extending their insights to the context of machine unlearning. We provide a rigorous theoretical basis for our verification method, incorporating concepts from optimization theory and functional analysis.

Let $D=\left\{\left(\mathbf{x}_{i},y_{i}\right)\right\}_{i=1}^{n}\subseteq\mathbb{R}^{d}\times\{-1,1\}$ be a binary classification training dataset. Consider a neural network $M(\boldsymbol{\theta};\cdot)$: $\mathbb{R}^{d}\rightarrow\mathbb{R}$ parameterized by $\theta\in\mathbb{R}^{p}$. The training process with a logistic loss $\ell(q)=\log\left(1+e^{-q}\right)$ can be viewed as an implicit margin maximization problem.

As we discussed in Theorem 1, for a homogeneous ReLU neural network $M(\boldsymbol{\theta};\cdot)$, gradient flow on the logistic loss

converges in direction to a KKT point of:

subject to

The KKT conditions for this problem yield [27, 26]:

Based on these KKT conditions, we can formulate a reconstruction method [28, 29]. The goal is to find a set of $\{\mathbf{x}_{i}\}_{i=1}^{m}$ and $\{\lambda_{i}\}_{i=1}^{m}$ that satisfy following equation:

where:

Let $U$ be an unlearning operator that unlearns $(\mathbf{x}_{i},y_{i})$ from a model with parameters $\tilde{\boldsymbol{\theta}}$ to $\boldsymbol{\theta^{\prime}}$:

To verify unlearning, we compare the recovered samples before and after unlearning those samples. Let $F$ be the index set of samples to be unlearned. The parameters of the model after unlearning $\boldsymbol{\theta}^{\prime}$ should also satisfy the KKT conditions:

And the corresponding $L_{stationary}$ is

where:

The verification involves:

1. 1.

   Performing sample recovery on both the original model $\tilde{\boldsymbol{\theta}}$ and the unlearned model $\boldsymbol{\theta}^{\prime}$, obtaining recovery samples sets $X=\{\mathbf{x}_{i}\}_{i=1}^{m}$ and $X^{\prime}=\{\mathbf{x}^{\prime}_{i}\}_{i=1}^{m}$.

2. 2.

   Calculating the differences between recovered samples:

   $$D_{i}=\|\mathbf{x}_{i}-\mathbf{x}^{\prime}_{i}\|$$

   (18)

3. 3.

   Comparing the differences for samples that unlearned and retained samples:

   $$E[D_{i}\mid i\in F]\text{ vs }E[D_{i}\mid i\notin F]$$

   (19)

If the unlearning process is effective, we expect:

This expectation arises because:

1. 1.

   For $i\notin F$, both $\mathbf{x}_{i}$ and $\mathbf{x}^{\prime}_{i}$ should satisfy the constraints of equations 9 and 14, leading to small differences.

2. 2.

   For $i\in F$, $\mathbf{x}_{i}$ satisfies equation 9 but not 14, while $\mathbf{x}^{\prime}_{i}$ does not satisfy equation 9 but satisfies equation 14, resulting in larger differences.

Additionally, recent work proposed by Buzaglo et al. [29] has extended the reconstruction method in [28] to multi-class classification scenarios. For a dataset $D_{m}=\{\left(\mathbf{x}_{i},y_{i}\right)\}_{i=1}^{n}\subseteq\mathbb{R}^{d}\times[C]$, where $C$ is the number of classes, and a neural network $M(\boldsymbol{\theta};\cdot)$: $\mathbb{R}^{d}\rightarrow\mathbb{R}^{C}$. Then, the KKT conditions for the multi-class problem yield:

The corresponding loss $L_{stationary}$ can be formulated as:

In this case, the above-proof process is also applicable. We will use this loss in our experimental evaluation when dealing with multi-classification tasks.

This theoretical framework utilizes the implicit bias inherent in neural network training and Karush-Kuhn-Tucker (KKT) conditions of margin maximization to evaluate the unlearning process. By analyzing the difference between recovered samples before and after the unlearning process, we can determine if the model provider has successfully removed the targeted samples from the model.

To evaluate our scheme, we utilize four widely-used image datasets: MNIST¹¹1http://yann.lecun.com/exdb/mnist/, Fashion MNIST²²2http://fashion-mnist.s3-website.eu-central-1.amazonaws.com/, CIFAR-10³³3https://www.cs.toronto.edu/ kriz/cifar.html and SVHN⁴⁴4http://ufldl.stanford.edu/housenumbers/.

Our evaluation includes sample and class level unlearning requests. To ensure consistency with existing studies [8], we employ retraining from scratch as our unlearning method.

As highlighted in Section III-A, the robustness of unlearning verification scheme is crucial for long-term deployment. A robust verification scheme should remain effective even after fine-tuning or pruning the models when the training or unlearning process is finished. In this Section, we evaluate the robustness of our proposed scheme, comparing it with the backdoor-based verification scheme [22]. We use the same experimental settings described in Section V-B1 and re-evaluate these schemes after performing the following operations:

1. (1)

   Training model $\rightarrow$ Pruning model

2. (2)

   Training model $\rightarrow$ Fine-tuning model

3. (3)

   Training model $\rightarrow$ Unlearning $\rightarrow$ Fine-tuning model

For pruning, we randomly prune $20\%$ of the parameters in each layer. For fine-tuning, we train the model using the original training samples and correct labels, maintaining the initial training configuration. For unlearning, we use retraining from scratch  [8]. The results of the backdoor-based scheme are illustrated in Figure 9, while Figure 10 presents the results of our proposed scheme.

Results: As shown in Figure 9(a), when the model undergoes pruning after training, the backdoor-based verification scheme becomes ineffective, as evidenced by the near-zero performance on the poison dataset. This indicates that the backdoor-based verification loses its robustness in the face of pruning operations, rendering it unusable. Similarly, in Figure 9(b), when fine-tuning is performed using the original, unperturbed training samples, the accuracy of the backdoor also decreases, indicating that fine-tuning also compromises the robustness of the backdoor-based verification scheme. Lastly, Figure 9(c) illustrates that when the model is finetuned with previously unlearned samples after unlearning, the backdoor-based verification scheme also fails due to the absence of the backdoor pattern in those samples. In conclusion, the backdoor-based method relies on pre-prepared samples for verification. If the backdoor pattern is not embedded in advance, if those patterns are disrupted after training, or if the backdoor has been previously used, subsequent verification will be infeasible.

Figure 10 shows the results obtained from our scheme. Figure 10(a) illustrate the original training sample, while other Figures show samples recovered after various processes: initial training (Figure 10(b)), pruning (Figure 10(c)), fine-tuning (Figure 10(d)), and unlearning followed by fine-tuning (Figure 10(e)). Unlike the backdoor-based scheme, our scheme effectively recovers training samples even after the model has been subjected to these modifications. This consistent performance demonstrates that our method exhibits a higher degree of robustness, maintaining its effectiveness across various post-training adjustments where the backdoor-based scheme fails.

Summary. The above experiments demonstrate that, as the backdoor-based verification scheme depends on pre-prepared patterns for verification, if those pre-prepared patterns are not embedded in advance, are disrupted after training, or have been previously used, subsequent verification becomes infeasible. In contrast, our method demonstrates consistent performance and a higher degree of robustness, maintaining effectiveness across various post-training adjustments.

As discussed in Section III-A, the ability to verify more samples is crucial in MLaaS unlearning verification. This section evaluates the number of verifications supported by our proposed scheme compared to the method introduced in [22]. Furthermore, in Section IV-C, we add a new constraint to improve the quality of recovered samples and provide more samples used for unlearning verification. In this Section, we also do a comparative analysis between our enhanced scheme and the data reconstruction scheme proposed in [29].

We follow experimental settings used in [29] to construct our comparison experiment. Specifically, we use the experimental setting in  V-B1 and select the MNIST dataset. We first recover samples based on the loss $L_{\text{reconstruct }}=\alpha_{1}L_{\text{stationary }}+\alpha_{2}L_{\lambda}$ and record the result as original. Then we add our new loss $\alpha_{3}L_{prior}$ to $L_{\text{reconstruct }}$ and continue to recover samples. We set $\alpha_{1}=1$, $\alpha_{1}=1$ and $\alpha_{3}=1$ and record the recover samples as ours. We adopted the same other hyperparameters provided in [29]. To evaluate the quality of our recovered samples, we employ the same evaluation method in [29]: for each sample in the original training dataset we search for its nearest neighbor in the recovered samples and measure the similarity using SSIM. A higher SSIM value indicates better recovery quality. In Figure 11(a), we plot the recovery quality (measured by SSIM) against the sample’s distance from the decision boundary. This distance is calculated based on:

where $M_{y_{i}}(\mathbf{x}_{i};\boldsymbol{\theta})$ is the logit for the true class, and $\max_{j\neq y_{i}}M_{j}(\mathbf{x}_{i};\boldsymbol{\theta})$ is the maximum logit among all other classes. In Figure 11(b), we show the change of SSIM for each corresponding original sample. For the backdoor-based scheme [22], we choose the experimental setting in V-B1 and use the same number of the training dataset in Buzaglo et al. [29]. The corresponding results are shown in Figure 11(c).

Results. Figures 11(a) demonstrates that both schemes proposed in [29] and ours successfully recover various samples from the model, aligning with the findings reported in [29]. In addition, our scheme shows an improvement, with a larger proportion of recovered samples (blue points) exhibiting greater similarity to the training dataset compared to the original scheme (red points) in Figure 11(a). Figure 11(b) visually represents this improvement, with green arrows indicating samples where our scheme achieves higher similarity, gray points representing unchanged similarity, and red arrows denoting decreased similarity. This improved similarity between recovered samples and training samples provides more samples for our subsequent verification processes.

Additionally, as shown in Figure 11(c), when the proportion of backdoored samples used for training is less than $5\%$, their performance is inadequate for unlearning verification. Effective verification is achieved only when the proportion of backdoored samples reaches $10\%$. This suggests that, for the MNIST dataset, approximately $10\%$ of the total training samples (500 in total) is necessary for a single verification. Given the total number of samples, it only supports $10$ times for verification. Furthermore, as the number of backdoored samples increases, the model’s performance will significantly decrease since the samples that have not been backdoored become less. For example, from Figure 11(c), when only $60\%$ training samples for original task training, the performance of the trained model will decrease to only $44\%$. For our scheme, we show some recovered samples in Figure 12. It can be seen that when the SSIM of the recovered image equals $0.15$, the recovered samples still partially retain information about the original sample. From Figure 11(a), we observe that approximately $255$ samples have an SSIM greater than $0.15$. This suggests that our scheme can support over $40$ times the number of verifications compared to backdoor-based methods, without compromising the model’s original performance.

Summary. Our enhanced sample recovery method significantly improves the quality of samples available for verification. In addition, it also allows a substantially higher number of verifications compared to existing backdoor-based methods, while maintaining model’s performance on its primary task.

Currently, many machine unlearning schemes achieve their goals through fine-tuning process [1]. This typically involves manipulating the samples targeted for unlearning, such as assigning random labels, and then fine-tuning the model with those relabeled samples [23, 24, 14, 25]. Experimental evaluations in these works, using membership inference attacks, model inversion attacks, backdoor attack and accuracy-based metrics, have suggested successful unlearning. However, the question remains: Is this truly the case?

Intuitively, any fine-tuning-based unlearning scheme involving unlearning samples should be considered incomplete, as samples targeted for unlearning are still processed by the model during the fine-tuning stage. To verify this hypothesis, we used the experimental setting described in Section V-B2, focusing on the MNIST dataset and replacing the unlearning method with relabel-based fine-tuning [14, 25]. We use our proposed scheme to recover samples both before and after fine-tuning. For evaluation, we select all recovered samples that can be correctly classified as class targeted for unlearning using the model before unlearning. Then, we calculate the SSIM between each recovered sample and its nearest original sample. Figure 13 shows the SSIM results, while Figure 14 shows some recovered samples after fine-tuning.

Results. As shown in Figure 13(a), before performing relabel-based finetuning, the SSIM between some recovered samples and training samples is very high, indicating that the trained model indeed contains some information about the class that needs to be unlearned. Figure 13(b) also reveals similar results, with many recovered samples exhibiting high similarity to the training samples (see both recovered samples in Figure 14). Furthermore, after fine-tuning, the number of recovered samples unexpectedly increases, as the model retains memory not only of the original training samples but also of the newly added fine-tuning samples. All those results suggest that even after unlearning, the model still retains information about the samples that need to be unlearned. Therefore, relabel-based fine-tuning is not an effective unlearning solution.