Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Authors: Anders Aamand
Justin Y. Chen
Mina Dalirrooyfard
Slobodan Mitrović
Yuriy Nevmyvaka
Sandeep Silwal
Yinzhan Xu
Venue: ICML 2025 poster (2025)
Keywords: Differential privacy
graph sparsification
graph cuts
Primary area: social_aspects->privacy
TL;DR: Differentially private graph sparsification

Abstract: We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1.5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC'12]. In contrast, \emph{inefficient} algorithms, i.e., those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eliáš,  Kapralov, Kulkarni, Lee SODA'20]. In this work, we break the $n^{1.5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon,\delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1.25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

Breaking the n n. Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Anders Aamand" 1
Justin Chen 22 Mina Dalirrooyfard *3 Slobodan Mitrović" '4 Yuriy Nevmyvaka
Sandeep Silwal Yinzhan Xu"
Abstract
1. Introduction
Many modern applications rely on personal data, with no- table examples including social networks and medical data analysis. However, traditional algorithms, developed over decades, are inherently non-private and often sensitive to even small changes in input. This sensitivity can lead to significant privacy breaches (Backstrom et al., 2007; Narayanan & Shmatikov, 2008; Culnane et al., 2019). These privacy concerns have driven extensive research on algo- rithms that protect users' privacy. Graphs, which are ubiqui- tous in machine learning and data processing. have received significant attention in preneeriig settings. Our work contributes to this growing body of research by design- ing private algorithms in the context of graph cuts. In social networks, cut queries are crucial in analyzing how tightly community is connected internally and how it interacts with the outside world. However, accurately releasing connec- tivity information can compromise user privacy (Hay et al., 2009). Moreover, there are exponentially many cuts, mak- ing direct private release of all the cuts infeasible. Hence, one way solve this problem is to construet synthetic graph the same node set as the original while preserving approximate cut values.
We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers n-node graphs approximate each cut within (55 additive error and 1 +7 multiplicative er- ror for any y > 0 [Gupta, Roth, Ullman TCC' 12]. In contrast, inefficient algorithms,, i.c., those re- quiring exponential time, can achieve an (n) ad- ditive error and + multiplicative error [Eliáš, Kapralov, Kulkarni, Lee SODA'20J. In this work. we break the n additive error barrier for private and efficient cut sparsification. We present an (s, 5)-DP polynomial time algorithm that, given non-negative weighted graph, outputs private synthetic graph approximating all cuts with multi- plicative error + y and additive error n² 25+o(1) (ignoring dependencies on E, 5, 7).
At the heart of our approach lies a private algo- rithm for expander decomposition, a popular and powerful technique in (non-pri (non-private) graph algo- rithms.
The standard notion of privacy differential privacy (DP) introduced by Dwork, McSherry, Nissim, and Smith in their seminal work (Dwork et al., 2006), which indicates that the output of private algorithm of two neighbor- ing inputs must be statistically indistinguishable For- mally, an algorithm A is (c, ()-P) if given two neighbor- ing inputs G and G' and subset of outputs O, we have Pr(A(G) E O) < e Pr(A(G") E O) + When = 0, we say that the algorithm preserves pure-DP, and otherwise approximate-Di In the context of graphs, the most widely studied notion of neighboring graphs is edges-neighboring: two neighboring graphs differ in only one edge, and the graphs' node sets are publicly available. For weighted graphs, two neighboring graphs are those whose total edge weights differ by at most one, and in single edge'.
Equul contribution UUniversity of Copenhagen, BARC, Denmark. aa@di.ku. dk. "Massachusetts
Institute of Technology. Cambridge, MA. USA. just::mit.eddu *Machnne Leamiing Research, Mor- gan Stanley, Canada. minadêmit Califomia, Davis, USA. smitroviceucdavis edu. 'Machine Learning Research, Morgan Stanley, USA. puriy.nevmyvae waapvakaemorganttnller..
"University of
"UW-
Madison, USA. silwalêcs. www.. UUiiversity of Califomia, San Diego, USA. Correspondence Mina Dalimrooyfard <minad@mit.cdu>..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Algorithms satisfying this notion are often also private for graphs whose vector of (2) edge weights differ by at most 1 in & distance.

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Given non-negative weighted, undirected graph G (V; E. w), we consider the problem of releasing non- negative weighted, undirected synthetic graph G on the same node set V which (a) is differentially private and (b) approximately preserves values of all the cuts in G. A cut is formed by a subset S C V where S A 0. and the value of the cut wg (S) is the weight of the edges between S and V \ S. Prior works (Gupta et al., 2012; Eliáš et al., 2020; Liu et al., 2024) have settled the complexity of this problem when no multiplicattive error is allowed. In par- ticular, Gupta, Roth, and Ullman showed how to release synthetic graph in pure-DP manner and with ((n!.s) additive error of each cut value. When the number of edges of the input graph is upper-bounded by m, the additive er- ror can be improved to ((mmn) (Eliáš et al., 2020; Liu et al., 2024) for approximate-DD DP algorithms.? 2 Thus, despite a long line of work, the additive error of this problem has been stuck at (n5. for dense graphs, the same error that the simple algorithm of just adding Laplace noise to all pos- sible edges achieves (although this would result in a graph with negative edges, whereas the aforementioned works re- lease a non-negative weight graph). The fundamental reason
substantial progress toward resolving this open problem.
Theorem 1.1. Let E (0. 1). There is polynomial time (e, DDP algorithm, which on any non-negative weighted n- node graph G = (V, E, w) outputs non-negatie weighted sparse graph H with O(n/7²) edges such that with high probability:
CSCV |urc(S) wH (
S Sywa(S) + n 2225 polylog(1/))
e-.0.5
We remark that prior work listed in Table 1 (except the first one which adds Laplace noise to every edge) can also output sparse graph by simply running a non-private sparsifier in post-processing. Then the prior results in Table also incur the same multiplicative approximation as Theorem 1.1 (but retain their additive error). Thus, the best prior work on sparse cut-sparsifiers with (mn/7²2 edges has mul- tiplicative approximation 1 1+7 and additive error ((r2.//e) (Gupta et al., 2012), even allowing approximate DP.
A key technical ingredient for proving Theorem 1.1 is pri- vate expander decomposition, which may be of independent interest; see more details in Section 4. The formal proof of Theorem 1.1 can be found in Section 3. We show that Theorem 1.1 has important downstream applications in Sec- tion and Appendix B, where we obtain DP algorithms for max-cut, iixiimum-bisection max-k-cut, and minimum- bisection, with optimal multiplicative and improved addi- tive error in the DP setting. We conclude in Section 6 with several open questions that we find exciting and interesting to pursue.
for this is that (2n!..)) 1-5) additive error is necessary even for approximate-DP (Eliáš et al., 2020; Liu et al., 2024).
The synthetic graph that achieves the O(n2-5) bound a dense graph. However, in many applications, storing only sparse graph is desirable due to communication memory requirements. Indeed, this is the original motivation for the extensive algorithmic work on graph sparsification (going back to (Karger, 1 1994) more than three decades ago). This requirement is also crucial in many other sub-fields, such as the semm-streaming graph model (Feigenbaum et al., 2005). For sparse synthetic graphs, it is unavoidable to also have a multiplicative error in addition to the additive error (even non-private graph sparsification has the multiplicative error). However, the 2(2225) lower bound does not apply when a multiplicative error is allowed. In fact, using the exponential mechanism, is known how to achieve multiplicative error 1 + y and additive error (n log n²) (Eliáš et al.. 2020), which is known to be near-optimal (Dalirrooyfard et al., 2023). One caveat, though, is that this algorithm takes exponential time, and the best polynomial time algorithm still has ( additive error. Closing this gap between Onn!55) and (n) additive error, while allowing for + y multiplicative approximation, is considered "a prominent open problem in the differential privacy literature" (Eliás et al., 2020).
1.1. Related Work
Here, we mention some relevant problems to our work. There has been a lot of work on releasing synthesized graphs in a DP manner with objectives other than cut queries, such as maintaining the degree sequence or subgraph counting (see the survey (Li et al., 2023)). Depending on the objective, different techniques are used. There have been studies on DP algorithms for other cut problems such as min cut (Gupta et al., 2010), min-s/-cut (Dalirrooyfard et al., 2023), all pairs min-st-cut (Aamand et al., 2024) and multiway cut (Dalirrooyfard et al., 2023; Chandra et al., 2024), where the error guarantees for all these problems are optimal. Note that the output size in these problems is polynomial, so there is no need output synthetic graph, and the techniques are not directly applicable to our problem.
In this work, we provide the first polynomial time algorithm that beats the O(n! 1.5 additive error barrier, thus making
1.2. Technical Contribution
Throughout this paper, Ō,e,C Z hide polylog(n/8) factors for approximate-DD DP problems, and polylog(n) factors for other problems.
Our main technical contribution is an algorithm which, given an input graph G (V, E, w), in differentially private manner outputs a synthetic graph G such that for any
2

---

Breaking the n Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Reference
DP
Multiplicative Error
Additive Error
Runtime
Laplace Noise*
Pure
O(n /t)
Polynomial
(Gupta et al., 2012)
Pure
O(n' (2/19/8)
Polynomial
(Arora & Upadhyay, 2019)
Approx
1+a
Polynomial
(Eliá al., 2020; Liu et al., 2024)
Approx
Ō(vmn//)
Polynomial
(Eliáš et al., 2020)
Pure
1
Onllogn/8
Exponential
Theorem 1.1 (Our Work)
Approx
1+a
n n1255401)/
Polynomial
Table 1. A comparison of approaches for differentially private eut-approxination that release synthetic graphs. Dependencies the approximate DP parameter 5 are hidden, but the dependency is only polylog(1/O) in all cases. We also omit the dependency on the multiplicative approximation parameter a. (Arora & Upadhyay, 2019) obtain bound of ÖV (S/e) to approximate a (S, V. \ S) cut, which can ( for large [S]. We note that (2 additive error necessary even for approximate- (Eliáš et al., 2020; Liu et al., 2024) if no multiplicative error is allowed.
*The first result naively adding Laplace noise does not produce a non-negative graph, which the other results ensure.
S (wea(C) + n 1125++(() for any desired small constant = 2(1). To obtain a sparse graph approximating all cuts with similar approximation guarantee, we then run any graph sparsifica- tion algorithm on G, e.g., the classic algorithm by Benezúr and Karger (1996), and by post-processing properties of differential privacy, the resulting graph is still private.
cut (C, V. \ C)) we have
-
Our approach. Our approach is illustrated in Figure 1. The main observation behind our algorithm is the follow- ing: If for all cuts (C,V V C) the cut weight (C((C) is D(CC)/7/a) then the Ö(ClV)) additive error achieved by Approach 2 is only an a fraction of wc(C). Phrasing it differently, the synthetic graph output by Approach 2 al- ready achieves (1 + muultiipllicative approximation for all the cuts.
To describe our construction of G we first outline two other approaches for private graph cut approximation. For the sake of simplicity, throughout this overview, we assume the parameters e, 6, a are all constants.
Unfortunately, not all graphs satisfy the property described above, i.e., WC(C) E M(CCVnnaa). Nevertheless, that observation raises the following question: Can we process an input graph G so that the resulting graph, or conveniently chosen subgraphs of G, exhibit that desired property? Our approach answers this question affirmatively and shows how to leverage it to obtain the advertised upper bound on the additive error. We now provide more details.
Approach 1: Additive error of Ö(Vmm). For approxi- mating all cuts in DP-manner with purely additive error guarantees Eliáš, Kapralov, Kulkarni, and Lee (2020) pro- vide an (e, 8DP algorithm with an additive approximation of (VVWW) for graphs with total edge weights bounded by W. Liu, Upadhyay, and Zou (2024) provide an improved algorithm with approximation Ō O(ynm). In the case where the number of edges m is small, these algorithms already achieve an improvement over additive error (5).
Graph expanders. Graphs satisfying the above property coincide with the notion of expander graphs. To elaborate, for a cut (C, V \ C) of the graph, we define its sparsity as
(C))
x(C) = IVIICCIIICCIII
The sparsity of the graph is then defined as ((G) minagoçu (CC). If (G)) > vi call G re-expander. The property considered in the previous paragraph can be phrased as ((G) 2 Ó(vn/a).
Approach 2: Additive error of Ö(IC) vn). Another way of privatizing G is to add Laplace noise Lap(1/=) to the weight of each edge of G. This algorithm is trivially private, and by standard concentration bounds and union bounding over all cuts of size s, one can see that these cut values are preserved within additive error (ss)n) In fact, Upadhyay, Upadhyay, and Arora (2021) provide an approximate DP algorithm with essentially the same approximation guar- antee and with the additional property that the synthetic graph they output has non negaatvveeee edge weights. For cuts C' where = CC| = o(n), these algorithms again improve over the additive error of 55...))
Expander decomposition is a popular and powerful algorith- mic tool that has been studied by numerous groups, e.g., (Nanongkai & Saranurak, 2017: Wulff-Nilsen, 2017: Sara- nurak & Wang, 2019; Chuzhoy et al., 2020: Li & Saranurak, 2021). For any parameter & > 0, it is known how de- compose the vertices V of an arbitrary weighted graph into
There are several notions of expanders, including edge, vertex, and spectral expanders. We use a certain version of edge expanders.
3

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
that the induced subgraph G[V] for every V is dh-expander, and the sum of weights of the edges that are not within any V; is (mrz)), Suppose we can privately obtain such decomposition for (Vvaaa). Then, the sum of weights of the inter-component edges that refer to by Exparse would be (//t.//a),, We apply Approach to Espars to obtain synthetic graph that preserves each cut with an additive error of O( n) O(1 /Va). For the edges within each G[V,], we apply Approach 2 to obtain private graph sparsifier that preserves each cut in G[V]] with (1 + at) multipliiicatee approximation.
... Vk, Vi....,
c[Ki]
G[V]]
E Esparse
(C, V/3 |C) has sparsity 2 1/ in G[Va]
G[V3]
C
Private expander decomposition. Unfortunately, to the best of our knowledge, private expander dccomposition has not been studied the literature.
Figure I. For d n 0.55+(()) our algorithm privately obtains a partition of the vertices of G into sets Vi,... V12 such that (1) each induced subgraph G[Vi] (red) has sparsity at least d and (2) the total weight of edges between components (blue) is "n +o(1), We run the O(ynm) /nm) additive error algorithm by (Eliáš et al., 2020) on Espane formed by the blue edges, and the algorithm by (Upadhyay et al., 2021) on cach G[V.). The high density of G[Vi] ensures that the multiplicative approximation can subsume the error of the latter algorithm.
One natural approach is execute a non-private expander decomposition algorithm e.g., G' obtained by Approach 2. However, this straightfor- ward approach has a major issue: Let (S, T) be the sum of the weights of edges between S and T for any S,T C V(G), = If G[V]] is a ((y'))-expndde it does not immediately imply that G[V] is ((V In order to achieve so, one would need to lower-bound J [C, V; C)- (C Vi C by @(vn), which the algorithm in Approach 2 does not achieve; it achieves this bound for = V,+*
private synthetic graph G,
When it is clear from the context, we omit the subscript G. Theorem 2.2 ((Upadhyay et al., 2021)). Given a non- negative weighted n-node graph G (V, F), there is polynomial time (e,5)-DP algoritium which outputs non- negative weighted graph G on the same vertex set V. such that with probability 1 for any S SV..
Hence, instead of applying non-private expander decom- position algorithms in a black-box way, privatize existing expander decomposition algorithm in white-box manner. On high level, our approach follows the work by (Nanongkai & Saranurak, 2017). To support weighted graphs, we replace one of the key subroutines in (Nanongkai Saranurak, 2017) with a result from (Li & Saranurak, 2021). As the outcome, we obtain a private expander de- composition algorithm that, for de 2 0,.++(1)), decomposes graph into dl-expanders with the total weights of inter- component edges upper-bounded by (o0(), Our private expander decomposition might be of independent interest.
[|] b) n log n log(
(Wc(S) wwy(s) so
To be more precise, we use the synthetic graph G described in their Algorithm 8, and the guarantee on the cut values is implied by their Equation (9). In their paper, they only formally state the results for the case where À is constant, but they can be easily extended to arbitrarily small À by incurring cost of ((log(//)) (see their discussion after Theorem 15).
2. Preliminaries
Theorem 2.3 ((Eliá et al., 2020)). Given a non-negative weighted n-node graph G = (V, E, w). there is a poly- nomial time (e, 8DD algorithm for 0 E < 1/2 and 0 << 1/2, which outputs a non-negative weighted graph G on the same vertex set V, such that with high probability, for every S SV.
Definition 2.1 (Cut crossing edges). Let G (V, E) be weighted graph and S V a subset of vertices. We use WS(S) to denote the total weights of edges with one endpoint in S and the other endpoint in V S. That is,
wG(S)=
Σ
w(u,v).
(w((S) - (g(
(N.VEEE:ESSWEEVS
*Such bounds are achievable if we allow negative weights in G (Upadhyay et al., 2021), but then we will not be able to run non-private expander decompasition algorithms G because they only work for graphs with non-negative edge weights.
w W(''n log log²
(n log
00
where w/ (F) denotes the sum of all edge weights.

---

Breaking the n' Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
The original statement in (Eliá' et al., 2020) does not pro- vide high probability guarantee, so we provide a proof in Appendix A for the above version.
Algorithm Differentially Private algorithm for preserving
all cuts in a graph
1: Input: An n-node graph G = (V, E, w); DP parame-
ters e,
Differential Privacy Tools. We now list basic definitions and tools we use in the context of differential privacy.
Compute V1, V2...., ., V by invoking Theorem 3.1 on G with parameters e/3, 8/3, and ab = (n)naa/a
Definition 2.4
Graphs), Graphs G= (V, E, w) and G' = (V, E", w') are called edge-neighboring if there is (u, 2) E V2 such that [w(u, v) w w'(u, v)1 S and for all {u', (u',e' * v), u',v' E V2, we have ww'' e²) w''',,"' 2²). Non-edges are considered to have zero weight.
polylog(n/8)) n 02.5++(11)
3: Let Expanse be the edges of E that are not within any V, Let Goparse be obtained by applying Theorem 2.3 with parameter (e/3, 5/3) Gaparse = (V, Esparse; w).
5: Let G. be obtained by applying Theorem 2.2 on G[V] with privacy parameter (e/3, 6/3) and X 1/n2".
Definition 2.5 (Differential Privacy (Dwork, 2006)), A ran- domized algorithm A is (c, 5)DP if for any neighboring graphs G and G" and any set of possible outcomes O of A it holds Pr (A(G) E O) < e Pr (A(G") E O) + 5.
6: return G whose edge weights are the corresponding edge weights from Gspars and {
When d = 0, algorithm A is called pure DP, or only E-DP. Theorem 2.6 (Basic composition (Dwork et al., 2006; Dwork & Lei, 2009)). Consider algorithm A running (possibly adaptive) algorithms. If the i-th algorithmm is (ei; 6:)- for ei, 6, 2 0, then A is (2 E,, D..
3.1. Privacy Guarantee
The only places where Algorithm uses edge weights are via Theorem 3.1, Theorem 2.3 and Theorem 2.2. Let the edge difference between two inputs be on e = {u, w). Note that there only one invocation of Theorem 3.1 and one in- vocation of Theorem 2.3. To see the impact of Theorem 2.2 privacy, consider the partitioning Vi...., V2 of Theo- rem 3.1, which we assume is the same in both neighboring graphs. If e is between two partitions, then the subgraph on each Vú in both neighboring graphs is the same and the invocations of Theorem 2.2 yield the same output without losing any privacy. e in some partition Vi, then only one invocation of Theorem 2.2 uses the privacy budget. Hence in total, at most three invocations of Theorem 3.1, Theo- rem 2.3 and Theorem 2.2 use privacy budget, and since each of these invocations is (e/3, 8/3)-DP, overall the algorithm is (s, DDP by basic composition.
3. Private Cut Sparsifier
In this section, we use our DP expander decomposition result stated in Theorem 3.1 (which we prove in Section 4) to describe our algorithm for private cut approximation.
Theorem 3.1. Let0 < e, 1/2 be parameters. For Forany any n,, there exists a parameter (n) = n (0.5+0(11) (0.5+t00..poyloo(111 -polyoo((188) (88)// so that given an n-node non-negative weighted graph G = (V, E, w) and a parameter v > (n), there exists a polynomial time (s, DDD algorithm that oulputs par- tition of V = V1 ....U Vs, such that with probability 1 1-0(1/)))
For every 1 Si S k, the sparsity of G[Vi) is at least vb.
3.2. Success Probability
. The total weights of inter-component edges is vē - nz+o(1),
Several favorable events must occur so our algorithm yields the desired error bounds. First, we need the invocation of Theorem 3.1 and Theorem 2.3 to succeed. By union bound, these happen with high probability. Second, we need all invocations to Theorem 2.2 to succeed. Since there are at most O(n) invocations, by union bound, the probability that any one of the invocations fails is O(n)) = O(1nn").
Thus we get the following theorem.
Theorem 3.2. Let O < E, < 1/2,0 < < 1 be pa- rameters. Given any non-negative weighted n-node graph G -V, E, w). there is an (e, 8DDP algorithm running in polynomial time that outputs a synthetic graph G on the same vertex set V with non-negative edge weights, so that with high probability, for every C CVV,
By union bound, the probability that none of these failure events occur is 1 - 1/ poly(n). In the rest of our analysis. we condition on the good events occurring.
(1 (C) A < wa(C) S (1+ (L)+)w((C)+ +A,
for some
3.3. Additive Error Upper Bound
n (())) polylog A
20.3.g
(1)
Here, we analyze the additive error of Algorithm 1. Let C C V be an arbitrary subset. We aim to prove an upper bound B on the additive error while allowing a (1 + a)-
Proof. The algorithm is described in Algorithm 1.
5

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
factor multiplicative error. That is, we want show
Putting everything together. By combining all the cases, i.e., Equations (2) and (3), the final upper-bound on the additive error can be written n 2.2000(()) ppolylog 1 This o
(1 ---a) (--awaa(C) BB S wa(C) S (1 + (C) + B.
concludes the proof.
Hence, it suffices to show the following: (ug(C)-wa(C) - a we(C) I B. To derive an upper bound on (w)(C)) - wa(C)] - a (C)( define
C. def C V, for 1 S I k, where Vi is obtained by Theorem 3.1. Then,
We are now ready to prove Theorem 1.1. The difference between Theorem 3.2 and Theorem 1.1 that the latter out- puts sparse graph with a near linear number of edges. The proof of Theorem 1.1 follows directly from Theorem 3.2: we obtain a synthetic private graph G. Then, we run a vanilla non-private cut-sparsification algorithm (which is private via post-processing), such as (Benczúr & Karger, 1996), on G, giving us a spare synthetic graph. Given a non- non-negative weighted graph and a parameter y, the algo- rithm from (Benczúr & Karger, 1996) outputs sparse graph with (n/7>² edges in polynomial time where all cuts approximated with (1 + muultippiicative factor.
wg((C) - wwa(C) a wa(C)
" (C) WGGunnn (c)) a WGG (C))
(w,,(C.)) (Ct) wG. (Ci) a wG: (C:))
We now analyze each of the two terms separately.
Additive error of Sparss.
Since
Proof of Theorem 1.1. Let > = 7/100. We run Theo- rem 3.2 to compute a synthetic graph G with = >2, and then run (Benczúr & Karger, 1996)'s 's algorithm with parame- ter 7' on G to find H. Let A additive error guaranteed by Theorem 3.2. By the guarantee of (Benczúr & Karger, 1996), the number of edges of H is ((nn72), and for any S C V, we have (wG(S) - wH (S)l
(C) - WGnne (C) ar W. (C)
W6 Gapane
G (C') WW WGyoe (C)
n. 2..25 polylog(1/á) be the 550
focus upper-bounding the latter term.
By Theorem 3.1. the total edge weights of edges cross- ing two diffrent Vú and Vi, w ((ssaase), are 1b n [+[(1] = n (l1++(()) polylog(1/8)/(es)
$ (wc(S) - wz(S)] + -
Therefore, by Theorem 2.3, we conclude that
I ()) +1'
+
+
W (C) - youe (07) 2ō(
wv( (sspaasee n
I (s) + A) + (1'-(11 ((++))-wa(S)) + A))
S 7 + +OA).
n1 1:23-(((1) polylog
(2)
00.5.
4. Private Expander Decomposition
In this section we describe how to design a private expander decomposition algorithm. To that end, we first state a result that directly follows from prior work.
Additive error of G., Let n; be the number of vertices in V, As a reminder, we defined C; def C V,, where V; is obtained by Theorem 3.1. Let D, be the smaller one of C. and V2 C..
Theorem 4.1 (Theorem 2. 14 in (Li & Saranurak, 2021)).
Given positive weighted n-node graph G (V, E, w) where the ratio between the largest edge weight and the smallest edge weight is bounded by U, and parameter db > O. there is deterministic poly(n, log -tim algorithm that finds cut (S, V.V. S) with |S] < V S) such that
By Theorem 2.2, we have wa (D.) - WG. -w; (D.)
S
(1)
By Theorem 3.1, we have
6G, (Dz) v. which implies wa, (Dx) 2 DD.ly In (.300)) s+ot1) polyylog(1)) Hence, we have
w(S) S $11s;
wa (C,) wo, (C.) a WG, WG,(C: (C()
For any cut (S.. ( S') with [S S V S'I and w(S') S \/d'p/ have that |S| > S / for some parameters S (ee(() = log 0(1) (n), 1
@ = (D:) - wG. (D:) wa (D,) v
0.
(3)
we set the polylog(n//) factor in s large enough.
(nizo = 0(1)
6

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Note that Theorem 4.1 essentially gives a bicriteria- approximation of the largest set with sparsity most v, where the approximation factors are denoted by deep and dsize- In other words, the size of the set S output by The- orem 4.1 is a sparsity at most // /esps.
and (S) is only caused by edges in G with weight smaller than v//0n. Therefore, wa(S) I wa. + (1/110)) - [S |S]) - 0.9 Furthermore,
of the largest set with
wc(() - w + (c) " S 0.9 + A - *IS,,
To obtain Theorem 4.1, we set the demand vector d to be the all-1 vector, and r 1 in Theorem 2.14 in (Li &
where the final step holds because vp 2 1 (n) 2 10
Saranurak, 2021). See also other versions of the results in,
For any cut (S", V \ 8") with |s V VV \ S and wc(( S / /Cexpp we have
e.g., (Nanongkai & Saranurak, 2017; Wulff-Nilsen, 2017; Chuzhoy et al., 2020).
"3(S") S (S') + (a - - $ $ + A|S = 3/5r1/2desp + A
Note that Theorem 4.1 may return S = 0. in which case it certifies that (SS) > /depp for all cuts (5', V \ S*) with 0 < |S"| < n. By combining Theorem 2.2 and Theorem 4.1, we can obtain a private version of Theorem 4.1 in a black- box way:
The above can be upper bounded by 0.6v|S5 dapp be- cause vo 2 v(n) 2 10Adesp. Furthermore, "2 (5') I wa((5") because we only decrease edge weights or re- move edges in G" compared to G. Therefore.
Theorem 4.2. Let 6, À E (0, 1/2) be parameters. For any n, there exists (nn) = (Lloo(///oo//////////// TTEE). so that given a non-negative weighted n-node graph G (V, E, w) and parameter & 2 (n.). there is polynomial time (e, 8DD algorithm that finds cut (S, V \, 5) with |S| S IV \S| such that with probability 1 - X it holds:
w S 0.6]S'//dexp S 0.8]5'1/dexp.
and we can apply the second guarantee of Theorem 4.1 to obtain |S] 2 |S'| as desired.
w(() S +1S);
The privacy guarantee follows because Theorem 2.2 is (c, 5)- DP, and the remainder of the algorithm is post-processing on the private output of Theorem 2.2.
For any cul (S' 5') with |S S IV \ S
and w(S') I $1S' we have that |S| >
|5'1/Cate for some parameters (n) = 2dexp( (11 log (1) (sizel))) = daize (n)=
=
Using Theorem 4.2, one could obtain a private expander decomposition algorithm using the method in (Nanongkai & Saranurak, 2017) for given graph G and sparsity parameter v. To describe the algorithm, we define few parameters. If n is the number of vertices in the input graph. then Esize = Csize Csize(n).. (n), Gexp = Cexp(n), and a Vlog Coxp/ logn. 31....,51 are parameters where $1 = n/2 + 1. 3, = 5:-1/n² for i > 1, and L is the smallest integer where 5r. < (these imply I. = ((1/o)). Also, let v; = v (Eesp) for 1 < S L. Let A(H, v) be the returned result of applying Theorem 4.2 on graph H with DP parameters g' nn log n), 8' (L log n), probability parameter X = 1/n and sparsity parameter vb
Proof. We first apply Theorem 2.2 with parameters e, 6, A to the input graph to obtain a graph G. With proba- bility 1- X, we have (s) - wc() I A|S| for A (log((//A) / n log n lo) for all S S V. We assume this holds in the remainder of the proof. Let y (n) 10Adesp(n)).
If some edge in G has weight smaller than v/10n, we simply remove this edge. Furthermore, if some edge in G has weight greater than vin, we set its weight to y.n. We call the updated graph G'. This way, the ratio between the largest edge weight and the smallest edge weight in G' is bounded by U = O(n?).
The algorithm is described in Algorithm 2. Note that com- pared to (Nanongkai & Saranurak, 2017), our description of the algorithm omits one variable I to the recursive calls, as it was not used by the algorithm and only used for analysis in (Nanongkai & Saranurak, 2017).
Then we run Theorem 4.1 on δ" with parameter 0.8g to obtain cut (S, V \ S) with [S] S IV \ (S.. The running time is hence poly (n,, log U)= (n).
Theorem 4.1 guarantees that (1) uyy (S) < 0.8 and (2) For any cut (S', V\SS") with |S|| < SV\'' and wa (S") < (')eepp we have |S| 2 | = S' Caize- Then,
The following two lemmas summarize some of the re- sults proved in (Nanongkai & Saranurak, 2017) regarding Algorithm 2. Lemma 4.3 shows that Algorithm 2 satis- fies the properties we want for our expander decomposi- tion, and Lemma 4.4 bounds the recursion depth of Algo- rithm 2 which is used in proving privacy. Even though in
Because way (S) < 0.8&|S), there is no edge in the cut with weight vin. Hence, the difference between wzz (5)
7

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Algorithm 2 The expander decomposition algorithm in (Nanongkai & Saranurak, 2017). A(H, ()) is the returned result of applying Theorem 4.2 on graph H with DP pa- rameters '' nn log n), 8' = (/ l),,), probability parameter À= = 1/n 10, and sparsity parameter
total number of recursive calls, and hence the total number of invocations of A, is + By union bound, the overall success probability is 2 - -- +
((1/n)).
We also need to guarantee that all invocations of Theo- rem 4.2 have sparsity parameter > ( as required. This holds because the smallest sparsity parameter we use is th = き (n) 2 ((H)).
Rb.
1: Input: A graph H = (V, F, w); a level parameter &
2: S 4 A(H, we)
3: if H a singleton or S = 0 then
Hence, all invocations of A are correct with probability O(1/n)), ), so the correctness follows from Lemma 4.3.
4: return H
5: else
Finally. we analyze the privacy guarantee of Algorithm 2. Let the edge difference between two inputs be at c = fu, w). Observe that when Algorithm recurses, the edge affects at most one of the recursive calls. Therefore, the number of recursive calls affected by e is upper-bounded by the recursion depth, which is bounded by Löszen" log n. The only part in Algorithm 2 that uses edge weights is via A, which is (E/ L" log n. 8/ LO log -DDP. Hence, Algorithm 2 is (s, O)-P by basic composition.
6: if [S] 2 1 then
7:
Recurse on (H[)), 1) and (H[V)S) f), and return
union of the results
8: else
9: Recurse on (H, l + 1) and return the result.
10: end if
11:
end if
(Nanongkai & Saranurak, 2017) their whole algorithm is stated work for unweighted graphs, these two lemmas still work for weighted graphs with little to no change of their proofs. The only slight change needed is for the second bullet point of Lemma 4.3, where (Nanongkai & Saranurak, 2017) showed an upper bound on the number of edges, but the same method can be extended to bound the total weight of edges for weighted graphs in a straighforward manner.
5. Applications
We highlight some downstream applications of our main result beyond the improved error bound for private all-cuts. These applications include many of those in prior DP graph cut works, e.g., (Arora & Upadhyay, 2019), except we use our improved bound from Theorem 1.1 as needed. We present our max-cut application in the main body and dis- cuss our other applications to the maximum meximummbissettoon, max- k-cut, and minimum-bisection problems in Appendix B.
Lemma 4.3 ((Nanongkai & Saranurak, 2017)). A always correctly returns a set S that satisifes the guarantees in Theorem 4.2, then Algorithu 2 on input (G = (V, E, w), 1) for an n-node non-negative weighted graph G returns a partition of V = V1 U...UI Vk. such that
Max-Cut. In the Max-Cut problem, we are given a weighted graph G (with non-negative weights), and the goal is output subset S C V maximizing (S). Goe- mans and Williamson gave a polynomial time algorithm for computing Çaw 1) approximation for any 1) > 0 where (Gw ss 0,87856 (Goemans & Williamson, 1995). Furthermore, is known that assuming the Unique-Game conjecture, it is NP-Hard to approximate Max-Cut to any factor better than Çaw + p for any p >> (Khot al., 2007).
For every 1 i S k the sparsity of G[Vi] is at least sb.
The total weights of edges between different parts V; and for i # j is O(Vinloggg n) x to()))
Lemma 4.4 (NNaonnkkai & Saranurak, 2017)). The re- cursion depth of Algorithm 2 on input (G, is at most Le log n (1))
With respect to DP, the prior state-of ti--thean art algorithms ob- tain the same multiplicative approximation as above, with additional additive enror coming from cut-sparsification. In particular, it is known that for any fixed r7 > O, there is a polynomial time algorithm satisfying E-DP with respect to adge-neighboring graphs, which on any non-negative weighted input graph G = (V, outputs subset C V satisfying wa(S) > (Gow - 17) maxs'gv wa(S")
Now we are ready to prove Theorem 3.1
Proof of Theorem 3.1. The algorithm is to simply call Al- gorithm with input (G, 1) and the value of (n) is the same as that from Theorem 4.2.
In order to apply Lemma 4.3, we need to show that all invocations of algorithm A are correct with probability 1 - ((1/n"). On each recursion level, the set of vertices in all the graphs H in the recursive calls are disjoint, so the total number of recursive calls on each recursion level is On). As the recursion depth o1) by Lemma 4.4, the
δ (n' meeting the same Ö(n 155) factor from cut- sparsification (Gupta et al., 2012).
We note that even if approximate-DD is allowed, there are no algorithms obtaining better than Ö(n--5) error, al-
8

---

Breaking the nt Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
though we remark that (Arora & Upadhyay, 2019) ob- tain refined guarantee with error of the form where [S"] is the cardinality of the optimal set maximizing the cut value. However, in the worst case, this bound is still 2(n Using our synthetic graph leads to improved guarantees, corollary of our main theorem, with a full proof in Appendix B.
of which we feel must be specifically highlighted here. Our work is theoretical in nature.
O(S"" polylog(1/8/]))
References
Aamand, A., Chen, J. Y., Dalirrooyfard, M., Mitrović, S., Nevmyvaka, Y. Silwal, S., and Xu, Y. Differentially pri- vate gomory-hu trees. arXiv preprint arXiv:2408.01798, 2024.
Corollary 5.1 (Corollary of our Main Theorem 3.2). For any fixed o > O, there exists polynomial time (c, 6)-DP algorithm that on any non-negative weighted n-node graph G (V, E, w) outputs a subset S S V satisfying (with high probability) that (S) is at least
Alon, N. and Naor, A. Approximating the cut-
norm via grothendieck's inequality. SIAM J. Comput., 35(4):787-803, 2006. doi: 10.1137/
S0097539700441629, URL https: /opps://dod aoiiorrg/0.. 1137/8009753970440 629.
(Gow - 7) max wa((") - 0(2).
S'EV
Arora, R. and Upadhyay, J. On differentially private graph sparsification and applications. In Proceedings of the Advances Neural Information Processing Systems 32 (NeurIPS), pp. 13378-13389, 2019.
6. Conclusion
Given graph G, we develop algorithm that, in DP manner, computes synthetic graph whose cut values are close to those in G. On n-node graphs with more than 1.5 edges, our algorithm imposes significantly lower additive error than the prior work. We obtain this result by decom- posing the input graph into sparse and dense regions. As byproduct, we show how to design DP algorithm for expander decomposition. One interesting open question is whether private expander decomposition has applications beyond all cuts.
Austrin, P., Benabbas, S., and Georgiou, K. Better balance by being biased: A 0.87766-aproximmation for max bisec- tion. ACM Transactions on Algorithms (TALG), 13(1): 1-27, 2016
Backstrom, L., Dwork, C., and Kleinberg, J. Wherefore art thou R3579X? anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th international conference on World Wide Web (WWW), pp. 181-190, 2007.
Our work leaves a few intriguing questions. Perhaps the most natural one is whether the additive error can be re- duced beyond n 1.25 while still allowing for a multiplicative approximation. Interestingly, an improved additive error the cost of allowing multiplicative errors) for graphs with roughly 15 edges would directly imply improvements for all graphs by plugging it into our method. This yields an- other open question: What is the range of the number of edges m > n for which the /mn additive error can be polynomially improved while allowing multiplicative er- rors?
Benezúr, A. A. and Karger, D. R. Approximating t minimum cuts in Ó(n²) time. In Proceedings of the Twenty-Eigtth Anmual ACM Symposium on Theory
of Computing, STOC '96, pp. 47-55. Association for Computing Machinery, 1996. ISBN 0897917855. doi:
10.1145/237814.237882
Chandra, R., Dinitz, M., Fan, C., and Zou, Z. Differentially private multiway and k-cut. CoRR, abs/2407.0691 2024. doi: 10448500/ARXIV.2407.0066
Chuzhoy, J., Gao, Y., Li, J., Nanongkai, D., Peng, R., and Saranurak, T. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 61 IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1 1158-1167, 2020. doi: 10. 109/FFCS4670002220..C.
Acknowledgements
A. Aamand was supported by the VILLUM Foundation grant 54451. J. Chen was supported by an NSF Graduate Re- search Fellowship under Grant No. 17453. S. Mítrović was supported by the NSF Early Career Program No. 2340048. Y. Xu was supported by HDR TRIPODS Phase II grant 2217058.
Culnane, C., Rubinstein, B. I. P., and Teague, V. Stop the open data bus, we want to get off. CoRR, hsss/190.05000. 2019.
Impact Statement
Dalirrooyfard, M., Mitrović, S., and Nevmyvaka, Y. Nearly tight bounds for differentially private multiway cut. In Proceedings of the Advances in Neural Information Pro- cessing Systems 36 (NeurIPS), 2023.
This paper presents work whose goal is to advance algorith- mic tools applied in the field of Machine Learning. There are many potential societal consequences of our work, none

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
de Klerk, E., Pasechnik, D. V., and Warners, P. On approx- imate graph colouring and max-k-cut algorithms based the O-function. Journal of Combinatorial Optimization, 8:267-294, 200--994.2000 2004.
Karger, D. R. Random sampling in eut, flow, and network de- sign problems. In Proceedings of the twenty-sixhh annual ACM symposium Theory of computing, pp. 648-657, 1994.
Dwork, C. Differential privacy. In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 1-12, 2006.
Khot, S., Kindler, G., Mossel, E., and O' D'Donnell, R. Opti- mal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing, 37(1): 319-357, 2007.
Dwork, C. and Lei, J. Differential privacy and robust statis- tics. In Proceedings of the 41st Anmual ACM Symposium on Theory of Computing (STOC), pp. 371-380, 2009.
Li, J. and Saranurak, T. Deterministic weighted ex- pander decomposition in almost-linear time. CoRR, abs/2106.01567, 2021.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Con- ference (TCC), volume 3876, pp. 265-284, 2006. doi: 10.1007/1 16877781688888.... _14.
Li, Y., Purcell, M., Rakotoarivelo, T., Smith, D., Ranbaduge, T., and Ng. K. S. Private graph data release: A survey, ACM Computing Surveys, 55(1 (0111))1-33)) 2023.
Liu, J., Upadhyay, J., and Zou, Z. Optimal bounds on private graph approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1019-10499 2024.
Eliáš, M., Kapralov, M., Kulkarni, J., and Lee, Y. T. Dif- ferentially private release of synthetic graphs. In Pro- ceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 560-578, 2020.
Nanongkai, D. and Saranurak, T. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n 1/2 Onn - Sy-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 1 1122-1129. ACM, 2017. doi: 10.1145/305339.305522
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., and Zhang, J. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-)):207-216 2005.
Frieze, A. and Jerrum, M. Improved approximation algo- rithms for MAX k-CUT and MAX BISECTION. Algo- rithmica, 18(1):67-88) -1,, 1997.
Narayanan, A. and Shmatikov, V. Robust de-anonymization of large sparse datasets. In Proceedings of the 2008 IEEE Symposium Security and Privacy (SP), pp. 111-125, 2008
Garey, M. R., Johnson, D. S., and Stockmeyer, L. Some simplified NP-complete problems. In Proceedings of the sixth annual ACM symposium Theory of computing, pp. 47-63, 1974.
Räcke, H. Optimal hierarchical decompositions for con- gestion minimization in networks. In Proceedings of the fortieth annual ACM symposium Theory of computing. pp. 255 265-264,77 2008
Goemans, M. X. and Williamson, D. P. Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115-1144 1995.
Raghavendra, P. and Tan, N. Approximating CSPs with global cardinality constraints using SDP hierarchies. In Proceedings of the twenty-thirl annual ACM-SIAM sym- posium on Discrete Algorithms, pp. 373-387, SIAM, 2012.
Gupta, A., Ligett, K., McSherry, F., Roth, A., and Talwar, K. Differentially private combinatorial optimization. In Proceedings of the st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
Saranurak, T. and Wang, D. Expander decomposition and pruning: Faster, stronger, and simpler. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2616-2635, 2019. doi: 10.1137/ 1.9781611975482.162.
Gupta, A., Roth, A., and Ullman, J. R. Iterative construc- tions and private data release. In Proceedings of the 9th Theory of Cryptography Conference (TCC), volume 7194, pp. 339-333-03333 3369-56,2220 2012. doi: 10.1007/978 00007797883-622-289144 _19.
Upadhyay, J., Upadhyay, S., and Arora, R. Differentially private analysis on graph streams. In The 24th Interna- tional Conference on Artificial Intelligence and Statistics, AISTATS 2021, volume 130 of Proceedings of Machine Learning Research, pp. 1171-1179, PMLR, 2021.
Hay, M., Li, C., Miklau, G., and Jensen, D. Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining, pp. 169-178. IEFE, 2009.
10

---

Breaking the n² Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Wulff-Nilsen, C. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1 1130-1144 143,, 2017. doi: 10.1145/
3055399.3055415.

---

Breaking the nt Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
A. Proof of Theorem 2.3
Proof of Theorem 2.3. order to prove the theorem, we first introduce the notion of cut norm. For any real n by n matrix A, the cut norm of A is defined as
|
max IJJS
ΣΣ
A.j
iE JEJ
Given any matrix A, there is polynomial time algorithm that outputs an estimate ||A|le such that 0.56|| S ||Alc S ||Alle (Alon & Naor, 2006).
For an undirected graph G, let Wa denote its weighted adjacency matrix. Given non-negative weighted graph G, (Eliăš et al., 2020) showed an (s, (DPP polynomial time algorithm that outputs a non-negative weighted graphs G such that
E [ Walle] s
(V"L
w
(F)
log (m)
Let L be Olognn) with a sufficiently large constant hidden in front of O. We run (Eliáš et al., 2020)'s algorithm with parameters (e/ 6) independently for L times to obtain G1....,Gy Gz. By Markov's inequality, for each G.
for some A o (V
[|WG- Walllc <
(( (e(E)nlog log
log? nn gllog with probability at least 2/3.
The algorithm then proceeds to compute an approximation di, of ||G; - -ÿylc for every i,j E [L] using (Alon & Naor, 2006)'s algorithm. The algorithm then outputs arbitrary G; the result where di, S 2A for more than half of the indices j E [L] (break ties arbitrarily; if there is no such satisfying the requirement, the algorithm may output an empty graph).
First of all, this graph is (s, 6)D by basic composition.
Next, we show the correctness of the algorithm with high probability. By standard concentration bounds, E ||W6- Wa [lo]
A holds for more than half of the synthetic graphs G with high probability. We next condi-
tion on this event.
Let C [Z.] with [7] > L/2 be the set of indices with | Wa [cc]
s A. For any i,j E I,
d.s & IWa. Wa lc S IWa. - Wallo + ||WG Wa lce 22.
Hence, for any i the number of j where dı, - 2A is than L/2, the algorithm will not output empty graph.
Now let G be the graph output by the algorithm. Since there are more than L.2 indices j with de, S 24, and |T| L/2, there must exist some j E where dij I 2A. Then
W -Walc S [Wa
-W Waylcc+110 +IWW, Wolle 0.56
d + =A=
For any cut (S, V S), we have
w (8) - (8)--
Σ Σ
(Wa. WVG.-W).. u.
$ <|W Woll O(D),
WES vEViS
as desired.
B. Omitted Applications
We discuss additional applications of our main result to the maximum bisection, max-k-cut, and minimum bisection problems. We also give the full proof of Corollary 5.1 for our max-cut application.
12

---

Breaking the n Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Max-Cut.
Proof of Corollary 5.1. The algorithm is straightforward. We compute our private synthetic graph G on the input graph G, letting a 10100 in Theorem 3.2. Then, we run the best off-the-shee shelf approximation algorithm for max-cut on G. This yields solution in & with Şow 17110 100 multiplicative error. Note that privacy is not affected since the latter step is post-processing- In our private synthetic graph, every cut is approximated up to additive error A as defined in Equation 1. Letting S be the subset of V that we output, we have
wG(S) 2 1 (g((5) -
SGw 7/100
w A
1+ a
s'CV
SGW - 1/100
max ((1 - aSwa((") - A) - A g'CV
1+
(Sow
7/100) - a)
max "a((') 0(4)
1+ a
S'gV
(Sow 11) max wa( O(A),
5'CV
as desired.
Maximuum-Bisection and Max-k-Cut. The Mokiimum-Bisectionn problem is a well-studied variant of Max-Cut with balance constraints. More precisely, given weighted graph G. seek to find cut S satisfying |S| n/2 we can assume n is even by adding an isolated node - such that (c(S) is maximized (Frieze & Jerrum, 1997).
Max-k-Cut is an alternate way to generalize Max-Cut where we seek to partition V into k pieces, maximizing the total weight of edges across distinct pieces (Frieze & Jerrum, 1997). Since these problems generalize Max-Cut, both problems cannot be solved exactly in polynomial time unless = P. Furthermore, similar to Max- Max-Cut, cannot be approximated better than Çaw + 77 for any 1) 0 (Khot al., 2007; Raghavendra & Tan, 2012), under the Games conjecture. For upper bounds, it is known that Maximum Mlxiimum-Bisection can be approximated to factor SMB - ") for any 17 > 0 where {MB R 0.8776 (note that this is not quite the same Çaw, although it is close) (Austrin et al., 2016), and Max-k k-tt can be approximated to multiplicative factor > - 1/k for any k 2 1 (Frieze & Jerrum, 1997; de Klerk et al., 2004). We remark that better bounds are known for small values of l: (Frieze & Jerrum, 1997; de Klerk et al., 2004).
known that Mexiiuu--Bieection
To obtain DP algorithms for these problems, we follow the same approach as for the previous applications. Namely, we invoke the appropriate non-privee privarivae optimization algorithms on private synthetic graph, resulting an e-DP algorithm with the same multiplicative factor approximation as non-private, and with additive error O(n 1.5 /e) in the Maximum-Bisecta problem, and Ökn 1.5 /s) for Max-k-Cut. For example, this follows from the work of (Gupta et al., 2012).
Our main result yields improved bounds, as stated by the following claim. The proof is almost identical that of Corollary 5.1, omit it.
Corollary B.1 (Corollary of our Main Theorem 3.2). There exists polynomial time (), algorithm that any non non-negative weighted n-node graph G = (V, E, w) outputs subset S S V. n/2 satisfying (with high probability) that (G(S) 9) is at least
max wa(S') n 1.25+ polylog S'CV. =n/2
(SMB 11
E
Similarly, for any k 2 1, there exists an (E, DDP algorithm that runs in time poly(n, log log(1/8), log(1/=)) and partitions V into Sy...., Sy such that (with high probability) the total weight of the edges between distinct partitions at least (ck 11) fruction of the optimal solution up to an additive error
kn 1,25++(1) polylog
Sinniuum-Bisection This application is the natural minimizing variant of Bexximum-Bisecttinn Recall that a bisection of a graph is a partition of its nodes into two equal-sized sets, so we want to minimize w(S)) subject to |S| n//2.. The cost of
13

---

Breaking the nt Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
bisection is the weighted cost of edges crossing the The study of this problem can be traced back to almost five decades ago (Garey et al., 1974), and it is known that solving the problem exactly is NP-hard. The best-known polynomial-time algorithm achieves (log n) -approximation (Räcke, 2008).
Concerning DP, prior work on DP all-cuts can again be applied straightforwardly (simply run the bisection algorithm of (Räcke, 2008) as post-processing), which gives an E-DP algorithm computing the conimum--biecttion with multiplicative approximation (n)) and additive error O (e)). Again, we note that even if approximate DP allowed, previous algorithms cannot improve the additive enror. Our main theorem gives the following corollary, which obtained by again running the standard bisection algorithm of (Räcke, 2008) on the output of our main theorem as post-processing.
Corollary B.2 (Corollary of our Main Theorem 3.2). There a polynomial time algorithm satisfying (e, 5)-DP, which on any nonnegative weighted n-node graph G (V, E, w) outputs subset S V satisfying |S| n/2 and wg(S) is (with high probability) at most
min "G() + n n1.25+0(1) polylog s'
(llg(nn)
14


Reviews:
[{"review_id": "by1JdhFcpo", "reviewer": "Reviewer_pbng", "summary": "This paper studies the problem of graph cut sparsification under the constraint of differential privacy (DP). They cross the known $n^{1.5}$ additive error mark to provide a DP algorithm that has an additive error of $\\tilde{O}(n^{1.25+o(1)})$ and a small multiplicative error. Their key underlying subroutine is one that *privately* outputs an expander decomposition of the input graph $G$, which has not been done prior to this work. Their main algorithm has three steps, where they first run the private expander decomposition algorithm, followed by running the algorithm by Elias et al. 2020 on the inter-component edges, and finally running the algorithm by Upadhyay et al. 2021 on the individual components. There is one last post-processing step to sparsify the graph using non-private prior work (which is fine in this case as we're just post-processing). Their DP expander decomposition algorithm is of independent interest. This paper has purely theoretical results, and they show other theoretical applications of their work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We will adjust the final draft according to your suggestions, elaborating where there were points of confusion.\n\n> I'm confused by the proof of Theorem 3.2 It just says that it's in Algorithm 1. That's not really a proof. Or are you just trying to say that you will show this constructively by proving the correctness of Algorithm 1?\n\nWe apologize for the confusion. Please note that the proof environment for Theorem 3.2 ends on Line 310 and the proof is contained in Subsections 3.1 - 3.3. Each subsection handles the privacy, approximation, and success probability parts of the proof separately. However, we admit it is misleading to use numbered subsections to organize a proof. We will change the style.\n\n> For Theorem 4.1, maybe explain the meanings of d_exp and d_size. I don't know what they're supposed to mean beforehand, and what they're supposed to imply.\n\nWe used the same notation as in the prior work of Li & Saranurak. The intuition is that the theorem can find a cut such that any possible cut with substantially smaller sparsity (as measured by d_exp; note exp stands for expansion), must also be smaller in size in terms of the number of vertices (as measured by d_size). Note that later in Theorem 4.2 we obtain a private version of Theorem 4.1. We will update the text to include more intuition.\n\n> More explanation about the theorems and what their roles are would make sense. For example, some details about what Theorem 4.1 and 4.2 are saying, along with what Lemmata 4.3 and 4.4 are implying would be really helpful. It just feels like I'm reading technical statements without context/intuition on why they're going to be useful.\n\nThanks for the suggestion. We will include a more intuitive summary of Section 4 before the theorem statements and proofs in the paper. At a high level, in Theorem 4.1 and Lemma 4.3, we introduce the existence of an algorithm for non-private expander decomposition from prior work. By expander decomposition, we mean a partition of the vertices such that every part has high connectivity in the sense that every cut is non-sparse (has a high fraction of edges to vertices). We use Lemma 4.4 from prior work, which upper-bounds the recursive depth of this algorithm. Theorem 4.2 introduces our contribution, which replaces the core algorithm from Theorem 4.1 with a private analogue.\n\n> For Section 3.1, two partitions will get affected if you're doing replacement definition. Under add/remove, only one partition will be affected. Please, be clear about your model of privacy.\n\nThis is a good question. We use the standard model of edge-neighboring privacy, which is the same as the add/remove model over the database of edges. Importantly, two partitions are still affected in the add/remove model because a single edge touches two vertices.\n\n> Have you thought about node DP for this problem? What could the potential challenges be and how would the bounds be affected? It's just a speculative question, rather than something for the purpose of evaluation.\n\nThis is a nice open question raised by Elias et al. This setting is much harder and there is nothing non-trivial known for preserving cuts using node DP to the best of our knowledge. \n> Also, have you thought about proving lower bounds in this multiplicative error setting? I'm mostly speculating about the tightness of your bounds (mostly out of curiosity).\n\n\nWe are optimistic that near-linear additive error, when allowing constant multiplicative error, is possible to achieve in polynomial time. It is already known how to achieve this in exponential running time; see Eliás, Kapralov, Kulkarni, Lee SODA’20. We believe this is an interesting challenge for the field. We also note that $\\Omega(n)$ error is necessary even when allowed a multiplicative approximation, see Dalirrooyfard, Mitrović, Yuriy Nevmyvaka, NeurIPS’23.", "claims_and_evidence": "I'm confused by the proof of Theorem 3.2 It just says that it's in Algorithm 1. That's not really a proof. Or are you just trying to say that you will show this constructively by proving the correctness of Algorithm 1?", "methods_and_evaluation_criteria": "The metrics make sense -- the problem is very well-defined, so there is no question of checking the evaluation criteria. Theoretical comparison with prior work is there, which is pretty much what we're looking for.", "theoretical_claims": "I read the proofs quickly in the main body, but briefly glanced at the proofs in the appendix. What I looked at seemed fine.", "experimental_designs_or_analyses": "N/A, since the results are purely theoretical.", "relation_to_broader_scientific_literature": "This is a well-defined fundamental problem that didn't have better results. The results in this work are significantly better, but that said, it keeps the question open to get even better bounds on the additive error. The DP expander decomposition algorithm is of independent interest with potential applications in other places.", "essential_references_not_discussed": "Not that I'm aware of.", "other_strengths_and_weaknesses": "Strengths:\n1. The $\\tilde{O}(n^{1.25+o(1)})$ additive bound is great and is significant. It's a big improvement over the prior $O(n^{1.5})$ bounds.\n2. I like the DP expander decomposition algorithm as a subroutine, and I'm curious to see what other applications it may have. It seems like a good contribution -- to be fair, it might be the main contribution, given that the other two steps of the main algorithm are simply applying the prior work as black-box.\n3. The theoretical applications are also interesting. Would like to see more though to put the results into perspective a bit more.\n\nWeakness:\n1. I'm mostly concerned about the writing a bit. Whilst the high-level flow is clear enough, the low-level details are sometimes hard to follow. I will write a little bit below.", "other_comments_or_suggestions": "1. For Theorem 4.1, maybe explain the meanings of $d_{exp}$ and $d_{size}$. I don't know what they're supposed to mean beforehand, and what they're supposed to imply.\n2. More explanation about the theorems and what their roles are would make sense. For example, some details about what Theorem 4.1 and 4.2 are saying, along with what Lemmata 4.3 and 4.4 are implying would be really helpful. It just feels like I'm reading technical statements without context/intuition on why they're going to be useful.\n3. For Section 3.1, two partitions will get affected if you're doing replacement definition. Under add/remove, only one partition will be affected. Please, be clear about your model of privacy.", "questions_for_authors": "Have you thought about node DP for this problem? What could the potential challenges be and how would the bounds be affected? It's just a speculative question, rather than something for the purpose of evaluation.\n\nAlso, have you thought about proving lower bounds in this multiplicative error setting? I'm mostly speculating about the tightness of your bounds (mostly out of curiosity).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3orCdGG2KP", "reviewer": "Reviewer_E2qf", "summary": "The paper studies the problem of graph sparsification which preserves all cuts, a fundamental problem in graph algorithms, under differential privacy. This problem has been well studied but remains open. The paper makes significant improvements to prior work in terms of the additive approximation factor and running time, in particular beating the n^{1.5} bound, which held for a long time. The technical contributions are strong, and the presentation is quite good.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\n> In definition 2.4, since non-edges are viewed as weight 0 edges, and (u, v) can be any pair of nodes, the edge set should be V^2? So E and E’ both should be V^2. This would be relevant for all the formal statements which mention E.\n\nThank you. This is a good point, and we will update the text to address it.\n\n> Do the results hold if the set of edges is fixed and only the weights of two existing edges differ by 1?\n\nYes, this is an easier setting (consider the non-edges to be zero-weight edges), so our results also hold. \n\n> It might be helpful to explain the main theorems a bit more as part of the technical contribution in section 1.2. \n\nThank you. We will add more exposition in Section 1.2 in the final version.\n\n> It would be useful to explain the notion of private expanders\n\nBy an expander partition, we intuitively mean a partition of the nodes into some number of parts such that the “connectivity inside” every part is high and the total number of edges in between the partitions is low. We use sparsity to formalize “connectivity” (see line 140, right column). We want to output such a decomposition which respects edge-neighboring privacy.\n\n> Is it possible to get better approximation using your approach if you preserve only large cuts lower bounded by some threshold?\n\nOur results directly imply that we obtain a multiplicative approximation for all cuts above $n^{1.25}$ (ignoring logarithmic and privacy factors). This improves upon prior work which can only guarantee a multiplicative approx. for cuts above $n^{1.5}$. It is an interesting open question of whether one can do better.\n\n> Would the techniques work for other notions of expansion?\n\nWe did not consider other notions of expansion since our final goal was towards cut approximation, but this is an interesting direction for future work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "This is a theoretical paper", "theoretical_claims": "Not very carefully, but generally seem right", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Very good comparison. The paper makes significant advances over prior bounds as described in Table 1", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The paper is technically quite interesting and makes a significant improvement over\nprior results, as the authors compare well. The presentation is generally quite nice.\nThe authors also show that their methods lead to improvements to other important problems such as max-cut and max-k-cut.", "other_comments_or_suggestions": "In definition 2.4, since non-edges are viewed as weight 0 edges, and (u, v) can be any pair of nodes, the edge set should be V^2? So E and E’ both should be V^2. This would be relevant for all the formal statements which mention E.\nDo the results hold if the set of edges is fixed and only the weights of two existing edges differ by 1?\nIt might be helpful to explain the main theorems a bit more as part of the technical contribution in section 1.2. \nLine 240: “outputs partition of” --> “outputs a partition of”\nIt would be useful to explain the notion of private expanders", "questions_for_authors": "Is it possible to get better approximation using your approach if you preserve only large cuts lower bounded by some threshold?\nWould the techniques work for other notions of expansion?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YThPolw3iQ", "reviewer": "Reviewer_qAzu", "summary": "This paper investigates $(\\varepsilon, \\delta)$ differentially private graph cut sparsification under edge-privacy.\nMore exactly, given a non-negative, undirected graph $G=(V, E, w)$ the goal is to output a non-negative, weighted, undirected graph $\\tilde{G}$ that (1) approximates the value of all cuts in $G$ and (2) satisfies differential privacy.\nError is measured as $\\lvert w(G) - w(\\tilde{G}) \\rvert \\leq \\gamma w(G) + \\alpha$ for $\\gamma \\geq 0$, and we are primarily interested in dense input graphs.\n\nFor a purely additive error ($\\gamma=0$), when an upper bound on the number of edges $m$ is known, error $\\tilde{O}(\\sqrt{mn})$ is possible (Elias et al., 2020, Liu et al., 2024).\nFor dense graphs more broadly $\\alpha = O(n^{1.5})$ is always possible (Gupta et al., 2012) and there is a matching lower bound (Elias et al., 2020; Liu et al., 2024).\nHowever, once a multiplicative error ($\\gamma > 0$) is also allowed, this lower bound no longer applies.\nAllowing for a multiplicative error, $\\alpha = O(n\\log n)$ is known (Elias et al., 2020) which is known to be near-optimal (Dalirrooyfard et al., 2023), but this algorithm requires exponential time.\nThe main question addressed in this paper is closing the gap between the $O(n^{1.5})$ and $\\tilde{O}(n)$ additive error, while allowing $\\gamma > 0$, for algorithms running in polytime.\n\nThis paper makes meaningful progress towards this by designing a polytime algorithm with dependence $n^{1.25 + o(1)}$ for their additive error.\nThe central idea in the paper is to implement a private expander decomposition (Theorem 3.1) and apply it to $G$ to yield partition of the vertices $V_1,\\dots, V_k$.\nEach of the induced subgraphs $G[V_1], \\dots, G[V_k]$ will be dense, and the remaining edges not included in the subgraphs form a sparse graph on $V$, call it $G_{sparse}$.\nRunning existing private cut approximation algorithms for carefully chosen parameters on $G[V_1], \\dots, G[V_k]$ and $G_{sparse}$, leveraging the density of the former and the sparsity of the latter, gives us private synthetic graphs $\\tilde{G}[V_1], \\dots, \\tilde{G}[V_k], \\tilde{G}_{sparse}$.\nReturning the union of all of these edge weights gives a synthetic graph $\\tilde{G}$, with non-negative edge-weights that preserves all cuts up to the aforementioned errors (Theorem 3.2).\nTo get a sparse synthetic graph with similar guarantees, the authors show that post-processing $\\tilde{G}$ with a non-private cut-sparsification algorithm allows for recovering much the same guarantee (Theorem 1.1).\nThis last step, however, can be performed for all algorithms in Table 1 that achieve non-negative weights.\n\nThe authors go on to show that their algorithm can be used for downstream applications, including max-cut, where their results imply better polytime algorithms for these problems.\n\n## update after rebuttal\n\nI had no questions, but after taking all other rebuttals into account, I feel confident in keeping my score as is.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I read through the proofs in the main part of the paper.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The results in this paper achieve state of the art for private cut sparsification in polytime.\nThe private expander decomposition in the paper is of independent interest.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well-written. The balance between intuition and technical detail is good.\n2. The problem being studied is practically motivated, and I think the main algorithm is a meaningful contribution.\n3. The idea for the main algorithm seems natural in hindsight, but requires some technical work (notably the private expander decomposition).\n4. The private expander decomposition could see use for other problems in this domain.\n\nWeaknesses:\nNothing comes to mind.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "I have no questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VHGMba22VH", "reviewer": "Reviewer_xtuG", "summary": "This paper focuses on designing differentially private algorithms for graph cut sparsification.\n\nThe previously best-known private and efficient cut sparsifiers on n-node graphs approximate each cut within $O(n^{1.5})$ additive error and $1+\\gamma$ multiplicative error for any $\\gamma>0$.    \nExponential time algorithms can achieve an $O(n)$ additive error and $1+\\gamma$ multiplicative error.    \n\nThis work breaks the $n^{1.5}$ additive error barrier for private and efficient cut sparsification.   \nThe authors present an $(\\varepsilon, \\delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\\gamma$ and additive error $n^{1.25+o(1)}$ (ignoring dependencies on $\\varepsilon, \\delta, \\gamma$).    \n\nThe approach is based on a private algorithm for expander decomposition, a technique in graph algorithms.\n\n---\n## update after rebuttal\nSparsification is an important procedure in graph algorithms, and private implementations can lead to improved private graph algorithms. Given the nice theoretical improvement and the independent contribution of private expander decomposition, as confirmed in the rebuttal, I remain positive about the result.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\n> While it is justified by lower bounds, an argument could be made that the additive error is large and is unlikely to yield a practical implementation.\n\nWe are hopeful that for dense graphs, where cuts can be as large as $\\Omega(n^2)$, our techniques could yield improved practical results over the prior $n^{1.5}$ error algorithms. However, our focus is on proving an improved asymptotic privacy-utility trade-off. \n\n> There is a possible typo on line 365: all S should be S’\n\nThanks, we will update the typo.\n\n> Are there any prior applications of private expander decomposition? If not, I think this fact should be highlighted more.\n\nTo the best of our knowledge, we are the first to study private expander decomposition. In our paper we mainly focused on cuts, and it is an interesting future direction to study further applications of our private expander procedure. We will make sure to highlight this in the paper.", "claims_and_evidence": "All claims are theoretical and are supported by formal proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I verified all proofs in the main body but not extremely thoroughly.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work breaks the $n^{1.5}$ additive error barrier for private and efficient cut sparsification and achieves multiplicative error $1+\\gamma $ and additive error $n^{1.25+o(1)}$. The previously best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $O(n^1.5)$ additive error and $1+\\gamma$ multiplicative error.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n- The application of expander decomposition for graph DP appears to be novel and can likely find applications elsewhere.\n- The overall algorithm is conceptually simple and is well-presented\n- Private cut sparsification is an important problem with many downstream applications for DP graph algorithms, as shown by the authors.\n\nWeaknesses:\n- The key contribution of private expander decomposition consists of using a previous ($n^{1.5}$ additive error) DP cut approximator and running a non-private sparsest cut algorithm recursively. While the combination requires some cleverness, it does consist of stitching together existing results.\n- While it is justified by lower bounds, an argument could be made that the additive error is large and is unlikely to yield a practical implementation. \n\nThat being said, the theoretical improvement is nice and would still be a great addition to ICML", "other_comments_or_suggestions": "There is a possible typo on line 365: all $S$ should be $S’$\n\nAre there any prior applications of private expander decomposition? If not, I think this fact should be highlighted more.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper develops a private algorithm for expander graph decomposition in order to give a better private cut sparsifiers. The reviewers agree that the result is interesting and a clear improvement over prior work. Moreover, this seems to be the first application of expander decompositions to private algorithms, and it may influence future work. The paper would make a nice contribution to ICML.
Decision: Accept (poster)