Feature Unlearning: Theoretical Foundations and Practical Applications with Shuffling

We thank the reviewer for their feedback and for engaging with our work. We have carefully considered the comments and revised our manuscript/clarified our responses accordingly.

Response to “Lack of citations in 5.1 - where does TRI, RASI, etc. come from”

Thank you for your suggestions on adding references to the evaluation metrics.

The metrics Test Retention Index (TRI), Efficiency Index (EI) are stemmed from the reference [1], which was accepted by EuroS&P 2025.

Our study originally designed the metric Unlearning Robustness Against Shuffling Index (RASI) based on the shuffling characteristic of our shuffling-based approach. To calculate this metric, we shuffled the values of unlearned features within the test set and then observed whether such shuffling affects prediction outcomes. As a result, RASI can examine whether the unlearned model has successfully eliminated dependency on the unlearned feature regarding model predictions.

The other two metrics, i.e., SHAP Retention Index (SRI) and SHAP Distance-to-zero Index (SDI), were inspired by explainable AI techniques. In our study, we calculate each feature’s importance using the SHapley Additive exPlanations (SHAP). By applying an effective unlearning algorithm, the unlearned feature’s importance should be reduced to zero. The designed two SHAP-related metrics are able to investigate the targeted feature’s importance after unlearning.

[1] Xavier F. Cadet, Anastasia Borovykh, Mohammad Malekzadeh, Sara Ahmadi-Abhari, and Hamed Haddadi. Deep unlearn: Benchmarking machine unlearning

Response to “Why did the authors leave out bias/discrimination/privacy metrics from the evaluation”

We thank the reviewer for insightful feedback. We agree that evaluating the practical significance of feature unlearning requires auditing for both privacy and fairness, as accuracy alone is insufficient.

In our revised manuscript, we now include 1) a feature-level membership inference attack (MIA) and 2) fairness audits to evaluate our method in terms of privacy and fairness, respectively.

For 1), we adapt the standard MIA to the feature level. Instead of asking “was this individual data point in the training dataset?”, the feature-level MIA asks “was this feature used to train the model?”. For a successful unlearning algorithm, a feature-level attacker cannot distinguish the unlearned model from a model that is retrained from scratch without the unlearned feature.

We implement the feature-level MIA in the following steps. Firstly, we create an attack dataset. For each sample, we query $f_{\theta’}$ (model after unlearning) and $g_\phi$ (retrained-from-scratch model) to get their outputs, i.e., the full vector of prediction probabilities. Then, we label the outputs from $f_{\theta’}$ as class “Unlearned” and the outputs from $g_\phi$ as class “Retrained”.

Subsequently, we train an attack model – a RandomForecast binary classifier (via the $`sklearn`$ Python library) on this built attack dataset. This attacker’s job is to learn the subtle differences between the outputs distributions of our unlearned model ($f_{\theta’}$) and a truly “clean” model ($g_\phi$).

Finally, we evaluate this trained attack model on a holdout set of queries. The final “Attack Accuracy” is the new metric regarding privacy. An accuracy near 50% MIA suggests that the attacker cannot do better than random guessing. Our unlearned model ($f_{\theta’}$) is indistinguishable from a model retrained from scratch ($g_\phi$), which indicates that our unlearning is successful from the privacy perspective.

For 2), we introduce two standard fairness metrics – demographic parity (DP) and equalized odds (EO). For a successful unlearning, the fairness score of the unlearned model should be very close to the retrained-from-scratch model.

The DP score is calculated in the following steps. Firstly, we identify several key components related to DP, including

• Unprivileged/Privileged Groups: The group that has historically faced a disadvantage/advantage (e.g., for features like “Race” or “Gender”).
• Favorable Outcome: The desired model prediction (e.g., “loan approved”).
• Model Predictions: The output labels generated by our unlearned model or the retrained-from-scratch model.

Next, for both the privileged and unprivileged groups, we calculate the rate at which they receive the favorable outcome from models. The formula for the rate is calculated as

$$\textrm{Rate} = \frac{\textrm{Number of individuals in the group who received the favorable outcome​}}{\textrm{Total number of individuals in the group}}$$

