Graph privacy release methods fail real-world privacy checks
Practical Auditing of Differentially Private Graph Release Mechanisms: Methodology, Toolkit, and Case Study
Cryptography and Security
Summary
Keeping graph data private is important but hard to check in practice. The authors studied how well privacy protections called differential privacy actually work for graph data. They created tests and a toolkit to check if the privacy guarantees hold up. Using this, they found that a top graph privacy method claimed to protect data was actually weaker than advertised under real testing. Their work shows that different ways of checking privacy can change what problems are found.
What this means in practice
- •For data privacy teams: Verify if graph data privacy mechanisms truly meet their privacy guarantees before deployment.
- •For software engineers: Use the provided toolkit to test graph privacy implementations during software development and maintenance.
Authors
Nicholas D'Silva, Surya Nepal, Salil S. Kanhere
Abstract
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.