WHERE PRIVACY BELONGS: PLACEMENT DIAGNOSIS AND CERTIFIED SELECTION FOR PRIVATE COUNTERFACTUAL EXPLANATIONS ON GRAPHS

Counterfactual explanations for graph neural networks (GNNs) find the minimal intervention that flips a node’s prediction—the gold standard of recourse—but computing one requires reading sensitive graph structure, and releasing it discloses that structure. The two existing placements both fail. Privatizing the graph before explaining corrupts the explanation target on exactly the borderline nodes that need recourse, manufacturing spurious flips: interventions that flip the privatized graph but not the true one. Explaining on the clean graph and perturbing the released explanation resists certification: our re-audit of the standard heuristic shows that its implied full-release budget reaches 573–753 on Cora and 256 on CiteSeer—orders of magnitude beyond its advertised per-entry budget—with worst-case single-entry leakage at AUC 1.0. We propose PRIVCFS, which replaces certification-byoptimization 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, with no-op semantics so that every neighboring graph shares the same output support. A validity-gated, clipped utility whose global sensitivity bound ∆u ≤ 1 requires no optimizer sensitivity analysis is released through the exponential mechanism, giving pure ε-DP for the complete released object, composable over queries—to our knowledge the first such guarantee for counterfactual explanations on graphs. Empirically, privacy noise is the cheapest stage of the pipeline: the sampled release retains 94–97% of its support-restricted non-private optimum on the recourse population and 83– 95% on the general population at ε=8; the optimal likelihood-ratio edge-inference audit attains AUC 0.50 on average and 0.59 in the worst pair, against the heuristic baseline’s worst entry of 1.0 under the same attack; and the mechanism transfers to a 15K-node graph with a 0.96 valid rate at ε=8. The dominant cost is instead 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 for the data owner.Counterfactual explanations for graph neural networks (GNNs) find the minimal intervention that flips a node’s prediction—the gold standard of recourse—but computing one requires reading sensitive graph structure, and releasing it discloses that structure. The two existing placements both fail. Privatizing the graph before explaining corrupts the explanation target on exactly the borderline nodes that need recourse, manufacturing spurious flips: interventions that flip the privatized graph but not the true one. Explaining on the clean graph and perturbing the released explanation resists certification: our re-audit of the standard heuristic shows that its implied full-release budget reaches 573–753 on Cora and 256 on CiteSeer—orders of magnitude beyond its advertised per-entry budget—with worst-case single-entry leakage at AUC 1.0. We propose PRIVCFS, which replaces certification-byoptimization 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, with no-op semantics so that every neighboring graph shares the same output support. A validity-gated, clipped utility whose global sensitivity bound ∆u ≤ 1 requires no optimizer sensitivity analysis is released through the exponential mechanism, giving pure ε-DP for the complete released object, composable over queries—to our knowledge the first such guarantee for counterfactual explanations on graphs. Empirically, privacy noise is the cheapest stage of the pipeline: the sampled release retains 94–97% of its support-restricted non-private optimum on the recourse population and 83– 95% on the general population at ε=8; the optimal likelihood-ratio edge-inference audit attains AUC 0.50 on average and 0.59 in the worst pair, against the heuristic baseline’s worst entry of 1.0 under the same attack; and the mechanism transfers to a 15K-node graph with a 0.96 valid rate at ε=8. The dominant cost is instead 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 for the data owner.