The above rates are denoted as $\textrm{DP(Label=Favorable Outcome | Privileged Group)}$ and $\textrm{DP(Label=Favorable Outcome | Unprivileged Group)}$, respectively.

Finally, we calculate the DP differences between unprivileged and privileged groups, formulated as

$$\textrm{DP Difference} = \textrm{DP(Label=Favorable Outcome | Unprivileged Group) - \textrm{DP(Label=Favorable Outcome | Privileged Group)}}$$

A DP difference of zero indicates perfect fairness.

For the EO difference, we calculate the differences of True Positive Rate (TPR), False Positive Rate (FPR) between the privileged and the unprivileged groups. $\textrm{EO-TPR Difference} = \Delta\textrm{TPR}$ $\textrm{EO-FPR Difference} = \Delta\textrm{FPR}$

Both metrics should be as close as to zero from the perspective of fairness.

In the following, we present the results of feature-level MIA attack accuracy, DP difference, and EO differences (including both TPR and FPR) across all three adopted neural architectures (i.e., MLP, ResNet, and FT-Former). All results shown below are averaged across all four unlearned features, all three neural architectures, and all used datasets. In particular, the features “HouseAge”, “age”, “fConc:” in the CALI, CREDIT, MAGIC_TELE datasets are considered sensitive attributes, with thresholds of 20, 40, 0.5 to distinguish between privileged and unprivileged groups, respectively.

The below results demonstrate the effectiveness of our unlearning methods in terms of privacy and fairness.

Table 1: Averaged MIA attack accuracy across our unlearning method and the two baselines (optimal: 0.5)

Table 2: Averaged DP difference across our unlearning method and the two baselines (optimal: 0)

Table 3: Averaged EO-TPR difference across our unlearning method and the two baselines (optimal: 0)

Table 4: Averaged EO-FPR difference across our unlearning method and the two baselines (optimal: 0)

Thank you very much for your timely response! We sincerely appreciate the reviewer’s recognition of our additional privacy experiments and are pleased that the strong results further demonstrate the effectiveness of our proposed method.

1. Regarding the two “self-created” evaluation metrics, we respectfully believe there might have been a misunderstanding, and we kindly ask for the opportunity to further their motivation and theoretical grounding.

• The two “self-created” evaluation metrics were not arbitrarily defined; rather, they are carefully designed based on core principles of unlearning.
• Specifically, in an unlearning task, based on the definition, if a feature is successfully unlearned, it should exhibit the property that it no longer contributes to the model’s output (SDI, SRI), and any changes to that feature should have no impact on the model’s predictions (RASI).

2. Regarding the concern about the “lack of extensive discussion and validation,” in the original submitted manuscript, we have provided theoretical analysis and proofs supporting these two metrics.

• Appendix E provides a proof that our unlearning algorithm causes the Shapley value of the target feature to converge to zero almost surely. The metrics SRI and SDI are designed to directly and empirically measure this provable outcome.
• Theorem 4.1 and Appendix B show that a successfully unlearned feature should be independent of both other remaining features and the label. RASI aligns with this theoretical foundation, making it a well-justified metric for assessing unlearning effectiveness. Thank you for pointing this out and we will make this discussion much clearer in the revised manuscript.

Finally, we would also like to highlight that our evaluation incorporates all the metrics used in prior studies and additionally introduces the above theory-backed metrics to provide a more comprehensive and nuanced assessment of unlearning performance.

Thank you again for engaging with our rebuttal. We hope that our clarifications, along with the additional experiments, helps address the remaining concerns regarding the evaluation metrics and further strengthens the overall contribution. As always, we would be happy to respond to any additional questions.

Authors

Dear Reviewer nUD2,

Thank you so much for your positive engagement and for confirming that our rebuttal has addressed all of your concerns. We were very encouraged by your feedback and sincerely appreciate you taking the time to discuss our work.

As the discussion period is closing within 12 hours, we just wanted to send a gentle reminder regarding the final rating. If you have a moment, we would be sincerely grateful if you could update your score in the system to reflect your final assessment.

