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

Yuxiang Yao; Zijun Zhao

cs.LGSep 29, 2026

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

Authors: Yuxiang Yao, Zijun Zhao

Organizations: Project Management Department, Research Center, China Life Insurance Company Ltd., Beijing, China · School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China

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.

Figures & tables

Figure 1: Overview of PrivCFS . The release selects from a fixed, data-independent candidate universe (public prior snapshot + public feature schema); the validity-gated utility carries a global sensitivity bound; the exponential mechanism releases the complete intervention set with pure $\varepsilon$ -DP. The crossed-out graph-level placement corrupts the explanation target and induces spurious flips (Sec. 3.2 ).

Dataset	$\rho$	starCF	@0.5	@1	@2	@4	@8	Ret.@8
Cora	0.5	$0.167{\pm}.373$	$0.078{\pm}.194$	$0.089{\pm}.215$	$0.098{\pm}.242$	$0.116{\pm}.278$	$0.139{\pm}.320$	84%
Cora	0.7	$0.250{\pm}.433$	$0.117{\pm}.235$	$0.123{\pm}.248$	$0.142{\pm}.282$	$0.172{\pm}.323$	$0.213{\pm}.377$	85%
Cora	1.0 †	$0.312{\pm}.464$	$0.136{\pm}.237$	$0.146{\pm}.248$	$0.166{\pm}.272$	$0.211{\pm}.336$	$0.260{\pm}.397$	83%
CiteSeer	0.5	$0.146{\pm}.353$	$0.076{\pm}.185$	$0.085{\pm}.210$	$0.091{\pm}.224$	$0.118{\pm}.287$	$0.139{\pm}.336$	95%
CiteSeer	0.7	$0.229{\pm}.420$	$0.114{\pm}.217$	$0.128{\pm}.239$	$0.152{\pm}.282$	$0.184{\pm}.340$	$0.219{\pm}.401$	95%
CiteSeer	1.0 †	$0.292{\pm}.455$	$0.145{\pm}.235$	$0.157{\pm}.259$	$0.181{\pm}.295$	$0.223{\pm}.352$	$0.268{\pm}.421$	92%

Table 1: Primary: the privacy–utility frontier on the general population (

16

publicly drawn targets per seed, mean

\pm

std over

n{=}48

3

seeds). starCF: support-restricted non-private ceiling; P(flip): valid rate of the sampled release (empty-output rate

0.1

–

0.4\%

throughout).

\rho

: public-prior strength (

\rho{<}1

certified;

{\dagger}

: data-dependent upper reference). Retention: P(flip)@

\varepsilon{=}8

/starCF.

Dataset	$\rho$	starCF	@0.5	@1	@2	@4	@8	Ret.@8
Cora	0.5	$0.500{\pm}.500$	$0.295{\pm}.315$	$0.328{\pm}.344$	$0.369{\pm}.380$	$0.420{\pm}.424$	$0.484{\pm}.484$	97%
Cora	0.7	$0.633{\pm}.482$	$0.373{\pm}.331$	$0.392{\pm}.340$	$0.448{\pm}.364$	$0.525{\pm}.411$	$0.614{\pm}.467$	97%
Cora	1.0 †	$0.900{\pm}.300$	$0.513{\pm}.235$	$0.544{\pm}.243$	$0.631{\pm}.252$	$0.742{\pm}.266$	$0.866{\pm}.291$	96%
CiteSeer	0.5	$0.367{\pm}.482$	$0.172{\pm}.235$	$0.199{\pm}.275$	$0.235{\pm}.315$	$0.288{\pm}.381$	$0.348{\pm}.458$	95%
CiteSeer	0.7	$0.567{\pm}.496$	$0.287{\pm}.287$	$0.314{\pm}.303$	$0.357{\pm}.334$	$0.447{\pm}.400$	$0.534{\pm}.468$	94%
CiteSeer	1.0 †	$0.767{\pm}.423$	$0.397{\pm}.263$	$0.439{\pm}.279$	$0.500{\pm}.307$	$0.611{\pm}.355$	$0.738{\pm}.408$	96%

