arXiv CSopen access

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

· arxiv_cs

arXiv CS · Papers · License: Open Access

cryptography cybersecurity privacy security

cryptography, security, privacy, cybersecurity

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks Jacob Imola University of Waterloo [email protected]

Rasmus Pagh BARC, University of Copenhagen [email protected]

arXiv:2609.10877v1 [cs.DS] 9 Sep 2026

Lukas Retschmeier BARC, University of Copenhagen [email protected] September 11, 2026

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, w) where the vertex set V and edges E are public and the weights w : E → 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 · 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 (ε, δ)-DP as long as δ ≤ (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 ℓ∞ 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.

Introduction

Graph-structured data is a fundamental abstraction in modern data management. Weighted graphs naturally arise, for example, from relational data describing transportation networks, communication infrastructure, recommendation systems, similarity relations, and interactions between entities. Many important analysis tasks on such data reduce to classical graph optimization problems, including computing sparse connectivity structures such as minimum spanning trees, assignment structures such as minimum-weight perfect matchings, and multiscale summaries such as hierarchi-

cal clusterings. These structures serve as compact summaries that support downstream tasks such as routing, indexing, similarity search, visualization, and unsupervised learning. In many applications, however, the edge weights encode sensitive aggregate information derived from individuals. For example, edge weights may represent traffic intensities collected from users, communication frequencies between populations, similarity scores derived from behavioral data, or compatibility measures computed from medical records. In such settings, a single individual may affect multiple edge weights simultaneously, but only by a small amount in each coordinate. This motivates studying differential privacy under an ℓ1 neighboring relation on edge weights, where neighboring weighted graphs differ by bounded total change in their edge-weight vectors [Sealfon, 2016]. Other researchers have applied this appealing privacy model to other graph problems, including hierarchical clustering [Deng et al., 2025] and all pairs shortest distances [Chen et al., 2023, Bodwin et al., 2024]. Examples. In a transportation network, an MST can represent a sparse backbone connecting cities or distribution centers using low-cost routes inferred from aggregate traffic data. Publishing such a structure enables routing, infrastructure planning, and resilience analysis while dramatically compressing the underlying weighted network. Similarly, in a recommendation or similarity graph, a hierarchical clustering, also known as a dendrogram, provides a navigable taxonomy of users, products, or documents derived from sensitive behavioral correlations. These structures often involve sensitive data, such as road traffic data or user browsing activity, and thus are good candidates for private data release. Problem Setting In this paper, we study the problems of Minimum Spanning Tree (MST), Minimum-Weight Perfect Matching (MWPM), and Hierarchical Clustering (HC) in the edge-weight model of differential privacy (DP), where the graph topology G = (V, E) with n vertices and m edges is publicly known, but the edge weights w ∈ Rm must be kept private. A randomized algorithm A must output a solution (e.g., a spanning tree, perfect matching, or dendrogram) of the known topology G that approximately minimizes a problem-specific cost function with respect to the private weights. The privacy constraint requires that the output distribution of A is similar for neighboring weight w, w′ vectors that are close in ℓ1 distance. We measure the expected error additively as the difference between the cost of a released solution and the optimum. We defer a formal introduction to Section 2.

1.1

Our Contributions

We derive two types of reconstruction-based lower bounds for approximate DP and the ℓ1 neighboring relationship. We first consider lower bounds on explicit worst-case topologies. For MST and MWPM, we provide lower bounds showing that the expected additive error must grow with a factor of Ω n · log( m ) n . These lower bounds work via a new reconstruction-attack setup using a dataset from a large domain where more information can be reconstructed compared to a binary dataset. This lifts the prior lower bound of Ω(n) by a logarithmic factor and tightly matches the upper bound obtained by the simple input perturbation algorithm that adds noise to each weight independently [NN, 2026, Sealfon, 2016]. The fact that input perturbation is an optimal approach for these problems is additional evidence that input perturbation is often a good approach to graph 2

optimization problems, as recently seen in Pagh et al. [2025]. Furthermore, the fact that this upper bound under pure differential privacy (δ = 0) can be matched by lower bounds shown under approximate differential privacy (with polynomially small δ) is somewhat surprising given the polynomial √ separation by a factor of O( n) between pure and approximate differential privacy for Minimum Spanning Tree under the ℓ∞ neighboring relation [Pagh et al., 2025]. The lower bounds in the previous paragraph, and indeed many other lower bounds in edge-weight DP, use worst-case topologies that are not always realistic in a real-world setting. For example, the lower bounds for MST (with δ > 0) and HC use a doubly-connected star graph or the complete graph as their worst-case topology, respectively (see Figure 1), leaving it open whether better performance is possible on sparser or more realistic topologies. Our second type of lower bounds show that it is not possible to achieve much better performance for large classes of sparse topologies. For MST, we show that any topology with minimum cut at least Ω log(n) must incur error Ω(n), differing from the lower bound of the worst-case topology by a log( m n ) factor. This complements a lower bound of Hladı́k and Tětek [2025] which establishes that the error must grow linearly with the diameter of the topology but holds for pure DP only. For HC under Dasgupta’s cost function [Dasgupta, 2016], we obtain a fully-parameterized lower bound that grows with the expansion (in the sense of expander graphs), and decreases with the maximum degree of the graph. For constant-degree regular expander graphs, our lower bound is Ω(n2 ), which matches the state-of-the-art lower bound of Deng et al. [2025], Imola et al. [2023] but generalizes it to approximate DP and beyond the complete graph. A summary of all our new results together with known bounds appears in Figure 1. Note that the error bounds depend only on graph parameters, so the error is independent of the weight (or cost) of a solution. Thus these problems can be solved privately with good error bounds whenever the weight (or cost) of an optimal solution is sufficiently large compared to the error bound. Techniques Our lower bounds work via reconstruction attacks, where a private dataset is encoded into the weights of the graph topology, and based on the solution to the graph problem, a decoding process attempts to reconstruct the dataset. If the error of the graph algorithm is low enough, we show that the reconstruction will be successful, contradicting DP. We introduce several new techniques in designing these reconstruction attacks. For our lower bounds on worst-case topologies, our sharper bounds come from encoding a dataset in [m/n]n rather than a binary dataset, which allows for more information to be reconstructed. To do this, we need to use a new encoding scheme on a dense topology. For Minimum Spanning Tree, we use a complete bipartite graph whose left vertices represent coordinates and whose right vertices represent possible values, assigning low weight to the edge connecting each coordinate i to its value xi . Thus, a sufficiently accurate spanning tree reveals the value of many coordinates, contradicting the reconstruction guarantees imposed by differential privacy. Using the same construction again for Minimum-Weight Perfect Matching, we note that a perfect matching can not encode the same value multiple times. Therefore, we draw a connection to the classic balls-into-bins problem showing that a large fraction of the dataset is collision-free with high probability. It turns out to be sufficient to run the reconstruction attack on this non-colliding subset of the random dataset. As recently observed by NN [2026] the known lower bounds for MST and MWPM are matched by Sealfon’s input perturbation algorithms that simply add Laplace noise to each edge weight and run 3

Problem

Error Bound

Reference

Graph type

Parameters

O(n · log n) O(n · log(m/n)) Ω(n) Ω(D) Ω(n · log(m/n)) Ω(n)

Sealfon [2016] NN [2026] Sealfon [2016] Hladı́k and Tětek [2025] Theorem 3.1 Corollary 3.4

Any Any Multi-edge star graph Diameter D Worst-case Min-cut ≥ 5 log(n)

δ=0 δ=0 δ < cε δ=0 δ < (n/m)Ω(1) δ < cmε

MWPM

O(n · log n) O(n · log(m/n)) Ω(n) Ω(n · log(m/n))

Sealfon [2016] NN [2026] Sealfon [2016] Theorem 4.2

Any Any Collection of 4-cycles Worst-case

δ=0 δ=0 δ < cε δ < (n/m)Ω(1)

O(n2 log n) Ω(n2 ) Ω(n2 )

Imola et al. [2023] Deng et al. [2025] Theorem 5.2

Any Complete graph Degree-O(1) pander

MST

ex-

δ=0 δ=0 δ < cmε

Figure 1: Upper and lower bounds for the error of differentially private graph optimization problems: MST, MWPM, and HC under the ℓ1 neighboring relationship parameterized by the number of vertices n and edges m. Upper bounds hold for pure differential privacy (δ = 0), while lower bounds are for (ε, δ)-DP. All bounds omit a multiplicative factor 1/ε for readability; cε > 0 is a constant that depends only on ε. the non-private optimization algorithm as post-processing. For completeness, we include a simple proof of the improved bound of NN [2026]. Interestingly, our worst-case lower bound asymptotically matches this upper bound, even when parameterized by the number of vertices and edges. For our second type of lower bound, we focus on reconstructing binary datasets and encode them randomly into the edge weights of a given topology. This requires analyzing the behavior of the random weights using ideas from random graph theory. At a high level, we need to establish that a low-cost optimal solution exists in the random weights, and that the decoding procedure will reveal many more 0-edges than 1-edges. For Minimum Spanning Tree, it is enough to assume that the topology has min-cut at least log(n); a union bound over all cuts in the graph will then ensure that a MST of weight 0 exists. Then, a simple decoding procedure where the algorithm guesses all data points in the tree have weight 0 is an effective reconstruction attack. For Hierarchical Clustering, we have to further subsample the edges at a rate of d1 from the topology (assuming the topology is d-regular) before encoding the dataset; this ensures that a low-cost clustering exists. Given a returned HC, the decoder guesses that all data points in edges crossing the top-most balanced cut (Lemma 5.1) of the HC are 0. This opens up an interesting challenge where it is possible that returned low-cost HC adversarially has few sampled 0-weight edges crossing its balanced cut, which would reveal too little information in the dataset. To circumvent this, we leverage the fact that the HC algorithm cannot distinguish between sampled 0-weight

edges and non-sampled edges, meaning that any tree it returns cannot adversarially avoid sampled edges, and it will reveal sufficiently many 0s in the dataset. Our lower bounds also use generalized reductions from differential privacy to reconstruction rates (Section 2), which may find more application in the edge weight setting. We note that the assumption on δ < (1/n)Ω(1) in our lower bounds is common in the privacy literature because, for example a mechanism that releases a uniformly drawn δ-fraction of the dataset would satisfy (0, δ)-DP. We refer to the discussion in Vadhan [2017]. Nevertheless, it remains an interesting open question to show tight bounds for larger values of δ.

1.2

Related Work

Graph optimization problems. Minimum Spanning Tree and Minimum-Weight Perfect Matching are classic graph optimization problems, with applications including tree-structured graphical models, synthetic data generation, and market or network matching. Hierarchical Clustering is an unsupervised learning technique that - unlike flat clustering methods such as kmeans - organizes data into clusters at multiple levels of granularity. The problem dates back more than half a century [Ward, 1963] and has applications across many domains, including network analysis [Leskovec et al., 2014], text analysis [Steinbach et al., 2000], and biology [Jardine and Sibson, 1968, Sneath, 2005, Diez et al., 2015, Eisen et al., 1998, Sotiriou et al., 2003]. Reconstruction attacks. Our lower-bound proofs are part of a long line of reconstruction attacks in differential privacy. The seminal work of Dinur and Nissim [2003] showed that answering too many queries too accurately can allow reconstruction of most of a private database. Subsequent work developed this connection into general lower-bound methods for private data release, including iterative constructions [Gupta et al., 2012], lower bounds based on reconstruction and fingerprinting ideas [De, 2012], and robust traceability arguments [Dwork et al., 2015]. In the graph setting, Sealfon [2016] and Eden et al. [2025] achieve lower bounds via reconstruction attacks; we improve on the results of Sealfon, while the latter result applies to a different privacy model. Private graph algorithms. Early graph-DP work studied edge-level statistics such as degree distributions [Hay et al., 2009], while node-DP was formalized and studied by Kasiviswanathan et al. [2013]. Under edge-level DP, Eliás et al. [2020] gave near-optimal algorithms for approximating cuts via synthetic graphs, and Liu et al. [2024] obtained optimal bounds for several other cut-related private graph approximation tasks. In a local version of edge-DP where each node releases its own perturbed view of the graph, Eden et al. [2025] studied triangle counting and used reconstructionstyle lower-bound techniques. Private matching in a different privacy model and objective has been studied in discrete allocation and graph models [Hsu et al., 2014, Dinitz et al., 2025]. These privacy models are distinct from the edge-weight model, and the techniques do not easily carry over. Edge-weight private graph optimization. The edge-weight model was introduced by Sealfon [2016], modeling the situation where graph structure is public but weights are sensitive. He studied differentially private release of approximate shortest paths and distances, and also gave algorithms and lower bounds for releasing Minimum Spanning Tree, Single-Source ShortestPath Trees, and Minimum-Weight Perfect Matching under the ℓ1 neighboring relation on

weights. A recent line of work has studied private release of all-pairs shortest-path distances under the ℓ1 neighboring relation, with lower bounds shown using discrepancy-based methods [Fan et al., 2022, Chen et al., 2023, Bodwin et al., 2024]. MST was studied under the ℓ∞ neighboring relation in Hladı́k and Tětek [2025] and Pagh et al. [2025], showing tight error bounds in pure and approximate DP settings, respectively. To our knowledge, Hladı́k and Tětek [2025] provide the only other topology-dependent lower bounds for edge-weight DP, showing the error of MST for the ℓ1 neighboring relation must grow with Ω(D), where D is the diameter of the topology. Their argument uses the packing technique, which restricts it to pure DP (δ = 0). Private hierarchical clustering. The non-private objective framework for hierarchical clustering was introduced by Dasgupta [2016] and recently won a STOC Test of Time Award [ACM SIGACT, 2026]. It was further developed by Cohen-Addad et al. [2019] and the differentially private version was first studied by Imola et al. [2023], who gave algorithms and proved a packingbased Ω(n2 /ε) additive-error lower bound for pure edge-DP. Deng et al. [2025] subsequently studied hierarchical clustering in the edge-weight model and showed that hard instances can be embedded into the weights of the complete graph, implying an Ω(n2 /ε) lower bound under pure DP. Our hierarchical-clustering lower bound follows the edge-weight line of Deng et al. [2025], but strengthens the picture by applying to approximate DP and to beyond the complete topology. They also derived an algorithm achieving Õ( 1ε ) multiplicative error for graphs in which every edge weight is at least 1; we do not compare with this algorithm as this assumption is too specialized for our purposes.

Preliminaries

P ′ For two vectors w, w′ ∈ Rm , we define the Hamming distance dH (w, w′ ) := m i=1 1[wi ̸= wi ] to ′ be the number of coordinates in which they differ. For sets S, S we extend the definition by the symmetric difference dH (S, S ′ ) := |S \ S ′ | + |S ′ \ S|. We write x ∼H x′ if dH (x, x′ ) ≤ 1. Graph Terminology We consider a finite, simple and undirected graph G = (V, E, w), where the set of n vertices V and the set of m edges E are public and the weight vector w = (w1 , · · · , wm ) ∈ Rm is private. We use w ∈ Rm and w : E → R interchangeably to denote the edge weights. We refer to F = (V, E) as the topology of G. Throughout the paper, we assume m > n and that F is connected. We denote by G (respectively Gω ) the family of all unweighted (weighted) graphs. WeightsPof Sets and Cuts For a subset of edges S ⊆ E of edges, we denote the weight as w(S) = e∈S Pwe . We refer to a partition A, B of V as a cut of G. The weight of the cut is given by w(A, B) := uv∈E∩(A×B) wuv . Similarly, for any edge set E ′ ⊆ E, we denote E ′ (A, B) = |{(u, v) ∈ E ′ : u ∈ A, v ∈ B}| to be the size of the cut, or the number of edges crossing between A, B. We refer to any cut A, B satisfying 31 n ≤ |A|, |B| ≤ 23 n as a balanced cut. Spanning Trees and Perfect Matchings A spanning tree is an acyclic subset T ⊆ E of size n−1 making the graph connected. A matching M ⊆ E is a set of pairwise vertex-disjoint edges, i.e., e∩e′ = ∅ for any two distinct e, e′ ∈ M . For a matching M and a subset S ⊆ V , we let S(M ) denote those vertices in S that are incident to an edge of M . A perfect matching is a matching that covers every vertex of V . We denote the set of all spanning trees and perfect matchings of G as S(G) and 6

P(G), respectively. A minimum spanning tree (MST) is a spanning tree T ∗ that minimizes w(T ) among all spanning trees T ∈ S(G); analogously, a minimum weight perfect matching (MWPM) is a perfect matching M ∗ ∈ P(G) that minimizes w(M ) among all M ∈ P(G). Hierarchical Clustering A hierarchical clustering (HC) for a graph G is represented by a rooted tree T whose leaves correspond to V , and where each internal node corresponds to the union of the leaves in its subtree. Traversing the tree from the root to the leaves corresponds to successively refining the clustering. In seminal work [Dasgupta, 2016], Dasgupta introduced a cost function costw (T ) evaluating the quality of a hierarchical clustering, setting the stage for optimization. Intuitively, it charges the total weight separated at each merge times the size of the subtree at that merge, encouraging less weight to cross higher merges. Formally, Definition 2.1 (Dasgupta [2016] Dasgupta’s cost objective). Given an input graph G = (V, E) together with weights w : E → R≥0 and a hierarchical clustering tree T , the Dasgupta cost function costw is given by X costw (T ) := |T [u ∨ v]| · w({u, v}) , (2.1) {u,v}∈E

where |T [u∨v]| denotes the number of leaves in the subtree induced by the lowest common ancestor of u and v in T . As noted by Dasgupta, we may assume without loss of generality that T is a rooted binary tree, because every non-binary hierarchical clustering tree can be transformed into a binary one without increasing costw (T ). We illustrate this cost function on a small example in Appendix A. Differential Privacy In this work, we consider edge-weight differential privacy Sealfon [2016], where the private information is encoded in the weights themselves. We say that two graphs G = (V, E, w) and G′ = (V ′ , E ′ , w′ ) are neighboring (denoted G ∼ G′ ) if V = V ′ , E = E ′ and ∥w − w′ ∥1 ≤ 1, i.e., their ℓ1 distance is at most one. Definition 2.2 (Dwork et al. [2006] (ε, δ)-Private Algorithm). Let ε ≥ 0 and δ ∈ [0, 1]. A mechanism A : Gω → Y is (ε, δ)-(edge-weight)-DP, if for every pair of neighboring graphs G ∼ G′ , and all measurable sets of outputs Y ⊆ Y, we have, P [A(G) ∈ Y ] ≤ eε P A(G′ ) ∈ Y + δ. (2.2) Importantly, F = (V, E) is a public topology, and privacy is with respect to the weights. Reconstruction Attacks. Our DP lower bounds will be shown via reconstruction attacks, which are algorithms that try to reconstruct the private dataset x based on the algorithm output. If the attack reconstructs coordinates of x, they demonstrate an impossibility for DP, and any reasonable notion of privacy (see Vadhan [2017] for an overview of reconstruction attacks). We will use two types of reconstruction attacks in our lower bounds. In the first type, we consider an algorithm that attempts to reconstruct a fixed coordinate i of x, and show that any DP algorithm cannot be too successful at doing so. This is a slight generalization of Sealfon [2016, Lemma 5.3] to general data domains X . 7

a) Minimum Spanning Tree

