# Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 13 Oct 2025.

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

- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)
- [Densest Subgraph in Dynamic Graph Streams](https://mlsanity.com/paper/1506.04417/) (2015)
- [Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs](https://mlsanity.com/paper/2211.10887/) (2022)
- [Optimal Bounds on Private Graph Approximation](https://mlsanity.com/paper/2309.17330/) (2023)
- [Differentially Private Continual Release of Graph Statistics](https://mlsanity.com/paper/1809.02575/) (2018)
- [Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation](https://mlsanity.com/paper/2306.10428/) (2023)
- [Rejoinder: Gaussian Differential Privacy](https://mlsanity.com/paper/2104.01987/) (2021)
- [Dynamic Graph Stream Algorithms in o(n) Space](https://mlsanity.com/paper/1605.00089/) (2016)
- [Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs](https://mlsanity.com/paper/2305.16815/) (2023)
- [Differentially Private Matchings](https://mlsanity.com/paper/2501.00926/) (2025)
- [Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism](https://mlsanity.com/paper/2508.02182/) (2025)

## Abstract (arXiv)

We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms, with a focus on the densest subgraph problem (DSG) in the insertion-only setting. Our main result is the first continual release DSG algorithm that matches the additive error of the best static DP algorithms and the space complexity of the best non-private streaming algorithms, up to constants. The key idea is a refined use of subsampling that simultaneously achieves privacy amplification and sparsification, a connection not previously formalized in graph DP. Via a simple black-box reduction to the static setting, we obtain both pure and approximate-DP algorithms with O(log n) additive error and O(nlog n) space, improving both accuracy and space complexity over the previous state of the art. Along the way, we introduce graph densification in the graph DP setting, adding edges to trigger earlier subsampling, which removes the extra logarithmic factors in error and space incurred by prior work [ELMZ25]. We believe this simple idea may be of independent interest.