Thank you again for your valuable time and insightful review.

Authors

We thank the reviewer for their feedback and for engaging with our work. We have carefully considered the comments and revised our manuscript/clarified our responses accordingly.

Response to the assumption of access to the full training dataset

Our approach deliberately assumes access to the full training dataset, since the core mandate of machine unlearning is to eradicate the model’s dependence on specified data—not merely to sidestep access to the original training set. Methods that impose a rigid “no-access-to-data” constraint fundamentally compromise the integrity of unlearning by prioritising convenience over correctness, thereby failing to achieve robust, auditable, and faithful unlearning. Such a trade-off thus results in diluted guarantees and unverifiable unlearning outcomes.

Moreover, as the aim of our method is to re-establish the original empirical joint distribution while selectively breaking the dependence on the target feature, it is only achievable by reshuffling the feature across the entire training set (as shown in our theoretical proof), ensuring that all statistical relationships—especially between correlated variables—are properly preserved or neutralised. Without full data access, such reshuffling would introduce unintended distribution shifts or artifacts, thereby compromising the validity of unlearning.

We acknowledge that in certain regulatory or operational contexts, full access to the original training data may not be possible at unlearning time. In such cases, our method may not be directly applicable. However, we view this limitation not as a flaw, but as a deliberate design choice to prioritise unlearning fidelity and theoretical guarantees. Organisations can retain light-weight, privacy-preserving statistics (e.g., marginal feature distributions or conditional histograms) computed before deletion requests. These can support approximate feature removal via pseudo-shuffling or data regeneration, though the resulting guarantees will necessarily be weaker than our full-data method.

Response to the assumption of temporal shift or non-i.i.d. behavior

We adopt the i.i.d. and stationarity assumptions for three main reasons:

• The assumptions of i.i.d. samples and stationarity serve as a standard theoretical simplification that ensures mathematical tractability and allows us to build a rigorous understanding of model behaviour under controlled conditions.

• Moreover, our empirical evaluations demonstrate strong performance of our method across all tested datasets, indicating empirical robustness that extends beyond the idealised theoretical assumptions. Such empirical success reveal the capability of our method in handling real-world datasets which may not fully align with our assumptions and have substantial internal dependencies and correlations.

• These assumptions are standard throughout the machine learning and unlearning literature [1][2][3], and form the foundation of nearly all theoretical analyses of unlearning–retraining equivalence, e.g., SISA, FOUL, MIUL, where the latter two have been implemented as baselines in our experiments. Such frameworks consistently adopt empirical risk minimisation under the premise of a stable, stationary data-generating process.

In the revised manuscript, we have made this discussion clearer and explicitly distinguish between theoretical guarantees and practical robustness.

[1] Warnecke, Alexander, et al. "Machine unlearning of features and labels." arXiv preprint arXiv:2108.11577 (2021).

[2] Tao Guo, Song Guo, Jiewei Zhang, Wenchao Xu, and Junxiao Wang. Efficient attribute unlearning: Towards selective removal of input attributes from feature representations, 2022.

[3] Xu, Heng, et al. "Don't Forget Too Much: Towards Machine Unlearning on Feature Level." IEEE Transactions on Dependable and Secure Computing (2024).

Response to additional baselines that involving adversarial feature disentanglement or post-hoc pruning

First, we would like to clarify that FOUL, the first baseline we evaluated, is itself an adversarial method. Specifically, FOUL trains a feature discriminator in an adversarial setting to ensure that the representation does not encode information about the feature to be unlearned. This aligns closely with the family of adversarial feature disentanglement techniques the reviewer referred to.

Secondly, we include additional baselines that employ a model-centric adversarial masking strategy [3], in addition to two already-implemented baselines, i.e., FOUL and MIUL. Notably, our approach is fundamentally different from the strategy used in [3]. Instead of introducing complex architectural modifications, our method employs a simple yet effective data permutation (i.e., shuffling) technique that directly disrupts statistical dependencies. More importantly, our approach is backed by theoretical guarantees of achieving statistical independence, which distinguishes it from methods like [3] that lack such formal assurances.

