Differentially Private Analysis on Graph Streams
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
Text
Upadhyay et al. "Differentially Private Analysis on Graph Streams." Artificial Intelligence and Statistics, 2021.Markdown
[Upadhyay et al. "Differentially Private Analysis on Graph Streams." Artificial Intelligence and Statistics, 2021.](https://mlanthology.org/aistats/2021/upadhyay2021aistats-differentially/)BibTeX
@inproceedings{upadhyay2021aistats-differentially,
title = {{Differentially Private Analysis on Graph Streams}},
author = {Upadhyay, Jalaj and Upadhyay, Sarvagya and Arora, Raman},
booktitle = {Artificial Intelligence and Statistics},
year = {2021},
pages = {1171-1179},
volume = {130},
url = {https://mlanthology.org/aistats/2021/upadhyay2021aistats-differentially/}
}