Table 2: Diagnostic: the same frontier on borderline targets (

10

lowest-margin nodes per seed,

n{=}30

3

seeds). Columns as in Table 1 .

Borderline (diagnostic); support ceiling: starCF of Table 2
Dataset	Method	CSR $\uparrow$	Spur. $\downarrow$	Poll $\downarrow$	$\varepsilon$	Certified?
Cora	CF (no privacy)	1.000	0.000	0.000	$\infty$	—
Cora	RR-LDP (graph-level)	0.633 $\pm$ .125	0.367 $\pm$ .125	0.600 $\pm$ .141	7.2	✓(graph)
Cora	DP-SGD backbone	0.967 $\pm$ .047	0.433 $\pm$ .047	0.767 $\pm$ .047	7.16	✓(model)
Cora	PrivCF-out (heur.)	1.000	0.000	0.000	7.2	×
Cora	PrivCF-SGD	0.500 $\pm$ .141	0.000	0.000	7.16	✓

Table 3: Same-population mechanism comparison on the recourse population (borderline targets; the general-population rows mirror Table 1 , and the full baseline suite—PNS, RCExplainer, COMBINEX, NaiveDP, LapDP—is Table 8 in App. H ). Every row shares the same targets, the same public prior (

\rho{=}0.5

), and clean-graph validation. CSR: valid counterfactual rate on the clean graph (Ours-EM: sampled rate at

\varepsilon{=}8

). Spur./Poll.: spurious-flip / prediction-pollution rates. Certified: does the quoted

\varepsilon

certify the complete released object? PrivCF-out: heuristic output perturbation—full-release budget

573

–

753

256

(App. A ).

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	#Nodes	#Edges	Feat.	#Classes	Acc.
Cora	2,708	5,278	1,433	7	0.809
CiteSeer	3,327	4,552	3,703	6	0.682
ogbn-arxiv-core	15,000	160,944	128	40	0.792

Appendix

Table 4: Datasets and roles.

Figure 2: Loss decomposition on both protocols (

3

seeds; borderline:

n{=}30

targets, stratified:

n{=}48

). CF: non-private CF-GNNExplainer CSR (upper bound, Sec. 4.4 );

\rho{=}1

: valid rate of the support-restricted non-private optimum;

\rho{=}0.5

: the public-prior support (certified under the fixed-snapshot premise);

\varepsilon{=}8

: the sampled release (soft utility,

\Delta u{=}0.8

; the validity-gated variant reproduces every number within

\pm 0.01

). Annotated drops on the borderline chain mark each stage’s price: the privacy price (

{-}0.02

) is the smallest, and the public prior is the dominant purchase.

Arm	Cora	CiteSeer
edge-only (12/2, 0)	$0.500$ / $0.478{\pm}.478$	$0.367$ / $0.341{\pm}.449$
feature-only (0, 12/3)	$0.000$ / $0.000{\pm}0.000$	$0.000$ / $0.000{\pm}0.000$
joint (12/2, 12/3)	$0.500$ / $0.485{\pm}.486$	$0.367$ / $0.349{\pm}.459$

Appendix

Table 5: Edge vs. feature contribution of the certified arm (borderline,

\rho{=}0.5

\varepsilon{=}8

3

seeds): starCF / P(flip)@

\varepsilon{=}8

. The feature-only arm is exactly zero—the certified arm’s utility is carried by public-prior edge interventions, not by the (privacy-free) feature masking.

Figure 3: Audit of the certified release (

80

real adjacent pairs per dataset,

\varepsilon{=}8

\Delta u{=}1

). Left: per-pair likelihood-ratio attack AUC (black ticks: mean and max). The release sits at chance on average and below

0.59

on every pair; measured max

|\Delta u|{=}0.96

(bound

1.0

), and the support-optimum changes on only

8.75\%

3.75\%

of pairs (Cora/CiteSeer). Right: maximum release-probability ratio versus the

e^{8}{=}2981

