Graph Rewriting Primitives for Semantic Graph Databases Sanitization

Adrien Boiret¹ , Cédric Eichler 1¹ , Benjamin Nguyen 1¹ and Sara Taki¹

INSA Centre Val de Loire, Laboratoire d’Informatique Fondamentale d’Orléans
88 Bd Lahitolle, 18000 Bourges, France
firstname.lastname@insa-cvl.fr

Abstract

Due to the rapid proliferation of data online, an important quantity of private or sensitive informations is being stored as linked data in graph databases (e.g., represented as RDF). For such databases to be shared without jeopardizing privacy, they must first undergo a process known as database sanitization. During this process, databases are transformed following graph transformations that are usually described informally or through ad-hoc processes. However, a more thourough formalization of these transformations would aid in analysing the sanitization process, ensuring its correctness, and demonstrating the resulting privacy guarantees. This paper is an effort toward bridging the gap between the rigorous graph rewriting approaches and graph sanitization. We propose a graph transformation language to serve as a basis for constructing various sanitization mechanisms. This language relies on a set of elementary transformation operators formalized using a generic algebraic graph rewriting approach. Our language takes into account semantic and supports the equivalent of W HERE and E XCEPT clauses. As a proof of concept, we use these operators to implement two mechanisms from the literature, one generic (Local Differential Privacy) and one specifically introduced for semantic graph databases (sensitive attribute masking through anatomization). We propose an open-sourced tool implementing the elementary operators and the privacy mechanisms we derive from them relying on the Attributed Graph Grammar System (AGG) and its java API, providing a concrete tool implementing formal graph rewriting mechanisms to sanitize semantic graph databases. We present experimental results on this implementation regarding both proposed schemes and discuss its efficiency and scalability.

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS230426026B

Publication information

Volume 21, Issue 3 (June 2024)
Year of Publication: 2024
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

Download Available in PDF
Portable Document Format

How to cite

Boiret, A., 1, C. E., 1, B. N., Taki, S.: Graph Rewriting Primitives for Semantic Graph Databases Sanitization. Computer Science and Information Systems, Vol. 21, No. 3, 1033-1054. (2024), https://doi.org/10.2298/CSIS230426026B