# Where Privacy Belongs: Placement Diagnosis and Certified Selection for Private Counterfactual Explanations on Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 27 references that are in the map.
- First posted on arXiv 29 Sep 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [Exploiting Explanations for Model Inversion Attacks](https://mlsanity.com/paper/2104.12669/) (2021)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [Interpretable and Differentially Private Predictions](https://mlsanity.com/paper/1906.02004/) (2019)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [Differentially Private Counterfactuals via Functional Mechanism](https://mlsanity.com/paper/2208.02878/) (2022)
- [Feature-based Learning for Diverse and Privacy-Preserving Counterfactual Explanations](https://mlsanity.com/paper/2209.13446/) (2022)
- [On the Probability of Necessity and Sufficiency of Explaining Graph Neural Networks: A Lower Bound Optimization Approach](https://mlsanity.com/paper/2212.07056/) (2022)
- [DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy](https://mlsanity.com/paper/2210.04442/) (2022)
- [Private Counterfactual Retrieval](https://mlsanity.com/paper/2410.13812/) (2024)
- [COMBINEX: A Unified Counterfactual Explainer for Graph Neural Networks via Node Feature and Structural Perturbations](https://mlsanity.com/paper/2502.10111/) (2025)

## Abstract (arXiv)

Counterfactual explanations for graph neural networks (GNNs) find the minimal intervention that flips a node's prediction--but computing one requires reading sensitive graph structure, and releasing it discloses that structure. Both existing placements fail. Privatizing the graph before explaining corrupts the target on exactly the borderline nodes needing recourse, manufacturing spurious flips that flip the privatized graph but not the true one. Explaining on the clean graph and perturbing the released explanation resists certification: re-auditing the standard heuristic shows an implied full-release budget of 573--753 on Cora and 256 on CiteSeer--orders of magnitude beyond its advertised budget--with worst-case single-entry leakage at AUC 1.0. We propose PrivCFS, which replaces certification-by-optimization with certification-by-construction: counterfactual selection over a fixed, data-independent candidate universe--edge interventions from a public prior graph, feature interventions from a public schema--whose no-op semantics give neighboring graphs the same output support. A validity-gated, clipped utility of global sensitivity Delta u ≤ 1 released through the exponential mechanism gives pure varepsilon-DP for the complete released object, composable over queries--to our knowledge the first such guarantee on graphs. Privacy noise is the cheapest stage: at varepsilon=8 the release retains 94--97% of its support-restricted non-private optimum on the recourse population and 83--95% on the general one; the optimal edge-inference audit attains AUC 0.50 on average and 0.59 worst-pair, versus the heuristic's worst entry 1.0; and transfers to a 15K-node graph at 0.96 valid rate. The dominant cost is a measurable, monotone price in public disclosure, readable off one table before any budget is spent--turning explanation privacy from an accounting risk into a purchasable decision.