bound (log scale)—the measured worst case,

35.3

, sits two orders of magnitude below the guarantee. The audit is supplementary evidence for Theorem 1 , not a substitute for it.

Dataset	$\rho$	starCF	@2	@4	@8
arxiv-core	0.5	$1.000{\pm}.000$	$0.734{\pm}.147$	$0.838{\pm}.110$	$0.963{\pm}.026$
arxiv-core	1.0 †	$1.000{\pm}.000$	$0.704{\pm}.143$	$0.831{\pm}.107$	$0.957{\pm}.056$

Appendix

Table 6: Transfer to ogbn-arxiv-core (

15{,}000

nodes,

160{,}944

edges,

40

classes): borderline protocol,

10

lowest-margin test nodes, mean

\pm

std over targets (one seed; margins

\approx 8{\times}10^{-4}

—the GNN is near-tied on all targets). starCF: support-restricted non-private ceiling; P(flip): sampled valid rate; sampled releases average

4.24{\pm}0.22

4.31{\pm}0.13

budget elements at

\varepsilon{=}8

Figure 4: Privacy–utility frontier (

3

seeds). Left: general population (primary,

16

publicly drawn targets per seed); right: borderline targets (diagnostic of the recourse population,

10

lowest-margin nodes per seed). Solid curves: valid counterfactual rate

P(\mathrm{flip})

of the sampled release versus budget

\varepsilon

(log scale), per public-prior strength

\rho

; shaded bands:

\pm 1

std; dashed lines: starCF, the support-restricted non-private ceiling;

{\dagger}

: data-dependent upper reference (Sec. 4.1 ). Ret.@8: retention of the ceiling at

\varepsilon{=}8

. Privacy noise costs little at

\varepsilon\geq 4

, while the ceiling itself is set by the public prior—the binding constraint (Tables 1 and 2 ).

Dataset	starCF	restr.-NaiveDP	Poll.	Ours-EM@8
Cora	$0.500{\pm}.500$	$\mathbf{0.000{\pm}0.000}$	0.733	$0.485{\pm}.486$
CiteSeer	$0.367{\pm}.482$	$\mathbf{0.000{\pm}0.000}$	0.700	$0.349{\pm}.459$

Appendix

Table 7: Same-operation-space placement control (borderline protocol,

\rho{=}0.5

3

seeds,

n{=}30

targets). Every row uses the identical candidate support; validity columns are clean-graph CSR / P(flip). starCF: support-restricted non-private optimum on the clean graph. restricted-NaiveDP: privatize the graph first (Gaussian,

\varepsilon{=}7.2

), take the support-restricted argmax on the privatized graph, then verify it on the clean graph (protocol in Ablation (j)). Ours-EM: sampled release at

\varepsilon{=}8

General population (primary)
Dataset	Method	CSR $\uparrow$	Spur. $\downarrow$	Poll $\downarrow$	$\varepsilon$	Certified?
Cora	starCF (support ceiling)	0.167 $\pm$ .373	0.000	0.000	$\infty$	—
Cora	CF (no privacy)	1.000	0.000	0.000	$\infty$	—
Cora	PNS (causal)	0.958 $\pm$ .029	0.000	0.000	$\infty$	—
Cora	RCExplainer (rob.)	0.854 $\pm$ .029	0.000	0.000	$\infty$	—
Cora	COMBINEX (unif.)	0.646 $\pm$ .059	0.000	0.000	$\infty$	—

Appendix

Table 8: Same-population mechanism comparison: every row shares the same target nodes, the same public prior (

\rho{=}0.5

), and the same clean-graph validation. General panel: the primary table,

16

fixed publicly drawn targets

\times

3

seeds. Borderline panel: diagnostic, the

10

lowest-margin targets

\times

3

seeds. CSR: valid counterfactual rate on the clean graph (for Ours-EM, the sampled rate at

\varepsilon{=}8

; non-empty invalid releases count as failures, and the empty-output rate is

0.1

–

0.4\%

). starCF: the support-restricted non-private ceiling—the same-operation-space reference. Spur./Poll: spurious-flip and prediction-pollution rates (diagnostic). Certified: does the quoted

