A new method for explaining graph-based machine-learning decisions reported a formal privacy guarantee for a graph's edge structure while preserving most of the useful counterfactual recourse available without privacy protection. At a privacy budget of 8, its sampled releases retained 83% to 95% of the support-restricted non-private ceiling in the general evaluation and 94% to 97% in a separate borderline diagnostic.
The work is a preprint, so its findings have not yet been established through peer review. Its central question was whether private graph counterfactual explanations could protect sensitive connections while preserving useful recourse and limiting edge inference. The method, called PrivCFS, fixes a public context for each target so neighboring graphs share the same candidate universe and release support.
The privacy guarantee covers the whole release
The key design choice is where privacy is applied. PrivCFS fixes the candidate universe and release support in advance, making them independent of the private edge set. It uses a validity-gated utility for selecting interventions, with a reported global sensitivity bound of 1 for neighboring graphs.
The paper's theorem states that the complete released intervention set satisfies pure edge-level differential privacy under replace-one edge adjacency, with the additive privacy parameter delta equal to zero. In ordinary terms, the guarantee applies to the full object released by the method, not just to each selected edge or feature separately. The claim is conditional on the study's public context and adjacency assumptions.
Where the alternatives lost ground
The comparison tested what happened when graph-level privacy was applied upstream. That arm reported 60% to 92% polluted targets and 23% to 37% spurious flips. All of the spurious flips occurred on polluted nodes.
A separate re-audit raised a different concern about heuristic clean-graph output perturbation. Its implied full-release privacy budget was 573 to 753 on Cora and 256 on CiteSeer, while the worst single-entry edge-inference attack reached an area under the curve of 1.0. The audit therefore did not certify the complete release at its advertised accounting.
The comparison was also run with the same candidate support. In that control, the graph-first arm had a reported valid-counterfactual rate of 0.000 on both datasets, alongside pollution rates of 0.73 and 0.70. PrivCFS retained rates of 0.485 and 0.349 at a privacy budget of 8, pointing to privacy placement as a major part of the difference.
Public disclosure set the ceiling
The study's strongest warning concerns the information made public before private selection begins. Among borderline targets, the non-private ceiling rose as public-prior strength increased: it ranged from 0.37 to 0.50 at a strength of 0.5, from 0.57 to 0.63 at 0.7, and from 0.77 to 0.90 at a data-dependent upper reference. The upper-reference values were not certified privacy arms, so they are best read as a comparison point rather than a deployable guarantee.
The authors interpret the pattern as evidence that public support and disclosure choices account for much of the quality trade-off, while the added privacy noise was comparatively inexpensive under the tested conditions. The results do not establish that the same balance will hold outside the tested public contexts and benchmark settings.
An audit found little signal in the certified release
In the real-adjacent-pair audit, an optimal likelihood-ratio attack achieved an area under the curve of 0.50 on average and 0.59 in the worst pair for the certified release. The heuristic release reached 1.0 under the same attack and protocol. The audit is supporting evidence; the theorem supplies the method's worst-case privacy guarantee.
What was tested, and what remains open
The evaluation used Cora, with 2,708 nodes, CiteSeer, with 3,327, and a 15,000-node degree-core subset of ogbn-arxiv containing 160,944 edges and 40 classes. A frozen two-layer graph convolutional network was used for the benchmark experiments. The main evaluation drew 16 targets, the borderline diagnostic used the 10 lowest-margin targets, results used three seeds, and each cell included 100 Monte Carlo release draws.
The method also transferred to the larger ogbn-arxiv subset in a small test. For 10 targets on the certified public-prior strength of 0.5, the support-restricted ceiling was 1.000 and the sampled valid rate was 0.963, with a standard deviation of 0.026, at a privacy budget of 8. The scale-transfer result used one seed and 10 near-tied targets, leaving broader performance an open question.
The stated theorem is for edge-level privacy under the paper's public context and fixed frozen backbone. It does not by itself cover feature-entry privacy or a model trained on private edges, and a public snapshot would require separate accounting. The experiments used public benchmarks and no human subjects or newly collected private data. The paper says an anonymized code bundle is available and that reported means are generally based on three seeds unless stated otherwise.
Paper data and sources
Original title: Where Privacy Belongs: Placement Diagnosis and Certified Selection for Private Counterfactual Explanations on Graphs
Authors: Yuxiang Yao, Zijun Zhao
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-09-29
DOI: Not available
Original paper · Full text