Differentially Private Gomory-Hu Trees
Authors: Anders Aamand
Justin Y. Chen
Mina Dalirrooyfard
Slobodan Mitrović
Yuriy Nevmyvaka
Sandeep Silwal
Yinzhan Xu
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
graph algorithms
cuts
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: This paper gives a pure dp algorithm for all the pairs min cut problem with the same error as private min-st-cut.

Abstract: Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ that preserves the Min-$s$-$t$-Cut between any pair of vertices $s, t \in V$. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, since [Dalirrooyfard, Mitrovic and Nevmyvaka, Neurips 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega(n)$ additive error even with $(\varepsilon, \delta)$-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth, Ullman, TCC 2009] and $\tilde{O}(\sqrt{mn}/ \varepsilon)$  for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024], both achieved by DP algorithms that preserve all cuts in the graph. To achieve our result, we develop an $\varepsilon$-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle `bounded overlap' computational branches in recursive algorithms, which maybe of independent interest.

Differentially Private Gomory-Hu Trees
Anders Aamand BARC, University of Copenhagen aa@di ku. dk
Justin Y. Chen
Massachusetts Institute Technology justc@mit. edu
Mina Dalirrooyfard
Slobodan Mitrović
Morgan Stanley minad@mit.edd edu
UC Davis
smi smndttoovic@ucaais.ccc
Yuriy Nevmyvaka
Sandeep Silwal UW-Madison silwal@cs. wisc. edu
Yinzhan Xu UC San Diego
Morgan Stanley
yuriy nermyyatae@morggastaaalleee.... com
xyzhan@ucsd, edu
Abstract
Given undirected, weighted n-vertex graph G (V, E, w), Gomory-Hu tree T is weighted tree on V that preserves the Min-s-I-Cut between any pair of vertices L E V. Finding cuts in graphs is a key primitive in problems such bipartite matching, spectral and correlation clustering, and community detection. We design differentially private (DP) algorithm that computes an approximate Gomory-Ho tree. Our algorithm is e-DP, runs in polynomial time, and can be used to compute s-t cuts that are ( -additive approximations distinct t V with high probability. Our error bound is essentially optimal, since [29] showed that privately outputting a single Min-s-t-Cr requires ((n) additive error
the Min-s-t-Cuts G for all
with (e, dDDP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-s-l-Cuts were (n3//2/e /e) for c-DP [47] and (V/mn/e)) for (e. 8)- [66], both achieved by DP algorithms that preserve all in the graph. To achieve our result, we develop an s-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce novel privacy composition technique combining elements of both parallel and basic composition to handle 'bounded overlap' computational branches recursive algorithms, which maybe of independent interest.
Introduction
Over the last two decades, there has been significant attention to privatizing graph algorithms (see [70, 51, 57, 47, 10, 58, 37, 17, 78, 31, 39, 22, 32, 29, 66, 53) and references within). Graph algorithms often applied to large data sets, such social networks, containing sensitive information. It is well understood by now that even minor negligence in handling user data can severely impact privacy; see [8, 74, 59, 82, 26] for few examples. Differential privacy (DP), introduced by Dwork, McSherry, Nissim, and Smith in their seminal work [36], is widely adopted standard for formalizing the privacy guarantees of algorithms. Informally, an algorithm differentially private the outputs for two given neighboring inputs are statistically indistigguishabl..
A major part of the literature private graph algorithms has been approximating cuts which is the setting our paper. Given an undirected, weighted graph G = (V. E, w) with positive edge weights, cut is bipartition of vertices (U, V \ U), and the value of the cut is the sum of the weights of edges crossing the bipartition. Given a pair of distinct vertices s, E V, the Min-s-I-Cut is
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

a minimum-valuse cut (U, V \ U) where E U and t E VV U. Min-s-f-Cut is dual to the Max-s-t-Flow problem, and the celebrated max-flow min-cut theorem states that the value of the Min-s-I-Cut equals the value of the Max-s-I-Flow [41, 38.. Finding a Min-s-t-Cut (or equivalently Max-s-t-Fllw) is fundamental problem algorithmic graph theory, which has been studied for over seven decades (earliest references include [30, 50, 41, 38)) and has inspired ample algorithmic research and applications, including edge connectivity [71], bipartite matching (see, c.g., [25]), minimum Steiner cut [62], vertex-connectivie oracles [77], among others (see the survey [23]).
Over the recent years, nearly tight algorithms have been developed on outputting private Min-s-t-Cut [29], private global Min Cut [46], and private All Cuts problems [47, 9, 37, 66, 67]. However, no work has been done on private All-Pairs Min Cut (APMC) which our focus. Given an imput graph, the goal of APMC is to output a Min-s-t-CC Cut for all the pairs of vertices s and in V. We fill this gap, and obtain a private algorithm on APMC with the same error guarantee as private Min-s-I-Cut.
The definition of neighboring inputs depends on the specific application and yields semantically different privacy guarantees. We now specify the standard privacy model for graph cut problems which is used in ours and the aforementioned works. The graph's vertex set is publicly available, and two neighboring graphs differ in only one edge. If the graphs are weighted, two neighboring graphs are those whose total weights differ by at most one and in single edge. Semantically, this protects privacy if the inclusion of any individual affects the weight of an edge by bounded quantity," Given neighboring inputs G and G", and a subset of outputs O, an (s. -DDP algorithm A satisfies P(A(G) E O) S e ((A(G") E 0) + 5. When ò = the algorithm satisfies pure DP, and otherwise approximate DP. There is always a trade-off between privacy and accuracy: algorithms for nontrivial problems satisfying DP must have errors.
Since the above privacy model is standard for analyzing cut problems under DP, it is natural to also adopt it for the APMC problem. To further motivate the study of APMC under this particular privacy model from a more practical perspective, note that the graph could correspond to a road network and the weight of an edge could correspond to the number of people who travel along the road corresponding to that edge. The above model then ensures that whether any particular individual uses any particular road cannot be deduced based on the output of a DP allalgrrithm run on the graph. Moreover, minimum cuts are a natural measure of bottlenecks in transportation networks, and it may therefore be of interest to compute them on such traffic graphs in differentially private fashion.
We now discuss the relevant private algorithms for cut problems. Dalirrooyfard, Mitrović, and Nevmyvaka [29] recently gave the optimal c-DP algorithm for the Min-s-t-Cut problem with additive error ((n/s). They show an essentially matching s(n) lower bound, even for algorithms which satisfy only approximate DP and allow both multiplicative and additive error.
For the problem of global Min Cut, where one seeks the cut minimizing Min-s-t-Cun over all pairs of node s, t, Gupta et al. [46] gave an e-DP algorithm with additive error O llggm. ). Their algorithm runs in exponential time, but they also give a version running in polynomial time but only satisfying
approximate + The authors also show that there does not exist an cDDP algorithm for global Min Cut incurring less than M)ognn additive error.
The private All Cuts problem, where one seeks to output a synthetic, private graph which preserves the value of all the cuts, has been extensively studied. Given a graph G, the goal is to output synthetic graph H on the same vertices such that each cut-value in H is the same as the corresponding cut-value in G, up to some additive error. Gupta, Roth, and Ullman [47] and, independently, Blocki, Blum, Datta, and Sheffet [9] gave algorithms for this problem with additive error of O (n 1.5 /EE) while satisfying pure and approximate DP, respectively. Eliáš, Kapralov, Kulkarni, and Lee [37] improved
Note that the focus of all of these works and our paper is outputting the actual cut structure not the value of the cut.
"We note that there are several other notions of neighboring datasets for other graph problems implying different privacy semantics (including allowing vertex and all of its edges to change or fixing the unweighted topology of the graph and only allowing edge weights to change). The notion which we use the standard for cut problems (used in [46, 9, 37, 84, 29, 66]) as it is the strongest form of privacy that allows for any approximation of cuts or cut values. Moreover, this notion carries over to weight-DP, where in the two neighboring graphs all edges can change in total é distance 1. We include detailed discussion of various forms of differential privacy on graphs in Appendix A.5.
'The parameter ó corresponds to the small probability that an individual's 's data is leaked. In this case the additive error has dependency 6, we do not mention this dependency for simplicity.
2

---

Problem
Additive Error
Output
Runtime
Global Min Cut [46]
((lo((n)/s)
Pure
Cut
Exponential
Global Min Cut [46]
((log(x)/e)
Approx
Cut
Polynomial
Min-s-t-Cut [29]
O(n/s) and Q(x)
Pure
Cut
Polynomial
All Cuts [47]
O(1(/2)))
Pure
Synthetic Graph
Polynomial
All Cuts [37, 66]
Ólymn/e) and Q( mm//))
Approx
Synthetic Graph
Polynomial
APMC Values (Trivial)
O(n/s)
Approx
Values Only
Polynomial
APMC (Our Work)
Ö(n/s)
Pure
GH-Tree
Polynomial
Table State-of-the-art bounds for private cut problems. Dependencies on the approx. DP parameter
5 are hidden. The APMC result with approx. DP follows from advanced composition by adding
Lap(O(n/e) random noise to (*) true values. For APMC, the lower bound of (2(n) error [29] also applies APMC generalizes Min-s-t-Cut.
on these results for sparse, unweighted (or small weight) graphs, achieving error Ô (v mar approximate DP. The authors show that this сгтог is essentially tight for algorithms with purely additive error (and no multiplicative approximation). In follow-up work, Liu, Upadhyay, and Zou [66] extended these results to weighted graphs and gave an algorithm for releasing synthetic graph for the All Cuts problem with Ó
with
error. Recently, Liu et al. [67] gave an algorithm for the same problem with worse error Ó but which runs in near-linear time.
One important cut problem absent in the study of private graph algorithms is All-Pairs Min Cut (APMC), which has been extensively studied in the graph algorithms community for over six decades. In seminal paper, Gomory and Hu [44] showed that there is a tree representation for this problem, called a GH-tree or cut tree, which takes only n 1 Min-s-f-Cut (Max Flow) calls to compute. Consequently, there are only n different minimum cut values in an arbitrary graph with positive edge weights. There has been long line of research in designing faster GH-tree algorithms (c.g. [49, 15, 2, 88, 63, 3, 5, 6). also see the survey [75]), culminating an almost linear time algorithm for computing the GH-tree [6].
Beyond its importance graph algorithms, the all-pairs aspect of APMC is especially important in the context of DP. Answering multiple queries degrades privacy, so key feature of differential privacy the ability control this degradation through composition theorems (see, for instance, [34, 83]). Applying advanced composition of private mechanisms to the (nn/s) error result of [29] for single s-t--s-tCuut implies that APMC can be solved with O(n² /E) additive error while satisfying approximate DP. Given the structure of the APMC problem as characterized by the existence of GH-trees, natural ask one can improve upon black-box composition results. 6
Existing works provide a preliminary answer. Since the algorithm by [66] approximately preserves all cuts, it can also be used to solve APMC with approximate DP and additive error of Ô (/mn/c). Additionally, the 2(n) lower bound for Min-s-t-Cur of [29] also applies to APMC, as it is harder problem. So, in contrast to computing global Min Cut [46), Min-s-l-Cut [29], and All Cuts [37, 66), where the privacy/error tradeoff is tightly characterized up to poly(log n. 1/e) factors, there remains a gap of xs //nn between the best known lower and upper bound for DP APMC, which can be as large R( (z) dense graphs. This motivates the following question, which is focus:
Question Can we obtain tight bounds on the additive error for APMC with DP?

---

1.1
Our Results
Our main contribution an E-DP algorithm for APMC with Ó(n/s) additive error. Our algorithm privately outputs all the Min-s-t-Cutt while incurring the same error, up to polylog(n) factors, required to output a Min-s-t-Cut for single pair of vertices s and To achieve this result, we introduce an algorithm that solves the more general problem of privately generating an approximate Gomory-Hu tree (GH-treee. Gomory and Hu [44] showed that for any undirected graph G, there exists a tree T defined on the vertices of graph G' such that for all pairs of vertices s, L, the Min-s-t-Cut in T also a Min-s-t-Cur in G. We develop a private algorithm for constructing such a tree.
Theorem 1.1. Given weighted graph G EV,E, w) with positive edge weights and a privacy parameter & > O, there exists an E-DP algorithm that outputs an approximate GH-tree T with additive error Ö(n/e): for any 8 + t E V, the Min-s-I-Cut on TT and the Min-s-t-Cut on G differ in (n/E) in cut value with respect to edge weights in G. The algorithm runs in time Ón²)) and the additive error guarantee holds with high probability.
Theorem 1.1 essentially outputs a synthetic graph in a DP manner that approximates each Min-s-l-Cut with an additive error of (nn/e). Since the GH-tree output by Theorem 1.1 is private, any post- processing this tree is also private. This yields the following corollary.
Corollary 1.1. Given a weighted graph G with positive edge weights and a privacy parameter > 0, there exists an E-DP algorithm that outputs, for all the pairs of vertices and t, cut whose value is within Ó(n/E) from the value of the Min-g-t-Cut with high probability.
Another corollary of Theorem 1.1 is polynomial time, pure DP algorithm for global Min-Cut. Corollary 1.2. Given weighted graph G with positive edge weights and a privacy parameter > O, there exists an e E-DP algorithm that outputs an approximate global Min-Cut of G in Ó( time and has additive error Ö(n/e) with high probability.
Prior work obtained an exponential -iteeettilltimeeeeeeee pure DP algorithm and a polynomial- approximate DP for global Min-Cur with error O (log n/E) [46]. It is an open question whether there exists an efficient algorithm which satisfies pure DP and outputs an approximage global Min-Cut with polylog(n)/e additive error.
Lastly, we note another application of Theorem 1.1 is pure-DP algorithm for min k-cut? problem with multiplicative error 2, additive error Ö(nk/e). No prior poly time pure DP algorithm can compute min k-cut on weighted graphs with near-linear in n error. See Corollary F.1) for details.
Tightness of Our Main Result Corollary 1.1 is tight up polylog(n) and factors since any DP algorithm outputting the Min-s-t-Cut for a single fixed pair of vertices 8 and requires (2()) additive result shows that required for a single cut up to log factors. We also note that the 2())) lower bound for a single cut of [29] is on sparse graphs and applies to both pure and approx DP. Hence, there can be polynomial improvement on our result even if the input is sparse or if we relax to approx DP.
error [29]. Thus,
compute all min-cuts privately with the same error
Paper Organization In the rest of the main body, we give detailed overview of the challenges in privately creating a GH-tree as well as a technical overview of our approach. Due to space constraints, all pseudocode and proofs are given in the appendix. Two technical ingredients which may be generally applicable are (1) e- e-DP, Ö(n/E) additive error algorithm for Minimum Isolating Cuts [62, 3]. a recently introduced problem which has found success as a subroutine in fast algorithms for cut problems, and (2) general theorem for privacy composition on recursive algorithms where sensitive data is not partitioned into disjoint sets on each recursive call (in this setting, composition is straightforward), but rather the recursive subsets have "bounded-overlap."
Open Problems. We highlight three interesting open problems related to our work in Appendix G.
In this work, the notation Ō(z) stands for O( polylog
'A recent line of work on approximating all all-pairs shortest path distances with differential privacy has the
same goal of using graph structure to limit the error necessary to answer many queries [81, 39, 22, 13].
'The goal is to partition the vertex set into & pieces and the cost of partitioning is the total weight of all edges between different pieces in the partition. We wish to find the smallest cost solution.

---

2 Technical Overview
A greatly simplified view of a typical approach to designing a DP algorithm begins with a non-DP algorithm, which is modified ensure privacy. The primary challenge lies in finding an appropriate method to privatizing the algorithm, if such method even exists, and rigorously proving that satisfies DP. For instance, Gupta et al. [46] employ Karger's 's algorithm [56] to produce a set of cuts and then use the Exponential Mechanism [70] to choose one of those cut. This simple but clever approach results in an (c, 6)-DP algorithm for global Min Cut, for 5 = poly(a)) with O log additive error. Dalirrooyfard et al. [29] show that the following simple algorithm yields e- e-DP Min-s-t-Ca sutt with (nn/E) additive error: for each vertex v, add an edge from v to s and from v to t with their weights chosen from the exponential distribution with parameter 1/s; return the Min-s-t-Cut on the modified graph. In the remainder of this section, we first explain why directly privatizing certain existing non-private algorithms fails to achieve the desired additive error. After, describe our approach.
2.1 Obstacles in Privatizing the Algorithm of Gomory and Hu
The All-Pairs Min-Cut (APMC) problem produces cuts for (*) pairs of vertices; it is known that these cuts have only (n) distinct values. This property was leveraged in the pioneering work by Gomory and Hu [44], who introduced the Gomory-Hu tree (GH-tree), a structure that succinctly represents all the Min-s-f-Cuts in a graph.
The original GH-tree algorithm uses a recursive construction, solving the Min-s-I-Ca problem at each recursion step: In each step of the recursive call, the input will be graph H and special set of terminal vertices R S V. (1) The root of the recursion starts with H = G and R = V. (2) At each recursive step, select two arbitrary vertices and f within R (if [R] = 1, then the problem becomes trivial and the recursion stops). (3) Compute the Min-s-l-Cut in the graph, and say the Min-s-I-Cut is (U, V (AU U) where: E U,L & U. (4) Create two graphs, H, and He, where H, the graph with V V contracted, and H, is the graph with U contracted. Then recursively solve the problem on H, with terminal set R n U, and on H, with terminal set R n (V U). (5) Finally, we combine the two trees created by the two recursive calls, argue the correctness utilizing the submodularity of cuts. The GH-tree efficiently represents all pairwise Min-s-f-Cuts in the graph by iterating through these steps until there is no supernode of size larger than 1.
To privatize this algorithm, the Min-s-t-Cut procedures be replaced with the private Min-s-t-Cut algorithm introduced in [29]. However, several challenges arise in ensuring low error with this approach. First, the algorithm of [29] modifies the graph. It unclear whether these modifications should persist in each Min-s-I-Cut call or if the graph should revert to its original form. Second, the recursion depth may reach (n)). Even ignoring the propagation of error across recursive calls, dependent invocations of the DP Min-s-t-Cut must use very small values of z due to privacy composition. Under basic composition [35], each call the algorithm of [29] must use E' O(E/n) to guarantee DD for the final algorithm. Even using advanced composition [34] would require e' = O(e/Vn hog////////////// (1))) to achieve (c, D)-DP. The resulting error would still be higher than that achieved in the prior work preserving all cuts. Finally, we may hope that a single edge impacts only small number of min-cuts, property that could be leveraged in constructing a private GH-tree. However, as we depict in Figure 3, the -isseiiitvv of changing a single edge is 2(n), even when outputting only the values of the Min-s-I-Cuts.
2.2 Towards Privatizing a Low-Depth Algorithm
The preceding discussion indicates that low recursive depth is a crucial property of private algorithm for producing a GH-tree. While the canonical algorithm of [44] has linear recursive depth, recent breakthroughs in fast GH-tree algorithms offer the additional advantage of polylogarithmic depth, e.g., [3, 61, 4, 64, 6]. At a high-level, our result derives from privatizing the algorithm described in [61. Section 4.5] (this same algorithm also appears in [4]). To replace components of this algorithm with differentially private counterparts necessitates adding noise, which introduces additive errors throughout the recursive algorithm. Tracking the propagation of this error throughout the algorithm requires careful accounting. Moreover, the specific steps of the non-private algorithm presents several fundamental challenges in creating a private version. The remainder of this subsection briefly summarizes the structure of this algorithm.
5

---

1/2
Sey
:
Starge
Starge
(a)
(b)
(c)
Figure 1: Recursive structure of low-depth GH-tree. (a) The decomposition into (S.) and Starge = V \ Uven S, defines the recursive subinstances. For each v E R, S, constitutes a Min-s-u-Cut. None of the S, Starge too large, which leads polylogarithmie upper-bound on the recursion depth of the algorithm. (b) A subinstance obtained by contracting V Se, to single vertex ze,, (c) A subinstance obtained by contracting S, single vertex yv for each v E B.
Minimum Isolating Cuts. For a set U of vertices in G, let wuU)) be the sum of the weights of the edges in G with exactly one endpoint in U. The first building block is subroutine called Minimum Isolating Cuts, introduced in [62, 3].
Definition 2.1 (Min Isolating Cuts [62, 31). Given set of terminals R S V, the Min Isolating Cuts problem asks to output a collection of sets {S, S VV : E R] such that for each vertex v E R, the set S, satisfies Sy R {v), and it has the minimum value of w(S)) over all sets S that S S = {r}- In other words, each S. is the minimum cut separating v from R {o].
The Isolating Cuts Lemma [62, 3] shows how to solve Min Isolating Cuts in O n) calls to Min-s-t-Cut. At a high level, the Isolating Cuts Lemma is used to simultaneously find disjoint Min-s-t-Cuts for several s, pairs. More precisely, single recursive step of the GH-tree algorithm of [61] uses Min Isolating Cuts to find a collection of disjoint subsets of vertices {S, C Viven for some set of terminals R V and a source vertex & R which satisfy three properties:
(a) The subsets correspond to Min-s-v-Cuit each subset S. is the v-side a Min-s-v-Cut.
(b) The subsets not too large: |S. < (1 22
(c) The union of the subsets is not too small: Σ J.S.1 2 n/ polylog(n).
The algorithm is recursively applied to each of the subsets S, (with vertices outside of S, contracted) as well as the remainder of the vertices Suagee = V US. (with each S, contracted). In concert, conditions (b) and (c) guarantee that the recursive depth will be polylogarithmic. Condition (a) allows us to stitch the outcome of these recursive calls together into a GH-tree that preserves Min-s-t-Cuts. See Figure 1 for visualization of this process. It remains deseribe how generate the source s, terminals R. and subsets [Se]ve to complete the high level description of the algorithm [61]. We call subset S. having properties (a) and (b) good subset.
Choosing The vertex is chosen uniformly due to the following: Let Dr be the set of all vertices V E V.V {s} for which there exists Min-s-o-Cut with the v-side having cardinality at most n/2, i.e., the side of the cut satisfies condition (b). A lemma from [2] shows that, as long
is chosen uniformly at random from V. we have E | [[ = 2(m): constant fraction of vertices have small cardinality Min-s-y-Culle This is important since the algorithm chooses R from D", i.c., all the subsets S, chosen by the algorithm have cardinality at most n/2 2 and hence they satisfy property (b).
Finding good subsets (S.) which cover D After choosing s, the algorithm selects geometrically decreasing sets of potential terminals n2" ...... Rllgn) where each vertex other than & selected into Rt uniformly at random with probability 2- For each set of terminals Rt, the algorithm runs Min Isolating Cuts on R R'U(s} and keeps the "good" subsets (S.) ] output by Min Isolating Cuts. Recall that good subset S, has properties (a) and (b). To test property (a), verify which subsets

---

Se correspond to Min-s-e-Cuts by computing the single source Min-s-o-Cus values from s to all V E V {s} and comparing that to the value of the cuts S... To satisty property (b), we only keep S, if [Sa.] S n/2..
The first observation is that for any particular Min-s-e-Cur with e-side Sy. there is some sampling level it where there is a reasonable probability that the only terminal sampled in S is v, i.c. Re S = {v). If this event occurs, then Min Isolating Cuts with terminals R² U {s} will return Sy as one of its outputs-the minimum cut separating from the other terminals is the Min-s-v-Cut. The second observation is that there is some sampling level i < [ig n where, when run on the corresponding terminals R' U {s), the expected size of the union of good subsets is D'L
Ω
i... satisfying (c). Thus, selecting the sampling level whose good subsets have maximum total cardinality produces collection { satisfying conditions (a), (b), (c).
log ni
log*
2.3
Three Core Challenges
As the Min Isolating Cuts are a major building block of the algorithm of [61], our first challenge is finding a privatized version of it.
Challenge 1. Construct a differentially private, approximate Min Isolating Cuts algorithm.
Next, in one recursive step, the non-private algorithm compares the Min Isolating Cuts single source Min-s-e-Cus values. Making these procedures private will introduce additive errors, and this makes it difficult satisfy conditions (b) and (c). Recall that in [61], at some sampling level Min Isolating Cuts will correspond to Min-s-e-Cuts which are neither too large for condition (b) nor too small for condition (c). This convenient property is deduced from the cardinality of the true Min-s-o-Cut and the fact that calls to Min Isolating Cuts will find exactly those Min-s-o-Cuts. Without adjustment, plugging in additive approximate subroutines will fail produce recursive of a reasonable size, undermining the goal of low recursive depth.
Challenge 2.
Design a recursive step that employs additive approximations for Min-s-u-Cut
values and Min Isolating Cuts while ensuring that (1) no sub-instunce is too large and (2) the union of sub- instances is sufficiently large.
Even assuming that the above two challenges are resolved, it remains unclear how to account for the privacy loss of the final low-depth recursive algorithm. The difficulty lies in the fact that, despite the polylogarithmic recursion depth, a single edge of the original graph may appear in multiple sub-instances across a single recursive level. A given instance with terminal set R will have R + 1 recursive aub-instances: R| of them are obtained by contracting each of the vertex sets (V \. Se Rt into a single vertex Te, and one obtained by contracting each Sg, V E R into a single vertex ye (see Figure 1 (b)). If an edge has both of its incident vertices lying in single S, or in Starge == Uren S,, then that edge will only appear in the corresponding sub-instance. However, an edge with, say, one endpoint in S,, and the other in S, for different u and will appear in three recursive sub-instances: those obtained by contracting V / Su. V\S, and V Starge Moreover, this edge could appear in up to (n) sub-instances. So, if we naïvely apply basic composition, need the computation on each aub-instance to be (s/n)-DP. This would lead to final Ö(n? /E) additive error guarantee, which is again worse than previous work on preserving all cuts.
Challenge 3. Modify the algorithm so that the privacy loss of a given edge can be accounted for by the recursion depth.
In the following sections, we give technical overview how we overcome these challenges.
2.4 Addressing Challenge 1: Privatizing Min Isolating Cuts (Appendix B)
[62] and [3] independently introduce the Isolating Cuts Lemma, showing how to solve the Min Isolating Cuts problem using Oloog [R] many Min-s-t-Cut calls. [62] use it to find the global Min Cut in polylogarihmmially many invocations of Max Flow and [3] use it to compute GH-tree in
'Note that the final set of terminals Ht is inferred from the selection of (S.). corresponding to the good subsets certain sampling level.
7

---

unweighted graphs. Subsequent algorithms for GH-tree also use the Isolating Cuts Lemma, including the almost linear time algorithm for weighted graphs [6]. The Isolating Cuts Lemma has been extended to obtain new algorithms for finding the non-trivial minimizer of symmetric submodular function and solving the hypergraph minimum cut problem [72, 21J. We develop the first differentially private algorithm for finding Min Isolating Cuts.
Theorem 2.1. There is an s-DP algorithm that given a graph G and a set of terminals R, outputs sets {S. E R), such that for each vertex v E R. the set Sy satisfies S. n R = {v}, and w((S.) S w(())) + O(g) with high prob, where (S) e E R] are the Min Isolating Cuts for R.
Tackling this first challenge-obtaining out to be not too difficult. We repeatedly invoke the private Min-s-t-Cut algorithm of [29] O (log n) times. To establish the error bound, carefully apply the cut submodularity property (Lemma A.1) to account for the approximate errors. Since we are separating a potentially large set of terminals rather than single pair, we must ensure the total error, summed across all terminals, remains bounded by Ô (*) (see Lemma B.1 for this stronger result).
DP algorithm for constructing Min Isolating Cuts turns
2.5 Addressing Challenge 2: Privatizing the Recursive Step (Appendix B and Appendix C)
The second challenge involves controlling the size of the sets produced by our DP Min Isolating Cuts algorithm. To address this, we use the following idea to bias the algorithm toward selecting smaller cardinality sets satisfy that property (b). Consider graph G with terminals 8 and l. We aim find an approximate Min-s-l-Cut where the s-side of the cut contains a small number of vertices, without significantly sacrificing accuracy. To achieve this, we can add edges from to every vertex with a certain weight, penalizing the placement of vertices on the s-side of the cut. Applying this idea to our DP Min Isolating Cuts algorithm, we enforce that if true minimum isolating cut of size most n/2 exists, we will output an isolating cut of size at most 0.9n while increasing the additive error of the algorithm by only a constant factor.
The above only takes care of property (b). A subtlety in the argument of [61] in making sure property (c) is satisfied over all good subsets is the following: Randomly sampling terminals It' will, with reasonable probability, mean that for some vertices v. its Min Isolating Cut S. will be the same as its Min-s-o-Cut S In particular, this will be true if E Rt is the only vertex sampled on its side of the Min-s-o-Cut. In this case, S. is good subset and is kept by the algorithm. Later, using that S, S. they argue that the union of good subsets is not too small.
Unfortunately, even though the Min Isolating Cuts output by our DP algorithm have small additive error, they can have significantly fewer nodes than the optimal cut S Essentially, although the true Min-s-e-Cut may be large, there is no lower bound on the node size of approximate Min-s-o-Cuts. This poses a challenge in showing that the union of the good sets S, retained by the algorithm is not too small (property (c)). To address this, we compare S, not to S but instead to the smallest cardinality "approximate" Min-s-e-Cut S,,. The argument that, for some sampling level, there will be reasonable probability that Min Isolating Cuts will return an S, which an approximate Min-s-o-Cur and has cardinality lower bounded by |$.1 then goes through. For the complete argument, we adjust our notion of "approximation" based on the size of S,,, allowing for weaker approximations for smaller cardinality sets. This only degrades our approximation with respect to property (a) by log factors.
2.6 Addressing Challenge 3: Bounding Privacy along the Recursion Tree (Appendix D)
The third challenge involves controlling the privacy budget. We need to ensure that, for any two neighboring graphs, the output distributions across polylog(n) recursive layers differ by, at most e factor. To achieve this guarantee, we allocate the privacy budget across polylog(n) recursive sub-instances. Recall that a recursion depth of polylog(n) does not imply that the privacy budget can be evenly allocated across polylog(n) instances. To recall the 3rd challenge, consider two neighboring instances, G and G", that differ on edge zy. Suppose that in the first step of the algorithm, the good sets { and Suuge are the same in both graphs G and G'. Suppose that In this case, the edge ry affects multiple recursive instances: specifically, in G.. Gu, and Giare (similarly Gy,, G²,, and (. Thus computations across multiple branches of the recursion depend on the same edge, meaning the privacy guarantee depends more than just the recursion depth.
S, and y Su-
8

---

Input node
Number of children of o, egs d
Sensitive data: X m (N,, No. X4. Xz)
Sensitive and sanitized indices 1" and J" for each child o, eig.
Sanitized data: Y
[1,3]
(2
1 [2,5) and -== (1)
Input to child
Toput child x - Xg) x (Xa) Manntsa (2,, Xs))
Input to child ny:
1 (4) and n (2.5.3)
x - (a)
Auxiliary output d"
( (X,,
Figure 2: Bounded-overles branching composition. Node u receives as imput a set of sensitive data X" and set of sanitized data Y". Via DP mechanism Mecurse it then computes the number of children of u, and for each child e, a set of sensitive indices L, and a set of sanitized indices Jg. Importantly, the sets I, are disjoint, and index j can appear in at most different sets J (in the figure 8 = 2). Node u may further return some other DP output a". Each child v now receives as input the data (X,)igr- and the concatenation (f(Y), (f(YiiMaaniizz (Xz)je.")) where Msanitize is DP mechanism and f is some arbitrary function. Intuitively, if an element X; of the dataset is sanitized in child v, then post-processing ensures that the entire computation in the subtree rooted at o DP with respect to user i. Since user i's data X; can only appear unsanitized in a single child, and is sanitized in at most é children, we can apply basic composition over h computations of Mascure and é h computations of Maanitize, where h is the depth of the tree.
To address this issue, we introduce an additional step before recursing on certain new instances. For the instances where all vertices in V \ S, are contracted to single vertex, we first add an edge from the contracted vertex to every vertex in S. with weights drawn from Lap(polylog (n)))))) Then we recurse on this altered graph. The intuition is that in neighboring instances, if x E S, and y & S.. these noisy edges cancel the effect of xy. preventing its influence from propagating further along this branch of the recursion. As result, ay impacts only Glarge- Fortunately, the added noise only contributes (n/ss) to the final additive error, as noise is added to only (n) edges.
Bounded-Overlan Branching Composition. The approach outlined above is an example of more general privacy composition technique, which we develop and formalize (Appendix D.2). Here, we provide a high-level overview of the technique and refer to Figure 2 for an illustration. Consider an algorithm Maranch that takes a sensitive dataset X as input, performs DP computation on X, and recurses on some subsets of X. Now, consider the computation tree corresponding to the recursive branching of Mbranch- If the subsets assigned to a node's 's children are chosen privately and the subsets are disjoint, privacy composition straightforward, as outlined below.
Let upper-bound the depth of the tree. If, at single node, the release of the computation on as well as the indices to the subsets of its children is (e, DDP, then the entire mechanism Mbranchh (X) is (he, -DP. To see this, consider any pair of neighboring datasets X, X' which differ only on the coordinate i" As the subsets of indices assigned by each node to its children are disjoint, there is a unique path from the root of the tree along which nodes do computation on X All other nodes in the tree do not depend on the value of X₃- after conditioning on the release of the index sets of all children of nodes along the path. Composition along this path gives the result. This can be thought of as a novel combination of parallel and basic composition, and post-processing.
The challenge in our setting is that each node in the recursion tree does not partition its data among its children (the same edge weight can appear in multiple subinstances). A single data point may be sent to multiple children, so the number of nodes in the tree whose input includes X;- may be exponential in the depth h. We define restricted class of recursive mechanisms, which take in both sensitive dataset X and sanitized dataset Y. The overall recursive mechanism Mbennch is formed using two private subroutines Mreeurse and Msanitize At each recursive step, Mrecurse (X, Y) used to generate some partial output, the number of recursive children, and a set of sensitive and sanitized index sets I= (iz.... in) and (1) a sensitive dataset X,,,... Xt, which is subset of its parent's 's sensitive dataset X, and (2) sanitized input, which is the concatenation of any function of its parent's 's sanitized dataset Y and the j.
(fi.....3 .m)) for each recursive child. A child receives as input
output of the private computation Msuntiize X jn.-
We use parallel composition to refer to the fact that the union of outputs of an (e,8)-DP mechanism applied separately to disjoint subsets of sensitive dataset is itself (c, DD.
9

---

The key property of the mechanisms we define is bounded-overlap. parameterized by some constant For any index into the sensitive dataset X of the parent: (1): There is at most one child whose sensitive index set contains i. (2): There are at most l children whose sanitized index sets contain i. Theorem 2.2 (Informal Version of Theorem D.2). Let Miranch be a recursive mechanism as described above with bounded-overlap and maximum depth h with subroutines M Mecurse and Manitize which are (E1, 61) DDP and (E2, -D) respectively. Then, releasing the union of outputs of Mrecure and Mannitze over the entire recursion tree is (hεi + (h- 1)(22, hō1 + (h - 1)
Note that this generalizes the above example, where all children get disjoint subsets of the parent's s data by setting = Indeed, the high-level idea of the proof of this theorem follows the same argument, with more care taken to argue that, by sanitizing the overlapping data sent to a node's children, we can bound privacy along a single path from the root of the tree for any partieular index i". We ultimately prove the privacy of our GH-tree algorithm by the application of this general theorem. As described earlier in this subsection, the sanitization procedure is to add Laplace noise from the contracted node to all other nodes in S, subinstances. Then, each edge is only part of the private input to a single recursive child. A key observation is that the recursive GH-tree algorithm has bounded overlap with f = 2 as any given edge can only belong two such S. instances.
Acknowledgements
A. Aamand was supported by the VILLUM Foundation grant 54451. J. Chen was supported by an NSF Graduate Research Fellowship under Grant No. 17453. S. Mitrović was supported by the Google Research Scholar and NSF Faculty Early Career Development Program No. 2340048. Y. Xu was supported by NSF Grant CCF-2330048, HDR TRIPODS Phase II grant 2217058, and Simons Investigator Award. Part of this work was conducted while J. Chen and S. Mitrović were visiting the Simons Institute for the Theory of Computing.
References
[1] Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrovic, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Breaking the n 1.5 additive eгror barrier for private and efficient graph sparsification via private expander decomposition. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025, 138
[2] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Cut-equivalent trees are optimal for min-cut queries. In Proceedings of the 2020 IEEE 61 Annual Symposiun on Foundations of Computer Science (FOCS). pages 105-118. IEEE, 2020. 13, 16, 117, 131
[3] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Subcubic algorithms for Gomory- Hu tree in unweighted graphs. In Samir Khuller and Virginia Vassilevska Williams, editors, Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing (STOC), pages 1725-1737, ACM, 2021. doi: 10. (0.1144/3406325.. 1155344066253355173. 3451073. URL 1145/3406333 3451073. 13, 14, 15, 16, 17, 121
[4] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi. Thatchaphol Saranurak, and Ohad Trabelsi. Breaking the cubic barrier for all-pairs max-flow: Gomory- tree nearly quadratic time. In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 884 895, 10 2022. 15, 124, 136
[5] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. APMF < APSP? Gomory-Ho tree for unweighted graphs in almost quadda-q time. In Proceedings of the 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 1 1135- 125--144 146. IEEE, 2022. 13
[6] Amir Abboud, Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. All-pairs max-flow no harder than single-pair max-flow: Gomory-Hu trees in almost-linear time. In Proceedings of the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2204 2212. IEEE, 2023. 13, 15.18 18
[7] Arik Azran. The rendezvous algorithm: Multiclass semi-supervised learning with markov random walks. Proceedings of the 24th international conference on Machine learning, pages 49-56, 2007. 136
10

---

[8] Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou R3579X? anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th international conference World Wide Web (WWW), pages 181-190, 2007. 11
[9] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Joohnoon-Lindensranne trans- form itself preserves differential privacy. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 410-419, 2012. doi: 10.1 10.1109/FOCS.20022..
URL https: / /doi. org/ 10. 1109/FOCS. 2012.62 67. 12
[10] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Robert D. Kleinberg, editor, Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS), pages 87-96. ACM, 2013. 11
[11] Avrim Blum and Shuchi Chawla. Learning from labeled and unlabeled data using graph mincuts. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 19-26,
2001. 136
[12] Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, and Rajashekar Reddy, Semi- supervised learning using randomized mincuts. In Proceedings of the twenty-first international conference Machine learning, page 13, 2004. 136
[13] 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, Proceedings of the 51 International Colloquium Automata, Languages, and Programming (ICALP), volume 297 of LIPIcs, pages 27:1-27:20. Schloss Dagstuhl Leibnlnzzziiiiiieeete für Informatik, 2024. doi: L.4230LIPCCS..CCALPPP00 https:/ httts://doi.oor/100 4230/LIPICs. ICALP 2024 27, 14, 137
URL
[14] Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. Revealing network structure, confidentially: Improved rates for node-private graphon estimation. In Mikkel Thorup. editor, Proceedings of the 59th IEEE Annual Symposiun on Foundations of Computer Science (FOCS), pages 533-543, IEEE Computer Society, 2018. 199
[15] Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen. Min st-cut oracle for planar graphs with near-linear preprocessing time. ACM Trans. Algorithms, 11(3):1-29, 2015. 13
[16] Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Sándor P. Fekete and Anna Lubiw, editors, Proceedings of the 32nd International Symposium Computational Geometry (SoCG), volume 51 of LIPlcs, pages 12. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2016. doi: D04200LIPCCS..0C.G22002.. LIPICs. SoCG. 2016.0262222222 22. 117
URL https: ooo.orgg///0 11//1/00.42/////
[17] Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 1136-1 1 146. PMLR, 2021. 11
[18] Rishi Chandra, Michael Dinitz, Chenglin Fan, and Zongrui Zou. Differentially private multiway and k-cuut CORR, abs/2407.069 1,, 2024. doi: 10:48550AAXXV22200006911 URL https: 485.00/5555//aii / 240. 06911. 136
[19] Chandra Chekuri. Approximation Algorithms, Lecture 7, 2009. URL htRps//tps//correeee
grainger bedingeriillioof illinoiis......
/eectuurrrreeeeteeeeeeeeeeeeeeee pdf. Url: https:
//courses.. grainger.... illinois..... www.inois.educseeeeeeeeee http://///eeaeppp////eeeeeee/eee http:///llcctueeeeeurrrer.e. 7ppff
Accessed: August 1, 2024. 137
[20] Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. In Conference on Learning Theory, pages 35-1. JMLR Workshop and Conference Proceedings, 2012. 136
[21] Chandra Chekuri and Kent Quanrud. Isolating cuts, (bi-)sabmodullarity and faster algorithms for connectivity. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP),
11

---

volume 198 of L/Plcs, pages 50:1-50:20 Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021. doi: (044200LIPPCS..CAALP2202
URL htttps://do..org// 201.0/4230/1PPP
ICALP. 2021 50. 18
[22] 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 ACM-SIAM Symposium Discrete Algorithms (SODA), pages 5040-5067. SIAM, 2023, doi: 10. 1 1113/19997810 1977554.CH1 URL htthtt/s///ol org/ooo.///oo 111.:/1.1111111111111111111 99771//1777711117755557 ch184. 11, 14, 120, 137
[23] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623. IEEE, 2022. doi: 10. N0.1109/FCCS4455.000 202.4455.2222000666 URL httthst////o...... org/10. 1109/F0CS544$3 2022.00064 12, 136
[24] Vincent Cohen-Addad, Frederik Mallmann-TTemm and David Saulpie. Community recovery in the degree--httroggeneous stochastic block model. In Conference on Learning Theory, pages 1662-1692. PMIR, 2022. 136
[25] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022. 12
[26] Chris Culnane, Benjamin I. P. Rubinstein, and Vanessa Teague. Stop the open data bus, we want to get off. CoRR, abss/1908.0000 0000040 2019. URL http://arxiv org/ abaaaba//1000 19008 10bb/999.00004, 05004. f1
[27] William H. Cunningham. Minimum cuts, modular functions, and matroid polyhedra. Networks, 15(2):205-215, 1985. 117
[28] Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864-894, 1994. 136
[29] Mina Dalirrooyfard, Slobodan Mitrović, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. In Proceedings of the Advances in Neural Information Processing Systems 36 (NeurlPS), 2023. 11, 12, 13, 14, 15, 18, 119, 136, 137
[30] George B. Dantzig. Application of the simplex method to a transportation problem. Activity analysis and production and allocation, 1951. +2
[31] Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdì Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposi- tion, low out-degree ordering, and densest subgraphs. In Proceedings of the 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 754 765. IEEE, 2022.
11
[32] Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Improved differentially private densest subgraph: Local and purely additive. arXiv preprint arXiv:2308.103: 10316, 2023. 1
[33] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the sl Annual ACM Symposium on Theory of Computing (STOC), pages 371-380, 2009. 118
[34] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Compul. Sci., 9(3-4):21 1-)2412-11-7,, 2014. 13, 15, 118, 137
[35] Cynthia Dwork, Krishnaram Kenthapadi, Frank MeSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 486-503, Springer, 2006. 15
12

---

[36] 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, Proceedings of the 3rd Theory of Cryptography Conference (TCC), volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. doi: 10. 16818781 14. URL https: //doi. orgil.or//// 10. 11.00001110 0110000011111111111111 14. 11, 118
[37] Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the I 14th Annual ACM-SIAM Symposiun Discrete Algorithms (SODA), pages 560-578, 2020. doi: 34. 11, 12, 119, 138
.788161 1975994.34, URL
https://doi: org/ 10. 11171111111 (11.1/71..9111119995881819
[38] Peter Elias, Amiel Feinstein, and Claude Shannon. A note on the maximum flow through network. IRE Trans. Inf. Theory, 2(4):117-119, 1956. 12
[39] Chenglin Fan, Ping Li, and Xiaoyun Li. Private graph all -ll--arwwis--shortttt-pade distance release with improved error rate. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Proceedingg of the Advances in Neural Information Processing Systems 35 (NeurIPS), 2022. URL http:://tppppp mips. ctppscccpppae wttpp/ccpppppppppppeepepppppee Seaper_fiiee www.eeeaeeeeeeeee 2aless/apprr/222/ /2022/ CestrractCooffreent html. 11, 14, 137
[40] Gary William Flake, Steve Lawrence, and C Lee Giles. Efficient identification of web com- munities. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 150-160, 2000. 136
[41] Lester Randolph Ford and Delbert R. Fulkerson. Maximal flow through a network. Can. Math., 8:399 40399-404, 1956. 12
[42] Julia Gaudio and Nirmit Joshi. Community detection in the hypergraph sbm: Exact recovery given the similarity matrix. In The Thirty Sixth Annual Conference Learning Theory, pages 469-510. PMLR, 2023. 136
[43] Julia Gaudio, Miklos Z Racz, and Anirudh Sridhar. Exact community recovery in correlated stochastic block models. In Conference on Learning Theory, pages 2183-2241. PMLR, 2022. 136
[44] Ralph E. Gomory and Tien Chung Hu, Multi-terminal network flows. J. Soc. Indust. Appl. Math., (4):551-570, 1961. 13, 14,15
[45] Andrew Guillory and Jeff A Bilmes. Label selection graphs. Advances in Neural Information Processing Systems, 22, 2009. 136
[46] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedingy of the 21st Annual ACM-SIAM Symposium on Discrete Algorithums (SODA). 2010. doi: 10. 11/.////99111197777 / aodoi..or//100
URL https:
90. 12, 13, 14, 15, 119, 137
[47] Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Ronald Cramer, editor, Proceedings of the 9th Theory of Cryptography Conference (TCC), volume 7194 of Lecture Notes in Computer Science, pages 339-356. Springer, 2012. doi: 10. 10.10077977--3-442 3-642-28991--9 23336444229991-11... 11, 12, 13, 119, 137
URL https:///oiiii http:/do..oorggg// org/10.10000
[48] Steve Hanneke. An analysis of graph cut size for transductive learning. In Proceedings of the 23rd international conference on Machine learning, pages 393-399, 2006. 136
[49] Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, and Anand Bhalgat. An mmm) Gomory-Hu tree construction algorithm for unweighted graphs In Proceedings of the 39th Anmual ACM Symposium on Theory of Computing (STOC), pages 605-614, 2007. 1
[50] Harris and S. Ross. Fundamentals of a method for evaluating rail net capacities. Technical report, RAND Corporation, Santa Monica, CA, 1955. 12
13

---

[51] 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 Xindong Wu, editors. Proceedings of the 9th IEEE International Conference on Data Mining (ICDM), pages 169-178. IEEE Computer Society, 2009. 11
[52] Chester Holtz, Pengwen Chen, Zhengchao Wan, Chung- Cheng, and Gal Mishne. Con- tinuous partitioning for graph-baset based semi-supervised learning. In The eiihth Annual Conference on Neural Information Processing Systems, 2024. URL httttttt//ppprreeeeeet //ppnr/vi/e/eeeeee.e www.orruunnn-hhhhhp5p0.0m.. 136
[53] Palak Jain, Iden Kalemaj. Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. Proceedings of the Advances in Neural Information Processing Systems 36 (NeurIPS), 36, 2024.
11
[54] Svante Janson. Tail bounds for sums of geometric and exponential variables. Stat. Probab. Lett., 135, 09 2017. doi: 10.1016fj.pl..017.11... 11..00077..111.. 118
[55] Thorsten Joachims. Transductive learning via spectral graph partitioning. In Proceedings of the 20th international conference on machine learning (ICML-03), pages 290-297, 2003. 136
[56] David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Vijaya Ramachandran, editor, Proceedings of the 4th Annual ACM/SIGACT- SIAM Symposium on Discrete Algorithms (SODA), pages 21-30, ACM/SIAM, 1993. URL http:/ //dl. acm. acm.org/ citation. wtfmidd .136003.3 15
[57] Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. ACM Trans. Database Syst. 39(3):22:1-22333, 2014. doi: 10.1145/ 261 1523. URL https: http:///oooooo///////// 10. 1145/ f1
[58] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. In Amit Sahai, editor, Proceedings of the 10th Theory of Cryptography Conference (TCC), volume 7785 of Lecture Notes in Computer Science, pages 457-476. Springer, 2013, 1
[59] Aleksandra Korolova. Privacy violations using microtargeted ads: A case study. In Proceedings of the 2010 IEEE International Conference on Data Mining Workshops (ICDMW), pages 482. IEEE, 2010. 11
[60] Samuel Kotz, Tomasz J. Kozubowski, and Krzysztof Podgórski. The Laplace Distribution and Generalizations: A Revisit with Applications to Communications, Economics, Engineering, and Finance. Birkhäuser, 2001. ISBN 978081 17111641166 7641665. Proposition 2.2.2, Equation 2.2.8. 126
[61] Jason Li. Preconditioning and Locality in Algorithm Design. PhD thesis, Carnegie Mellon University, USA, 2021. 15, 16, 17, 18, 117, 123, 124, 129, 130, 136
[62] Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows
In Sandy Irani, editor, Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 85-92. IEEE, 2020. doi: 10.1 10.1109/FCS446000.00 200.:7000.2220000000 00 URL https://doi. org wttpg/....1.////. 1000//0000/000000... 2020. 00017. 12, 14, 16, 17, 117, 121, 125
[63] Jason Li and Debmalya Panigrahi. Approximate Gomory-Hu tree is faster than n 1 max-flows. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages
2021. 13
[64] Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. A nearly optimal all-pairs min-cuts algorithm in simple graphs. In Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1124-1134. IEEE, 2022. 15
[65] Daogao Liu. Better private algorithms for correlation clustering. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of the 35th Annual Conference on Learning Theory (COLT), volume 178 of Proceedings of Machine Learning Research, pages 5391-5412, PMLR, 2022. URL https:/ / /ttp///eeoogg....///// mlr, www...pres//ee. ppress/v17et www.///////n/ html. 136
14

---

[66] Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph ap- proximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Al- gorithms (SODA), pages 1019-1049, 2024. doi: 10. 01177/7981111177122553
URL
https://dol http//i...rrg/.////// 1ttp//1..117/111111 TT1.1//7111911119199991119 39. 11, 12, 13,
[67] Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Almost linear time differentially private release of synthetic graphs. arXiv preprint arXiv:2406.02/55, 2024. 12, f3
[68] Xizhi Liu and Sayan Mukherjee. Tight query complexity bounds for learning graph partitions. In Conference on Learning Theory, pages 167-181. PMLR, 2022. 136
[69] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Correlation clus- tering with noisy partial information. In Conference on Learning Theory, pages 1321-1342. PMLR, 2015. 136
[70] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94-103. IEEE, 2007. 11, 15
[71] Karl Menger. Zur allgemeinen kurventheorie. Fundam. Math., 10(1):96-115, 1927. 12
[72] Sagnik Mukhopadhyay and Danupon Nanongkai. A note on isolating cut lemma for submodular function minimization. arXiv preprint 1rXxv:2103.15724 2021. 18
[73] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy matrix inversion. Comb. 70)):0051113 1987. doi: 10. 10700077/00 URL https: /doii org/
10. NO.1007/BFO2579206 117
[74] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets, In Proceedings of the 2008 IEEE Symposium on Security and Privacy (SP), pages 111-125. IEEE, 2008. 11
[75] Debmalya Panigrahi.
Gomory-Hu trees. In Encyclopedia of Algorithmss pages 858-861, URL httptttts////iorrrggrge 10007/ 1007/
Springer, 2016. doi: 978- 190---1499--8888 168_11611111 13
[76] Richard Peng. He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! In Conference on learning theory, pages 1423-1455. PMLR, 2015. 136
[77] Seth Pettie, Thatchaphol Saranurak, and Longhui Yin. Optimal vertex connectivity oracles. In Stefano Leonardi and Anupam Gupta, editors, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 151-161. ACM, 2022. doi: 10.1145/ 35 151995.3519995.. URL htttps://dot org/10. 1145/3519985 3519945. 12
[78] Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith, and Marika Swanberg. Dif- ferentially private sampling from distributions. In Mare Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Proceed- ings of the Advances in Neural Information Processing Systems 34 (NeurIPS), pages 28983-28994, 2021. URL https://proceeddings wwwpeddiiinnnnnnniiieeeeeee wttp:pp..ppppppe/eeeeee ///22//hhh/////// 5255921551166222266866666 www.:eeeeeeeae--aaaaaaaaaaaaaaae html. 11
[79] Shota Saito and Mark Herbster. Multi-class graph clustering via approximated effective resistance. In International Conference on Machine Learning, pages 29697-29733. PMLR. 2023. 136
[80] Huzur Saran and Vijay V. Vazirani. Finding k-cuts within twice the optimal. SIAM J. Comput., 1401):101-108, 1995. 136, 137
[81] Adam Scalfon. Shortest paths and distances with differential privacy. In Proceedings of the 35th ACM SIGMOD-SIGACT SIDC-IGATTSIGA Symposium on Principles of Database Systems (PODS), pages 29 41, 2016. 14, 120, 137
[82] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In Proceedings of the 2017 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2017. 11
15

---

[83] Thomas Steinke. Composition of Differential Privacy & Privacy Amplification by Subsampling. arXiv e-prints, art. arXiv:2210.00597. October 2022. doi: 10.48500/rX11.220000557.7 13
[84] Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In The 24th International Conference on Artificial Intelligence and Statis- tics (AISTATS), pages 1171-1179, 2021. URL http://proceeddings mlr. press/v130/
upadhyay21a. html. 12
[85] Jan den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and fi-regression in nearly linear time for dense instances. In Samir Khuller and Virginia Vassilevska Williams, editors, Proceedings of the 53rd
Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 859-869. ACM, 2021. URL / org/ 10. 1011111//444430 3451108. 136
doi: 10.1 (...144//406325355511
[86] Nate Veldt, David Gleich, and Michael Mahoney. A simple and strongly-local flow-based method for cut improvement. In International Conference on Machine Learning, pages 1938- 1947. PMLR, 2016. 136
[87] Jun Wang, Tony Jebara, and Shih-Fu Chang. Semi-supervised learning using greedy max-cut. The Journal of Machine Learning Research, 14(1):711-800, 2013. 136
[88] Tianyi Zhang. Gomory- Hu trees in quadratic time, arXiv preprint 12.00221/2.00042, 2021. 13
16

---

A Preliminaries
A.1 Notation
We use G = (V, E. w) to denote weighted, undirected graph with vertex set V. edge set F and edge weights w. For a subset of vertices S S V. we use ÖgS, or simply äs when G is clear from context, to denote the set of edges between S and V \ S. For a set of edges Q S E, we use w (Q) to denote the sum of the weights the edges Q. For a set of vertices S C V, we use w(S) to denote w(OS), for simplicity.
For s,t E V, we use (s, to denote the Min-s-t-Cur value specified graph G. When clear from context, the subscript G might be omitted. Throughout our computation. we assume that all Min-s-t-Cuts or Min Isolating Cuts are unique. This is without loss of generality by adding small noise to the edges and applying the isolation lemma [73] (see also [16, 2)). 10 For >> O, (l(nn) is logarithm base-2 and In(n) is logarithm base-e. Unless specified, high probability refers to failure probability of at most 1/n 0(1) where we can pick the (1) factor to be an arbitrarily large constant of our choice.
Notation
Meaning
Reference
8 0,8,8 VV
privacy parameter
Definition
set of edges between S and V S in G
Appendix A.1
(Q), S E
sum of weights of edges in Q in G' sum of weights of edges in 0S in G min s-t value in G isolating cut for vertex u (G(()) Sw privatized versions of wa(() and S..
Appendix A.1
(G()), V
Appendix A.1
to(s,t)
Appendix A.1
Su
Definition 2.1
Algorithm
Table A summary of our notation throughout the paper. When clear from the context, we drop the subscript of the graph G = w.).
A.2
Graph Cuts
In our algorithms, we use the notion of vertex contractions, which we formally define next.
Definition A.1 (Vertex contractions). Let X C V be a subset of vertices of the graph G (V, E, w) Contracting the set X into vertex is done follows: we add vertex to the graph and remove all the vertices in X from the graph. Then for every vertex v E X, we add an edge from x to w with weight Ex'ex w w(x'v). Note that if none of the vertices in X has an edge to v, then there is no edge from x to C.
We the submodularity property of cuts in many of proofs.
Lemma A.1 (Submodularity of Cuts [27]). For any graph G (V, w), and any two subsets
S,T C V, it holds
w(S) + w(T) 2 w(SUT) w w(SnT).
Recall the definition of Min Isolating Cuts problem (see Definition 2.1). We use the following simple fact.
Fact A.1 ([62]). Given set of terminals R S V, there always exists a set of minimum isolating cuts {S, v E R} such that the cuts are disjoint.
Definition A.2 (Gomory-Hu Steiner tree [61]). Given a graph G = (V, E, w) and a set of terminals U CCV. V, the Gomory-Iuu Steiner tree is weighted tree T on the vertices U, together with a function
The isolation lemma involves adding noise to existing edge weights. This noise can be bounded in magnitude to be at most 1/ poly (n), so scaling the weights down by a (1+ 1/ (n)) factor yields the normal neighboring detinition for DP.
17

---

f: V. + U, such that: For all s,t E U. consider the minimum-weight edge ue on the unique s-t path in T. Let Up be the vertices of the connected component of uu containing Then, the set (U)) CV is the Min-s-I-Cut, and is value is wr(wv).
Note that for U =V f())
the Gomory-Hu Steiner tree equals the Gomory-Hu tree.
A.3 Concentration Inequalities
Theorem A.1 (Sums of Exponential Random Variables ([54, Theorem 5.1))) Let X1...., independent random variables with X; ~ Exp(a;). Let Jr Ei a, be the expectation of the sum of the X; 's and let a min; ag.. Then, for any 2 1,
.......Xy, Xx be
P xi
Σ
S expl- a" 1ut Int)]
Corollary A.1. Let X1...., XN be independent random variables with X; Exp(a) for some real mumber a > 0. Let N/a be the expectation of the sum of the X; 's. Then, for any T 2 2μ,
Σ X T
exxp(-oT/10).
Proof. Apply Theorem A.I with a" = a and = T/μ, μ. we obtain
N
P
X; T
expl- -a a u(l - In()
= expl- -N(N--N( 1- 1- -((-I--n(+(hnt//))
S exp( (Nt(-)N
(as t 2 2)
= exp(-aa/11).
A.4 Differential Privacy
In this paper, focus weighted version of edge differential privacy. the end of this section, we discuss why this choice of neighboring graphs is made as well as some connections between notions of neighboring graphs.
Definition A.3 (Edge-Neighboring Graphs). Graphs G (V, E, w) and G' = (V, w') are called adge-neigh if there is uv E V2 such that (wg(wv) wer (wv) I 1 and for all u''d + wv, u'u' V² we have we (o''v')) (u''(' Note that w(u"v")
for all non-edges u"
Definition A.4 (Differential Privacy [36]). A (randomized) algorithm i (e, -'--vvvtete (or (s,0) 6)- DP) for any neighboring graphs G and G' and any set of outcomes O c Range (A) it holds
[A(G) E O) S e ([A(G') E + +
When 8 0, algorithum A pure differentially private, or E-DP.
We now state some standard properties of differential privacy which we will utilize in our algorithm design and analysis.
Theorem A.2 (Basic composition [36, 33]). Let Ei....,EE > and Sy..... 8, 2 O. If we run (possibly adaptive) algorithms where the i-th algorithm is (ex, -DP, then the entire algorithm is DDP
(61 + + Ety 81
Theorem A.3 (Laplace mechanism [34]). Consider any function f which maps graphs G to Rdd with the property that for any two neighboring graphs G, G', [lf (( f(G' 1 & A. Then, releasing
f(G) + (X1,...;
where each X; is i.i.d. with X; Lap( A/E) satisfies e-DP.
18

---

G
G
2(
2(n
2(n
2(n
2(xz
2(x
This example describes weighted graphs, G and G", that differ by single edge {u, v): G is a path, while is a cycle. The numbers next to the edges are their weights. Note that both graphs have n distinct min-cut values. However, the min-cut values in G are {2, 4, ...... 2(n 1)}. while the min-cut values in G" are {3.5..... 2(n + 13. Thus, the min-cut value sets of these two neighboring graphs differ in entries.
Figure 3:
Note that any w(S) for C V has sensitivity A as changing one edge weight by one can change the sum of subset of edge weights by at most one. We now state a result on privately releasing an approximate Min-s-f-Cut for single pair of vertices s,t.
Theorem A.4 (Private Min-s-t-Cuu (291). Fix any E O. There is an O) algorithm PrivateMiinsst-Cuu(( (V, E. w), s, t,e) for + V that reports s-t cut for n-vertex weighted graphs that is within (²)) additive error from the Min-s-l-Cut with high probability.
By standard techniques, we can also use Theorem A.4 to design an (e, D)-DP algorithm for computing an approximate Min-S-T-Cut for two disjoint subsets S, T C V that is within O additive error from the actual Min-S-T-Cut (e.g., by contracting all vertices in S and all vertices in to two supernodes). Furthermore, our final algorithm is recursive with many calls to Private Min-S-T-Cul for graphs with few vertices, and it is not enough to succeed with high probability with respect to n. The error analysis of [29] shows that the error is bounded by the sum O(n) random variables distributed as Exp(e). Using Corollary A. yields the following corollary:
Corollary A.2 (Private Min-S-T-Cut, Fix any > O, there exists (c, 0)-DP algorithm PrivateMin-S-T-Culle
(V, F,E,E,,,, S, T,,,, for disjoint S,T C V that reports a set C C V where S and CnT 0, and w (dC') within O [++ogg(1/))
additive ervor from the true
min-S-T-cut with probability at least 1 - B.
A.5
On various notions of neighboring graphs
For graph data, there several choices of neighboring datasets with very different semantics for the privacy they correspond to.
At one extreme are vertex- neighbrnngg graphs, where neighboring graphs differ arbitrarily in the edges incident on a single vertex, c.g., [14]. Semantically, each vertex corresponds to person, and vertex differential privacy protects the data of that individual person. While this offers broad protection, this notion of privacy is simply too restrictive for cut problems. has been found to be useful in simpler problems, such estimating the edge density of random graphs. However, the value of any cut can change arbitrarily between neighboring graphs, so no approximation of any cut value is possible while maintaining privacy.
We consider edge-neighboring graphs, which the standard for cut problems the literature, see, e.g., [46, 47, 37, 66, 29]. It is the strongest form of privacy for which we can get meaningful approximation to cut problems. For unweighted graphs, neighboring graphs are those in which a single edge has been added/removed. For weighted graphs, two related notions considered: where a single edge can change in weight by and where all edges can change total & distance 1 II Semantically, these notions of privacy are meaningful if individuals impact the existence of edges and the size of edge weights. We use the former definition but note that, as is often the case, our result applies in both settings. We outline the reduction below.
Note that both of these capture the unweighted case as zero weight edges are equivalent to edges not belonging to the graph in the context of problems.
19

---

Let A be an algorithm satisfying the former notion of edge differential privacy (changing a single edge by weight 1) with an approximation error that depends linearly on 1/E and scale-invariant in that it does not explicitly depend on the scale of the edge weights in the graph. Say two graphs have
edge weight vectors wa, way E (R))) with ||w - wer Il S Let - wG - WG', and let C be some constant such that CA is integer-valued we assume that such a constant exists either due to finite precision of the weights or by rounding the weights to finite precision with arbitrarily small loss. Note that ||CA||| < C. By group privacy, running A on graph with edge weights Cwg will preserve a Ce-DP guarantee with respect to all graphs which are formed by starting with Cwg and iteratively changing C' edge weights by 1. In particular, this holds for Cugy Rescaling the solution by 1/C yields a reduction of error by a factor of 1/C at the cost of increasing the privacy parameter by a factor of C. As the error of A scales linearly in 1/e, rescaling the privacy parameter by factor of C' yields an equivalent error/privacy tradeoff for the & notion of neighboring graphs.
We note that yet more restrictive notion of privacy is used for privacy in the context of shortest path problems, e.g., [81, 22]. the context of shortest paths, zero-weight edge is not the same as a non-edge: non-edge is equivalent to edge of infinite weight. Therefore, standard notions of edge differential privacy do not allow for any approximation to path lengths. The notion considered in these shortest path problems is edge weight differential privacy, where the unweighted topology of the graph is fixed and made public while the weights on each edge are private. Specifically, neighboring graphs have the same edge set E but differ in weights those edges in & distance most 1. This is in contrast to the former notion of edge differential privacy, where two graphs are neighboring if one contains edge of weight and the other has non-edge in that location.
B Private Min Isolating Cuts
In this section we prove Theorem 2.1. In fact, we prove stronger version given by Lemma B.1. The steps in the algorithm that differ meaningfully from the non non- private version are in color. We refer to Appendix A.1 and Table for the definitions of our notation.
Algorithm 1: Privatt/MinlsolaatnngCusss
R,U,,
Initialize W, & V for every E R 2 Identify R with {O..... |R] - 1}
for i from 0 to [[[[ 1)] do
A; + E R: mod 26+1 < 2
4
G PrivateMin-S-T-Cuus
A., R \ A,, /lgg -)) 3))
W, + W,, n C₁ for every E E A,
W, W, n (V CG) for every E R A
end
9 for r E R do
10
Let H, be G with all vertices in V W, contracted, and let 4 be the contracted vertex
In Hy, add weight Bμ (a++)(11/2)) (IR)) between every vertex in W, n U and t, for some s|0]
sufficiently large constant BH
12 end H. + UPER dr, C ---PivateMinnS---Curfe R, (Ir)vER, 33,,8/0gg11) + +3)
15 return {C n WrhreR
Lemma B.I. On graph G with n vertices, set of terminals R C V. another of vertices U V. and a privacy parameter e, there is an (e, O)-D algorithm irivateeiilsolatingg.nn that returns a set of Isolating Cuts over terminals R. The total cut values of the Isolating Cuts is within additive error O((n lg(1/B)) (g)))))(()))))))))) from the Min Isolating Cuts with probability 1 1.
&.
Furthermore, suppose the Min Isolating Cut for any terminal E R contains most U. vertices from U. In that case, the Isolating Cut for returned by the algorithm will, with probability B. contain at most 0.9[U] vertices from U.
20

---

Proof. The algorithm is presented in Algorithm 1. On a high level, the algorithm follows the non- private Min Isolating Cuts algorithm by [62, 3], but replacing all calls to Min-S-T-Cui with private Min-S-T --t- from Corollary A.2. One added step is Line 10, which is used to provide the guarantee that if the Min Isolating Cut for terminal r E R contains small number of vertices in U, then the isolating cut for terminal r returned by the algorithm also does.
Next, we explain the algorithm in more detail. For every E R. we maintain set W. that should contain the r-side of a cut seperating r from R {r} obtained in the algorithm. In each of the
[[g([R) - 1)] + 1 iterations, we find a subset A, S R. and find cut that separates A, from R \ A, Let C2 be the side of the cut containing A,. Then for every E A,, we update W, with W, n C2 for every r R\, A,, we update W, with WV (YA)
Ct). The choice of A is so that every pair 71, 12 E R are on different sides of the Min-S-T-Cut in at least one iteration; as a result, W, O R = {r} for every r E R after all iterations.
Next, for every r E R. the algorithm aims to compute a cut separating r from R \ {r), where the side containing is inside W,. This can be done by contracting all vertices outside of W,, a vertex t, and computing private Min-r-t,-Cutt To incentivize cuts that contain fewer vertices in U on the side containing r, the algorithm adds an edge with positive weight from every vertex in W,, n U ty. Finally, these private Min-r-t,-Cuu instances can be solved at once by combining them into a single graph H.
Considering the first for loop in the algorithm, The only parts that depend on the edges or edge weights the calls to PrivateMin-----CC
Privacy analysis.
Each call to PiivateMinSS---Cu is (e/ (1g R + 3), D)-DP and the number of calls is [gg( R 1)J + 1, so this part of the algorithm is log [ +1
log 11 +3 C
DP via basic composition (Theorem A.2).
Next, note that the sets W, are private since they are obtained from postprocessing the lg J privately computed min cuts C. Furthermore, the sets W, form a partition of V. This implies that an edge in the initial graph contributes its weight to at most two edges in H. Namely, an edge internal to some W, appears only in H, and an edge between some Wr, and W is only contracted into an edge in Hy and an edge in Hp. Thus, the sensitivity of H. is 2, so running SeratteMiinS---C-. on H is 2e 2l/(lo R 3-DP. Hence, the overall algorithm is c-D..
Error analysis. First, we analyze the error introduced by the for loop starting at Line 3. Let {S,)re be the (non-private) Min Isolating Cuts for terminals in R. which are only used for analysis purposes. Recall by Fact I, we can assume ) R are disjoint. Take iteration of the for loop and let { {W, Jrv n be the values of W,'s 's before the start of the iteration, and let (W)rren denote the value of W,'s 's at the end of the iteration.
Recall that with probability 1- 1- (1g( ( Rl) +3), the PrivateMinn-ST-CCT algorithm Corollary A.2 has additive error O((n + [g(([g((/R)) + (I) in the following analysis, we assume all calls of the PrivateMin-S-T-Cut algorithm have additive error O(nn (1) (((()))))) (which holds with probability 1 by union bound).
+3)/E) Ig lg) Hence,
We show the following claim:
Claim 1. It holds that
Σ w (W' nS,) S Σ w [ (( FR
rER
Proof. We first show Σ ErEA, w (W S,) S ErEA, w + Let SA, = USEA, (W, S.). By Lemma A.1,
w(SA.) + w(C) 2 +
Recall that with probability 1 1- (3g((()))))))) 3), C, is within O((n+g((()( (3))))))))))(()))))))))))
3)/e) = ((n + lg(1//)) lg(( R)) of the minimum cut separating A, and R Ag, by the guarantee of Corollary A.2, and note that SA, U U., is also a cut separating A, and R \ A,. Therefore,
w(C+)) wS U..) + O( + lg(1 (R))e).
(2)
Combining Equations (1) and (2), we get that
w(S n C.) < wS. + O(I + lggggg((1)))))) Ig( RR))
(3)
21

---

Therefore,
Σ rE4,
w (W, nS,) E
u wW,ns,,CC)
rEA:
(Umrnnsnnc)+
Σ w w ns₁ nC;) x (W,, ns, n (.)))
rEA:
S WSA +
E n
w (E ((Wr, n.,))) x (Wr, n.S)))))
+ (O
Σ
w (En n.S,)) (W,, n (s,)))
(by Equation (3))
Σ w wW, + +(nn0(((n0))) lg(1/3)) +0 (((1))))))))((((/))))))
rEA.
By an analogous argument, can show EremA n S Erems w (W, (W,)
O ((nlg((R))/s)) Summing up the two inequalities gives the desired claim.
By applying Claim repeatedly, we easily show the following claim:
Claim 2. At the end of for loop starting at Line 3, Eren (W, s E ((,)) +0()) lg(1/3)) lg ((R)))/s).
Proof. Before the for loop starting Line 3, have W, V for every R. so Erer wWW, n S,) = Eren wSS). Claim 1 shows that after each iteration of the for loop. the quantity EvER w(W, n S,) does not increase by more than O((n + lg(1/))) lg((R))/s). As there are O(g(( iterations, we get that at the end of the for loop.
Σ WW, n.)))) S Σ w(S,) + O(In ((2)))
The following claim is simple observation:
Claim 3. At the end of the for loop starting at Line 3, r E W, for every r E R and distinct W, 's are disjoint.
Next, we show that the Min-r-t,-Cur values in H, are close to the Min Isolating Cut values:
Claim 4. Erer Nn, (r,b)) < Eren (S,) + O((n lg(1/8)) lg (1R1)/e).
Proof. We have that
Σ AH. (r, (,) S
Σ
WH. (W, n S.)
TER
FER
Σ
rER
+ +0((n +0((+++(((1)))))((1)))) wa(W, wa(W,,
AER
(as {StTer are disjoint)
< Σ ma(S,)) + +0((n +0( [g(())))))))))
(by Claim 2)
rER R
22

---

Because of Claim 4, and the guarantee of Corollary A.2, the final cuts C n W, returned by the algorithm will have the property that
Σ TER
EwH, (C, S
(r,4)) +
rER
rER
Furthermore, WarC n (W,) WH, (n, W,) as we only add positive weights to H, compared to G, we further get
Σ EwlCCnW, S
Σ +
rER
which is the desired error bound.
Additional guarantee. Finally, we need to show that if nU < 0.50 for some r E R, then with probability - 3, the returned isolating by the algorithm C W, has C W, n s 0.9U. Again, we can assume all calls of the PrivateMin-S-T-Cur algorithm have additive error O((n (1((1/3) (g(( /e)). As is cut returned by the PrivateMin-S-T-Cuu algorithm separating R and (lrhee and (C \ W,) U (S, n W,) is also a cut separating R and (4rrER we have WH S wx((C)
+ O((n [g((//))((((
By removing cut values contributed by H,, for r' # r from both sides, get that WH, (C W,) S wH, (S, n W,) + O((n + (g( R)))/s). Rewriting the cut values in terms of the edge weights of G instead of H, (recall the weights of G and Н, are related as shown in Line 11), the above becomes
w(C n W,) + (Bu - + (4=+44/////))))(((///////eneen//
< w05.111111....ae0000000000000000 ())))))) (By Claim 2)
w (Bn ( (1tp:4/hhhhieeaaaaeee00/05511140
Because w (C n W,) 2 (S,) by definition of S,,, the above implics
O((n + (
Cnw,
+ +18,nw
Bu (n lg(1//)) (g(()))))
< 0.44 + (S,
(By setting By large enough)
< +
< 0.9
as desired.
C Core Recursive Step
We now describe key subroutine, outlined Algorithm 2, used to compute DP Gomory-Hu tree. The high-level goal to use Min Isolating Cuts to find minimum cuts that cover a large fraction of vertices in the graph. The overall structure of this algorithm follows that of the prior work [61] with several key changes to handle additive approximations and privacy. The inputs to Algorithm 2 are the weighted graph, a source vertex s, a of active vertices U C privacy parameter e, and failure probability B. The steps that differ meaningfully from the non non-private version developed in [61] are color. To obtain DP version of this method, Algorithm 2 invokes the DP Min-s-t-Cut and the DP Min Isolating Cuts algorithm; the latter primitive is developed in this work in Appendix B. In the original non-private algorithm, isolating cuts St are included in D' if the set St corresponds to the side of the Min-s-o-Cut, i.e., (S)) A(s, v). The analysis in prior work relies on this equality, i.e., on wo( (S() and A(s, v) being the same, in crucial way. Informally speaking, it enables the selection of many Min Isolating Cuts of the right size. In our case, since the cuts and their values are released
23

---

Algorithm 2: PrivateHHThheeeep((G (V, w), ,,), U,)
Tiso (n+1g(1/8)) lg (161))
and T values +- 0 |0| 10110100/88)
(s t (s, + Lap 4[10] for all E EU {s}
Initialize RD +- U
4 for i from 0 to [gg [ do
Call PrivateMinlsoaatnnguuks G, R', U. 2[ U1J+1]+ Del (Algorithm obtaining
disjoint sets S
/* v ranges over vertices in R */
vi(()) - (S:) + Lap 801 for each R2 (8)
Let D C U the union of S nu over v E RR {s} satisfying
w < \(s v) (2(1lg [t]]] - + 1) I and SS n < (9/10)JU)
R²+1 + sample U where each vertex in (s) sampled independently with
probability 2 i+1, and sampled with probability 1
end
10 return 1) (the largest set D'), R (the set of terminals v E Rt {8} satisfying the conditions on Line 7), and sets S for R.
privately by random perturbations, it is unclear how to test that condition with equality. On the other hand, still would like to ensure that many isolating cuts have "the right" size. Among our key technical contributions is relaxing that condition by using a condition which changes from iteration iteration of the for-loop. The actual condition we use is
(4) on Line 7 of Algorithm 2 where I and I values are upper bounds on the additive errors of the approximate Min Isolating Cuts and the approximate Min-s-o-Cut values, respectively.
((t) I \(s v) + (2( UI] - + 1)T values
When using Equation (4), we also have to ensure that significant progress can still be made, i.e., to ensure that both (a) we will find large set De which is the union of approximate Min Isolating Cuts $ satisfying the condition above and (b) none of the individual Š which we return are too large as we will recurse within each of these sets. A new analysis uses this changing incquality to show that the former true. For the latter, we utilize the special property of our PrivateMinnsolatingCuu in Appendix B that forces an approximate isolating cut to contain at most 0.9]U] terminals if there exists an exact isolating cut of size at most /U/ We now turn to the analysis.
C.1 Correctness
As in prior work [61, 4], let D C U. {s} be the set of vertices e such that if S is the side of the Min-s-u-Cut, SSt nu| < /U//2.
Lemma C.1. PrivateGHHTreStep( U, s, (Algorithm 2) has the following properties:
Ler = (n Ig" ((U))/E and waises = Cg(UU /B) for large enough constants C1, C2. Let (S") VeRR be the optimal Min Isolating Cuts for terminals RC (by Fact A.I, these are disjoint without loss of generality). Let R be the set of vertices for which Algorithm 2 returns St. Then with probability at least 1 - O(8), the sets {Št v E R²) returned by Algorithm 2 approximate Min Isolating Cuts and approximate Min-o-s-Cuts:
Σ VER
w(S)) w((s)) S Tiin ison
and, for all U E R",
w(S)) M(s u) $ 2( [g |U]| + 1) + 2T valner-
. returned by the algorithm satisfies
D
B|| = Ω
Ig [0'
24

---

To prove this, we will need the following helpful definition and lemma. Let X be random variable for the number of vertices in U added to D by set :
Sst nul
if E R and S nu & (9/10)(U and
x
((S)) S ((8 + (2(1)g i) 1)T + values
(5)
O.W.
Lemma C.2. Consider vertex E D". Let S be the part of the optimal solution to Min Isolating Cuts at stage i. Assume that [Ms, v) (ss, v)l S I values and w/ (0(t) á ((s)) + (w())) (()) ww(s)) S
I for all E .O.... Ug UI]}. Additionally, (St nu = 1/2, assume S - (9/10)[U). Then, there exists an E ...... ........ Ug [U]]] such that
x = S2(1).
Proof. Consider a specific sampling level i E {o...., [gg [[]]]. We say that i is "active" if there exists a set 5 C U containing and not such that |St n U1 E [2 22+) and
w(S))) S Ä(s, v) + 2(LIg(IUI)) i)I + values
(6)
Note that this is deterministic property regarding the existence of such set St independent of the randomness used to sample terminals or find private Min Isolating Cuts.
Let i' be the smallest active i. Recall St is the side of the true Min-s-o-Cut. Let [lg [ n UIJ. As w(S)) X(s, v) < A(s, v) + T values 8 must be active, so i' is well-defined and /' i As is active, there exists a set 5% with |S nu] E [2",, 2'+1) and with cost within 2([]g( [U)) - - i') isD I values of İ(s, v). On the other hand, as i' is the smallest active level, there is no set containing V but not s, whose intersection with U is less than 2", and whose cost is within 2([Ig(IU|) - (i' 1))l ko + valnss of \(s,t). v).
Consider the event that in Rt', we sample but no other vertices in S as terminals, i.e., R n n {u). Then, 5 is cut separating v and R' \ {u). By the assumed guarantee of in the lemma statement, the actual cut we output has approximated cost:
v6 ((() S w(S) + w(() (
S ((()) + ((() vi (5(5
S w(S)) + ((() w((: +1 +l=((())) =(:)
I w(.)) + Tio
< ((x,u) + (2(Ug((U))) -1) + 1)T + values.
For sake of contradiction, assume that SS nul < 2 Using the fact that all solutions of this size have large cost, we can conclude that
((()))
w($t) iiso
i(s, v) + ((Ug(())) - (6' - -1) + I values Tiso
i(s, v) + (2(LLg((U))) - -²)) 1)1'ss + l'vatnes
This contradicts the previous inequality that shows that w(s))) is upper bounded by this quantity, so J& nu 2 2 as long as the sampling event occurs.
Next, we show that JŠ nuI & (9/10)UU)- As v E D", the true minimum cut S: has the property [S; nu| < |U//2. Furthermore, by the isolating cuts lemma of [62], there is one minimum isolating cut solution for any set of terminals including and s will have that the part S, is a subset of S (this is the basis for the isolating cuts algorithm). So. if sampled in It' there will exist an optimal isolating cuts solution St with SSt nu < |U1/2. By the assumption in the lemma statement, JŠ nul (9/10)JU
25

---

Overall, we can bound the contribution of $ to D as
E x 2 1s nu
PP
V the only vertex sampled in Sy under sampling probability 2-
2' ( 12- 18
( - 2- 22
If i' = O. this evaluates to 1. Otherwise, if 2 1,
2
2'+1
x 2 1 - 2- 2
1+ 2- 1-2-1
2-
= e
1-2-1 1
2 6
e 2-12-1
We are now ready to prove the main lemma this section.
Proof of Lemma C.1. The first step of the proof will be to show that Tiso and I values upper-bound the error of the approximate isolating cuts and min cut values used in the algorithm with probability 1 033). Applying the guarantee of Lemma B. and union bounding over all the following guarantee of the quality of S holds with probability 1 B. If (5)} optimal Min Isolating Cuts for terminals :
(n lg(1/B)) 1g))))2(( (111)) )
Σ w(()) w(S)) S 0 VERe
We remark that w($)) 2 w()) due to the optimality of St.
Now noting (from Line of Algorithm 2) that w(Stt) - w(tt) is a Laplace random variable Lap 8(12)G11+)) and that the absolute value of it is distributed Exp ((
[60].
Note that the expected value of EvEre (w(S)) - (8t) is $1R"((1)))11 O n log U We then apply Corollary A.I with 5(180011+) and T = O (m+ log [V]) so that
Σ (w(St) (($)) < exp (-I(aT)) exp (-I(n log(1/3))) S B, LER
when the constant factor hidden in the bound for T is sufficiently large. Therefore, with probability (()), for all E (0...., : [lg U]]} holds
Σ
(w((S))
w/ S | + |wo (w;)) - v (S:) < Tiso-
VERS
This satisfies the approximate Min Isolating Cuts guarantee of the lemma.
Similarly, the additional guarantee in Lemma C.2 (if JS U| < |U1/2, assume $ < (9/10)
also holds with probability - 0(3) by union bound.
For the approximate min cut values, by the tail of the Laplace distribution and a union bound, each )(s, 2) satisfies
Ias v) Ms8 v) < T values o | (U(()()))/)) (1U1))(U113)
with probability
3. We condition on these events moving forward.
Next, we show that sets S are only included in our output if they are close to the min cut value A(s, v). Specifically, for any set returned by our algorithm:
((S)) < À(s, v) + (2 [V]] - 1)I' + valoss.
26

---

Applying the enror guarantees for (())), S and \(s, v) derived above,
( I T bo v(()
S 1s0 {(s.v) (2( |U]| 1) + 1) values
< 1 ho (A(s, + values) + (2( [U] - i) + 1)I + 1 values
(s, + 2 [U]] + 1) 2I values.
This completes the first part the proof concerning the error of the returned sets. In the remainder, we focus on the cardinality of the output.
By definition X the size D is given by sum over X
DD
Σ x
DEUM
By linearity of expectation and D CU \ {s},
Us |il
1x |
E
Σ
DI
x=
VED
As we output the largest D across all i, the output of our algorithm will have an expected size of at least
LR
Σ
Σ [
1g
t=0
RED*
Via Lemma C.2 (note that the condition holds with probability 0(3) from the first part of this proof), the expected output size will be at least
D
Ω
Ig
U0
C.2 Privacy
We now analyze the privacy guarantee of our algorithm. key technical observation behind our analysis is that the (approximate) isolating cuts found by Algorithm 2 disjoint subsets of vertices, so any edge can only appear in at most 2 sets at any sampling level in the for loop starting at Line 4. This is formalized in the lemma below.
Lemma C.3. PrivateGHTrrestty (Algorithm 2) is c-DP.
Proof. The algorithm PrivateGHTreeStey interacts with the sensitive edges only through calculations of approximate min cut values Å(s, v). approximate min isolating cut values a(S;), ($;), and calls to PrivateMinlsolatinge
(Algorithm 1). Otherwise, the computation only deals with the vertices of the graph, which are public. The calculation of each of the [U] cut values is -y -DP via Laplace mechanism (Theorem A.3) as a change in any edge weight by can affect a cut value by at most 1. By basic composition (Theorem A.2), the total privacy of these calls is
V - 4(10 -
4
Via the privacy of PrivateMinnsolatingCCts, each call to that subroutine is 2(1x (01+))1++) -DP. By basic composition, the total privacy of these calls is
(Ig UIl + 1)
(2(1g|U11+
E
+ 1)) E
Consider the vector of R1 where each entry in xf corresponds to w(S)) for some v E RR (ss) At any sampling level i, the approximate isolating cuts Št are disjoint. Therefore, change in any
27

---

edge weight by 1 can change at most two coordinates of x each at most by 1 (namely, the coordinates corresponding to the sets St which contain the endpoints of the edge). So, x² has & -i-siiiityy 2 relative to the edge weights of the graph. By the Laplace mechanism, release of all noised entries of DD. Summing over all sampling levels via basic x', given by w ), for any fixed i (1 composition, these calls have privacy
E
(Lg |0 +
4(1g|U1] +1)
In total, this algorithm is s-DP as 1 +
D Final Algorithm
Algorithm 3: PrivateGHTTreeG (V, w),e)
(T, < PrivatehhSteinee/TTee(CC e,
2 Add Lap 2(x-1) noise each edge in T
return T
Algorithm PrivatGGHSteine/rreee (V, E, w) U,e, e, fmax)
max < ~Ogl Rmmxx)
ift 1max then
return abort;
/* the privacy budget is exhausted */
end
5 + uniformly random vertex in U
Call PrivatGHTTreStep((., U, Tmmax to obtain D, C U and disjoint sets 8, for
v E R (recall for each v R do
UvER S, nt)
Let G, be the graph with vertices V S, contracted to single vertex Fy
Add edges with weight Lap( Sfmux) from 2, to every other vertex in Gy, truncating resulting edge weights to be at least
U. U,l > 1, recursively set (Tv: fu) +- PrivateGHSteeneeTTreeCG., E, + 1, Amma)); otherwise, T, is single node and f, the identity map
S, n
11
12 end
Let Giunge be the graph G with (disjoint) vertex sets 8, contracted to single vertices ye for all
U UEE.
Unage t U D D
15
Unnrge! > 1, recursively set
(Tunge: Starge) <- PrivateGHSStiinerTrreee (iange, Unage e, 1, Amax); otherwise, Turge is single node and /harge is the identity map
16 return Combine((Tinrg) fiarg)), {TTo, fo) u RJ, (S, R2))
Algorithm 5: Combine((Tiene Jtanee) { fo) RJ, (S. : WEEEE R))
Construct 7 by starting with the disjoint union Thange U n Tr and for each E R, adding edge between (x E U, and flarge (yv) E Utrgg
Construct V U Unage U Uven Un by f(v') Sunge (v') if E V U.en S, and f(v') f(())) of e S, for some v E R
In this section, we present the algorithm PrivateGHTree (Algorithm 3) for constructing an c-DP approximate Gomory-Ho Hu tree and analyze its approximation error and privacy guarantees. The steps
28

---

Suz
Sm
Soz
Su
yos
Ses
S
Bis
Zog
Starge
Starge
Figure 4: The Combine procedure of Algorithm 5. The computation each recursive subinstance provides a Gomory-Hu Steiner tree on that subinstance. To stitch these together to a Gomory-Hu Steiner tree of the initial instance, For a node E R, such that T. is assigned to fx,r,) ) in S, and is assigned to ftarge (Ye) in Starge in the recursively obtained Gomory-Ho Hu Steiner trees, we add an edge between fo (I,) and flarge (yo).
need add edges between the solutions the subinstances.
that differ meaningfully from the non-private version developed in [61] are in color. As in [61], we construct the slightly more general structure of a Gomory-Ho Steiner tree as an intermediate step in Algorithm 4.
Definition D.1. Let E,) be weighted graph and U C V a set of terminals. r- approximate Gomory-Hu Steiner tree is a weighted spanning tree T on U with a function f V - U where flu is the identity.
For all distinct t E U, if (u, v) is the minimum weight edge on the unique path between s and t, in T, and U' is the connected component of {(u, e) containing s, then f f-1(U") is a T-approximate Min-s-l-Cul with Aa(8 1) S wr(u, v) wa(s-1(0
(a(8,
To construct the final approximate Gomory- -Hu tree, we make a call to PrivateHHSteinerThee (Algo- rithm with U = V, the entire vertex set. The algorithm PrivateHHSteineTTree a private version of the GHTree algorithm in [61]. It computes several (approximate) min cuts from a randomly sampled vertex 8 E U by making a call PrivateGHTrreStep (Algorithm 2) to obtain D, R U and disjoint sets S, (where
U S, n U). For each of these cuts Š, it constructs recur- sive sub-instance (Gu, Uv) where G, is obtained by contracting V \ 8, single vertex x, and U. < Š, U. Moreover, creates sub-instance (Glanges Unrge) by contracting each of S, single vertex yo for y E It and setting Unage = U t- D.
Notably, on Line 8, where the algorithm recurses on the graph G, with V V Š, contracted to single vertex Z,, we add noisy edges from Ig of any actual edge from I. in the entire recursive subtree of that instance without incurring too much error. This will imply that for any edge and any instance during the recursion, there is at most one sub-instance where the edge does not receive this privacy guarantee. If L is the depth of the recursion tree, this allows us to apply basic composition over only O(1) computations of the algorithm. Essentially, there is only one path down the recursion tree on which we need to track privacy for any given edge in the original graph. We enforce < mmax and as we will show, the algorithm successfully terminates with depth less than mmx with high probability.
other vertices of the graph. This ensures the privacy
To combine the solutions to the recursive sub- aub-problems, we use the Combine algorithm (Algorithm 5) from [61], which in turn is similar to the original Gomory- Hu tree combine step except that it combines more than two recursive sub-instances. See Figure for an illustration of the Combine step.
Finally, Algorithm 3 calls Algorithm with privacy budget e/2. To be able to output weights of the tree edges, it simply adds Laplace noise Lap( 2(n-12) to value of the corresponding cuts in G. hence incurring error O n 1g with high probability. This also has privacy loss e/2 by basic composition over the 1 tree edges, so the full algorithm is e-differentially private.
29

---

D.1 Correctness
In this section, we analyze the approximation guarantee of our algorithm. The following main lemma states that Algorithm 4 outputs an On polylog(n)) -aprooxxiit Gomory-Ho Hu Steiner tree.
Lemma D.1. Let
Clg² n for a sufficiently large constant C. TrivateGSStineeTTeee( e,e, outputs O ) free T of with high probability.
tmax
aapproximmaee Gomory-Hu Steiner
We start by proving a lemma for analyzing a single recursive step of the algorithm. It is similar to [61, Lemma 4.5.4) but its proof requires
careful application of the submodularity lemma.
Lemma D.2. With high probability, for any distinci vertices p, q E Ulages we have that >a(p, q) S Aoan (p. 9) >a(p.g) q) +0(% Q0"lls" Nemax) ). Also with high probability, for any E R and distinct vertices p. 9 E Uo. we have that >a(p, AG. (p.9) >c(p, 9) O(" n mmax
Proof. Let us start by upper bounding how close the cuts Š, are to being Min-s-o-Cuts and how close the approximate min cut values ($.) are to the true sizes w(S)). Algorithm calls Algo- rithm 2 with privacy parameter E Tmaa θ Ig" Tennax and error parameter न. where mmax is the number of vertices in the original graph. By Lemma C.I with privacy and error parameter B, it follows that (a) the sets {S.} are approximate minimum isolating cuts with total eтror O (n=tog(L/A))ss"
0 n Rmas and (b) each set S,, is an approximate Min-s-o-Cut
F1
with error O
On any given call to Algorithm 2, these error bounds hold with probability 1 - -- max As each call to Algorithm 2 ultimately contributes edge to the final Gomory-Hu tree via Algorithm 5, there can be at most maxx 1 calls throughout the entire recursion tree, resulting in failure probability of nmax overall after union bound.
The fact that (p, q) S AGrap (p.q) follows since Guarg is a contraction of G. To prove the second inequality, let S be one side of the true Min-p-q-Cut in G. Let R₁ = R. n and R2 R R2)5 S.S. We show that the cut 5 = Uwen, S.) \ (UPER, S.) is an O "mmax/s)) aappro//aappooxxmaaee min cut. Since 5* is also cut in Gaage: the desired bound on AGuar (p, q) follows.
Let Ui,..., 11 | be the vertices of Rı in an arbitrary order. By |Ra applications of the submodularity lemma (Lemma A.1),
[R S,,
[il Σ
w ((SuUs, n S.,. 1)
S
SSUSS 1=1
(S)
w w(Sm.)
jei
[Ral Note that SUU! (m1 Moreover, for each i, S contains vs and so (SUUjes Suy)) n S., isolates u; from all vertices in
S,, is still (p, g)-cut as p. E Unrge and the sets S,, are each disjoint from Unrge-
V VAS. S... Using the fact that {S..} are approximate minimum isolating cuts, the sum in the RHS above can be upper bounded by O O nn
mmax) Letting S' = SUU.ER) S,, and S" = (V\S5) S.
a similar argument but applied to V S², shows that
S w(V) (') + +0 ng Amax
w(S") = w (V (Y)S)
U MER,
S.
But S* = V\ S", so we get that
n nl Rmmax
n nlg
w(S*) w(S") < wo(') 0
S <w(() 0
Amax
as desired.
For the case of p. g U, for some u again the bound (c q) S Ag. (p. 9) is clear. Thus, it suffices to consider the upper bound on XG (p,q). q). Let S the side of the Min-p-q-Cun but in G which does not contain v. Assume first that & S. By the submodularity lemma (Lemma A.
w(S n S.) S w(S) w(Ss) w(S U...
30

---

By the approximation guarantees of Algorithm 2, w(S.) I (s Os m Moreover, note that S S, is an (s, cut of G, so w(SUS.) 2 Ac(s, v). Thus,
w S.)) I wS)) + o lg Rmax = Ao(p. + 0 n Ig Amax
Since Sn is a (p. cut of G., we must have that w(5 S.)) 2 ÅG (p. so in conclusion ÀG (p,4) I (p( g) + 0(" lig Ranax) ignoring the added noisy edges to G,, in Line 8 of Algorithm 4.
Adding the noisy edges can only increase the cost by O 0(mlg" Amax)) with high probability via Laplace tail bounds (note that there can be at most mmma noisy edges added as each time noisy edge is added an edge is added to the final approximate Gomory Hu Steiner tree). This finishes the proof in the case s & S. A similar argument handles the case where s E S but here relate the value w(VV S) to (V ())).
To bound the error of the algorithm, we need a further lemma bounding the depth of its recursion. The argument is similar to that of [61].
Lemma D.3. m Clgg n for sufficiently large constant C, then, with high probability, no recursive call to Algorithm 4 from PrivateGHTree(G. E) aborts.
Proof. Each of the recursive instances (Gu, U.) has JU,1 S To [U] by the way D is picked in Line 7 of Algorithm 2. Moreover, by [2, Corollary II1.7], if s is picked uniformly at random from U, then E [ = 22 - 1). By Lemma C.I, the expected size of D returned by call to Algorithm 2 when [10-]
By Line 14 of Algorithm 4, it follows that, [[uueee]] S [1 - 221 Ig)) when [U] > 1. Thus any instance at recursive depth satisfies E [[iurgll] S n11 - (11/lg))) S exxp(-S(t//) ()))n If = 2(1g² n). the expectation is smaller than 1/ (oly(n), so by Markov's inequality, any instance at recursive depth & satisfies |U| = 1 with high probability. Now note that at every recursive depth, we can only have at most n instances, since the sets U passed the recursive calls of Algorithm 4 depth i disjoint. Thus, there are polynomially many recursive instances up to recursive depth fmax. so we can union bound over all sub-instances. In conclusion, all sub-instances have [U] = within Ollg n) recursive depth with high probability.
picking s at random from [U] is then at least 22
lg
We can now prove Lemma D.1. The argument is again similar to [61] except we have to incorporate the approximation errors.
Proof of Lemma D.1. By Lemma D.3, the algorithm does not abort with high probability.
Throughout the proof, n denotes the number of vertices in the input graph. Let A = O O nlg be such that with high probability Åo. (p, q) S λo q) + A for p.q E U, and similarly AG (20) S Ae g) + A for p. q E Utarge. The existence of A is guaranteed by Lemma D.2. We prove by induction on = O...., mmax,
,,mxx that the output to the instances at level funax aip-approxim Gomory-Ho Steiner trees. This holds trivially for i = 0 as the instances on that level have [U] = 1 and the tree is the trivial veevvertex tree approximating no cuts at all. Let 2 1 and assume inductively that the result holds for smaller i. In particular, if (T, f) is the output of an instance at recursion level i, then the trees fo) and (Tiage ftarge) are 2( - 1) approoxmtee Gomory-Hu Steiner trees of their respective G, or Gurge graphs.
of the recursion are
Consider any internal edge (a, b) E Targe (without loss of generality, what follows also holds for (a, E T.). Let U' and U'ange be the connected component containing after removing (a, b) from T and Turge: respectively. By design of Algorithm 5, Finge (Ui (Ulinge) and f (U') are the same except each contracted vertex yo E Stuge (Ulange) appears as S, S f (U'). It follows that WGGgg (finge (Ulage)) )) = wo(f-1(U') By the inductive hypothesis, (Tiuge, furgg)) is an approximate Gomory-Hu Steiner tree, so WGGte (Fimge (U) (Ulmgge) WT.n (a. b). Therefore setting wa b) = Whit (a, b) = wo (f- (U")) has the correct cost for T according to the definition of an approximate Gomory- Hu Steiner tree.
Furthermore, on the new edges (fo (xw), (y+)), the weight w(S.) is the correct weight for that edge in I as S, is the (x.) side of the connected component after removing that edge. Finally, by
31

---

adding these new edges, the resulting tree is a spanning tree. So, the structure of the tree is correct, and it remains to argue that the cuts induced by the tree (via minimum edges on shortest paths) are approximate Min-s-l-Cuts.
Consider any p,q U. Let (a, b) be the minimum edge on the shortest path in T. Note that it is always the case that wr(a, b) 2 M(a b) as wr (a, b) corresponds to the value of a cut in G separating a and 6. We will proceed by cases.
If (a, E Tiager then by induction, wy(a,,) = Wham (a, b) S AGume (a, - (2i - A) By Lemma D.2, it follows that wr(a,,) b) S Sc(a, b) + (2i 1)A. applies if (a, b) E To for some E R.
The exact same argument
The case that remains is if (a, b) is a new edge with a = fo (x.)) E U, and b = Sige (Ve) E Marge for some V E R. Then, wr(a, b) = wc(S,). By Lemma C.I, S, is an approximate Min-e-s-Cut and wT(a, 6) S (o( s) + A. To connect this value to Aa b), note that by considering the choices of where v and s lie on the Min-a-b-Cut, we can show
Aa(a, b) 2 min(Aa v), Ac(v, s). Ac(s, b)).
Let S¹ be the a side of the a-v cut induced by the approximate Gomory-Hu Steiner tree (T,,, f.). As = J (x.,) and 8 E F., Sy is also the side of e-s cut. Therefore, (a()) 2 Aa(u, 8). On the other hand, by our inductive hypothesis and Lemma D.2, this is an approximate Min-a-o-Cut: (S.) I λG. (a, + 2 Ào v) + (2i (2i-22))) 1) Hence, (c s) S Ao v) +2)+ 1)A. The analogous argument holds to show Aa(u,s) & (c(s, b) + (2i - 1)A. Therefore,
Ad(u, 8) S min()aa(,,))
b) + (2i - 1)4,,
which further implics Ac(u, 8) S Ac(a, b) + (2i - 1) by combining with Equation (7). Therefore, ur(a, b) S \a 8) + A S (a b) + 21A.
In all cases, (r, b) S ba( + 21A. As the cut corresponding to the edge (a, b) is the path from to it is also a (p, c)-cut, so λa q) S wT b). Furthermore, it must the case that there an edge (a', b') along the path between p to q such that a' and b' are in different sides of the true Min-p-q-Cut. Therefore, \a(p, q) 2 Aa(a', B¹). As we chose (a, b) to be the minimum weight edge,
(T(a,,) S wT((', 8)) W (a B) + 21 S Ac 9) + 21A.
This completes the induction. It follows that the call to PrivateGHSSeinerTTeeee V,e, 0) outputs a 2mmax A a-approximate Gomory-Hu Steiner tree T. Substituting in the values fmax = Ol1g 2 n) and
A 0 rigg 2 gives the approximation guarantee.
We now state our main result on the approximation guarantee of Algorithm 3.
Theorem D.1. Let T (Vr, Er, WT) be the weighted tree output by PrivateGHTree(G
E) on weighted graph G. For each edge E ET, define Se to be the set of vertices of one of the connected components of 3 {e). Let u, U E be distinct vertices and let emin be an edge on the unique u-v path in T such that Wr (Cmin) is minimal. With high probability, Semin is an
O n ig
approoximate Min-u-u- v-Cut and moreover, (Aa(,,)) u) wr(Cmia)) 0 nlg nlg"n)
Proof. Note that for each edge e, the final tree weight wT(e) is obtained by adding noise ((alkm) with high probabil- Lap 2(n-1) to the cut value w(.)). Thus, (w(S.) - wr(e)) O e
ity for all E T. Now let en be an edge on the unique u-v path in T such that w(Seg) is minimal. Then, by Lemma D.I, w(S,.) < Aa(u, v) + O O("lg"") with high probability. As Emin was chosen as edge on the u-t path in T of minimal weight, wy (emin) S (eo).. and so
w((Semin S WT wT(emi)) + +0 nlgn
n nlgn n
S wT(ce) +
E
S (( ) +
ni (rlg
S Ao(u, v) + n
n
32

---

On the the other hand, Semin defines (u, e)-cut, so Aa v) I w w(Sema)) This proves the first statement. Moreover, the string of inequalities above combined with Ag (u, v) I w (Seemm) in particular entails that
nlgn n
nlg
Aa(u, v) S wr(emin) +
S u)( +
8
from which the final statement follows.
D.2 Privacy via Bounded-Overlan Branching Composition
Consider a family of computation trees parameterized by two differentially private mechanisms, denoted Mrecuse and sunitize- Through Mrecuee each node in the tree privately produces both (1) the output of its computation and (2) the topology and description of its children's 's input. Each child's input consists of a combination of "sensitive" data, transmitted in plaintext, and "sanitized" data, provided as the output of the private mechanism Maanitize. Let (u) denote the set of children of node a tree.
Specifically, upon receiving a sensitive dataset X" x xi...... X and a sanitized dataset Y = Y1" ..... Y, from its parent, node u computes the following objects via Mreeurse y") (we only require that Mreeuse is DP with respect to its first input):
A number of children d"
For each child e E (u), set of "sensitive" indices 1 = -..,..... ;
For each child v E au)), set of "sanitized" indices J {J . J
An auxiliary output a
Let e be one of the d' children of The input for consists a sensitive dataset X and a sanitized dataset, formed by concatenating any function Y with Msanitize (X This setup illustrated in Figure 2.
X
X
Additionally, consider privacy model where the indices of the data are public, and two neighbor- ing data sets differ at most one index. The theorem below holds regardless how we define the neighborhood relation single index. For example, there exists at most one index such that X, + X However, for our main result on DP Gomory-Hu trees, X (Xe)eEε (w(e))esB
could say that X and X' are neighboring if
the weights of edges of the input graph, and two data sets X'X are neighboring there exists an e E E such that for all E E \ {c). Xe X and moreover, [Xe X < 1.
Theorem D.2 (Bounded-Ovenl Overlap Branching Composition). Let Mrecurse and Myanitize be mechanisms described, satisfying 61),6 and (22,82)-DD respectively. Let the subsets of indices {I"} and {Jo} produced by Mweeuse satisfy the following conditions deterministically for all inputs:
The index sets } are disjoint.
For all indices j. He: j E JJH f fixed constant É.
Consider the following mechanism Mbranch that, as input. receives sensitive dataset X and maximum depth parameter h. Minanci creates a tree T = (V, F) recursively using Mrecuree and Msumiize with X the sensitive imput to the root node; the root node does receive any sanitized imput. If the depth of T is greater than or equal to h, the mechanism outputs 1. Otherwise, the mechanism releases T along with all outputs {YY d {1") Joea(u); {Jr) (J") (vea(a)aa")) u Vj. This mechanism is (hεi (h- 1)8E2, hō1 (h- 1)E82)-DP.
Proof. Let = [ For any t E N. let Miranchh be the mechanism which, given a sensitive dataset X, creates tree by recursively using Miecurse and Msanitie with X as the input the root node, stopping after recursion depth f; we adopt the convention that a tree with a single node has depth 0. The output of M (ranch is the tree T (V', E`) with maximum depth t, and the sanitized inputs and node outputs {(Y d {I") (")eeat)) {J" "oooo()) a"): u V
Let E()), ((t) be the privacy parameters for Mirannht The mechanism described in the theorem statement is (=(h- 1), ((h--))--DD as checking whether the tree (with unbounded recursive depth) has
33

---

depth at most h can be verified by rumning the recursion for up to h steps and checking whether d" = 0
for every node at depth h. Outputting either or (T, {(Y", (d""""d', { (eea(u) hee(()) a")
V*J) is post-processing of the output of M and therefore cannot increase the privacy loss.
We prove by induction over that the following conditions hold:
(a) <(t) - (t + 1) + tlz2
(b) 8(1) - (L+ + 1) + Ll82
(c) Let St C V be the subset of vertices in the tree produced by Miranch (X) depth t. For any i E [N], there is at most one vertex u E St for which X; E X
The theorem statement immediately follows from conditions (a) and (b) by plugging in / = h 1.
For the base case, consider 0. M (X) releases a tree 7 (Vo, E*) as well as {(Y", d" { (vEa()), [J"")e a") u E Vo The tree T simply contains a single node independently of X. Let be the single node in V The root node receives no sanitized dataset, so y = 0 independently of X. The output (d" (errt)) (J") (uea(w). a²) is produced by M which is (e 61) )DD. Therefore, the entire mechanism M is (11,,))-DP, Furthermore, condition (c) of the inductive hypothesis is trivially satisfied as there is unique vertex.
Consider any O. By the inductive hypothesis, releasing the tree T (Vt-1, along with {(Y", ,d", (("rve(())) (e")) a") u E V(-1 is (ts) + (ft-1)eEy) t6j + (t 1)(82)
DP. We will assume that these objects have been released and analyze the privacy of releasing the additional objects output by Mbranch (X). Note that the topology of the tree 7 = (V' E
can already be calculated as post-processing from these objects as the structure of the t-th level of the tree is contained in the degrees of the leaves of 7 Let S = V Vt-1 The addi- tional objects output by Moraneh (X) that cannot be obtained via post-processing of M (X) are {(Y", ((",d", dd" {Te) )wea(v): (J )wEe(e); a²)= v E 5*).
We will continue by bounding the privacy of releasing these outputs for any node at depth i with respect the sensitive inputs the node and its parent. Consider any u E St and let p(v) E 5t be the parent of in T The only part of y which cannot be obtained by post-processing Yp(v) is the
output of Manttiize (Xp(x)
,..., .....,,plo)) xp(e)). So releasing Y is (E2, DDP with respect to the subset of
jy
its parent's 's sensitive input (Xx(() .x(())) and (0, O)-DP with respect to X (X
x²(")).
Jf
Jm
Given the release of y well as 1e and J releasing (d", (T") wwer()) {J") (weo(u), a" the output of Maccurse (X" (xp(x)
xp(x)), Y"). is (1),8))-DP with respect to X" and (0. DDP
with respect to \X".
Consider any particular index i" E [N] corresponding to the sole index on which two neighboring datasets X and X' differ. By the inductive hypothesis, there is at most node u" St such that X,. X Consider any node E St which is not child of u", p(u) * u². Note that X,, & Xx)))) implies that X,, & X as X C XP(r), By the argument in the paragraph above, conditioning on the release of M (X). the release of (Y", d", [["""a(()) (J") {J")"em(() (wEa(s): a²) does not depend on
X,, and does not affect privacy.
Consider nodes u E (u""). the children of u². if 8" & 1" and i" É J", as above, conditioning on (X). ). the release of (Y", dd, { heento) {J") "wEe())) a²) does not depend on X₃- and does not affect privacy. if E JJ, the release of (Y", d", {I" [w""))(()): )")))t(())) a") is E 7", the release of (Y",60 d", (1" ( [w) (J") )wea("); (J")))t)) a²) is (E1,6))-D..
the release of M (X),
(c2, 52)
By the condition on Mrecurs in the theorem statement, there is most one child 8" E I" and at most u E ou") such that i E JJ. This implies that there is at most one node v E S where i' I", satisfying condition (c) of the inductive hypothesis. As this holds for any choice of tt, conditioned on the release of M (X), releasing ((Y", d', {T" ]wea()) (J") (J") Wee a")
o(u)) such that
E 5*) is (E1 + LE2, 8, + LDP) By basic composition, summing over the privacy parameters of releasing M s(l) < (8) + faz) + (Ie) + (1 1){s2) (l + 1) + ll82 and, likewise, 5(1) S (1 + 1)6, + 1862, satisfying conditions (a) and (b) of the inductive hypothesis. This completes
the proof.
34

