betaFeedback

WorksComputer Science

Tight Bounds for Differentially Private Cut Release

Abstract

We give a polynomial-time algorithm for releasing a nonnegative weighted synthetic graph under (ε,δ)(\varepsilon,δ)-edge differential privacy. Given an nn-vertex nonnegative weighted graph G=(V,wG)G=(V,w_G), the output H=(V,wH)H=(V,w_H) satisfies, with probability at least 1−β1-β, simultaneously for every S⊆VS\subseteq V, ∣wG(S,V∖S)−wH(S,V∖S)∣≤γwG(S,V∖S)+O((nlog⁡n)/(εγ))|w_G(S,V\setminus S)-w_H(S,V\setminus S)| \leγw_G(S,V\setminus S)+O\bigl((n\log n)/(\varepsilonγ)\bigr), provided that γ,ε,δ,βγ,\varepsilon,δ,β are at least inverse polynomial in nn. For constant γ,εγ,\varepsilon and δ=β=n−10δ=β=n^{-10}, this improves the recently obtained additive error bound of O(nlog⁡7n)O(n\log^7 n) to O(nlog⁡n)O(n\log n). We also prove a matching Ω(nlog⁡n)Ω(n\log n) lower bound. Our algorithm combines degree decomposition with private multiplicative weights, using a degree-sensitive semidefinite oracle to generate update proposals from single Gaussian samples. Each proposal is validated by a noisy check of its exact entropy decrease, and a joint Rényi analysis of sampling and validation avoids additional logarithmic losses.

Introduction

Graphs that record relationships between individuals, such as social, financial, or communication networks, often contain sensitive information. Differential privacy [3] provides a rigorous framework for publishing statistics of such graphs; we use edge-level privacy, which protects the presence and weight of individual relationships while treating the vertex set as public. A central problem in this setting is to release a synthetic graph that approximately preserves every cut. Cut values underlie cut maximization, balanced partitioning, and clustering, and the released graph can be postprocessed freely, at no additional privacy cost.

Formally, we consider a graph G=(V,wG)G=(V,w_G) on a public vertex set V=[n]V=[n] with nonnegative edge weights wG∈R≥0(n2)w_G\in\mathbb{R}_{\geq0}^{\binom{n}{2}}. For disjoint sets S,T⊆VS,T\subseteq V, we write wG(S,T)w_G(S,T) for the total weight of edges between them, so the cut defined by SS has weight wG(S,V∖S)w_G(S,V\setminus S). Two inputs G,G′G,G' are adjacent if ∥wG−wG′∥1≤1\|w_G-w_{G'}\|_1\leq1, so privacy protects every change of total edge weight at most one, whether concentrated on one edge or spread over many. The weights may be arbitrary nonnegative reals; neither their support nor a bound on their magnitude is public. Given a relative error γ>0\gamma>0, we seek a polynomial-time differentially private mechanism that releases a nonnegative weighted graph H=(V,wH)H=(V,w_H) satisfying, simultaneously for every cut SS,

∣wG(S,V∖S)−wH(S,V∖S)∣≤γwG(S,V∖S)+B,(1)|w_G(S,V\setminus S)-w_H(S,V\setminus S)|\leq\gamma w_G(S,V\setminus S)+B, \tag*{(1)}

with additive error BB as small as possible. The relative term makes the guarantee uninformative for sparse graphs: with purely additive error (γ=0\gamma=0), an error of order n3/2n^{3/2}, up to logarithmic factors, is unavoidable in the worst case over graphs with Θ(n2)\Theta(n^2) edges [6, 12]. This error can exceed every cut value of a sparse graph.

Table 1 summarizes the known bounds. In the purely additive setting, independent noise on every edge weight gives additive error O~(n3/2/ϵ)\widetilde{O}(n^{3/2}/\epsilon), where O~\widetilde{O} hides logarithmic factors, including the dependence on δ\delta. Following earlier work by Gupta, Roth, and Ullman [9] and Eliáš, Kapralov, Kulkarni, and Lee [6], Liu, Upadhyay, and Zou [12] obtained O~(mn/ϵ)\widetilde{O}(\sqrt{mn}/\epsilon) additive error for graphs with mm weighted edges, which is tight for dense graphs up to logarithmic factors. With relative error, Blocki, Blum, Datta, and Sheffet [2] obtained nearly linear additive error by applying the exponential mechanism to the exponentially large family of sparse graphs; no polynomial-time implementation is known. Aamand et al. [1] gave the first polynomial-time mechanism below the n3/2n^{3/2} scale, with additive error n5/4+o(1)n^{5/4+o(1)} for constant γ\gamma and ϵ\epsilon, using a private expander decomposition, and Fan et al. [7] reduced the additive error to n13/12+o(1)n^{13/12+o(1)} for unweighted inputs through degree-sensitive private spectral primitives.