As an example, the results on the Credit dataset below confirm our method's effectiveness against this newly added baseline.

Response to motivation related to unlearning sensitive attributes

Our method is capable of unlearning any individual feature or combination of features, including sensitive attributes, like gender or race (referred to Definition 3.1 and Theory 4.4 in the original manuscript). This flexibility is a direct consequence of both our theoretical guarantees and empirical design. Specifically, we provide formal proof that our approach removes statistical dependence between the unlearned feature and the model’s representation or output—regardless of the semantic nature of the feature itself.

To support this claim, we also conducted extensive evaluations across a wide range of tabular and visual datasets. In particular, for the visual datasets, we have targeted diverse features such as nose shape, eye size, and eyeglasses. These features vary substantially across individuals and may capture latent demographic cues, including those related to identity and fairness.

Further, we highlight our results on the CALI dataset, where we successfully unlearned the DebtRatio feature (see Appendix L, table 6, page 31 in the original manuscript)—a sensitive financial indicator tied to personal debt levels. The ability of our method to remove this feature while preserving model utility further underscores its effectiveness for privacy- and fairness-sensitive applications.

In the revised manuscript, we have clarified these points and expanded our discussion on how our approach applies to unlearning sensitive features such as race, gender, and socioeconomic attributes—areas that are closely aligned with the core motivation of our work.

Response to experiments on more complex visual features

The authors are not entirely certain what is meant by “more complex visual features,” but we attempt to address the question based on our interpretation. In raw, pixel-based human facial images, features such as the eyes, eyebrows, nose, mouth, and ears are semantically identical. Our method has already been evaluated on key features like the eyes, nose, and their combination (eyes + nose) across various classification tasks. Adding additional facial attributes of a similar nature does not introduce further methodological complexity for our approach, which directly processes raw image inputs without relying on specialised preprocessing. Moreover, identifying specific facial regions such as the nose or eyes or more ambiguous features is not the main focus of our study.

If we have misunderstood the reviewer’s request, please let us know—we would be happy to provide additional clarification or experiments as needed.

Response to more qualitative examples

In Appendix G of the original manuscript, we provided an image example illustrating the unlearning task for the nose feature to demonstrate the core idea behind our process. In the revised manuscript, we have expanded Appendix G to include a broader set of qualitative examples, covering all the test cases conducted on the image dataset. The enriched results now include diverse identities and multiple feature removal scenarios to provide a more comprehensive visual summary of the method’s effect.

We thank the reviewer for their feedback and for engaging with our work. We have carefully considered the comments and revised our manuscript/clarified our responses accordingly.

Response to the novelty of our paper

We would like to respectfully clarify that our method is both not "quite commonly used" and not mentioned in reference [1]. Our novelty is summarized in the following three aspects.

• Methodological Difference: Our method performs a global random permutation (i.e., shuffling) on the feature to be unlearned. This breaks the feature's statistical correlation with the label and other features. The method in [1] is fundamentally different; it uses influence functions to compute a local, approximate update to the model's parameters in response to a specific perturbation (i.e., adding noise or revoking it). Global shuffling is not discussed in their work.
• Novelty and Literature Context: To the best of our knowledge, global feature shuffling for unlearning is a new concept in the reviewed existing studies, as supported by comments from Reviewers ZoQd and nUD2 on our method's novelty.
• Empirical Superiority: In our original manuscript, we implemented the method from [1] as a primary baseline (termed FOUL). Our experimental results showed that our method consistently and significantly outperforms FOUL across all evaluation metrics.

Hence, our shuffling-based feature unlearning method is a novel contribution to the field, distinct from the influence-function-based approach of reference [1].

[1] Warnecke, Alexander, et al. "Machine unlearning of features and labels." arXiv preprint arXiv:2108.11577 (2021).

Response to baseline comparison

