Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

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,) where the vertex set V and edges E are public and the weights w:E to R must be kept differentially private under an 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 times (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 (epsilon,δ) -DP as long as δ at most (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 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 infinity 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 Ω((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.