We proposed an adaptation of DP to edge-labeled directed graphs with an underlying semantic. The main difficulty is that It proposes methods to query RDF graphs while respecting DP constraints and contribute to designing, implementing, and evaluating algorithms that guarantee privacy while preserving data utility. The main
Design principle
Privacy models: we consider three privacy definitions: node, outedge and typed-outedge privacy. We formalize three distances over RDF graphs to define the corresponding notions of neighborhood.
Approach: The approach is based on graph projection to adapt DP to RDF graphs while reducing the sensitivity of many queries. In detail, we introduced three edge-addition based graph projection methods that transform the original RDF graph into a graph of bounded degree, bounded out-degree, and bounded typed-out-degree .
Two of the proposed projections are proven to preserve neighborhoods, allowing to expand the domain of any differentially private algorithm from graphs with bounded out- or typed-out-degree to any arbitrary RDF graph.
Analytical and experimental evaluation show improvement of up to two order of magnitude over a naive approach without projection.
Code
A prototype has been implemented that performs the proposed projections and apply DP mechanisms to various queries. Its code is available on github.
References
[1] Sara Taki, Cédric Eichler, Benjamin Nguyen. « It’s Too Noisy in Here: Using Projection to Improve Differential Privacy on RDF Graphs. » ADBIS (Short Papers) 2022: 212-221