- 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
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:
| Mechanism | Released object | Sensitivity | Noise | Sampling | δ | Accountant | add/remove-one ε | replace-one ε (Theorem 1's relation) |
|---|---|---|---|---|---|---|---|---|
| NaiveDP graph release | Full 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.952 | none | 1e-5 | Analytic Gaussian (Balle & Wang 2018) | 6.97 | 10.63 |
| PrivCF-SGD | Explainer parameters | 2C — 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-5 | Opacus RDPAccountant, T = 100 | 16.73 | 16.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 mechanism | none | 0 | Theorem 1 (pure DP) | ε | ε |
Three points complete the picture, stated as ledgers rather than a ranking:
- 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.
- 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.
- 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.
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.
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:
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.