PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Auditing of Differentially Private Graph Release Mechanisms: Methodology, Toolkit, and Case Study

Nicholas D'Silva, Surya Nepal, Salil S. Kanhere

arXiv:2610.31294v1cs.CR

TL;DR

Empirical DP auditing has largely focused on tabular data and machine learning, while graph releases require explicit attention to structural context and witness statistics. The paper adapts certified testing to graph releases and audits PrivDPR, finding certified violations across canary pairs, while showing that outcomes depend on witness choice.

  • Problem

    Empirical DP audits have largely targeted tabular data and machine learning, while graph structure creates distinct challenges for canary construction and witness selection.

    Source: §1 · p. 1, §3.1 · p. 3

  • Method

    The paper separates graph-specific canary construction from witness-statistic selection, combines them with established certified testing, and implements the approach in an open-source toolkit.

    Source: §1 · p. 1

  • Results

    Across six audited canary pairs, edge-count audits yielded certified ε lower bounds exceeding the claimed value in each presented case, at individual 99% confidence.

    Source: §5.2 · p. 7

  • Takeaways & Limitations

    The audited implementation does not satisfy its claimed bounded Node-DP guarantee, and violation detection depends strongly on witness selection.

    Source: §5.2 · p. 7

    This is a falsification procedure: an unsuccessful audit does not establish that a mechanism satisfies its claimed guarantee.

    Source: §6 · p. 7

Abstract

from arXiv · show

Differential Privacy (DP) has become a prominent approach for protecting graph data releases, yet empirical auditing methodologies have largely been developed for tabular datasets and machine learning pipelines rather than graph-structured outputs. We present a methodology for empirically auditing DP graph release mechanisms, identifying two graph-specific audit design problems: canary construction and witness statistic selection. We combine these components with an established statistically certified testing procedure and implement the resulting methodology as an open-source Python toolkit. To demonstrate the approach, we audit a published state-of-the-art Node-DP graph release mechanism. Across a series of synthetic and real-world canary pairs, we obtain certified lower bounds on the privacy parameter {\varepsilon} that exceed the claimed value, yielding counterexamples sufficient to falsify the claimed guarantee for the audited implementation. The violations persist under progressively stronger restrictions on the input domain, including non-empty and connected graphs. We also show that witness selection can materially affect whether a violation is detected, highlighting the importance of evaluating a diverse battery of statistics when auditing DP graph release mechanisms.

1 Introduction

Empirical DP auditing has largely focused on tabular data and machine learning, while graph releases require choices about canary context and witness statistics. This work adapts certified auditing to graph releases and applies it to PrivDPR, finding violations that persist on non-empty and connected inputs.

1 Introduction

  • Graph audits must construct canaries with meaningful structural context and select witness statistics that expose distributional differences.Unlike tabular audits, graph releases have no single natural attack signal, and witnesses can reveal different structural properties.Source: §1 · p. 1
  • The proposed methodology combines graph-specific canary construction and witness selection with established statistical certification techniques.The open-source Python toolkit supports user-defined releases, neighboring relations, canary procedures, and witness statistics.Source: §1 · pp. 1–2
  • The case study audits the authors’ released implementation of PrivDPR, a state-of-the-art Node-DP graph release mechanism.The evaluation proceeds from a trivial edge case through increasingly restrictive synthetic canaries to real-world graph datasets.Source: §1 · p. 1
  • Across the audited canaries, certified lower bounds exceed PrivDPR’s claimed privacy budget, including for non-empty and connected input graphs.The audit covers synthetic and real-world canary pairs and falsifies the guarantee for the audited implementation.Source: §1 · pp. 1–2
  • Violation detection depends on witness selection, motivating a diverse battery of statistics when auditing DP graph releases.The paper reports that some witnesses do not expose violations detected by other statistics on the same pair.Source: §1 · p. 2

2 Background and Related Work

This section reviews differential privacy’s neighboring-dataset framework and prior empirical auditing work. It positions the paper as adapting established statistical auditing to graph releases, where structural dependencies require explicit design choices.

2.1 Background on Differential Privacy

  • An (ε,δ)-DP guarantee bounds output behavior across neighboring datasets; ε is the privacy budget, δ the additive relaxation, and sensitivity determines noise magnitude.Smaller ε gives stronger privacy, generally at a utility cost; δ=0 is pure DP, while δ>0 is approximate DP.Source: §2.1 · p. 2
  • Neighboring datasets may differ by adding or removing a record, or by substituting one; graph relations typically protect edges or vertices.Edge-DP is typically unbounded, while Node-DP mechanisms use bounded and unbounded variants.Source: §2.1 · p. 2

