Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors audit existing private counterfactual explanation methods for graph neural networks, demonstrating that current perturbation heuristics suffer from catastrophic leakage (implied $\varepsilon > 700$ and AUC 1.0 edge recovery) while input privatization produces spurious non-transferable recourses. To resolve this, they design PrivCFS, an algorithm that achieves the first composable, pure $\varepsilon$-differential privacy guarantees for graph explanations by defining counterfactual selection over a fixed, data-independent candidate universe with identical output supports across neighboring graphs. Across benchmarks including a 15k-node graph, PrivCFS collapses adversarial edge inference from AUC 1.0 down to near-random guessing (AUC 0.50 average) while preserving 94–97% of non-private explanation utility at $\varepsilon=8$.
Existing "private" graph explanations quietly leak sensitive edges with an empirical AUC of 1.0 and implied privacy budgets exceeding $\varepsilon = 700$, exposing a structural flaw that can only be solved by enforcing data-independent intervention universes.
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.