Firstly, we would like to clarify that, in our original manuscript, we identified two key related works in the field of feature unlearning and implemented them to compare with our proposed unlearning algorithm. The first identified work is the above mentioned FOUL [1] and the other is the work by [2], termed MIUL. The MIUL uses a representation detachment loss defined by mutual information to eliminate specific features. However, this method lacks a theoretical guarantee for the unlearning process. Also, mutual information is simultaneously estimated during unlearning, thereby introducing potential bias. In our original manuscript, our experiments demonstrated the superior performance of our method across all datasets and metrics.

Secondly, we appreciate the reviewer suggesting that some additional baselines were not properly mentioned in the literature review section, such as [3]. In our revised manuscript, we have 1) discussed [3] in the literature review part and 2) implemented [3] as another baseline in addition to FOUL and MIUL.

Our method differs fundamentally from the complex, model-centric adversarial masking used in [3]. Our simpler data permutation (i.e., shuffling) directly breaks statistical correlations and, critically, is supported by theoretical guarantees of achieving statistical independence—a distinct advantage that [3]'s framework lacks.

As an example, the results on the Credit dataset below confirm our method's effectiveness against this newly added baseline. The complete experiments and results have been updated in the revised manuscript.

[2] Tao Guo, Song Guo, Jiewei Zhang, Wenchao Xu, and Junxiao Wang. Efficient attribute unlearning: Towards selective removal of input attributes from feature representations, 2022.

[3]Xu, Heng, et al. "Don't Forget Too Much: Towards Machine Unlearning on Feature Level." IEEE Transactions on Dependable and Secure Computing (2024).

Response to used datasets in experiments

Thank you for the opportunity to clarify our experiments. We would like to highlight that the CelebA image dataset was not converted into a tabular format. Our unlearning method was applied directly to the visual features within the images themselves.

As detailed in Section 5.2 of the original manuscript, we addressed the challenge of implicit image features by shuffling specific image regions corresponding to semantic attributes. For the used CelebA image dataset, we unlearned features like "nose" and "eyes" by shuffling the corresponding image patches across the training set. Appendix G (in the original manuscript) provides a clear visual example of this process.

These image-based experiments, with full results for single and multi-feature scenarios in Figure 3 and Appendix N (in the original manuscript), complement our extensive evaluations on six diverse tabular datasets. Our experiments encompass seven datasets in total (six tabular and one image datasets), not just two. Various features has been unlearned within each used dataset to validate the effectiveness of our method. We trust this confirms the comprehensive nature of our experimental validation.

Response to evaluation metrics

We chose the "metric vs. number of epochs" curves to illustrate the convergence dynamics of the unlearning process, which we believe is a crucial aspect of evaluation. These plots show not just the final outcome, but also how efficiently each method reaches an effective state. For example, our results demonstrate that our unlearning method consistently achieves more effective unlearning (e.g., high RASI and TRI near 1.0) within a relatively small number of epochs. At this point of convergence, the efficiency (EI) remains very high, showcasing that our method does not require sacrificing efficiency for effectiveness.

Regarding the EI vs. RASI trade-off, while it is true that running more epochs generally improves unlearning (higher RASI) at the cost of efficiency (lower EI), our experiments show that our method reaches a near-perfect RASI long before the EI becomes impractically low. This rapid convergence is a key advantage over baselines, which may converge slowly or fail to reach an acceptable level of unlearning regardless of the number of epochs.

To make the results more direct and easier to compare, in the revised manuscript, we have adopted the format used in our multi-feature unlearning analysis (Tables 7, 8, and 9) and added summary tables for the single-feature experiments. These tables now report the values for all key metrics (TRI, EI, RASI, SRI, SDI) at a specific epoch count where our method has clearly converged, providing a clear, at-a-glance comparison that complements the dynamic curves.

Response to insufficient literature review

In the revised manuscript, we have included the reference [4] (that the reviewer mentioned) into our literature review as follows. The work [4] proposes a data privatization technique, not exactly a model unlearning method, that uses an adversarial filter-generator architecture to first remove a sensitive attribute and then synthetically replace it with a new, randomly sampled value. Their goal is to create a transformed, privacy-preserving dataset, which fundamentally differs from machine unlearning's objective of modifying a pre-trained model to make it forget learned information. Consequently, while our methods directly alter an existing model's parameters to achieve the unlearning of features, their technique serves as a data pre-processing step to anonymize a dataset before its use.