b) Minimum-Weight Perfect Matching

R 0

R li

l⌈αn⌉

... ...

rj ...

Figure 2: a) Encoding the vector x = (x1 , · · · , xn ) into the minimum-weight spanning tree. b) The encoding for min-weight perfect matching for a vector of length ⌈αn⌉. We pad the left side with the gray vertices. In both cases, each vertex rj represents the integer j, and we set the weight of the edge from li to rj to 0, if xi = j and otherwise to R = O( 1ε ln n). Lemma 2.3. Let B : X d → X d be any mechanism that is (ε, δ)-differentially private under the Hamming neighborhood relationship, i.e. dH (x, x′ ) ≤ 1 for neighboring datasets x ∼ x′ . Then a dataset x ← X d , drawn uniformly at random, we have for each i ∈ [d], we have P [B(x)i = xi ] ≤ exp(ε) |X | + δ. As we will see, using a data domain of size |X | = m n will be critical to obtaining tight lower bounds. We also consider reconstructing an entire set I ⊆ [d] of indices of a binary dataset x. An attack is then a mechanism B : {0, 1}d → 2[d] × {0, 1}d , and its success is measured by Succ(B) =

1 E [dH (x|I , y|I )] − , 2 E [|I|]

(2.3)

where x ∼ {0, 1}d and (I, y) := B(x), and x|I indicate the subvector of x on indices I. Intuitively, success is the normalized error that randomly guessing I would yield (namely 12 ) minus the normalized error made by B in the set I. DP limits the possible success as follows. Theorem 2.4. Let B : {0, 1}d → 2[d] × {0, 1}d be any (ε, δ)-DP algorithm and let x ∼ {0, 1}d be eε −1 dδ drawn uniformly at random. Then, Succ(B) ≤ 2(e ε +1) + eε +1 . The proof appears in Section B.2. It differs from prior reconstruction attacks because I is itself a differentially private output. When δ = o( d1 ), the second term becomes negligible, and when ε < 1, we have that Succ(B) = O(ε).

Private Minimum-Weight Spanning Trees

In Section 3.1, we show that there is a worst-case topology F on which the additive error of MST under DP is tight in Θ ((n/ε) · log(m/n)) (for small enough δ) achieved by the Laplace mechanism. Going beyond worst-case graphs, in Section 3.2, we show that the lower bound of Ω(n/ε) due to Sealfon [2016] holds on all graph topologies with minimum cut Ω(log(n).

3.1

Tight Lower Bounds on Worst-Case Topologies

Assuming δ ≤ (n/m)Ω(1) , we now close the gaps between the known upper and the lower bounds. The idea is to encode a random vector x ∈ [m/n]d into the MST of a dense graph G so that releasing an overly accurate MST by a differentially private mechanism would contradict the reconstruction rate in Lemma 2.3. As a by-product, we also get a lower bound for ε-DP, obtained by taking the limit of δ towards 0 recovering the packing-based lower bound obtained by Hladı́k and Tětek [2025]. Theorem 3.1 (Worst-Case Lower Bound MST). Let ε > 0 and δ ≤ (n/m)Ω(1) where m > 2n. There exists a graph topology F = (V, E) and a distribution Dω of weights such that for any (ε, δ)DP algorithm A that outputs an approximate MST T under the ℓ1 neighboring relationship, if the weights w ∼ Dω then the expected additive error satisfies w(T ) − w(T ∗ ) ≥ Ω (n/ε) · min(ln(1/δ), ln(m/n)) , where T ∗ is the optimal MST. We will start with the case m = n2 , and focus on the general case later. The full encoding scheme appears in Figure 2. Throughout the construction, we assume the topology F ∈ G to be public. Encoding Let EncR : [n]n → Gω be the encoding function that takes some dataset x ∈ [n]n and returns a weighted graph that encodes the dataset into the MST. The parameter R > 1 is used to control the edge weights. We construct a new connected graph G = (V1 ∪ V2 , E, w) with 2n vertices and n2 + (n − 1) edges in the following way: Let V1 = {ℓ1 , · · · ℓn } and V2 = {r1 , · · · , rn } be two vertex sets each of size n. Each one coordinate of x and has edges to vertex ℓi ∈ V1 represents each vertex in V2 . Set w {ℓi , rxi } := 0 and w {ℓi , rj } := R for j ̸= xi . We ensure connectivity by adding a path through the vertices in V2 with zero weighted edges (contributing the n − 1 extra edges). Decoding Let DecG : S(G) → [n]n be a decoder and assume that the topology G was produced by the encoder (to simplify notation we assume F is public as soon as the instance has been created). Given a spanning tree T ∈ S(G), we reconstruct the vector y ∈ [n]n as follows: for each i ∈ [n], choose any rj ∈ V2 with {ℓi , rj } ∈ T and set yi := j. Note that any vertex in V1 must have at least one edge in T by construction, and therefore, the reconstruction for each coordinate is well-defined. In case there are multiple, we break ties arbitrarily. Now define the attack Rec : [n]n → [n]n as RecAMST ,R (x) := DecG AMST (EncR (x)) where AMST is any (possibly randomized) MST algorithm. By the construction above, it is clear that an optimal MST algorithm AOPT recovers all coordinates perfectly, i.e. RecAOPT ,R (x) = x. This leads to the following two observations. Observation 1. Let R > 0 and G = (F, w) be obtained from EncR (x). If T ∈ S(F ) is any and T ∗ the optimal spanning tree of G, then dH (DecF (T ), x) ≤

w(T ) − w(T ∗ ) w(T ) = , R R

Indeed, w(T ∗ ) = 0, and whenever DecF (T )i ̸= xi , the tree T contains an edge {li , rj } with (j ̸= xi ), which has weight R. These bad edges are distinct for different i, so the number of decoding errors is at most w(T )/R. Observation 2 (Induced ℓ1 ). For every x ∼H x′ and R > 0, setting k := 2⌈R⌉, there is a chain of ℓ1 -neighboring graphs, i.e. EncR (x) := G0 ∼1 G1 ∼1 · · · ∼1 Gk =: EncR (x′ ). Each consecutive Gi is obtained by successively changing a single weight by one. By group privacy (see e.g. [Vadhan, 2017, Lemma 7.2.2]), this means there is a (2⌈R⌉ε, 2⌈R⌉e2⌈R⌉ε δ)-DP guarantee on EncR (x) under the Hamming neighboring relationship. We are now ready to prove Theorem 3.1. Proof of Theorem 3.1. Suppose for contradiction, that there exists an (ε, δ)-DP MST algorithm n AMST with expected additive error less than 100 · R. Assume a random dataset x ∼ Uni([n]n ). Note that the decoding step is simply post-processing,and hence Rec AMST ,R parameterized by AMST

and R is (2⌈R⌉ε, 2⌈R⌉e2⌈R⌉ε δ)-DP. Now set R := min

ln n ln(1/δ) 2cε , 2cε

for some c > 1. Combining with

99 Observation 1 and by the utility guarantee of AMST , we would leak at least 100 · n of the input coordinates in expectation. Let y := RecAMST ,R (x) and by Lemma 2.3,

e2⌈R⌉ε + 2⌈R⌉e2⌈R⌉ε δ n ln(n) 1 ≤ exp ln(n1/c ) + exp ln n1/c δ n εc ln(n) 1/c (1−c)/c =n + n δ. εc

P [yi = xi ] ≤

By our assumption on δ = n−Ω(1) , the second term vanishes. Linearity of expectation gives   X E (1 [yi = xi ]) ≤ n · n(1−c)/c = n1/c . i∈[n]

In particular, for a sufficiently large constant c, we contradict the utility guarantee of AMST . Note n also that we require R ≤ ln 2cε to get any meaningful probability. Thus, we have shown a lower bound of Ω((n/ε) ln n) in the dense case (m = Θ(n2 )), for sufficiently small δ. It remains to show that this technique can be parameterized by the number of edges m to yield a bound of Ω((n/ε) · ln(m/n)) for any 2n ≤ m ≤ n2 . Suppose, we want a lower bound for graphs with m edges and 2n vertices. Without loss of generality, we treat m/n as an integer. We can build n2 /m many subgraphs on 2(m/n) vertices (constructed as described above for the dense case with n replaced by m/n). To make the full graph connected, we add a path through one representative vertex from each subgraph, adding only O(n2 /m) low-cost edges that would only affect the bound by a constant. Ignoring this lower-order term, observe that the number of edges is exactly (m/n)2 · (n2 /m) = m (we ignore edges on the path of length ≤ n). For i ∈ n2 /m, let each subgraph encode an i.i.d. random vector x(i) ∈ [m/n]m/n of length m/n. Since an (ε, δ)-DP algorithm satisfies the same privacy guarantees on the weights of each individual 10

Algorithm 1 Subset Reconstruction Attack RecMST for MST Require: Public graph topology F = (V, E), dataset x ∈ {0, 1}m , parameter R > 0, algorithm AMST . m 1: Initialize weights w ∈ {0, R} . 2: Let ℓ : E → [m] be any bijection from E to [m] labels. 3: Set w(e) := Rxℓ(e) for all e ∈ E. ▷ Encode the dataset into the weights 4: Let G = (F, w). 5: Compute minimum spanning tree T := AMST (G). 6: Initialize reconstruction set I = {ℓ(e) : e ∈ T } ⊆ [m]. 7: for each i ∈ I, guess yi = 0. 8: return Reconstruction set I, reconstructed vector y = {yi : i ∈ I}.

subgraph, the previous lower bound applied to a single subgraph states that we cannot reconstruct m a single x(k) with expected error better than Ω( nε · ln m n ). By linearity of expectation, we get a 2 m m lower bound on the expected total error of Ω( nε · ln n ) · nm = Ω nε · ln( m n) .

3.2

Lower Bounds for General Topology Classes

We will design a subset reconstruction attack that uses any given approxmate DP MST algorithm AMST . Assuming the additive cost of AMST is sufficiently low, the reconstruction success will be high enough to form a contradiction with Theorem 2.4 and establish an error lower bound for any DP algorithm. Our reconstruction attack works as follows: the dataset is drawn from x ∼ Uni({0, 1}m ), and then arbitrarily encoded into E with a labeling function ℓ : E → [m]. The weights are set as w(e) = Rxℓ(e) , where R is a factor used to amplify the weight that we will choose later. Then, AMST is run on (V, E, w) to produce a tree T ⊆ E. The returned tree T contains edges whose weight is more likely to be 0, and thus the reconstructed set is set to be I = {ℓ(e) : e ∈ T }, and all guesses {yi : i ∈ I} are yi = 0. This procedure appears in Algorithm 1. We will show that if AMST has sufficiently low additivePerror, then this attack has a success By construction, rate muchP higher than 0. Specifically, we will show E[ i∈I xi ] ≤ 0.1 E[|I|]. P w(T ) = R i∈I xi . Using the additive error guarantee of AMST , we have E[ i∈I xi ] = R1 E[w(T )] ≤ 1 1 ∗ R w(T ) + 10 n. Thus, we need to show that the optimal MST in (V, E, w) is likely to have low weight. This is where we assume that the minimum cut of F is not too small. Recall that the minimum cut is given by minA⊔B=V E(A, B). We use a concentration inequality, and a union bound over all cuts, to argue that if the mincut of F is at least 5 log n, then with high probability all cuts have an edge labeled 0. This immediately implies that an MST of weight 0 exists. In order for the union bound to work, we use a result of Karger [1993] bounding the number of approximate minimum cuts, as these cuts have higher failure probability. Formally, Lemma 3.2. Suppose the graph topology F = (V, E) has minimum cut λ ≥ 5 log(n), and the random dataset x ∼ Uni({0, 1}m ) is embedded into w via an arbitrary bijection. Then, with probability at least 1 − n32 , there exists a zero-cost spanning tree T ⊆ E, i.e. w(T ) = 0.

The proof appears in Section B.3. Note that E[|I|] = |I| = n − 1 always. Having established bounds P on both E[ i∈I xi ] and E[|I|], we can show a reconstruction attack lower bound: Theorem 3.3. Let (V, E) be a public graph topology with minimum cut at least 5 log(n). Suppose R that AMST attains expected additive error ≤ 10 n for some R > 0. Then Succ(RecMST ) ≥ 0.4. Proof. Let E denote the event that the optimal MST has weight that is not 0. We have that " # " # " # " # X X X X E 1[xi ̸= yi ] = E xi ≤ E xi ¬E + P [E] E xi E i∈I

i∈I

≤E

" X

i∈I

# xi ¬E + P [E] · n · R.

i∈I

P By Lemma 3.2, we know P [E] ≤ n32 . Furthermore, by the construction of I, we know R i∈I xi = R w(T ). Given that ¬E occurs, we have E[w(T )] ≤ 10 n by the error guarantee of AMST . Thus, the n R above bound is 10 + O n . Theorem 3.3 and Lemma 2.4 immediately imply the following corollary: Corollary 3.4. For any topology F = (V, E) with minimum cut at least 5 log(n), there is no 1 (ε, δ)-DP algorithm AMST attaining 10ε n additive error for any ε ≤ 1, δ ≤ 0.01ε m . Proof. Suppose the contrary, and instantiate RecMST with AMST and R = 1ε . By group privacy, RecMST satisfies (ε⌈R⌉, δ⌈R⌉eε⌈R⌉ )-DP, which means it satisfies (2, 10 ε δ)-DP as ε⌈R⌉ < 2. 1 1 By Lemma 2.4, this means it can only be a 2 − 1+e2 + mδ < 0.39-successful reconstruction attack, yet this contradicts Theorem 3.3. While looser than Theorem 3.1 by a log( m n ) factor, this result establishes that the error of MST must still grow linearly under (ε, δ)-DP for many topologies. We note that this proof would still work if F had any linear-sized subgraph with large enough min-cut.

Minimum-Weight Perfect Matchings

As any perfect matching has size n/2, the upper bound in Theorem 6.1 immediately carries over to Minimum-Weight Perfect Matching as well. We now show that the resulting additive error m of Θ (n/ε) · ln n is tight for this problem as well (for sufficiently small δ). The encoding will be slightly different for MST because all coordinates with the same value would be encoded by the same vertex, and a matching can only recover one of those. To fix this, we prove a standard balls and bins result stating that if x has length n′ = αn for some small 0 < α ≤ 1, only a α2 fraction of a random x ∼ Uni([n]⌈αn⌉ ) has collisions with high probability. Lemma 4.1 (Collision-free). Let (X1 , . . . , Xd ) ∼ Uni [n]d with d = ⌈αn⌉ for a constant 0 < α ≤ 1. Then, with probability at least 1 − exp(−Ω(α3 n)), the number of indices i for which there exists some j ̸= i with Xi = Xj is O(α2 n).

Pd Proof. Define X̃ = 1 [∃ j = ̸ i : X = X ] and let Y = i j i i=1 X̃i . By a union bound, E[X̃i ] ≤ P 2 2 j̸=i P [Xj = Xi ] = (d − 1)/n, so that E[Y ] ≤ d(d − 1)/n = α n − α ≤ α n. Since changing a single Xi affects at most two of the X̃i ’s, Y is 2-Lipschitz. By McDiarmid’s inequality [McDiarmid, 1989], for any t > 0, P [Y ≥ E[Y ] + t] ≤ exp(−2t2 /(4d)). Setting t = E[Y ] gives P [Y ≥ 2E[Y ]] ≤ exp(−E[Y ]2 /(2d)) = exp(−Ω(α3 n)). Thus, with probability at least 1 − exp(−Ω(α3 n)), we have Y ≤ 2E[Y ] = O(α2 n). Theorem 4.2 (Lower bound MWPM). Let ε > 0, δ ≤ (n/m)Ω(1) , and m > 2n. Then there exists a graph topology F = (V, E) and a distribution of weights Dω on weights of E such that for any (ε, δ)-DP protocol B that outputs an approximate minimum-weight perfect matching M under the ℓ1 neighboring relationship, if the weights w ∼ Dω , then the expected additive error satisfies w(M ) − w(M ∗ ) ≥ Ω((n/ε) · min(ln(1/δ), ln(m/n))) , where M ∗ is an optimal minimum-weight perfect matching. Proof sketch. Using a similar encoding and observation as before, we can show that for some suitable constant 0 < α < 1, for some an encoded random vector x ∈ R⌈αn⌉ , at least αn(0.99−α) coordinates could be reconstructed in expectation. This stands in contradiction with an allowed additive error of ≤ αn−Ω(1) imposed by Lemma 2.3 for δ ≤ n−Ω(1) . Finally, the same generalization technique to m edges works here again. Find the full proof in Section B.5.

Hierarchical Clustering under Dasgupta’s Cost Function

In this section, we design the first reconstruction-attack based lower bound for hierarchical clustering. Observe that our approach for MST, where the dataset is encoded into every edge of the topology, does not work here. This is because, by a simple concentration argument, every cut in the graph will have weight approximately half the total size of the cut, preventing any cheap hierarchical clustering from existing. Instead, we use a sparse dataset encoding, which requires new technical ideas. Before describing the attack, we introduce new graph notation. For a topology F = (V, E), let dmax (F ) denote the maximum degree vertex in F . Also, let ϕ(F ) denote the minimum-size balanced cut in F ; i.e. ϕ(F ) = minA,B balanced cut |E(A, B)| where |E(A, B)| denotes the number of edges crossing the cut. For any n and d ≥ 3, there exist spectral expander graphs where every node has degree d and ϕ(F ) ≥ Ω(nd) [Vadhan, 2012]. These are the graphs where our bounds will be tightest. To ensure the existence of a low-cost hierarchical clustering, we will encode a random dataset into a random sparse subset, where each edge is sampled with probability ≤ 1/dmax (F ). After privately computing the hierarchical clustering, we use the induced balanced-cut (Lemma 5.1) to try to reconstruct edges carrying encoded data that crossPthis cut; these edges will form the set I. The error guarantee is sufficient to establish that E[ i∈I xi ] is low. However, because the encoding is now sparse, it becomes harder to argue that E [|I|] is sufficiently large; i.e. that there are sufficiently many sampled edges crossing the cut which carry a 0. In principle, a low-weight hierarchical clustering could also avoid many sampled edges and drive |I| low. 13

Algorithm 2 Reconstruction Attack RecHC for Hierarchical Clustering Require: Public graph topology F = (V, E), dataset x ∈ {0, 1}m , parameter R, HC algorithm AHC 1: Initialize weight function w : E → {0, R}. 2: Subsample E ′ ⊆ E by selecting each edge from E with p = d0.5 . Let k = |E ′ |. max 3: Let ℓ : E ′ → [k] be any bijection from E ′ to [k] labels. 4: Set w(e) := R · xℓ(e) for all e ∈ E ′ and w(e) := 0 for all e ∈ E \ E ′ . ▷ Encode x into the weights 5: Compute hierarchical clustering T := AHC (F, w) . 6: Compute induced balanced cut (A, B) := HCToBC(T ). ▷ See Lemma 5.1 7: Initialize reconstruction set I = {ℓ(e) : e ∈ E ′ (A, B)} ⊆ [n]. 8: for each i ∈ I, guess yi = 0. 9: return Reconstruction set I, reconstructed vector y = {yi : i ∈ I}.

To circumvent this, we make the observation that the clustering algorithm cannot distinguish sampled vs. non-sampled edges among the edges of weight 0, and thus the number of sampled edges in the cut carrying 0 is not much lower than its expectation by another concentration argument. ϕ(F ) This enables us to prove a lower bound of Ω εdmax (F ) n that grows with the minimum balanced cut size. Somewhat counterintuitively, the lower bound shrinks, rather than grows, with the maximum degree, which is a byproduct of our sparse encoding. Nonetheless, this bound applies to many topologies, and is tight up to a logarithmic factor for sparse expanders (see discussion in Section 5.2).

5.1

Reconstruction Attack Outline

Our reconstruction attack encodes the dataset into a random subsample of edges E ′ ⊆ E, where 0.5 each edge e ∈ E is selected i.i.d. with probability p = dmax (F ) . The dataset is encoded by taking ′ an arbitrary bijection ℓ : E → [k] (a label function) where k = |E ′ |, and setting w(e) := R · xℓ(e) for all e ∈ E ′ , and w(e) := 0 for all e ∈ E \ E ′ . This sparse encoding ensures that there is a lowcost hierarchical clustering. Our reconstruction attack will not use the entire returned hierarchical clustering T to reconstruct data. Instead, it will use only the edges in the induced balanced cut of T , which is defined in the following lemma from Dasgupta [2016]. Their proof is constructive and forms the balanced cut with a procedure similar to a heavy-light decomposition. We refer to the balanced cut guaranteed by Lemma 5.1 as the induced balanced cut of T . Lemma 5.1 ([Dasgupta, 2016, Lemma 11]). For any hierarchical clustering T , there exists a w(A,B) 27 balanced cut A, B with |A|, |B| ∈ ( n3 , 2n 3 ) such that |A|·|B| ≤ 4n3 · costw (T ). Moreover, there exists a procedure HCtoBC(T ) which outputs the cut in linear time. The attack proceeds by running a hierarchical clustering algorithm AHC on the graph (V, E, w), obtaining a low-cost hierarchical clustering T , and computing the balanced cut A, B of T (which, by Lemma 5.1, is also guaranteed to have low cost). Then, it uses the reconstruction set I = {ℓ(e) : e ∈ E ′ (A, B)} (i.e. those data elements which are encoded to edges that cross A, B), and guesses yi = 0 for every i ∈ I. This reconstruction procedure, RecHC , appears in Algorithm 2.

An important observation for our analysis is the following: The edges e ∈ E ′ such that xℓ(e) = 0 appear the same as the edges e ∈ E \ E ′ in the weight function (both appear as 0), and thus the returned tree T gives us no further information to which of these two sets an edge of weight 0 belongs. Formally, define E0′ = {e ∈ E ′ : xℓ(e) = 0} and {E1′ = {e ∈ E ′ : xℓ(e) = 1}. The observation can be stated as: Observation 3. In Algorithm 2, the tree T , and subsequent post-processing of it, are conditionally independent of E0′ given E1′ . We will use this observation to show that there are many edges in E0′ (A, B), just due to the randomness of E ′ , and thus I will be sufficiently large.

5.2

Reconstruction Attack Lower Bound

We will now prove the following reconstruction attack. Theorem 5.2 (Lower Bounds HC). Let F = (V, E) be a public graph topology such that dmax (F ) ≥ 8, and ϕ(F ) ≥ max{8n, 10000dmax (F ) log n}. Suppose HC is a hierarchical clustering algorithm with nϕ(F ) additive error ≤ R· 400d for some R > 0. Then, Succ(RecHC ) ≥ 0.4. Furthermore, the expected max (F ) ϕ(F ) size of the reconstructed set is at least 8dmax (F ) .

This yields the following immediate corollary whose proof is identical to Corollary 3.4: Corollary 5.3. Let F = (V, E) be a public graph topology satisfying the conditions of Theorem 5.2. Then, for any ε ≤ 1, δ ≤ 0.01ε m , there is no (ε, δ)-DP algorithm for hierarchical clustering with error nϕ(F ) . less than 400εd max (F )

Corollary 5.3 is tightest when F is a d-regular spectral expander graph where ϕ(F ) ≥ Ω(nd). In 2 this case, the lower bound of Ω nε is the same as that in Deng et al. [2025] (for the complete graph only) and is tight with the upper bound in Imola et al. [2023] up to log(n) factors. Observe that our lower bound argument can be applied to any subgraph of F by just ignoring edges and vertices, and thus it is possible to remove a small number of high-degree nodes and derive a stronger lower bound on a subgraph. We now prove Theorem 5.2 and therefore need some supporting lemmas. First, we will show the optimal cost of clustering the encoded graph is just O(n · log(n)) with high probability. This comes from the fact that the components in E ′ w.h.p. will have size O(log(n)). Lemma 5.4 (Existence of a good Dasgupta cluster). Suppose F = (V, E) is a graph and let 1−α α ∈ (0, 1) be a constant. Now, assign weights w(e) := 1 with probability dmax (F ) and w(e) := 0 otherwise for each edge e ∈ E independently. Then with probability at least 1 − 2n−3 , there exists a clustering tree T , such that costw (T ) ≤ 2−α · 4n log(n). α2

The in Appendix B.6. The number of mistakes made in the set I is given by P proof appears ′ i∈I xi = |E1 (A, B)|. We use the previous bound on the optimal clustering cost to convert the additive error of HC into an absolute bound on |E1′ (A, B)|. Lemma 5.5. Suppose Algorithm 2 is instantiated with an algorithm AHC with expected additive error at most CF Rn for a constant CF (that may depend on n, F ). Then, the balanced cut (A, B) returned by HCToBC(T ) has expected size E[|E1′ (A, B)|] ≤ 2CF + 50 log(n). Proof. By the additive error guarantee of HC, we have for fixed weights w, E [costw (T )|w] ≤ costw (T ∗ ) + CF Rn. Recall that R > 0 is the weight, that we put on the subsampled edges that encode an one of the dataset. Note that in Algorithm 2, we use α = 0.5 and then 2−α = 6. By α2 −3 Lemma 5.4, with probability at least 1 − 2n , we have that w has an optimal clustering cost of (6 · 4) · Rn log n. In the worst case, the cost of clustering a complete graph is n3 R. Thus, we can use conditional expectation to show E [costw (T )] ≤ 24n log(n) + 2n−3 n3 R + CF Rn ≤ 25Rn log(n) + CF Rn. Furthermore, by Lemma 5.1, the balanced cut A, B satisfies w(A, B) ≤

27 27 |A||B|costw (T ) ≤ costw (T ) , 3 4n 16n

n because |A||B| maximizes in the interval ( n3 , 2n 3 ) exactly if both have size exactly 2 . The last step is to observe that w(A, B) = R · |E1′ (A, B)| due to the way the data is embedded. Hence, we get the following in expectation,

27 27 R · E E1′ (A, B) = E [w(A, B)] ≤ E [costw (T )] ≤ (CF Rn + 25Rn log n) 16n 16n ≤ R(2CF + 50 log n). Dividing by R yields the result. Next, we need to show that |I| is sufficiently large, as this will show that I is a successful reconstruction set. As |I| = |E0′ (A, B)| + |E1′ (A, B)|, and we have already upper bounded |E1′ (A, B)|, we will lower bound |E0′ (A, B)|. Precisely, we lower bound E [|E0′ (A, B)||E1′ ] since conditioning on E1′ allows us to consider A, B as a constant per Observation 3. Under this conditioning, the edges in E0′ are distributed multinomially, allowing us to do a straightforward Chernoff bound. Find the proof for the Lemmas 5.6 and 5.7 in Section B.7. Lemma 5.6. Suppose x and E ′ are sampled as they are in Algorithm 2. Then, for any balanced cut A0 , B0 , we have that E [|E0′ (A0 , B0 )||E1′ ] ≥ p2 |Ẽ(A0 , B0 )| where Ẽ = E \ E1′ . The prior bound of |Ẽ(A0 , B0 )| is not completely independent of E1′ ; the following result shows it is almost always bigger than 23 |E(A0 , B0 )|, giving us a simple bound to work with. Lemma 5.7. Suppose dmax ≥ 8 and ϕ(F ) ≥ 8n. With probability 1 − 2−0.2n , for all balanced cuts A0 , B0 , we have |E1′ (A0 , B0 )| ≤ 13 |E(A0 , B0 )|. We are now ready to put it all together and prove our main reconstruction lower bound for HC.

Theorem 5.2 (Lower Bounds HC). Let F = (V, E) be a public graph topology such that dmax (F ) ≥ 8, and ϕ(F ) ≥ max{8n, 10000dmax (F ) log n}. Suppose HC is a hierarchical clustering algorithm with nϕ(F ) additive error ≤ R· 400d for some R > 0. Then, Succ(RecHC ) ≥ 0.4. Furthermore, the expected max (F ) ϕ(F ) size of the reconstructed set is at least 8dmax (F ) .

P Proof. Observe that, based on the construction of the set I and y, we have i∈I 1[xi ̸= yi ] = ′ ′ ′ ′ E1′ (A, B) and |I| P = E1 (A, B)+ E0 (A, B). We will prove that 9 E[E1 (A, B)] ≤ E[E0 (A, B)], as this implies E i∈I 1[xi ̸= yi ] ≤ 0.1E [|I|], meaning the attack is 0.4 successful. Because HC has ) ϕ(F )R + 50 log(n). By additive error 400dmax (F ) n, by Lemma 5.5, we have E[|E1′ (A, B)|] ≤ 200dϕ(F max (F ) ) ) assumption, we know that 50 log(n) ≤ 200dϕ(F , and so E[|E1′ (A, B)|] ≤ 100dϕ(F . By the law of max (F ) max (F ) ′ ′ ′ total expectation, we have E[|E0 (A, B)|] = E[E[|E0 (A, B)||E1 ]]. We can bound the inner quantity, E[ E0′ (A, B) |E1′ ] = EA,B E |E0′ (A, B)| A, B, E1′ E |E0′ (A0 , B0 )| A = A0 , B = B0 , E1′ ≥ min A0 ,B0 balanced cut = min E |E0′ (A0 , B0 )| E1′ (by Observation 3) A0 ,B0 balanced cut

≥

p min |(E \ E1′ )(A0 , B0 )|. 2 A0 ,B0 balanced cut

(by Lemma 5.6).

Now, we will expand the whole expectation. In the following, let E be the event in Lemma 5.7; i.e. that for all balanced cuts A0 , B0 , we have |E1′ (A0 , B0 )| ≤ 31 |E(A0 , B0 )|. p ′ ′ E[ E0 (A, B) ] ≥ E min |(E \ E1 )(A0 , B0 )| 2 A0 ,B0 balanced cut p ′ ≥ P [E] E min |(E \ E1 )(A0 , B0 )| E 2 A0 ,B0 balanced cut 2 −0.2n p ≥ (1 − 2 ) E min |E(A0 , B0 )| E (by Lemma 5.7) A0 ,B0 balanced cut 3 2 p ϕ(F ) > ϕ(G) = . 4 8dmax ) ϕ(F ) ′ Putting it all together, recalling that E[|E1′ (A, B)|] ≤ 100 ϕ(F dmax (F ) and E[|E0 (A, B)|] > 8 dmax (F ) , we ) ) obtain 9 E[|E1′ (A, B)|] ≤ 1009dϕ(F < 8 dϕ(F < E[|E0′ (A, B)|]. max (F ) max (F )

Private Algorithms with Tight Error

We now detail algorithms with superior error on MST and MWPM that appear in ongoing work [NN, 2026] demonstrating that the lower bounds of Sections 3.1 and 4 are tight. The algorithm is a simple input privatization, adding Laplace noise to each of the edge weights independently. The novelty lies in the analysis: instead of bounding the maximum noise added to individual edge weights as in prior work [Sealfon, 2016, Hladı́k and Tětek, 2025, Pagh et al., 2025], it uses a concentration bound on the total noise of any single spanning tree and then applies a union bound. We can phrase it even problem that outputs k edges can achieve additive error more general: any graph m em k , because one can bound ≤ ( O kε · ln m k k k ) . In the cases of MSTs and MWPMs where 17

k = Θ(n), this gives an upper bound with a logarithmic dependence of ln in Section B.8.

m n

. The proof appears

Theorem 6.1 (NN [2026]). Let G = (V, E, w) be a graph and let S(G) be a family of solutions such that every S ∈ S(G) satisfies S ⊆ E and |S| = k. Consider the problem of minimizing w(S) among all S ∈ S(G). Then there exists an ε-DP algorithm A that outputs a feasible solution S ∈ S(G), such that with probability at least 1 − n−Ω(1) , m k w(S) − w(S ∗ ) ≤ O , · ln ε k where S ∗ = arg min w(S̃) is any optimal solution. S̃∈S(G)

Conclusion and Future Work

We first showed that for MST and MWPM there exist worst-case topologies where the error is tight with the upper bounds. We also proved lower bounds for MST and HC on large classes of topologies which are close to the upper bounds, off by just a log(n) factor. For MWPM, it remains open whether lower bounds can be derived for a large class of topologies, and what specific property that class should satisfy. For HC, closing the gap between the best lower 2 2 bound of Ω nε and upper bound of O n log(n) is an interesting question, as well as deriving a ε polynomial-time algorithm that achieves this additive error (as opposed to using the exponential mechanism). Finally, we believe that both our lower bound techniques for obtaining tight bounds and bounds on general topologies are likely to carry over to other graph problems as well.

Acknowledgments

Pagh and Retschmeier were supported by a Data Science Distinguished Investigator grant from Novo Nordisk Fonden, and are part of BARC, supported by the VILLUM Foundation grant 54451. Imola partially completed this work while working at BARC, University of Copenhagen, and was supported by the same grants.

References ACM SIGACT. STOC Test of Time Award. https://sigact.org/prizes/stoc_tot.html, 2026. Accessed: 2026-05-30. Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The discrepancy of shortest paths. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, Tallinn, Estonia, July 8-12, 2024, volume 297 of LIPIcs, pages 27:1–27:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. ISBN 978-3-95977322-5. doi: 10.4230/LIPIcs.ICALP.2024.27. URL https://doi.org/10.4230/LIPIcs.ICALP. 2024.27. Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, and Yinzhan Xu. Differentially private all-pairs shortest path distances: Improved algorithms and lower bounds. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACMSIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5040–5067. SIAM, jan 2023. ISBN 9781611977554. doi: 10.1137/1.9781611977554.ch184. URL https://doi.org/10.1137/1.9781611977554.ch184. Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu. Hierarchical clustering: Objective functions and algorithms. J. ACM, 66(4):26:1–26:42, jun 2019. ISSN 1557735X. doi: 10.1145/3321386. URL https://doi.org/10.1145/3321386. Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 118–127. ACM, 2016. doi: 10.1145/2897518.2897527. URL https://doi.org/10.1145/2897518.2897527. Anindya De. Lower bounds in differential privacy. In Ronald Cramer, editor, Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, volume 7194 of Lecture Notes in Computer Science, pages 321–338. Springer, Springer, 2012. doi: 10.1007/978-3-642-28914-9\ 18. URL https://doi.org/10. 1007/978-3-642-28914-9_18. Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang, and Samson Zhou. On the price of differential privacy for hierarchical clustering. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. doi: 10.48550/arXiv.2504.15580. URL https://openreview.net/forum?id=yLhJYvkKA0. Ibai Diez, Paolo Bonifazi, Iñaki Escudero, Beatriz Mateos, Miguel A Muñoz, Sebastiano Stramaglia, and Jesus M Cortes. A novel brain partition highlights the modular skeleton shared by structure and function. Scientific reports, 5(1):10532, 2015. Michael Dinitz, George Z. Li, Quanquan C. Liu, and Felix Zhou. Differentially private matchings. CoRR, abs/2501.00926, 2025. doi: 10.48550/arXiv.2501.00926. URL https://doi.org/10. 48550/arXiv.2501.00926.

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Frank Neven, Catriel Beeri, and Tova Milo, editors, Proceedings of the Twenty-Second ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 202–210. ACM, 2003. doi: 10.1145/773153.773173. URL https://doi.org/ 10.1145/773153.773173. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. ISBN 9783540327325. doi: 10.1007/11681878\ 14. URL https://doi.org/10.1007/11681878_14. Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan R. Ullman, and Salil P. Vadhan. Robust traceability from trace amounts. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 650–669. IEEE, IEEE Computer Society, 2015. doi: 10.1109/FOCS.2015.46. URL https://doi.org/10.1109/FOCS.2015.46. Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam D. Smith. Triangle counting with local edge differential privacy. Random Struct. Algorithms, 66(4):e70002, 2025. doi: 10.1002/rsa. 70002. URL https://doi.org/10.1002/rsa.70002. Michael B Eisen, Paul T Spellman, Patrick O Brown, and David Botstein. Cluster analysis and display of genome-wide expression patterns. Proceedings of the National Academy of Sciences, 95(25):14863–14868, 1998. Marek Eliás, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 560– 578. SIAM, jan 2020. ISBN 9781611975994. doi: 10.1137/1.9781611975994.34. URL https: //doi.org/10.1137/1.9781611975994.34. Chenglin Fan, Ping Li, and Xiaoyun Li. Private graph all-pairwise-shortest-path distance release with improved error rate. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, volume 35, pages 17844–17856. Curran Associates, Inc., 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/ 71b17f00017da0d73823ccf7fbce2d4f-Abstract-Conference.html. Anupam Gupta, Aaron Roth, and Jonathan R. Ullman. Iterative constructions and private data release. In Ronald Cramer, editor, Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, volume 7194 of Lecture Notes in Computer Science, pages 339–356. Springer, 2012. ISBN 9783642289149. doi: 10.1007/978-3-642-28914-9\ 19. URL https://doi.org/10.1007/978-3-642-28914-9_19. Michael Hay, Chao Li, Gerome Miklau, and David D. Jensen. Accurate estimation of the degree distribution of private networks. In Wei Wang, Hillol Kargupta, Sanjay Ranka, Philip S. Yu, and 20

Xindong Wu, editors, ICDM 2009, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009, pages 169–178. IEEE Computer Society, dec 2009. doi: 10.1109/ICDM.2009.11. URL https://doi.org/10.1109/ICDM.2009.11. Richard Hladı́k and Jakub Tětek. Near-Universally-Optimal Differentially Private Minimum Spanning Trees. In Mark Bun, editor, 6th Symposium on Foundations of Responsible Computing (FORC 2025), volume 329 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:19, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-367-6. doi: 10.4230/LIPIcs.FORC.2025.6. URL https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.FORC.2025.6. Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 21–30, New York, NY, USA, 2014. ACM. ISBN 9781450327107. doi: 10.1145/2591796.2591826. URL https: //doi.org/10.1145/2591796.2591826. Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, and Vahab Mirrokni. Differentially private hierarchical clustering with provable approximation guarantees. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 14353–14375. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/v202/ imola23a.html. Nicholas Jardine and R Sibson. A model for taxonomy. Mathematical Biosciences, 2(3-4):465–482, 1968. David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Vijaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, volume 93, pages 21–30. ACM/SIAM, 1993. URL http://dl.acm.org/citation.cfm?id=313559.313605. Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. In Amit Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 457–476. Springer, 2013. ISBN 9783642365942. doi: 10.1007/978-3-642-36594-2\ 26. URL https://doi.org/10.1007/ 978-3-642-36594-2_26. Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. Mining of Massive Datasets, 2nd Ed. Cambridge University Press, jan 2014. ISBN 978-1107077232. doi: 10.1017/9781108684163. URL http://www.mmds.org/. Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1019– 1049. SIAM, jan 2024. ISBN 9781611977912. doi: 10.1137/1.9781611977912.39. URL https: //doi.org/10.1137/1.9781611977912.39. 21

Colin McDiarmid. On the method of bounded differences, page 148–188. London Mathematical Society Lecture Note Series. Cambridge University Press, 1989. NN. Personal communication, 2026. Communication with undisclosed researcher. Rasmus Pagh, Lukas Retschmeier, Hao Wu, and Hanwen Zhang. Optimal bounds for private minimum spanning trees via input perturbation. Proc. ACM Manag. Data, 3(2), June 2025. doi: 10.1145/3725240. URL https://doi.org/10.1145/3725240. Adam Sealfon. Shortest paths and distances with differential privacy. In Tova Milo and WangChiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, PODS ’16, pages 29–41, New York, NY, USA, 2016. ACM. ISBN 9781450341912. doi: 10.1145/2902251.2902291. URL https://doi.org/10.1145/2902251.2902291. Peter HA Sneath. Numerical taxonomy. In Bergey’s manual® of systematic bacteriology, pages 39–42. Springer, 2005. Christos Sotiriou, Soek-Ying Neo, Lisa M McShane, Edward L Korn, Philip M Long, Amir Jazaeri, Philippe Martiat, Steve B Fox, Adrian L Harris, and Edison T Liu. Breast cancer classification and prognosis based on gene expression profiles from a population-based study. Proceedings of the National Academy of Sciences, 100(18):10393–10398, 2003. Michael Steinbach, George Karypis, and Vipin Kumar. A comparison of document clustering techniques. Proceedings of the International KDD Workshop on Text Mining, 06 2000. V. Strassen. The existence of probability measures with given marginals. The Annals of Mathematical Statistics, 36(2):423–439, apr 1965. ISSN 0003-4851. doi: 10.1214/aoms/1177700153. URL http://dx.doi.org/10.1214/aoms/1177700153. Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. ISSN 1551-3068. doi: 10.1561/0400000010. URL https://doi.org/10.1561/0400000010. Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, Cham, 2017. ISBN 978-3-319-57048-8. doi: 10.1007/978-3-319-57048-8 7. URL https://doi.org/10.1007/ 978-3-319-57048-8_7. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. ISBN 9781108415194. doi: 10.1017/9781108231596. URL http://dx.doi.org/10.1017/9781108231596. Joe H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301):236–244, mar 1963. ISSN 1537-274X. doi: 10.1080/01621459. 1963.10500845. URL http://dx.doi.org/10.1080/01621459.1963.10500845.

lca(v3 , v4 )

v4 e v3

v2 v3

Figure 3: An example of a hierarchical clustering T with costw (T ) = 12 for a graph G = (V, E) assuming unit weights. The edge e has cost 2 as the lowest common ancestor lca(v3 , v4 ) has exactly two leaves in its subtree of T . Furthermore, cutting the tree at lca(v3 , v4 ) would give a balanced cut.

Additional Details

In Figure 3, we illustrate the Dasgupta cost function, costw (T ), for a given hierarchical clustering tree T .

Omitted Proofs

B.1

Proof of Lemma 2.3

Lemma B.1. Let B : X d → X d be any mechanism that is (ε, δ)-differentially private under the Hamming neighborhood relationship, i.e. dH (x, x′ ) ≤ 1 for neighboring datasets x ∼ x′ . Then a dataset x ← X d , drawn uniformly at random, we have for each i ∈ [d], we have P [B(x)i = xi ] ≤ exp(ε) |X | + δ. Proof. Let n ∈ N. We index the elements in X by {1, · · · , n}. For some arbitrarily chosen i ∈ [d], assume a random vector x = xi ∼ Uni [n]d where ⊕ denotes vector concatenation, and we use the subscript xi to split the vector at index i. Now we can bound the probability that the i’th coordinate of the output of B(x) leaks its corresponding input xi :

P [B(x)i = xi ] =

1 |X |d−1 x

≤ |X |

∈[n]i−1 x

∈[n]d−i

1−d

≤ |X |

xi ∈[n]

≤

Xi ∼Uni ([n])

eε

xi ∈[n]d−i 1−d

[B(xi )i = xi ]

xi ∼Uni ([n])

ε1 e +δ n d−i

[B(xi )i = xi ] + δ

(B.1)

(B.2)

eε +δ. |X |

In line B.1, we use the fact that each Xi is i.i.d. and in step B.2, we use the privacy guarantees of the mechanism B and flip to a neighboring dataset where we explicitly set Xi = 1 under the hamming adjacency relation.

B.2

Proof of Theorem 2.4

First, we start with a supporting lemma. Lemma B.2. Suppose P, Q are distributions on a discrete set X satisfying P [X ∈ S] ≤ eε P [Y ∈ S] + δ for all S ⊆ X . Y ∼Q

X∼P

Then, there exists a function δ(x) : X → [0, ∞) satisfying 1. 2.

P [X = x] ≤ eε P [X = x] + δ(x) , and

X∼P

X∼Q

x∈X δ(x) ≤ δ .

Proof. We denote P (x) = P [X = x] (and similar for Q). X∼P

We take the function δ(x) = max{P (x) − eε Q(x), 0}. Condition 1 is satisfied because P (x) = eε Q(x) + (P (x) − eε Q(x)) ≤ eε Q(x) + δ(x). For condition 2, let N ⊆ X denote the set where P (x) − eε Q(x) ≥ 0. On x ∈ N , we have δ(x) = P (x) − eε Q(x), and on x ∈ X \ N , we have δ(x) = 0. Thus, X X X δ(x) = δ(x) = P (x) − eε Q(x) = P [X ∈ N ] − eε P [Y ∈ N ] ≤ δ . x∈X

x∈N

Y ∼Q

X∼P

x∈N

Theorem 2.4. Let B : {0, 1}d → 2[d] × {0, 1}d be any (ε, δ)-DP algorithm and let x ∼ {0, 1}d be eε −1 dδ drawn uniformly at random. Then, Succ(B) ≤ 2(e ε +1) + eε +1 . Proof. It suffices to show that " # X E 1[xi ̸= yi ] ≥ i∈I

1 1 E [|I|] − dδ . ε 1+e 1 + eε

We use conditional expectation to write ## " # " # " " X X X =E E [|yi − xi ||I] . E 1[xi ̸= yi ] = E E |yi − xi | I i∈I

i∈I

We will form a bound E [|yi − xi ||I] for each i. To do this, we expand it as follows by conditional probability,

E [|yi − xi ||I] = P [xi = 1, yi = 0|I] + P [xi = 0, yi = 1|I] P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I] = . P [I] 24

In the following, a sum over the variable x implicitly ranges over {0, 1}n , and a sum over y implicitly ranges over {0, 1}I . We can write X X P [A(x) ∈ (I, Yi,b )] , P [xi = a, yi = b, I] = 2−n P [A(x) = (I, y)] = 2−n x:xi =a y:yi =b

x:xi =a

where Yi,b = {y ∈ {0, 1}I : yi = b}. For a vector x ∈ {0, 1}n , let x(i→0) and x(i→1) denote x with its ith bit set to 0 (resp. 1). Because each A(x(i→0) ) and A(x(i→1) ) satisfy (ε, δ)-DP, by Lemma B.2, there exists a non-negative function δx↑i (I, b) such that h i h i P A(x(i→0) ) ∈ (I, Yi,b ) ≤ eε P A(x(i→1) ) ∈ (I, Yi,b ) + δx↑i (I, b), P P and I⊆[n] b∈{0,1} δx↑i (I, b) ≤ δ. Similarly, there exists a non-negative function δx↓i (I, b) such that h i h i P A(x(i→1) ) ∈ (I, Yi,b ) ≤ eε P A(x(i→0) ) ∈ (I, Yi,b ) + δx↓i (I, b) P P and I⊆[n] b∈{0,1} δx↓i (I, b) ≤ δ. By summing the first inequality over x ∈ {0, 1}n with xi = 0 (and the second over x with xi = 1), we obtain X P [xi = 0, yi = 0, I] = 2−n P [A(x) ∈ (I, Yi,0 )] x:xi =0 −n

≤2

(eε P [A(x) ∈ (I, Yi,0 )] + δx↑i (I, 0))

x:xi =1 ↑ = e P [xi = 1, yi = 0, I] + δi,1 (I, 0), P ↑ where δi,a (I, b) is defined to be 2−n x:xi =a δx↑i (I, b). Rearranging, we have ε

↑ P [xi = 1, yi = 0, I] ≥ e−ε P [xi = 0, yi = 0, I] − e−ε δi,1 (I, 0).

Similarly, we can write ↓ P [xi = 0, yi = 1, I] ≥ e−ε P [xi = 1, yi = 1, I] − e−ε δi,0 (I, 1), P ↓ where δi,a (I, b) = 2−n x:xi =a δx↓i (I, b). This means that

P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I] 1 = (P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I]) 1 + eε eε + (P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I]) 1 + eε 1 (P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I]) ≥ 1 + eε eε ↑ ↓ + (e−ε P [xi = 0, yi = 0, I] − e−ε δi,1 (I, 0) + e−ε P [xi = 1, yi = 1, I] − e−ε δi,0 (I, 1)) 1 + eε 1 = (P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I]) 1 + eε 1 ↑ ↓ + (P [xi = 0, yi = 0, I] − δi,1 (I, 0) + P [xi = 1, yi = 1, I] − δi,0 (I, 1)) 1 + eε 1 1 ↓ = P [I] − (δ ↑ (I, 0) + δi,0 (I, 1)), ε 1+e 1 + eε i,1 25

where the last step follows from the law of total probability. Thus, P [xi = 1, yi = 0, I] + P [xi = 0, yi = 1, I] P [I]

E [|yi − xi ||I] =

↑ ↓ δi,1 (I, 0) + δi,0 (I, 1) 1 ≥ − . 1 + eε (1 + eε )P [I]

Finally, we bound the entire expectation as " # " X X E E[|yi − xi ||I] ≥ E i∈I

i∈I

P [I]

i∈I

I⊆[n]

1 − 1 + eε

↑ ↓ δi,1 (I, 0) + δi,0 (I, 1) 1 − ε ε 1+e (1 + e )P [I] ! ↑ ↓ δi,1 (I, 0) + δi,0 (I, 1)

(1 + eε )P [I] ↑

↓

X X X δi,1 (I, 0) + δi,0 (I, 1) 1 1 = P [I] · |I| − P [I] 1 + eε 1 + eε P [I] I⊆[n]

i∈I

I⊆[n]

XX ↑ 1 1 ↓ = δi,1 (I, 0) + δi,0 (I, 1) . E[|I|] − 1 + eε 1 + eε

(B.3)

I⊆[n] i∈I

The second term simplifies to XX ↑ ↓ δi,1 (I, 0) + δi,0 (I, 1) I⊆[n] i∈I

! =

2−n

δx↑i (I, 0) +

n X X

≤

i=1

δx ↓ i (I, 1)

x:xi =0

! X

2−n

δx↑i (I, 0) +

x:xi =1

δx ↓ i (I, 1)

x:xi =0

 2−n 

 X X

δx↑i (I, 0) +

x:xi =1 I⊆[n]

i=1 n X

δx↑i (I, 0) +

x:xi =1

i=1 I⊆[n]

1[i ∈ I] · 2−n

n X X

n X

δx ↓ i (I, 1)

x:xi =0

i=1 I⊆[n]

≤

x:xi =1

I⊆[n] i∈I

X x:xi =1

δ+

δx ↓ i (I, 1)

x:xi =0 I⊆[n]

! −n

X X

x:xi =0

n X

δ = nδ.

i=1

Plugging back into (B.3), we obtain " # X 1 E |I| − nδ, E E[|yi − xi ||I] ≥ ε 1+e 1 + eε i∈I

giving the answer. 26

B.3

Proof of Lemma 3.2

Let E0 ⊆ E denote the embedded edges where xℓ(e) = 0. By the embedding procedure, we know E0 is a Bernoulli subsample of E with probability 21 . It suffices to show that all cuts in the subgraph induced by E0 are non-empty, as this will mean it is possible to construct a spanning tree entirely in E0 . In other words, we show that each cut in the graph has at least one zero-edge sampled with high probability, which, by a standard argument, implies that there must exist a zero-cost spanning tree. Now let E denote the complement event; i.e., that there exists a cut A, B such that E0 (A, B) = 0. We will upper bound P [E] by a union bound over all cuts. Let λ denote the minimum cut size in (V, E), and let Ni denote the number of cuts A, B such that E(A, B) = i. The probability that a cut with value i has no edges sampled is given by 2−i . By the union bound, we have P [E] ≤

|E| X

2−i Ni .

i=λ

To bound this, we use [Karger, 1993, Theorem 6.2] which shows that Ni ≤ n⌈2i/λ⌉ ≤ n · n2i/λ . Plugging this in, we have by a geometric sum 2/λ λ !i n |E| ∞ ∞ 2/λ X X X 2 n n3 −i −i 2i/λ = 2 Ni ≤ 2 n·n ≤n =n . 2/λ 2 1 − 21 n2/λ · 2λ 1− n i=λ i=λ i=λ 2

2/5

Using λ ≥ 5 log(n), it holds that n3 2−λ < n12 , and 12 · n2/λ ≤ 2 2 (1 − 12 n2/λ ) ≥ 13 . Thus, the probability of failure is at most n32 .

B.4

< 23 , so the denominator

Proof of Lemma 4.1

Lemma B.3 (Collision-free). Let (X1 , . . . , Xd ) ∼ Uni [n]d with d = ⌈αn⌉ for a constant 0 < α ≤ 1. Then, with probability at least 1 − exp(−Ω(α3 n)), the number of indices i for which there exists some j ̸= i with Xi = Xj is O(α2 n). Pd Proof. Define X̃ = 1 [∃ j = ̸ i : X = X ] and let Y = i j i i=1 X̃i . By a union bound, E[X̃i ] ≤ P P [X = X ] = (d − 1)/n, so that E[Y ] ≤ d(d − 1)/n = α2 n − α ≤ α2 n. Since changing a j i j̸=i single Xi affects at most two of the X̃i ’s, Y is 2-Lipschitz. By McDiarmid’s inequality [McDiarmid, 1989], for any t > 0, P [Y ≥ E[Y ] + t] ≤ exp(−2t2 /(4d)). Setting t = E[Y ] gives P [Y ≥ 2E[Y ]] ≤ exp(−E[Y ]2 /(2d)) = exp(−Ω(α3 n)). Thus, with probability at least 1 − exp(−Ω(α3 n)), we have Y ≤ 2E[Y ] = O(α2 n).

