# Private Counterfactual Retrieval

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 17 Oct 2024.

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

- [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)
- [Model extraction from counterfactual explanations](https://mlsanity.com/paper/2009.01884/) (2020)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [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)

## Built on by (most cited first, 2 of 2)

- [Private Counterfactual Retrieval With Immutable Features](https://mlsanity.com/paper/2411.10429/) (2024)
- [Where Privacy Belongs: Placement Diagnosis and Certified Selection for Private Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2609.37667/) (2026)

## Abstract (arXiv)

Transparency and explainability are two extremely important aspects to be considered when employing black-box machine learning models in high-stake applications. Providing counterfactual explanations is one way of fulfilling this requirement. However, this also poses a threat to the privacy of both the institution that is providing the explanation as well as the user who is requesting it. In this work, we propose multiple schemes inspired by private information retrieval (PIR) techniques which ensure the user's privacy when retrieving counterfactual explanations. We present a scheme which retrieves the exact nearest neighbor counterfactual explanation from a database of accepted points while achieving perfect (information-theoretic) privacy for the user. While the scheme achieves perfect privacy for the user, some leakage on the database is inevitable which we quantify using a mutual information based metric. Furthermore, we propose strategies to reduce this leakage to achieve an advanced degree of database privacy. We extend these schemes to incorporate user's preference on transforming their attributes, so that a more actionable explanation can be received. Since our schemes rely on finite field arithmetic, we empirically validate our schemes on real datasets to understand the trade-off between the accuracy and the finite field sizes. Finally, we present numerical results to support our theoretical findings, and compare the database leakage of the proposed schemes.