Privacy safe counterfactual explanations for graph neural networks
Where Privacy Belongs: Placement Diagnosis and Certified Selection for Private Counterfactual Explanations on Graphs
Machine Learning
Summary
Graph neural networks make predictions based on graph data, but explaining those predictions can expose sensitive connections in the graph. Existing methods either hide the graph too much or reveal too much, causing problems or privacy leaks. The authors propose PrivCFS, a method that safely selects explanations from fixed, public options, ensuring privacy while maintaining explanation quality. Their approach includes a strong privacy guarantee and works well on real graphs without leaking sensitive information.
What this means in practice
- •For data privacy teams: Securely provide private explanations for node predictions in sensitive graph datasets without risking data leaks.
- •For machine learning engineers: Integrate privacy-certified counterfactual explanations into graph-based AI models for trustworthy interpretability under privacy constraints.
Authors
Yuxiang Yao, Zijun Zhao
Abstract
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 $Δu \le 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.