# Private Counterfactual Retrieval With Immutable Features

arXiv: https://arxiv.org/abs/2411.10429 · HTML: https://mlsanity.com/paper/2411.10429/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 44 references that are in the map.
- First posted on arXiv 15 Nov 2024.

## Builds on (most cited first, 29 of 29)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [NICE: An Algorithm for Nearest Instance Counterfactual Explanations](https://mlsanity.com/paper/2104.07411/) (2021)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [A Survey on the Robustness of Feature Importance and Counterfactual Explanations](https://mlsanity.com/paper/2111.00358/) (2021)
- [DualCF: Efficient Model Extraction Attack from Counterfactual Explanations](https://mlsanity.com/paper/2205.06504/) (2022)
- [On the Privacy Risks of Algorithmic Recourse](https://mlsanity.com/paper/2211.05427/) (2022)
- [The privacy issue of counterfactual explanations: explanation linkage attacks](https://mlsanity.com/paper/2210.12051/) (2022)
- [Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory](https://mlsanity.com/paper/2405.05369/) (2024)
- [Differentially Private Counterfactuals via Functional Mechanism](https://mlsanity.com/paper/2208.02878/) (2022)
- [Private Retrieval, Computing and Learning: Recent Progress and Future Challenges](https://mlsanity.com/paper/2108.00026/) (2021)
- [The Capacity of Private Information Retrieval](https://mlsanity.com/paper/1602.09134/) (2016)
- [The Capacity of Robust Private Information Retrieval with Colluding Databases](https://mlsanity.com/paper/1605.00635/) (2016)
- [The Capacity of Private Information Retrieval from Coded Databases](https://mlsanity.com/paper/1609.08138/) (2016)
- [The Capacity of Symmetric Private Information Retrieval](https://mlsanity.com/paper/1606.08828/) (2016)
- [Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes](https://mlsanity.com/paper/1702.01739/) (2017)
- [Privacy-Preserving Algorithmic Recourse](https://mlsanity.com/paper/2311.14137/) (2023)
- [Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost](https://mlsanity.com/paper/1808.07536/) (2018)
- [Semantic Private Information Retrieval](https://mlsanity.com/paper/2003.13667/) (2020)
- [The Capacity of Private Information Retrieval from Byzantine and Colluding Databases](https://mlsanity.com/paper/1706.01442/) (2017)
- [Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching](https://mlsanity.com/paper/1709.01056/) (2017)
- [Private Information Retrieval Through Wiretap Channel II: Privacy Meets Security](https://mlsanity.com/paper/1801.06171/) (2018)
- [The Capacity of Private Information Retrieval with Eavesdroppers](https://mlsanity.com/paper/1804.10189/) (2018)
- [The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases](https://mlsanity.com/paper/1805.04104/) (2018)
- [The Capacity of Private Information Retrieval from Heterogeneous Uncoded Caching Databases](https://mlsanity.com/paper/1902.09512/) (2019)
- [Private Counterfactual Retrieval](https://mlsanity.com/paper/2410.13812/) (2024)

## Abstract (arXiv)

In a classification task, counterfactual explanations provide the minimum change needed for an input to be classified into a favorable class. We consider the problem of privately retrieving the exact closest counterfactual from a database of accepted samples while enforcing that certain features of the input sample cannot be changed, i.e., they are immutable. An applicant (user) whose feature vector is rejected by a machine learning model wants to retrieve the sample closest to them in the database without altering a private subset of their features, which constitutes the immutable set. While doing this, the user should keep their feature vector, immutable set and the resulting counterfactual index information-theoretically private from the institution. We refer to this as immutable private counterfactual retrieval (I-PCR) problem which generalizes PCR to a more practical setting. In this paper, we propose two I-PCR schemes by leveraging techniques from private information retrieval (PIR) and characterize their communication costs. Further, we quantify the information that the user learns about the database and compare it for the proposed schemes.