# Differentially Private Algorithms for Graphs Under Continual Observation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2021.

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

- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [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)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)
- [Privacy-Preserving Graph Machine Learning from Data to Computation: A Survey](https://mlsanity.com/paper/2307.04338/) (2023)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Concurrent Shuffle Differential Privacy Under Continual Observation](https://mlsanity.com/paper/2301.12535/) (2023)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)
- [The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting](https://mlsanity.com/paper/2607.00876/) (2026)
- [Differentially Private Range Subgraph Counting](https://mlsanity.com/paper/2606.08179/) (2026)

## Abstract (arXiv)

Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T. We also give varepsilon-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log3/2T / varepsilon), where W is the maximum weight of any edge, which, as we show, is tight up to a (√log T / varepsilon)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (varepsilon β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution's range.