On the Privacy Risks of Algorithmic Recourse

Martin Pawelczyk, Himabindu Lakkaraju, Seth Neel

Abstract: As predictive models are increasingly being employed to make consequential decisions, there is a growing emphasis on developing techniques that can provide algorithmic recourse to affected individuals. While such recourses can be immensely beneficial to affected individuals, potential adversaries could also exploit these recourses to compromise privacy. In this work, we make the first attempt at investigating if and how an adversary can leverage recourses to infer private information about the underlying model’s training data. To this end, we propose a series of novel membership inference attacks which leverage algorithmic recourse. More specifically, we extend the prior literature on membership inference attacks to the recourse setting by leveraging the distances between data instances and their corresponding counterfactuals output by state-of-the-art recourse methods. Extensive experimentation with real world and synthetic datasets demonstrates significant privacy leakage through recourses. Our work establishes unintended privacy leakage as an important risk in the widespread adoption of recourse methods.

Introduction

As machine learning models are increasingly deployed in high-stakes domains like finance and healthcare, there is a growing legal and ethical push to provide algorithmic recourse to individuals who receive negative outcomes. Recourse algorithms generate "counterfactual explanations" that tell a user exactly what features to change to flip the model's decision (e.g., "increase your income by $5k to get this loan").

While there is extensive literature on privacy attacks against ML models—such as Membership Inference Attacks (MIAs), which deduce whether a specific person's data was in the private training set—no prior work has investigated the privacy risks inherent in algorithmic recourse. This research addresses a highly practical threat model: If an adversary only has access to a user's original data and the single counterfactual explanation provided by the system, can they infer sensitive information about the model's private training data?

Methodology

Standard MIAs typically rely on accessing the model's confidence scores or loss values, exploiting the fact that models usually have lower loss on data they were trained on. This paper introduces a novel class of Counterfactual Distance-based (CFD) attacks that require no direct access to the model's loss or true labels, and only require a single query to the recourse algorithm.

CFD Thresholding Attack

During training, optimization tends to push the model's decision boundary away from the training points. Therefore, the distance between an input and its counterfactual (which sits on the decision boundary) acts as a proxy for membership. If the distance is greater than a certain threshold, the attack classifies the point as a member of the training set.

CFD Likelihood Ratio Test (LRT)

A more sophisticated, state-of-the-art approach involves training "shadow models" on public data to estimate the probability distributions of counterfactual distances for both "in" (training) and "out" (test) points. The adversary then uses a likelihood ratio test to classify new points based on these distributions.

The authors also provide theoretical bounds, showing that if the recourse generation algorithm is Differentially Private (DP), the success rate of any membership inference attack is strictly bounded.

Experimental Setup

The attacks were evaluated using three real-world tabular datasets and one synthetic dataset:

  • Adult (Census): Predicting if an individual's income exceeds $50k/year.
  • Heloc (Home Equity Line of Credit): Predicting if a borrower will repay a loan account.
  • Diabetes: Predicting hospital readmission within 30 days based on medical records.
  • Synthetic Data: Generated to precisely control feature dimensionality and model capacity to study the underlying mechanisms of attack success.

Key Results and Insights

The physical distance to a counterfactual explanation is a surprisingly strong signal for membership inference. Because models overfit, they carve out "safe zones" around training data, making training points measurably further from the decision boundary than unseen test points.

ROC curves for CFD attacks across different datasets (Adult, Heloc, Diabetes) and recourse methods (SCFE, GS, CCHVAE).

As shown in the ROC curves above, the proposed CFD LRT attack consistently outperforms random guessing and simple distance thresholding, especially in the critical low False Positive Rate (FPR) regime. The Heloc dataset proved particularly vulnerable. At an FPR of 0.01, the CFD LRT attack achieved True Positive Rates (TPR) that were significantly higher than the random baseline across three different standard recourse algorithms: SCFE, GS, and CCHVAE.

Interestingly, when using generative models to create recourses (like CCHVAE), the attack logic reverses. Generative models inherently produce samples closer to their training data; therefore, a smaller distance to the recourse strongly indicates membership. This effect is most pronounced in the Heloc dataset under the CCHVAE method.

Detailed ROC curve for the Heloc dataset using the CCHVAE recourse method, showing high True Positive Rates at low False Positive Rates.

Furthermore, synthetic experiments revealed a "curse of dimensionality" for privacy: attacks become significantly more potent as the number of features and model capacity increase. On high-dimensional synthetic data, the recourse-based CFD LRT attack actually outperformed state-of-the-art loss-based attacks.

Conclusion and Future Work

This work demonstrates that unintended privacy leakage is a significant risk in the adoption of recourse methods. In 7 out of 8 real-world dataset/recourse combinations, the CFD LRT attack achieved reliable privacy leakage.

Future research is urgently needed to develop mitigation strategies, such as heuristic defenses or novel ways to generate Differentially Private recourses that maintain utility. A deeper theoretical exploration into how the geometry of a model's decision boundary relates to privacy leakage will also be crucial for building more robust and private machine learning systems.

Summary updated

Abstract

As predictive models are increasingly being employed to make consequential decisions, there is a growing emphasis on developing techniques that can provide algorithmic recourse to affected individuals. While such recourses can be immensely beneficial to affected individuals, potential adversaries could also exploit these recourses to compromise privacy. In this work, we make the first attempt at investigating if and how an adversary can leverage recourses to infer private information about the underlying model’s training data. To this end, we propose a series of novel membership inference attacks which leverage algorithmic recourse. More specifically, we extend the prior literature on membership inference attacks to the recourse setting by leveraging the distances between data instances and their corresponding counterfactuals output by state-of-the-art recourse methods. Extensive experimentation with real world and synthetic datasets demonstrates significant privacy leakage through recourses. Our work establishes unintended privacy leakage as an important risk in the widespread adoption of recourse methods.
BibTeX
@inproceedings{pawelczyk2023privacy,
  author = {Martin Pawelczyk and Himabindu Lakkaraju and Seth Neel},
  title = {{On the Privacy Risks of Algorithmic Recourse}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=eSjJSPfTHE},
}
Figure