Differentially Private Densest Subgraph Detection

Dung Nguyen, Anil Vullikanti
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:8140-8151, 2021.

Abstract

Densest subgraph detection is a fundamental graph mining problem, with a large number of applications. There has been a lot of work on efficient algorithms for finding the densest subgraph in massive networks. However, in many domains, the network is private, and returning a densest subgraph can reveal information about the network. Differential privacy is a powerful framework to handle such settings. We study the densest subgraph problem in the edge privacy model, in which the edges of the graph are private. We present the first sequential and parallel differentially private algorithms for this problem. We show that our algorithms have an additive approximation guarantee. We evaluate our algorithms on a large number of real-world networks, and observe a good privacy-accuracy tradeoff when the network has high density.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-nguyen21i, title = {Differentially Private Densest Subgraph Detection}, author = {Nguyen, Dung and Vullikanti, Anil}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {8140--8151}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/nguyen21i/nguyen21i.pdf}, url = {https://proceedings.mlr.press/v139/nguyen21i.html}, abstract = {Densest subgraph detection is a fundamental graph mining problem, with a large number of applications. There has been a lot of work on efficient algorithms for finding the densest subgraph in massive networks. However, in many domains, the network is private, and returning a densest subgraph can reveal information about the network. Differential privacy is a powerful framework to handle such settings. We study the densest subgraph problem in the edge privacy model, in which the edges of the graph are private. We present the first sequential and parallel differentially private algorithms for this problem. We show that our algorithms have an additive approximation guarantee. We evaluate our algorithms on a large number of real-world networks, and observe a good privacy-accuracy tradeoff when the network has high density.} }
Endnote
%0 Conference Paper %T Differentially Private Densest Subgraph Detection %A Dung Nguyen %A Anil Vullikanti %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-nguyen21i %I PMLR %P 8140--8151 %U https://proceedings.mlr.press/v139/nguyen21i.html %V 139 %X Densest subgraph detection is a fundamental graph mining problem, with a large number of applications. There has been a lot of work on efficient algorithms for finding the densest subgraph in massive networks. However, in many domains, the network is private, and returning a densest subgraph can reveal information about the network. Differential privacy is a powerful framework to handle such settings. We study the densest subgraph problem in the edge privacy model, in which the edges of the graph are private. We present the first sequential and parallel differentially private algorithms for this problem. We show that our algorithms have an additive approximation guarantee. We evaluate our algorithms on a large number of real-world networks, and observe a good privacy-accuracy tradeoff when the network has high density.
APA
Nguyen, D. & Vullikanti, A.. (2021). Differentially Private Densest Subgraph Detection. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:8140-8151 Available from https://proceedings.mlr.press/v139/nguyen21i.html.

Related Material