Differentially Private Algorithms for Graphs Under Continual Observation

• URL: http://arxiv.org/abs/2106.14756v3
• Date: Tue, 23 Sep 2025 09:51:03 GMT
• Title: Differentially Private Algorithms for Graphs Under Continual Observation
• Authors: Hendrik Fichtenberger, Monika Henzinger, Lara Ost,
• Abstract summary: We study differentially private dynamic graph algorithms for graph problems under continual observation.<n>We present event-level private problems such as triangle count that improve the additive error by a factor.<n>We also give $varepsilon$-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching.
• Score: 11.111949824180277
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 \log^{3/2}T / \varepsilon)$, where $W$ is the maximum weight of any edge, which, as we show, is tight up to a $(\sqrt{\log T} / \varepsilon)$-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error $(1+\beta)$ for any constant $\beta > 0$ and additive error $O(W \log(nW) \log(T) / (\varepsilon \beta))$. 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.

Related papers

• Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism [5.4971134662997025]
  We formulate a novel generalized sparse vector technique which generalizes SVT to vectors with multiple dimensions.<n>As an application, we solve a number of important graph problems with better bounds than previous work.<n>We give a tight local edge DP algorithm for $k$-core decomposition with $O(epsilon-1log n)$ additive error and no multiplicative error in $O(n)$ rounds.
  arXiv  Detail & Related papers  (2025-08-04T08:26:58Z)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  We give the first sublinear space differentially private algorithms for the fundamental problem of counting distinct elements in the turnstile streaming model.<n>Our result significantly improves upon the space requirements of the state-of-the-art algorithms for this problem, which is linear.<n>When a bound $W$ on the number of times an item appears in the stream is known, our algorithm provides $tildeO_eta(sqrtW)$ additive error using $tildeO_eta(sqrtW)$ space.
  arXiv  Detail & Related papers  (2025-05-29T17:21:20Z)
• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  We study the problem of robustly estimating the edge density of ErdHos-R'enyi random graphs $G(n, dcirc/n)$.<n>Our algorithm is based on the sum-of-squares hierarchy.
  arXiv  Detail & Related papers  (2025-03-05T21:45:17Z)
• Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
  We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates.<n>Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only.<n>We give upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems.
  arXiv  Detail & Related papers  (2024-09-26T08:17:49Z)
• Faster Private Minimum Spanning Trees [11.72102598708538]
  We present a new differentially private MST algorithm that matches the utility of existing in-place methods while running in time. We present a data structure that allows us to sample a noisy minimum weight edge among at most $O(n2)$ cut edges in $O(sqrtn log n)$ time.
  arXiv  Detail & Related papers  (2024-08-13T16:00:30Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  We make novel use of sparsification techniques from the non-private streaming and static algorithms literature to achieve new results in the sublinear space, continual release setting.<n>This includes algorithms for densest subgraph, maximum matching, and the first continual release $k$-core decomposition algorithm.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  We show that an $eps$-edge differentially private algorithm for $k$-core decomposition outputs the core numbers with no multiplicative error and $O(textlog(n)/eps)$ additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error.
  arXiv  Detail & Related papers  (2023-12-12T20:09:07Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Private Isotonic Regression [54.32252900997422]
  We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
  arXiv  Detail & Related papers  (2022-10-27T05:08:07Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.