ResultPrivacyRunning timeGuarantee
[6]approximatepolynomialwG(S,V∖S)±O~(∥wG∥1n)w_G(S,V \setminus S) \pm\widetilde{O}(\sqrt{\lVert w_G\rVert_1 n})
[12]approximatepolynomialwG(S,V∖S)±O~(mn)w_G(S,V \setminus S) \pm\widetilde{O}(\sqrt{mn})
[2]pureexponential*(1±γ)wG(S,V∖S)±npoly⁡(log⁡n)(1 \pm\gamma)w_G(S,V \setminus S) \pm n\operatorname{poly}(\log n)
[1]approximatepolynomial(1±γ)wG(S,V∖S)±n5/4+o(1)(1 \pm\gamma)w_G(S,V \setminus S) \pm n^{5/4+o(1)}
[7]†approximatepolynomial(1±γ)wG(S,V∖S)±n13/12+o(1)(1 \pm\gamma)w_G(S,V \setminus S) \pm n^{13/12+o(1)}
[5]approximatepolynomial(1±γ)wG(S,V∖S)±O(nlog⁡7n)(1 \pm\gamma)w_G(S,V \setminus S) \pm O(n\log^7 n)
Theorem 1.1approximatepolynomial(1±γ)wG(S,V∖S)±O(nlog⁡n)(1 \pm\gamma)w_G(S,V \setminus S) \pm O(n\log n)
Lower bound [5]approximate—B=Ω(n)B = \Omega(n)
Theorem 1.2approximate—B=Ω(nlog⁡n)B = \Omega(n\log n)

Table 1. Error bounds for private all-cut release on nn-vertex graphs, with m=∥wG∥0m = \lVert w_G\rVert_0. We fix constant ϵ\epsilon, γ\gamma and δ=β=n−c\delta= \beta= n^{-c} for constant c≥2c \ge2; O~\widetilde{O} hides polylogarithmic factors. *Information-theoretic exponential mechanism. †Unweighted inputs.

Most recently, Eliáš et al. [5] gave the first polynomial-time algorithm with nearly linear additive error, B=O(ϵ−1γ−1nlog⁡7(n/(γϵδβ)))B = O(\epsilon^{-1}\gamma^{-1}n\log^7(n/(\gamma\epsilon\delta\beta))) for arbitrary nonnegative weighted graphs. They also prove a lower bound of Ω((n/ϵ)min⁡{n,1/γ})\Omega((n/\epsilon)\min\{\sqrt{n},1/\gamma\}) for 0<γ≤1/40 < \gamma\le1/4, δ≤ϵ/100\delta\le\epsilon/100, and β≤1/40\beta\le1/40. For fixed γ\gamma and ϵ\epsilon and inverse-polynomial δ\delta and β\beta, the optimal additive error was therefore known to lie between Ω(n)\Omega(n) and O(nlog⁡7n)O(n\log^7 n). We show that it is Θ(nlog⁡n)\Theta(n\log n): a single logarithmic factor is both sufficient, in polynomial time, and necessary.

Our results

Theorem 1.1 (Weighted cut release). Fix a constant c≥1c \ge1. Let n≥2n \ge2, n−c≤γ≤1/4n^{-c} \le\gamma\le1/4, n−c≤ϵ≤1n^{-c} \le\epsilon\le1, and n−c≤δ,β<1/10n^{-c} \le\delta, \beta< 1/10. There is an (ϵ,δ)(\epsilon,\delta)-differentially private algorithm that, given any nonnegative weighted graph G=(V,wG)G = (V,w_G) on V=[n]V = [n], outputs a nonnegative weighted graph H=(V,wH)H = (V,w_H) satisfying, with probability at least 1−β1-\beta, simultaneously for all S⊆VS \subseteq V,

∣wG(S,V∖S)−wH(S,V∖S)∣≤γwG(S,V∖S)+O(nlog⁡nϵγ).(2)\lvert w_G(S,V \setminus S)-w_H(S,V \setminus S)\rvert\le\gamma w_G(S,V \setminus S)+O\left(\frac{n\log n}{\epsilon\gamma}\right). \tag*{(2)}

The implied constant depends only on cc. For rational inputs, the running time is polynomial in nn and the input encoding length.

The inverse-polynomial assumptions allow the additive error to be written as O((n/(ϵγ))log⁡n)O((n/(\epsilon\gamma))\log n). Without these assumptions, the analysis gives the more general bound in (25), which makes the dependence on γ,ϵ,δ,β\gamma,\epsilon,\delta,\beta explicit.