[4]Martinsson, John, et al. "Adversarial representation learning for synthetic replacement of private attributes." 2021 IEEE International Conference on Big Data (Big Data). IEEE, 2021.

Response to proof simplification

In the revised manuscript, we have streamlined the proof presentation. In addition, we would like to highlight that, though the idea of shuffling seems to be intuitive, a rigorous proof is necessary to formally guarantee that our method is effective. Our proof first establishes that shuffling creates statistical independence and then connects this property to the final model, showing it is $(\epsilon,\delta)$-close to a retrained one.

In the revised manuscript, we have included concise proof sketch in the main paper to improve readability and moved the detailed, complete proof to the appendix.

Dear Reviewer U1oC,

With the rebuttal period closing in less than 12 hours, we would like to respectfully follow up on our previous response. We hope we have been able to fully address your concerns and wanted to briefly summarize our clarifications.

In response to your review, we have:

• Clarified our focus on exact unlearning: We explained that our goal of providing theoretical guarantees for unlearning necessitates access to the original dataset, a standard requirement in this specific subfield.
• Discussed the scope regarding restricted data access: We acknowledged that approaches for restricted-access settings exist (e.g., using synthetic data or privacy-preserving summaries), but they cannot offer the formal equivalence guarantees that are the core of our work.
• Demonstrated real-world relevance: We highlighted that our model can be adopted under supervised access, thereby directly aligned with regulatory frameworks like the GDPR, where data controllers (such as Google and Microsoft) must verifiably prove deletion on the original data.

We would be very grateful for the opportunity to address any final questions you might have. If our rebuttal has clarified the points of concern, we would sincerely appreciate it if you would consider updating your score accordingly.

Thank you for your time and valuable feedback.

Authors

We thank the reviewer for their feedback and for engaging with our work. We have carefully considered the comments and revised our manuscript/clarified our responses accordingly.

Response to writing and overall presentation

Thank you for your feedback regarding the clarity of writing and notation. We appreciate the reviewer pointing this out, and we have taken steps to improve the overall presentation in the revised manuscript. Specifically, we have revised and clarified the notations in the formal definitions and theoretical sections, particularly in places where some symbols may have benefited from additional explanation. To further aid readability, we have included a dedicated table of notations in Appendix, which consolidates the definitions of all symbols, parameters, and variables used throughout the paper. This appendix also includes a brief explanation of the key mathematical tools we rely on (e.g., total variation distance and conditional independence) for readers who may not be familiar with them.

We hope these revisions make the theoretical sections more accessible and precise, and we welcome any further suggestions to improve clarity.

Response to the observations on patterns of unlearning various features

Thank you for this thoughtful question. We do observe some meaningful patterns in how different types of features affect unlearning performance, although these were only briefly mentioned in the original experimental section. To address this, we will expand the discussion in the revised manuscript to provide a more detailed analysis.

For single-feature unlearning, our method shows consistently strong performance, regardless of the importance or influence of the target feature. As shown in Figure 2 and Appendix F, even for features with high SHAP values, our approach achieves near-complete unlearning within approximately 150 epochs. This stability stems from the fact that our method explicitly removes statistical dependence by reshuffling the target feature across the entire training set, effectively breaking both direct and indirect correlations. The process does not rely on learning a complex adversarial signal, making it less sensitive to the feature's original importance. In contrast, baselines such as FOUL tend to perform better on less important features and struggle more with high-impact ones. This is likely because FOUL relies on an adversarial feature discriminator, which may face difficulty suppressing deeply entangled or high-importance signals within the model representation.

That said, we did observe that unlearning multiple features simultaneously is more challenging for all methods, including ours. These cases generally require longer training and exhibit slightly lower performance, likely due to the increased complexity of disentangling joint dependencies among multiple correlated features.

We will clarify these observations in the revised manuscript and expand our discussion in Appendix F to include a more detailed breakdown of performance trends across different feature types.