---

We will use bounded-overlap branching composition to prove the privacy of our GH-tree algorithm.
Theorem D.3. PrivateGlTTree(:; s), i.e., Algorithm 3, is s-DP.
Proof. We will first argue that releasing the unweighted tree returned by the call to PrvateGHSteineeTreee V,E,0.1 is (e/2)-DP. To invoke Theorem D.2, we will describe the mechanisms Mreausse and Maniiiiie for which the corresponding Maranch mechanism simulates the computation done this call to PrivatGHHSteineTTTee
Mieeuse has a sensitive and sanitized input. Its sanitized input is list of vertices and edges, edge weights for subset of its edges, as well U, ł, m'ax. Its sensitive input is a set of edge weights for the rest of its edges. Let G be the weighted graph which is formed by combining the two inputs. M Mrecusse contracts some vertices (if it is itself Glarge subinstance), picks a uniformly random vertex
caleulates fmaax and runs PrivateGHTreeStep [,,,, s, U, mfmax T
obtain D, R U, and
{$ [Seveen- The output of Mrecuse is the following:
Recursive degree [ + 1.
For each E R, a recursive child is created which gets sensitive indices corresponding to all edges between pairs of vertices in S.. In addition, this child gets sanitized indices corresponding to all edges between S, and V Sp.
An additional recursive child (corresponding to the Giarge subinstance) is created which gets sensitive indices corresponding all edges whose endpoints do both belong the same set S.. This child has no sanitized indices.
Auxiliary output R, J.e.
By the privacy of PrivateGHTreeStep in Lemma C.3, Mrecurs is 4.aax
DP.
Msanitize takes input set of edge weights for edges between a set S, and its complement V S. It contracts V \ Sy, to vertex Ty and outputs the resulting (summed) edge weight from edges between S, and ve plus Lap( Stmax) noise. By the privacy of the Laplace mechanism Theorem A.3 and the contraction/sum operation has sensitivity 1, Manittiz is 8
-DP.
The unweighted tree output by PrivateGHSteineTTreeeCC V, n) can be calculated via post- processing of the recursive mechanism Mbranch parameterized by Miecurse and MManiiize with maxi- mum depth h fmax- While in Algorithm 4, we invoke the Combine step to construct the GH-tree, this can easily be simulated given the auxiliary outputs {$²) {Su)oen n at each recursive node these sets determine the GH-tree topology.
The final step bound the overall privacy of outputting the unweighted tree is to ensure that Mrecurse satisfies the bounded-overlay condition. Consider edge weights which are the sensitive input to call to M Note that these edge weights are partitioned across the recursive children: either the weight corresponds an edge with both endpoints in single $,,, in which case is sent to the corresponding G, subinstance, otherwise, it is sent to the special Giange subinstance. Furthermore, any edge weight only belongs to the sanitized indices of most two recursive children. Each G, subinstance receives all edge weights for edges between S, and V S,, sanitized indices. Any particular edge has two endpoints and so can only belong to two such sets.
Plugging in l Theorem D.2, get the following bound on the privacy of releasing the unweighted approximate GH-tree: he + (h- 1)682 = Imax E
+ 21mmax
1)
4f
8t
2
In the final algorithm PrivateGHTree(G,ee the tree weights are set to be the corresponding cut value in plus Lap 21n-11 noise. Note that the choice of which cut values to calculate
35

---

post-processing of the privatized output of the unweighted tree. As any specific cut value can change by at most in neighboring graphs, outputting a single tree edge weight is 2( -DP. Basic composition over all 1 tree edges means that releasing the edge weights given the tree topology is (e/2)-DP. In total, releasing the weighted tree is e-DP, as required.
D.3 Runtime
While runtime is not our main focus, final note, our algorithm can be implemented to run in near-quadratic time in the number of vertices of the graph. The runtime inherited directly from prior work of [4], which utilizes the same recursive algorithm introduced in [61]. The overall structure of their main algorithm and subroutines remains in our work with changes of the form (a) altering runtime-independen conditions in if statements or (b) adding noise to cut values or edges in the graph. While left unspecified here, computation of single source Min-s-e-Cuts in Algorithm should be done via the runtime-optimize via Theorem 1.3 of [4], Algorithm 3 runs in time ( (note that if instead of [85], we use the almost-linear time algorithm for single source Min-s-u-Cutt [23], the running time would be n for dense graphs)
algorithm of prior work [85] to achieve the best bound. Then,
E
Additional Related Work
Multiway cut is another cut problem that has been studied in the privacy setting. Given k terminals. the multiway cut problem seeks a partitioning of the graph's nodes into k parts such that (1) each part contains exactly one terminal, and (2) the sum of the weights of edges between parts, known as the cut value, minimized [28]. The multiway cut problem is NP-hard for k 2 3 [28], implying that all non-private polynomial-time algorithms have approximation factors greater than 1. Dalirrooyfard, Mitrović, and Nevmyvaka [29] present an e-DP algorithm for the multiway cut problem with a multiplicative approximation factor of 2 and an additive error of On log k/s). Chandra et al. [18] provide c-DP algorithm achieving an additive error of Ó(nk/a /e) and multiplicative approximation ratio that matches the best-known non non-private algorithm. They show that an additive error of On log k/E) is necessary for any E-private algorithm for multiway cut. An open question is whether there exists an algorithm with an additive error of On log k/s) and a multiplicative approximation ratio that matches the best-known non-private algorithm.
Computing cuts on (suitably defined) graphs is also a key primitive in a wide-range of applications beyond the aforementioned graph algorithms. For example in many clustering problems, cuts explicitly computed, as in spectral [20, 76] or correlation clustering [69, 65]. or the objective involves identifying small cut implicity, such in community detection in the stochastic block model and beyond [40, 24, 43, 42]. Cuts are also at the heart of many learning-thees theoryy tasks on graph data, such as learning graph partitions [68, 79], (semm)-supervvsed learning using cuts [12, 7, 87, 86, 52], active learning [1 1, 45], and transductive learning [55, 48], to name a few examples. We refer to the papers and references therein for details.
F Minimum k-cut
Lastly, we note an application to the minimum k-cut problem. Here, the goal is to partition the vertex set into l pieces and the cost of partitioning is the total weight of all edges between different pieces in the partition. We wish to find the smallest cost solution. is known that simply removing the smallest & - edges of exact GH tree gives multiplicative approximation of 2 [80]. Since we compute an approximate GH tree with additive error Ó(n/E), we can obtain a solution to minimum k-cut with multiplicative error 2 and additive error Ö(nk/e), Our corollary is the following.
solution to the minimum k-cut problem with
Corollary F.1. Given weighted graph G with positive edge weights and a privacy parameter 0. there exists an E-DP algorithm that outputs solution the minimum k-cut problem on G in (n²)) time with multiplicative error 2 and additive error Ö(nk/e) with high probability
The only prior non-trivial DP algorithm for the minimum k-cut problem is given in [18]. Their pure DP algorithm obtains the optimal additive enror O (EE) but requires the input graph to be
36

---

unweighted while also requiring exponential time. They also give polynomial time algorithm which also has multiplicative error 2 with additive error D(kl.//s) which holds for weighted graphs, but only works in the approximate DP settin.. Note that there are also trivial algorithms such as finding the minimum k-cut from a solution to the All Cuts problem, e.g., those from Table 1, but this strategy only gives additive error Oken /e) for dense graphs.
Thus, to the best of our knowledge, no prior polynomial-tine pure DP algorithm can compute the minimum k-cut on weighted graphs with near-linear in n error. Determining the limits of efficient and pure DP algorithms for the minimum k-cut problem is an interesting open question.
Proof of Corollary F.1. We follow the proof of [80] (via the lecture notes in [19]). replacing the exact GH-tree with our approximate version. The algorithm is simple: we cut the edges corresponding to the union of cuts given by the smallest & - edges of our approximate GH-tree T of Theorem 1.1. If this produces more than k pieces, arbitrarily add back cut edges until we reach a k-cut.
For the analysis, consider the optimal k-cut with partitions Vi,..., V12 and let wv(1) .... S wo (Ve) denote the weight of the edges leaving each partition without loss of generality, Since every edge in the optimum is adjacent to exactly two pieces of the partition, it follows that Σ, wo (V.) is twice the cost of the optimal k-cct. We will now demonstrate k- different edges in T which have cost at most 2; w(V)), up to additive error (Kk)) (nk/ee, where A O(n/s) is the additive error from Theorem I.1.
As in the proof in [80], contract the vertices in Vi in T for all i. This may create parallel edges, but the resulting graph is connected since T was connected to begin with. Make this graph into a spanning tree by removing parallel edges arbitrarily, root this graph at Vj. and orient all edges towards Va.
Consider arbitrary V; where * k. The 'supernode' for V, has a unique edge leaving it, which corresponds to a cut between some vertex v E V; and some vertex w E Vi- Since T is an approximate- GH tree, the weight of this edge must be upper bounded by vVV)) (which is also valid cut separating e and w), up to additive error A. The proof now follows by summing across Vi.
G Discussion on Open Problems
An interesting open question is whether a better additive error can be achieved or a lower bound established in the setting where we only care about values of cuts and not the cuts (vertex bipartitions) themselves. To our knowledge, the best-known error bound for this All-Pairs Min-s-t-Cut Values problem O(n/e) for approximate DP, obtained by a trivial algorithm that adds Lap(n/s) noise to each of the (") true values; this method satisfies privacy through advanced composition and the Laplace mechanism [34]. Note that this algorithm does not leverage the fact that there are, in fact, at most n 1 distinct cut values or any of the structure of the graph. Before our work, the best algorithm for this problem in the pure DP setting solved the All Cuts problem, incurring an (nn//2 /s) error [47]. Our work yields an improvement to ((n/s) error with pure DP. Both of these solutions in the pure DP setting output the cuts and the values, so it seems probable that better error can be achieved. No non-trivial lower bound is known for this problem. The 22()) lower bound of [29] applies to releasing an approximate Min-s-I-Cut, whereas releasing a single Min-s-I-Cut value can be achieved with an error of O(1/e) using the Laplace mechanism. This question parallels the All-Pairs Shortest-Pathh Distances problem studied in [81, 39, 22, 13], where sublinear additive error is achievable for releasing the values of all (?) shortest-paths. In contrast, the linear error is required to release any shortest path itself. One might wonder about the sensitivity of a single edge on Min-s-t-Cui values; specifically, whether two neighboring graphs differ in only small number of Min-s-l-Cut values. However, as illustrated in Figure 3, the Min-s-I-Cut value sets of two neighboring graphs can differ by as many as n 1 entries.
An additional open question is whether there exists a polynomial-time c-DP algorithm for the global Min Cut problem that achieves error below Ö(n/z). As noted in Corollary 1.2, the polynomial time algorithm from [46] is only approximate DP, though it can be made pure DP if allowed exponential runtime. The same question applies to minimum k-cut (see Corollary F.I): what are the limits of efficient, i.c., polynomial-tnne algorithms that are also pure DP for this problem?
37

---

Finally, in the problem of outputting synthetic graphs that preserve all cuts, the work of [37] establishes lower bound of 52 ( on the additive error. However, this result applies to the same paper, the authors discuss
algorithms that do not permit any multiplicative approximation. that an additive error of O(n) with multiplicative error of 1 + 7), for any constant 7) > 0, can be achieved in exponential time using the existence of linear-size cut-sparsifiers and the Exponential mechanism, Recently, Aamand et [1] gave polynomial time algorithm for this problem with roughly n.1.25 additive error with constant multiplicative error. It remains an intriguing open question whether a synthetic graph that preserves all cuts within an additive error roughly n and a constant multiplicative error can be generated in polynomial time.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We give full proofs of all of our theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We fully specify the theoretical (differential privacy) setting for which our main results hold. Since this is a theoretical work, specific concerns about any practical applications of our work beyond the scope of our paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: Full proofs given in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper has experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
40

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper has no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
Boglli/ggiiee/CodeSeee www.ssubbbsssiooocoooooocoo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/nips. cttpsscccppbllcccccccccc http:/pullcggggdddeeeeeeppp guides/ CoodeSummis ssion asionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper has no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper has no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
41

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative emrrr rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper has no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurrpg:
Answer: [Yes]
Justification: Our paper complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper presents work whose goal is to advance algorithmic and theoretical tools the field of Machine Learning. There are many potential societal consequences of work. The most direct consequence which we highlight in the paper is that develop better algorithm for fundamental graph problem with differential privacy. This may allow more private/more accurate analysis of graph data.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
42

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com aamdaatseess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
43

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
All the assets of the papers (the proofs) are given the appendix.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
44

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our paper is not related to LLMs in any meaningful way, and we did not use LLMs in creating the paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: :attps:/on /ttp///er.pp.///// for what should or should be described.
45


Reviews:
[{"review_id": "zP7upp3mXl", "reviewer": "Reviewer_SqTp", "summary": "Gomory-Hu tree (GH tree) is a data structure that preserves all pairs $s-t$ min cuts of a graph. This paper designs an $\\epsilon$-DP algorithm to compute an approximate GH tree with $\\tilde{O}(n/\\epsilon)$ additive error on each query. Previously, the best $\\epsilon$-DP algorithm for all pairs $s-t$ min cuts required an additive error of $O(n^{\\frac{3}{2}}/\\epsilon)$. Moreover, an existing lower bound shows that even for a single $s-t$ min cut, $\\epsilon$-DP algorithm requires $\\Omega(n)$ additive error.", "questions": "In Line 47, neighbouring weighted graphs are defined as those that have total weights that differ by at most one and in a single edge. I am curious about the number one here. Why can't we scale the weight to make the difference arbitrarily large? Are there other reasonable neighbouring models for weighted graphs?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: \n  1. New and improved differentially private algorithm for a fundamental graph problem. Partially match the lower bound.\n  2. The paper is written well. I like the first half of section 2, which introduces the existing approaches and the challenges. It is clear to people who are not working in this direction.\n\nWeaknesses:\n  1. Pure theory paper, may not be interesting to a large body of the NeurIPS community. Maybe it is helpful to use one or two sentences to discuss the applications of GH tree in machine learning.", "was_revised": true, "final_justification": "I have read the rebuttal. I think it addressed most of my concerns, and I will keep the positive rating.", "rebuttal": "> Pure theory paper, may not be interesting to a large body of the NeurIPS community. Maybe it is helpful to use one or two sentences to discuss the applications of GH tree in machine learning.\n\nThank you for the feedback. Indeed, the main focus of our work is theoretical and gives nearly optimal private algorithms for releasing all pairs min $st$ cuts (with error comparable to the lower bound even for releasing a **single** cut).\nThat said, there are applied works that use the computation of many min $st$ cuts, and thus their private version might benefit from our work (see, e.g., [1] and [2]). To give a specific example that is relevant to privacy, consider a social network, where each node represents a person and a weighted edge represents the strength of the relationship between two people. Edge-neighboring privacy corresponds to the case where the set of people are known, but we do not want to leak information about any specific friendship relation. Running multiple min $st$ cuts can help in community detection by detecting tightly-knit communities within a network by identifying weak links that separate different groups (see [2] for a non-private version of this example).\n\n[1] Gary William Flake, Robert Endre Tarjan, and Kostas Tsioutsiouliklis. Graph clustering and minimum cut trees. Internet Math., 1(4):385–408, 2003.\n\n[2] Hyungsik Shin, Jeryang Park, and Dongwoo Kang. A graph-cut-based approach to community detection in networks. Applied Sciences, 12(12), 2022.\n\n\n>In Line 47, neighbouring weighted graphs are defined as those that have total weights that differ by at most one and in a single edge. I am curious about the number one here. Why can't we scale the weight to make the difference arbitrarily large? Are there other reasonable neighbouring models for weighted graphs?\n\nThank you for the feedback. We discuss the choice of neighboring graphs in section A.5.\n\nThis is a great point to scale the weight and one can indeed define neighboring graphs to have total weight difference of say $\\Delta$, which would result in the additive error also being scaled by $\\Delta$. Thus, the “one” is a natural choice to use. This notion of DP is a standard generalization of unweighted edge-DP and has been widely used to study cut problems in graphs (see [1-5] for a small selection of such works).  \nOther reasonable DP models include changing an edge (of unbounded weight) or changing the entire neighborhood of a node. But these notions of privacy are too stringent and result in trivial solutions for cut problems. If the edge weights are arbitrary, as in our setting, removing a node or an edge can cause a cut value to go from any positive value to 0. This is a main reason why the literature on preserving cuts uses the edge weight definition, but it is an interesting future direction to explore other natural neighboring notions for weighted graphs.\n\n[1] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In SODA, 2010. \n\n[2] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Lindenstrauss transform itself preserves differential privacy. In FOCS, pages 410–419, 2012. \n\n[3] Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In SODA, pages 560–578, 2020. \n\n[4] Mina Dalirrooyfard, Slobodan Mitrović, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. In NeurIPS, 2023. \n\n[5] Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In SODA, pages 1019–1049, 2024."}, {"review_id": "LlfA0y0TKT", "reviewer": "Reviewer_FS48", "summary": "The goal of the paper is to output differentially private s-t-min-cuts for all pairs s,t of an input graph. The paper achieves this by outputting a tree that preserves all s-t-min-cuts with high probability (w.h.p.). The privacy model is edge-weight privacy, where two neighboring graphs differ by exact one unit in the weight of one edge.\n\nThe private algorithm is built on top of Li's work on constructing a fast non-private Gomory-Hu tree, particularly incorporating privacy into a subroutine called minimum isolating cuts. This subroutine finds the collection of all minimum cuts that separate each of the nodes in the input set from the remaining nodes. Privacy is ensured by replacing an s-t-min-cut query in the minimum isolating cuts algorithm with a private s-t-min-cut as proposed by Dalirrooyfard et al. The algorithm then artificially injects edges with randomly generated weights into the graph before sampling subgraphs for the next steps, which guarantees certain properties regarding the quality of the selected sets.\n\nFinally, the paper bounds the privacy cost incurred by each edge using a composition theorem on the recursion tree. The main contribution is a private synthetic graph structure that can answer all s-t-min-cuts with a similar additive factor (with an extra the logarithmic factor) as that of answering a single s-t-min-cut in prior work.", "questions": "The privacy analysis is my major concern for the correctness of the work. Please answer these questions and provide a more explicit discussion of the privacy guarantees, mostly for Algorithm 1 and 4.\n\n- Algorithm 1 invokes the contraction sub-rountine multiple times. By its definition A1, the subroutine uses edges and edges' weights information. The privacy analysis of Algorithm 1, line 801-804, claims that only the min-cut uses the sensitive information, which is straightforward for the input graph $G$, but not directly for the last call. Can the author comments on the correctness of the privacy analysis, especially analyzing the sensitivity of $\\mathcal{H}$?\n- Similarly to Algorithm 4 and its privacy analyses on graph $G_v$ and $G_{large}$.\n- In Algorithm 2, what does \"satisfying the conditions on Algorithm 2\" mean?\n- In the composition theorem, can the authors specify the privacy model (wrt to the sensitive dataset and sanitized data),i.e., the neighborhood definition wrt the two types of data.", "limitations": "Yes.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- Addresses an important problem.\n- Provides strong theoretical guarantees, with the utility guarantee close to the theoretical lower bounds (with an additional logarithmic factor).\n- The analyses of utility and privacy are non-trivial.\n- The composition theorem is interesting and of independent interest.\n\nWeaknesses:\n\n- The algorithm is largely built on two previous works: the non-private Gomory-Hu tree algorithm by Li and the private s-t-min-cut query by Dalirrooyfard et al., with modifications to control the quality of some intermediate objects.\n- Some technical details, especially for the privacy analysis, are not clear (will question later)", "was_revised": true, "final_justification": "I appreciate the discussion, but I remain firm in my recommendation.\n\nThe idea and execution of this paper are promising and have the potential to result in very good work. Therefore, I believe the paper would benefit greatly from a careful revision and should not be rushed for this cycle.\n\nThe main justification for this recommendation lies in the correctness of the privacy analysis, which is the most critical aspect of a rigorous privacy method such as differential privacy. I have reviewed the maths carefully and found several mistakes in the privacy analysis—these are somewhat tricky given the context. Although the authors have made some corrections in response, I believe the privacy analysis should be thoroughly reviewed with all formal details, which the authors were unable to provide due to limitations imposed by the conference.\n\nI appreciate the positive opinions of other reviewers regarding this work. However, I opt for a weak reject. If the other reviewers can confidently certify the correctness of the privacy analysis, I will not oppose their judgment. Otherwise, I hope the paper will be carefully revised and reviewed again.", "rebuttal": ">Weaknesses:\nThe algorithm is largely built on two previous works: the non-private Gomory-Hu tree algorithm by Li and the private s-t-min-cut query by Dalirrooyfard et al., with modifications to control the quality of some intermediate objects.\n\nThese two works are important to our paper, but we would point out that many DP papers follow the general strategy of carefully privatizing a known non-DP algorithm. In our case, beyond finding the right non-DP algorithm as a starting point and identifying the steps needed to make it private, we had to tackle several technical challenges, which we have highlighted in Section 2 and again below.\n\nTwo important examples are (1) ensuring the private min isolating cuts found are close to their non-private counterparts in terms of their weighted edge values and are simultaneously not 'too small' in cardinality and (2) ensuring that a single edge does not appear in many recursive calls of our private GH tree subroutine, even if the recursive depth is bounded.\n\nThese challenges are not relevant in the non-private setting, but require novel analysis for a DP algorithm. Furthermore, the Bounded-Overlap Branching Composition technique which we develop along the way may be of independent interest. We refer to Section 2.3-2.6 for further discussion.\n\n>Some technical details, especially for the privacy analysis, are not clear (will question later)\n\nSee the discussion below.\n\n>Algorithm 1 invokes the contraction sub-rountine multiple times. By its definition A1, the subroutine uses edges and edges' weights information. The privacy analysis of Algorithm 1, line 801-804, claims that only the min-cut uses the sensitive information, which is straightforward for the input graph G, but not directly for the last call. Can the author comments on the correctness of the privacy analysis, especially analyzing the sensitivity of  H?\n\nFirst, the sets $W_r$ are private since they are obtained from postprocessing the $\\lg|R|$  privately computed min cuts $C_i$. Furthermore, the sets $W_r$ importantly form a partition of $V$. This implies that an edge in the initial graph contributes its weight to at most two edges in $\\mathcal{H}$. Namely, an edge internal to some $W_r$ appears only in $H_r$ and an edge between some $W_r$ and $W_{r’}$ is only contracted into an edge in $H_r$ and an edge in $H_{r’}$. Thus, the sensitivity of $\\mathcal{H}$ is 2, and running an $\\epsilon$-DP algorithm on $\\mathcal{H}$ is thus $2\\epsilon$-DP with respect to the initial graph. It appears we have forgotten to incorporate this factor of 2 in our privacy analysis. Fortunately, it only affects our bounds by a constant factor, but we apologize for the confusion and will update the manuscript to address this. Thanks for pointing this out!\n\n>Similarly to Algorithm 4 and its privacy analyses on graph Gv and $G_{large}$.\n\nThe privacy analysis of Algorithm 4 is more complicated and requires our Bounded-Overlap Branching Composition Theorem D.2 to analyze the privacy loss through all recursive steps of the algorithm. We note (similar to the previous comment) that since the sets $\\hat S_v$ are disjoint, any edge of the initial graph can contribute its weight to at most three of the sub-instances $G_v, v\\in R$ and $G_{large}$. Moreover, in the language of Theorem D.2, it appears unsanitized in *at most one* of these subinstances, which turns out to be crucial to bound the privacy loss over all recursive steps of the algorithm. Bounding the number of times (sanitized and sensitive) edges appear in recursive sub-instances makes it possible to apply Theorem D.2 to our problem.\n\n>In Algorithm 2, what does \"satisfying the conditions on Algorithm 2\" mean?\n\nWe apologize for the typo. It should say “satisfying the conditions on Line 7 of Algorithm 2”, which is the following condition (stated in the description of Algorithm 2): $\\hat{w}(\\hat{S}{\\_v}^i) \\le \\hat{\\lambda}(s,v)+ (2 \\lfloor \\log_2 |U| \\rfloor - i) + 1) \\Gamma_{\\text{iso}} + \\Gamma_{\\text{values}}$. We will update the manuscript to include algorithm lines and fix this typo.\n\n>In the composition theorem, can the authors specify the privacy model (wrt to the sensitive dataset and sanitized data),i.e., the neighborhood definition wrt the two types of data.\n\nThe theorem works generally for any replacement definition of neighboring datasets where the indices of the dataset (e.g., the $\\binom{n}{2}$ edge weights) are public, but any given datapoint may be replaced with a different value. The key properties we require are that (a) the index set is public and (b) any neighboring datasets $X, X’$ differ at a single index. We will update the manuscript to clarify this."}, {"review_id": "YQUlXlc3ur", "reviewer": "Reviewer_EWfq", "summary": "This paper presents a purely differentially private (DP) construction of approximate Gomory-Hu tree. As corollaries, they get purely differentially private approximation algorithms for all-pairs min-cuts, global min-cuts, and minimum k-cuts, all with nearly linear additive error which also runs in poly time. \n\nAt a high level, the authors closely follow the recent line of work on approximate Gomory-Hu tree construction in [LP21]. But along the way they have to make a number of changes to privatize the algorithm. \n\nFirst of all, the min-isolating cuts alone are relatively straightforward to privatize. Making it useful for the Gomory-Hu tree application requires an extra contracting property. In Appendix B, the authors introduce line 11 (the middle highlighted part) in Algorithm 1 so that a contracting property is approximately preserved after introducing noises. This contracting property is mainly used to bound the recursion depth, similar to the recursive approximate Gomory-Hu tree analysis in [LP21]. The trick in line 11 here is to introduce extra deterministic weights to the undesirable cuts so as to beat the noisy perturbations. The same trick is also used in Appendix D.\n\nThen Appendix C is mainly the DP version of Cut Threshold Step in [LP21]. An interesting modification is line 7 of Algorithm 2, where they try to include more vertices for smaller isolating cuts. \n\nI have reviewed an earlier version of this paper, and I'm happy to report that significant revisions have been made in improving the exposition of the paper. In particular, the technical overview appears to be substantially rewritten, with very well-structured intuitions along the way.\n\nOverall this looks like a nice paper. Their approach seems to follow [LP21] closely but there are a number of non-trivial modifications to be made for privacy both in the algorithms and in the analysis. In particular, they also have to work with recursive subsets that are not necessarily disjoint, but only known to have bounded overlap. \nTarget audience would include people who work on differential privacy and graph algorithms in general. The paper also does a decent job in explaining the contexts and giving a high level technical overview. As such, I would vote for acceptance.", "questions": "You introduced edge weight differential privacy in Appendix A.5, but in Appendix G you tried to draw an analogy between min s-t cuts and all pairs shortest path distances without mentioning that many existing works considered different privacy notions for these two problems. How are these two problems comparable? \n\nAlso, in line 1349-1350, you appear to be describing an obstacle in min s-t cuts. Why exactly is this an obstacle? In particular, for all pairs shortest path distances, even under edge weight differential privacy, the value set of the shortest path distances can also change in at least $\\Omega(n)$ entries right? If these problems are somewhat comparable, then this shouldn't really be an obstacle?\n\nRegarding your discussion on synthetic graph, perhaps you want to discuss and/or cite a recent work that goes along the direction that you proposed:\nBreaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition by Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* the problem considered is of general interests, many real-world problems can be formulated as cut problems\n* the technical approach consists of neat observations and non-trivial modifications to recent developments of fast algorithms for graph cuts; considering the versatility of the isolating cut framework in the design of non-private graph algorithms, I expect many nice applications following a successful example of privatizing the isolating cut framework, and the authors also demonstrated some of these applications.\n* the writing is clear and easy to follow\n* all the claims come with rigorous proofs\n\nWeaknesses:\n* this is clearly a theoretical paper, with constants and/or poly-log hidden in the bounds; Needless to say, figuring out the constants and supplying numerical evaluations would improve the impacts and outreach of the paper,  and I encourage the authors to do so considering the algorithms are not insanely complicated. For this revew though, I tried to look up the reviewer guidelines but did not see that experiments are explicitly stated as mandatory, where the wordings are phrased as theoretical or experimental supports; so I would not hold the lack of experiments strongly against the authors.", "was_revised": true, "final_justification": "*The problem considered is of general interests, many real-world problems can be formulated as cut problems\n*The technical approach consists of neat observations and non-trivial modifications to recent developments of fast algorithms for graph cuts; considering the versatility of the isolating cut framework in the design of non-private graph algorithms, I expect many nice applications following a successful example of privatizing the isolating cut framework, and the authors also demonstrated some of these applications.\n*Their approach follows [LP21] closely but there are a number of non-trivial modifications to be made for privacy both in the algorithms and in the analysis. In particular, they also have to work with recursive subsets that are not necessarily disjoint, but only known to have bounded overlap. Target audience would include people who work on differential privacy and graph algorithms in general. \n*The paper also does a decent job in explaining the contexts and giving a high level technical overview. \n\nAs such, I would vote for acceptance.", "rebuttal": ">You introduced edge weight differential privacy in Appendix A.5, but in Appendix G you tried to draw an analogy between min s-t cuts and all pairs shortest path distances without mentioning that many existing works considered different privacy notions for these two problems. How are these two problems comparable?\n\nThese two problems are not directly related (i.e. as far as we are aware, results for one don't imply results for the other). Our goal was to contrast the progress on the private shortest path problem to the APMC problem (please see the next answer). \nRegarding privacy models, most works on the two problems use the same model of edge privacy, where two graphs are defined to be neighboring if they differ in one edge weight by at most one. Works on DP shortest paths also assume the graph *topology* is public (but the edge weights are private). In our setting, we do not need such assumptions.\n\n>Also, in line 1349-1350, you appear to be describing an obstacle in min s-t cuts. Why exactly is this an obstacle? In particular, for all pairs shortest path distances, even under edge weight differential privacy, the value set of the shortest path distances can also change in at least Omega(n) entries right? If these problems are somewhat comparable, then this shouldn't really be an obstacle?\n\nThe discussion on lines 1344-1350 is attempting to motivate a different version of our problem where we only ask to release the pairwise min s-t cut *values*, rather than the cuts themselves. In the DP shortest paths problem, there is a separation between these two versions, as sublinear error is possible for the value problem, but linear error is necessary to release an approximate shortest path. Thus, we are motivated to ask if such a separation also exists for min $st$ cuts. \nThe lines starting from “One might wonder…” argue that the simple, but natural, algorithm of just computing pairwise min $st$ values and releasing a noisy version can have large errors since changing even one edge can impact $\\Omega(n)$ min cut values. Please see lines 178-181 for further discussion. \nWe are not arguing that achieving sublinear error for this values problem is impossible, rather we are hopeful that future work could make progress on this interesting open question."}]

Author rebuttal:

Meta-review: This paper designs an 
edge-differentially private algorithm to compute all s-t minimum cuts in a weighted graph with additive error $\tilde O(n/\varepsilon)$. The adjacency model allows the weight of a single edge to increase or decrease by 1.

Overall, the reviewers were impressed with the result and its presentation. Cuts and related properties are fundamental to graph analysis, and so a relatively clean characterization such as this one feels like a fundamental result. 

The reviewers did have several concerns about the current presentation, which I hope the authors will address.

*Correctness.* One reviewer has concerns about correctness, detailed in their review. While the other reviewers were confident that the final result is correct, we encourage the authors to use the comments and discussion to further improve and clarify the presentation. 

*Adjacency notion and semantics.* Another major concern was the meaningfulness of the adjacency model for privacy. The authors write, in one response, 

> consider a social network, where each node represents a person and a weighted edge represents the strength of the relationship between two people. Edge-neighboring privacy corresponds to the case where the set of people are known, but we do not want to leak information about any specific friendship relation.

The example is not convincing. For the additive error bounds in the paper to be meaningful, the magnitude of the allowed change to one edge's weight must be at most an $\varepsilon$ fraction of the weight of a typical edge. That means only a tiny relative change in the strength of a relationship can be hidden. 

A more meaningful example might come from settings where each edge represents a type of person (say, those who work at one endpoint's location and live at the other's), and the weight represents the number of people of that type. 

I would encourage the authors to discuss the limitations of this modeling more transparently in the paper. The authors explain their model clearly in the submission's introduction, and discuss it in Appendix A.5. While the discussion elucidates the mathematical model clearly, the only justification for its interest is the fact that it is the most general standard model that allows any approximation at all. Giving an example of data sets where minimum cuts are a useful tool _and_ the adjacency model makes sense is important. If the authors are not aware of any such settings, they should say so.
Decision: Accept (poster)