# Differentially Private Densest Subgraph Detection

arXiv: https://arxiv.org/abs/2105.13287 · HTML: https://mlsanity.com/paper/2105.13287/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 46 references that are in the map.
- First posted on arXiv 27 May 2021.

## Builds on (most cited first, 6 of 6)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]](https://mlsanity.com/paper/1304.4795/) (2013)
- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [Detecting Communities under Differential Privacy](https://mlsanity.com/paper/1607.02060/) (2016)
- [Differentially Private Exponential Random Graphs](https://mlsanity.com/paper/1409.4696/) (2014)

## Built on by (most cited first, 7 of 7)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Sharper Utility Bounds for Differentially Private Models](https://mlsanity.com/paper/2204.10536/) (2022)
- [Privacy-Preserving Graph Embedding based on Local Differential Privacy](https://mlsanity.com/paper/2310.11060/) (2023)
- [Differentially Private Partial Set Cover with Applications to Facility Location](https://mlsanity.com/paper/2207.10240/) (2022)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)

## Abstract (arXiv)

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.