Differentially Private Analysis on Graph Streams

Jalaj Upadhyay, Sarvagya Upadhyay, Raman Arora
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:1171-1179, 2021.

Abstract

In this paper, we focus on answering queries, in a differentially private manner, on graph streams. We adopt the sliding window model of privacy, where we wish to perform analysis on the last $W$ updates and ensure that privacy is preserved for the entire stream. We show that in this model, the price of ensuring differential privacy is minimal. Furthermore, since differential privacy is preserved under post-processing, our results can be used as a subroutine in many tasks, including Lipschitz learning on graphs, cut functions, and spectral clustering.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-upadhyay21a, title = { Differentially Private Analysis on Graph Streams }, author = {Upadhyay, Jalaj and Upadhyay, Sarvagya and Arora, Raman}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {1171--1179}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/upadhyay21a/upadhyay21a.pdf}, url = {https://proceedings.mlr.press/v130/upadhyay21a.html}, abstract = { In this paper, we focus on answering queries, in a differentially private manner, on graph streams. We adopt the sliding window model of privacy, where we wish to perform analysis on the last $W$ updates and ensure that privacy is preserved for the entire stream. We show that in this model, the price of ensuring differential privacy is minimal. Furthermore, since differential privacy is preserved under post-processing, our results can be used as a subroutine in many tasks, including Lipschitz learning on graphs, cut functions, and spectral clustering. } }
Endnote
%0 Conference Paper %T Differentially Private Analysis on Graph Streams %A Jalaj Upadhyay %A Sarvagya Upadhyay %A Raman Arora %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-upadhyay21a %I PMLR %P 1171--1179 %U https://proceedings.mlr.press/v130/upadhyay21a.html %V 130 %X In this paper, we focus on answering queries, in a differentially private manner, on graph streams. We adopt the sliding window model of privacy, where we wish to perform analysis on the last $W$ updates and ensure that privacy is preserved for the entire stream. We show that in this model, the price of ensuring differential privacy is minimal. Furthermore, since differential privacy is preserved under post-processing, our results can be used as a subroutine in many tasks, including Lipschitz learning on graphs, cut functions, and spectral clustering.
APA
Upadhyay, J., Upadhyay, S. & Arora, R.. (2021). Differentially Private Analysis on Graph Streams . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:1171-1179 Available from https://proceedings.mlr.press/v130/upadhyay21a.html.

Related Material