Abstract
Differential privacy is one of the most popular and prevalent definitions of privacy, providing a robust and mathematically rigid definition of privacy. In the last decade, adaptation of DP to graph data has received growing attention. Most efforts have been dedicated to unlabeled homogeneous graphs, while labeled graphs with an underlying semantic (e.g. RDF) have been mildly addressed.
In this paper, we present a new approach based on graph projection to adapt differential privacy to RDF graphs, while reducing query sensitivity. We propose an edge-addition based graph projection method that transforms the original RDF graph into a graph with bounded typed-out-degree. We demonstrate that this projection preserves neighborhood, allowing to construct a differentially private mechanism on graphs given a similar mechanism on graphs with bounded typed-out degree. Experimental and analytical evaluation through a realistic twitter use-case show that this provide up to two orders of magnitude of utility improvement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Blocki, J., Blum, A., Datta, A., Sheffet, O.: Differentially private data analysis of social networks via restricted sensitivity. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 87–96 (2013)
Day, W.Y., Li, N., Lyu, M.: Publishing graph degree distribution with node differential privacy. In: Proceedings of the 2016 International Conference on Management of Data, pp. 123–138 (2016)
Delanaux, R., Bonifati, A., Rousset, M.-C., Thion, R.: Query-based linked data anonymization. In: Vrandečić, D., et al. (eds.) ISWC 2018. LNCS, vol. 11136, pp. 530–546. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00671-6_31
Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 1–12. Springer, Heidelberg (2006). https://doi.org/10.1007/11787006_1
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_14
Dwork, C., Roth, A., et al.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9(3–4), 211–407 (2014)
Hay, M., Li, C., Miklau, G., Jensen, D.: Accurate estimation of the degree distribution of private networks. In: 2009 Ninth IEEE International Conference on Data Mining, pp. 169–178. IEEE (2009)
Heitmann, B., Hermsen, F., Decker, S.: k-RDF-neighbourhood anonymity: combining structural and attribute-based anonymisation for linked data. PrivOn@ ISWC 1951 (2017)
Johnson, N., Near, J.P., Song, D.: Towards practical differential privacy for SQL queries. Proc. VLDB Endow. 11(5), 526–539 (2018)
Kasiviswanathan, S.P., Nissim, K., Raskhodnikova, S., Smith, A.: Analyzing graphs with node differential privacy. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 457–476. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_26
Klyne, G., Carroll, J.J.: Resource description framework (RDF): concepts and abstract syntax. W3C Recommendation (2004). http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/
Radulovic, F., García-Castro, R., Gómez-Pérez, A.: Towards the anonymisation of RDF data. In: SEKE, pp. 646–651 (2015)
Raskhodnikova, S., Smith, A.: Efficient Lipschitz extensions for high-dimensional graph statistics and node private degree distributions. arXiv preprint arXiv:1504.07912 (2015)
Reuben, J.: Towards a differential privacy theory for edge-labeled directed graphs. SICHERHEIT 2018 (2018)
Silva, R.R.C., Leal, B.C., Brito, F.T., Vidal, V.M., Machado, J.C.: A differentially private approach for querying RDF data of social networks. In: Proceedings of the 21st International Database Engineering & Applications Symposium, pp. 74–81 (2017)
Task, C., Clifton, C.: A guide to differential privacy theory in social network analysis. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 411–417. IEEE (2012)
Acknowledgements
This work is supported by the French National Research Agency, under grant ANR-18-CE23-0010.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Taki, S., Eichler, C., Nguyen, B. (2022). It’s Too Noisy in Here: Using Projection to Improve Differential Privacy on RDF Graphs. In: Chiusano, S., et al. New Trends in Database and Information Systems. ADBIS 2022. Communications in Computer and Information Science, vol 1652. Springer, Cham. https://doi.org/10.1007/978-3-031-15743-1_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-15743-1_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15742-4
Online ISBN: 978-3-031-15743-1
eBook Packages: Computer ScienceComputer Science (R0)