2.2 Related Work

  • Prior empirical DP audits use statistical counterexample detection and have been applied to DP-SGD and synthetic data generators.The paper adopts established statistical testing directly, focusing its contribution on graph-specific considerations around that procedure.Source: §2.2 · p. 2
  • Graph release auditing complements benchmarks and deployment evaluations by addressing whether a mechanism meets its claimed privacy guarantee.The paper notes that graph attacks can miss certified violations because attacks test exploitability, whereas audits test distributional compliance.Source: §2.2 · p. 2
  • The paper identifies its novelty as adapting existing principled empirical auditing to graph releases, not inventing the underlying statistical construction.The adaptation addresses structural and relational considerations that prior methods do not handle directly.Source: §2.2 · p. 2

3 Audit Methodology

The methodology adapts statistical DP auditing to graph releases by treating canary construction and witness selection as distinct design choices. It searches for statistically certified counterexamples to a claimed guarantee, while an unsuccessful audit remains inconclusive.

3 Audit Methodology

  • The black-box procedure tests an implemented graph release against its claimed DP guarantee, and an unsuccessful audit does not establish that the guarantee holds generally.The auditor can query chosen inputs and observe outputs without inspecting internal computation.Source: §3 · pp. 2–3, §3.1 · p. 3

3.1 Problem Setting and Audit Objective

  • The auditor fixes the neighbouring relation and searches for an output event whose probabilities under one neighbouring pair conflict with the claimed DP bound.The tested claim concerns observable behavior of the implementation, including implementation-level effects.Source: §3.1 · p. 3

3.2 Graph Canaries

  • A canary is the graph element or structure that differs between neighbouring inputs; its surrounding context can shape how the mechanism treats it and how distinguishable outputs are.Canary context may be described using degree, local density, centrality, or participation in selected substructures, guiding construction rather than entering the statistical test.Source: §3.2 · p. 3

3.3 Graph Witness Statistics

  • Witness statistics reduce released graphs to scalar scores, but no single statistic captures every structural discrepancy, so a battery should span different graph properties.Canary construction locates the input difference; witnesses distinguish the resulting outputs, and failure across a finite battery does not rule out other tests.Source: §3.3 · p. 3

3.4 Selection of a Distinguishing Test

  • For each canary pair and statistic, selection data choose the threshold, score-tail, and privacy direction; independent evaluation samples then test the selected event.The selection set is exploratory and cannot also support the final confidence bound; tests are run separately rather than pooling evidence across statistics or pairs.Source: §3.4 · p. 4, §3.5 · p. 4

3.5 Evaluation

  • One-sided Clopper–Pearson bounds certify the event probabilities; a positive privacy lower bound requires α_lower > δ, and the claimed guarantee is rejected when ε_LB > ε_0.A successful test gives evidence of violation for the audited pair and event; a lower bound that does not exceed ε_0 is inconclusive, not a privacy certificate.Source: §3.5 · p. 4

4 Practical Considerations

The audit’s threshold search is quadratic in selection samples, but mechanism execution and graph-statistic evaluation typically dominate runtime. The authors position empirical auditing as a validation layer alongside utility evaluation and provide a modular toolkit for conducting and reproducing audits.

4.1 Time Complexity

  • For one canary pair, runtime is O((Nsel + Neval)TA(Gi) + Σs∈S((Nsel + Neval)Ts(Gi) + Nsel^2)); threshold search is typically a comparatively small share.Mechanism execution and evaluating graph-based witnesses on full graph outputs usually dominate the quadratic threshold-search term.Source: §4.1 · p. 5

4.2 Integration into Broader Evaluation Frameworks

  • Empirical auditing should accompany utility evaluation because certified incompatibility with a claimed privacy guarantee means utility at its nominal privacy parameter does not represent that operating point.The authors describe auditing as a validation stage between mechanism configuration and interpreting its privacy–utility performance.Source: §4.2 · p. 5
  • An unsuccessful empirical audit cannot establish general DP compliance because it tests only finitely many neighboring pairs, witnesses, and decision rules.The authors frame auditing as a falsification layer that complements formal privacy analysis and can expose implementation or configuration discrepancies.Source: §4.2 · p. 5

4.3 Implementation Details

  • The open-source toolkit separates mechanism execution, witness computation, test selection, certification, and result export, and includes workflow examples and reusable graph witnesses.Users can supply mechanism outputs and witness functions; the optional NetworkX collection includes degree, distance, centrality, spectral, and subgraph statistics.Source: §4.3 · p. 5

5 Case Study: PrivDPR

The case study audits PrivDPR’s released bounded Node-DP implementation using synthetic and real-world neighboring graph pairs. Edge-count tests yield certified violations across the audited canaries, while other witnesses sometimes do not detect them.