Theorem 1.2 (Lower bound). Fix a constant κ∈(0,1/2)\kappa\in(0,1/2). For sufficiently large nn, let n−1/2+κ≤γ≤1/4n^{-1/2+\kappa} \le\gamma\le1/4, 0<ε≤10 < \varepsilon\le1, 0≤δ≤ε/n20 \le\delta\le\varepsilon/n^2, and 0≤β≤1/40 \le\beta\le1/4. Any (ε,δ)(\varepsilon,\delta)-differentially private mechanism that, on every nonnegative weighted input graph GG on [n][n], outputs a nonnegative weighted graph HH satisfying (1) simultaneously for all cuts with probability at least 1−β1-\beta must have

B=Ω(nlog⁡nεγ).(3)B = \Omega\left(\frac{n\log n}{\varepsilon\gamma}\right). \tag*{(3)}

The implied constant depends only on κ\kappa.

Together, Theorems 1.1 and 1.2 determine the optimal additive error Θ(nlog⁡n/(εγ))\Theta(n\log n/(\varepsilon\gamma)) under their common parameter assumptions. In particular, the optimal error is Θ(nlog⁡n)\Theta(n\log n) for constant γ\gamma, ε\varepsilon and δ=β=n−10\delta=\beta=n^{-10}. § 5 gives a more general lower bound.

Technical overview

The logarithm in our bound reflects the cost of making many noisy decisions accurate simultaneously while keeping the total privacy loss small. We account for these costs, together with the logarithm in the initial entropy potential, through the parameter

σ=Θ(1εlog⁡nγεδβ).\sigma= \Theta\left(\frac{1}{\varepsilon}\log\frac{n}{\gamma\varepsilon\delta\beta}\right).

The guiding principle of the design is to pay this logarithm only once: neither the number of degree layers nor the number of trials should introduce another logarithmic factor. In the parameter range of Theorem 1.1, our mechanism achieves a total additive error of O(nσ/γ)O(n\sigma/\gamma). We first recall the framework we build on and then describe the three ideas that achieve this.

Private multiplicative weights with a semidefinite oracle. Our mechanism is a private multiplicative-weights search [11]. It maintains a public candidate graph hh, repeatedly looks for a cut on which hh is inaccurate, and then scales the edges of hh across that cut up or down, depending on whether hh underestimates or overestimates the cut. Progress is measured by the relative entropy between the private graph and hh, which decreases with every good update. The most violated cut cannot be used directly: finding it is NP-hard, and small input changes can change the maximizing cut abruptly, making its direct release incompatible with privacy. As in [6, 7, 5], we instead solve a semidefinite relaxation of the cut problem regularized by λlog⁡det⁡X\lambda\log\det X. Its optimizer XX is a covariance matrix, and a Gaussian vector z∼N(0,X)z\sim N(0,X) assigns each pair uvuv a nonnegative score (zu−zv)2/4(z_u-z_v)^2/4, giving a random update direction. The log-determinant term makes XX insensitive to small changes of the private graph, so the sample zz can be released at a cost of O(α/λ2)O(\alpha/\lambda^2) in Rényi divergence of order α\alpha, provided α/λ\alpha/\lambda is sufficiently small (Lemma 4.3).

References

  1. [1]Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Breaking the n^{1.5} additive error barrier for private and efficient graph sparsification via private expander decomposition. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research, pages 59–72, 2025.arxiv.org/abs/2507.01873
  2. [2]Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson–Lindenstrauss transform itself preserves differential privacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 410–419. IEEE, 2012.
  3. [3]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006.
  4. [4]Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.
  5. [5]Marek Eliáš, Gautam Kamath, Janardhan Kulkarni, George Z. Li, Jingcheng Liu, Sepideh Mahabadi, Pan Peng, Jakub Tarnawski, Hangyu Xu, and Zongrui Zou. Polynomial-time differentially private synthetic graph release with nearly-linear additive error. arXiv preprint arXiv:2611.06670, 2026.arxiv.org/abs/2611.06670
  6. [6]Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560–578. SIAM, 2020.
  7. [7]Chenglin Fan, Jingcheng Liu, Pan Peng, Hangyu Xu, and Zongrui Zou. Private approximation of graph spectra and cuts via spectral amplifiers. arXiv preprint arXiv:2607.18846, 2026.arxiv.org/abs/2607.18846
  8. [9]Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of Cryptography Conference (TCC), volume 7194 of Lecture Notes in Computer Science, pages 339–356. Springer, 2012.
  9. [10]Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115–1145, 1995.DOI
  10. [11]Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 61–70. IEEE, 2010.DOI
  11. [12]Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1019–1049. SIAM, 2024.arxiv.org/abs/2309.17330
  12. [13]Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017.DOI
  13. [14]Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94–103. IEEE, 2007.
  14. [15]Yurii Nesterov and Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, 1994.DOI

Paper details

vlnc:W_drrk7pfx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents