PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

Jacob Imola, Rasmus Pagh, Lukas Retschmeier

arXiv:2609.10877v1cs.DScs.CR

TL;DR

The paper studies private graph optimization when sensitive edge weights are protected under ℓ1 differential privacy. It develops reconstruction attacks and proves tight lower bounds for spanning trees and perfect matchings, with additional bounds for hierarchical clustering and broader graph classes.

  • Problem

    Sensitive aggregate information can affect multiple edge weights, motivating differential privacy for graph optimization under an ℓ1 neighboring relation.

  • Method

    The paper encodes binary datasets into randomly or arbitrarily labeled edge weights and uses structures returned by private optimization algorithms to reconstruct data.

  • Results

    The paper proves tight worst-case lower bounds for minimum spanning trees and minimum-weight perfect matchings, and additional lower bounds for hierarchical clustering and broad topology classes.

  • Takeaways & Limitations

    Reconstruction attacks yield lower bounds close to known upper bounds for several private graph optimization problems, including large classes of graph topologies.

  • Takeaways & Limitations

    The lower bounds assume δ ≤ (n/m)^{Ω(1)}, and tight bounds for larger δ remain an open question.

Abstract

from arXiv · show

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.

1 Introduction

This paper develops reconstruction-based lower bounds for private graph optimization, tightening worst-case guarantees and extending hardness results to sparse, expanding topologies and hierarchical clustering.

  • General topology classes: Ω(n/ε) MST error persists on every topology with minimum cut at least Ω(log(n)), showing that sparse graphs cannot generally avoid linear error.This extends the lower-bound perspective beyond unrealistic worst-case topologies.
  • Hierarchical clustering: For hierarchical clustering, the lower bound is parameterized by graph expansion and maximum degree, reaching Ω(n^2) on constant-degree regular expanders.This generalizes prior complete-graph and pure-DP lower bounds to general graphs and approximate DP.
  • Implications: The bounds depend only on graph parameters, so private optimization has good error whenever the optimal solution’s weight or cost is sufficiently larger than the error bound.The conclusion concerns the relationship between graph-parameter error bounds and the scale of the optimum.
  • Reconstruction techniques: The reconstruction attacks encode datasets into edge weights and decode information from sufficiently accurate optimization outputs, contradicting differential privacy.The techniques include large-domain encodings for dense topologies and randomized binary encodings for general topologies.
  • Open limitations: The approximate-DP lower bounds require δ to be polynomially small, while tight bounds for larger δ remain open.The paper notes that this restriction is common because releasing a uniformly drawn δ-fraction of a dataset satisfies (0,δ)-DP.

2 Preliminaries

The preliminaries define private edge-weight graph optimization and introduce reconstruction attacks for proving DP lower bounds.

  • Graph Optimization: The paper studies MST, MWPM, and hierarchical clustering as optimization problems over a known topology.MST and MWPM minimize total selected-edge weight, while hierarchical clustering uses Dasgupta’s cost function.
  • Differential Privacy: The graph topology is public, while edge weights are private under an ℓ1 neighboring relation.Neighboring graphs share V and E and have weight vectors at ℓ1 distance at most one.
  • Reconstruction Attacks: Reconstruction attacks encode private data into graph weights and attempt to recover it from the released optimization solution.Successful coordinate reconstruction contradicts differential privacy.
  • Encoding: The MST encoding maps vector coordinates to right-side value vertices, assigning zero weight to matching values and weight R otherwise.The figure also describes padding for the perfect-matching encoding.
  • Reconstruction Attacks: For binary datasets, DP bounds the success of reconstructing a private subset of coordinates, with negligible δ contribution when δ=o(1/d).For ε<1, the stated bound gives Succ(B)=O(ε).

3 Private Minimum-Weight Spanning Trees

The MST results establish tight worst-case error bounds through large-domain reconstruction and extend linear lower bounds to broad topology classes.

  • 3.1 Tight Lower Bounds on Worst-Case Topologies: The dense-topology attack encodes a vector into a bipartite graph so that an accurate spanning tree reveals many coordinates.Incorrect decoded coordinates require weight-R edges, linking reconstruction error to MST additive error.
  • 3.1 Tight Lower Bounds on Worst-Case Topologies: Θ((n/ε)·log(m/n)) is the tight worst-case MST additive error for m>2n and sufficiently small δ.The bound is achieved by the Laplace mechanism and applies under ℓ1 neighboring.
  • 3.1 Tight Lower Bounds on Worst-Case Topologies: The reconstruction attack contradicts DP because sufficiently low MST error would recover nearly all encoded coordinates.The proof uses induced privacy under Hamming neighbors via a chain of ℓ1-neighboring graphs.
  • 3.1 Tight Lower Bounds on Worst-Case Topologies: The logarithmic factor is obtained for general m by partitioning the construction into subgraphs, each encoding an independent vector.The resulting total error scales with log(m/n).
  • 3.2 Lower Bounds for General Topology Classes: A minimum cut of at least 5 log(n) ensures, with high probability, that the random zero-weight subgraph contains a zero-cost spanning tree.This makes the returned tree informative about the encoded binary dataset.
  • 3.2 Lower Bounds for General Topology Classes: For any topology with minimum cut at least 5 log(n), no approximate-DP MST algorithm can attain additive error below n/(10ε) for ε≤1 and sufficiently small δ.The proof uses binary random weights and a subset reconstruction attack.

4 Minimum-Weight Perfect Matchings

The paper extends reconstruction-based lower bounds from MST to minimum-weight perfect matching using an encoding that controls collisions.

  • Worst-Case Lower Bound: Θ((n/ε)·log(m/n)) is also a tight worst-case additive-error bound for MWPM under approximate DP with sufficiently small δ.The result applies when m>2n under the ℓ1 neighboring relation.
  • Encoding: The MWPM encoding uses a vector of length ⌈αn⌉ and pads the left side with dummy vertices.This adapts the MST encoding while respecting matching constraints.
  • Encoding: Random vectors have only an O(α^2n) number of colliding coordinates with probability at least 1−exp(−Ω(α^3n)).The collision bound allows many coordinates to remain reconstructible in the matching construction.
  • Lower-Bound Proof: The proof sketch reconstructs at least αn(0.99−α) coordinates in expectation, contradicting the reconstruction limit imposed by DP.The same generalization from dense to m-edge graphs is then applied.

5 Hierarchical Clustering under Dasgupta’s Cost Function

The paper develops a sparse reconstruction attack for private hierarchical clustering and derives approximate-DP lower bounds governed by balanced-cut expansion. The attack encodes data on sampled edges, extracts a balanced cut from the clustering, and reconstructs information from zero-weight crossing edges.

  • Reconstruction attack: The method exploits indistinguishability between sampled zero-weight edges and nonsampled edges to ensure that many sampled zero edges remain available for reconstruction.This addresses the difficulty that a low-cost clustering might otherwise avoid sampled edges and produce too little reconstruction information.
  • Reconstruction attack: The attack sparsely encodes a binary dataset into sampled edge weights, runs hierarchical clustering, and reconstructs coordinates from edges crossing an induced balanced cut.Sampled edges receive weight R times their encoded bit, while nonsampled edges receive weight 0; the returned clustering is post-processed into a balanced cut and reconstruction set.
  • Balanced-cut reduction: A clustering tree contains a balanced cut whose normalized crossing weight is at most 27/(4n^3) times its Dasgupta cost, enabling efficient cut extraction.The procedure HCtoBC computes the cut in linear time.
  • Lower bounds: For topologies with ϕ(F) ≥ max{8n, 10000dmax(F) log n}, additive error at most R·nϕ(F)/(400dmax(F)) enables reconstruction success at least 0.4.The attack also reconstructs an expected set of size at least ϕ(F)/(8dmax(F)).
  • Lower bounds: For ε ≤ 1 and δ ≤ 0.01ε/m, no approximate-DP hierarchical-clustering algorithm achieves error below nϕ(F)/(400εdmax(F)) on these topologies.For d-regular spectral expanders with ϕ(F) ≥ Ω(nd), the bound is tight up to log(n) factors relative to the cited upper bound.
  • Low-cost instances: The sparse encoding has low-cost clusterings because independently sampled components are small with high probability, and a separate lemma bounds the optimal cost by O(n·log(n)).The supporting lemma gives cost at most 2^(-α)·4n log(n) with probability at least 1−2n^-3 under the stated random weighting.

6 Private Algorithms with Tight Error

The paper describes an input-privatization algorithm that independently adds Laplace noise to edge weights. A concentration-based analysis yields logarithmically improved upper bounds for MST and MWPM, matching the paper’s reconstruction lower bounds.

  • Input privatization: Independent Laplace perturbation of every edge weight gives superior MST and MWPM error bounds through concentration rather than maximum-noise analysis.The analysis differs from prior approaches that bound the largest perturbation on individual edges.
  • Tight error bounds: For MSTs and MWPMs with k = Θ(n), the resulting upper bound has logarithmic dependence on the relevant edge-count ratio.The supplied passage identifies this improvement as the consequence of the concentration analysis.

7 Conclusion and Future Work

The paper concludes that its worst-case MST and MWPM lower bounds are tight, while lower bounds for broad topology classes remain close to known upper bounds. It identifies unresolved questions for MWPM, hierarchical clustering, and efficient algorithms.

  • Main conclusions: Worst-case MST and MWPM lower bounds are tight with the corresponding upper bounds, while MST and HC bounds for large topology classes are within a log(n) factor.
  • Open problems: Whether MWPM admits lower bounds for a large class of topologies, and which topology property characterizes that class, remains open.
  • Open problems: Closing the hierarchical-clustering lower–upper-bound gap and obtaining a polynomial-time algorithm with the target additive error are identified as open questions.The current alternative mentioned is the exponential mechanism.

B.2 Proof of Theorem 2.4

This proof bounds approximate-DP reconstruction accuracy by relating coordinate-wise errors to conditional probabilities and privacy slack. Summing these bounds yields the stated global success limit.

  • Conditional expectation: The conditional-error calculation combines the privacy inequalities with the law of total probability to obtain a bound involving P[I] and e^ε.
  • Final bound: Theorem 2.4 bounds reconstruction success by (e^ε−1)/(2(e^ε+1)) + dδ/(e^ε+1) for a uniformly random binary dataset.
  • Coordinate-wise error: The proof decomposes each conditional reconstruction error into the two possible bit-flip events and bounds them using approximate-DP inequalities.The decomposition is conditioned on the reconstruction set I and distinguishes xi=1, yi=0 from xi=0, yi=1.
  • Privacy inequalities: Approximate-DP slack is represented by nonnegative functions whose sums over output bits are bounded by δ, enabling the coordinate-wise inequalities.
  • Final bound: The final expectation is obtained by summing over the reconstruction set and simplifying the resulting terms into E[|I|] and dδ contributions.

B.3 Proof of Lemma 3.2

The proof shows that a randomly sampled zero-edge subgraph contains a spanning tree with high probability when every cut is sufficiently large, while bounding coordinate collisions through concentration.

  • Zero-edge spanning tree: A spanning tree entirely composed of zero-weight edges exists whenever every cut contains at least one sampled zero-edge.This equivalence lets the proof reduce existence of a zero-cost spanning tree to showing that no cut is empty in the sampled subgraph.
  • Zero-edge spanning tree: 3/n^2: the probability that some cut has no sampled zero-edge is at most 3/n^2.The proof applies a union bound over cuts, using a bound on the number of cuts of each size and the probability 2^-i that a cut of size i has no sampled edge.
  • Collision bound: O(α^2n) coordinates collide with probability at least 1 − exp(−Ω(α^3n)) when d = ⌈αn⌉ coordinates are sampled uniformly from [n].The collision count is bounded using a 2-Lipschitz function and McDiarmid’s inequality.

B.5 Proof of Theorem 4.2

The proof encodes coordinates into a weighted complete bipartite graph so that accurate perfect matchings reveal many coordinates, contradicting differential privacy.

  • Theorem application: The MWPM lower bound applies for ε > 0, δ ≤ (n/m)^Ω(1), and m > 2n under the ℓ1 neighboring relation.The theorem asserts the existence of a topology and weight distribution for which every private protocol incurs the stated expected additive-error bound.
  • Encoding: The encoding assigns weight 0 to each coordinate’s represented value and weight R to its other incident edges in a complete bipartite graph.The first d = αn vertices on one side represent coordinates, while the opposite side represents possible values.
  • Encoding: Θ(n) non-colliding coordinates remain recoverable from correct matching edges, despite collisions affecting the optimum.The collision count can be made arbitrarily small with exponentially small failure probability.
  • Reconstruction argument: An accurate MWPM would recover at least αn(0.99 − α) encoded coordinates in expectation.Assuming expected additive error below 0.01αnR, the decoding Hamming distance is at most 0.01αn + α^2n in expectation.
  • Theorem application: The proof extends the reconstruction contradiction to an edge-dependent bound using the same decomposition technique as the MST argument.The decomposition is simplified because the matching construction does not require connecting subgraphs.

B.6 Proof of Lemma 5.4

The proof bounds connected-component sizes in an independently sampled subgraph using stochastic domination of a BFS exploration, then constructs a low-cost Dasgupta clustering from those components.

  • Component-size bound: Stochastic domination is established through a monotone coupling between the actual exploration process and the binomial process.The proof uses the equivalence between stochastic domination and the existence of a monotone coupling.
  • Component-size bound: The BFS frontier is dominated by a process with binomial offspring, because ignoring explored-cycle edges can only increase newly discovered vertices.The coupling establishes that the dominating process provides a valid upper bound on component growth.
  • Component-size bound: 2^(2−α) log n: with probability at least 1 − n^-3, no sampled component exceeds this size.The component-size bound follows from the largest-components lemma after choosing the BFS exploration horizon appropriately.
  • Dasgupta clustering: 2^(2−α) · 4n log(n)/α^2: a clustering tree exists with probability at least 1 − 2n^-3 and has Dasgupta cost at most this value.The construction decomposes cost over sampled-edge components and bounds each component’s contribution using its size and number of edges.
  • Dasgupta clustering: The sampled-edge count is bounded by n with probability at least 1 − exp(−Ω(n)), completing the high-probability cost bound.This event is combined with the component-size event by a union bound.

B.7 Proof of Lemmas 5.6 and 5.7

The proof analyzes two independent edge-sampling stages and applies binomial tail bounds to control balanced-cut edge counts with exponentially small failure probability.

  • Sampling decomposition: Conditioned on the first sampled edge set, each remaining edge is independently assigned to the complement or the second sampled set with probability p/2 each.The proof uses this conditional independence to characterize the second-stage cut counts as binomial variables.
  • Balanced-cut sampling: The number of second-stage sampled edges crossing a fixed balanced cut is binomial, enabling a Chernoff tail bound.The proof reduces the cut analysis to bounding a binomial random variable on the edges crossing the cut.
  • Balanced-cut sampling: 2n e^-n ≤ 2^-0.2n: after union bounding over all balanced cuts, the failure probability is exponentially small.The preceding tail bound is applied across all 2^n balanced cuts.

B.8 Proof of Theorem 6.1

The theorem analyzes independent Laplace noise on edge weights and bounds the resulting optimization error by controlling the maximum total noise over feasible solutions.

  • B.8 Proof of Theorem 6.1: Independent Laplace noise Ze ~ Lap(1/ε) is added to every edge, yielding an ε-DP mechanism under ℓ1 neighboring weights.The algorithm optimizes over the perturbed weights w′.
  • B.8 Proof of Theorem 6.1: The proof compares the noisy optimum with the original optimum and obtains w(T′) ≤ w(T∗) + 2M, where M is the maximum absolute total noise over feasible solutions.This comparison transfers concentration of the noise into an approximation guarantee.
  • B.8 Proof of Theorem 6.1: Bernstein concentration bounds each solution's sum of independent Laplace variables, after which a union bound controls all feasible solutions.The threshold is set to t = c·(k/ε) ln(m/k) so the tail is sufficiently small.
  • B.8 Proof of Theorem 6.1: O((k/ε) ln(m/k)) bounds the excess weight w(T′) − w(T∗) with probability at least 1 − n^−Ω(1).The bound follows from the theorem's high-probability control of the noisy optimization output.
Loading 2609.10877v1…