\varepsilon

certify the complete released object?

\varepsilon{=}7.2

rows: graph-level Gaussian/Laplace/RR releases of the adjacency;

\varepsilon{=}7.16

: Opacus RDP,

T{=}100

\sigma{=}7

. PrivCF-out: heuristic output perturbation—full-release budget

573

–

753

256

(App. A ), listed as non-certified. Ours-EM: pure

\varepsilon

-DP (certified arm, Sec. 4.1 ). Operation spaces differ (continuous masks vs.

\leq 2

edges

+\leq 3

features); starCF is the same-operation-space non-private anchor.

Figure 5: Population gating (deployment guidance). Solid bars: starCF, the support-restricted non-private ceiling; hatched bars: valid-CF rate of the sampled release at

\varepsilon{=}8

; whiskers:

\pm 1

std across

3

seeds;

{\dagger}

: data-dependent upper reference (Sec. 4.1 ). The ceiling is a one-number function of the target’s margin (borderline

{\approx}0.008

vs. general

0.69

–

0.75

): the owner may choose who to explain from public information at no privacy cost, while margin-based gating would itself disclose private margin information and is reported only as a diagnostic.

Explore similar work

Graph Reconstruction from Differentially Private GNN Explanations
May 5, 2026Rishi Raj Sahoo, Jyotirmaya Shivottam, Subhankar MishraData Leakage Differential Privacy
National Institute of Science Education and Research (NISER), Bhubaneswar, India · Homi Bhabha National Institute, Mumbai, India
RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks
Sep 29, 2026Yuxiang Yao, Zijun ZhaoGNN Explainability Counterfactual Learning
Project Management Department, Research Center, China Life Insurance Company Ltd. · School of Computer Science and Technology, Beijing Institute of Technology
A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit
Sep 4, 2026Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1Counterfactual Explanations GNN Explainability
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece

May 5, 2026, cs.LGJ/K move · Enter open · S save

Graph Reconstruction from Differentially Private GNN Explanations

Rishi Raj Sahoo, Jyotirmaya Shivottam, Subhankar Mishra

National Institute of Science Education and Research (NISER), Bhubaneswar, India · Homi Bhabha National Institute, Mumbai, India

Data Leakage Differential Privacy GNN Explainability

Open paper AskPDF arXiv

Regulatory frameworks such as GDPR increasingly require that ML predictions be accompanied by post-hoc explanations, even when raw data and trained models cannot be released. Differential privacy (DP) is the standard mitigation for the residual privacy risk of releasing these explanations. We show that DP is not sufficient: an adversary observing only DP-perturbed GNN explanations can reconstruct hidden graph structure with high accuracy. Our attack, PRIVX, exploits the fact that the Gaussian DP mechanism is a single DDPM forward step at known noise level σ(ε), recasting reconstruction as reverse diffusion conditioned on the corrupted signal, a principled Bayesian denoiser under known DP corruption. We formalise a stratified adversary model parameterised by (M, \hatε, \hatδ, S, ρ) that interpolates between oblivious and oracle attackers, and derive endpoint-matched two-sided bounds on reconstruction AUC. For practitioners, we provide regime-stratified guidance on explainer choice: on homophilic graphs, neighbourhood-aggregating explainers (GraphLIME, GNNExplainer) leak more structure than per-node gradient explainers under the same DP budget; on strongly heterophilic graphs the ordering reverses. We introduce PRIVF as an auxiliary diagnostic sharing the same diffusion backbone to decompose leakage into explainer-induced and intrinsic graph-distribution components. Experiments across seven benchmarks, three DP mechanisms, and three GNN backbones show PRIVX achieves AUC above 0.7 at ε = 5 on five of seven datasets, with the attack succeeding well within typically deployed privacy budgets.

Abstract

Explore similar work

Graph Reconstruction from Differentially Private GNN Explanations

RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks

A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit