Nearly Tight Bounds For Differentially Private Multiway Cut
Authors: Mina Dalirrooyfard
Slobodan Mitrović
Yuriy Nevmyvaka
Venue: NeurIPS 2023 oral (2023)
Keywords: Differential Privacy
clustering
multiway cut
min cut
graph partitioning
TL;DR: We provide the first DP algorithm for min s-t cut and multiway k cut.

Abstract: Finding min $s$-$t$ cuts in graphs is a basic algorithmic tool, with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this problem, we are given two nodes as terminals and the goal is to remove the smallest number of edges from the graph so that these two terminals are disconnected. We study the complexity of differential privacy for the min $s$-$t$ cut problem and show nearly tight lower and upper bounds where we achieve privacy at no cost for running time efficiency. We also develop a differentially private algorithm for the multiway $k$-cut problem, in which we are given $k$ nodes as terminals that we would like to disconnect.
    As a function of $k$, we obtain privacy guarantees that are exponentially more efficient than applying the advanced composition theorem to known algorithms for multiway $k$-cut.
    Finally, we empirically evaluate the approximation of our differentially private min $s$-$t$ cut algorithm and show that it almost matches the quality of the output of non-private ones.

Nearly Tight Bounds For Differentially Private Multiway Cut
Mina Dalirrooyfard
Slobodan Mitrovic"
Machine Learning Research
Department of Computer Science
Morgan Stanley
UC Davis smitroviccuccavis..o edu
mina.
Yuriy Nevmyvaka
Machine Learning Research
Morgan Stanley
Abstract
Finding min s-l. cuts in graphs is a basic algorithmic tool, with applications image segmentation, community detection, reinforcement learning, and data clus- tering. this problem, we are given two nodes as terminals and the goal is to remove the smallest number of edges from the graph that these two terminals are disconnected. We study the complexity of differential privacy for the min s-t problem and show nearly tight lower and upper bounds where achieve privacy at no cost for rumning time efficiency. We also develop a differentially private algorithm for the multiway k-cut problem, in which as terminals that we would like to disconnect. As a function of k, we obtain privacy guarantees that exponentially more efficient than applying the advanced com- position theorem to known algorithms for multiway k-cut. Finally, we empirically evaluate the approximation of differentially private min cut algorithm and show that it almost matches the quality of the output of non-private ones.
given k nodes
Introduction
Min s-t cut, more generally Multiway k-cut, is fundamental problem in graph theory and occupies central place in combinatorial optimization. Given a weighted graph and k terminals, the multiway k-cut problem asks to divide the nodes of the graph into A partitions such that (I) each partition has exactly one terminal, and (2) the sum the weights of edges between partitions, known the cul value, is minimized [9] Multiway k-cut is clustering method used in a large
variety of applications, including energy minimization 21 and image segmentation [27 32 in vision,
reinforcement learning [25]. community detection 33 29 and many other learning and clustering
tasks 5 30
The above applications are carried on large data sets, and more and more frequently those applications are executed on sensitive data. Hence, designing algorithms that preserve the privacy of data has been given substantial attention recently. A widely used and conservative standard of data privacy is differential privacy (DP) developed by Dwork [12] which indicates that an algorithm is differentially private if, given two neighboring databases, it produces statistically indistinguishable outputs. When DP applied to graph data, two variants of DP were introduced [19]: edge DP, two neighboring graphs differ in only one edge, and in node DP, two graphs neighboring if one graph is obtained
These authors contributed equally this work
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

from removing one node and all the edges incident to that node from the other graph. In this work, we focus on the edge DP. In a large fraction of cases, the nodes of network are public but the edge attributes - which are the relationships between nodes - are private.
For many clustering algorithms such as k-means, k-median, and correlation clustering, tight or near-tight differentially private algorithms have already been developed 33 20 8] In particular, tight algorithms for differentially private min-cut has been long known [8] where the min-cut problem asks to divide the graph into two partitions such that the cut value is minimized; in the min-cut problem, there no restriction that two nodes must be on different sides of the cut. Even though min-cut and min s-t cut might seem similar, the algorithm techniques for min-cut do not extend to min s-t cut, glimpse of this difference can be seen the fact that there exist polynomially many min cuts in any graph, but there can be exponentially many min s-t cuts for fixed terminals s and
Our Results and Technical Overview In this paper, we provide the edge-differentially private algorithm for min 8-1 cut and prove that it is almost tight. To the best of our knowledge, this is the first DP algorithm for the min s-t cut problem.
Our first result is an e-private algorithm for min s-t cut with ( additive error.
Theorem 1.1. For any E > O and for weighted undirected graphs, there is an algorithm for min s-t cut that is (e, 0) private and with high probability returns a solution with additive error O ((²). Moreover, the running time of this private algorithm is the same as the running time of the fastest non-private one.
Moreover, our proof of Theorem 1.1 extends to when an edge-weight changes by at most in two neighboring graphs. In that case, our algorithm is (c. 0)-private with O(n r/c) additive error.
Furthermore, our approach uses the existing min s-t cut algorithms in a black-box way. More precisely, our method changes the input graph in specific way, i.e., it adds 2(n 1) edges with special weight, and the rest of the processing is done by an existing algorithm. In other words, our approach automatically transfers to any computation setting centralized, distributed, parallel, streaming as long as there is non-private min s-t cut for that specific setting. The main challenge with this approach is showing that it actually yields privacy. Perhaps surprisingly, our approach is almost optimal in terms of the approximation it achieves. Specifically, we complement our upper- bound by the following lower-bound result.
Theorem 1.2. Any (c, 8) diffferrrtti private algorithm for min s-t cut on n-node graphs requires expected additive error of at least n/20 for any e S and 5 < 0.1.
Note that Theorem 1.2 holds regardless of the graph being weighted or unweighted. Given an unweighted graph G, let the cut (G) be the s-t cut where node is in one partition and all the other nodes are in the other partition. The algorithm that always outputs C.) is private, and has the additive error of ((n) since the value of (G) is most n in unweighted graphs. Thus one might conclude that we do not Theorem 1.1 for a private algorithm, as one cannot hope to do better than O(n) additive error by Theorem 1.2 However, for weighted graphs, this argument fails when (G) has a very large value due to weighted edge incident to s, or when a graph has parallel unweighted edges. In |Secction 5] we show an application in which one computes a weighted min s-t cut while as the input receiving an unweighted graph. We further evaluate our theoretical results on private min s-t cut in |Section 5) and show that despite our additive approximation, our approach outputs a cut with the value fairly close to the min s-t cut. Moreover, we show that it is in fact more accurate than more natural heuristics (such as outputting (G)) for a wide range of the privacy parameter e.
Theorem 1.1 and Theorem 1.2 depict interesting comparison to differentially private min cut algorithms. Gupta et al 18 provide an c-private algorithm with Ollog n/ce) additive error for min cut and shows that any e-private algorithm requires ((log additive error. The large gap between
nodes vi,-.., in addition to and and add v, to both and t for all Suppose the weight of all edges is 1. There are 2n min s-t cuts, as each min s-t cut should remove exactly one edge from each s - Vi- - path; either (s, v.) or (v,, t) is fine. In this example, there are n 2 min cuts: for each i, remove edges (v:, s) and (v., t) and this would be cut of size 2. Moreover, one can show that the number of min- cuts is polynomial for any graph, there are at most (?): please !II.
TTake
2

---

e-private algorithms for the min cut and min s-t cut could provide another reason one cannot easily extend algorithms for one to the other problem.
While finding (non-private) Min s-t cut is polynomially solvable using max-flow algorithms 1 7 the (non-private) Multiway k-cut problem is NP-hard for l 2 3 10] and finding the best approximation
algorithm for it has been an active area of research [0] 6 2 24 The best approximation factor for the Multiway cut problem is 1.2965 28 and the largest lower bound is 1.20016 3 24 From more practical point of view, there are a few simple 2-approximation algorithm for multiway k-cut such as greedy splitting 34 which splits one partition into two partitions in a sequence of k - 1 steps. Another simple 2-approximation algorithm by [10] is the following: (1) if the terminals of the graph are $1, $1....: Sks for each i, contract all the terminals except s; into one node, t,; (2) then run min s-t cut on this graph with terminals 8,, 4;; (3) finally output the union of all these l cuts. This algorithm reduces multiway k-cut into & instances of min 8-1 cut. Hence it is easy to see that if we use a c-private min s-t cut with additive error r, we get a ke-private multiway k-cut algorithm with additive error kr and multiplicative error 2. In a similar way one can make the greedy splitting algorithm private with same етτоr guarantees. Using advanced composition [13 [6 can further reduce this dependency polynomially at the expense of private parameters. We design an algorithm that reduces the dependency on k of the private multiway cut algorithm to log k. which is exponentially smaller dependence than applying the advanced composition theorem. We obtain this result by developing novel 2- 2-approximation algorithm for multiway k-cut that reduces this problem to log k instances of min s-t cut. Our result is represented in Theorem I.3] and we defer the proof to supplementary materials. We note that the running time of the Algorithm of Theorem 1.3 is at most Olog k) times the private min 8-t cut algorithm of Theorem 1.1
Theorem 1.3. For any e > O, there exists (c. 0) -private algorithm for multiway k-cut weighted undirected graphs that with probability 1 - 1/n at least returns a solution with value 2 - OPT O log k/c), where OPT is the value of the optimal non-private multiway k-cut.
Finally, we emphasize that all our private algorithms output cuts as opposed to only their value. For outputting a number æ privately, the standard approach is to add Laplace noise Lap(1/e) to get an e-private algorithm with additive error most (1/ec) with high probability.
Additional implications of our results. First, the algorithm for Theorem 1.1 i.c.. Algorithm
uses a non-private min s-t cut algorithm in black-box manner. Hence, /Algorithm 1 essentially translates to any computation setting without asymptotically increasing complexities compared to non-private algorithms. Second, BoaonddAAlgorttio Algorithm 2) creates (recursive) graph partitions such that each vertex and edge appears in (log k) partitions. To see how it differs from other methods, observe that the standard splitting algorithm performs k- 1 splits, where some vertices appear in each of the split computations. There are also LP-based algorithms for the multiway k-cut problem, but to the best of our knowledge, they are computationally more demanding than the 2-approximate greedy splitting approach. As a consequence, in the centralized and parallel settings such as PRAM, in terms of total work. Alloorthh 2 depends only logarithmically on while the popular greedy splitting algorithm has a linear dependence on k. To the best of our knowledge, no existing method matches these guarantees of Algorithm 2
2 Preliminaries
In this section, we provide definitions used in the paper. We say that an algorithm A outputs an (a, approoitoooiinnooonn to minimization problem P for 2 1, 2 0, if on any input instance I, have (TT I aA((T) + 3 where A(T) is the output of AA on input I and OPT(TT is the solution to problem P on input T. We refer to and 3 as the multiplicative and additive errors respectively.
We use we to refer to the edge between nodes u and v. Let = (V, E, wa) be a weighted graph with node set V, edge set E and we 122 + Rzo. where for all edges ue E E, wc(wv) > 0, and for all uv & E, wG(ur) = 0. For any set of edges C, let wC(C)= = Eeer we(e). If removing C' disconnects the graph, we refer to C' as cut set. When C is a cut set, we refer to Wc(C) as the weight or value of C. We drop the subscript G when it is clear from the context. For subsets A, B C V. let E(A, BB be the set of edges wy e E E such that E A and E B.
Graph Cuts
Definition 2.1 (Multiway k-cut). Given k terminals 81, 8ks a multiway k-cut is a set of edges C. C E such that removing the edges in C disconnects all the terminals. More formally, there
3

---

exists k-disjoint node subsets Vi...., V& E V such that E Vi for all i. U, = V, and C== () EV, V,). The Multiway k-cut problem asks for a Multiway k-cut with the lowest value.
In our algorithms, we use the notion of node contructions which we formally define here.
Definition 2.2 (Node contractions). Let Z S V be subset of nodes of the graph G EV,E, w.). By contracting the nodes in Z into node [", we add node 1* to the graph and remove all the nodes in Z from the graph. For every V \ Z, the weight of the edge th is equal >xez wa(vz). Note that if none of the nodes in has an edge to v, then there is no edge from t to v.
Differential Privacy We formally define neighboring graphs and differential private algorithms.
Definition 2.3 (Neighboring Graphs). Graphs G = (V, E, w) and G' = (V, E', w²) are called neighboring if there ue V2 such that (wg(uv) we (uz) S 1 and for all u'v' # uv, u'v' E V2, we have vo(("' (1') = (u'v("'
Definition 2.4 (Differential 12) (randomized) algorithm A is (c, 8 (or (c, 6)-P)
for any neighboring graphs G and G' and any of outcomes O C Range(A) it holds
Pr[A(G) & O S e Pr[A(G") E 0] 0 6.
When 8 = 0, algorithm A pure differentially private, or e-private.
Definition 2.5 (Basic composition [14 13].. Let el....,fe > 0 and , 2 O. If we run I. (possibly adaptive) algorithms where the i-th algorithm is (et, 6D)- then the entire algorithm is 6t)-DP.
(E1 +... Ec, 01
Exponential distribution. For À > O. we use X Exp(X) to denote that random variable X drawn from the exponential distribution with parameter X. In our proofs, we use the following fact. Fact 2.1. Let X ~ Exp(A) and = 2 0. Then Pr [X 2 2] exp (-A=).
Laplace distribution. We use X ~ Lap(b) to denote that X is random variable is sampled from the Laplace distribution with parameter b. Fact 2.2. Let X Lap(b) and
Then
Pr 2) = exp (-x) and Pr Pr[]X] =| (-
Fact 2.3. X,Y ~ Exp(E). Then, the distribution X Y follows Lap(1/e).
We use Stap to denote the cumulative distribution function of Lap(b), i... Shap 26 exp (-1z) [x] We use Flup to denote the cumulative distribution function of (ap,
exp
i <
Frap (x) [
exp (-
otherwise
When it clear from the context what b is, we will drop from the superscript. Claim 1. For any i and ' 0 holds
Fl +
S ee and Sapp +
=e
Fl/e (t)
stae (t)
The proof of this claim is standard and, for completeness, appears in the Supplementary material.
3 DP Algorithm for Min s-t Cut
Our DP min s-l cut algorithm quite simple and is provided as Algorithm I] The approach simply adds edge between and every other node, and an edge between / and every other node. These edges have weight drawn from Exp(e). The challenging part is showing that this simple algorithm actually preserves privacy. Moreover, when couple the
In this section, we prove Theorem 1.I

---

Algorithm 1: Given a weighted graph G, this algorithm outputs DP min s-t cut.
Input :A weighted graph = (V, E,
Terminals and t
Privacy Parameter c
for E V \ {s,t) do
Sample s,s Exp(e) and Xt, Exp(e).
In G' add an edge between and with weight X and edge between & and with weight X
return the min s-t cut in (the modified) G
approximation guarantee of Alggorthm I with our lower-bound shown in the Supplementary material, then up to a 1/c factor| Algorithmm Ijyields optimal approximation guarantee.
Remark: Technically, there might be multiple min s-t cuts that can be returned on Line 4 of Algorithm We discuss that, without loss of generality, it can be assumed that there is unique one. We elaborate on this in the Supplementary material.
3.1 Differential Privacy Analysis
Before we dive into DP guarantees of Algorithm we state the following claim that we use in our analysis. Its proof given in the Supplementary material.
Lemma 3.1. Suppose and y are two independent random variables drawn from Lap(1/e). Let o, 0,3,7 7 be three fixed real numbers, and let T 2 O. Define
P(a, = Pr [ < kay B,x y 7).
Then, it holds that
1 + (T
< eTe
P(a,3,7)
Lemma 3.2. Let T be the edge-weight difference between two neighboring graphs. Algorithm (4Te,0)-Di
/ is
Proof. Let G and G' be two neighboring graphs. Let edge = uv be the one for which we in G and G' differ; recall that differs by at most T. To analyze the probability with which Ahicch/Algorihmm ] outputs the same cut for input G as it outputs for input G', we first sample all the X and X for x E {s, 1, u, v). Intuitively, the outcomes of those random variables are not crucial for the difference between outputs of Algorithm I invoked on G and G¹. We now elaborate that.
Consider all the s-t cuts not only the minimum ones in G' before Xa,.s Xs,es Xx,. and Xx.. are sampled; for instance, assume for a moment that those four random variables equal 0. Let Call-st-cuts (G) be all those cuts sorted in a non-decreasing order with respect to their weight. Observe that Call-st Call-st-cuts (G) = 2-- As we will show next, although there are exponentially many cuts, we will point only four of them as crucial for our analysis. This will come very handy in the rest of this proof. We now partition Call-st- ftlllst-cuuts cuts (G) into four groups based on which u and v are on the same side of the cut as s. Let (G) be the subset Can--s- -tlt-st-euts(C (G) for which u on the same side of a cut as while is on the same side of the cut as l. Analogously we define C,, (G). We use Cu (G) to represent the subset Call-st-cute (G) for which s, u, and u are all on the same side. Finally, by Co (G)) we refer to the subset of Call-st-euta (G) for which f, u, and are all on the same side.
Let Cu. Co. Cu.v, and Cg be the min cuts in (G), (G), (G), and Cg)G), respectively. before X X,,v. Xx, and Xt, are sampled. is an easy observation that sampling X X,,us X,,0s Xz, and Xe, and altering the weight of the edge changes the weight of all the cuts in C. (G) by the same amount. This same observation also holds for (,), (G) and GG). This further implies that the min s-l cut of G after X. Xs,v Xt. and Xx,r are sampled will be among Cy, C.. Ca and Cg. Observe that these four cuts are also the minimum-weigge cuts in C., (G"), C.) Ca (G"), and Co Co'G", respectively.
5

---

In other words, the min s-t cuts in G and in G' are among Co, C2 Ca.e and Cg. but not necessarily the same; this holds both before and after sampling X x. X X Xt.u and X,,. In the rest of this proof, we show that sampling s. Xs.s Xt and Xt. makes it likely that the min 8-f cuts in G and G' are the same cut.
The ratio of probabilities in G' and G that C. is the min s-t cut. Simply, our goal is to compute
Pr (wo (Cw) < wo (Co) A we (Cw) < war (Cu,e) A wer (Cu) < we (Co) Pr [C,) (C. A (C, < wG wG(CCu) wa wC(C
(I)
First consider the case we(e) (e) + T, for some > 0. For the case of calculation, for I E {0, fu, u.j, define A, = (G(CC)) (c(C2) - and define A. = wc(C..) wG(C,) before 8..u Xx,u, Xt, and Xt, are sampled. In the rest of this proof, we are analyzing the behavior of cuts when Xa,u, X Xe,u and Xt, are sampled. Then, we have
Pr (C. < wo(C.) A wa(Cn) < ww A wo(C.) < wa(Co))
=Pr(A + X.N + XI, < Xe, tou+A +N,
A Au, + Xa,v + Xt,a + < Xt, + Xi,u A Ao + Xe,v tr, + T Xa,v + Xe.u
= =Pr(A, + Xa. + Xx, < Xxx + Xs,
A An, + Xa, + < Xt. A Ao + Xt, + Xaul.
(2)
Now, we replace X X1,v by and Xt,u Xx,u by y. Then, Eq. (2) be rewritten as
Pr (C.) (C. A wo(C.) < wC.Cu.v) wo(C.) wCo)
= =r + < A. A x -A. 7 A y - TJ.
T].
Applying the same analysis for G' we derive
Pr Frler (C.) (C,) A war (Cu) < wo (Cu,u) A we (C,) < w. (Co)
= =Pr[A, + Nav + XI,u < Xe, + +aa
A Du, + +X, + Xi,u < X1, + Xe, A A + +X, + Xt, Xx,v + X
-Pr[A, + Xan + Xe,u < Xx,, + xa,u A Du, + +Xav < Xxw A Do + Xex < Xaul-
Replacing Xa, - Xx,, by x and Xe,u Xs,, by y yields
Pr [ww (C.) < wa (Cv) A we (Ca) < wa (Cu.o) A (C,) < wo (C
Pr x +
A, A Au, <<===---- -Ag..
Note that by Fact 2.3 we have that æ and y follow Lap(1/e). Moreover, observe that the random
variables x and y are independent by definition. Therefore, by invoking Lemma 3.1 with
A,, - T. 3 Ds - т, and 7 A, we derive
Pr Pr < wa (Co) A wo (Cu) < wo (Cu,)) A wor (Cu) < wo (Co) Pr (C,) < WC(Co)) A WC(CCu) < (C,C) A wC(CC.) wc(C))]
S Ste
Considering the second case we(e) + wa (e). for some 0, we derive that the ratio Bq. (1) is upper-bounded by < crre
The remaining cases. The proof for the remaining case, i.e., analysis when Co, Cu, and Cp is the minimum, follows the same steps as the case we have just analyzed.
Finalizing the proof. It remains to discuss two properties that are needed to complete the proof. First, our analysis above is applied for all but 4 random variables X fixed. Nevertheless, our analysis does not depend on how those random variables are fixed. Therefore, for any fixed cut C, summing/integrating over all the possible outcomes of those variables yiclds
Pr
Algorithm
outputs C given G)
outputs C' given G*] S Are
Pr
Algorithm
Second, our proof shows the ratio of cut C' being the minimum one in G and G'. However, the DP definition applies to any set of multiple cuts. It folklore that in the case of pure DP, i.e., when 6 = 0, these two cases are equivalent. This completes the analysis.

---

3.2 Approximation Analysis
Observe that showing that Algorithm 1 has O(n/c- log n) additive error is straightforward random variable drawn from Exp(b) is upper-bounded by O(log n//b) whp. Lemma 3.3 proves the O(n/c) bound. On very high level, our proof relies on the fact that for a suffictenlyy large constant it holds that only a small fraction of random variables Xi, exceeds c/t; this fraction is e
Lemma 3.3. With probability least 1 n=2 Algorithm 1 outputs min s-t cut with additive error O(n/e).
Proof. Let G be an input graph to Algorithm and let G be the graph after the edges on Line 2 added. G contains 2(n - 1) more edges than G. This proof shows that with probability least 1 1-n- the total sum of weights of all these edges is Onn/c).
We first provide a brief intuition. For the sake of it, assume = 1. Whp, each Xi, weighs at most log n. Also, consider only those X,, such that X,,; 2 2: the total sum of those random variables having weight less than 2 is O(n). It is instructive to think of the interval [2. log ni being partitioned into buckets of the form [2 2 Then, the value each edge added by Algorithm falls into one of the buckets. Now, the task becomes upper-bounding the number c; of edges in bucket i. That is, we let Y.,, = 1 iff X.,u E [2', 2 which results in C; = =E (Y,, + Yi,u)- Hence, c; is a sum of 0/1 independent random variables, and we use Chernoff bound to argue about its concentration.
There are two cases. If [c/] is more than Oloog n). then C₁ E O (c,]) by the Chernoff bound. If IE [cs] E o(log n), e.g., E [c]] = O(), we can not say that with high probability E O [cs]). Nevertheless, still holds e E O(log whp.
Edges in B(G) \ F(G) with weights more than 5 log Let Y ~ Exp(e). By Fact 2.1 5 1o
Pr Y
= exp log = n 5 Since each X and Xt,e is drawn from Exp(c).
we have that for n 2 with probability least n each of the edges in E(G) \ E(G)) has weight at most 5 logn
Edges in E(G) E(G) with weights at most 5 log Observe that the sum of the weights of all the
edges in E EG) having weight at most 2/c is (n/c). Hence, we focus on the edge weights in We partition this interval into Ollog l) subintervals where each, except potentially the last one, of the form [2'/e, 2 11))
the interval log n
Let Y ~ Exp(cc. We have
Pr ( 2 /e)] Pr Y 2 2'/e| = -
Let be the number of random variables among X and X whose values belong to (2'/e, 2 /e). Then, we derive
2(n
2n
2n
F [ca] <
2²
22
2
where to obtain the inequalities, we use that i >> 1. By the Chernoff bound, for appropriately set 2n
constant > 0, holds that c; < 6 max (log n, 22: with probability at least 1 - n -5 By the union
bound, this claim holds for all the Olog log n) partitions simultaneously and with probability at least 1 - n Hence, with probability at least 1 n -4 the sum of the edge-weights in E(G) E(G)
across all the Olog log rı) partitions is most
log(5 n)
2n 22i
2
(poly log n)
2n
b-axx log
+2b
poll log logn+8h" E O
2
$20
where we used max(log n, 2n/22i) < log n + 2n 2n/22 By taking the union bound over both cases, we have that with probability least 1 n it holds that the sum of the weights of all edges added
to G is (n/e). Hence, with probability 1 -2 at least, the min s-l cut in G has weight at most the min s-t cut in G plus Onn/e). This completes analysis.
7

---

4 DP algorithm for multiway cut
In this section we show our approach for proving Theorem 1.3 restated below.
Theorem 1.3. For any e > O, there exists an (c. 0)- privaae algorithm for multiway k-cut on weighted undirected graphs that with probability 1 n at least returns solution with value 2 OPT O(n log k))), where OPT is the value of the optimal non-private multiway k-cut.
We first develop an algorithm for the non non-private multiway k-cut problem and then use it to prove Theorem 1.3 The algorithm we design invokes a min s-l cut procedure Olog k) times.
4.1 Solving Multiway Cut in log k Rounds of Min s-t Cut
Algorithm 2 first finds a cut that separates $1,.... Sk from sk'+1.-... -g.- This separation obtained by contracting $ Sj into single node called contracting $1'+1,.... Sy into a single node called t, and then running min s-t cut on this new graph. Afterward, each of the two partitions is processed separately by recursion, and the algorithm outputs the union of the outputs on each of the two partitions.
Our new myltiway k-cut algorithm is presented in Algorithm 2
Algorithm 2: Given a weighted graph G, this algorithm outputs multiway k-cut. Input :A weighted graph G = (V, F,
Terminals $1 $1,..., 8k
A min s-t cut algorithm A that with probability 1 - a is (1,ee())-approxiiaa)
i then
return G as one partition
3 else
Let k' [
Let G be the graph obtained by contracting $1,...; Sk into and contracting 81+1, into t.
Run algorithm A on G with terminals s, to obtain cut C' with partitions TN and Gz.
For i 1, let G; be the graph obtained from G by reversing the contraction of terminal
nodes.
Let C1 be the output of Algorithm 2 on G1 and C₁ be the output of Algorithm 2 on G2- return Ci U C2 UC.
We first show that in each recursion level of the algorithm, we can run the min s-1 cut step Line 6 of all the instances in that level together as one min cut, so that we only run Oloo k) many min s-t cuts.
Lemma 4.1. Algorithm 2 is a reduction of multiway k-cut on n-node graphs to OOlog k) many instances of min s-1. cut on O(n)) graphs. Moreover, T(A, n. m) the running time of A on an n-node m-edge graphs, Algorithm runs in Ollog k. [T(,,)) n) + ml).
Proof. Let G be the input graph and suppose that it has n nodes. If we consider the recursion tree of the algorithm G, we can perform the min s-t step (Line 6) of all of the subproblems on one level of the recursion tree by single min s-t cut invocation. To see this, assume that Gi',... ,.....,G G are in level r' of the recursion tree for r = 2r'-1, and for sake of simplicity, assume that i: a power of 2. Let fy be the two terminals in G (defined in Line 5) for i E {1,..., r). We can think one graph G" Contract ,, into and contract t .2.....5 t, into f, obtain the graph G"' from Gr'. Then performing min s-t cut algorithm on G equivalent to performing min s-l
of the collection of graphs G ....,Gr G
each of Gy', there is no edge between G.¹ and G² for any i.j. Note that since " G are disjoint and are subgraphs of G, Gr' has at most nodes. Moreover, the node contraction processes in each recursion level takes at most O(m) as each edge scanned at most once.
8

---

To prove that Algorithm 2) ouiputs multiway k-cut that is a 2-approximation of the optimal multiway k-cut, we first present few definitions. Given graph G with node set V. a partial multiway k-cut is a set of disjoint node subsets Vi...., VE such that for each i, terminal E V,. Note that Vi U... V not necessarily the whole V. For set of nodes 5 S V, let (S) be the sum of the weights of the edges with exactly one endpoint in S, i.e., the sum of the weights of the edges in E(S. V \ S). Let
w (((()) be the sum of the weights the edges with both endpoints in S. Theorem 4.1 is the main result in this section and we state the proof of it the Supplementary material
Theorem 4.1. Let e(n) be convex function and G = (V. E, w) be a weighted graph. Let A be an a outputs a ((n))-approxiime for constants > 0, C > O. Then, for any graph with terminals s,,..., Sy and any partial multiway k-cut Vi,... V2 of it, Algorithm 2 ouiputs a multiway cut that with probability
algorithm that with probability
min s-t cut for e(n) = cn/e
aO(oo k) has value at most Σ 8(1)) + (VE(V)) + Olog (k)e(n)) where V = V [
A direct Corollary of Theorem 4.1 is 2 2-approximation algorithm of the optimal multiway k-cut. Recall that the novelty of this algorithm is in using (log k) many min s-t cut runs as opposed to O(k) which is depicted in Lemma 4.1
Corollary 4.1. Given a graph G, integer k 2 2 and any exact min s-t cut algorithm. Algorithm 2 returns a multiway k--cut that is 2-approximation of the optimal multiway k-cut.
Proof. Let A be an exact s-t-cut algorithm that is part of the input to Algorithm 2 e(n) 0. Let CALG be the output of Algorithm 2 By Theorem 4.1, CALG is a multiway k- cut. Let CoPr be the optimal multiway k-cut with partitions Vi.... Vg. Note that there are no nodes that are not partitioned, and hence w w(E(V) = 0. So by Theorem 4.1 we have that w( w(CALG) I E (V,V = 2w(CoPT).
So we have
4.2 Differentially Private Multiway Cut
Our Differentially Private Multiway cut algorithm is essentially Algorithm 2 where we use a differ- entially private min s-t cut algorithm (such as Algorithm 1p in Line 6 to compute a differentially private multiway k-cut. This concludes the approach for Theorem 1.3 which is direct corollary of Theorem below.
Theorem 4.2. Let c > 0 be a privacy parameter, G an n-node graph, and A an c-DP algorithm that with probability least 1 - -1/n² computes min s-t cut with additive error ((e(n)/c) on any n-node graph. Then, Algorithm 2 is a (c (clog DDP algorithm that with probability at least - O(log k) .)n"" 2 finds a multiway k-cut with mulliplicative error 2 and additive error O(log k- e(n)/e).
Proof. The error guarantees are a direct result of Theorem 4.1 and anddaadmdaa Lemma 3.3 Hence here we prove the privacy guarantee, Consider the recursion tree Algoooti 2 which has depth (log k). As proved by Lemma 4.1] each level of the recursion tree consists of running algorithm A on disjoint graphs, and each level is e-DP. By basic composition (see Definition 2.3), since Algorithm is composition of Olog k) many cDD mechanisms, it is (c log k)-DP.
5 Empirical Evaluation
We perform an empirical evaluation on the additive error of Algorrihmm I and validate our theoretical bounds.
Set-up. As our base graph, we use email-Eu-core network [22 which is an undirected unweighted 1, 005-node 25, 571-edge graph. This graph represents email exchanges, where two nodes and are adjacent if the person representing u has sent at least one email to the person representing v or vice-versa. However, this graph does not account for multiple emails sent between two individuals. To make the graph more realistic, we add random weights to the edges from the exponential distribution with mean of 40 (rounded to an integer) to denote the number of emails sent between two nodes. We take 10 percent of the nodes and contract them into a terminal node 8, and take another 10 percent of the nodes and contract them into another terminal node 1. We make different instances of the problem by choosing the nodes that contract into 8 or i uniformly at random. Note that node contraction into terminals is standard practice in real-world min s-t cut instances, there often nodes with

---

0.044
cut relstivee arar
0.06
tormino cut relative eror
0012
private cut relativ ener
privall cuil relutive srun
0.010
Reletive Ere
0.008
0010
0.006
Ag
0.006
0.002
0.000
0.000
30
12
14
Epsilon Inverse
Figure 1: (left) Terminal cut and private cut with error bars over 50 graph instances, for 0.5. For each instance, [Algrithhm I was run 100 times. (right) Average terminal cut value and private cut value over different values of The axis For each value of the set up the same as in the left figure.
predetermined partitions and to make a s-1 cut (or multiway k-cut) instance one needs to contract these nodes into one terminal node for each partition. We take the floor of the values X and Xt," to obtain integral weights.
Baseline. Let C. be the cut where one partition consists of only s. and let C, be the where one partition consists of only t. We compare the cut value output by Algorithm against min(w(C,) (C))). Particularly, Co is the min s-t cut of an instance and Algorithm ooutputs
Calg. then we compare relative errors wi(art))w(Co) and
Cale We refer to the
w(Co) former value as the private cul relative error, and to the later value as the terminal cul relative error.
w((C))
Results. We first set = 0.5. We then consider 50 graph instances, and for each of them, we evaluate the average private error over 50 rounds of randomness used in Algorithm I] see Figure I]left) for the results. For almost all instances, the private cut error (including the error bars) is less than the terminal cut error. Moreover, the private cut error is quite stable, and far below the theoretical bound of n/e. We next change and repeat the set-up above for each E { 14 ....... each e this set we produce 50 graph instances, measure the average private error over 100 rounds of randomness for each, and then average the terminal cut error and mean private cut error for each graph instance. In this way, we obtain an average value for terminal cut and private cut errors for each of the values; we refer to Figure I rright for the results. The linear relationship between the private cut error and can be observed in Figure right.)
J. For
Conclusion And Future Work
In this work, we investigate the differential privacy of the min s-t cut and of, its generalization, the multiway k-cut problem. For the first problem, show almost tight lower- and upper-bounds in terms the error guarantee. Moreover, our DP algorithm is as fast as the fastest non-private one. For the multiway k-cut problem, error, as opposed to (nn/c. (ekk) k) that standard algorithms lead to, in order to achieve DP. This algorithm might be of independent interest. In particular, the total running time of our multiway k-cut algorithm only (log k) more than that of the fastest non-private min s-t cut. This in stark contrast with the prior non-private 2-approximate approach, which (k) times slower than the fastest non-private min s-t cut algorithm.
develop novel approach that yields only O(n/c log k) additive
Comparing our lower- and upper-bounds, it remains to close the gap of 1/e multiplicative factor in the additive error of the min s-t cut problem. also remains open whether O k) factor in the additive error for the multiway k-cuut problem is needed. We believe that techniques relying solving LPs might be able to avoid this dependence on (log k). Finally, it would be interesting to explore whether smaller additive error possible for special but interesting classes of graphs.
As another standard heuristic one could consider random s-t cut. We do not include this baseline here as it often has very high error and the terminal cut does much better than random cut.
10

---

Acknowledgments and Disclosure of Funding
We are grateful to anonymous reviewers for the valuable feedback. Mitrović was supported by the Google Research Scholar Program.
References
[1] Ravindra Ahuja and James B Orlin. fast and simple algorithm for the maximum flow problem. Operations Research, 37(5):74--759) 1989.
[2] Haris Angelidakis, Yury Makarychev, and Pasin Manurangsi. An improved integrality gap for the cälinescu cälinescu-karloff karloff-rabani relaxation for multiway cut. In International Conference on Integer Programming and Combinatorial Optimization, pages 39-50. Springer, 2017.
[3] Kristóf Bérezi, Karthekeyan Chandrasekaran, Tamás Király, and Vivek Madan. Improving the integrality gap for multiway cut. Mathematical Programming, (83(1):77-199)) 2020.
[4] 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.
[5] Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, and Rajashekar Reddy. Semi- supervised learning using randomized mincuts, In Proceedings of the twenty-firsi international conference on Machine learning, page 13, 2004.
[6] Gruia Cälinescu, Howard Karloff, and Yuval Rabani. An improved approximation algorithm for multiway cut. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 48 52, 1998.
[7] Li Chen, Rasmus Kyng. Yang P Liu, Richard Peng. Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-com flow in almost-linear time. In 2022 JEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623. IEEE, 2022.
[8] Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. Near-optimal correlation clustering with privacy. arXiv preprint 2rXiv:2203.01442 2022.
[9] Elias Dahlhaus, David S Johnson, Christos H Papadimitriou, Paul D Seymour, and Mihalis Yannakakis. The complexity of multiway cuts. In Proceedingy the twenty-fourth annual ACM symposium on Theory of computing, pages 241-251, 1992.
[10] 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.
[11] E.A. Dinits, A.V. Karzanov, and M.V. Lomonosov. On the Structure of Family of Mini- mal Weighted Cuts in a Graph. 1991. URL htt.h:://booottee.e googgooooooeeoooooo le. wel.de/bbbole /tt.//ookk/ee.. ?id= OOPOKgAACAAJ
[12] Cynthia Dwork. Differential privacy. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II 33, pages 1-12. Springer, 2006.
[13] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[14] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-2884 Springer, 2006.
[15] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pages 51-60. IEEE, 2010.

---

[16] Cynthia Dwork. Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):211-007, 2014.
[17] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. Advances in Neural Information Processing Systems, 33:4040-4054, 2020.
[18] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1106-1125. SIAM, 2010.
[19) Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference Data Mining, pages 169-178. IEEE, 2009.
[20] Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering, In Proceedings of the 37th ACM JIGMOD-SIGACT-SIEE Symposium on Principles of Database Systems, pages 395-408, 2018.
[21] Vladimir Kolmogorov and Carsten Rother. Minimizing nonsubmodular functions with graph cuts-a review. IEEE transactions on pattern analysis and machine intelligence. 29(7): 1274- 1279, 2007.
[22] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection.
wdw./orddddddddeeoo data June 2014.
[23] Meng Liu and David Gleich. Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering. Advances in neural information processing systems, 33: 5023-5033 5023,5035,20 2020.
[24] Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, and Roy Schwartz. Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. In Proceedings of the fortieth anmual ACM symposium on Theory of computing, pages 11-20, 2008
[25] Ishai Menache, Shie Mannor, and Nahum Shimkin. dynmmiynamic discovery of sub-goals in reinforcement learning. In Machine Learning: ECML 2002: 13th European Conference on Machine Learning Helsinki, Finland, August 19-23, 2002 Proceedings 13, pages 295-306. Springer, 2002.
[26) Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345-354, 1987.
[27] Bo Peng, Lei Zhang, David Zhang, and Jian Yang. Image segmentation by iterated region merging with localized graph cuts. Pattern Recognition, 44(10- (1110-11):2527-25888 2011.
[28] Ankit Sharma and Jan Vondrák. Multiway cut, pairwise realizable distributions, and descending thresholds. In Proceedings of the forty- forty-sixth annual ACM symposium on Theory of computing, pages 724-733, 2014.
[29] Hyungsik Shin, Jeryang Park, and Dongwoo Kang. A graph-cut basdeed approach to community detection in networks. Applied Sciences, 12(12):6218, 2022.
[30] Apoorva Singh, Sriparna Saha, Mohammed Hasanuzzaman, and Anubhav Jangra. Identifying complaints based on semi-supervised mincuts. Expert Systems with Applications, 186: 15668, 2021.
[31] Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private k-means clustering. In Proceedings of the sixth ACM conference on data and application security and privacy, pages 26-37, 2016.
[32] Wenbing Tao, Feng Chang, Liman Liu, Hai Jin, and Tianjiang Wang. Interactively multiphase image segmentation based on variational formulation and graph cuts. Pattern Recognition, 43 (10):3208-322 22188888888...1 2010.
12

---

[33] Yapu Zhang, Jianxiong Guo, Wenguo Yang, and Weili Wu. Mixed-case community detection problem social networks: Algorithms and analysis. Theoretical Computer Science, 854: 94-104, 2021.
[34] Liang Zhao, Hiroshi Nagamochi, and Toshihide Ibaraki. Greedy splitting algorithms for approximating multiway partition problems. Mathematical Programming, 102:167-183, 2005.
13

---

A Multiple min s-t cuts
Let G and G' be two neighboring graphs, and let G and G', respectively, be their modified versions constructed by |Algorthhm II [Algorithm IJoutputs min s-t cut in G. However, what happens if there are multiple min s-t cuts in and the algorithm invoked on Line 4 breaks ties in a way that depends on whether specific edge e appears in G' or not? If it happens that is the edge difference between G and G', then such a tie-breaking rule might reveal additional information about G and G". We now outline how this can be bypassed.
Observe that if the random variables Xs,. and X were sampled by using infinite bit precision, then with probability 1 no two cuts would have the same value. So, consider a more realistic situation where edge-weights are represented by Olog n) bits, and assume that the least significant bit corresponds to the value 2-1, for an integer I. 2 O. We show how to modify adge-weights by additional (log r) bits that have extremely small values but will help obtain unique min s-t cut. Our modification consists of two steps.
First step. All the bits corresponding values from 2- to 2-t-2log remain O, while those corresponding to larger values remain unchanged. This is done so that even summing across all but most (2) edges it holds that no matter what the bits corresponding values 2 -- log x and less are, their total value is less than 2- Hence, if the weight of cut C1 is smaller than the weight of cut C2 before the modifications we undertake, then C₁ has a smaller weight than C2 after the modifications as well.
Second step. We first recall the celebrated Isolation lemma.
Lemma A.1 (Isolation lemma, (66)). Let T and N be positive integers, and let F. be an arbitrary nonempty family of subsets of the universe {1....,T) T.. Suppose each element x E (1....,TT T in the universe receives integer weight ( each of which is chosen independently and uniformly at random from {1.....)) The weight of a set S E F is defined as g(S) = =Ezs g(x).
Then, with probability at least -T/N there unique set in F that has the minimum weight among all sets of F.
We now apply Lemma A.l to conclude our modification of the edge weights in G. We let the universe {1,.... T3 from that lemma be the following 2(n - 2) elements U {(s, v) |u V(G) \ {s,t]} {(t, | v E V(G) \ {s, Then, we let F represent all min s-t cuts in G ie., S C 4 belongs to F iff there is a min s-t cut C in G such that for each (a. b) E S the cut C contains Xa,b- So, by letting N = 2n², we derive that with probability 1 1/n it holds that two cuts represented by F have the same minimum value with respect to g defined in Lemma A.I To implement y in our modification of weights, we modify the bits of each X.,v and X corresponding log to values from 2og-2logn- 2 n- N be integer between and N chosen uniformly at random.
Only after these modifications, we invoke Line of Algorithm I defined only for the sake analysis. not needed to know it algorithmically.
Note that the family of cuts F is
B Lower Bound for min s-t cut error
In this section, we prove our lower bound. Our high-level idea is similar to that of (8] for proving a lower bound for private algorithms for correlation clustering.
Theorem 1.2. Any (e, 8) ddfffffrrettta private algorithm for min s-t cut on n-node graphs requires expected additive error of at least n/ n/220 for any
and 5 0.1.
Proof. For the sake of contradiction, let A be a (c, 5) -iifferrential private algorithm for min s-t cut that any input n-node graph outputs an s-t cut that has expected additive error of less than n/20. We construct a set of 2" graphs S and show that A cannot have low expected cost on all of the graphs on this set while preserving privacy.
The node set of all the graphs in are the same and consist of V = {s8, L, ui, } where s and t the terminals of the graph and n > 30. For any 7 E {0, 1)"h, let G, be the graph node set V
14

---

with the following edges: For any 1 S S n. T; 1, then there is an edge between and v.. If 0, then there is an edge between and v,. Note that v; is attached to exactly one of the terminals aaddd. 1. Moreover, the min s-f cut of each graph G, is zero.
Algorithm A determines for each i if i is the s-side of the output cut or the I-side. The contribution of each node tú to the total error is the number of edges attached to v, that are in the cut. We denote this random variable in graph G, by e (v;). Since there are no edges between any two non-terminal nodes in any of the graphs G,, the total error of the output is the sum of these individual errors, i.c., E Ei (v:). Let (v:) be the expected value of e- over the outputs of A given Gy.
Let pF be the marginal probability that ey is on the s-side of the output s-t cut in G,. I; 0, then 2 is connected to f and so (v+) p If T; 1, then U; is connected to and so é (v;) 11 p, By the assumption that A has a low expected error on every input, we have that for any E [0, 1]",
(n+
Σ 1,T
Σ (1- 1,1=1
Let S; be the set of E {0, 13 such that T; O. and S; be the complement of S; so that r E S; if Ti = 1. Note that |S, = |S = 2n-1, Fix some i, and for any T E (0. 1)" let 7' be the same except for the i-th entry being different, i.., for all i, Ty. and T, # T/. Since G. and G,, only differ in two edges, from A being (e, (effe-diffrrentiillly private for any j we have
pr s 2c, py + 6. So for any i. we have
Σ
D
S
Σ TES:
(e2pp))
+
TES.
From Eq. (3)
we have
2n 0.05(n
Σ
Σ (1 (1-)
(E(0,1)* i:
Σ (1 p(0)
1=1 TES:
Σ (1 162( (1) +8)
i=1 TES.
n2n 8)
EES.
Where the last inequality comes from Eq. (4) Using Eq. (3) again, have that Σ Eres, pfo
2n. 0.05 + 2). so we have that 2n 0.05 +2) > n22 (1-)) 22 (2 0.05(n + +2). Dividing
by 2" we have
0.05 + 2) + e²r) n(1 8)/2.
Now since
S 1, s 0.1, and e² < 7.4 we get that
0.05 8.4(n 2) 0.45m Hence we have n < 28 which is contradiction to n > 30.
C Omitted Proofs
C.1 Proof of Claim 1
By definition, we have
Stp +T) 2 exp (xcp(-ct+ = exp (-elt + + e[1)) < exp (TE). Stap(1)
(5)
2 exp (-e|())
Also by definition, it holds Fiap (t + T) = s fLaD(T) Using Eq, (5) we derive
(t + r) S (Te( / Sampl - -i T)dr exp(Te) 1" (x) = exp(Te) (t).
15

---

C.2
Proof of Lemma 3.1
To prove the lower-bound, observe that if x < and B, then a + and y < 3 + as well. Hence, trivially holds P(a + r, 7,7) 2 P(a, 3, and hence
P(a + T, B, P(a, 3,7)
21. 1.
We now analyze the upper-bound. For the sake brevity, in the rest of this proof, we use to denote FLap and f to denote fLap. We consider three cases depending parameters a, B.
Case y 2 a + 3 + 2r. this case we have Pr + < 7|2 <a, <3] =
Pr (x + y < 7/2 <a aa+t T, < B + T|. So we have that
P(a,
a,
=Pr(x a,, x1 =F(a)F(33)
Similarly, P(a + T, + T,7) F(a + F)B(3 + r). Now using Claim P(a+t,8tT71) < 2
obtain that
P(a,8,1)
Case 7 < a B. We write P(a, 7) as follows.
8 P(a,B,7)
min(a.7-1)
F(min(a, - (y))
F(a)) (Tre f(y)dy 8
Fly f)y(ydd
1"
3
F(a) - a)
Fly v)f(y)dy
(6)
7-a
Similar to Eq. (6)
we have
gtT P(a + (,+,,,) F(a =(o r) +)+
f
JT--T
F(y- y)fly)dy
Now we rewrite
Eq. (6) as follows to obtain lower bound on P(a,B,))
F(a)s(y)dy + 1 F(y-w) - (y)dy
-(a.B,))-F(a)F((() F(a)((-------11
3-a-2r
25e 1
2 F(a)F(( a 2T) + -
F F(1-))f(wydy y-a-2r
(8)
In obtaining the inequality, used the fact that if y
b aa--a-27 2-,7
a) then 0 S (r (1y-)) ()- 27
and so by Claim we have F(a) 2 e 25e Fly
7).
Now we compare the two terms of Eq. (8)
with Eq. (7)
By Claim we have that F(a) (()-))22)))
- FFa + F - a-77--0 7) and - 27
F(y 4) dy) 2 T 1 F(7 - fy) So
have P(a,8,7) 2 e -3re 33a + 7, 3 7,7).
16

---

Case a a 2T.
Then
P(a, |
8 minna, 5)
F(min(a, -
F(3)F(3)
(9)
2 e 25c F(a+
(10)
E (F(a - -T) F(a ((
2 2e + +(3++))) (3)) F(3 r)).
(11)
Note that Eq. (9) obtained since for any y S we have - 7 y. Eg. and Eq. (11) are both
obtained using Claim 1 One can easily verify that Eq. (7) for +1 7) holds in this case as well. Using the fact that y - a 7 I 3 + y and F being non-decreasing function, we further
lower-bound bq. (7) as
B+T
P(a
F(7 - ())(( 7-a-r
g+
(((++))F(3+7)) F(a+
f(yddy
7-a-T
= +
(T (F(3 +T) - -F(7 a a-
+F( F(a (a- + (F + +7) 10(3-F3115 (12)
Eqs. (11) and (12)
conclude the analysis of this case as well.
C.3
Proof of Theorem
We use induction on k to prove the theorem. Suppose that Algorithm 2 outputs CALG. We show that the CALG is multiway k-cut and that the value of CaLg is at most wi (F(V)) H 5(V)) 2 log (k))(n). We will first perform the analysis of approximation assuming that A provides the stated approximation deterministically, and at the end of this proof, we will take into account that the approximation guarantee holds with probability 1 --a
Base case: k 1. If 1, then CALG 0, and it is multiway 1-cut and wCCAlG) 0 5(V)) + ( (F(VV).
Inductive step: k: 2 So suppose that k > 2. Hence, k/ and k- 1, where defined on Line Let (A, B) be the s-t cut obtained Line 6. where G1 is the graph induced on A and G2 is the graph induced on B. Since the only terminals in G are 81,..., 8gr, we have that Vi n..... Vv n is partial multiway k't G1. By the induction hypothesis, the cost of the multiway that Algorithm 2 finds on G1 at most w (EE((V)))
6G (VinA)+2log (k' (e))e Similarly, by considering the partial multiway (k (k-k') cut Vi++nB,.... VanB on G2, the cost of the multiway cut that Algorithm finds on G2 is at most (VV(VVVVV (B) ++ 8; (ViBB + log (K - k BI). So the total cost w (CAL.) of the multiway cut that Algorithm 2 outputs is at most
w(CALG) < w(E(V n A)) + w(E(V
(13)
86 (V (K
Σ i=
(V,nB)
w
log (K' (k") ((A))((())))))))))) 2 log (k: 1 k))
First note that CALG is multiway k-cut: this is because by induction the output of the algorithm on G is multiway cuu and the output of the algorithm on G2 is multiway (I ke)-cut. Morcover,
17

---

A
B
+U1 0 A*
U1 unnB
U2 0
*U2 n Bx
Vn
V VnB
Figure 2: Node subsets of graph G. The subsets in asterisks have terminals them. Red edges indicate the left-hand side edges in Eq. (14) and purple edges indicate the edges the right-hand side Eq. (14)
E(A, B) E CALG. So the union of these cuts and E(A, B) is k-cut, and since each terminal is in exactly one partition, is multiway k-cut.
Now we prove the value guarantees. Let U1 = .... U V& and U2 = V441 U... UUV. Vg. So U U1 U Vi ....UV, V. is the set of nodes that in at least one partition. Recall that
V = V U is the set of nodes that are not in any partition.
that separates {S1, ,, from +I sp Let A' [U1 A] UU n B] U n A]. Let B' [U2 BJ U IU2 A n BJ. Since (A, B) is min
Consider the following
that separates {s1,-.., 8k3 from {,w+1,-.. S with additive error e(n). we have w [( B)) <
w ('A'' +((). Note that A = [U (uaaa)aaAAAVVVnVnn and = BBnnB)(UUnBBBU[VV So turning (A, B) into (4', B¹) equivalent switching U2 A and U1 B between A and B. So
we have that
w(E(22 DA,
w(E(U A, B)) wE(U OBU 0 A)) (EEU B, B,V A))
(14)
w E(U2 0 n n 4 + 1B
B, B))
+ e(n))
Eq. (14) is illustrated in
Figure
Using
Eq. (14) we obtain that
w/ (((E,,, B)) = =w((U,, 0 A, w (B(U, (
+w(E((U 0 B, + n B, V n 4))
+ (([() A) U (V A/, BJ))
S SuEE)SssAAA(innA))-(LLlAAAA nA))
+
+
+ e((n)
So we conclude that
wi E (EA,
BJU nl)
(15)
+wEE(U, (U(ECGnnAA(553BBBABm))))
+ (=(EUSnnAA((/4AA([[[A0))))
+WBBUnnB,Vnnd)
e(n)
We substitute w w(E(ABB) in Eq. (13) using Eq. (15). Recall that U1 UK Vo 88, (VnA)
n =
w(E(V, n A,A \ V.)) and VV(V.) w( EE V V.)). For any E {l,... k'}, we have that
18

---

E(V B, [U2 n B U B U n A) and E(V, n A, UU2 n B U V n B)) are both disjoint
from AVAAA, Moreover all these three terms appear EVV, V V,). So we have
w (B( n B, U2 n B
( (
w(B(U n A, U2 B B BJ)
Σ a.. (VinA)
(c(V))
Note that the first two terms above are the first two terms in Fq. (15) Similarly, we have
&
āa (Vin) S
da(Vi) (16)
k=
1441
Note that the first two terms above are the third and forth terms in Eq. (15)
Finally w (EVV n A)) =
w(E(V n B)) + w(E(V AAVnBB) s w(E(V). So, we upper-bound
Eq. (13) as
((CAl)) Σ do(V)) + w(E(V)
+ e(n) + 2 log (M' Al) + 2 log (k- ())
Since k' [1/2] and k- k'
[k/2]] we have that k N | and k k' s [+1 Moreover, [[||++|D] c([A|
since cn/e for and c 0, we have that e(AA)) + e (B) el
e(n). Therefore,
e(n) 2 log (K' ))((A)) 2og (k k))e((B))
1: 1
))
<e(n) + log
< 2 llog())e(m))
The above inequality finishes the approximation proof.
The success probability. As proved by Lemma 4.1] the min s-t cut computations by Algorithm can be seen as invocations of min s-ł cut algorithm on Ollog k) many n-node graphs; in this claim, we use to compute min s-t cuts. By union bound, each of those Ollog k) invocations output the desired additive error by probability at least 1 alog k).
19


Reviews:
[{"review_id": "e9BVCIa3Zv", "reviewer": "Reviewer_u9Zr", "summary": "This paper presents edge-DP algorithms for min s-t cut and multiway k-cut. The s-t cut algorithm injects fake edges with weights drawn from the exponential distribution, then returns the min s-t cut of the modified graph. The k-cut algorithm is based on $O(\\log k)$ calls to the min s-t cut algorithm. They showed that the s-t cut algorithm has $O(n/\\varepsilon)$ additive error, along with a lower bound of $n/20$ for $(\\varepsilon,\\delta)$-DP estimation of the problem, where $\\varepsilon \\le 1$.", "questions": "- The error in Lemma 3.3, I suspect it should be $O(n/\\varepsilon \\cdot \\log n)$? Since the sum of $n$ exponential random variables has gamma distribution with parameters $n$ and $\\varepsilon$. I am not sure how you arrived at the bound in line 224, since only an upper bound on the $E[c_i]$ is given.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is generally well-structured.\n- The DP s-t cut algorithm is surprisingly simple, and it's also the first work on this problem.\n- Lower bound is given.\n", "weaknesses": "- The proof of Lemma 4.1 does not match exactly the steps of Algorithm 2. The algorithm could be modified to fit the descriptions in the proof. In any case, I think Algorithm 2 as described, can also be made DP by expending only $O(\\log k \\cdot \\varepsilon)$ privacy, where on each level one can apply parallel composition, similar to what was done in [a].\n- There is no related work section? I think the greedy partitioning method for multiway cut [b] could be described here, since it is similar to your non-private multiway cut algorithm.\n- The experiments seem uninformative to me. Why compare the error of your s-t cut algorithm to error of a terminal cut? To me, an evaluation of the k-cut algorithm would be more useful, the setup could be: OPT vs. non-private approximation vs. DP algorithm.\n- a few minor typos.\n\n\n[a] Haim Kaplan et al. \"Differentially Private Approximate Quantiles\"\n\n[b] Liang Zhao et al. \"Greedy splitting algorithms for approximating multiway partition problems\"\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The proof of Lemma 4.1 does not match exactly the steps of Algorithm 2. ...\n\nWe agree with your comment that Lemma 4.1 does not match exactly the steps of Algorithm 2. Our intent is to represent Algorithm 2 in the simplest form, and Lemma 4.1 provides an alternative view on Algorithm 2, which we then leverage to prove DP. We agree with your comment on how DP guarantees can be proved, and our formal proof – please see Theorem 4.2 – is very similar to the argument you provided.\n\n> There is no related work section? I think the greedy partitioning method for multiway cut [b] could be described here, since it is similar to your non-private multiway cut algorithm.\n\nThank you for providing the references, we will mention the references you suggested. The greedy splitting technique is indeed one of the most widely known algorithms. However, there is a _significant_ difference between the greedy splitting and our approach.\nNamely, the usual greedy splitting has $k$-dependant splits, while ours has only $O(\\log k)$. That $k$ dependence also applies to algorithms GSA and M-GSA in the reference [b]. As a result, we get much stronger DP guarantees compared to the direct application of the folklore greedy splitting yields. As an additional feature, the running time of our algorithm depends only logarithmically in $k$, as opposed to linearly like the algorithms in [b].\n\nEven though Algorithm 2 is simple and intuitive (and similar results have been proved for other problems such as in [a]), our proof is more technically involved and quite different from that of [b].\nThe same problem described above exists for the 2-approximation algorithm outlined in lines 85-87 of our submission.\n\nWe agree that a separate related work section is beneficial to have all the related references in one place and we will make one for the final version of our paper. However, there is very limited work on differentially private min-cut and min s-t cut, and we mention most of the references in the introduction. In addition to the references provided, please let us know if adding any other references or looking into any other problems is beneficial.\n\n> The experiments seem uninformative to me. Why compare the error of your s-t cut algorithm to error of a terminal cut? To me, an evaluation of the k-cut algorithm would be more useful, the setup could be: OPT vs. non-private approximation vs. DP algorithm.\n\nThe terminal cut is the only differentially private benchmark we are aware of. Another potential benchmark is partitioning the vertices randomly without even considering edges. However, although it has perfect privacy, such a benchmark has an extremely high additive error of the order $0.5$ * # of edges. We provide the relative errors in the PDF in the Official Rebuttal, showing that the relative errors are very small.\n\nFor $k>2$, obtaining the optimum solution is NP-hard, so experimenting with that is more tricky. Moreover, we focused on experimentally evaluating Alg 1 because our Alg 2 achieves DP by using Alg 1 as a sub-routine. \n\n> The error in Lemma 3.3, I suspect it should be $O(n / \\epsilon \\cdot \\log n)$? ...\n\nWe still believe the right answer is $O(n / \\epsilon)$. Indeed, it is more involved to show that bound than $O(n \\log n / \\epsilon)$; the bound of $O(n \\log n / \\epsilon)$ is direct as each of the $n$ random variables has value $O(\\log n / \\epsilon)$ with high probability. Intuitively, for a sufficiently large constant $c$, one can still show a bound of $O(n / \\epsilon)$ because only _a small fraction_ of random variables exceeds $c/\\epsilon$; this fraction is roughly $e^{-c}$. We explicitly state this on Line 220 and in Fact 2.1, and then leverage it in our proofs. In the Official rebuttal for the entire submission, we comment more on that paragraph, including expanding on Line 224. We are happy to provide more details in that proof in the final version.\n"}, {"review_id": "D4vSFeY1DY", "reviewer": "Reviewer_PcBW", "summary": "The paper presents differentially private algorithms for the s-t mincut and multiway cut\nproblems under an edge privacy model with weights. It shows that a simple algorithm gives\nan O(n) additive error bound for the s-t mincut problem, and obtain a near tight lower bound.\nThis is used for obtaining a bound for the k-multiway cut problem, which has an additional\nO(\\log{k}) term, which improves over the O(k) term that would result by applying the\ns-t cut algorithm repeatedly. The s-t mincut algorithm is evaluated empirically, and the\nresults are compared with a simple baseline.", "questions": "The edge privacy model assumes the weight of an edge changes by at most 1 in neighboring graphs\n(definition 2.3). Suppose this is allowed to be w, do the upper and lower bounds scale accordingly?\n\nAre better accuracy bounds possible when the graphs have some special properties?\n\n\nline 160: the first sentence (\"Let G and G' be two neighboring graphs\") doesn't need to be part\nof the Lemma statement\n\nIt would be interesting to show the relative error of the solution computed by Algorithm 1,\ni.e., compare the error of Algorithm 1 with the actual s-t mincut. This could be done for the baseline\nas well. Without that it is hard to really understand how well the algorithms are doing.", "limitations": "To some extent. There are no negative social impacts", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Differentially private algorithms for the s-t mincut problem have been open for a long time, since\nthe global mincut algorithm of Gupta et al. The paper gives tight upper and lower bounds on the\ncomplexity of this problem, and shows that a very simple algorithm gives these bounds. For the\nk-multiway cut problem, the paper shows that a slightly simple modification of the standard\nnon-private approximation algorithm can be adapted to have an error with O(log k) dependence,\ninstead of O(k) dependence. The presentation is good.", "weaknesses": "The main ideas in the paper are quite simple. The experiments section is also somewhat limited.\nWhile the presentation is generally good, there is not enough discussion about the related work.\nSo it is not clear if the technical contributions and the paper overall meet the bar for neurips.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The main ideas in the paper are quite simple. ...\n\nWe agree that a separate related work section is beneficial to have all the related references in one place, and we will make one for the final version of our paper. However, there is very limited work on differentially private min-cut and min s-t cut, and we mention most of the references in the introduction. The relevant problems to min s-t cut could be the clustering problems referenced on line 34. However, the techniques for clustering problems are very different from cut problems. \n\nThe min-cut problem has a differentially private algorithm that was developed back in 2010 [17] with tight error bound $O(\\log(n)/\\epsilon)$. \n\nFor the multiway-cut problem, we discuss the best approximation algorithms and lower bounds for it in lines 80-83. Several simple algorithms achieve approximation bounds near 2; we mention one of them on lines 85-87. There is also a folklore greedy splitting algorithm (Liang Zhao et al. \"Greedy splitting algorithms for approximating multiway partition problems\") that starts with the whole graph as one partition and at each step greedily cuts one of the partitions, hence after k-1 rounds achieved k partitions. The problem with all of these algorithms is that they require k rounds of min s-t cut, and hence using an $\\epsilon$-private algorithm for min s-t cut in these algorithms would yield a $k\\epsilon$-private 2-approximation algorithm for multiway cut. We show that using Algorithm 2, one can decrease this dependency on $k$ to $\\log(k)$.\n\nWe believe this captures all the related work to our problem. Please let us know if adding any other references or looking into any other problems is beneficial. \n\n\n> The edge privacy model assumes the weight of an edge changes by at most 1 in neighboring graphs (definition 2.3). Suppose this is allowed to be w, do the upper and lower bounds scale accordingly?\n\nThis is a great question. Yes, it does generalize to any $w$. Our proof of Lemmas 3.1 and 3.2 is actually already proved for a general weight difference; we use $\\tau$ instead of $w$ to define this difference. Those proofs show that our Alg 1 is $(\\epsilon \\cdot w, 0)$ DP. As a consequence and by rescaling the input $\\epsilon$ by $w$, our Alg 1 is $(\\epsilon, 0)$ DP and incurs an additive approximation of $O(n \\cdot w / \\epsilon)$. We are happy to include these comments in the final version.\n\n> Are better accuracy bounds possible when the graphs have some special properties?\n\nThis is an interesting question for future research. We are happy to include it in our conclusions. It is worth noting that our lower-bound graph has the min s-t cut equal to 0.\n\n> line 160: the first sentence (\"Let G and G' be two neighboring graphs\") doesn't need to be part of the Lemma statement\n\nYou are right. We will fix this.\n\n> It would be interesting to show the relative error of the solution computed by Algorithm 1, i.e., compare the error of Algorithm 1 with the actual s-t mincut. This could be done for the baseline as well. Without that it is hard to really understand how well the algorithms are doing.\n\nYou are right. In the Official rebuttal (please see the attached PDF there) we provided the relative errors. The errors are quite low for both algorithms, though our approach still has lower relative errors.\n"}, {"review_id": "mQwdMTEduV", "reviewer": "Reviewer_pWxc", "summary": "The authors give a novel and simple diferentially private algorithm for the min $s$-$t$ cut and multiway $k$-cut problems.", "questions": "What are some computational complexity implications of your work?\n\nLine 39:\nCan you please sketch an example where there are exponentially many min $s$-$t$ cuts but only polynomially many min cuts?\n\nThe discussion after Theorem 1.2 (Line 60 to Line 74) is a bit confusing.\n\nLine 65:\nTheorem 1.1 should be Theorem 1.2.\n\nLine 89:\nCan you elaborate a bit on advanced composition?\n\nLine 161:\nProof of Lemma 3.2:\nCan you please add an explanatory figure for the discussion from Line 161 to Line 173?\n\nLine 191:\nI do not understand this math display.\n\nSection 4.1 is amazing!\n\nLine 227:\nCan you please explain this math display a bit better?\n\nExperiments look OK!", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality:\nWork seems original.\nSimple but novel!\n\nQuality:\nQuality of the paper is high.\nThe authors give interesting upper and lower bounds for the min $s$-$t$ cut and multiway $k$-cut problems.\n\nClarity:\nWriting is clear.\n\nSignificance:\nThe result is significant, as min $s$-$t$ cut and multiway $k$-cut are important problems.", "weaknesses": "None significant weakness found.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> What are some computational complexity implications of your work?\n\nThank you for this great question. There are several implications. *First*, our Alg 1 uses a non-private min $s$-$t$ cut algorithm in a black-box manner. Hence, it essentially translates to any popular computation setting without asymptotically increasing complexities compared to non-private algorithms. *Second*, our Alg 2 creates (recursive) graph partitions such that each vertex (and edge) appears in $O(\\log k)$ partitions. To see how it differs from other methods, observe that the standard splitting algorithm performs $k-1$ splits, where some vertices appear in each of the split computations. There are also LP-based algorithms for the multiway $k$-cut problem, but to the best of our knowledge, they are less efficient than the $2$-approximate greedy splitting approach. *Third*, in the centralized and parallel settings such as PRAM, in terms of total work, Alg 2 depends only logarithmically on $k$ while the popular greedy splitting algorithm has linear dependence. This question was thoroughly investigated by groups of authors, e.g., see “Faster Parallel Multiterminal Cuts” by Henzinger, Noe, and Schulz, and references therein. To the best of our knowledge, no existing method matches these guarantees that Alg 2 provides.\nWe didn’t expand on this in our submission and kept the focus on the DP guarantees of our Alg 2, but we are happy to discuss the complexity implications in more detail in the final version.\n\n\n> Line 39: Can you please sketch an example where there are exponentially many min s-t cuts but only polynomially many min cuts?\n\nTake $n-2$ nodes $v_1,...,v_{n-2}$ in addition to $s$ and $t$, and add $v_i$ to both $s$ and $t$ for all $i$. Suppose the weight of all edges is $1$. There are $2^{n-2}$ min $s$-$t$ cuts, as each min s-t cut should remove exactly one edge from each $s-v_i-t$ path; either $(s, v_i)$ or $(v_i, t)$ is fine. \nIn this example, there are $n-2$ min cuts: for each $i$, remove edges $(v_i,s)$ and $(v_i,t)$ and this would be a cut of size 2. Moreover, one can show that the number of min-cuts is polynomial for any graph, there are at most ${n \\choose 2}$; please see “On the structure of a family of minimum weighted cuts in a graph” by Dinitz et al.\n\n> The discussion after Theorem 1.2 (Line 60 to Line 74) is a bit confusing.\n\nWe will polish this paragraph.\n\n> Line 65: Theorem 1.1 should be Theorem 1.2.\n\nIt is true, and we will fix that.\n\n> Line 89: Can you elaborate a bit on advanced composition?\n\nWe remark that we do not use the advanced decomposition theorem. We only mention that, even if applied to the standard greedy approach for multiway cut, it does not yield the guarantees that Alg 2 has. To be more precise, the folklore greedy splitting multiway $k$-cut algorithm yields $(k \\epsilon, 0)$-DP via direct composition. The advanced decomposition, see [1], improves that to $(\\sqrt{k} \\epsilon, \\delta)$-DP, for some $\\delta > 0$. Note that the advanced decomposition yields to approximate DP instead of a pure one in which $\\delta = 0$.\n[1] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. “Boosting and differential privacy”\n\n> Line 161: Proof of Lemma 3.2: Can you please add an explanatory figure for the discussion from Line 161 to Line 173?\n\nYes, we are happy to improve that discussion.\n\n> Line 191: I do not understand this math display.\n\nHere is a complete derivation\n $\\Pr[w_{G’}(C_u) < w_{G’}(C_v)\\ \\wedge\\ w_{G’}(C_u) < w_{G’}(C_{u,v})\\ \\wedge\\ w_{G’}(C_u) < w_{G’}(C_{\\emptyset})] =$\n$\\Pr[\\Delta_v + X_{s,v} + X_{t,u} < X_{t, v} + X_{s, u}\\ \\wedge\\ \\Delta_{u, v} + X_{s, v} + X_{t, u} < X_{t, v} + X_{t, u}\\ \\wedge\\ \\Delta_{\\emptyset} + X_{s, v} + X_{t, u} < X_{s, v} + X_{s, u}] =$\n$ \\Pr[\\Delta_v + X_{s,v} + X_{t,u} < X_{t, v} + X_{s, u} \\ \\wedge\\ \\Delta_{u, v} + X_{s, v}  < X_{t, v} \\ \\wedge\\ \\Delta_{\\emptyset} + X_{t, u} < X_{s, u}].$\nNow, we replace $X_{s,v} - X_{t,v}$ by $x$ and $X_{t,u} - X_{s,u}$ by $y$, which leads to the math on Line 191.\nWe will include this derivation in the full version.\n\n> Line 227: Can you please explain this math display a bit better?\n\nWe provided additional explanations within the Official Rebuttal section. Please check there.\n"}]

Author rebuttal:
We thank all the reviewers for their constructive comments.

Two of the reviewers asked for clarification of the analysis in Lemma 3.3, so in addition to our comments below, we provide more explanations that we will include in the final version.

For intuition and brevity, assume that $\epsilon = 1$. Observe that showing that Alg 1 has $O(n \log n)$ additive error is straightforward as a random variable drawn from $Exp(b)$ is upper-bounded by $O(\log n / b)$ whp. Our Lemma 3.3 proves the $O(n)$ bound. It is instructive to think of the interval $[2, 5 \log n]$ being partitioned into buckets of the form $[2^i, 2^{i+1})$. Then, the value of each edge added by Alg 1 falls into one of the buckets; we can safely assume that no edge $X_{s, u}$ or $X_{t, u}$ has a weight more than $5 \log n$. Now the task becomes upper-bounding the number $c_i$ of edges in bucket $i$. That is, we let $Y_{s, u}^i = 1$ iff $X_{s, u} \in [2^i, 2^{i+1})$, which results in $c_i = \sum_{u \in V}(Y_{s, u}^i + Y_{t, u}^i)$. Hence, $c_i$ is a sum of 0/1 independent random variables, and we can use Chernoff bound to argue about its concentration.
There are two cases. If $E[c_i]$ is more than $O(\log n)$, then $c_i \in O(E[c_i])$ by the Chernoff bound. If $E[c_i] \in o(\log n)$, e.g., $E[c_i] = O(1)$, we can not say that with high probability $c_i \in O(E[c_i])$. Nevertheless, we can still say $c_i \in O(\log n)$ whp. This is why there is $\max$ including $\log n$ in it.
Finally, Line 227 simply sums the weights of $X$ random variables over all the buckets, $\log (5 \log n)$ of them, where if a random variable $X$ falls into bucket $i$ we upper-bound its weight by $2^{i + 1}$, although it can be smaller by a factor of $2$. Also, to obtain the first inequality on Line 227, we use that $\max(\log n, 2n / 2^{2i}) \le \log n + 2n / 2^{2i}$.

In regards to the experiments, we attached a figure containing relative errors as requested by some of the reviewers. This figure shows that the relative errors are very small. Note that the errors are computed with respect to the optimal $s$-$t$-cut which is not private.

Meta-review: The paper presents new differentially private algorithms for s-t mincut and multiway cut problems. The problem is interesting and the techniques are novel. The reviewers were in agreement that the paper is above bar and I am happy to recommend acceptance. The authors are encouraged to incorporate reviewer feedback, and relevant portions of the rebuttal in the final version of the paper. It would be great also if they could further elaborate on the relevance of their solutions to various ML problems.
Decision: Accept (oral)