B.5

Proof of Theorem 4.2

Theorem 4.2 (Lower bound MWPM). Let ε > 0, δ ≤ (n/m)Ω(1) , and m > 2n. Then there exists a graph topology F = (V, E) and a distribution of weights Dω on weights of E such that for any (ε, δ)-DP protocol B that outputs an approximate minimum-weight perfect matching M under the ℓ1 neighboring relationship, if the weights w ∼ Dω , then the expected additive error satisfies w(M ) − w(M ∗ ) ≥ Ω((n/ε) · min(ln(1/δ), ln(m/n))) , 27

where M ∗ is an optimal minimum-weight perfect matching. Fix some constant 0 < α ≤ 1 and let R again be a parameter that controls the weights. Now let EncR : [n]d → Gω be constructed as follows. Let x ∈ [n]d be some vector of length d = αn and 0 < α ≤ 1. Then the encoder creates a complete bipartite graph G = (V1 ∪ V2 , E, w) with bipartitions V1 = {ℓ1 , · · · , ℓn } and V2 = {r1 , · · · , rn }. Each of the first d vertices ℓi ∈ V1 represents a single coordinate of x. For each i ∈ [d], we set w({ℓi , rxj }) := 0 and w({ℓi , rj }) := R for j ̸= xi . We treat the remaining (1 − α)n vertices in V1 as dummy nodes that simply get zero-weight edges to all vertices in V2 . Furthermore, let DecG : P(G) → [n]d and RecG : [n]d → [n]d be analogously defined as in Section 3. Find this construction also in Figure 2. Using this encoding, the optimal solution is determined by the number of collisions C in x and is not necessarily 0 as before. By Theorem 4.1, we can make C arbitrarily small with probability exponentially small in n. The key observation is that there are still Θ(n) many coordinates that do not collide. Every non-colliding coordinate can be recovered from a correct edge in some perfect matching M . Hence, we get this observation. Observation 4. Let G = (F, w) be obtained from EncR (x) and let C = |{i ∈ [d]|∃j ̸= i, xi = xj }| be the number of colliding coordinates. If M ∈ P(F ) is any perfect matching, then dH (DecF (M ), x) ≤

w(M ) − w(M ∗ ) + C, R

where M ∗ is an optimal MWPM of G. We now have all the ingredients ready to prove the theorem. The proof is similar to Theorem 3.1. First, draw x ∼ Uni([n]αn ) and fix a small constant 0 < α ≤ 1. WLOG, assume that αn is an integer. Then C ≤ α2 n with probability 1 − exp(−Ω(α3 n)) by Lemma 4.1. Suppose for contradiction that there exists an (ε, δ)-DP MWPM algorithm B with expected additive error E [w(M ) − w(M ∗ )] < 0.01 αnR. Then by Observation 4, E [dH (DecG (M ), x)] ≤ 0.01 αn+α2 n. So B correctly recovers at least αn − 0.01 αn − α2 n = αn(0.99 − α) coordinates in expectation. Observe that for some fixed R > 1, Observation 2 holds again, and the induced ℓ1 -distance of two encoded graphs differs by at most 2⌈R⌉ if the encoded vectors are Hamming neighbors. Hence, by Lemma 2.3, e2⌈R⌉ε + 2⌈R⌉e2⌈R⌉ε δ n ln(n) 1 ≤ exp ln(n1/c ) + exp ln n1/c δ n εc ln(n) = n(1−c)/c + n1/c δ . εc

P [RecA,R (x)i = xi ] ≤

Assuming δ = n−Ω(1) , the second term is o(1/n) and vanishes. Using linearity of expectation over all i ∈ [αn],   X E 1 [RecA,R (x)i = xi ] ≤ n(1−c)/c · αn = α · n1/c , i∈[αn]

For sufficiently large c > 1, this is sublinear in n, contradicting the assumed utility guarantee of Θ(αn). Finally, to obtain a bound that also depends on the number of edges, we use the same decomposition technique as in the proof of Theorem 3.1 with simplification that we don’t need to connect the subgraphs.

B.6

Proof of Lemma 5.4

First, we will show that the connected components in the sampled edges E ′ have size O(log n). Lemma B.4 (Largest components). Suppose F = (V, E) is a graph and let H be the subgraph 1−α obtained by keeping each edge independently with probability p ≤ dmax (F ) for some α ∈ (0, 1). Then 2−α the maximal size of a connected component in H is α2 4 log n with probability at least 1 − n−3 . We first introduce the following definitions. Definition B.5 (Stochastic domination). A random variable X is stochastically dominated by a random variable Y , if P [X ≥ a] ≤ P [Y ≥ a] for all a. A coupling of X and Y is a random vector (X̃, Ỹ ) such that the marginal distributions coincide with X and Y respectively. The following theorem due to Strassen [1965] shows that stochastic dominance is equal to the existence of a monotone coupling. Lemma B.6 (Strassen [1965]). A random variable X stochastically dominates a random variable h i Y , if and only if there exists a (monotone) coupling (X̃, Ỹ ) of X and Y such that P X̃ ≥ Ỹ = 1. Now, we are ready to prove Lemma B.4. Proof. We prove this result assuming that the graph is d-regular, so dmax (F ) = d. The proof for a general graph is similar. Let α ∈ (0, 1), set p := 1−α d and let Cv denote the connected component of a fixed vertex v in H and WLOG assume that our edge subsampling is exploring Cv by BFS starting in v. If 0 ≤ mt ≤ d is the number of neighbors of the currently explored vertex at step t ≥ 1 that have not already been explored, then observe that the size of the frontier conditioned on the past F, can be described as X0 = 1 ,

Xt = Xt−1 − 1 + Zt

where Zt | Ft ∼ Bin(mt , p) ,

because we keep each neighbor that is not already included with probability p independently. Intuitively, cycles can only reduce the number of newly discovered vertices, so the BFS exploration is dominated by the process that simply ignores them. Therefore, define the process Y0 = 1 ,

Yt = Yt−1 − 1 + Z̃t

where Z̃t ∼ Bin(d, p) ,

(B.4)

We claim that for each t ≥ 1, the random variable Yt conditional on the past, stochastically dominates Xt . Therefore, we will explicitly give a coupling (X̃, Ỹ ) of X and Y and apply Theorem B.6. Set X̃ = X and draw Ut | Ft ∼ Bin(d − mt , p) independently of Zt . Now, let Ỹt = Ỹt−1 − 1 + Zt + Ut and consider the coupling (X̃, Ỹ ). Clearly, the marginal distributions 29

match because Zt + Ut ∼ Bin(d, p) by the convolution of binomials. We show by induction that for each t ≥ 0, X̃t ≤ Ỹt . The base cases X0 , Y0 = 1 are trivial. Now, observe that for Zt ∼ Bin(mt , p), we have X̃t = X̃t−1 − 1 + Zt ≤ Ỹt−1 − 1 + Zt ≤ Ỹt−1 − 1 + Zt + Ut = Ỹt , where the last line follows from the non-negativity of the binomial distribution. Hence, Yt gives a valid upper bound on how large the component grows, i.e. P [|Cv | ≥ t] = P [Xt ≥ 1] ≤ P [Yt ≥ 1] . Because Yt is a sum of t binomials, by a standard convolution result, we get Yt =

t X

Z̃k − t ,

k=1

which is distributed as Yt ∼ Bin(td, p) − t. Now, let µ = t(1 − α). By a standard Chernoff bound, γ2µ ) for all γ > 0. Rearranging the term, yields P [Bin(td, p) ≥ (1 + γ)µ] ≤ exp(− 2+γ (t − µ)2 α2 P [Bin(td, p) ≥ t] ≤ exp − = exp −t · . t+µ 2−α

(B.5)

To make this decrease with n13 , we choose t = 2−α · 4 ln(n). Then we get by a union bound α2 P [∃v : |Cv | ≥ t] ≤ n exp (−4 ln(n)) = n−3 . Hence, with probability at least 1 − n−3 , no component has size larger than 2−α · 4 log n. α2 Now, we are ready to prove Lemma 5.4. Lemma B.7 (Existence of a good Dasgupta cluster). Suppose F = (V, E) is a graph and let 1−α α ∈ (0, 1) be a constant. Now, assign weights w(e) := 1 with probability dmax (F ) and w(e) := 0 otherwise for each edge e ∈ E independently. Then with probability at least 1 − 2n−3 , there exists a clustering tree T , such that costw (T ) ≤ 2−α · 4n log(n). α2 Proof. Let H = (V, EH ) be the random subgraph consisting of the sampled edges, i.e. EH = {e ∈ E | w(e) = 1} and note that only edges in EH contribute to the Dasgupta cost in G. This is equivalent to analyzing the connected components C1 , · · · , Ck ⊆ V of H separately because the overall Dasgupta cost decomposes to a sum of the cost within each Ci . Now, observe that any Ci can only contribute an additive term of at most |Ci | · mi where mi is the number of edges in component Ci . The worst case can be achieved if each of the mi edges has to cross the balanced cut, thus adding cost of at most |Ci | each.

Therefore, we have for the optimal Dasgupta clustering tree T , X X mi = max|Ci | · |EH | . |Ci | · mi ≤ max|Ci | · costw (T ) ≤ i∈[k]

i∈[k]

By Lemma B.4, with probability at least 1 − n−3 , each |Ci | ≤ 2−α · 4 log n. Furthermore, |EH | ∼ α2 nd 1−α Bin( 2 , d ) and by a Chernoff bound with probability at least 1 − exp(−Ω(n)), we have |EH | ≤ n. A union bound over both high probability events yields the desired result.

B.7

Proof of Lemmas 5.6 and 5.7

Proof. (Of Lemma 5.6) By construction, each edge e ∈ E is independently assigned to E \ E ′ , E0′ and E1′ with probabilities (1 − p, p2 , p2 ). Thus, conditioned on E1′ , each remaining edge in e ∈ E \ E1′ p/2 1−p , 1−p/2 . Thus, is independently assigned to E \ E ′ or E0′ with probability 1−p/2 p/2 |(E \ E1′ )(A0 , B0 )| 1 − p/2 p ≥ |(E \ E1′ )(A0 , B0 )| . 2

E E0′ (A0 , B0 ) | E1′ =

Proof. (Of Lemma 5.7) E1′ (A0 , B0 ) is a binomial distribution on E(A0 , B0 ) with probability p2 . p Thus, it suffices to compute a tail bound P X ≥ m 3 , where m = E(A0 , B0 ) and X ∼ Bin(m, 2 ). By 2 t Chernoff’s bound, we know P X ≥ mp 2 + t ≤ exp(− mp+2t/3 ) for all t ≥ 0. By assumption we know m2 /16 1 m m m m p = d0.5 ≤ . Taking t = the above bound is P X ≥ + ≤ exp − 8 4 16 4 m/4+m/6 < exp(− 8 ). max m n Because m ≥ ϕ(F ) ≥ 8n, we have exp(− 8 ) ≤ exp(−n), the failure probability over all 2 balanced cuts is at most 2n e−n ≤ 2−0.2n .

B.8

Proof of Theorem 6.1

Theorem 6.1 (NN [2026]). Let G = (V, E, w) be a graph and let S(G) be a family of solutions such that every S ∈ S(G) satisfies S ⊆ E and |S| = k. Consider the problem of minimizing w(S) among all S ∈ S(G). Then there exists an ε-DP algorithm A that outputs a feasible solution S ∈ S(G), such that with probability at least 1 − n−Ω(1) , m k ∗ w(S) − w(S ) ≤ O · ln , ε k where S ∗ = arg min w(S̃) is any optimal solution. S̃∈S(G)

The following proof is due to NN [2026]. Consider the algorithm that adds noise Ze ∼ Lap(1/ε) to each edge independently. Denote these weights with w′ . This mechanism is ε-DP under the ℓ1 neighboring relationship by a standard result [Dwork et al., 2006]. Now let T ⊆ S(G) be an ′ ∗ optimal Psolution over the noisy weights w and T be an optimal over the original weights w. Let ZT = t∈T Zt be the total noise of any T and let M = maxT ∈S(G) |ZT |. Then, w(T ′ ) ≤ w′ (T ′ ) + M ≤ w′ (T ∗ ) + M ≤ w(T ∗ ) + 2 · M , 31

by the same inequalities as used in Sealfon [2016]. Note that the sub-exponential norm of each of the i.i.d. Laplace random variables Ze is ∥Ze ∥ψ1 ≤ 2ε . By a standard Bernstein inequality [Vershynin, 2018], we get for each T for any t > 0 and an absolute constant c > 0, 22 P [|ZT | ≥ t] ≤ 2 exp −c min ε nt , εt , Now setting t = c·(k/ε) ln(m/k) for a sufficiently large constant c, the tail above becomes dominated k by the linear term exp − Ω(n ln(m/k)) . Clearly, |S(G)| ≤ nk ≤ em . A union bound over S(G) k yields, k P max |ZT | ≥ C ln(m/k) ≤ n−Ω(1) , ε T ∈S(G) Combined with the chain of inequalities above, this gives w(T ′ ) − w(T ∗ ) ≤ O((k/ε) ln(m/k)) with probability at least 1 − n−Ω(1) .

Record · ID 673427 · SHA-256 204f168d4fda9ca0
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.