  When individuals are subject to adverse outcomes from machine learning
models, providing a recourse path to help achieve a positive outcome is
desirable. Recent work has shown that counterfactual explanations - which can
be used as a means of single-step recourse - are vulnerable to privacy issues,
putting an individuals' privacy at risk. Providing a sequential multi-step path
for recourse can amplify this risk. Furthermore, simply adding noise to
recourse paths found from existing methods can impact the realism and
actionability of the path for an end-user. In this work, we address privacy
issues when generating realistic recourse paths based on instance-based
counterfactual explanations, and provide PrivRecourse: an end-to-end privacy
preserving pipeline that can provide realistic recourse paths. PrivRecourse
uses differentially private (DP) clustering to represent non-overlapping
subsets of the private dataset. These DP cluster centers are then used to
generate recourse paths by forming a graph with cluster centers as the nodes,
so that we can generate realistic - feasible and actionable - recourse paths.
We empirically evaluate our approach on finance datasets and compare it to
simply adding noise to data instances, and to using DP synthetic data, to
generate the graph. We observe that PrivRecourse can provide paths that are
private and realistic.
