Differentially Private Densest Subgraph Detection
This work addresses privacy concerns in graph mining for domains with sensitive network data, though it is incremental as it applies differential privacy to an existing problem.
The paper tackled the problem of detecting the densest subgraph in private networks by developing the first sequential and parallel differentially private algorithms, achieving an additive approximation guarantee and demonstrating a good privacy-accuracy tradeoff on high-density real-world networks.
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.