Document Open Access Logo

Differentially Private Algorithms for Graphs Under Continual Observation

Authors Hendrik Fichtenberger , Monika Henzinger, Lara Ost

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2021.42.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Security and privacy → Pseudonymity, anonymity and untraceability
Keywords
  • differential privacy
  • continual observation
  • dynamic graph algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T.
We also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range.

Cite As Get BibTex

Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially Private Algorithms for Graphs Under Continual Observation. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.42

Author Details

Hendrik Fichtenberger
  • Universität Wien, Austria
Monika Henzinger
  • Universität Wien, Austria
Lara Ost
  • Universität Wien, Austria

Funding

Research supported by the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Lara Ost gratefully acknowledges the financial support from the Vienna Graduate School on Computational Optimization which is funded by the Austrian Science Fund (FWF project no. W1260-N35).

References

  1. Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 13399-13410. Curran Associates, Inc., 2019. Google Scholar
  2. Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '07, pages 273-282, New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1265530.1265569.
  3. Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, pages 87-96, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2422436.2422449.
  4. BlumAvrim, LigettKatrina, and RothAaron. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM), May 2013. URL: https://doi.org/10.1145/2450142.2450148.
  5. T. H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams. In Simone Fischer-Hübner and Matthew Wright, editors, Privacy Enhancing Technologies, Lecture Notes in Computer Science, pages 140-159, Berlin, Heidelberg, 2012. Springer. URL: https://doi.org/10.1007/978-3-642-31680-7_8.
  6. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3), 2011. URL: https://doi.org/10.1145/2043621.2043626.
  7. Shixi Chen and Shuigeng Zhou. Recursive mechanism: Towards node differential privacy and unrestricted joins. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD '13, pages 653-664, New York, NY, USA, June 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2463676.2465304.
  8. Wei-Yen Day, Ninghui Li, and Min Lyu. Publishing Graph Degree Distribution with Node Differential Privacy. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, pages 123-138, New York, NY, USA, June 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2882903.2926745.
  9. Cynthia Dwork. Differential Privacy. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, Lecture Notes in Computer Science, pages 1-12, Berlin, Heidelberg, 2006. Springer. URL: https://doi.org/10.1007/11787006_1.
  10. Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pages 371-380, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1536414.1536466.
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Lecture Notes in Computer Science, pages 265-284, Berlin, Heidelberg, 2006. Springer. URL: https://doi.org/10.1007/11681878_14.
  12. Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, page 715–724, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806787.
  13. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pages 381-390, New York, NY, USA, May 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1536414.1536467.
  14. Marek Eliás, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially Private Release of Synthetic Graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 560-578. Society for Industrial and Applied Mathematics, December 2019. URL: https://doi.org/10.1137/1.9781611975994.34.
  15. M. A. Erdogdu and N. Fawaz. Privacy-utility trade-off under continual observation. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 1801-1805, June 2015. URL: https://doi.org/10.1109/ISIT.2015.7282766.
  16. Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially Private Combinatorial Optimization. In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pages 1106-1125. Society for Industrial and Applied Mathematics, January 2010. URL: https://doi.org/10.1137/1.9781611973075.90.
  17. Moritz Hardt and Guy N. Rothblum. A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 61-70, October 2010. URL: https://doi.org/10.1109/FOCS.2010.85.
  18. M. Hay, C. Li, G. Miklau, and D. Jensen. Accurate Estimation of the Degree Distribution of Private Networks. In 2009 Ninth IEEE International Conference on Data Mining, pages 169-178, 2009. URL: https://doi.org/10.1109/ICDM.2009.11.
  19. Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146-1157, August 2011. URL: https://doi.org/10.14778/3402707.3402749.
  20. S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What Can We Learn Privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 531-540, 2008. URL: https://doi.org/10.1109/FOCS.2008.27.
  21. Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing Graphs with Node Differential Privacy. In Amit Sahai, editor, Theory of Cryptography, Lecture Notes in Computer Science, pages 457-476, Berlin, Heidelberg, 2013. Springer. URL: https://doi.org/10.1007/978-3-642-36594-2_26.
  22. Georgios Kellaris, Stavros Papadopoulos, Xiaokui Xiao, and Dimitris Papadias. Differentially private event sequences over infinite streams. Proceedings of the VLDB Endowment, 7(12):1155-1166, 2014. URL: https://doi.org/10.14778/2732977.2732989.
  23. Wentian Lu and Gerome Miklau. Exponential random graph estimation under differential privacy. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pages 921-930, New York, NY, USA, August 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2623330.2623683.
  24. Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proceedings of the VLDB Endowment, 10(6), 2017. Google Scholar
  25. F. McSherry and K. Talwar. Mechanism Design via Differential Privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103, October 2007. URL: https://doi.org/10.1109/FOCS.2007.66.
  26. Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 75-84, New York, NY, USA, June 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1250790.1250803.
  27. J. Le Ny and G. J. Pappas. Differentially Private Filtering. IEEE Transactions on Automatic Control, 59(2):341-354, 2014. URL: https://doi.org/10.1109/TAC.2013.2283096.
  28. Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, pages 765-774, New York, NY, USA, June 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806794.
  29. Shuang Song, Susan Little, Sanjay Mehta, Staal Vinterbo, and Kamalika Chaudhuri. Differentially private continual release of graph statistics, 2018. URL: http://arxiv.org/abs/1809.02575.
  30. Q. Wang, Y. Zhang, X. Lu, Z. Wang, Z. Qin, and K. Ren. Real-Time and Spatio-Temporal Crowd-Sourced Social Network Data Publishing with Differential Privacy. IEEE Transactions on Dependable and Secure Computing, 15(4):591-606, 2018. URL: https://doi.org/10.1109/TDSC.2016.2599873.
  31. Yue Wang, Xintao Wu, and Leting Wu. Differential Privacy Preserving Spectral Graph Analysis. In Jian Pei, Vincent S. Tseng, Longbing Cao, Hiroshi Motoda, and Guandong Xu, editors, Advances in Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, pages 329-340, Berlin, Heidelberg, 2013. Springer. URL: https://doi.org/10.1007/978-3-642-37456-2_28.
  32. Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Private Release of Graph Statistics using Ladder Functions. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD '15, pages 731-745, New York, NY, USA, May 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2723372.2737785.
  33. Sen Zhang, Weiwei Ni, and Nan Fu. Differentially Private Graph Publishing with Degree Distribution Preservation. Computers & Security, page 102285, 2021. URL: https://doi.org/10.1016/j.cose.2021.102285.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact