Lower bounds on private graph optimization error under differential privacy
Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
Data Structures and AlgorithmsCryptography and Security
Summary
The paper looks at how well we can keep certain details private when solving graph problems like finding the cheapest way to connect points or match pairs. It shows that even if you allow a small chance of privacy leakage, there’s a minimum unavoidable error when protecting edge weights. This error depends on the graph size and cannot be reduced for many graphs, meaning some mistakes in the output are inevitable if privacy is strong. The authors expand known limitations and explain when approximate privacy doesn’t improve results.
What this means in practice
- •For network system designers: Understand fundamental limits when adding differential privacy to network weight optimization tasks to better balance privacy and solution accuracy.
- •For privacy engineers: Recognize that approximate differential privacy may not improve error rates in certain graph problems, guiding design choices for private algorithms.
A theory result. No direct application yet.
Authors
Jacob Imola, Rasmus Pagh, Lukas Retschmeier
Abstract
This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.