acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
interpretability and explainable AI
Keywords:
Graph neural networks, counterfactual explanations, differential privacy, private selection, privacy–utility tradeoff

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Lf9YOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to release counterfactual explanations for graph neural networks while limiting disclosure of sensitive edges. It contrasts graph perturbation before explanation with heuristic perturbation of an optimized explanation, identifying prediction pollution and incomplete privacy accounting. PRIVCFS selects an intervention from a fixed public candidate universe using a bounded utility and the exponential mechanism, with no-op semantics for nonexistent edges. The resulting pure edge-level differential privacy guarantee conditions on a fixed public snapshot, public features, a public frozen backbone, and an externally specified target. Experiments on Cora, CiteSeer, and an ogbn-arxiv subset show high retention of the restricted non-private ceiling, although absolute validity depends strongly on the candidate support and target population.

Critical strengths

1.Valid conditional release construction. The bounded utility and identical output support provide a straightforward pure-DP proof for the complete intervention rather than individual coordinates.

2.Useful separation of sources of utility loss. The paper reports both absolute validity and retention relative to the support-restricted optimum, with separate random and borderline populations.

3.Substantive implementation and leakage checks. Small-graph neighbor checks, exact release-distribution audits, and edge-versus-feature ablations test several mechanisms that could otherwise undermine the claim.

Critical weaknesses

1.The public-prior experiment supports a conditional claim. Section 3.3 generates the experimental snapshot by sampling a fraction of the current private edges, while the theorem requires a fixed public context and separately accounts for any snapshot disclosure. Conditioning on an already public snapshot is legitimate, but these experiments do not establish the privacy cost or utility of obtaining that snapshot from private data. Consequently, the claim that disclosure can be purchased before spending any budget needs to be restricted to an externally fixed public prior.

2.High retention does not establish broadly effective recourse. At epsilon 8 and snapshot strengths 0.5/0.7, general-population validity is only 13.9%–21.9%, and nonempty invalid releases are counted as failures rather than prevented. The worst-case utility bound is explicitly vacuous at the operating parameters, while repeated releases consume additional budget. The 96.3% scale result uses one seed and ten lowest-margin nodes, so it provides limited support for practical recourse across a large graph.

3.Some baseline privacy labels are insufficiently justified. Equation 3 uses the classical Gaussian calibration expression at epsilon approximately 7.2 without documenting an applicable accountant and numerical delta; its familiar sufficient theorem has an epsilon-range restriction. Appendix A also calls values obtained from sampled optimizer-output differences true or effective full-release budgets, although sampled maxima cannot establish global sensitivity or the exact privacy loss of a randomized optimization pipeline. These issues weaken the advertised certified comparison and quantitative re-audit, while leaving the bounded-utility proof for PRIVCFS intact.

Questions for authors

1.For each reported certified arm, was the snapshot held fixed across neighboring graphs, and what concrete externally fixed snapshot or separately private snapshot mechanism is the intended deployment assumption? Please identify which private edges remain protected relative to that public disclosure and which additional release costs are excluded.

2.What numerical delta, adjacency unit, clipping/sampling assumptions, and Gaussian or RDP accountant support the certified labels for the Gaussian and PrivCF-SGD baselines? How do the resulting guarantees compare under the same edge-level neighboring relation as Theorem 1?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Lf9Y (Part 1/3)

We thank the reviewer for the careful distinction between the conditional construction (which the review confirms is intact) and the certification labels of the baselines, and for the two concrete questions. We answer both, then address the W2 items.

Q1. For each certified arm, was the snapshot held fixed across neighboring graphs? What is the intended deployment assumption, which edges remain protected, and which costs are excluded?

Answer. Yes — in all PrivCFS arms the candidate universe and output support are functions of the public context only (public snapshot, public features, frozen backbone), so they are fixed across neighboring graphs by construction; this is exactly what Lemma 1 and the implementation-level certification checks (small-graph neighbor checks, exact release-distribution audits, probability-ratio checks) verify. Arm by arm:

ArmSnapshot sourceFixed across neighbors?What is protected
Ours-EM, simulated prior (Tables 1/2)Subsample of current edges, designated publicYes (support depends only on public context)Residual edges E ∖ E_pub
Ours-EM, external priors (new: historical / metadata network)Public, independent of current edgesYesAll current private edges
NaiveDP graph release— (releases a noisy graph)n/aAll edges, at its own (ε, δ) label
PrivCF-SGD— (private training)n/aTraining edges, at its own (ε, δ) label

Deployment assumption: an externally fixed public snapshot — now instantiated by two working constructions (historical-scenario reconstruction on arxiv, reaching 97.7–120% of the privileged prior's utility; feature-kNN metadata network on Planetoid, which carries zero edge knowledge and recovers 58–64% (CiteSeer) / 25–47% (Cora) of it on the borderline population; full tables in the overview comment). The temporal arm makes the premise concrete as a historical-scenario reconstruction: the public context is the citation state observable at time T (all edges with both endpoint years ≤ T, exact under the append-only structure of citation graphs), and every newer edge is protected. Protected object: all edges not in the public snapshot; excluded costs: snapshot construction, target selection, and backbone training, which Section 3.1 lists explicitly as accounted separately. If no public snapshot exists, a DP-generated one closes the ledger: we prove the joint release (snapshot, k queries) is pure (a·ε_s + Σε_q)-DP with a = 1 (add/remove-one) or a = 2 (replace-one), and measure its cost (support-ceiling retention 0–7% of the matched reference at per-entry ε_s ≤ 2 in the tested per-edge-RR configuration) — which is why we recommend already-public sources.

AuthorsOpenReview ↗

Response to Reviewer Lf9Y (Part 2/3)

Q2. What δ, adjacency unit, clipping/sampling, and accountant support the certified labels of the Gaussian and PrivCF-SGD baselines? How do they compare under the same edge-level relation as Theorem 1?

Answer. Mechanism cards, verified against the released code, with the guarantee stated under both adjacency conventions:

MechanismReleased objectSensitivityNoiseSamplingδAccountantadd/remove-one εreplace-one ε (Theorem 1's relation)
NaiveDP graph releaseFull noisy adjacency (i.i.d. Gaussian per entry, clamped to [0,1] — clamping is post-processing)Δ₂ = √2 (add/remove: two matrix entries) / Δ₂ = 2 (replace: four entries)σ = 0.952none1e-5Analytic Gaussian (Balle & Wang 2018)6.9710.63
PrivCF-SGDExplainer parameters2C — the whole gradient is clipped to C = 1 at every step, so one edge change (add/remove or replace) moves the clipped gradient by at most 2Cσ = 7·C (effective multiplier 3.5)none (q = 1, full batch)1e-5Opacus RDPAccountant, T = 10016.7316.73
PrivCFS (ours)Complete interventionΔu ≤ 1 for any single-edge change — the flip term, the size term, and the plausibility term of Eq. (8) each move by at most 1 whether the change is an addition, removal, or replacement (the sensitivity proof never uses which kind)Exponential mechanismnone0Theorem 1 (pure DP)εε

Three points complete the picture, stated as ledgers rather than a ranking:

  1. The paper's classical ε = 7.2 labels for the graph-level baselines are conservative under add/remove-one adjacency. The reviewer is right that the classical closed-form calibration invoked at Eq. (3) has an ε-range restriction; we replace that citation with the analytic Gaussian mechanism (Balle & Wang 2018). Under the same deployed noise (verified in code: full-matrix i.i.d. Gaussian, σ = 0.952, clamping as post-processing), the exact label is ε ≈ 6.97 ≤ 7.2 — so no experimental number moves.
  2. PrivCFS's pure-DP label is convention-independent by proof, not by phrasing. The utility's global sensitivity bound (Lemma 2) holds term by term for any single-edge change, so Theorem 1 applies identically under add/remove-one and replace-one — this is the sense in which the construction the reviewer validated stays intact regardless of the convention chosen for the baselines.
  3. PrivCF-SGD's previous 7.16 label assumed unit sensitivity of the whole clipped gradient; the implementation clips the total gradient to C. One edge change can then move a step's clipped gradient by up to 2C, so the corrected certified label at the same configuration (Opacus RDPAccountant, effective multiplier 3.5, T = 100, δ = 1e-5) is 16.73 — the raw accountant output is archived with the revision artifact. The paper's comparison tables retain the explicitly stated add/remove-one label ε = 7.2 for NaiveDP (conservative relative to 6.97); the mechanism cards give its replace-one label of 10.63 at the same noise. PrivCF-SGD is labeled 16.73 under either convention. The same-candidate-support control (Table 13) isolates placement at the reported noise settings, rather than matching ε across mechanisms: the graph-first certified baseline (restricted-NaiveDP) achieves zero validity on the original graph inside the identical support, while PrivCFS delivers 0.485 (Cora) / 0.349 (CiteSeer) with a pure-DP guarantee at ε = 8.

Appendix A wording. The reviewer is also right that sampled optimizer-output differences cannot establish a global sensitivity or an exact budget for the randomized pipeline. The revision renames those values (up to 753/256) as a sampled lower bound / calibration diagnostic under the stated sampling conditions — the empirical maxima and the attack AUC stay, the "true/effective budget" phrasing goes.

AuthorsOpenReview ↗

Response to Reviewer Lf9Y (Part 3/3)

W2(1). General-population validity is 13.9–21.9%, and non-empty invalid releases count as failures. Confirmed — and we report the full failure decomposition in our reply to 5t63-Q3 (empty releases are only 0.1–0.4%; the dominant failure mode is non-empty invalid, concentrated on random high-margin targets). Two contextual facts: the 13.9–21.9% range retains 83–95% of the non-private support-restricted ceiling (0.146–0.250), which is low because random high-margin nodes rarely admit small edits within the tested candidate space — our new arxiv general-population arm finds a non-private ceiling of 0.083 and P(flip) = 0.057 under private selection at ε=8; and on the borderline population, the most actionable one, absolute validity is 0.35–0.61 at ε=8 (0.24–0.45 at ε=2; ranges span ρ = 0.5–0.7 and both datasets). The revision presents both populations side by side (Tables 1/2) so the absolute and relative readings cannot be conflated.

W2(2). The 96.3% scale result uses one seed and ten lowest-margin nodes. Correct as stated — that configuration stays in the paper, labeled with its exact conditions. We now add the corroborating arm the reviewer asks for: 50 borderline targets per seed × 3 seeds (150 target–seed evaluations, targets drawn independently per seed) on the same 15K-node arxiv graph — support ceiling remains 1.000 (every low-margin target admits a valid flip inside the candidate support), P(flip)@8 = 0.920 at ρ=0.5 (SD 0.081 across the 150 target–seed evaluations; per-seed means 0.913 / 0.918 / 0.929; 0.937 ± 0.054 at ρ=1.0); release collision stays ≈ 5×10⁻⁴. The mild 0.963 → 0.920 movement is expected: the pool expanded from the 10 ultra-lowest margins (≈8×10⁻⁴) to the 50 lowest (≈5×10⁻³), a less extreme population. The revision reports both settings (Tables 11/12) so the original probe and the corroboration are directly comparable.

W2(3). The worst-case utility bound is vacuous at the operating parameters. At the operating parameters (ε=8 and the tested candidate-support sizes), the penalty term exceeds the utility range of [0,1], so the bound provides no nontrivial numerical guarantee in this regime (Section 3.5). The measured regret is 0.164 on the [0,1] utility scale at ε=8 (borderline Cora, ρ=0.7; Section 4.3, finding v), decaying smoothly from 0.368 at ε=0.5. The revision reports the worst-case bound and the measured operating regret separately.

W2(4). Repeated releases consume additional budget. They do, linearly — and the measured payoff makes the composition worthwhile. For total budget B split into k queries at ε_q = B/k, the at-least-one-valid probability, computed per target from the logged release probabilities as mean_v[1 − (1 − p_v(B/k))^k], grows monotonically and respects the support ceiling on every arm (full table in the overview comment): on the borderline population, B=2: 0.369 (k=1) → 0.473 (k=4, Cora) and 0.688 → 0.957 (k=8, arxiv external prior); at B=8, k=8 the Cora borderline arm reaches 0.498 — 99.6% of the non-private ceiling. Single-query validity itself degrades gently at small ε (Cora random 0.139@ε=8 → 0.098@ε=2 → 0.089@ε=1). Tables 1/2 report this per-budget behavior explicitly.

Reviewer_rCcjOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies how differential privacy should be integrated into counterfactual explanation pipelines for graph neural networks. It argues that two natural privacy placements are inadequate: privatizing the graph before explanation can alter the model prediction and produce counterfactuals that do not transfer to the original graph, while optimizing an explanation on the private graph and perturbing the resulting mask may lack a valid global sensitivity bound for the complete released object. To address these issues, the paper proposes PRIVCFS, a private counterfactual selector based on the exponential mechanism. The method constructs a fixed candidate universe using edge interventions derived from a public graph snapshot and feature interventions derived from public features and a frozen GNN. A bounded, validity-gated utility is used to sample an intervention with pure edge-level ε\varepsilonε-differential privacy. The authors provide a sensitivity analysis, a standard exponential-mechanism utility guarantee, implementation-level certification tests, and experiments on Cora, CiteSeer, and a 15,000-node subset of ogbn-arxiv.

Critical strengths
  • Given a fixed, data-independent output support and a bounded utility, the use of the exponential mechanism provides a valid pure-ε\varepsilon guarantee for the complete released intervention. The no-op semantics for nonexistent edges are a sensible way to preserve common output support across neighboring graphs.

  • The paper distinguishes formal certification from empirical privacy auditing. The exhaustive small-graph checks, sensitivity tests, probability-ratio checks, and likelihood-ratio attack are useful implementation diagnostics.

Critical weaknesses
  • The experimental construction of the public prior does not convincingly match the theoretical or deployment premise. The guarantee assumes an externally fixed public snapshot, but the experiments generate this snapshot by sampling a fraction of the current private graph’s true edges. This creates a favorable candidate universe with privileged knowledge of sensitive structure and does not demonstrate performance with a genuinely external public prior.

  • The utility and privacy conclusions depend heavily on a relatively permissive privacy budget and a narrow privacy scope. Most positive conclusions use pure ε=8\varepsilon=8 for a single query, while the target, features, candidate support, public snapshot, and frozen backbone are treated as public. Repeated explanation queries compose linearly, and model training or snapshot construction may require substantial additional privacy accounting.

Questions for authors
  • The current public snapshot is generated by sampling true edges from the current graph. Could the authors evaluate a historical snapshot, a public metadata network, or an independently trained link predictor that was not constructed from the current private edge set? Without such an experiment, it is difficult to determine whether the method works under the premise required for deployment.

  • What exactly is certified when the snapshot was constructed from the private graph? Is the guarantee intended to protect only the residual information in EE after the sampled snapshot is designated public? If so, the paper should state clearly that its empirical certification does not provide end-to-end protection for the original graph. What would the total privacy guarantee be if GpubG_{\mathrm{pub}}​ were itself produced using a DP mechanism?

  • Why should a valid-CF rate of approximately 0.14 to 0.22 be considered practically useful? On representative targets, most sampled non-empty interventions are invalid. How would a user know whether a released intervention actually flips the prediction? If the system releases a validity indicator or privately abstains, how is the additional disclosure accounted for?

  • The main conclusions focus on ε=8\varepsilon=8. What are the absolute valid-CF rates at a realistic total budget after accounting for repeated queries, target selection, snapshot construction, and possibly private model training? Would the claim that privacy noise is the least important source of utility loss remain true under an end-to-end budget of ε≤2\varepsilon\leq 2?

5 comments
AuthorsOpenReview ↗

Response to Reviewer rCcj (Part 1/4)

We thank the reviewer for the precise reading — especially the clean separation of the conditional guarantee from the deployment premise — and for suggesting the exact experiment that became our strongest new evidence. We answer Q1–Q4 in order.

Q1. Evaluate a historical snapshot, a public metadata network, or an independently trained link predictor not constructed from the current private edge set.

Answer. Done — the first two, under the paper's exact protocol (same target pools, evaluation graph, frozen backbone, ε grid, candidate caps; 3 seeds). The temporal construction is a historical-scenario reconstruction: from the current dataset we retain exactly the edges whose endpoints both have year ≤ T (and protect every newer edge). Because citation networks are append-only — a paper published by T and its reference list do not change afterwards — the year-filtered subgraph equals the citation state a deployer would have observed at T. It is not an independently released historical dump, and we name it accordingly. The kNN construction uses only public feature similarity and never reads the adjacency matrix. Both constructions are standalone and auditable.

Evidence (borderline population; full grids including the random population are in the overview comment).

Public priorDatasetSnapshot edgesEmpty edge-candidate universe rateSupport ceilingP(valid)@8Retention vs. matched privileged reference
Historical T=2015ogbn-arxiv9,02831.2%1.0000.930100% ceiling, 98.5% P@8
Historical T=2016ogbn-arxiv19,89827.1%1.0000.922100%, 97.7%
Historical T=2017ogbn-arxiv39,80220.8%1.0000.945100%, 100.2%
Feature-kNN k=4CiteSeer9,5250%0.2330.21864%, 62%
Feature-kNN k=8CiteSeer18,7750%0.2330.21364%, 61%
Feature-kNN k=4Cora8,4340%0.1670.15133%, 31%
Feature-kNN k=8Cora16,4490%0.2330.20547%, 42%

The external historical prior matches the privileged simulated prior (97.7–120% retention on both populations; on the random population it reaches 0.154–0.173 vs. the reference 0.145), with a measurable coverage cost (empty edge-candidate rate 16.7–31.2% at T=2015, falling as the cutoff advances; targets with no public incident edges are still served by feature interventions, which is why the ceiling stays at 1.000). The zero-edge-knowledge metadata network (kNN rows paired on the reference arm's 10 targets/seed) recovers 58–64% of the reference on CiteSeer and 25–47% on Cora, where feature-kNN candidates overlap true citation structure only ~5–7%: utility tracks prior informativeness, which is itself a placement-level finding of the paper.

Paper location. These arms instantiate the deployment premise already stated in Section 3.3; the revision adds the full table (Table 9) and per-arm construction details (Appendix G).

AuthorsOpenReview ↗

Response to Reviewer rCcj (Part 2/4)

Q2. What exactly is certified when the snapshot is built from the private graph? What would the total guarantee be if G_pub were itself produced by a DP mechanism?

Answer. Three snapshot provenances, with three guarantee statements — this is exactly the reviewer's phrasing, formalized:

  • (A) Externally fixed public snapshot (deployment premise). Theorem 1: each release is pure ε_q-DP for the complete intervention; k queries compose to Σε_q. Q1's experiments instantiate this case.
  • (B) Snapshot sampled from the current graph (the paper's simulated arms). Sampling is not a DP mechanism: the sampled edges are designated public, and the certified object is precisely the residual edge set E ∖ E_pub — protection against any two graphs that agree on the public entries and differ by replacing one non-public edge with another under Theorem 1's adjacency convention (the same utility bound also covers a single non-public edge addition or removal). Section 3.1/3.3 state the fixed-context and separate-accounting conditions; the revision states the residual-protection wording explicitly at Theorem 1 and in the experimental setup (Section 4.1), so the simulated arms are not read as end-to-end protection of the original graph.
  • (C) DP-generated snapshot (new). Let the snapshot be produced by per-edge randomized response at parameter ε_s (upper-triangle entries flipped independently, then symmetrized). Proposition (pure DP). Per-edge RR is ε_s-DP under add/remove-one edge adjacency: neighboring graphs then differ in exactly one upper-triangle entry, whose likelihood ratio is at most e^{ε_s}, all other entries contributing a factor of one. Under the replace-one adjacency of Theorem 1 (two entries), the same mechanism is 2ε_s-DP by the same calculation — equivalently, a replace-one snapshot guarantee at ε_s is obtained at per-entry parameter ε_s/2. Proposition (end-to-end composition). The joint release (snapshot, S_1, …, S_k), where each S_i is a PrivCFS query at ε_{q,i} conditionally on the released snapshot, is pure (a·ε_s + Σ_i ε_{q,i})-DP with a = 1 (add/remove-one) or a = 2 (replace-one): for every fixed snapshot g the candidate support is fixed and the utility is bounded with global sensitivity ≤ 1 (the proof of Theorem 1 uses only these two properties, not how g was produced), so the per-query ratio e^{ε_{q,i}} multiplies the RR ratio e^{a·ε_s}.

What does purchasing a snapshot cost? We measured case (C) at per-entry ε_s ∈ {1, 2} (replace-one snapshot labels 2ε_s ∈ {2, 4}) under the same protocol: the RR snapshot inflates the edge set 84–187× (Cora: 442K–989K edges vs. 5.3K true), the candidate existence rate falls to 0–0.6%, the support ceiling retains only 0–7% of the matched reference, and measured P(valid)@8 is at most 0.027 in these arms. So, within the tested configuration (per-edge RR, ε_s ≤ 2, our utility metric), buying the snapshot with budget is theoretically closed but practically expensive — and the deployment conclusion reinforces the paper's placement thesis: use information that is already public (historical snapshots, metadata networks; Q1 shows both are usable, with utility tracking their informativeness), and spend the budget on the explanation queries.

Paper location. Theorem 1 and Sections 3.3–3.5; the revision adds the taxonomy and the two propositions with proofs (Appendix C), and the RR arm (Table 9).

AuthorsOpenReview ↗

Response to Reviewer rCcj (Part 3/4)

Q3. Why is a valid-CF rate of 0.14–0.22 useful? How would a user know a released intervention flips the prediction? How is an additional validity signal accounted for?

Answer.

(i) On usefulness. The 0.14–0.22 range is measured on the random population, where the non-private, support-restricted ceiling is itself 0.146–0.250 (Table 1): the mechanism retains 83–95% of what is achievable at all in this setting, and the absolute ceiling reflects that random high-margin nodes rarely admit small edits within the tested candidate space — on the 15K-node arxiv graph our new stratified general-population arm finds a non-private ceiling of 0.083 and P(flip) = 0.057 under private selection at ε=8. The population on which recourse is most actionable is the borderline one, where absolute validity is 0.35–0.61 at ε=8 and remains 0.24–0.45 at ε=2 per single query (Tables 1/2; ranges span ρ = 0.5–0.7 and both datasets). And when a deployment allows k queries at total budget B, the at-least-one-valid probability approaches the ceiling (overview table: 94.6% of the Cora borderline ceiling at B=2, k=4; 95.7% under the external prior at k=8). We regard the population-dependence as one of the paper's findings; the abstract and Section 4.3 (Tables 1/2) state it explicitly.

(ii) On per-release validity. The released object is a candidate intervention; validity statistics (Tables 1/2 and the frequency table in our reply to 5t63-Q3) are computed server-side for evaluation. Checking whether a specific release flips the prediction requires the private graph, so no per-release validity label is included in the current interface, and we do not claim one. Section 3.5 (release semantics) states this interface boundary explicitly.

(iii) If a validity signal is desired, it must be — and can be — accounted for. For example, releasing (S, RR(flip(S); ε_v)) costs ε_q + ε_v by the same composition argument as Q2. We report the trade-off at two operating points (per-release P(valid) from the logs). At ε_q=8 (random/Cora/ρ=0.5, P(valid)=0.139): ε_v=1 gives indicator correctness 0.731 and an indicate-valid rate of 0.333, and user-facing precision P(truly valid | indicated valid) = 0.305; ε_v=2 gives correctness 0.881, an indicate-valid rate of 0.225, and precision 0.544 — total budgets 9 and 10 respectively, not an ε≤2 configuration. At the ε_q=1 operating point (P(valid)=0.089): ε_v=1 gives correctness 0.731, an indicate-valid rate of 0.310, and precision 0.210, at total budget 2. We report this trade-off rather than overclaim it: a noisy indicator is an auxiliary signal, and any stronger filtering/verification mechanism would need its own accounting, exactly as the reviewer notes.

Reviewer_5t63OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies where to introduce DP when generating counterfactual explanations for GNNs. It proposes PrivCFS, which selects interventions from a fixed public candidate universe using the exponential mechanism, providing pure edge-level DP conditional on a public graph prior and fixed backbone.

Critical strengths
  1. The paper addresses an interesting problem: how to provide counterfactual explanations for GNNs while protecting private graph structure.
  2. The proposed method is simple and has a clear pure ε\varepsilon-DP guarantee without requiring sensitivity analysis of the explanation optimizer.
  3. The analysis of different privacy placements is interesting, especially how privatizing the graph can lead to incorrect explanations.
  4. The experiments are quite extensive, including privacy audits, comparisons with baselines, and an analysis of where utility is lost.
Critical weaknesses
  1. The privacy guarantee assumes a fixed public graph independent of the private one. This is central to the paper but it is unclear how realistic this assumption is in practice.
  2. The actual success rates are quite low. The paper emphasizes retaining 83-97% of the non-private optimum (Section 5), but this is only the optimum within the restricted candidate space. For example, on randomly selected nodes, the success rate is only around 14% at ε=8\varepsilon=8 and ρ=0.5\rho=0.5 (Table 1).
  3. The method can still output interventions that do not flip the prediction or contain edges that do not actually exist in the graph, compared to prior methods.
  4. Regarding writing, the abstract is long and difficult to read and understand compared to other parts of the paper.
Questions for authors
  1. Is it possible to discuss or show how a public graph can be constructed independent of the private one? and how would that affect the utility?
  2. Given the relatively low success rates on randomly selected nodes, how useful would the method be in practice?
  3. How often does the method output invalid explanations or interventions containing nonexistent or unnecessary edges?
4 comments
AuthorsOpenReview ↗

Response to Reviewer 5t63 (Part 1/3)

We thank the reviewer for the positive assessment of the problem, the mechanism, and the experimental breadth, and for four well-posed questions. We answer each in turn.

Q1. How can a public graph be constructed independently of the private one, and how would that affect utility?

Answer. We now provide two concrete, externally fixed constructions — a historical-scenario reconstruction and a public metadata network — evaluated under exactly the same protocol as the paper's simulated-prior arms (same target pools, evaluation graph, frozen backbone, budget grid, candidate caps; 3 seeds throughout). Both constructions are standalone and auditable:

  • Historical-scenario reconstruction (ogbn-arxiv). From the current dataset we retain exactly the edges whose endpoints both have year ≤ T, and protect every newer edge (at least one endpoint year > T). Because citation networks are append-only — a paper published by T and its reference list do not change afterwards — the year-filtered subgraph equals the citation state a deployer would have observed at T. It is not an independently released historical dump, and we name it accordingly. The snapshot is fixed across neighboring graphs by construction, and no protected edge enters the public context.
  • Public metadata network (Planetoid). A feature-kNN graph built only from public feature cosine similarity; the construction never reads the adjacency matrix, so it carries zero edge knowledge.

Evidence.

Historical-scenario reconstruction (ogbn-arxiv, target pool = nodes with year ≤ 2015):

PriorSnapshot edgesEmpty edge-candidate universe ratePopulationSupport ceilingP(valid)@8Retention vs. privileged reference
Privileged simulated (ρ=0.5)80,4728.3% / 20.8%random / borderline0.229 / 1.0000.145 / 0.944—
Temporal T=20159,02816.7% / 31.2%random / borderline0.250 / 1.0000.157 / 0.930109% / 100% (ceiling), 109% / 98.5% (P@8)
Temporal T=201619,89810.4% / 27.1%random / borderline0.250 / 1.0000.154 / 0.922109% / 100%, 106% / 97.7%
Temporal T=201739,8028.3% / 20.8%random / borderline0.250 / 1.0000.173 / 0.945109% / 100%, 120% / 100.2%

The historical-scenario reconstruction — with as few as 1/9 of the reference's edges — reaches 97.7–120% of the privileged prior on both populations (98–120% at T = 2015/2017). Newer snapshots improve coverage (the empty edge-candidate rate falls as the cutoff advances).

Public metadata network (feature-kNN, Planetoid, borderline population, ρ=0.5 reference; paired on the reference arm's 10 targets/seed × 3 seeds):

PriorDatasetSupport ceilingP(valid)@8RetentionCandidate existence rate
Privileged simulatedCora0.5000.483—100% (by construction)
kNN k=4 / k=8 / k=12Cora0.167 / 0.233 / 0.1330.151 / 0.205 / 0.12033% / 47% / 27% (ceiling); 31% / 42% / 25% (P@8)4.7–6.7%
Privileged simulatedCiteSeer0.3670.350—100%
kNN k=4 / k=8 / k=12CiteSeer0.233 / 0.233 / 0.2330.218 / 0.213 / 0.20464% / 64% / 64% (ceiling); 62% / 61% / 58% (P@8)4.7–11.7%

Reading. The zero-edge-knowledge metadata network recovers a substantial but partial share of the privileged prior's utility — 58–64% on CiteSeer and 25–47% on Cora, where feature-kNN candidates overlap the true citation structure only ~5–7% (see the existence-rate column) — while the historical reconstruction, which carries real (past) edge knowledge, matches the reference. Together with the arxiv results this gives a coherent picture: the mechanism works unchanged under external priors, and utility tracks prior informativeness — which is precisely the paper's placement-level claim.

Paper location. Section 3.3 lists historical snapshots and public metadata networks as intended sources; the revision adds this matched comparison as Table 9 with construction details in Appendix G, and states the deployment reading in the Introduction (contribution 3) and Conclusion.

AuthorsOpenReview ↗

Response to Reviewer 5t63 (Part 2/3)

Q2. Given the low success rates on randomly selected nodes, how useful is the method in practice?

Answer. Three clarifications, all supported by the paper's own tables and new per-target computations.

First, 13.9% is 83% of the non-private optimum within the same candidate support (Table 1 reports 84% after rounding). On Cora, random population, ρ=0.5, ε=8 (Table 1), the measured 13.9% sits against a non-private, support-restricted ceiling of 16.7%; the gap attributable to privacy noise is 2.8 percentage points. On the borderline (recourse) population the same comparison is 48.4% vs. 50.0% (Table 2). Across Table 1/2, retention of the non-private ceiling is 83–95% (random) and 94–97% (borderline) at ε=8.

Second, the low absolute ceiling on the random population is a property of the recourse problem, not of privacy. Within the tested candidate space (k ≤ 2 edge edits, k ≤ 3 feature edits), random high-margin nodes rarely admit valid interventions at all: on the 15K-node arxiv graph, our new stratified general-population arm (96 target–seed evaluations) finds a non-private support ceiling of 0.083 and P(flip) = 0.057 under private selection at ε=8 — the same regime as Planetoid's random population (0.14). The population on which recourse is most actionable is the borderline one, where the method delivers 0.35–0.61 absolute validity at ε=8 and 0.24–0.45 at ε=2 (single query, fixed context; ranges span ρ = 0.5–0.7 and both datasets).

Third, a fixed budget can be split into multiple queries, and the measured payoff approaches the ceiling. For total budget B split into k queries at ε_q = B/k, the at-least-one-valid probability — computed per target as mean_v[1 − (1 − p_v(B/k))^k] — grows monotonically and respects the ceiling on every arm (full table in the overview comment): Cora random, B=2: 0.098 (k=1) → 0.141 (k=4), i.e., 84.4% of the 0.167 ceiling; Cora borderline, B=2: 0.369 → 0.473, i.e., 94.6% of the 0.500 ceiling; arxiv borderline under the external prior, B=2: 0.688 → 0.957 at k=8.

Evidence. Table 1/2 (paper); new scale arms and the multi-query table (overview comment); per-target analysis shows validity is strongly bimodal (83–85% of random targets have P(valid)=0, the rest near 1), i.e., the mechanism succeeds exactly where recourse exists within the candidate space.

AuthorsOpenReview ↗

Response to Reviewer 5t63 (Part 3/3)

Q3. How often does the method output invalid explanations, or interventions containing nonexistent or unnecessary edges?

Answer. We report the categories separately (they are different quantities), measured over all releases (3 seeds × 16 targets (random) / 10 targets (borderline) × 100 draws per configuration, ε=8):

PopulationDatasetρP(valid)P(empty)P(non-empty, no flip)P(≥1 nonexistent edge)P(redundant | valid)
randomCora0.50.1390.0010.8600 (by construction)0.17
randomCiteSeer0.50.1390.0040.85700.15
randomCora0.70.2130.0020.78500.25
randomCiteSeer0.70.2190.0020.77900.23
borderlineCora0.50.4830.0030.51400.50
borderlineCiteSeer0.50.3500.0020.64800.33
borderlineCora1.00.8600.0000.13900.90
  • Empty releases are rare (0.1–0.4%), including under the validity-gated utility: the ∅ candidate denotes "no intervention drawn this round" (Section 3.5–3.6) and is not designed as a reliability signal.
  • Nonexistent edges: zero in the paper's simulated-prior arms and in the historical-reconstruction arm — both snapshots are subsets of true edges, so this holds by construction (verified in the logs). Under the zero-edge-knowledge metadata network (candidate existence 4.7–11.7%), a release contains at least one no-op edge operation in 77–95% of draws at ε=8 (both populations): the candidate grid is dominated by combinations that include such pairs, and a no-op op costs only the size penalty, so the aggregate sampling mass lands there. What the user receives in such a release is still its effective content: the no-op operations never change the graph, so the operations that drive the outcome are the existing-edge deletions and feature masks — validity is measured on the true graph, and every release remains ε-DP by the same support-independence argument (Lemma 1, Section 3.3). Most releases therefore carry at least one inert operation, increasing the released set's size without changing its effect.
  • Unnecessary (redundant) operations within valid releases (last column), measured by per-operation ablation over the logged releases — a valid release is single-operation-redundant if removing one operation leaves a flipping intervention: 15–31% on the general population and 33–90% on the borderline population under the simulated priors (rising with ρ and ε), 2–38% under the metadata network (lower on the general population, where few releases are valid at all), and 24% (general) / 97% (borderline) under the external historical prior on arxiv, where the 128-dim feature interventions dominate. Redundancy is a minimality gap: a redundant valid release still flips and remains ε-DP, but is larger than necessary. The size penalty of Eq. (8) mainly orders candidates within the flipping set (Section 4.3, finding vii). Higher size/plausibility weights and smaller caps could reduce inert or redundant operations; their effects on these rates have not been evaluated.

W4 (writing). Abstract too long. We agree. The revised abstract (in the uploaded PDF) is compressed to the problem, the placement diagnosis, the conditional pure-DP selection mechanism, and the headline absolute numbers — the external-prior retention (97.7–120%), the borderline validity rates, and the multi-query result — with attack-audit details and secondary figures moved to the body.

Thank you for the rebuttal and additional experiments. I appreciate the effort to address my concerns.

The responses have clarified the scope of the privacy guarantee and the sources of utility loss. Although the rebuttal has addressed several of my concerns, I remain unconvinced that the proposed mechanism provides useful counterfactual explanations in practice.

To be more specific, although multiple queries increase the probability of obtaining at least one valid intervention, the proposed release mechanism does not allow the analyst to identify which intervention is valid without additional access to the private graph or a separately accounted private validity mechanism. Also, while I appreciate the additional analysis of invalid and redundant interventions, the reported rates reinforce my concerns about the practical usefulness of the released outputs as counterfactual explanations.

Overall, I acknowledge the improvements, but I remain concerned about the practical utility and usefulness of the proposed method. Therefore, I have decided to maintain my original score.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Global Official Comment [1/2]

We thank all three reviewers for their careful and constructive reviews. We first summarize the new evidence common to our point-by-point replies, then respond to each question in the individual threads. A revised PDF is uploaded alongside these responses; the locations referenced below point to it.

New evidence in this round.

  1. Externally fixed public priors, evaluated under the protocol requested by Reviewer rCcj (Q1). We evaluate two public-snapshot constructions that are strictly independent of the current private edge set, under the same target pools, evaluation graph, frozen backbone, budget grid, and candidate caps as the paper's simulated-prior arms:
  • a historical-scenario reconstruction on ogbn-arxiv (only edges whose endpoints both have year ≤ cutoff are public; newer edges are private), and
  • a public metadata network on Planetoid (a feature-kNN graph built only from public features, never touching the adjacency matrix). The reconstruction matches or exceeds the privileged simulated prior (97.7–120% retention of both the support ceiling and P(valid)@ε=8 across cutoffs T = 2015–2017; 98–120% at T = 2015/2017), while using as few as 1/9 of its edges. The zero-edge-knowledge metadata network recovers part of the reference utility (58–64% on CiteSeer, 25–47% on Cora): utility tracks how informative the public prior is.
  1. Scale corroboration. The 15K-node arxiv result now rests on 50 borderline targets per seed × 3 seeds — 150 target–seed evaluations, targets drawn independently per seed (previously 10 targets × 1 seed): support ceiling remains 1.000, P(flip)@ε=8 = 0.920 (SD 0.081 across the 150 target–seed evaluations; per-seed means 0.913 / 0.918 / 0.929). A stratified general-population arm (32 targets/seed × 3 seeds) gives a non-private support ceiling of 0.083 and P(flip)@8 = 0.057 under private selection, clarifying the population boundary of the result.

  2. Complete baseline accounting, per adjacency convention. We document released object, adjacency unit, sensitivity, noise, sampling, δ, and accountant for every certified baseline, verified against code. Two findings result. (a) Under add/remove-one edge adjacency the paper's classical ε = 7.2 labels are conservative (analytic Gaussian, Balle & Wang 2018: ε ≈ 6.97 at the same noise). (b) PrivCFS's pure-DP label is convention-independent by proof: the utility's global sensitivity bound Δu ≤ 1 holds term by term for any single-edge change — addition, removal, or replacement — so Theorem 1 applies identically under both conventions. At the certified labels of the compared mechanisms (PrivCFS ε = 8, pure; NaiveDP 10.63 under replace-one; PrivCF-SGD 16.73 with its global-gradient clipping accounted at sensitivity 2C), the graph-first certified baseline (restricted-NaiveDP, Table 13) achieves zero validity on the original graph inside the same candidate support, while PrivCFS delivers 0.485 (Cora) / 0.349 (CiteSeer).

  3. A snapshot-source taxonomy with an end-to-end theorem. We formalize three snapshot provenances: (A) externally fixed public snapshot (the deployment premise of Theorem 1); (B) snapshot sampled from the current graph (what our simulated arms measure: conditional protection of the residual edges); (C) DP-generated snapshot, for which we prove the joint release (snapshot, k queries) is pure (a·ε_s + Σε_q)-DP (a = 1 add/remove-one, a = 2 replace-one), and measure its utility cost.

  4. Multi-query operation at a fixed total budget, measured per target. For total budget B split into k queries at ε_q = B/k (basic composition), the probability that at least one release is valid — computed per target from the logged release probabilities as mean_v[1 − (1 − p_v(B/k))^k] and averaged — grows monotonically with k and approaches the non-private support ceiling on every arm:

PopulationPriorBk=1k=2k=4k=8Support ceiling
Cora borderlinesimulated ρ=0.520.3690.4300.473—0.500
Cora randomsimulated ρ=0.520.0980.1240.141—0.167
CiteSeer borderlinesimulated ρ=0.520.2360.2830.330—0.367
arxiv borderlineexternal, T=201520.6880.7900.8930.9571.000
arxiv randomexternal, T=201520.0980.1180.1520.1830.250
Cora borderlinesimulated ρ=0.580.4830.4830.4940.4980.500

At total budget 2, four queries recover 94.6% of the non-private ceiling on the Cora recourse population; under the external historical prior, eight queries recover 95.7%. Repeated querying is thus a budgeted protocol feature with a measured, ceiling-respecting payoff.

AuthorsOpenReview ↗

Global Official Comment [2/2]

Matched external-prior comparison (ε = 8; support ceiling / P(valid) / retention vs. matched privileged reference).

Public priorDatasetPopulationSnapshot edgesEmpty edge-candidate universe rateSupport ceilingP(valid)@8Ceiling retentionP@8 retention
Privileged reference (ρ=0.5)ogbn-arxivrandom80,4728.3%0.2290.145——
Historical reconstruction T=2015ogbn-arxivrandom9,02816.7%0.2500.157109%109%
Historical reconstruction T=2017ogbn-arxivrandom39,8028.3%0.2500.173109%120%
Privileged reference (ρ=0.5)ogbn-arxivborderline80,47220.8%1.0000.944——
Historical reconstruction T=2015ogbn-arxivborderline9,02831.2%1.0000.930100%98.5%
Historical reconstruction T=2017ogbn-arxivborderline39,80220.8%1.0000.945100%100.2%
Privileged reference (ρ=0.5)CiteSeerborderline——0.3670.350——
Feature-kNN (k=4)CiteSeerborderline9,5250%0.2330.21864%62%
Privileged reference (ρ=0.5)Coraborderline——0.5000.483——
Feature-kNN (k=4)Coraborderline8,4340%0.1670.15133%31%

All arms use 3 seeds; Planetoid kNN arms are evaluated on the reference arm's own 10 targets/seed (paired comparison on identical targets); arxiv arms use 16 targets/seed from the year≤2015 target pool. "Empty edge-candidate universe" counts targets with no public incident edge; those targets are still served by feature interventions (in the T=2015 borderline arm, all 15 edge-empty targets — 31.2% — attain their ceiling through feature-only interventions, which is why the support ceiling remains 1.000). The full grids (T = 2015/2016/2017 on both populations; kNN k = 4/8/12 on the borderline population against the ρ=0.5 reference; a DP-generated snapshot arm) appear in Table 9 / Appendix G of the revision.

Point-by-point replies follow in each review thread.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.