5 Case Study: PrivDPR

  • PrivDPR is a Node-DP graph-release mechanism that learns per-node PageRank approximations with DP-noised gradients and samples edges from scores derived from learned embeddings.The case study uses the authors’ released implementation and bounded node adjacency, which permits arbitrary rewiring of one vertex’s incident edges while vertex identities and count remain fixed.Source: §5 · p. 5

5.1 Datasets and Canaries

  • The initial trivial counterexample distinguishes a k-star from its neighbor with an isolated center, but relies on a degenerate, disconnected graph.PrivDPR consistently returns an edgeless output on the isolated-center input and non-empty outputs on the k-star input.Source: §5.1 · p. 6

5.1.1 Synthetic Constructions.

  • Four synthetic canary constructions progressively impose non-empty, connected, and small-relative-perturbation restrictions to test whether violations persist under conditions more favorable to the mechanism.Constructions B and D embed the changed structure in an Erdős–Rényi graph so the difference is less than 10% of the graph’s edge count.Source: §5.1 · p. 6, §5.1.1 · pp. 6–7

5.1.2 Real-World Datasets.

  • The real-world canaries isolate the maximum-degree vertex in the RT-LOLGOP retweet network and the Anybeat interaction network.These datasets test whether analogous violations appear beyond controlled synthetic examples.Source: §5.1.2 · p. 7

5.2 Results and Discussion

  • On all six audited canary pairs, edge count yields certified lower bounds exceeding PrivDPR’s claimed privacy budget at the individual 99% confidence level.Violations persist for non-empty and connected graphs, for perturbations affecting less than 10% of edge count, and on real-world canaries.Source: §5.2 · p. 7
  • Maximum PageRank on Construction B and maximum degree on Anybeat do not exceed the claimed privacy budget, so either witness alone would miss violations detected by edge count.The reported confidence bounds are pointwise for each fixed canary–witness test; the authors do not claim simultaneous coverage across the tested collection.Source: §5 · p. 6, §5.2 · p. 7

6 Limitations and Future Work

The audit is a falsification procedure: an unsuccessful result does not verify a mechanism’s privacy guarantee. The case study leaves audit power across canary structures and the prevalence of similar issues across graph privacy mechanisms uncharacterized.

6 Limitations and Future Work

  • An unsuccessful audit does not establish that a mechanism satisfies its claimed privacy guarantee.It indicates only that the evaluated canary, witness statistic, and decision rule did not expose a violation.Source: §6 · p. 7
  • The case study does not systematically study audit power across canary degrees or other structural characteristics, and covers only one Node-DP mechanism.Thus, it does not characterize the prevalence of similar issues across the broader graph privacy literature.Source: §6 · p. 7
  • Future work could apply the methodology to Edge-DP methods, graph analytics mechanisms, and private graph learning pipelines.Source: §6 · p. 7
  • The authors identify automated canary construction and witness selection, and integration with broader graph privacy evaluation frameworks, as valuable future directions.Source: §6 · p. 8

7 Conclusion

The paper concludes that its toolkit-based audits found certified privacy violations in the released PrivDPR implementation, including under restrictive graph-domain conditions. It also finds that witness statistics differ in their ability to expose violations.

7 Conclusion

  • The methodology separates graph canary construction from witness statistic selection while retaining statistically certified privacy testing.Source: §7 · pp. 8–9
  • Certified lower bounds exceeded the claimed privacy budget for the audited PrivDPR implementation, with violations persisting on non-empty and connected graphs and real-world datasets.The audits used synthetic and real-world canary pairs.Source: §7 · p. 9
  • Different witness statistics varied substantially in their ability to expose privacy violations, supporting evaluation with a diverse battery rather than one predefined metric.Source: §7 · p. 9
  • The authors aim for the methodology and toolkit to encourage routine empirical auditing in evaluations of future graph DP mechanisms.Source: §7 · p. 9

Ethics and Privacy Statement

The experiments used synthetic graphs and publicly available datasets; no participants were recruited or contacted.

Ethics and Privacy Statement

  • The experiments used synthetic graphs and publicly available datasets, with no participants recruited or contacted.The case-study audit relied only on publicly released artefacts and documentation, without access to non-public information.Source: Ethics and Privacy Statement · p. 9

AI Use

AI-based tools assisted with proofreading, clarity and flow, and LaTeX formatting, but were not used for the research methodology or scientific claims.

AI Use

  • AI-based tools assisted with proofreading, text clarity and flow, and LaTeX formatting, but not with research methodology or scientific claims.The authors state that they manually verified and take responsibility for the tools’ output.Source: AI Use · p. 9
Loading 2610.31294v1…