arXiv CSopen access

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers Chenglin Fan∗

Jingcheng Liu†

Pan Peng‡

Hangyu Xu‡

Zongrui Zou†

arXiv:2607.18846v1 [cs.DS] 21 Jul 2026

Abstract We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additive error, the e (n3/2 ). If one allows a small multiplicative slack, an informationoptimal worst-case error is Θ theoretic exponential-time mechanism achieves nearly linear additive error, but the best known polynomial-time algorithms have substantially larger error. We give a polynomial-time (ε, δ)differentially private algorithm which, for every n-vertex unweighted graph G, outputs a none such that, with high probability, every cut S ⊆ V ( G ) negative weighted synthetic graph G satisfies e ε,δ,γ (n13/12+o(1) ). |wG (S) − wGe (S)| ≤ γwG (S) + O e (n5/4+o(1) ) of Aamand et al. This improves the previous polynomial-time worst-case bound O (ICML 2025) for mixed multiplicative/additive private cut approximation. The main technical ingredient is a new set of private spectral primitives for bounded-degree graphs. Our power-based spectral amplifier releases high powers of the adjacency matrix and uses the noisy amplified matrix to identify the large-eigenvalue subspace. The square amplifier √ e δ ((nd)1/4 / ε) in estimating the graph Laplacian for graphs of maximum gives spectral error O √ e δ ( n/ε)} baseline in the high-degree degree d, being the first to beat the standard min{2d, O regime. We further develop a bootstrapped fourth-power primitive with a sharper error dependence on n and d for the downstream cut approximation. Combined with a stable port gadget, a demand-aware recursive expander decomposition, and a new edge-sensitive termie (n + (n2 M )1/3 ) on graphs with M edges, this yields the final nal cut oracle with additive error O √ 13/12 + o ( 1 ) e worst-case O(n ) private cut-release error. We also prove an Ω( n) lower bound on the error of private Laplacian release, which holds under approximate √ differential privacy even for graphs of average degree O(1). This shows that the worst-case n-scale spectral barrier is information-theoretic, even for sparse graphs.

1 Seoul National University. Email: [email protected] 2 Nanjing University. Emails: [email protected], [email protected] 3 University of Science and Technology of China. Emails: [email protected], [email protected]

Contents 1

Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2

2

Technical Overview 5 2.1 Private Laplacian Analysis via a Spectral Amplifier . . . . . . . . . . . . . . . . . . . 5 2.2 Building an Edge-Sensitive Cut Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 e (n13/12+o(1) ) Additive Error . . . . . . . . . . . . . 10 2.3 Private Cut Approximation with O e (n5/4 ) bound . . . . . . . . . . . . . . . . . . . . . 10 2.3.1 The bottleneck behind the O 2.3.2 Our approach: recursive sparsification plus a relative terminal oracle . . . . . 11

3

Preliminaries 3.1 Basics in Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Spectral Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Useful Tools in Probability and Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 14 15

4

Power-based Spectral Amplifier for Private Matrix Release 4.1 Definitions and Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Privacy Guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Utility Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 17 17 19

5

Differentially Private Graph Laplacian Analysis 5.1 Graph Laplacian Estimation via Square Amplifier . . . . . . . . . . . . . . . . . . . . 5.2 A Bootstrapped Fourth-Power Spectral Primitive . . . . . . . . . . . . . . . . . . . . . 5.2.1 Local Column Norm for Two-Walk . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 The Improved Private Spectral Primitive . . . . . . . . . . . . . . . . . . . . .

21 23 25 25 27

6

An Edge-sensitive Private Cut Oracle 6.1 The Regularized Separation Objective and Cut Approximation . . . . . . . . . . . . . 6.2 The Private Mirror Descent Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Differential Privacy Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Utility Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33 34 37 37 41

7

e (n13/12+o(1) ) Additive Error for Cut Approximation An O 7.1 Stable Port Gadget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Private Demand Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Stable Port Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Demand-Sensitive Private Cut Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Private Expander Decomposition with Demand . . . . . . . . . . . . . . . . . . . . . 7.4 Private Cut Approximation via Recursive Expander Decomposition . . . . . . . . . .

47 48 48 49 50 52 58

8

Hardness of Graph Spectral Estimation with Approximate DP 8.1 The Hard Family and Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Reconstruction violates Approximate-DP . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Proof of Theorem 61 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63 64 66 68

1

Introduction

Graph data provides a powerful and intuitive framework for modeling complex interactions, making it widely used in areas like machine learning, network analysis, social sciences, and biology. As a graph may contain sensitive information such as contact networks, financial transactions and communication logs, ensuring the privacy of these underlying relationships is a fundamental challenge. To mitigate the risk of exposing sensitive data, Differential Privacy (DP) [DMNS06] has been established as the gold standard for privacy-preserving data analysis. A randomized algorithm A is (ε, δ)-differentially private if, for every pair of “neighboring” datasets D and D ′ differing by at most one individual record, and for every set of possible outputs S , it holds that: Pr[A( D ) ∈ S] ≤ eε Pr[A( D ′ ) ∈ S] + δ. Informally, this ensures that the behavior of the algorithm remains indistinguishable (parametrized by (ε, δ)) whether any single individual opts into or out of the dataset, so an adversary observing the final algorithmic output cannot infer the presence or exact data of any specific individual. Differential privacy has established successful applications in private graph analysis including cut approximation [GRU12, EKKL20, DMN23, LUZ24, ACD+ 25, CDFZ26], spectral approximation [BBDS12, AU19, UUA21, ZLU25], correlation or hierarchical clustering ([BEK21, CFL+ 22, IEM+ 23, CAEL+ 22, DGU+ 25, ZEFD26]) and numerical statistics release ([KNRS13, US19, BCSZ18, DSZ+ 21, IMC22, RSWZ26]), among others. A central problem in private graph analysis is to release a synthetic graph preserving the values of all cuts. For an unweighted graph G = ([n], E), write wG (S) for the number of edges (or the sum of edge weights in weighted graphs) crossing (S, [n] \ S). We seek to release a (probably weighted) e under edge-level privacy (firstly proposed in [DMNS06]) such that, simultaneously for all graph G S ⊆ [ n ], (1 − γ)wG (S) − α ≤ wGe (S) ≤ (1 + γ)wG (S) + α. (1) Here γ ∈ [0, 1) is a relative-error parameter and α is the additive error. In edge-level privacy, two graphs G, G ′ are neighboring if they differ by adding or removing at most one edge. The purely additive case γ = 0 is now well understood. It is easy to verify that adding independent Gaussian noise with variance O(log2 (1/δ)/ε2 ) on the 0/1 weight between each pair of e (n3/2 /ε). More revertices is (ε, δ)-edge-level differentially private, and it gives an error α = O √ e ( mn/ε) on m-edge fined algorithms of Gupta et al. [GRU12] and Eliáš et al. [EKKL20] achieve O graphs, and this dependence is essentially tight for unweighted graphs due to lower bounds in [EKKL20]. Liu et al. [LUZ24] further sharpened the weighted setting. Thus, in the dense worst e (n3/2 )-scale error. case m = Θ(n2 ), purely additive private cut release has an unavoidable Θ This error scale is too large for many dense graphs. A dense graph may contain sparse but structurally important cuts, and an additive error of order n3/2 can completely hide them. This motivates the mixed guarantee (eq. (1)) for γ ∈ (0, 1): large cuts are approximated relatively, while small cuts are protected by an additive floor. In this mixed model, Blocki et al. [BBDS12] e (n), using the gave an information-theoretic, exponential-time mechanism with additive error O existence of cut sparsifiers and the exponential mechanism over all sparse graphs. The challenge is algorithmic. The exponential-time mechanism searches over a huge family of sparse synthetic graphs, and it has not been clear how to reproduce the same behavior in polynomial time. Aamand et al. [ACD+ 25] recently made the first polynomial-time progress beyond the purely e (n3/2 ) barrier in the mixed model, achieving an additive error of O e ε,δ,γ (n5/4+o(1) ). Their additive O approach is based on private expander decompositions: inside an expander piece, the graph is highly connected, which means that any cut contains enough edges to absorb the additive noise of 1

a local private release as a small relative error (i.e. γwG (S)), leaving a residual graph of unprocessed inter-component edges to be released separately. Their work identifies the right high-level strategy, but it relies on a one-time decomposition and leaves two bottlenecks. First, the best-known (before this paper) private spectral primitive √ e used to estimate cuts inside the expanders has an O( n) spectral error. This error is oblivious to the graph’s density, and forces the algorithm to use a high expansion threshold that consequently leaves a massive residual graph. Second, to process this leftover graph, their algorithm falls back to a standard purely additive release. Specifically, it uses the synthetic graph oracle by Eliáš et √ e ( nM ) error on an M-edge residual. al. [EKKL20], which inherently incurs an O This paper addresses both bottlenecks. To overcome the first, we have to develop new private spectral primitives whose errors explicitly depend on the graph’s maximum degree d (e.g., achieve ((nd)1/4 ) spectral error). Because these primitives become increasingly accurate as the ing an O graph becomes sparser, they make it possible to √ apply expander decompositions recursively on the e ( n)-error private spectral estimators. To address residual, which is impossible with previous O the second bottleneck, we introduce a new terminal oracle for sparse residual graphs. Here terminal means “at the end of the recursion”: it is a final-stage subroutine invoked only after the recursive decompositions have made the residual sparse enough, releasing this leftover graph directly rather than decomposing it further. By our new degree-sensitive primitives, the recursion drives the residual graph to n5/4+o(1) edges. Our terminal oracle privatizes an M-edge residual with an e (n + (n2 M )1/3 ) and a small multiplicative relaxation. Combining these two inadditive error of O e (n13/12+o(1) ), improving over the previous O e (n5/4+o(1) ) gredients yields a final additive error of O e (n) information-theoretic benchmark. polynomial-time bound and moving closer to the O

1.1

Our Results

Private cut approximation.

Our main theorem is the following.

Theorem 1 (Private Cut Approximation, restatement of Corollary 60, Section 7). Let G = (V, E) be an n-vertex unweighted graph. For every ε ∈ (0, 1), δ ∈ (0, 1/2) and γ ∈ (0, 1/4), there is a polynomiale such that, with high time (ε, δ)-edge-DP algorithm that outputs a non-negative weighted synthetic graph G probability, simultaneously for all cuts C ⊆ V, ! 13/12+o (1) n eδ |wG (C ) − wGe (C )| ≤ γwG (C ) + O . εγ7/6 The theorem should be compared with three benchmarks. The first is the optimal purely addie (n3/2 ) in the dense worst case. The second is the exponential-time O e (n) mixed-error tive bound Θ mechanism of Blocki et al. [BBDS12]. The third is a recent polynomial-time mixed-error bound e (n5/4+o(1) ) of Aamand et al. [ACD+ 25]. Our exponent 13/12 lies strictly between the efficient O 5/4 barrier and the nearly linear information-theoretic target. More importantly, the proof introduces a modular way to combine degree-sensitive private spectral release with an edge-sensitive terminal oracle; this modular interface may be useful for further improvements. Private spectral primitives. The first main technical component is a family of private Laplacian estimators. For a graph G with Laplacian LG := DG − AG , we measure error in spectral norm ∥ LG − LGe ∥2 . This is stronger than cut approximation in the sense that

|wG (S) − wGe (S)| = |1⊤ e )1S | ≤ ∥ L G − L G e ∥2 · | S |. S ( LG − LG 2

(2)

Spectral approximation is also useful beyond cuts, since the Laplacian controls random walks, effective resistances, and many spectral graph quantities [Lov93, SS11]. For an n-vertex graph of maximum degree d, two simple baselines are immediate. The zero estimator has error √ at most 2d as ∥ LG ∥2 ≤ 2d if G is unweighted, and the dense Gaussian meche anism has error O( n/ε) (see e.g. [BBDS12]). Previous private spectral-approximation results, including the topology-sampler approach of Liu, Upadhyay and Zou [LUZ24], essentially achieve e (d)-type worst-case dependence on the maximum degree for weighted graphs, together with a aO √ e O( n)-type fallback. Both bounds are insufficient for our recursive √ cut algorithm: an additive ere ( n) error from adding Gaussian ror proportional to d is trivial for unweighted graphs, and the O noise is oblivious to graph sparsity and therefore does not yield better accuracy as the residual becomes sparser, preventing us from applying recursion to the residual graph. We therefore need a primitive that is genuinely sublinear in d in the regimes encountered by the recursion. Our new spectral primitives are based on a new technique, the power-based spectral amplifier (Theorem 24, Section 4), which we develop as a generic mechanism for the private release of symmetric matrices. Specialized to graph Laplacian matrices, the square √ amplifier already gives a e ( n/ε)}, and the fourth-power clean improvement upon the longstanding baseline min{O(d), O primitive is designed for the recursive cut framework. Theorem 2 (Private Laplacian Release, restatement of Theorems 29 and 32, Section 5). Let G be an n-vertex graph with maximum degree at most d. For every tunable parameter q ≥ polylog(n, 1/δ)/ε, e whose there is a polynomial-time (ε, δ)-edge-DP algorithm that outputs a non-negative weighted graph G Laplacian satisfies, with high probability,         1 n1/4 q1/4 (nd)1/4 d n1/8 d1/2 q1/8 e e e √ ∥ LG − LGe ∥2 ≤ O + + min O ,O √ + , 2d . (3) ε εq ε3/8 ε3/4 ε √ e (d) primitive. The term d/ q in (3) is important. It should not be confused with the known O In the recursive cut framework, a local spectral error Λ(d) leads to a residual-degree recurrence e (d) error therefore of the form dt+1 ≈ Λ(dt ), up to privacy, γ, and polylogarithmic factors. A O √ does not reduce the residual degree. By contrast, d/ q, with q a sufficiently large polylogarithm, is a tunably contracting linear term. The polynomial fixed point is then governed by the sublinear terms in (3). We also show that the maximum degree d cannot be replaced by average degree, as the worst√ case private spectral release has an unavoidable n lower bound even if average degree is constant. Theorem 3 (Spectral Lower Bound in Sparse Graphs, restatement of Theorem 61, Section 8). Fix a constant 0 < ε < 1 and let δ = n−c . Any (ε, δ)-edge-DP algorithm that releases a synthetic graph Laplacian b L must incur worst-case expected spectral error √   E ∥ LG − b L ∥2 = Ω ( n ). The hard instances are connected graphs with maximum degree Θ(n) and average degree O(1). √ It should be noted that an Ω( n) worst-case spectral lower bound in dense graphs already im3/2 plicitly follows by Eliáš et al. [EKKL20] (since a spectral √ from the Ω(n ) lower bound for cut error 3/2 error of o ( n) would immediately yield a cut error of o (n ) by eq. (2)). However, their hard instances require davg = Θ(n) so cannot rule out possibility of a spectral primitive whose error scales with the√average degree. Our lower bound is based on connected hidden-star instances. Spectral error o ( n) would reconstruct most private edges incident to a high-degree center; approximate differential privacy forbids such reconstruction. This shows that the role of our degree-sensitive spectral primitives is not to beat this barrier on every graph, but to exploit the decreasing residual degree inside the cut algorithm. 3

Edge-sensitive terminal cut release. The second ingredient is a terminal oracle for sparse residual graphs. We use the phrase terminal cut release for this final direct release step: after the recursive expander routine has reduced the hard leftover edges to a graph with only M edges, we stop recursing and privately release that leftover graph’s cut function in one shot. This terminal step is different from the local spectral releases used earlier in the recursion; it is designed to exploit sparsity of the residual edge set rather than expansion of individual pieces. Theorem 4 (Edge-Sensitive Cut Oracle, restatement of Theorem 37, Section 6). Let G = (V, E) be an n-vertex unweighted graph, and let M ≥ | E| be a public upper bound. For every ε, δ ∈ (0, 1) and γ ∈ (0, 1/4), there is a polynomial-time (ε, δ)-edge-DP algorithm that outputs a non-negative weighted e such that, with high probability, simultaneously for all cuts C ⊆ V, graph G  2 1/3 ! n n M e |wG (C ) − wGe (C )| ≤ γwG (C ) + O + . ε ε2 γ √ e ( nM/ε) in The above theorem should be compared with the purely additive error bound O [EKKL20]. When M is moderately sparse and a relative slack is allowed, our terminal oracle is better. The key new feature is that its error depends √ on the number of residual edges through the cubic expression (n2 M )1/3 , rather than through nM. This improved edge sensitivity is the reason reducing the residual to n5/4+o(1) edges suffices to obtain the final exponent 13/12. A modular composition theorem. To compose preceding primitives, we must bridge the arbitrary degrees of intermediate residuals with the bounded-degree requirements of our spectral oracles. We achieve this via two combinatorial tools: a stable port gadget (Section 7.1) privately flattens high-degree vertices to match the graph’s average degree. It routes incident edges to public “ports” via randomized stable truncation, preserving cuts with O(1) sensitivity. The demand-aware expander decomposition (Section 7.3) is the matching decomposition step: it measures the size of a side by its public port demand, not by the raw number of original vertices. This ensures that expansion, spectral error, and residual charging are all measured in the same units. Theorem 5 (Modular spectral-to-cut amplification, informal). Suppose there is a polynomial-time (ε, δ)-DP spectral primitive which, on every N-vertex graph of maximum degree at most d, releases a Laplacian with error at most Π( N, d). Suppose further that there is a terminal cut oracle with mixed error αterm (n, M ) on residual graphs with at most M edges. Then the recursive port-and-expander framework gives a polynomial-time private cut release algorithm whose residual edge counts satisfy    e ε,δ,γ n Π O e (n), Mt /n , Mt + 1 ≤ O up to polylogarithmic and no(1) factors. If this recurrence reaches MT , then the final cut error is γwG (S) + αterm (n, MT ) simultaneously for all cuts S ⊆ V ( G ). In our instantiation, Π is the bootstrapped fourth-power primitive (the second term in eq. (3), e (n + (n2 M )1/3 ) due to Theorem 4. The recurrence reaches MT = Theorem 2) and αterm (n, M ) = O 5/4 + o ( 1 ) n , and the terminal oracle then gives n13/12+o(1) . This theorem is included to emphasize that the proof is not a black-box substitution into the one-shot expander-decomposition algorithm in Aamand et al. [ACD+ 25]. The spectral primitive, the stable port gadget, the recursive demandaware decomposition, and the terminal oracle must be matched so that each edge is charged either multiplicatively inside an expander or additively only at the sparse terminal stage. 4

2

Technical Overview

We now give a more detailed overview of the proof. The algorithm has three layers. The first layer is spectral: we build private Laplacian estimators whose accuracy improves as the maximum degree decreases. The second layer is combinatorial: we use a stable port gadget and a demandaware expander decomposition so that a residual with m edges can be treated as a graph of degree scale m/n. The third layer is terminal: once the residual is sparse enough, the edge-sensitive cut oracle finishes the release. The layers are complementary. A better spectral primitive alone only yields an additive cut error proportional to the size of the queried side |S| (as illustrated in eq. (2)). An expander decomposition alone reduces the problem size only if the local spectral oracle is accurate enough relative to the expansion threshold. A terminal oracle alone helps only after the graph is already sparse. The proof is therefore a unified pipeline: the spectral primitive triggers the private expander decomposition to shrink the residual recursively, and the terminal oracle converts the final residual size into the global all-cuts error bound.

2.1

Private Laplacian Analysis via a Spectral Amplifier

Given a simple graph G = ([n], E) with bounded degree d and adjacency matrix A ∈ Rn×n , our e to minimize ∥ A e − A∥2 , and then combine first step is to privately release a synthetic matrix A e A with privately released degrees to form an estimator of Laplacian LG . A direct application of the Gaussian mechanism to A adds independent noise N (0, σ2 ) with σ = Θ(log(1/δ)/ε) to each ′ ∥ ≤ O (1) under edge-level privacy. Therefore, the resulting noise matrix entry of A as ∥ A − A√ F e ( n/ε) due to Lemma 20. This gives the standard oblivious baseline, but it has spectral norm O does not exploit the bounded-degree structure of the graph. The square amplifier. Our first spectral amplifier improves on this baseline by releasing a noisy version of A2 rather than A itself. The entries of A2 count length-two walks, or equivalently common neighbors. In a d-bounded graph, changing one edge only changes a controlled local collec√ 2 ′ 2 tion of such two-walk counts. Formally, this ensures that ∥ A − ( A ) ∥ F = O( d) for neighboring ′ 2 e adjacency matrices √ A, A . Hence the noise matrix of a Gaussian release Y = A + W has spectral e ( nd/ε). norm ∥W ∥2 = O As illustrated in Figure 1, the advantage is that the signal is amplified quadratically. If A = with |λi | moderately large in A becomes ∑i λi ui ui⊤ , then A2 = ∑i λ2i ui ui⊤ . Thus an eigenvector √ e ( nd/ε), the direction ui can be separated much easier to detect in A2 . In particular, once λ2i ≳ O from the noise in the amplified matrix. Equivalently, the amplifier identifies all directions with  √  e (nd)1/4 / ε . | λi | ≳ O The remaining directions can be safely discarded, as their contribution to the final spectral √error 1/4 e e ∥ A − A∥2 is exactly their maximum absolute eigenvalue in A, which is at most O((nd) / ε). Driven by this intuition, the adjacency release proceeds in three steps: 2 e • First, we √ release an amplified matrix Y = A + W, where W is Gaussian noise calibrated to the O( d) sensitivity of A2 .

e with eigenvalues falling below the noise scale η = • Second, we truncate all eigenvectors of Y √ e O( nd/ε), leaving an orthonormal basis U ∈ Rn×r for the remaining r eigenvectors.

5

Squared amplifier A2

Original adjacency matrix A direct-release √ noise

amplified √ noise

e ( n) O

e ( nd) O

dense-graph scale

e (n) O

λ2i

| λi | hidden by

directions visible

discarded

noise

after direct release

directions

directions recovered from A2

Φ2 ( X ) = X 2 Spectral Amplification

√ e ( n). Releasing A2 Figure 1: Spectral amplification by the square map. Directly releasing A incurs spectral noise O √ instead amplifies eigenvalues from λi to λ2i , while bounded degree keeps the sensitivity of A2 at O( d), giving amplified √ √ e ( nd). Thus directions with λ2 ≳ O e ( nd), equivalently |λi | ≳ O e ((nd)1/4 ), can be recovered. This spectral noise O i 1/4 e explains the O((nd) ) adjacency spectral error.

• Third, privately release only the compressed matrix U ⊤ AU + E where E ∈ Rr×r is the Gaussian noise calibrated by ∥U ⊤ AU − U ⊤ A′ U ∥ F = O(1). The total spectral error balances the truncation bias and the subspace noise. For the truncation bias, eigenvalues of A2 in the discarded √ subspace are bounded by η, so their spectral contribution e ((nd)1/4 / ε). For the subspace noise, the diagonal of A2 contains to A is bounded by η 1/2 = O vertex degrees, giving tr( A2 ) ≤ nd. Since each of the r surviving √ eigenvectors has an eigenvalue of e ( nd). Consequently, the spectral at least η, we establish that r · η ≤ tr( A2 ) ≤ nd, yielding r ≤ O √ e ( r) = O e ((nd)1/4 ), matching the truncation error. norm of the noise matrix E is bounded by O e e yields a pseudo-Laplacian e Finally, combining A with a privately released degree matrix D L= e To guarantee non-negative edge weights for downstream cut algorithms, we apply an SDP e − A. D L − X ∥2 to project e L onto post-processing step from [UUA21]: solving LGe = arg minX ∈Ln ∥e Ln =

n

o X ∈ Rn×n | X = X ⊤ , Xij ≤ 0 for i ̸= j, X1 = 0 ,

the convex cone of all valid non-negative weighted graph Laplacians. √ e ( n/ε) This square amplifier is useful as a standalone primitive. It improves over the naive O e (d) bound when d ≫ adjacency release whenever d = o (n), and it improves over the degree-only O 1/3 n . Further, it is also strong for the cut-approximation in our recursive framework. If the spectral primitive has error scale n1/4 d1/4 , then the recurrence in the cut framework drives the edge count of residual graph to only M = n4/3 . Specifically, applying our new terminal oracle (Theorem 4) e (n10/9 ) additive cut error, which breaks the previous O e (n5/4 ) to this residual already yields an O 13/12 e (n polynomial-time barrier. However, to achieve our final O ) error, we must force the residual graph even sparser. Next we show how to develop a more advanced fourth-power primitive that achieves a sharper error contraction. Why fourth powers are delicate. Motivated by the A2 amplifier, it is natural to ask whether we can evaluate higher powers, as evaluating Aq for larger even q amplifies the spectral gap more aggressively. Unfortunately, the delicate trade-off between truncation error and subspace noise in A2 breaks down for higher powers, such as A4 . The obstacle is local two-walk congestion. The 6

sensitivity of A4 is governed by two-walk energy defined as κ2 ( G ) := max ∥ A2 ev ∥22 = max ∑ codeg(u, v)2 . v ∈V

v ∈V u ∈V

This quantity can be as large as d3 , for example in a d-clique or in a complete bipartite graph Kd,d . Thus the hard examples are not only triangle-rich graphs; biclique-like regions with many repeated two-walks are equally problematic. A naive A4
-amplifier calibrated to the worst-case d3 sensitivity e n1/8 d5/8 + (nd)1/4 , therefore does not improve over the A2 primitive. yields a spectral error of O For further improvements, our solution is to first identify, in a private aggregate way, the edges responsible for large two-walk energy κ2 , and only then apply the A4 amplifier to the remaining graph with smaller sensitivity. Iterated cubic-score cover. The key preprocessing step is an iterated cubic-score cover. The score ( A3 )uv counts length-three walks from u to v. It is useful because, for any remaining graph R and any x ∈ [n]: ∥ A2R e x ∥22 = ( A4R ) xx = ∑ ( A3R ) xy , (4) y∈ NR ( x )

where NR ( x ) is the set of neighbors of x in R. Hence, if every edge xy in R has small cubic score ( A3R ) xy , then every vertex has small two-walk energy. The cover works as follows. Starting with ei = A3 + Zi for the R0 = G, we privately release a noisy cubic matrix by Gaussian mechanism B Ri current residual Ri . We then add to a public pair support Pi all unordered pairs uv whose noisy cubic score is above the current threshold, and we remove from Ri the actual residual edges whose unordered pairs lie in Pi . In other words, [
Pi . Ri+1 := Ri \ E( Ri ) ∩ Pi , P := i

The support Pi contains pairs rather than only true edges; this aggregate support is important for privacy, because it avoids revealing the exact edge set. The reason for iterating is that the sensitivity decreases as the residual becomes less congested. Initially every d-bounded graph satisfies κ2 ( R0 ) ≤ d3 . More generally, we show that if the current √ e ( Ki ). residual satisfies κ2 ( Ri ) ≤ Ki , then the Frobenius sensitivity of the cubic query A3Ri is only O √ e ( Ki ). Since every remaining residual Thus the next noisy cubic-score cover can use threshold O edge has a cubic score below this threshold, and any vertex has at most d neighbors, the new local two-walk energy (which is the sum of cubic scores to adjacent neighbors, as shown in eq. (4)) is √ e bounded by d times the threshold. Thus, the next residual satisfies Ki+1 = O(d Ki ). Starting from e ( d2 q ), K0 = d3 , this recurrence rapidly approaches to a fixed point of d2 . We stop when Ki ≤ O where q is a polylogarithmic slack parameter. At this point, e (d2 /q). ∆( P) ≤ O

e ( d2 q ), κ2 ( R ) ≤ O

where ∆( P) is the maximum degree in the pair support P. We then release the actual edges of G inside the support P by adding Gaussian noise only to every existing pair in P, as P is now public. e (d2 /q), Gaussian mechanism gives spectral error Since the support degree is O q  2 e e (d/√q). O d /q = O This term is linear in d, but it is divided by a tunable polylogarithmic factor. In the recursive cut e (d) framework, this makes it a genuinely contracting linear term rather than the non-contracting O term from degree-only spectral release. 7

Fourth-power release on the residual. After the iterated cover, the residual graph R satisfies e (d2 q). This low two-walk-energy condition makes the fourth-power query stable: κ2 ( R ) ≤ O  q  4 4 e ( d2 √ q ) ∥ A R − A R′ ∥ F ≤ O d κ2 ( R ) ≤ O

√ 2√
e for neighboring graphs R, R′ . Therefore a Gaussian release of A4R has spectral noise O nd q .
e n1/8 d1/2 q1/8 . Taking fourth roots, the truncation bias is O Following the identical logic as the analysis of the square amplifier, the subspace noise added
e n1/4 q1/4 . into the retained low-dimensional space is O Combining the private release of the covered part, the application of A4 -amplifier on the residual graph, and a standard private degree estimation yields our improved spectral primitive, which achieves an error of   d 1/8 1/2 1/8 1/4 1/4 e e ∥ LG − L∥2 ≤ Oε,δ √ + n d q + n q , q which is the second bound stated in (3). As before, we conclude with a post-processing SDP projection to ensure the final output is a valid Laplacian of a non-negative weighted graph. √ The important feature is the combination of a tunable contracting term d/ q with two genuinely sublinear amplifier terms. Taking q = polylog n, the polynomial fixed point of the residualdegree recurrence is d = n1/4 , which is the source of the improved cut approximation bound.

2.2

Building an Edge-Sensitive Cut Oracle

We next describe the terminal cut oracle used at the end of the recursion. Its role is to release the cut function of a sparse residual graph more accurately than what is possible from a purely additive release (e.g., the mechanisms in Eliáš et al. [EKKL20] or Gupta et al. [GRU12]) alone. Let G = ([n], E) be the current residual graph, and suppose that we have a public upper √ bound e M ≥ | E|. A standard differentially private cut-release mechanism gives additive error O( Mn) simultaneously for all cuts [EKKL20]. This bound is essentially optimal for purely additive cut release. However, our overarching goal is to achieve a mixed multiplicative and additive error. Since the edges processed earlier in the recursive expander decomposition are already approximated with a γ relative error, it is sufficient to evaluate the sparse residual graph under the same multiplicative slack. We exploit this relaxation to bypass the purely additive barrier, designing a b satisfying mixed-error terminal oracle: for every cut S ⊆ [n], it outputs a synthetic graph G 
 e ε,δ,γ n + n2 M 1/3 . |wGb (S) − wG (S)| ≤ γwG (S) + O Our terminal oracle is best viewed as a private multiplicative-weights update over edge histograms. We represent the residual graph by a histogram h over the edge universe ([n2 ]). To make the total mass public and stable under edge replacement, we add a dummy coordinate ⊥ and set h(⊥) = M − | E|. Thus the padded histogram has total mass M. A cut S ⊆ [n] corresponds to a [n]

query vector cS ∈ {0, 1}( 2 )∪{⊥} , with cS (⊥) = 0, and ⟨h, cS ⟩ = cutG (S). The goal is to construct a synthetic histogram b h such that, for all cuts S,

|⟨b h − h, cS ⟩| ≤ γ⟨h, cS ⟩ + α, where α is the target error. In multiplicative weights update, we iteratively find a cut that violates the above inequality, computing the gradients and updating the edge weights in b h accordingly. 8

√ Breaking the Mn barrier: Absorbing variance via multiplicative slack. Inspired by private iterative methods [GRU12, EKKL20, PX25], we replace the computationally inefficient discrete search for violated cuts with a continuous regularized semidefinite programming relaxation. However, the fundamental departure from prior work lies in our potential function analysis. It is important to note that the improved (n2 M )1/3 bound cannot be achieved by just modifying the objective in prior works, that is, applying the standard private mirror √ descent analysis from e Eliáš et al. [EKKL20] to our relative-error objective fails to beat the O( Mn) barrier. Symmetri√ e ( Mn) cally, employing our analysis on a purely additive objective is also restricted to the same O bottleneck. To be more specifically, in standard private mirror descent using KL divergence as the potential1 (Bregman Divergence), a single update step with learning rate η changes the expected potential by roughly −η · (first-order gain) + η 2 U, where the second-order term η 2 U acts as a variance penalty proportional to the expected gradient magnitude U. For a purely additive error guarantee (γ = 0), one is forced to bound this η 2 U term generically (e.g., via Cauchy-Schwarz), which restricts √ the step size η to be very small and limits the potential drop per round, this results in the final Mn error. Our core insight is that with relative error γ, the first-order progress term naturally contains a −ηγU component. By carefully tuning the learning rate η = Θ(γ/B) (where B is a hard clipping threshold of gradients), this −ηγU term actually absorbs the positive variance penalty +η 2 U. As detailed in our proofs of Lemma 48, this absorption allows us to extract a much larger drop in the potential function per iteration (scaling with γ) without relying on generic Cauchy-Schwarz bounds. This rapid potential decay reduces the required number of iterations, lowering the privacy e ((n2 M )1/3 ) additive error. composition cost and yielding the final O Having established the intuition behind our improved error bound, we now detail the specific algorithmic components that gives our new edge-sensitive cut oracle. Multiplicative Gaussian mechanism and log-det stability. To privately generate the gradients for this update step, recall that we formulate the cut separation problem as a continuous SDP relaxation over a covariance matrix Σ. Conceptually, Σ is a fractional representation of a violating cut found by SDP. However, the exact optimum of an unregularized SDP can be very unstable under edge changes, making privatization difficult. To overcome this, we show that the log-det regularizer, λ log det(Σ), gives the stability needed for privacy. Let Σ and Σ′ be the optimal covariance matrices (i.e., fractional cuts) for two neighboring input graphs, we prove that Σ−1/2 (Σ′ − Σ)Σ−1/2

F

≤ O(1/λ).

We then use a multiplicative Gaussian mechanism, adapted from Eliáš et al. [EKKL20], to privately sample a Gaussian direction from the optimized covariance. By advanced composition over T √  T e iterations, it is enough to choose λ = Θδ to obtain (ε, δ)-differential privacy. ε

Relative multiplicative weights update. Once a private fractional violating cut is obtained, we update the synthetic histogram using a relative multiplicative-weights step. To bound the maximum gradient B and satisfy the learning rate requirement η = Θ(γ/B), the SDP feedback is clipped before being used in the update. Clipping controls the tails of the Gaussian sample and 1 In this framework, the potential function (specifically the KL divergence) acts as a metric of the "distance" between our current synthetic edge distribution and the true target graph. The algorithm’s convergence is proven by showing that every valid update strictly decreases this potential, thereby bounding the total number of required steps. See [BG17] for a detailed introduction to the potential method.

9

ensures that the expected KL potential decreases predictablyby the  γ-absorbed amount described M e iterations with high probability. above. Consequently, the capped run terminates after T = O γα

Balancing the parameters. The final error is obtained by balancing three effects. The log-det e (λn). Privacy requires λ to grow like regularizer contributes an additive bias proportional to O   √ e δ ( T/ε), where the number of adaptive calls is roughly T = O e M . Larger λ improves stability Θ γα

but increases the regularization bias. Solving the resulting balance gives  2 1/3 ! n M n eδ . α=O + ε ε2 γ This proves the edge-sensitive terminal cut oracle stated in Theorem 4. Conceptually, the terminal oracle is a separate, self-contained module from our recursive spectral reduction for the worst-case cut approximation. The recursion is used to reduce the residual edge bound M, while this terminal oracle converts the smaller M into a final mixed multiplicative/additive cut guarantee. Any future improvement either to the residual size produced by the recursion or to the terminal oracle itself can be plugged into the same modular framework.

2.3

e (n13/12+o(1) ) Additive Error Private Cut Approximation with O

We now explain how the spectral primitive and the edge-sensitive terminal oracle combine to yield our worst-case private cut approximation guarantee. We first recall the bottleneck in the previous e (n5/4 )-additive-error framework, and then describe how our recursive degree-sensitive approach O breaks this barrier. 2.3.1

e (n5/4 ) bound The bottleneck behind the O

e (n5/4 ), while Aamand et al. [ACD+ 25] obtains a private cut approximation with additive error O allowing a small multiplicative error. Their approach can be viewed as having two phases. First, one can just use a private Laplacian for estimating cut sizes as illustrated in eq. (2). The Gaussian e satisfying mechanism adds noise to all (n2 ) potential edges and produces a synthetic graph G

√ e ( n/ε). ∥ LG − LGe ∥2 ≤ O Consequently, for every cut S, the error is

√ e 1⊤ e ) 1S ≤ O (| S | n/ε ). S ( LG − LG Their key observation is that this error can be absorbed into a (1 + γ)-multiplicative error only √ e when the true value of every cut S is at√ least Ω(|S| n/(εγ)). Equivalently, the graph must have e ( n/(εγ)) with respect to the usual cardinality demand expansion parameter roughly ψ = Θ ρ(S) = |S| (see eq. (6) for the definition of expansion). Given this observation, the graph is privately decomposed into such expanders by iteratively using the private Laplacian estimator LGe to find sparsest cuts. In expanders, cuts are multiplica√ e (nψ) residual edges [NS17]. With ψ ≈ n, tively estimated. A ψ-expander decomposition leaves O e (n3/2 ) edges. Applying the standard purely additive private the residual therefore has mres = O e (√nmres ) = O e (n5/4 ). cut release of Eliáš et al. [EKKL20] to this residual gives error O

10

√ e ( n), forcThe bottleneck is thus twofold. The local spectral primitive has global error scale O √ ing the expander threshold to remain at n and leaving n3/2 residual edges. Moreover, the final release is purely additive, so even if the residual were somewhat smaller, the terminal cost would e (√nmres ). still be governed by the square-root expression O 2.3.2

Our approach: recursive sparsification plus a relative terminal oracle

Our framework improves both parts of the above pipeline.

√ e ( n)-spectral 1. Degree-sensitive recursive sparsification. Instead of using a worst-case O primitive, we use our new degree-sensitive private Laplacian primitive in Theorem 2. Its error decreases as the residual graph becomes sparser. This allows us to apply expander decomposition recursively: after each round, the residual becomes sparser, which in turn makes the next spectral call more accurate. 2. Edge-sensitive terminal release. Once the residual is sufficiently sparse, we do not use the √ e standard purely additive O( mn) release.  Instead,
we use  the relative-error terminal oracle 1/3 2 e from Theorem 4, which gives error Oε,δ,γ n + n M on a residual with at most M edges. A technical issue remains before a degree-sensitive primitive can be really used. A sparse graph may still have very large maximum degree; for example, a star has only O(n) edges but maximum degree Θ(n). Since our spectral primitive depends on maximum degree instead of average degree (which is unavoidable due to Theorem 3), we first flatten degrees using a stable port gadget and then run a demand-aware expander decomposition. This yields the following four-step pipeline. Step 1: Degree flattening via the stable port gadget. Let R be the current residual graph with m edges. Set davg := 2m/n. The stable port gadget replaces each vertex v by roughly 

degR (v) bv ≈ max 1, davg



ports. Incident edges are routed to ports using public hashing and stable truncation. The resulting proxy graph, denoted ♯ R, has

∑ bv = ∑ max{1, deg(v)/davg } = O(n)

v∈[n]

(5)

v∈[n]

vertices and maximum degree ∆( R♯ ) = O(davg ) = O(m/n). Moreover, changing one original edge changes only O(1) edges in the proxy graph, so the transformation preserves edge-level privacy up to constant factors. Cuts in the original graph are represented by clone-consistent cuts in the proxy graph. Step 2: Demand-aware expansion. Vertex splitting changes the correct notion of cut size. A set containing a high-degree original vertex may contain many ports, even if it contains only one original vertex. Thus cardinality is no longer the right scale. We assign each original vertex a demand ρ(v) := bv , so that the number of ports representing a set S is exactly ρ(S) = ∑v∈S ρ(v). A demand-aware ψ-expander guarantees that every internal cut has size at least ψ · min{ρ(S), ρ(V \ S)}. This matches the way the spectral error scales after the port transformation. Let mt be the public upper bound of residual edge count at round t, and write 11

dt := 2mt /n. Suppose the private spectral primitive on a graph of degree d has error Π(n, d, ε, δ). For further decomposing the residual with at most mt edges, after flattening the degrees to make sure that the maximum degree is around O(dt ), we choose the expansion parameter: ψt ≍

Π(n, dt , ε, δ) . γ

This ensures not only that such ψt -expanders can be found privately by our spectral primitives, and that the spectral additive error is absorbed into a γ-fraction of the true cut value inside the expander piece. Step 3: Recursive sparsification. Due to [NS17] and eq. (5), the demand-aware expander dee (ψt ρ(V )1+o(1) ) = O e (ψt n1+o(1) ) edges for the next residual. Hence, we composition leaves only O 2 start from the trivial upper bound m0 = n , and the recursion satisfies:    e ε,δ,γ n1+o(1) Π n, mt , ε, δ . m t +1 ≤ O n Equivalently,

e ε,δ,γ (Π(n, dt , ε, δ)) . d t +1 ≤ O

Our bootstrapped fourth-power spectral primitive gives   d 1/8 1/2 1/8 1/4 1/4 e Π(n, d, ε, δ) = Oε,δ √ + n d q + n q , q where the tunable q ≥ polylog(n, 1/ε, 1/γ, log(1/δ)) is chosen large enough to absorb privacy, √ failure-probability, and decomposition losses. The first term d/ q is a genuine polylogarithmic e (d) degree-only spectral bound, which would contraction. It is crucially different from the known O not contract the residual. The polynomial fixed point is determined by the two sublinear terms. Ignoring polylogarithmic factors, the recurrence is governed by dt+1 ≲ n1/8 d1/2 + n1/4 . t Both terms have the same fixed point: dt+1 ← n1/8 d1/2 t and trivially

dt+1 ← n1/4

=⇒ =⇒

d∗ = n1/4 , d∗ = n1/4 .

e (n1/4+o(1) ), and the final residual has m T = Thus after T = O(log n) recursive rounds, d T = O e (n5/4+o(1) ) edges. nd T /2 = O Step 4: The terminal end-game. If we applied the standard purely additive private cut release to e (√nm∗ ) = O e (n9/8+o(1) ). Instead, we use the edgethe terminal residual, the error would be O sensitive terminal oracle (Theorem 4). On a residual M edges, it gives a mixed  with at most
1/3  2 e relative/additive guarantee with additive term Oε,δ,γ n + n M . Substituting M = m T =  1/3 e (n5/4+o(1) ) yields n2 · n5/4+o(1) O = n13/12+o(1) .

12

Therefore the final synthetic graph satisfies, simultaneously for all cuts S ⊆ V, e ε,δ,γ (n13/12+o(1) ). | cutGb (S) − cutG (S)| ≤ γ cutG (S) + O This proves the claimed worst-case private cut approximation bound in Theorem 1. Conceptually, the recursion and the terminal oracle play complementary roles: the recursion reduces the residual edge count from n2 to n5/4+o(1) , while the terminal oracle converts this sparsity into a final additive error better than the purely additive square-root release.

3

Preliminaries

3.1

Basics in Differential Privacy

For two datasets D, D ′ in some data domain D ∗ , we denoted as D ∼ D ′ if they are neighboring. Fix any ε ≥ 0, 0 ≤ δ ≤ 1. A randomized algorithm A is (ε, δ)-differentially private if for any pair of neighboring datasets D ∼ D ′ and any set of outcomes O , Pr[A( D ) ∈ O] ≤ eε Pr[A( D ′ ) ∈ O] + δ. Lemma 6 (Post processing [DMNS06]). Let M : D ∗ → O be an (ε, δ)-differentially private algorithm. Let f : O → O ′ be an arbitrary randomized mapping, then f ◦ M : D ∗ → O ′ is also (ε, δ)-differentially private. Lemma 7 (Sequential Composition [DR14]). Let M1 , . . . , Mk be a sequence of randomized algorithms, where each Mi takes as input a dataset D ∈ D ∗ and a transcript of all previous outputs y<i = (y1 , . . . , yi−1 ). If for every i ∈ [k ] and every fixed transcript y<i , the algorithm Mi (·, y<i ) satisfies (ε i , δi )-differential pri  vacy, then the joint mechanism M( D ) = (M1 ( D ), . . . , Mk ( D )) satisfies ∑ik=1 ε i , ∑ik=1 δi -differential privacy.

Lemma 8 (Advanced Composition [DRV10, DR14]). Let ε ∈ (0, 1) and δ ∈ (0, 1). Suppose an algorithm adaptively applies a sequence of k randomized mechanisms, where each mechanism satisfies (ε 0 , δ0 )differential privacy. There exists an absolute constant c > 0 such that if ε0 ≤ c p

ε k log(2/δ)

and

δ0 ≤

δ , 2k

then the overall composite algorithm satisfies (ε, δ)-differential privacy. The following introduces the Laplace distribution and its standard tail bound: Definition 9 (Laplace distribution). Given parameter b, the Laplace distribution (with scale b) is the distribution with probability density function   1 |x| exp − . Lap( x |b) = 2b b We use Lap(b) to denote the Laplace distribution with scale b. Lemma 10 (Tail bound on Laplace distribution). Let x be a random variable with Lap(b) distribution. Then, Pr[| x | ≥ tb] ≤ exp (−t).

13

We also describe mechanisms that are commonly used in differential privacy. We begin by defining the sensitivity of a function. Definition 11 (ℓ p -sensitivity). Let f : D ∗ → Rk be a query function on datasets. The ℓ p -sensitivity of f (with respect to D ∗ ) is ∆( p) ( f ) = max ∥ f ( D ) − f ( D′ )∥ p . ′ ∗ D,D ∈D , D∼D′

Lemma 12 (Laplace mechanism [DMNS06]). Fix any ε > 0. Suppose f : D ∗ → Rk is a query function with ℓ1 -sensitivity ∆(1) ( f ). Then the mechanism

M( D ) = f ( D ) + ( Z1 , · · · , Zk )⊤ is (ε, 0)-differentially private, where Z1 , · · · , Zk are i.i.d random variables drawn from Lap(∆(1) ( f )/ε). Lemma 13 (Gaussian Mechanism [DR14]). Fix any ε ∈ (0, 1) and δ ∈ (0, 1). Suppose f : X → Rk is a query function with ℓ2 -sensitivity ∆(2) ( f ). Then the Gaussian Mechanism M, defined by

M( D ) = f ( D ) + N (0, σ2 Ik ), is (ε, δ)-differentially private if the noise scale σ satisfies s   ∆ (2) ( f ) 1.25 σ≥ 2 ln . ε δ

3.2

Spectral Graph Theory

Graph Laplacian Matrix. Consider a non-negative weighted graph G. Let AG ∈ Rn × Rn be the symmetric adjacency matrix of G. That is, AG [u, v] = AG [v, u] = wuv , where u, v ∈ V are vertices, and wu,v is the weight of edge uv. (If u is not adjacent with v, then wuv = 0.) For vertex v ∈ V, denote by dv the (weighted) degree of v, namely dv = ∑u̸=v wvu . Let DG ∈ Rn × Rn be a diagonal matrix where DG [i, i ] is the degree of i ∈ [n]. Here, we define the edge adjacency matrix: Definition 14 (Edge adjacency matrix). Let G be an undirected graph of n vertices and m edges. Consider an arbitrary orientation of edges, then EG ∈ Rm×n is the edge adjacency matrix where  √   + √we , if v is e’s head, if v is e’s tail, EG [e, v] = − we ,   0, otherwize. An important object of interest in graph theory is the Laplacian of a graph: Definition 15 (Laplacian matrix). For an undirected graph G with n vertices and m edges, the Laplacian matrix LG ∈ Rn×n of G is ⊤ L G = EG EG . Equivalently, one can verify that LG = DG − AG . Also, we note that for any graph G, LG is a positive semi-definite (PSD) matrix and LG 1 = 0, where 1 ∈ Rn is the all one vector. For any vector x in Rn , the quadratic form of LG is x ⊤ LG x ≥ 0. In particular, one can verify that x⊤ LG x =

∑ wu,v (x(u) − x(v))2 .

(u,v)∈ E

14

Demand Sparsity and Expander Graphs. To analyze the private expander decomposition, we use the generalized version of the standard cardinality-based sparsity to a demand-aware setting. Given a graph G = (V, E) and a demand vector ρ : V → R≥1 , we extend the demand to any subset S ⊆ V as ρ(S) = ∑v∈S ρ(v). Fix an U ⊆ V. The demand sparsity of a cut (S, U \ S) in an induced subgraph G [U ] is defined as: G [U ]

ϕρ

(S) =

wG[U ] (S, U \ S) . min{ρ(S), ρ(U \ S)} G [U ]

We say G [U ] is a (ψ, ρ)-expander if for all ∅ ̸= S ⊊ U, ϕρ

3.3

(6)

(S) ≥ ψ.

Useful Tools in Probability and Matrix

Lemma 16 (Properties and Tail Bounds of the χ21 Distribution, [Ver18]). Let Z ∼ N (0, 1) be a standard Gaussian random variable. Its square X = Z2 follows a chi-squared distribution with one degree of freedom, denoted as X ∼ χ21 . The following properties hold: 1. Moments: E[ X ] = 1 and E[ X 2 ] = 3. 2. Sub-exponential Tail: There exist absolute constants C, c > 0 such that for any s ≥ 0, Pr[ X > s] ≤ Ce−cs . Lemma 17 (Matrix Gaussian Series Inequality, [Tro12]). Let A1 , . . . , Ak ∈ Rn×n be deterministic symmetric matrices, and let g1 , . . . , gk ∼ N (0, 1) be independent standard Gaussian random variables. Consider the random symmetric matrix Z = ∑ik=1 gi Ai . Define the matrix variance proxy parameter v as: k

v=

∑ A2i

.

i =1

2

Then, for any failure probability β ∈ (0, 1), with probability at least 1 − β, the spectral norm of Z satisfies the tail bound: q ∥ Z ∥2 ≤ 2v log(2n/β). Lemma 18 (Hadamard’s Inequality, [HJ12]). Let X ∈ Rn×n be a symmetric positive semi-definite matrix. Then the determinant of X is upper-bounded by the product of its diagonal entries: n

det( X ) ≤ ∏ Xii .

(7)

i =1

Equality holds if and only if X is a diagonal matrix, or if any diagonal entry Xii = 0. To bound the retained rank of our spectral truncation, we recall on the following variational characterization of eigenvalues. Theorem 19 (Ky Fan’s Maximum Principle, Corollary 4.3.39 in [HJ12]). Let A ∈ Rn×n be a symmetric matrix with eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn . For any integer 1 ≤ k ≤ n, the sum of the top k eigenvalues satisfies: k

tr(U T AU ). ∑ λi = U∈R max × ,U U = I

i =1

n k

T

15

k

Consequently, for any positive semi-definite (PSD) matrix A ⪰ 0 and any set of k orthonormal vectors {u1 , . . . , uk }, we have: k

k

i =1

i =1

∑ uiT Aui ≤ ∑ λi ≤ tr( A).

Furthermore, to explicitly characterize the noise magnitude in the matrix mechanism, we recall the standard non-asymptotic bound for the spectral norm of symmetric Gaussian matrices. Lemma 20 (Spectral Norm of Symmetric Gaussian Matrices, Theorem 4.4.5 in [Ver18]). Let W ∈ Rn×n be a symmetric random matrix where the upper triangular entries (including diagonal entries) are sampled i.i.d. from N (0, σ2 ). Then, for any failure probability β ∈ (0, 1), there exists an absolute constant C > 0 such that with probability at least 1 − β, the operator norm of W satisfies:   q √ n + log(1/β) . ∥W ∥2 ≤ Cσ Our vertex splitting gadget heavily relies on pseudo-random routing. To formally analyze this without compromising the deterministic bounds required by differential privacy, we define the following hash function family and introduce concentration inequalities. Definition 21 (Public Hash Functions). Let H be a family of hash functions uniform at randomly mapping a universe U to a set of k bins. For each vertex v ∈ V, we publicly sample a fresh hash function hv : V \ {v} → [ρ(v)] from a family of fully independent hash functions. Crucially, these hash functions are generated using public randomness and strictly do not consume any privacy budget. Next we introduce the standard Chernoff bounds. Lemma 22 (Chernoff Bound [Che52]). Let X1 , . . . , Xm be independent Bernoulli random variables (Poisson trials) such that Pr[ Xi = 1] = pi . Let X = ∑im=1 Xi and denote its expectation by µ = EX. Then, for any δ > 0:  µ eδ Pr[ X ≥ (1 + δ)µ] ≤ . (1 + δ )1+ δ For δ ≥ 1, this bound simplifies to Pr[ X ≥ (1 + δ)µ] ≤ exp(− 3 ). δµ

The following direct corollary of Lemma 22 is useful for analyzing our stable port gadget: Corollary 23 (Balls-into-Bins Concentration). Suppose m balls are independently distributed into k bins using a random hash function h ∈ H. If the expected load of a specific bin is µ = m/k ≥ 1, then by applying Lemma 22, the maximum load across all k bins is bounded by O(µ + log(k/β)) with probability at least 1 − β.

4

Power-based Spectral Amplifier for Private Matrix Release

Our improvements in private graph analysis start from a new technique for the private estimation of general symmetric matrices, which we refer to as the power-based spectral amplifier. While our primary motivation is to deploy this tool for private spectral and cut approximation (in Section 5), we present its privacy and utility analyses in full generality as they may be of independent interest. In particular, we show the following generic theorem for private matrix release:

16

Theorem 24 (Power-based Spectral Amplifier; Combination of Theorem 25 and Theorem 26). Fix privacy parameters 0 < ε, δ < 1 and an integer n ∈ N+ . Let M( D ) ∈ Rn×n be a symmetric matrix evaluated on a dataset D. For any integer k ≥ 1, we define the k-th Frobenius sensitivity over neighboring datasets D ∼ D ′ as ∆k = maxD∼ D′ ∥ M ( D )k − M ( D ′ )k ∥ F . For any even integer q ≥ 2, there exists an efficient (ε, δ)-differentially private algorithm such that for any input matrix M ( D ) satisfying tr( M( D )q ) ≤ b satisfying, with high probability: Bq , it outputs a synthetic matrix M   s √ !1/q ∆q n Bq ε ∆ e b ≤O √ . M( D) − M + 1 (8) ε ε 2 ∆q n As illustrated in Section 2.1, the core idea of the spectral amplifier is: utilizing a non-linear matrix mapping Φq ( M ) = Mq (q ≥ 2) to amplify the true signal, specifically the spectral gap. This amplification ensures that the true data features contained in the subspace can still be truncated and extracted with high probability after adding privacy noise. Consequently, this approach restricts subsequent queries to this private, low-dimensional subspace, thereby achieving an error bound much smaller than that incurred by naive additive noise mechanisms that add noise directly into the original n-dimensional space.

4.1

Definitions and Algorithm

Given a dataset D, our goal is to privately release a symmetric real matrix M ( D ) ∈ Rn×n . For simplicity, we drop the dependency on D and write M when the context is clear. We denote D ∼ D ′ to indicate that D and D ′ are neighboring datasets. • Power Amplifier: For any symmetric matrix M with eigen-decomposition M = ∑i∈[n] λi vi vi⊤ , q we define the amplifying operator as Φq ( M ) = Mq = ∑i∈[n] λi vi vi⊤ for any even integer q ≥ 2. Because q is even, the amplified matrix Mq is positive semi-definite (i.e., Mq ⪰ 0), regardless of whether M contains negative eigenvalues.2 • Sensitivity Bounds: The mechanism design relies on the ℓ2 -sensitivities (for vectorized matrix, which is equivalent to Frobenius norm) in both the original and the powered spaces: – Original Frobenius sensitivity: ∆ M = ∆1 = maxD∼ D′ ∥ M ( D ) − M( D ′ )∥ F – Amplified Frobenius sensitivity: ∆q = maxD∼ D′ ∥ M ( D )q − M ( D ′ )q ∥ F • Trace Bound: We assume there exists an (pure analytical) upper bound Bq such that for all valid datasets, the trace of the amplified matrix is bounded: tr( Mq ) ≤ Bq .3 With these parameters, the Power-based Spectral Amplifier Framework proceeds in Algorithm 1.

4.2

Privacy Guarantee

Theorem 25. The Power-based Spectral Amplifier (Algorithm 1) is (ε, δ)-differentially private. 2 For example, graph adjacency matrices A has both positive and negative eigenvalues. 3 Importantly, this bound B is a structural property used solely in our utility analysis to bound the retained rank; it q

does not need to be public or provided as an input parameter to the privacy mechanism.

17

Algorithm 1: Power-based Spectral Amplifier Input: A dataset D with target symmetric matrix M ( D ) ∈ Rn×n , privacy parameters ε, δ ∈ (0, 1), failure probability β = 1/nc , and an even integer q ≥ 2. b Output: A synthetic matrix M. 1: Split the privacy budget such that ε 1 = ε 2 = ε/2 and δ1 = δ2 = δ/2; similarly allocate the failure probability β 1 = β 2 = β/2; Step 1: Amplified Spectral Release: 2: Compute the amplified matrix Y = M q . 3: Sample a symmetric Gaussian noise matrix W ∈ Rn×n by drawing its upper-triangular entries √ 2 log(1.25/δ )

1 i.i.d. from N (0, σ12 ) and setting Wj,i = Wi,j for i > j, with noise scale σ1 = ∆q . ε1 e 4: Construct the noisy amplified matrix Y = Y + W. Step 2: Spectral Truncation: p √ 5: Let the truncation threshold be η = Cσ1 ( n + log(1/β 1 )), such that by Lemma 20, ∥W ∥2 ≤ η holds with probability at least 1 − β 1 . ⊤ ⊤ e = ∑n e 6: Compute the spectral decomposition Y i =1 λi ui ui . Let P = ∑ j: e λ j >2η u j u j be the orthogonal projector onto the eigenspace associated with eigenvalues greater than 2η. 7: Extract an orthonormal basis U ∈ Rn×r for range( P ), where r = rank( P ). Step 3: Exact Release: 8: Project the original matrix into the low-dimensional subspace: C = U ⊤ MU. 9: Sample a symmetric Gaussian noise matrix E ∈ Rr ×r by drawing its upper-triangular entries √

i.i.d. from N (0, σ22 ) and setting Ej,i = Ei,j for i > j, with noise scale σ2 = ∆ M e = C + E. 10: Construct the noisy compressed matrix C ⊤ e b 11: return M = U CU .

2 log(1.25/δ2 ) . ε2

Proof. The algorithm interacts with the private dataset D through two sequential queries, and we bound the total privacy leakage via basic composition (Lemma 7). e = Mq + W. Since Y e is symmetric, In Step 1, the algorithm releases the symmetric matrix Y its output space is uniquely determined by its n(n + 1)/2 upper-triangular entries (including the diagonal). The ℓ2 sensitivity of these elements is indeed bounded by the Frobenius sensitivity of the full matrix Mq : s  

∑

1≤ i ≤ j ≤ n

q

q

Mi,j − ( M′ )i,j

2

≤ M q − ( M ′ )q F ≤ ∆q .

2 Thus, by the Gaussian p mechanism (Lemma 13), adding independent Gaussian noise N (0, σ1 ) calibrated to σ1 = ∆q 2 log(1.25/δ1 )/ε 1 to the upper-triangular entries (and mirroring them to the lower triangle) guarantees (ε 1 , δ1 )-differential privacy. In Step 2, the algorithm extracts the projection matrix P and its orthogonal basis U as a funce By the post-processing property of differential privacy tion solely of the privatized matrix Y. (Lemma 6), this step does not consume additional privacy budget. In Step 3, the algorithm performs a secondary query on the original dataset, releasing the matrix C = U ⊤ MU confined within the fixed public subspace spanned by U. To bound the ℓ2 sensitivity of this linear query, consider any two neighboring datasets yielding symmetric matrices M and M′ . The difference in the query output is U ⊤ ( M − M′ )U. Using the cyclic property of the trace

18

and the identity UU ⊤ = P, the Frobenius norm of the difference is bounded by: U ⊤ MU − U ⊤ M′ U

2

2

= U ⊤ ( M − M ′ )U F F   ⊤ ′ ⊤ = tr U ( M − M ) UU ⊤ ( M − M′ )U   = tr ( M − M′ ) P( M − M′ ) P .

Since P is an orthogonal projection matrix, its eigenvalues are exactly 0 or 1, establishing P ⪯ I. 2 Consequently, the trace is bounded by tr(( M − M′ )2 ) = ∥ M − M′ ∥ F ≤ ∆2M . Thus, the Frobenius sensitivity of U ⊤ MU remains bounded by ∆ M . Analogous to Step 1, since C = U ⊤ MU is also symmetric, we only need to release its uppertriangular entries. Their ℓ2 sensitivity is bounded by ∥C − C ′ ∥ F ≤ ∆ M . Adding independent Gaus2 sian noise N (0, pσ2 ) to these entries (and mirroring them to construct the symmetric matrix E) with scale σ2 = ∆ M 2 log(1.25/δ2 )/ε 2 guarantees (ε 2 , δ2 )-DP for this final query. Finally, by the adaptive composition theorem (Lemma 7), the overall algorithm satisfies (ε 1 + ε 2 , δ1 + δ2 )-DP, which concludes the proof.

4.3

Utility Analysis

Theorem 26 (Spectral Error Bound). Let q ≥ 2 be an even integer. Algorithm 1 generates a synthetic b such that with probability at least 1 − 1/nc : matrix M   s √ !1/q B ε ∆q n ∆ q eδ  b ≤O √ . (9) + M M−M ε ε 2 ∆q n e T . By substituting the definition b = U CU Proof. Recall that the reconstructed matrix is given by M T e = U MU + E, we have: of the noisy matrix C b = U (U T MU + E)U T = UU T MUU T + UEU T . M Notice that U ∈ Rn×r consists of orthonormal column vectors spanning the range of P, meaning b = PMP + UEU T . We decompose the total UU T = P and U T U = Ir . Substituting this yields M estimation error using the triangle inequality: b M−M

2

≤ ∥ M − PMP∥2 + UEU T . | {z } | {z }2 Truncation Bias

Subspace Noise

Because U has orthonormal columns, for any vector x, UEU T x 2 ≤ ∥ E∥2 ∥ x ∥2 . Hence, the subspace noise is at most ∥ E∥2 . First, we bound the truncation bias. Condition on the high-probability event E1 that ∥W ∥2 ≤ η, which occurs with probability at least 1 − β 1 (Lemma 20). For any unit vector x ⊥ range( P), its e satisfies x T Yx e ≤ 2η. Since Y e = Mq + W and ∥W ∥ ≤ η, the Rayleigh Rayleigh quotient on Y 2 quotient on the true amplified matrix is bounded by: e − x T Wx ≤ 2η + η = 3η, where x ⊥ range( P). x T Mq x = x T Yx To bound the spectral norm of M in the orthogonal complement P⊥ , we evaluate ∥ Mx ∥22 = x T M2 x. Let M = ∑in=1 λi vi viT be the eigendecomposition of M. We have x T M2 x = ∑in=1 λ2i (viT x )2 . Because 19

q ≥ 2, the mapping f (z) = z2/q is a concave function for z ≥ 0. Writing λ2i = (|λi |q )2/q , and noting that ∑in=1 (viT x )2 = ∥ x ∥22 = 1, we apply Jensen’s inequality:

∥ Mx ∥22 =

n

∑ (|λi | )

q 2/q

(viT x )2 ≤

i =1

n

∑

!2/q q

|λi | (viT x )2

i =1

 2/q = x T Mq x ≤ (3η )2/q . Taking the square root yields ∥ Mx ∥2 ≤ (3η )1/q for any unit vector x ⊥ range( P). To bound the matrix operator norm ∥ M ( I − P)∥2 , we note that:

∥ M( I − P)∥2 =

sup y ∈ Rn , ∥ y ∥ 2 = 1

∥ M ( I − P ) y ∥2 .

(10)

For any arbitrary unit vector y ∈ Rn , let z = ( I − P)y. Since I − P is a projector orthogonal to P, then z ⊥ range( P) and that ∥z∥2 ≤ ∥y∥2 = 1. If z = 0, the bound holds trivially. Otherwise, we can normalize it into a valid unit vector b z = z/ ∥z∥2 ⊥ range( P), then: z∥2 ≤ 1 · (3η )1/q = (3η )1/q . ∥ M( I − P)y∥2 = ∥ Mz∥2 = ∥z∥2 ∥ Mb Taking this back to eq. (10) yields ∥ M ( I − P)∥2 ≤ (3η )1/q . We then decompose the residual matrix:

∥ M − PMP∥2 ≤ ∥ M( I − P)∥2 + ∥ PM( I − P)∥2 ≤ 2 ∥ M( I − P)∥2 ≤ 2(3η )1/q . Next, we bound the variance inside the subspace. Still conditioning on E1 , let {u1 , . . . , ur } be the e i − u T Wui > 2η − η = η. orthonormal basis forming P. For each basis vector, uiT Mq ui = uiT Yu i Summing this over all r dimensions yields rη < ∑ri=1 uiT Mq ui . By Ky Fan’s Maximum Principle (Theorem 19), because Mq ⪰ 0, this sum is bounded by the total trace Bq : r

rη < ∑ uiT Mq ui ≤ tr( Mq ) ≤ Bq =⇒ r ≤ i =1

Bq . η

Conditioning on a second event E2 that the spectral norm of the Gaussian noise E ∈ Rr×r follows the concentration bound (Lemma 20): s !   q √ Bq ∆ M eδ , ∥ E∥2 ≤ Oδ σ2 r + σ2 log(1/β 2 ) = O ε2 η where we let β 2 = 1/nc . By a union bound, events E1 and E2 hold simultaneously with probability at least 1 − β. Summing the truncation bias and the subspace noise, the overall error is: s ! Bq ∆ e δ η 1/q + M b ≤O . M−M ε η 2  √  √ e δ (σ1 n) = O e δ ∆q n yields the desired bound eq. (9), concluding the proof. Substituting η = O ε

20

Remark 27 (The Square Amplifier Special Case and Column-Sparse Matrices). We note that the square amplifier (q = 2) presents an easy-to-use form of error. In particular, substituting q = 2 directly into Theorem 26 yields: s  s √ 2 ∥ M ∥2 ∆ M e δ  ∆2 n + b ≤O √ F M−M (11) ε 2 ε∆2 n This bounds the error by a function of the trace of the squared matrix (tr( M2 ) = ∥ M∥2F ) and its squared sensitivity ∆2 = M′2 − M2 F . Crucially, we can bridge these quantities with the matrix’s maximum column ℓ2 -norm, denoted as R = maxu∈[n] ∥ Meu ∥2 = ∥ M ∥1→2 4 . Furthermore, for any update H supported on at most O(1) entries with with ∥ H ∥ F = O(1), the squared sensitivity expands to ( M + H )2 − M2 F ≈ ∥ MH + HM∥ F ≤ O( R). Meanwhile, the trace bound is inherently tr( M2 ) = ∥ M∥2F = ∑ ∥ Meu ∥22 ≤ nR2 . u

Thus substituting ∆2 = O( R) and ∥ M ∥2F = nR2 into eq. (11) gives the spectral error on private matrix estimation: ! r r ! R ∥ M ∥ 1 → 2 e δ n1/4 e δ n1/4 b ≤O =O . (12) M−M ε ε 2 This new error bound highlights two powerful implications: 1. Column-Sparse Matrices: It provides an out-of-the-box private release mechanism for various of sparse symmetric matrices (such as event-level co-occurrence or item-similarity matrices commonly used in NLP [PSM14, WHX+ 25, HH+ 26] or recommendation √ systems [LSY03]), e δ ( n/ε) error accordoutperforming the Gaussian mechanism (Lemma 13, which incurs O ing to Lemma 20) in sparse regimes. 2. Graph Laplacian Approximation: More importantly, as we will detail in Section 5, using this e ε,δ ((nd)1/4 ) error in approxerror bound as an important building block, we will drive an O imating the Laplacian matrices of n-vertex graphs with bounded degree d, being the first to √ e δ ( n/ε)} worst-case baseline [BBDS12, UUA21]. bypass the longstanding min{2d, O The remainder of this paper focuses on graph spectral and cut approximations with privacy. While we believe that our generic spectral amplifier framework (Algorithm 1) has the potential to facilitate more general private matrix analysis and is of independent interest, we do not find it necessary to discuss more extensions specifically in this paper.

5

Differentially Private Graph Laplacian Analysis

Let G = ([n], E) be a simple undirected graph with maximum degree at most d. Let A ∈ {0, 1}n×n be the adjacency matrix of G = ([n], E), where ( 1 if (i, j) ∈ E, Aij = . 0 otherwise. 4 For any matrix A ∈ Rn×n and integer p, q ≥ 1, ∥ A ∥

∥Ax∥q p→q = max ∥x∥ p .

21

We define graph Laplacian matrix as LG := diag( A1) − A. Throughout this paper we adopt the well-established edge-level differential privacy in private graph analysis [DMNS06, GLM+ 10, BBDS12, EKKL20, LUZ24, ZFD+ 25, ACD+ 25, CDFZ26, ZEFD26], in which two graphs are adjacent if they differ by at most one undirected edge. Many advanced graph analysis tasks such as computing effective resistances [LUZ24], expander decomposition or answering cut queries (Section 7) rely inherently on the graph Laplacian matrix. In this section, we apply the power-based spectral amplifiers developed in Section 4 to privately approximate the graph Laplacian. To capture different structural requirements in downstream applications, we develop two distinct spectral primitives: Our Private Spectral Primitives • Primitive I: The Square Amplifier (Section 5.1). By utilizing the M2 amplifier, we e ((nd)1/4 ). This byprovide a private Laplacian estimator with an additive error of O √ e passes the trivial worst-case baseline min{2d, O( n/ε)} for unweighted graphs. • Primitive II: The Bootstrapped Fourth-Power Amplifier (Section 5.2). By applying an iterated cubic-walk preprocessing (bootstrap) followed by the M4 amplifier, we derive an alternative error bound. Specifically, for a tunable parameter q, with high probability, the primitive guarantees an additive error of:   d 1/8 1/2 1/8 1/4 1/4 e LG − LGe 2 ≤ Oε,δ √ + n d q + n q . (13) q While not universally beating the square amplifier, this specific error structure is essential for triggering the recursive expander decomposition procedure to finally get e (n13/12+o(1) ) error on private cut approximation(Section 7). the O At a high level, the standard approach of adding√independent Gaussian noise directly into the e δ ( n/ε) [UUA21]. To do better, our algorithm Laplacian matrix incurs an worst-case error of O follows the three steps for both primitives: 1. Adjacency Estimation: We first estimate the unweighted graph adjacency matrix A using the power-based amplifier Φq ( A) = Aq (incorporating the iterated cubic-walk preprocessing when q = 4). 2. Degree Estimation: We independently approximate the graph’s degree sequence using the standard Laplace mechanism, which has an O(1) ℓ1 -sensitivity under edge-level DP. 3. SDP Projection: Simply combining the noisy adjacency matrix and noisy degrees yields an intermediate matrix e L that is typically not a valid graph Laplacian (e.g., possessing positive off-diagonal entries or non-zero row sums). This breaks the structural requirements for downstream spectral algorithms. To resolve this, we adopt the semidefinite programming (SDP) projection technique formulated by Upadhyay et al. [UUA21], projecting e L back onto the convex cone of valid non-negative weighted graph Laplacians.

22

5.1

Graph Laplacian Estimation via Square Amplifier

Let G = ([n], E) be a simple unweighted graph with maximum degree bounded by d. In this e ((nd)1/4 ) section we will formalize the application of the square amplifier (q = 2) to achieve the O spectral approximation. First, we explicitly bound the amplified parameters ∆2 and B2 for the e δ (·) factors hide unweighted graph adjacency matrix under edge-level differential privacy. All O polylogarithmic factors in n, 1/δ, and log d, but not polynomial factors in 1/ε. ′ Lemma 28 (Square Sensitivity for Unweighted Graphs). Given two neighboring graphs √ G ∼ G , let ′ A and A be their respective adjacency matrices. Then √ the original sensitivity is ∆ A = 2, the squared ′ 2 2 Frobenius sensitivity satisfies ∆2 = A − A F ≤ O( d), and the trace bound is B2 = tr( A2 ) ≤ nd.

Proof. Let A′ = A + H, where the update corresponding to√a single edge between vertices √ u and v ⊤ ⊤ is H = s(eu ev + ev eu ) for s ∈ {−1, +1}. Clearly, ∥ H ∥ F = 2 = O(1), establishing ∆ M = 2. For the squared sensitivity, we have: A′2 − A2 = ( A + H )2 − A2 = AH + H A + H 2 . Because A is the adjacency matrix of qa graph with√maximum degree d, its local column ℓ2 -norm is bounded by the degree: ∥ Aeu ∥2 = ∑in=1 A2iu ≤ d. Consequently,

∥ AH ∥ F = A(seu ev⊤ + sev eu⊤ )

F

√ ≤ ∥ Aeu ∥2 ∥ev ∥2 + ∥ Aev ∥2 ∥eu ∥2 ≤ 2 d.

√ √ By symmetry, ∥ H A∥ F ≤ 2 d. Furthermore, H 2 = eu eu⊤ + ev ev⊤ , meaning H 2 F = 2. Applying the triangle inequality, we bound the squared sensitivity as follows: √ √ √ ∆2 ≤ ∥ AH ∥ F + ∥ H A∥ F + H 2 F ≤ 4 d + 2 = O( d). Finally, since the trace of A2 is exactly the sum of vertex degrees: n

B2 = tr( A2 ) = ∥ A∥2F = ∑ deg(u) ≤ nd. u =1

To enforce that our final output is a valid graph Laplacian, we define Ln as the convex set of all valid Laplacians of non-negative weighted graphs on n vertices: n o Ln = X ∈ Rn×n | X = X ⊤ , Xij ≤ 0 for i ̸= j, X1 = 0 . We combine the square amplifier with the SDP projection in Algorithm 2. Theorem 29 (Private Laplacian Estimation via A2 ). For any ε, δ ∈ (0, 1) and maximum degree d ≥ 1, Algorithm 2 is (ε, δ)-differentially private. Moreover, for any input graph G, it outputs a non-negative weighted graph Laplacian b L such that with probability at least 1 − 1/nc :  LG − b L

2

eδ ≤O

23

 (nd)1/4 1 √ + . ε ε

Algorithm 2: Private Graph Laplacian Oracle (Square Amplifier) Input: Graph G = ([n], E) with maximum degree d, privacy parameters ε, δ ∈ (0, 1). Output: The non-negative weighted graph Laplacian b L ∈ Ln . Adjacency Estimation: 1: Execute the Power-based Spectral Amplifier Framework (Algorithm 1) on A with q = 2, √ √ privacy parameters (ε/2, δ), sensitivity bounds ∆ A = 2, ∆2 = Θ( d), and B2 = nd. Let the b output be A. Degree Estimation: 2: Compute the true degree vector D1 = (d1 , . . . , dn )⊤ . 3: for each i ∈ [n ] do 4: Sample independent Laplace noise Zi ∼ Lap(4/ε). 5: Compute noisy degree dbi = di + Zi . 6: end for b = diag(db1 , . . . , dbn ). 7: Let D Intermediate Matrix: b b − A. 8: Construct the intermediate pseudo-Laplacian e L=D SDP Projection: 9: Solve the following semidefinite program to find the optimal valid projection b L: min

X ∈Ln , γ ∈R

γ

subject to

− γIn ⪯ e L − X ⪯ γIn

10: return b L.

Proof. We first see the privacy guarantee. We partition the budget: In line 1, running the Square Amplifier requires (ε/2, δ)-DP by Theorem 25. In line 5, we estimate the degree sequence. Adding or removing a single edge alters two vertex degrees by at most 1, so the global ℓ1 -sensitivity of the degree vector is 2. Applying the Laplace mechanism (Lemma 12) with scale 2/(ε/2) = 4/ε b and D b satisfies (ε, δ)-DP by the basic comguarantees (ε/2, 0)-DP. Therefore, the joint release of A position theorem (Lemma 7). The SDP projection in Step 9 operates exclusively on the privatized matrix e L without accessing the underlying graph topology, consuming zero additional privacy budget due to post-processing (Lemma 6). Thus, the algorithm is overall (ε, δ)-DP. For the utility bound, we first compute the spectral distance of the intermediate matrix e L. By the triangle inequality: e L − LG

2

b) − ( D − A) b−A = (D

2

b−D ≤ D

2

b + A−A

2

.

(14)

Applying Theorem √ 26 (specifically √the q = 2 form in eq. (11)) and substituting the parameters from Lemma 28 (∆ A = 2, ∆2 = Θ( d), B2 = nd) evaluated under budget ε/2, the approximation error on adjacency matrix is: s √  s √   d n 1 ndε  (nd)1/4 b e e  √ √ A − A ≤ Oδ = Oδ + . √ ε ε 2 ε d n

= maxi∈[n] | Zi |. By the tail bounds of the Laplace distribution (Lemma 10) and a union bound over n variables, with For the degree matrix, the error is only contained on the diagonal:

24

b−D D

2

high probability:  b−D D

2

≤O

log n ε

 .

Substituting both bounds into eq. (14):  e L − LG

2

b− A ≤ A

2

b−D + D

2

eδ =O

 (nd)1/4 1 √ . + ε ε

Finally, we analyze the SDP projection. The constraint −γIn ⪯ e L − X ⪯ γIn is identical to e L − X ≤ γ. The SDP computes the operator-norm projection onto Ln : 2

b L = arg min e L−X X ∈Ln

2

.

Because the true unweighted graph Laplacian inherently satisfies LG ∈ Ln , the optimality of b L b e e dictates that L − L ≤ LG − L . Applying the triangle inequality yields the final spectral 2 2 error:   (nd)1/4 1 e b e e b e √ . + L G − L ≤ L G − L + L − L ≤ 2 L G − L ≤ Oδ ε 2 2 2 2 ε e δ notation, completing the proof. The constant factor is absorbed by the O

5.2

A Bootstrapped Fourth-Power Spectral Primitive

In this section, we refine the algorithm for private graph Laplacian estimation beyond the direct square amplifier, deriving an alternative spectral error bound. In particular, we show that there is a polynomial-time, (ε, δ)-DP algorithm that, for any bounded-degree graph, outputs a valid nonnegative weighted synthetic graph whose Laplacian satisfies the error interface stated in eq. (13). e ε,δ ((nd)1/4 ) across all parameter regimes, Although this error bound does not universally beat O we will demonstrate in Section 7 that its dependence on d and q makes it useful for driving the recursive expander decomposition framework. A direct application of the power-based amplifier framework (Algorithm 1) with the operator Φ4 ( A) = A4 to the original graph would not give satisfying bounds, as its Frobenius sensitivity 2 ∥ A4 − ( A′ )4 ∥ F is governed by the graph’s local two-walk column norm (maxv∈V A2 ev 2 ), which can be as large as O(d3 ) in the worst case, leading to large privacy noise. To resolve this barrier, we introduce a bootstrapped mechanism. Before applying the A4 amplifier, we utilize an iterated cubic-walk (A3 ) scoring step to privately identify and “peel off” a sparse set of edges that cause high column norms. This preprocessing step reduces the local two-walk column norms of the e δ (d2 q/ε) for some q ≤ d. After that, we apply the A4 amplifier via our residual graph down to O framework to obtain a refined spectral approximation. Again, throughout this section, G = ([n], E) is a simple undirected graph with maximum degree at most d, adjacency matrix A, and Laplacian e δ (·) factors hide polylogarithmic factors in n, 1/δ, and log d, but not LG = diag( A1) − A. All O polynomial factors in 1/ε. 5.2.1

Local Column Norm for Two-Walk

For a graph G with adjacency matrix A, we define the maximum local energy: 2

κ2 ( G ) := max A2 ev 2 = max ∑ codegG (u, v)2 , v ∈V

v ∈V u ∈V

25

(15)

where codegG (u, v) denotes the number of common neighbors between u and v in G. For every d-bounded graph and any fixed vertex v, we have

∑ codeg(u, v)2 ≤ d ∑ codeg(u, v) ≤ d ∑ deg(x) ≤ d3 . u

u

x ∈ N (v)

Thus, we inherently have κ2 ( G ) ≤ d3 . The quantity κ2 is the critical obstacle to high-power private spectral release, as it controls the sensitivity of both cubic and fourth-power queries: Lemma 30 (Sensitivity of the cubic query under a local-energy promise). Let A, A′ be adjacency matrices of neighboring graphs of maximum degree at most d. Suppose both graphs satisfy κ2 ≤ K for a given threshold K ≥ d2 . Then: √ ( A′ )3 − A3 F ≤ C K. Proof. Let A′ = A + H, where H = ±(eu ev⊤ + ev eu⊤ ). We expand the difference:

( A + H )3 − A3 = A2 H + AH A + H A2 + AH 2 + H AH + H 2 A + H 3 . The first and third terms satisfy

√ A2 H F , H A2 F ≤ 2 max A2 ev 2 ≤ 2 K. v

Moreover, since maxu∈[n] ∥ Aeu ∥2 = maxu∈[n]

p

∑nv=1 A2uv ≤

√

d, we have:

∥ AH A∥ F ≤ 2 ∥ Aeu ∥2 ∥ Aev ∥2 ≤ 2d. By our premise K ≥ d2 , the remaining terms√involve at least two factors of H and√have Frobenius √ norm O( d + 1), which is dominated by O( K ). Therefore, ( A′ )3 − A3 F ≤ C K. Lemma 31 (Sensitivity of the fourth-power query under a local-energy promise). Let A, A′ be adjacency matrices of neighboring graphs of maximum degree at most d. Suppose both graphs satisfy κ2 ≤ K for a given threshold K ≥ d2 . Then:

( A ′ )4 − A4

F

√ ≤ Cd K.

Proof. Let A′ = A + H, where H = ±(eu ev⊤ + ev eu⊤ ). We expand ( A + H )4 − A4 binomially. We categorize the terms into those containing exactly one H (one-H terms) and those containing multiple (multi-H terms). The one-H terms take the form Ai H A3−i for i ∈ {0, 1, 2, 3}. Using the facts that A2 ev 2 ≤ √ √ √ κ2 ≤ K, ∥ Aev ∥2 ≤ d, and ∥ A∥2 ≤ d, we bound them as follows: √ A2 H A F ≤ A2 eu 2 ∥ Aev ∥2 + A2 ev 2 ∥ Aeu ∥2 ≤ 2 Kd,

√ A3 H F ≤ A3 eu 2 ∥ev ∥2 + A3 ev 2 ∥eu ∥2 ≤ ( A2 eu 2 + A2 ev 2 ) ∥ A∥2 ≤ 2d K. √ By symmetry, H A3 F and AH A2 F are similarly bounded by 2d K. Furthermore, the Frobenius √ norm of all multi-H terms is at most O(d2 ) ≤ O(d K ) because K ≥ d2 . Summing these bounded terms completes the proof.

26

5.2.2

The Improved Private Spectral Primitive

We now assemble the components to prove the following formal theorem corresponding to the error interface in eq. (13). Theorem 32 (Improved Bounded-Degree Private Spectral Release). For any ε, δ ∈ (0, 1), n-vertex input graph G with maximum degree d ≥ 1, and target parameter q ≥ polylog(n, 1/δ)/ε, there is a b with Laplacian L b such polynomial-time (ε, δ)-DP algorithm that outputs a non-negative weighted graph G G c that with probability at least 1 − 1/n :   d n1/4 q1/4 1 n1/8 d1/2 q1/8 e LG − LGb 2 ≤ Oδ √ + + + . εq ε ε3/8 ε3/4 Iterated Cubic-Score Cover. We use a cubic-walk strategy (Algorithm 3) to decompose G into a covered part P and a residual graph R with low local column norms for two-walks. P is a private set of vertex pairs identified via noisy cubic-walk scores. The cover routine repeatedly releases these √ 3 scores: if the current residual satisfies κ2 ≤ Ki , then A has sensitivity O( Ki ). Thresholding the noisy ( A3 )uv values successfully isolates the heavy pairs. In Algorithm 3, we also use a proposetest-release subroutine to explicitly test whether κ2 ≤ Ki to safely calibrate noise according to Ki . Lemma 33 (The Iterated Cover). Assume q ≥ polylog(d)/ε and d ≥ 1. IteratedCubicScoreCover is (ε, δ)-DP for any input graph G. Furthermore, with probability at least 1 − 1/nc , it outputs P ⊆ (n2 )  2 2 e δ εd and κ2 ( R) ≤ O e δ ( d q ). Here R = ([n], E( G ) \ ( E( G ) ∩ P)) without aborting, satisfying ∆( P) ≤ O q

ε

is the remaining graph and ∆( P) is the maximum degree of the edge support P. Proof. Privacy Guarantee. The algorithm runs for at most S = O(log log d) iterations. In each round i, the algorithm splits the budget into ε test and ε rel . First, we analyze the sensitivity of the true local energy κ2 ( G ) = maxv ∑u codeg(u, v)2 . Adding or removing a single edge e = { x, y} in a d-bounded graph changes the common neighborhood codeg(u, v) by at most 1, and this perturbation only occurs for pairs where {u, v} ∩ { x, y} ̸= ∅. Thus, for any fixed vertex v, the sum ∑u codeg(u, v)2 changes by at most ∑u∈ N (v) (2 codeg(u, v) + 1) ≤ 2d2 + d ≤ 3d2 . Consequently, κ2 ( G ) has an exact global sensitivity bounded by ∆κ ≤ 3d2 . By the standard Laplace mechanism (Lemma 12), releasing κ2,i + ξ i satisfies (ε test , 0)-DP. Next, we analyze the overall privacy via the propose-test-release framework. Let G, G ′ be a pair of neighboring graphs. By the principle of adaptive composition (Lemma 7), we analyze the i-th round conditioned on an arbitrary fixed transcript of previous outputs in rounds 0, · · · , i − 1. S 1 Because the set of removed edge pairs P<i = ij− =0 Pj can be fully recovered from these public outputs, it is identical for both executions between inputs G and G ′ , conditioned on any fix transcripts in the first i − 1 round. Consequently, the residual graphs Ri = G \ P<i and Ri′ = G ′ \ P<i differ by at most the single original edge separating G and G ′ . For any such pair of residual graphs, we consider three different cases based on their true local energies κ2,i ( Ri ) and κ2,i ( Ri′ ): ′ > K , the probability that the algorithm passes • Case 1 (Both Unsafe): If both κ2,i > Ki and κ2,i i the test for either graph is bounded by Pr[ξ i ≤ − Mi ] ≤ 21 exp(−ε test Mi /∆κ ) = δ′ /2. Thus, the algorithm outputs ⊥ with probability at least 1 − δ′ /2. For any set of outcomes O , we have

Pr[M( Ri ) ∈ O] = Pr[M( Ri ) ∈ O \ {⊥}] + Pr[M( Ri ) = ⊥ ∧ ⊥ ∈ O]

≤ δ′ /2 + δ′ + Pr[M( Ri′ ) = ⊥ ∧ ⊥ ∈ O] ′

≤ eε Pr[M( Ri′ ) ∈ O] + 1.5δ′ . 27

Algorithm 3: IteratedCubicScoreCover Input: Graph G = (V, E), degree bound d, target parameter q, privacy parameters (ε, δ). Output: Covered pairs P ⊆ (V2 ) or ⊥ (if safety test fails). 1: R0 ← G, P ← ∅, K0 ← 2d3 . 2: Let S ← ⌈C log log d ⌉ + 2. 3: Allocate per-round budgets: ε′ ← ε/S, δ′ ← 2δ/ (3S ). For each round, split ε′ = ε test + ε rel where ε test = ε rel = ε′ /2. 4: for i = 0, 1, . . . , S − 1 do e (d2 q/ε rel ) then 5: if Ki ≤ O 6: R ← Ri and break. 7: end if Propose-Test-Release (PTR) Check 8: Compute true local energy κ2,i = κ2 ( Ri ), and let ∆κ = 3d2 ; 9: 10: 11: 12: 13: 14: 15:

log(1/δ′ )

Let the safety margin be Mi = ∆κ ε test . Sample Laplace noise ξ i ∼ Lap(∆κ /ε test ). if κ2,i + ξ i > Ki − Mi then return ⊥ end if Private Release Let Ai be the adjacency matrix of Ri . √  Ki eδ ei = A3 + Zi , where Zi ∼ N (0, σ2 ) is Gaussian noise with σ = O Privately release B . √

i

ε rel

e δ ( Ki ) such that ∥ Zi ∥max ≤ ζ i with high probability. 16: Let ζ i = O ε rel 17: Let τi = max(2ζ i , dq/ε rel ). ei (u, v) ≥ τi }. 18: Pi ← {uv : B 19: P ← P ∪ Pi . 20: Ri+1 ← Ri \ ( E( Ri ) ∩ Pi ). 21: Ki+1 ← C1 dτi (where C1 ≥ 4 is a sufficiently large constant). 22: end for 23: return P. satisfying (ε′ , 1.5δ′ )-DP. ′ ≤ K , the true global sensitivity of the cubic query • Case 2 (Both Safe): If both κ2,i ≤ Ki and κ2,i i √ A3i is deterministically bounded by O( Ki ) due to Lemma 30. If the test fails, the algorithm outputs ⊥. If it passes, the Gaussian mechanism is calibrated to the true sensitivity, guaranteeing (ε rel , δ′ /2)-DP for the released matrix. Because the safety test itself provides (ε test , 0)DP, standard basic composition dictates that the entire procedure (including the probability of outputting ⊥) satisfies (ε test + ε rel , δ′ /2) ⊂ (ε′ , δ′ )-DP. ′ > K (unsafe). • Case 3 (Boundary): Without loss of generality, assume κ2,i ≤ Ki (safe) but κ2,i i ′ since they are neighbors, we have κ2,i ≤ κ2,i + ∆κ ≤ Ki + ∆κ . The probability that the unsafe graph Ri′ passes the test is bounded by:   1 Mi − ∆ κ δ′ ′ ′ ′ Pr[pass | Ri ] = Pr[ξ i ≤ Ki − κ2,i − Mi ] ≤ exp −ε test = eε test ≤ δ′ , 2 ∆κ 2

assuming ε test ≤ ln 2. Crucially, the probability that the safe graph Ri passes the test is iden28

tically bounded: Pr[pass | Ri ] = Pr[ξ i ≤ Ki − κ2,i − Mi ] < Pr[ξ i ≤ ∆κ − Mi ] ≤ δ′ . For any set of outcomes O , let Omat = O \ {⊥}, for the direction from Ri to Ri′ : Pr[M( Ri ) ∈ O] = Pr[M( Ri ) = ⊥] · 1⊥∈O + Pr[M( Ri ) ∈ Omat ]

≤ eε test Pr[M( Ri′ ) = ⊥] · 1⊥∈O + Pr[pass | Ri ] ′

≤ eε test Pr[M( Ri′ ) ∈ O] + δ′ ≤ eε Pr[M( Ri′ ) ∈ O] + δ′ , where the relation Pr[M( Ri ) = ⊥] ≤ eε test Pr[M( Ri′ ) = ⊥] follows from the (ε test , 0)-DP ′ property of Laplace mechanism (Lemma 12). Pr[M( Ri′ ) ∈ O] ≤ eε Pr[M( Ri ) ∈ O] + δ′ holds by identical reasoning. This proves (ε′ , δ′ )-DP on the boundary. Therefore, the single round satisfies (ε′ , 1.5δ′ )-DP for all possible inputs, without conditioning on high-probability utility events. Finally, basic composition (Lemma 7) over S rounds guarantees the overall (ε, δ)-DP. Utility Guarantee. For the utility guarantee, we condition on the high-probability event that for all rounds, the entry-wise maximum of the Gaussian noise matrix is bounded (∥ Zi ∥max ≤ ζ i ), and the safety test (lines 8-13) never aborts. By a union bound over the O(log log d) rounds and ′ all matrix entries, this joint event holds with probability at least 1 − 1/nc for δ = n−c . Consider a single cover round on the residual graph Ri with adjacency matrix Ai . If uv ∈ Pi , then ( A3i )uv ≥ τi − ζ i ≥ τi /2. For any vertex u, the row sum ∑v ( A3i )uv represents the total number of length-three walks originating from u, which is inherently at most d3 . Therefore, the maximum degree of the covered edges in this round is bounded by: ∆( Pi ) ≤ max u

2d3 d3 ∑v ( A3i )uv = . ≤ τi /2 τi minv:uv∈ Pi ( A3i )uv

(16)

Conversely, if an edge uv remains in the residual graph Ri+1 , it must be that uv ∈ / Pi , implying ( A3i )uv < 2τi . Because Ri+1 ⊆ Ri , the number of walks monotonically decreases, so ( A3i+1 )uv ≤ ( A3i )uv < 2τi . Thus, combing eq. (4), for any vertex u, the true local energy is bounded by: κ2 ( Ri+1 ) = max u

∑

( A3i+1 )uv ≤ 2dτi .

(17)

v∈ Ni+1 (u)

Notice that the algorithm explicitly defines the public threshold Ki+1 = C1 dτi with a constant C1 ≥ 4. This guarantees a safety gap Ki+1 − κ2 ( Ri+1 ) ≥ 21 Ki+1 . Since the algorithm ensures e (d2 q/ε rel ), and we assume q ≥ polylog(d)/ε, this gap is asymptotically larger than the K i +1 ≥ O e (d2 /ε test ), implying that the propose-test-release passes with required Laplace margin Mi+1 = O high probability in the next round. e (d2 q/ε rel ), the algorithm Now, we evaluate the recurrence. If the initial energy K0 = 2d3 ≤ O trivially satisfies the breaking condition at round i = 0 and immediately outputs P = ∅, naturally e (d2 q/ε rel ), satisfying all required bounds. Thus, we focus on the non-trivial regime where K0 > O which implies e (q/ε rel ) ≥ Ω(1/ε2 ), d≥Ω rel
√ e δ max( Ki /ε rel , dq/ε rel ) . meaning the base term 2dε2rel ≥ 1. By the algorithmic definition, τi = O Notice that the max operation implies a phase transition at Ki ≈ d2 q2 . In the noise-dominated regime where Ki ≥ d2 q2 , substituting the threshold into Ki+1 ← C1 dτi gives the recurrence relation 29

√ e δ d Ki /ε rel . Ignoring polylogarithmic factors, solving this exact recurrence for the base K i +1 = O case K0 = 2d3 yields −i d2 Ki = 2 (2dε2rel )2 . ε rel −i

For any d ≥ 1 and ε rel > 0, as i → ∞, the exponential term (2dε2rel )2 rapidly approaches 1. Thus, Ki converges to the fixed point d2 /ε2rel . Crucially, because we assume q ≥ polylog(d)/ε, the phasetransition target d2 q2 is larger than this fixed point d2 /ε2rel . To ensure the sequence reaches the target KT ≤ d2 q2 , it suffices to make sure that the residual factor satisfies:

(2dε2rel )2

−T

≤ (2d)2

−T

≤ 2 ≤ ε2rel q2 ,

√ which yields T = O(log log d) since our premise q ≥ polylog(d)/ε naively guarantees q ≥ 2/ε rel . e δ (d2 q2 ) for the first time, i.e., KT ≤ d2 q2 Assume that in the T-th round, KT becomes smaller than O 2 2 e δ (dq/ε rel ), thus and KT −1 > d q . At this point, the Gaussian noise bound drops below the floor O e the threshold transitions to τT = Θδ (dq/ε rel ). Then in the T + 1 round, e δ (d2 q/ε rel ). κ2 ( R T +1 ) ≤ dτT = O Therefore the algorithm successfully satisfies the breaking condition and stops after the T + 1 round. Since τi ≥ dq/ε rel for all i ≤ T + 1, substituting this into eq. (16) gives:   2 2d3 e δ ε rel d . ∆( Pi ) ≤ =O τi q Summing over T + 1 = O(log log d) rounds only alters the polylogarithmic factor. Recalling that ε rel = Θ(ε/ log log d), we conclude:  2 e δ εd . ∆( P) ≤ O q This completes the proof. Releasing the Covered Part. Proposition 34 (Gaussian Laplacian series). Let P ⊆ (V2 ) be an edge support of maximum degree at most d on n vertices, and let ξ e ∼ N (0, σ2 ) be independent Gaussian random variables. Then, with probability at least 1 − 1/nc , √ ∑ ξ e Le ≤ Oeδ (σ d). e∈ P

2

Proof. Let ge = ξ e /σ, so that ge ∼ N (0, 1) are independent standard Gaussian random variables. The target random matrix can be identically rewritten as Z = ∑e∈ P ge (σLe ). We first compute the matrix variance proxy v: v=

∑ (σLe )2

= σ2

e∈ P

∑ L2e

e∈ P

2

. 2

For any single edge e = {u, v}, its unweighted Laplacian matrix Le satisfies the identity L2e = 2Le . Substituting this identity simplifies the variance proxy to: v = 2σ2

∑ Le

e∈ P

= 2σ2 ∥ L P ∥2 , 2

30

where L P = ∑e∈ P Le is the Laplacian matrix of the subgraph induced by the edge set P. Since the edge support P is promised to have a maximum degree of at most d, it is easy to verify that ∥ L P ∥2 ≤ 2d. Therefore, the variance proxy is bounded by: v ≤ 2σ2 (2d) = 4σ2 d. Applying Lemma 17, we conclude that with probability at least 1 − 1/nc :

∑ ξ e Le

e∈ P

≤

q

√ e δ ( σ d ), 2(4σ2 d) log(2n · nc ) = O

2

which completes the proof. Lemma 35 (Covered-Part Error). Given the support P from Algorithm 3, ReleaseOnSupport is (ε, δ)DP. With probability at least 1 − 1/nc , its output satisfies:   d e b . L P − L G [ P ] ≤ Oδ √ εq 2 Proof. By the principle of adaptive composition (Lemma 7), we analyze this subroutine conditioned on an arbitrary fixed transcript of the public support P generated by Algorithm 3. For a fixed P, the query G 7→ (1[e ∈ E( G )])e∈ P has ℓ2 -sensitivity at most one under edge-level privacy. The privacy claim then follows from the Gaussian mechanism (Lemma 13). Next, we establish the spectral utility bound. The true Laplacian of the graph G restricted to the edge support P is denoted as LG[ P] = ∑e∈ P 1[e ∈ E] Le . By Algorithm 4, the spectral error matrix is: b L P − L G [ P ] = ∑ (1[ e ∈ E ] + ξ e ) L e − ∑ 1[ e ∈ E ] L e = ∑ ξ e L e . e∈ P

e∈ P

e∈ P

Since the elements ξ e ∼ N (0, σ2 ) are independent Gaussian random variables and the underlying edge support P has a maximum vertex degree of at most ∆( P), we apply Proposition 34 and with probability at least 1 − 1/nc , the operator norm of the error matrix satisfies: ! p  q  ∆ ( P ) e δ σ ∆( P) ≤ O eδ b L P − L G [ P] = ∑ ξ e Le ≤ O . ε 2 e∈ P 2

Combining the upper bound of ∆( P) in Lemma 33 completes the proof. Thresholded Fourth-Power Release of the Residual. With high probability, the residual graph e δ (d2 q/ε) according to Lemma 33. We directly invoke our Power-based R satisfies κ2 ( R) ≤ K := O Spectral Amplifier (Algorithm 1) with q = 4. Lemma 36 (Fourth-Power Residual Release). Let R be an n-vertex residual graph with maximum degree d and κ2 ( R) ≤ K. Instantiating Algorithm 1 with Φ4 ( A R ) = A4R provides an (ε, δ)-DP raw Laplacian estimate e L R satisfying, with high probability:   (nK )1/8 d1/4 (nK )1/4 1 e e L R − L R ≤ Oδ + √ + . ε 2 ε1/4 dε e δ (d2 q/ε), this simplifies to: Substituting K ≤ O  1/8 1/2 1/8  1/4 q1/4 n d q n 1 eδ . LR − e LR ≤ O + + ε 2 ε3/8 ε3/4 31

Algorithm 4: ReleaseOnSupport Input: Graph G = (V, E), pair support P ⊆ (V2 ), privacy parameters (ε, δ). Output: Noisy Laplacian b L P approximating LG[ P] . √  log(1/δ) 1: Set the Gaussian noise scale σ = Θ . ε 2: for each e ∈ P do

Set the indicator weight we = 1[e ∈ E]. Sample independent Gaussian noise ξ e ∼ N (0, σ2 ). b e = we + ξ e . 5: Compute the noisy weight w 6: end for be Le . 7: return b L P = ∑e∈ P w 3: 4:

√ Proof. By Lemma 31, the amplified sensitivity is bounded by ∆4 = O(d K ). The trace bound 2 satisfies B4 = tr( A4R ) = ∑v∈V A2R ev 2 ≤ nK. Applying the general bound for power amplifiers (eq. (9)) evaluated at q = 4 directly yields:  √  s √ !1/4   1/8 1/8 1/4 1 nKε n1/4 K1/4 bR ≤ O eδ  d K n eδ n K d √ √ =O √ AR − A . + + ε ε d K n 2 ε1/4 dε Finally, as in the analysis of Theorem 29, estimating the residual degree vector using the Laplace e δ (1/ε) to the diagonal. Summing mechanism with ℓ1 -sensitivity O(1) independently contributes O these errors yields the stated bound. Assembling the Final Oracle. Finally, to guarantee a valid graph Laplacian on non-negative edge graphs, in Algorithm 5 we integrate the SDP projection exactly as in Section 5.1. Proof of Theorem 32. The privacy of the algorithm follows universally from basic composition and the propose-test-release framework. Crucially, the algorithm employs explicit safety checks (lines 3-5 and lines 9-13) to ensure that the sensitivity bound is satisfied throughout the subsequent subroutines. Note that in the the testing phase (lines 9-13), the only event that consumes the approximate DP budget δ is when a residual graph R with true local energy κ2 ( R) > Kfinal accidentally log(6/δ) passes the test. By setting the safety margin to Mfinal = 3d2 ε test and applying the Laplace tail bound (Lemma 10), the probability of such an unsafe graph passing the test is bounded by δ/6. Therefore, with all √ but δ/6 probability, any graph that proceeds to line 14 satisfies the 4th-power sensitivity bound O(d Kfinal ), guaranteeing that the subsequent spectral amplifier (Algorithm 1) provides (ε amp , δ/6)-DP. Combining the budgets used in the cover (Algorithm 3), the support release (Algorithm 4), the PTR test, and the final amplifier via basic composition (Lemma 7) yields the overall (ε, δ)-DP guarantee. For the utility, we analyze by conditioning on the high-probability event that the algorithm does not abort (i.e., it does not output ⊥) and all noise tail bounds hold. By Lemma 33, the IteratedCubicScoreCover successfully outputs ( P, R) satisfying κ2 ( R) ≤ e (d2 q/ε cov ) with probability at least 1 − β/3, which ensures that κ2 ( R) ≤ Kfinal /2 for the pubO e (d2 q/ε) by choosing large enough constants for Kfinal . Belicly promised target energy Kfinal = O cause q ≥ polylog(n), the gap Kfinal − κ2 ( R) ≥ Kfinal /2 asymptotically dominates the safety mare (d2 /ε test ). Therefore, to trigger a false abort, the Laplace noise ξ final must exceed gin Mfinal = O

32

Algorithm 5: Bootstrapped Fourth-Power Private Laplacian Oracle Input: Graph G = ([n], E) with maximum degree at most d, tunable parameter q, privacy parameters (ε, δ), failure probability β = n−c . Output: A valid non-negative weighted synthetic graph Laplacian b LG ∈ Ln , or ⊥. 1: Split budgets evenly: ε cov = ε/3, ε sup = ε/3, and ε amp = ε/3. Split δ and β similarly. 2: P ← IteratedCubicScoreCover( G, d, q, ε cov , δ/3, β/3); 3: if P is ⊥ then 4: return ⊥; 5: end if 6: Let R = ([ n ], E \ ( E ∩ P )); 7: e L P ← ReleaseOnSupport( G, P, ε sup , δ/3, β/3); e (d2 q/ε) be the promised target energy. 8: Let Kfinal = O 9: Split ε amp into ε test = ε amp /2 and ε rel = ε amp /2. 10: Let the safety margin be Mfinal = 3d2 11: Sample ξ final ∼ Lap(3d2 /ε test ).

log(6/δ) ε test .

12: if κ2 ( R ) + ξ final > Kfinal − Mfinal then 13:

return ⊥;

14: end if 15: Run the power-based spectral amplifier (Algorithm 1) on R with q = 4 and budgets

(ε rel /2, δ/6, β/6) plus a degree estimate with budgets (ε rel /2, β/6) to obtain e LR . e e e 16: Form the raw Laplacian estimate: L ← L P + L R . 17: SDP Projection: Compute the projection X onto the valid Laplacian cone Ln . 18: return b LG = X. ln(3/β)

Kfinal /2 − Mfinal ≫ ∆κ ε test . By the standard tail bound of the Laplace distribution (Lemma 10), this happens with probability at most β/3. Conditioned on this successful execution, the true graph Laplacian partitions exactly as LG = LG[ P] + L R . Applying the triangle inequality to our raw estimate e L=e LP + e L R , we sum the spectral error bounds from the support release (Lemma 35) and the fourth-power residual release (Lemma 36). By a union bound over all subroutines, this raw estimation error bounds LG − e L 2

with overall probability at least 1 − β. Finally, because the true unweighted graph Laplacian inherently satisfies LG ∈ Ln , the optimality of the SDP projection guarantees that b LG − e L ≤ LG − e L . Applying the triangle inequality 2

2

one last time yields LG − b LG

2

≤ LG − e L

2

+ e L−b LG

2

L ≤ 2 LG − e

2

,

which gives the claimed error interface and completes the proof.

6

An Edge-sensitive Private Cut Oracle

Here we construct a new oracle for the private release of graphs that preserves all-cut values. This edge-sensitive cut oracle, together with the spectral approximation results in Section 5 serve as key components of our final worst-case cut approximation result in Section 7. However, the de-

33

velopment of this oracle is self-contained and independent of previous spectral primitives developed in Section 5. As such, it may be of independent interest. Throughout this section, we denote cutG (·) ≡ wG (·) as the cut size function. Theorem 37 (Cut Oracle). Let G = (V, E) be a simple unweighted graph on n vertices, and let M ≥ | E| be public. For ε ∈ (0, 1), δ ∈ (0, 1/2), γ ∈ (0, 1/4), there is a polynomial-time (ε, δ)-edge-DP algorithm b such that, with probability at least 1 − 1/nc , for all S ⊆ V, CutOracle that outputs a weighted graph G cutGb (S) − cutG (S) ≤ γ cutG (S) + α, where eδ α=O

n + ε



n2 M ε2 γ

1/3 ! .

Furthermore, the output has total edge weight at most M.
e δ (n/ε + n2 M/(ε2 γ) 1/3 ), we utilize the private mirror descent frameTo get the error bound O work. The challenge in applying this method to graph cuts is the need for a separation oracle: exactly identifying the worst-case cut violation among 2n subsets is both computationally intractable and sensitive. Inspired by Eliáš et al. [EKKL20], we resolve this by relaxing the combinatorial cut checking problem into a continuous convex optimization problem, which is equivalently a logdeterminant regularized SDP. This carefully designed objective encodes all cut violations while enforcing stability on its optimal solution matrix to adopt privacy mechanisms. Further, compared to the direct application of the standard mirror descent framework [EKKL20, PX25] which yields √ e ε,δ ( Mn), to obtain a better dependency on M we privately test the an additive error bound of O objective value at each iterate and use the potential function method to analyze the utility. Remark 38 (Remark of Theorem 37). The primary motivation √ for designing this oracle is to replace e the best-known (before us) edge-sensitive error bound of O( Mn) due to Eliáš et al. [EKKL20]. This oracle will serve as a black-box interface in Section 7, where it achieves its full potential: after using the spectral primitive (Theorem 32) from Section 5.2 to trigger a sequence of recursive private expander decomposition, for arbitrary dense input graphs, we are able to reduce the number of edges in the residual graph to n5/4+o(1) . Applying our oracle to this residual graph then yields e ((n2 n5/4+o(1) )1/3 ) = O e (n13/12+o(1) ), which improves upon the previous a worst-case bound of O 1.25 e O(n ) bound.

6.1

The Regularized Separation Objective and Cut Approximation n

Let G = (V, E) be a simple unweighted graph on n vertices with edge-weight vector w∗ ∈ {0, 1}( 2 ) . We assume a publicly known upper bound M ≥ ∥w∗ ∥1 . The goal is to privately release a weighted n b with edge-weight vector w ∈ R( 2 ) that preserves all cut values of G. To maintain a graph G ≥0 bounded solution space, we define the feasible region of the edge-weight vector as W := {w ∈ (n)

R≥20 : ∥w∥1 ≤ M }. For any w ∈ W , we introduce a slack variable s(w) := M − ∥w∥1 , which captures the difference of total weight sum. For any cut S ⊆ V, the Boolean cut query cS ∈ {0, 1}X is defined as: cS ({u, v}) = 1[{u, v} ∈ (S, V \ S)], hence the cut value of S on w equals to cutw (S) = ⟨w, cS ⟩.

34

Given a target multiplicative approximation parameter γ ∈ (0, 1), we define the signed edge n residual vectors between w and w∗ as aσ (w, w∗ ) ∈ R( 2 ) and their corresponding slack residuals (w, w∗ ) ∈ R for directions σ ∈ {+, −}: aslack σ a+ (w, w∗ ) = w − (1 + γ)w∗ ,

∗ ∗ aslack + ( w, w ) = s ( w ) − (1 + γ ) s ( w ),

(18)

a− (w, w∗ ) = (1 − γ)w∗ − w,

∗ ∗ aslack − ( w, w ) = (1 − γ ) s ( w ) − s ( w ).

(19)

We also write them in abbreviated form as aσ , aslack , if w, w∗ are clear in the context. Note that the σ = −γM for σ ∈ {+1, −1}. To construct sum of the residuals is an invariant: ∑e∈(n2 ) aσ (e) + aslack σ a computationally efficient and private separation oracle, we relax the problem of checking the all 2n cuts into a continuous convex optimization over a positive semi-definite matrix X ∈ Rn×n and a scalar t ∈ R. For a fixed parameter 0 < ρ ≤ 1/8, we define the regularized cut separation objective function Fσ (w, w∗ ) as:

∑

Fbσ (w, w∗ , X, t) :=

aσ (w, w∗ )[e] ·

e={u,v}∈(n2 )

Fσ (w, w∗ ) :=

max

X ∈X ,ρ≤t≤1

n

1 − Xuv + aslack (w, w∗ ) · t, σ 2

o Fbσ (w, w∗ , X, t) + λR( X, t) ,

(20)

(21)

where the domain of X is n o X = X ∈ Rn×n | X = X ⊤ , diag( X ) = 1n , X ⪰ ρIn , and the regularizer R( X, t) controls the stability of the optimum:

R( X, t) := log det( X ) + log t. The parameter λ is used to control the privacy. We use the private mirror descent method introduced by [EKKL20] to solve the optimization min max Fσ (w, w∗ ).

w∈W σ ∈{+,−}

(22)

Before we introduce our algorithm, we first show that solving this optimization will yield a graph approximation that preserves all cut values. For every cut S and every 0 < ρ ≤ 1/8, let βS ∈ {±1}n be the sign vector of S, with βSu = 1 on S and −1 outside S. We define the matrix XS = (1 − 2ρ) βS ( βS )⊤ + 2ρIn . ρ

Lemma 39 (Intuition Behind Objective Function). For every cut S and every 0 < ρ ≤ 1/8, we have ρ XS ∈ X and ρ Fbσ (w, w∗ , XS , ρ) = (1 − 2ρ) ⟨ aσ (w, w∗ ), cS ⟩ − ργM. In particular, we have ρ Fb+ (w, w∗ , XS , ρ) = (1 − 2ρ) (cutw (S) − (1 + γ) cutw∗ (S)) − ργM,

and

ρ Fb− (w, w∗ , XS , ρ) = (1 − 2ρ) ((1 − γ) cutw∗ (S) − cutw (S)) − ργM.

35

Proof. The diagonal of XS is one. Its eigenvalues are 2ρ on ( βS )⊥ subspace and n(1 − 2ρ) + 2ρ in ρ ρ the βS direction, so XS ⪰ ρI. Hence XS ∈ X . For any e = {u, v}, write be = eu − ev , we have ρ

ρ

1 − ( XS )uv 1 1 − 2ρ S 2ρ ρ = be⊤ XS be = ( β u − βSv )2 + ∥be ∥22 = (1 − 2ρ)cS (e) + ρ. 2 4 4 4

= −γM gives Combining this with ∑e∈(n2 ) aσ (e) + aslack σ ρ Fbσ (w, w∗ , XS , ρ) =

∑

ρ

aσ (w, w∗ )e ·

e={u,v}∈(n2 )

1 − ( XS )uv + aslack · ρ = (1 − 2ρ) ⟨ aσ , cS ⟩ − ργM. σ 2

Using cutw (S) = ⟨w, cS ⟩ completes the proof. We use the following lemma to bound the error introduced by the regularizer term: Lemma 40. For a given ρ ∈ (0, 1/8) and any X ∈ X , ρ ≤ t ≤ 1, we have,

R( X, t) ≤ 0. Furthermore, for any cut S, we have, ρ

R( XS , ρ) ≥ −C0 n log(1/ρ) for a universal constant C0 . Proof. Hadamard’s inequality (Lemma 18) gives det X ≤ 1 because diag( X ) = 1n . Plus that t ≤ 1 ρ gives R( X, ρ) ≤ 0. Since the eigenvalues of XS are 2ρ on ( βS )⊥ subspace and n(1 − 2ρ) + 2ρ in the βS direction, we have
ρ log det XS = (n − 1) log(2ρ) + log n(1 − 2ρ) + 2ρ . Therefore, by ρ ≤ 1/8,
ρ R( XS , ρ) = (n − 1) log(2ρ) + log n(1 − 2ρ) + 2ρ + log ρ ≥ −C0 n log(1/ρ) for a universal constant C0 . The next lemma ensures that solving the optimization problem (eq. (21)) sufficiently well yields a graph approximation that preserves all cut values with multiplicative error. α α ) and λ satisfies C0 λn log(1/ρ) ≤ 32 for the universal Lemma 41. Let α > 0. Assume ρ = min( 81 , 16γM constant C0 decided in Lemma 40, then if

max Fσ (w, w∗ ) ≤

σ ∈{+,−}

5 α, 8

then

| cutw (S) − cutw∗ (S)| ≤ γ cutw∗ (S) + α holds for all S ⊆ V.

36

Proof. We prove the contrapositive. Assume there exists a cut S such that

| cutw (S) − cutw∗ (S)| > γ cutw∗ (S) + α. Using cutw (S) = ⟨w, cS ⟩, this implies that there exists a sign σ ∈ {+, −} such that ⟨ aσ , cS ⟩ > α. By α ), we have Lemma 39 and ρ = min( 81 , 16γM 3α α 11 Fbσ (w, w∗ , X, t) = (1 − 2ρ)⟨ aσ , cS ⟩ − ργM ≥ − ≥ α. 4 16 16 α Furthermore, by Lemma 40 and the assumption C0 λn log(1/ρ) ≤ 32 , we have: ρ

λR( XS , ρ) ≥ −λC0 n log(1/ρ) ≥ −

α . 32

Because Fσ (w, w∗ ) maximizes over all X ∈ X and ρ ≤ t ≤ 1, evaluating it at ( XS , ρ) provides a lower bound of Fσ (w, w∗ ). Therefore, ρ

ρ ρ Fσ (w, w∗ ) ≥ Fbσ (w, w∗ , XS , ρ) + λR( XS , ρ) 11α α 5 ≥ − > α. 16 32 8

This contradicts with the assumption.

6.2

The Private Mirror Descent Algorithm

In this section, we use the Private Mirror Descent framework by [EKKL20] to solve the optimization problem defined in (eq. (21)). We use the mirror function ψ(w) : W → R defined as below: ψ(w) := ∑ we log we + s(w) log s(w) e∈(n2 )

Generally, in each iteration, we solve the SDP defined in eq. (21), privately release the clipped gradient of the objective function, and finally perform a mirror descent update step with respect to the mirror function ψ. The details are in Algorithm 6. Remark 42 (Remark of Algorithm 6). Lemma 47 shows that the unclipped gradient estimator gbt is an unbiased approximation of the real gradient of Fσ (wt , w∗ ). However, we cannot directly use the unclipped gradient estimator, as the proof of Lemma 48 requires a constant upper bound on the gradient to establish the per-iteration decrease of the potential function. Also note that the update step indeed follows the mirror descent update rule [Bub15]: n o wt+1 = arg min ⟨θt ηgt , w⟩ + θt ηgtslack s(w) + Dψ (w∥wt ) , w∈W

′

s(w′ )

′ e where Dψ (w∥wt ) is the Bregman divergence Dψ (w′ ∥w) := ∑e we′ log w we + s ( w ) log s(w) .

6.3

Differential Privacy Analysis

In this section, we analyze the privacy of Algorithm 6. Recall that we employ the standard edge level privacy, i.e., two unweighted graphs G and G ′ are considered neighboring (denoted as G ∼ G ′ ) if they differ by exactly one edge insertion or deletion. Therefore, their corresponding true edge-weight vectors satisfy ∥w∗ − (w∗ )′ ∥1 ≤ 1. 37

Algorithm 6: Private Edge-sensitive Cut Oracle via Mirror Descent Input: Graph G = ([n], E) with public edge bound | E| ≤ M, parameters γ, ε, δ ∈ (0, 1). Output: An edge-weight vector w ∈ W .  1/3 e δ ( n + n22M ), threshold B = Θ(log M 1: Set parameters: target error α = O ε α ), time limit ε γ √

T log3/2 ( T/δ) α ), ρ = min( 18 , 16γM ), learning rate η = Θ( γB ). ε 2: Choose the initial solution w1 (e ) = (nM for all e ∈ (n2 ) and s(w1 ) = (nM . 2 )+1 2 )+1 BM log n T = Θ( γα ), λ = ν = Θ(

3: for t = 1, 2, . . . , T do 4:

5: 6: 7: 8: 9: 10: 11: 12: 13: 14:

Solving the SDP: For both directions σ ∈ {+, −}, find the maximizer Xt,σ ∈ X and tt,σ ∈ [ρ, 1] of Fσ (wt , w∗ ), where Fσ is defined in eq. (21). Test and Release: Release private estimates Fet,σ = Ft,σ + Zt,σ , where Zt,σ ∼ N (0, ν2 ). if max( Fet,+ , Fet,− ) ≤ 19α/32 then return wt . end if Release the Private Clipped Gradient: Let σt = arg maxσ∈{+,−} Fet,σ . Choose a random vector z ∼ N (0, Xt,σt ) and z0 ∼ N (0, tt,σt ). Let gbt ({u, v}) = 41 (zu − zv )2 , ∀{u, v} ∈ (n2 ) and gbtslack = z20 . Let gt ({u, v}) = min ( B, gbt ({u, v})) , ∀{u, v} ∈ (n2 ) and gtslack = min( B, gbtslack ). Mirror Descent Step: Let θt = 1 if σt = +, and θt = −1 if σt = −. For each edge e ∈ (n2 ): w t +1 ( e ) = M ·

15:

wt (e) exp(−θt ηgt (e)) . s(wt ) exp(−θt ηgtslack ) + ∑e′ ∈(n2 ) wt (e′ ) exp(−θt ηgt (e′ ))

(23)

Update the slack variable: s(wt+1 ) = M − ∥wt+1 ∥1 .

16: end for 17: return ⊥.

For notations, denote Pσ (w, w∗ ) = ( aσ (w, w∗ ), aslack (w, w∗ )) and denote Q( X, t) = ({ 1−2Xuv }uv , t). n Note that Q( X, t) ∈ R( 2 )+1 and ∥ Q( X, t)∥∞ ≤ 1 since X ⪰ 0 and diag( X ) = 1n implies | Xuv | ≤ 1. Then we have Fbσ (w, w∗ , X, t) = ⟨ Pσ (w, w∗ ), Q( X, t)⟩. We first prove that the value of the objective function Fσ has bounded sensitivity, which guarantees the privacy of releasing Fet,σ . Lemma 43 (Sensitivity of Fσ ). For any fixed edge-weight vector wt ∈ W and any two neighboring original edge-weight vectors w∗ , w∗′ , the objectives satisfy:

| Fσ (wt , w∗ ) − Fσ (wt , w∗′ )| ≤ 4 for both σ ∈ {+, −}. Consequently, by adding Gaussian noise Zt,σ ∼ N (0, ν2 ) with ν ≥ Fet,σ is (ε 0 , δ0 )-differentially private for both σ ∈ {+, −} (Lemma 13). 38

4

√

2 ln(1.25/δ0 ) , the release of ε0

) ) be the signed residual vectors for w∗ , and Pσ′ = ( aσ (wt , w∗′ ), aslack Proof. Let Pσ = ( aσ (wt , w∗ ), aslack σ σ ∗′ be the signed residual vector for w . For σ = +, by the definition, the change in the edge residual vector is: ∥ a+ (wt , w∗ ) − a+ (wt , w∗′ )∥1 = (1 + γ)∥w∗ − w∗′ ∥1 ≤ 1 + γ. Since s(w) = M − ∥w∥1 , the change in the slack residual is: ∗ slack ∗′ ∗ ∗′ ∗ ∗′ | aslack | ≤ 1 + γ. + ( wt , w ) − a+ ( wt , w )| = (1 + γ )| s ( w ) − s ( w )| = (1 + γ )| ∥ w ∥1 − w 1

Thus, the total ℓ1 -norm change of ( a+ , aslack + ) is bounded by c = 2(1 + γ ) ≤ 4 (since γ ∈ (0, 1)). Similarly, for σ = −, the total ℓ1 -norm change of ( a− , aslack − ) is bounded by 2(1 − γ ) ≤ 2 ≤ 4. We can conclude that ∥ Pσ − Pσ′ ∥1 ≤ 4. Let ( X ∗ , t∗ ) and ( X ∗′ , t∗′ ) be the unique optimizers of the regularized objectives parameterized by w∗ and w∗′ , respectively. By the optimality of ( X ∗ , t∗ ), the objective value for w∗′ evaluated at the ( X ∗′ , t∗′ ) must be smaller, i.e., Fσ (wt , w∗ ) = ⟨ Pσ , Q( X ∗ , t∗ )⟩ + λR( X ∗ , t∗ )

≥ ⟨ Pσ , Q( X ∗′ , t∗′ )⟩ + λR( X ∗′ , t∗′ ). Conversely, the objective for w∗′ is exactly evaluated at its own optimizer: Fσ (wt , w∗′ ) = ⟨ Pσ′ , Q( X ∗′ , t∗′ )⟩ + λR( X ∗′ , t∗′ ). Combining the above yields: Fσ (wt , w∗′ ) − Fσ (wt , w∗ ) ≤ ⟨ Pσ′ − Pσ , Q( X ∗′ , t∗′ )⟩

≤ ∥ Pσ − Pσ′ ∥1 ∥ Q( X ∗′ , t∗′ )∥∞ ≤ 4 × 1 = 4. The last inequality comes from the fact ∥ Q( X, t)∥∞ ≤ 1 for any X ∈ X and t ∈ [ρ, 1]. A symmetric argument establishes that Fσ (wt , w∗ ) − Fσ (wt , w∗′ ) ≤ 4, concluding the proof. Next, we prove the release of the gradient gbt is  private. First the  we need to  bound  sensitivity ∗ ∗′ X 0 X 0 of the optimal solution. In particular, denote Σ = and Σ′ = . Then the 0 t∗ 0 t∗′ unclipped gradients ( gb, gbslack ) for w∗ and w∗′ are sampled from the multivariate Gaussian distributions N (0, Σ) and N (0, Σ′ ). Thus this lemma shows that covariance matrices from neighboring graphs are close in the relative Frobenius norm. Lemma 44 (Stability of the Optimizer). Let ( X ∗ , t∗ ) and ( X ∗′ , t∗′ ) be the unique optimizers of the regu∗′ , respectively. Denote the corresponding covariance matrices larized objectives parameterized by w∗ and w  ∗   ∗′ X 0 X 0 as Σ = and Σ′ = . If λ ≥ 12, then: 0 t∗ 0 t∗′ 1 1 ∥Σ−1/2 (Σ′ − Σ)Σ−1/2 ∥ F ≤ O( ) ≤ . λ 2 Proof. To match the dimensions the optimization variables X ∈ X ⊂ Rn×n and t ∈ R encoded in  of  X 0 the covariance matrix Σ = ∈ R(n+1)×(n+1) , we formulate the linear objective coefficients 0 t

39

⊤ ⊤ 2 ( eu ev + ev eu )

1

0 0



∈ R(n+1)×(n+1) and Cslack = as matrices in the exact same space. Let Cuv = 0   0 0 ∈ R(n+1)×(n+1) . We define the gradient matrix Gσ with respect to Σ: 0 1 Gσ = −

1 aσ (wt , w∗ )uv Cuv + aslack (wt , w∗ )Cslack , σ 2 e={∑ u,v}

and define Gσ′ analogously for w∗′ . Because the feasible space of Σ is a convex set and the objective is concave, the constrained optimal solutions satisfy the first-order variational inequality. Specifically, since both Σ and Σ′ are feasible, cross-evaluating the gradients ∇ Fσ = Gσ + λΣ−1 and ∇ Fσ′ = Gσ′ + λΣ′−1 at their respective optima yields:

⟨ Gσ + λΣ−1 , Σ′ − Σ⟩ ≤ 0,

⟨ Gσ′ + λΣ′−1 , Σ − Σ′ ⟩ ≤ 0

Summing these two inequalities gives: λ⟨Σ−1 − Σ′−1 , Σ′ − Σ⟩ ≤ ⟨ Gσ′ − Gσ , Σ′ − Σ⟩. Define E = Σ−1/2 (Σ′ − Σ)Σ−1/2 . We denote the eigenvalues of I + E as µi . Since I + E = Σ−1/2 Σ′ Σ−1/2 , it holds that µi > 0 and Σ′ = Σ1/2 ( I + E)Σ1/2 . Furthermore, µi ≤ 1 + |µi − 1| ≤ 1 + ∥ E∥ F and ∥ E∥2F = ∑i (µi − 1)2 . Thus the left-hand side can be lower bounded as follows:   λ⟨Σ−1 − Σ′−1 , Σ′ − Σ⟩ = λ tr (Σ−1 − Σ′−1 )(Σ′ − Σ)   = λ tr (Σ−1 − Σ−1/2 ( I + E)−1 Σ−1/2 )(Σ1/2 ( I + E)Σ1/2 − Σ)

= λ tr( E( I − ( I + E)−1 )) = λ ∑ i

≥λ

( µ i − 1)2 µi

∥ E∥2F

∑ i ( µ i − 1)2 =λ . 1 + ∥ E∥ F 1 + ∥ E∥ F

 For ⊤the right-hand  side, utilizing our earlier definition of Cuv , we note that Σ ⊤ 0 1 xu xv + xv xu where xu = X 1/2 eu . Its squared Frobenius norm expands to 2 0 0

1/2 C Σ1/2 uv

1 1 2 1 2 + Xuu Xvv ) = ( Xuv + 1). (( xu⊤ xv )2 + ∥ xu ∥22 ∥ xv ∥22 ) = ( Xuv 2 2 2 Since | Xuv | ≤ 1, we establish Σ1/2 Cuv Σ1/2 F ≤ 1. Thus by the Cauchy-Schwarz inequality,

⟨Cuv , Σ′ − Σ⟩ = tr(Cuv Σ1/2 EΣ1/2 ) = tr(Σ1/2 Cuv Σ1/2 E) ≤ Σ1/2 Cuv Σ1/2

F

∥ E∥ F ≤ ∥ E∥ F .

Similarly, since Σ1/2 Cslack Σ1/2 F = t ≤ 1, we have ⟨Cslack , Σ′ − Σ⟩ ≤ ∥ E∥ F . Then we have,

⟨ Gσ′ − Gσ , Σ′ − Σ⟩ = −

1 ( aσ (wt , w∗′ )uv − aσ (wt , w∗ )uv )⟨Cuv , Σ′ − Σ⟩ 2∑ uv

+ ( aslack (wt , w∗′ ) − aslack (wt , w∗ ))⟨Cslack , Σ′ − Σ⟩ σ σ ≤ Pσ − Pσ′ 1 ∥ E∥ F . 40

=

Combining both sides yields

∥ E∥2F λ ≤ Pσ − Pσ′ 1 ∥ E∥ F . 1 + ∥ E∥ F From the proof of Lemma 43, we have ∥ Pσ − Pσ′ ∥1 ≤ 4. Thus if λ ≥ 12, this simplifies to

∥ E∥ F = ∥Σ−1/2 (Σ′ − Σ)Σ−1/2 ∥ F ≤

∥ Pσ − Pσ′ ∥1 1 1 = O( ) ≤ . ′ λ − ∥ Pσ − Pσ ∥1 λ 2

With the stability bounded in the relative Frobenius norm, we utilize the the following lemma proven by [EKKL20] to prove the gradient is privately released. Lemma 45 (Close Covariances Give Approximate DP, Lemma 4.10 in [EKKL20]). Let δ0 a fixed parameter and Σ, Σ′ be symmetric positive definite matrices s.t. ∥Σ−1/2 (Σ′ − Σ)Σ−1/2 ∥ F ≤ 1/2. Denote pdfΣ ( x ) and pdfΣ′ ( x ) the probability density functions of N (0, Σ) and N (0, Σ′ ) respectively. Let ε 0 = O(log δ10 ∥Σ−1/2 (Σ′ − Σ)Σ−1/2 ∥ F ). Then we have pdfΣ ( x ) ≤ eε 0 pdfΣ′ ( x ) with probability at least (1 − δ0 ) over x ∈ N (0, Σ). We now state and formally prove the main privacy theorem for Algorithm 6. Theorem 46 (Privacy√of Algorithm 6). For any privacy parameters ε, δ ∈ (0, 1), Algorithm 6 with parameter λ = ν = Θ(

T log3/2 ( T/δ) 5 ) satisfies (ε, δ)-differential privacy. ε

Proof. Algorithm 6 executes for at most T iterations. In each iteration t, the algorithm accesses the sensitive true edge-weight vector w∗ exactly three times: releasing two independent noisy objective functions ( Fet,+ and Fet,− ) and generating one covariance sample sequence (z, z0 ) based on Xt,σt , tt,σt . Consequently, the entire algorithm consists of 3T adaptive mechanisms. log(1/δ ) By Lemma 43 and the Gaussian Mechanism (Lemma 13), setting ν = Θ( ε 0 0 ) ensures that each of the two objective evaluations is (ε 0 , δ0 )-differentially private. For the covariance sample, combining Lemma 44 and Lemma 45 bounds the density ratio by eε 0 with probability (1 − δ0 ). Symmetrically applying it in the reverse neighboring direction (as formalized in [EKKL20]) establishes that drawing the gradient samples satisfies (ε 0 , δ0 )-differential privacy. δ Therefore, setting the per-mechanism budgets to ε 0 = Θ( √ ε ) and δ0 = Θ( 3T ), by ap3T log(1/δ)

plying the Advanced Composition Theorem (Lemma 8) over the 3T total mechanisms, Algorithm 6 is (ε, δ)-differentially private.

6.4

Utility Analysis

We analyze the utility via a potential function based on the Bregman divergence in round t: Φ(t) := Dψ (w∗ ∥wt ) = ∑ we∗ log e

√ 5 For simplicity, we assume

T log3/2 ( T/δ) = Ω (1). ε

41

we∗ s(w∗ ) + s(w∗ ) log . ( wt )e s ( wt )

Note that this analysis differs from the utility analysis in the private mirror descent framework established in [EKKL20] and [PX25]. For simplicity, we condition √ on the good event when all p e δ ( T/ε) with probability at least the Gaussian noises { Zt,σ } are bounded by O(ν log(nT )) = O 1 − 1/nc , by the Gaussian Tail Bound (Lemma 20) and a union bound over T rounds. First, we prove that the unclipped estimator gb is unbiased and the clip process incurs small additional error. Lemma 47. For every u, v ∈ (V2 ), E[ gbt ({u, v})] =

1 − ( Xt,σt )uv , 2

E[ gbtslack ] = tt,σt ,

E[ gbt2 ({u, v})] ≤

3 − 3( Xt,σt )uv , 2

E[( gbtslack )2 ] ≤ 3tt,σt .

Furthermore, 0 ≤ E[ gbt ({u, v}) − gt ({u, v})] ≤ 2e− B/2 ,

0 ≤ E[ gbtslack − gtslack ] ≤ 2e− B/2 .

Proof. Since Xuu = Xvv = 1 and z ∼ N (0, Xt,σt ), the linear combination (zu − zv ) is a zero-mean Gaussian variable with variance:
E[(zu − zv )2 ] = E[z2u ] − 2E[zu zv ] + E[z2v ] = ( Xt,σt )uu − 2( Xt,σt )uv + ( Xt,σt )vv = 2 − 2Xuv . Since for Gaussian random variable Y ∼ N (0, σ ) there is E[Y 2 ] = σ2 and E[Y 4 ] = 3σ4 , we have:   1 1 − ( Xt,σt )uv , E[ gtslack ] = E[z20 ] = tt,σt , E[ gbt ({u, v})] = E (zu − zv )2 = 4 2   3 − 3( Xt,σt )uv 3 E gbt ({u, v})2 = , (2 − 2( Xt,σt )uv )2 ≤ 16 2

E[( gbtslack )2 ] = 3t2t,σt ≤ 3tt,σt .

because Xt,σt ∈ X ensures |( Xt,σt )uv | ≤ 1 and tt,σt ≤ 1. Since gt (e) = min( B, gbt (e)) and gtslack = min( B, gbtslack ), for every e = {u, v} ∈ (V2 ): E[ gbt (e) − gt (e)] = E [( gbt (e) − B) · 1[ gbt (e) > B]] = 1−( X

Z ∞ B

Pr[ gbt (e) > x ]dx.

)

t,σt uv · ξ 2 , where ξ ∼ N (0, 1) and ξ 2 follows a chi-squared Since we can write gbt ({u, v}) = 2 distribution with one degree of freedom (χ21 ). Applying the standard tail bound Pr[ξ 2 > y] ≤ e−y/2

for y ≥ 1 (Lemma 16), and noting that bounded by:

1−( Xt,σt )uv ≤ 1, the tail probability for all x ≥ B ≥ 1 can be 2

Pr[ gbt (e) > x ] = Pr[ξ 2 >

2x ] ≤ Pr[ξ 2 > x ] ≤ e−x/2 . 1 − ( Xt,σt )uv

Integrating this tail bound yields: E[ gbt (e) − gt (e)] ≤

Z ∞ B

e− x/2 dx = 2e− B/2 .

Following the identical process for the slack variable where gbtslack = t · ξ 2 with t ≤ 1, we obtain E[ gbtslack − gtslack ] ≤ 2e− B/2 , which concludes the proof. The next lemma shows that the expected potential function is decreasing after each update step. 42

Lemma 48 (Expected Potential Progress). Suppose Algorithm 6 does not terminate at iteration t. As√ γ T 1 6 sume α ≥ Ωδ ( ε ). By setting B = Θ(log M α ) such that ηB ≤ 4 and learning rate η = Θ ( B ) such that γ η ≤ 6(1+γ) , there exists a constant c such that the update step guarantees an expected negative potential progress: γα E[ Φ ( t + 1) − Φ ( t ) | w t ] ≤ − c . B Proof. In the following proof, we always condition on wt . Recall on the good √ p that we condition e δ ( T/ε) ≤ α , by the event that all the Gaussian noises { Zt,σ }t,σ are bounded by O(ν log T ) = O 32 √

assumption α ≥ Ωδ ( εT ). Suppose Algorithm 6 does not terminate at iteration t, then the chosen direction σt ensures a significant violation: α 9 19α − = α. Fbσt (w, w∗ , Xt,σt , tt,σt ) ≥ 32 32 16

(24)

For simplicity, we set: U := ∑ wt ({u, v}) u,v

1 − ( Xt,σt )uv + s(wt )tt,σt , 2

U ∗ := ∑ w∗ ({u, v}) u,v

1 − ( Xt,σt )uv + s(w∗ )tt,σt , 2

V := ∑(wt ({u, v}) − w∗ ({u, v})) gt + (s(wt ) − s(w∗ )) gtslack , u,v

b := ∑(wt ({u, v}) − w∗ ({u, v})) gbt + (s(wt ) − s(w∗ )) gbtslack . V u,v

Let Wt = ∑e wt (e)e−θt ηgt (e) + s(wt )e−θt ηgt

slack

. The mirror descent update rule in eq. (23) yields that:

s ( wt ) ( wt )e + s(w∗ ) log ( w t +1 ) e s ( w t +1 ) e ( wt )e s ( wt ) = ∑ we∗ log + s(w∗ ) log slack − θ ηg ( e ) (wt )e e t t M/Wt s(wt )e−θt ηgt M/Wt e Wt = θt η ⟨w∗ , gt ⟩ + θt ηs(w∗ ) gtslack + M log . M

Φ(t + 1) − Φ(t) = ∑ we∗ log

Since e x ≤ 1 + x + x2 holds for every x ≤ 1/4 and η | gt (e)| ≤ ηB ≤ 41 by the assumption7 , together with log(1 + y) ≤ y, we have, ! Wt wt (e) −θt ηgt (e) s(wt ) −θt ηgtslack log = log ∑ e + e M M M e ! wt ( e ) s ( wt ) 2 2 slack 2 slack 2 ≤ log ∑ (1 − θt ηgt (e) + η gt (e)) + (1 − θt ηgt + η ( gt ) ) M M e wt ( e ) s ( wt ) (−θt ηgt (e) + η 2 gt2 (e)) + (−θt ηgtslack + η 2 ( gtslack )2 ). M M e

≤∑

6 Without loss of generality, we assume M > α as M is public. Otherwise, we simply release the empty graph. 7 If we use the unclipped gradient, since it may be unbounded, the inequality may not hold.

43

Therefore, 



Φ(t + 1) − Φ(t) ≤ −θt η ⟨wt − w∗ , gt ⟩ + (s(wt ) − s(w∗ )) gtslack + η 2

∑ wt (e) gt (e)2 + s(wt )( gtslack )2 e

∑ wt (e) gt (e)2 + s(wt )( gtslack )2

= −θt ηV + η 2

! .

e

3−3( Xt,σt )uv 2

By Lemma 47, E[ gbt2 ({u, v})] ≤ gtslack ≤ gbtslack we have,

E[ gt2 ({u, v})] ≤ E[ gbt2 ({u, v})] ≤ Therefore,

" E η

2

and E[( gbtslack )2 ] ≤ 3tt,σt , together with gt ≤ gbt and

3 − 3( Xt,σt )uv , 2

∑ w t ( e ) gt ( e )

E[( gtslack )2 ] ≤ E[( gbtslack )2 ] ≤ 3tt,σt . !#

2

+ s(wt )( gtslack )2

≤ 3η 2 U.

e

By Lemma 47, E[ gbt ({u, v}) − gt ({u, v})] ≤ 2e− B/2 and E[ gbtslack − gtslack ] ≤ 2e− B/2 . Thus, b − V |] ≤ 2e− B/2 ∑(wt (e) + w∗ (e)) + (s(wt ) + s(w∗ )) E[|V e

= 4Me

− B/2

.

9 b ] = U − U ∗ again For the case when σt = +, eq. (24) implies U − (1 + γ)U ∗ ≥ 16 α. Note that E[V because of Lemma 47. Then we have,

b ] = U − U∗ ≥ E[V

γ 9 U+ α. 1+γ 16(1 + γ)

9 Similarly, for the case when σt = −, eq. (24) implies (1 − γ)U ∗ − U ≥ 16 α. We have,

b ] = U∗ − U ≥ E[−V

γ 9 U+ α. 1−γ 16(1 − γ)

Combining the above, we obtain, b ] + ηE[|V b − V |] + 3η 2 U E[Φ(t + 1) − Φ(t)] ≤ −ηE[θt V   γ 9ηα ≤ −ηU − 3η − + 4η Me− B/2 . 1 + θt γ 16(1 + θt γ) By the assumption that η ≤ 6(1γ+γ) < 6(1γ−γ) , the first term is negative for all U ≥ 08 . By setting the clipping threshold to be B = Θ(log M α ), the third term can be smaller than 100 . By setting γ γ η = Θ( B ), the requirement η ≤ 6(1+γ) and ηB ≤ 41 can hold. Therefore, utilizing the fact that γ ∈ (0, 1/4) and η = Θ( γB ), we conclude: ηα

E[ Φ ( t + 1) − Φ ( t ) | w t ] ≤ 0 −

9ηα ηα γα + ≤ −c . 20 100 B

=√ 0), this term reduces to 3η 2 U. Bounding U via the Cauchy-Schwarz e inequality finally yields an additive error of O( Mn), offering no improvement over the error bounds in [EKKL20]. 8 In the purely additive error setting (γ

44

!

The next lemma computes the number of the update steps needed in Algorithm 6 for obtaining the required accuracy. Lemma 49 (Stopping Time). Suppose that Algorithm 6 terminates after τ updates. If every nonterminal update t satisfies E[Φ(t + 1) − Φ(t) | wt ] ≤ −∆, then, E[ τ ] ≤ O (

M log n ). ∆

Consequently, with probability ≥ 5/6, τ ≤ O(

M log n ). ∆

Before proving this lemma, we introduce a standard tool in martingale analysis. Proposition 50 (Theorem 4.2.12 in [Dur19]). Let a sequence of random variables X = ( Xt )t≥0 be a supermartingale (i.e., E[ Xt+1 | X1 , . . . , Xt ] ≤ Xt ) and τ be a stopping time, both with respect to a filtration (Ft )t≥0 . If the stopping time τ is bounded, then, E[ Xτ ] ≤ E[ X1 ]. Proof of Lemma 49. Let t ≥ 1 denote the iteration index. We define the stochastic process Xt := Φ(t) + ∆ · t for any t ≤ τ.9 By the assumption, for any t ≤ τ, we have, E [ Xt +1 | w t ] = E [ Φ ( t + 1 ) | w t ] + ∆ · ( t + 1 ) = E [ Φ ( t + 1 ) − Φ ( t ) | w t ] + Φ ( t ) + ∆ · ( t + 1 )

≤ − ∆ + Φ ( t ) + ∆ · ( t + 1) = Φ ( t ) + ∆ · t = Xt . This implies that ( Xt )t≥1 is a supermartingale with respect to the filtration generated by (wt )t≥1 . Let τ denote the first iteration where the halting condition max( Fet,+ , Fet,− ) ≤ 19α/32 is met (with τ = ∞ if it is never met). Since Algorithm 6 explicitly enforces a maximum iteration limit of T, the actual number of executed steps is deterministically bounded by τT = min(τ, T ) ≤ T. Because this bounded stopping time is valid for the optional stopping theorem (Proposition 50), we have: E[ XτT ] ≤ E[ X1 ] = Φ(1) + ∆. Since the Bregman divergence is non-negative, Φ(τT ) ≥ 0, which yields: ∆ · E[τT ] ≤ E[Φ(τT ) + ∆ · τT ] = E[ XτT ] ≤ Φ(1) + ∆. By the identical calculation bounding the initial potential, we have Φ(1) ≤ 2M log n. Therefore, the expected number of steps before halting or hitting the horizon is bounded by:   2M log n M log n E[τT ] ≤ +1 = O . ∆ ∆ To ensure the algorithm halts successfully before hitting the hard limit T, we set T = ⌈6 · E[τT ]⌉ = M log n Θ( ∆ ). Applying Markov’s inequality unconditionally on the bounded variable τT : Pr[τ > T ] ≤ Pr[τT ≥ T ] ≤

E[τT ] 1 ≤ . T 6

Thus, with probability at least 5/6, the algorithm successfully terminates with a valid output within T iterations. 9 For any t > τ, we let X

t = Xτ .

45

Now we state the main utility theorem for Algorithm 6. Theorem 51 (Utility of Algorithm 6). Let G = (V, E) be a simple unweighted graph on n vertices, and let M ≥ | E| be public. For ε ∈ (0, 1), δ ∈ (0, 1/2), γ ∈ (0, 1/4), Algorithm 6 outputs a weighted graph b such that, with probability at least 2/3, for all S ⊆ V, G cutGb (S) − cutG (S) ≤ γ cutG (S) + α, where eδ α=O

n + ε



n2 M ε2 γ

1/3 ! . √

Proof. Combining Lemma 48 and Lemma 49, if α = Ωδ ( εT ), setting the total iteration limits to M log n BM log n T = Θ( γα/B ) = Θ( γα ) ensures that the algorithm outputs wt such that max( Fet,+ , Fet,− ) ≤ √ p e δ ( T/ε) ≤ 19α/32 with probability at least 5/6. Since { Zt,σ }t,σ are bounded by O(ν log T ) = O α 19α α 5α ∗ 32 with probability at least 5/6, we have, maxσ Ft,σ ( wt , w ) ≤ 32 + 32 = 8 . By Lemma 41, if α α ) and C0 λn log(1/ρ) ≤ 32 , we can conclude that, ρ = min( 81 , 16γM

| cutw (S) − cutw∗ (S)| ≤ γ cutw∗ (S) + α holds for all S ⊆ V. √ T log3/2 ( T/δ) α Since we set λ = Θ( ) and B = Θ(log M ε α ), combining them with C0 λn log(1/ρ ) ≤ 32 √

(already ensures α = Ωδ ( εT )) and T = Θ(

√ eδ α=O

BM log n ) yields γα

Tn ε

√

! eδ =O

Mn √ γαε

! .

Also noting that T ≥ 1, thus the total additive error eδ α=O

n + ε



n2 M ε2 γ

1/3 ! .

It can be verified that all assumptions in Theorems 41, 46 and 48 are satisfied under our choice of parameters. Proof of Theorem 37. We construct the final algorithm CutOracle by executing the core subroutine (Algorithm 6) repeatedly. Let K = ⌈C log(1/β)⌉ for a sufficiently large absolute constant C. The oracle runs Algorithm 6 up to K times independently. If an execution returns a valid edge-weight vector wt (instead of "⊥"), CutOracle halts immediately and outputs wt . If all K executions return "⊥", it outputs an empty graph. Privacy Guarantee. In the worst case, the algorithm executes the subroutine K times. We allocate a local privacy budget (ε 0 , δ0 ) to each individual run. By the advanced composition Theorem (Lemma 8), it suffices to set: ! ε δ ε0 = Θ p , δ0 = . 2K K log(1/δ) As the halting condition only depends on the privately released Fet,σ , the adaptive stopping time is private due to post-processing(Lemma 6). Finally, combing Theorem 46 concludes the proof. 46

Utility Guarantee. We bound the failure probability by analyzing two failure events. First, let c Enoise be the event that any drawn Gaussian noise | Zt,σ | across all K runs and T iterations exceeds α/32. Since Zt,σ ∼ N (0, ν2 ), applying standard Gaussian tail bounds (Lemma 20) and a union p bound over the 2KT random variables guarantees that setting α = Ω(ν log(KT/β)) is enough c to guarantee Pr[Enoise ] ≤ β/2. Second, let Eall abort be the event that all K independent runs fail to halt within their T horizons. Because the K runs are mutually independent, we apply the per-run utility analysis (Theorem 51), which bounds the failure probability of a single run by 1/3. Thus, the probability is Pr[Eall abort ] ≤ (1/3)K ≤ β/2 (by our choice of constant C). By the union bound, the probability that the algorithm either suffers from large noise or abort c is bounded by Pr[Enoise ∪ Eall abort ] ≤ β/2 + β/2 = β. Therefore, with probability at least 1 − β, neither failure event occurs. Because Eall abort does not occur, the algorithm successfully halts and c outputs a graph; because Enoise does not occur, the analysis in Theorem 51 guarantees this output graph satisfies the target error bound:  2 1/3 ! n n M eδ α=O . + ε0 ε20 γ Substituting ε 0 = Θ



ε √ log(1/β) log(1/δ)

eδ α=O

n

p

 , the error scales as: log(1/β) + ε



n2 M log(1/β) ε2 γ

1/3 ! ,

e δ (·) hides polylogarithmic factors in n, 1/δ. where the O Implementation. Follow a similar proof to [EKKL20], Algorithm 6 can be implemented in time Õε,δ,γ (n20/3 logO(1) (n)) with the same level of guarantee for additive error and privacy. Here we only give a proof sketch. BM log n By Algorithm 6 and Lemma 51, we have T = Θ( γα ) = Õε,δ,γ ( M2/3 n−2/3 ). In each iter∗ ∗ ation, note that the update step runs inO(n2 ) time.  Denote X , t be the maximizer of the SDP ∗ X 0 maxX ∈X ,ρ≤t≤1 F̂σ (w, w∗ , X, t) and Σ∗ = . We use the algorithm of [LSW15] to find an 0 t∗   X 0 approximate solution X, t (let Σ = ) of the SDP in Algorithm 6 in time Õ(n6 logO(1) (n/µ)), 0 t 1

1

s.t., (Σ∗ )− 2 (Σ∗ − Σ)(Σ∗ )− 2

F

≤ µ. Therefore, across all K rounds and T iterations, our algorithm

can be implemented in time Õε,δ,γ ( M2/3 n16/3 logO(1) (n)) = Õε,δ,γ (n20/3 logO(1) (n)). According to [EKKL20], the additive error only differs by a constant factor when we choose µ = 1/nO(1) . And the privacy loss in each iteration is still O( λ1 ) by Lemma 44, hence the privacy guarantee is the same as before. This concludes the proof of Theorem 37.

7

e (n13/12+o(1) ) Additive Error for Cut Approximation An O

In this section, we study private algorithms for approximating graph cuts. Given a private synthetic of graph Laplacian, the quadratic form xS⊤ ( LG − L Hb ) xS immediately bounds the cut error, and one can easily verify that the additive cut error for any set S is directly bounded by ∥ LG − LGb ∥2 ·

47

min(|S|, |V \ S|). However, the additive error of this direct corollary on cut approximation typically e (n1.5 ) or worse on dense graphs. reduces to O If allowing for multiplicative approximation, the best-known polynomial-time edge-differentially e (n1.25 ) additive error [ACD+ 25]. To make further improvement, we private algorithm suffers an O give a black-box reduction by assuming a generic primitive parameterized by a spectral error interface Π(n, d, ε, δ), then develop a demand-aware recursive expander decomposition framework. Assumption 1 (Private Spectral Primitive). For any n-node unweighted graph H with maximum degree bounded by d, and for any privacy parameters ε, δ ∈ (0, 1) and failure probability β ∈ (0, 1), there exists a polynomial-time (ε, δ)-edge-DP algorithm that outputs a non-negative weighted graph Laplacian b L H such that, with probability at least 1 − β: LH − b LH

2

≤ Π(n, d, ε, δ, β).

(25)

We assume Π = poly(n, d, 1/ε, log(1/δ), log(1/β)) and is non-decreasing in n and d, and nonincreasing in ε, δ and β. For brevity, when the privacy parameters are clear from the context or not the primary focus of an asymptotic discussion, we may use the shorthand Π(n, d). In this section, we will show that under (ε, δ)-differential privacy, we reduce the additive cut error to a bound purely determined by the recursive fixed point of this spectral primitive subject to privacy composition, maintaining a multiplicative error (Theorem 58). Finally, we use the spectral bound stated in Theorem 32 (Section 5.2) to instantiate Assumption 1 to get a polynomial time e (n13/12+o(1) ) additive error on cut approximation. private algorithm with O

7.1

Stable Port Gadget

To break the algorithmic dependency on the maximum degree in the spectral oracle (e.g., Theorem 29 or Theorem 32), we need to transform an input graph R (which might be a residual graph in some recursive steps) into a port proxy graph ♯ R with a smaller bounded maximum degree. For the ease of reading, we decouple this transformation into two distinct phases: (1) a differentially private mechanism to publish a demand vector ρ ∈ Zn≥1 , and (2) a sensitivity-preserving topological routing that constructs ♯ R conditioned on the public ρ. 7.1.1

Private Demand Allocation

We first define the demand vector ρ in terms of vertices in the original graph R, which determines the number of micro-nodes (ports) allocated to each vertex. Such allocation should be sufficient to route all incident edges while keeping the total graph volume bounded. Lemma 52 (Private Demand Allocation). Let R = (V, ER ) be an unweighted simple graph with |V | = n and a public edge upper bound M ≥ | ER |. Let D = max{1, M/n}. Given privacy parameter ε deg and failure probability β deg , there exists an (ε deg , 0)-edge-DP mechanism BuildDemand(ε deg , R, M ) that outputs a demand vector ρ : V → Zn≥1 satisfying: 1. Capacity: With probability at least 1 − β deg , for all v ∈ V, ρ(v) ≥ degR (v)/D. 2. Demand Mass: With probability at least 1 − β deg , the total demand is bounded by   n ln(n/β deg ) e ( n ). ρ (V ) ≤ O ( n ) + O =O D · ε deg Further, ρ(V ) is deterministically bounded by ρ(V ) ≤ poly(n, 1/ε deg , log(1/β deg )). 48

Proof. The true degree vector degR (·) has an ℓ1 -sensitivity of exactly 2 under edge-neighboring relations, as adding or removing an edge {u, v} changes the degrees of both u and v by exactly 1. We apply the Laplace mechanism (Lemma 12) by adding independent noise variables Zv ∼ Lap(2/ε deg ) and computing the noisy degrees dev = degR (v) + Zv . This is (ε deg , 0)-DP. To ensure that the capacity conditionholds  even under worst-case negative noise, we define a 2 ln high-probability noise bound a = ε deg

n β deg

. We further apply a deterministic upper cap: since

the true degree satisfies degR (v) < n, we hard-cap the shifted noisy degree at n + 2a: & ' min{n + 2a, max{0, dev + a}} bv = ρ ( v ) = 1 + . D

(26)

Deterministically, this hard cap limits the total demand to   4 ln(n/β deg ) n + ε deg . ρ ≤ n 2 + D By the tail bounds of the Laplace distribution (Lemma 10) and a union bound over all n vertices, the good event that | Zv | ≤ a for all v ∈ V holds with probability at least 1 − β deg . Conditioning on this good event, Zv ≥ − a guarantees that dev + a = degR (v) + Zv + a ≥ degR (v). Because the true degree degR (v) < n ≤ n + 2a, the deterministic cap never pulls the value below the true degree. Consequently, the allocated number of ports unconditionally guarantees bv ≥ degR (v)/D on this good event, satisfying the Capacity property. To bound the total demand mass ρ(V ) accurately on this good event, we sum the unclipped values over all vertices: 2M n(2a + 1) degR (v) + 2a + 1 ≤ n+ + . D D D v ∈V

ρ ( V ) = ∑ bv ≤ n + ∑ v ∈V

Since D = max{1, M/n}, we have 2M/D ≤ 2n. Therefore, substituting the constants yields e ε (n), concluding the proof. ρ(V ) ≤ 3n + n(2a + 1)/D = O deg 7.1.2

Stable Port Routing

Treating the demand vector ρ defined in eq. (26) as a fixed public parameter, we now construct the topology of the proxy graph ♯ R. We note that the construction should be stable in terms of edge change: changing one edge in R should only trigger a constant number of edge changes in ♯ R. Lemma 53 (Stable Port Graph). Given a public demand vector ρ ∈ Zn and failure probability β util , there is a routing mechanism BuildGadget( R, ρ) using public hashes to construct a port graph ♯ R on the lifted vertex set V (♯ R) = {(v, i ) : v ∈ V, i ∈ [ρ(v)]}. This construction satisfies: 1. Degree Bound: The maximum degree ∆(♯ R) ≤ O( D ) + O (ln(n/β util )). 2. Edge-Stability: If R and R′ differ by exactly one edge, the resulting graphs ♯ R and ♯ R′ differ by at most 4 edges. 3. Cut Preservation: If ρ satisfies the Capacity property of Lemma 52, then with probability at least 1 − β util , for all S ⊆ V, defining the lifted cut ♯ S = {(v, i ) : v ∈ S, i ∈ [ρ(v)]} yields w R (S, V \ S) = w♯ R (♯ S, V (♯ R) \ ♯ S). 49

Proof. For each vertex v ∈ V, we instantiate its ρ(v) ports. To distribute the original incident edges among these ports, we draw fresh, fully independent public hash functions hv : V \ {v} → [ρ(v)]. For any original edge e = {u, v} ∈ ER , its projection is deterministically mapped to the port pair {(u, hu (v)), (v, hv (u))}. To enforce a worst-case upper bound on the maximum degree of ♯ R, we apply a deterministic truncation mechanism. For each port (v, j), we define its candidate incident set as Cv,j ( R) = {{u, v} ∈ ER : hv (u) = j}. Instead of accepting all candidates, we sort Cv,j ( R) according to a globally fixed, public lexicographical order based on the vertex IDs. We truncate the sorted list, retaining only the first B = 2eD + 3 ln(2ρ(V )/β util ) elements, yielding the truncated set TopB (Cv,j ( R)). A candidate edge is added to ♯ R if and only if it survives the truncation at both endpoints. This hard cutoff guarantees that the maximum degree ∆(♯ R) ≤ B. Since Lemma 52 e (n), the threshold simplifies to B = O( D ) + O (ln(n/β util )), which proves the bounds ρ(V ) ≤ O Degree Bound property. To verify the Edge-Stability, suppose the private input graph changes by exactly one edge e = { x, y}. Because the hash mappings and the lexicographical sorting order are entirely public and independent of the graph topology, this perturbation modifies the candidate sets of exactly two ports: Cx,hx (y) and Cy,hy (x) . Within either candidate set, the addition or removal of e translates to inserting or deleting exactly one element in a deterministically sorted list. This operation shifts the truncation boundary, altering the membership of the TopB set by at most two elements (the perturbed element itself and the boundary element pushed out of or pulled into the list). Consequently, the symmetric difference between E(♯ R) and E(♯ R′ ) is bounded by at most four edges, ensuring O(1) sensitivity globally regardless of the graph’s density. Finally, we evaluate the probability of truncation under the assumption that the Capacity condition holds. Given ρ(v) ≥ degR (v)/D (Lemma 52), the expected load for any port (v, j) is µv,j = E|Cv,j ( R)| = degR (v)/ρ(v) ≤ D. By applying the standard Chernoff bound (Lemma 22), the probability that the load exceeds the threshold B is upper bounded by Pr[|Cv,j ( R)| ≥ B] ≤

β util . ρ (V )

Taking a union bound over all ρ(V ) ports across the entire graph, the probability that any port overflows its capacity B is bounded by β util . When no overflow occurs, every edge in ER passes the truncation at both endpoints, establishing an exact bijection between the edges of R and ♯ R. Therefore, mapping the vertices of S to their corresponding ports ♯ S preserves the cut edges across the boundary, yielding w R (S, V \ S) = w♯ R (♯ S, V (♯ R) \ ♯ S) holds with probability at least 1 − β util , which concludes the proof.

7.2

Demand-Sensitive Private Cut Oracle

Building upon the stable port gadget in Section 7.1, we construct a private cut oracle capable of achieving additive errors proportional only to the demand mass ρ(S) (defined in eq. (26)) and the spectral primitive’s error interface Π, rather than the true maximum degree d. Lemma 54 (Demand-Sensitive Private Cut Approximation). Let H = R[U ] be any induced subgraph of the input graph R = (V, ER ) subject to the public upper bound | ER | ≤ M. Given the public demand vector ρ from Lemma 53, there exists an (ε, δ)-edge-DP mechanism SyntheticOracle( H, ρ, ε, δ, β) outputting a b such that, with probability at least 1 − β, for all S ⊆ U: synthetic non-negative weighted graph H e (Π(n, M/n, ε, δ, β)) min{ρ(S), ρ(U \ S)}. |w H (S, U \ S) − w Hb (S, U \ S)| ≤ O

50

(27)

Proof. The oracle SyntheticOracle( H, ρ, ε, δ) simply first builds the proxy graph ♯ H with ρ and then run the generic spectral oracle (Assumption 1) on ♯ H to generate a synthetic graph. Instead of inducing from a globally truncated port graph ♯ R (which could leak information and introduce more sensitivity from edges outside U), we construct the local port proxy graph ♯ H with BuildGadget( H, ρ) (Lemma 53) directly on the induced subgraph H = R[U ]. We define the lifted S vertex set exclusively for U as ♯ U = v∈U {(v, j) : j ∈ [ρ(v)]}. The total number of micro-nodes in ♯ H evaluates to the local demand mass, bounded by the global capacity: e ( n ). |V (♯ H )| = |♯ U | = ∑ ρ(v) = ρ(U ) ≤ ρ(V ) ≤ O v ∈U

We then invoke the private spectral primitive (Assumption 1) on ♯ H. Because the addition or removal of an original edge in R modifies at most c = 4 edges in ♯ H 10 , treating the graph ♯ H under single-edge DP incurs a group privacy reduction of size c = 4. By standard group privacy guarantees for approximate differential privacy, running the primitive with calibrated privacy pa−1 jε′ rameters ε′ = ε/c and δ′ = δ/ ∑cj= 0 e ensures ( ε, δ )-edge-DP. The mechanism outputs a synthetic graph Laplacian b L♯ H . We define the error matrix E = L♯ H − b L♯ H . Given that Π(·, ·, ·, ·, ·) is monotonically non-decreasing in dimensions and monotonically non-increasing in privacy parameters, with probability at least 1 − β, the spectral norm of E satisfies:   e Π(|V (♯ H )|, ∆(♯ H ), ε′ , δ′ , β) . (28) ∥ E ∥2 ≤ O Here, ∆(♯ H ) is bounded by O(max{1, M/n}) + O(log(n/β′ )) due to Lemma 53. According to Assumption 1, the polylogarithmic inflation in vertices and degrees, alongside the constant splitting e notation. This cleanly yields: of privacy budgets, can be absorbed into the O e (Π(n, max{1, M/n}, ε, δ, β)) := Λρ ( M, ε, δ, β). ∥ E ∥2 ≤ O

(29)

b on the original vertex space U, we collapse the micro-nodes To form the final synthetic graph H b is defined by back to their source vertices. Note that, the Laplacian b L H of the synthetic graph H summing the corresponding block submatrices of b L♯ H : ρ(u) ρ(v)

b L H (u, v) = ∑ ∑ b L♯ H ((u, i ), (v, j)). i =1 j =1

♯

For any cut S ⊆ U, we lift it to the port space by defining its indicator vector 1♯ S ∈ {0, 1}| U | , where (1♯ S )(v,i) = 1 if and only if v ∈ S. Due to the exact cut preservation of the stable gadget, all inter-cluster gadget edges exactly correspond to original edges with probability at least 1 − β util = 1 − 1/nc . Consequently, the cut weight in H can be formulated identically as the quadratic form of the port Laplacian: w H (S, U \ S) = w♯ H (♯ S, ♯ U \ ♯ S) = 1♯⊤S L♯ H 1♯ S . Simultaneously, the matrix block-sum definition guarantees that the cut value in the synthetic b translates to the same quadratic form under the synthetic Laplacian: graph H w Hb (S, U \ S) = 1♯⊤S b L ♯ H 1♯ S . 10 Note that the truncation in BuildGadget( H, ρ ) (Lemma 53) is applied exclusively to the local edge set E ( H ), edges outside U have no effect. Thus, any single edge change in the global graph R modifies at most 4 edges in ♯ H.

51

The absolute additive error is therefore equivalent to the quadratic form evaluated over the error matrix E: (30) L♯ H )1♯ S = 1♯⊤S E1♯ S . |w H (S, U \ S) − w Hb (S, U \ S)| = 1♯⊤S ( L♯ H − b Applying the standard operator norm inequality, we bound the quadratic form utilizing eq. (28) and the ℓ2 -norm of the indicator vector: ρ(v)

1♯⊤S E1♯ S ≤ ∥ E∥2 ∥1♯ S ∥22 ≤ Λ( M, ε, δ) ∑ ∑ 12 = Λ( M, ε, δ) ∑ ρ(v) = Λ( M, ε, δ)ρ(S). v ∈ S i =1

(31)

v∈S

To establish the complementary bound for the complement cut U \ S, we note that by the definition of graph Laplacian matrix: L♯ H 1 = 0 and b L♯ H 1 = 0 hold unconditionally, implying E1 = ( L♯ H − b L♯ H )1 = L♯ H 1 − b L♯ H 1 = 0. We express the all-ones vector as 1 = 1♯ S + 1♯ U \♯ S and expand the quadratic form of the complement indicator vector: 1♯⊤U \♯ S E1♯ U \♯ S = (1 − 1♯ S )⊤ E(1 − 1♯ S ) = 1⊤ E1 − 1⊤ E1♯ S − 1♯⊤S E1 + 1♯⊤S E1♯ S . Note that E1 = 0 and 1⊤ E = 0⊤ , which yields that: 1♯⊤U \♯ S E1♯ U \♯ S = 1♯⊤S E1♯ S . Substituting this symmetric equality into the operator norm inequality mirroring eq. (31): 1♯⊤S E1♯ S = 1♯⊤U \♯ S E1♯ U \♯ S ≤ ∥ E∥2 1♯ U \♯ S

2 2

≤ Λ( M, ε, δ)

∑ ρ(v) = Λ( M, ε, δ)ρ(U \ S). (32)

v ∈U \ S

Combining Eq. (31) and Eq. (32) simultaneously restricts the absolute error to the minimum of the two respective demand masses, concluding the proof.

7.3

Private Expander Decomposition with Demand

To conduct expander decomposition and privately partition the graph into dense components, we utilize the deterministic bicriteria algorithm by Li and Saranurak ([LS21]). Theorem 55 (Demand-Aware Bicriteria Cut Routine, Theorem 2.14 in [LS21]). There is a deterministic polynomial-time algorithm that takes as input a graph H = (VH , EH ) with non-negative edge weights w H , a vertex demand vector ρ : VH → R≥0 , and a sparsity parameter ϕ > 0. The algorithm outputs either a cut S ⊂ VH or ∅ satisfying the following properties: 1. Sparsity Guarantee: If the algorithm outputs S ̸= ∅, then S is the side with the smaller or equal demand, i.e., ρ(S) ≤ ρ(VH \ S), and its demand-sparsity satisfies: w H (S, VH \ S) ≤ ϕ · ρ(S). 2. Bicriteria Maximality (Certifier): If there exists any other sparse cut S∗ ⊂ VH with ρ(S∗ ) ≤ ϕ ρ(VH \ S∗ ) such that: w H (S∗ , VH \ S∗ ) ≤ dexp · ρ(S∗ ), then the output S ̸= ∅ satisfies that: ρ(S) ≥ 52

ρ(S∗ ) . dsize

Here, dexp = O(logc n) and dsize = O(1) are global constants. We adapt this algorithm to operate over the private synthetic graph output by our demandsensitive oracle in Section 7.2. In particular, we formalize this procedure of the private cut finder in Algorithm 7. The algorithm acts as a differentially private wrapper, utilizing the synthetic graph from our demand-sensitive oracle to execute the deterministic routine in Theorem 55. Algorithm 7: Private Demand Cut Finder (CutFinder) Input: Induced subgraph H = R[U ], public demand vector ρ, target sparsity parameter ψ, privacy parameters (ε, δ). Output: A cut S ⊂ U satisfying ρ(S) ≤ ρ(U \ S) and w H (S, U \ S) ≤ ψρ(S), or ∅ // Private Graph Synthesis via Spectral Oracle (Lemma 54) b ← SyntheticOracle( H, ρ, ε, δ); 1 Let H // Trim and Cap (Deterministic Weight Regularization) ψ 2 Set θ ← 10n and Wmax ← ψρ (U ); b ) do 3 for each edge e ∈ E ( H 4 if we < θ then b 5 Delete e from H; 6 else if we > Wmax then 7 Truncate weight we ← Wmax ; // Deterministic Bicriteria Search b with input demand vector ρ 8 Execute the Demand-Aware Cut Routine (Theorem 55) on H and target sparsity ϕ = 0.8ψ; 9 if the routine returns a valid cut S then 10 return S; 11 else 12 return ∅ ; // Certifies H is a valid (ψ/dexp , ρ)-expander

Lemma 56 (Private Demand Cut Finder). Fix any U ⊆ V and let H = R[U ] be an induced subgraph. b satisfying the guarantee of Lemma 54 with additive error bound Λρ Assume we have a synthetic graph H on any cut value w(S, U \S) for S ⊂ U. For any parameter ψ ≥ 10cexp Λρ where cexp = O(logc n), there exists an (ε, δ)-edge-DP algorithm CutFinder( H, ψ) (i.e., Algorithm 7) that outputs either a cut S ⊂ U with ρ(S) ≤ ρ(U \ S) or ∅, satisfying: 1. Sparsity: If S ̸= ∅, then w H (S, U \ S) ≤ ψρ(S). 2. Bicriteria Maximality: If there exists any S′ ⊂ U satisfying ρ(S′ ) ≤ ρ(U \ S′ ) and w H (S′ , U \ ψ ρ(S′ ) S′ ) ≤ cexp ρ(S′ ), the output S ̸= ∅ satisfies that ρ(S) ≥ csize , where csize = O(1). b ′ from H b to bound the dynamic Proof. We first construct a trimmed and capped proxy graph H ψ range of the edge weights. We define a minimum weight threshold θ = 10n and a maximum b ′ , we simply delete any edge e ∈ H b with weight we < θ, capacity bound Wmax = ψρ(U ). To form H and truncate any edge with we > Wmax to exactly Wmax . The ratio of the maximum to non-zero b ′ is therefore bounded by Wmax /θ = 10nρ(U ) ≤ poly(n). We then minimum edge weight in H b′ execute the deterministic demand-vector routine (Theorem 55, or Theorem 2.14 in [LS21]) on H

53

with a target sparsity threshold of 0.8ψ. If the algorithm in Theorem 55 fails to find a cut meeting this threshold, we output ∅; otherwise, we output the returned cut S. First, we assume the algorithm outputs S ̸= ∅ and prove the sparsity guarantee. By the guarantee of such cut in Theorem 55, w Hb ′ (S, U \ S) ≤ 0.8ψρ(S). We prove by contradiction that the b ′ would be at least cut S does not sever any capped edges. If it did, the weight of the cut in H Wmax = ψρ(U ). Since S is the smaller demand side, ρ(S) ≤ ρ(U )/2, which implies ψρ(U ) ≥ b′ 2ψρ(S) > 0.8ψρ(S), which leads to a contradiction. Thus, the cut S evaluates identically in H b except for the deleted small edges. The total weight of all deleted edges crossing the cut is and H naively bounded by θ · |S| · |U \ S| ≤ θnρ(S) = 0.1ψρ(S). Consequently, the uncut synthetic weight is bounded by w Hb (S, U \ S) ≤ w Hb ′ (S, U \ S) + 0.1ψρ(S) ≤ 0.9ψρ(S). Applying the additive error guarantee from Lemma 54, the true weight in H evaluates to: w H (S, U \ S) ≤ w Hb (S, U \ S) + Λρ ρ(S)   ψ ≤ 0.9ψρ(S) + ρ(S) ≤ ψρ(S). 10cexp Next, we establish the bicriteria maximality. Assume there exists an optimal sparse cut S′ satψ isfying w H (S′ , U \ S′ ) ≤ cexp ρ(S′ ). The oracle’s additive error guarantees that the weight of S′ in b is bounded by: the synthetic graph H   ψ ′ ′ ′ ′ ′ + Λ ρ ρ ( S ′ ). w Hb (S , U \ S ) ≤ w H (S , U \ S ) + Λρ ρ(S ) ≤ cexp By setting cexp = 4dexp (recall that dexp = polylog(n) is the internal expansion loss of in Theorem 55) and invoking the premise ψ ≥ 10cexp Λρ , we see that: ψ cexp

+ Λρ ≤

ψ ψ ψ + = 0.275 . 4dexp 40dexp dexp

Because the trimming and capping operations can only decrease the weight of an existing cut, b ′ satisfies that w b ′ (S′ , U \ S′ ) ≤ 0.275 ψ ρ(S′ ) ≤ 0.8 ψ ρ(S′ ). Under this the weight of S′ in H dexp dexp H condition, the bicriteria guarantee in Theorem 55 dictates that the returned cut S ̸= ∅ satisfies ρ(S′ ) ρ(S) ≥ dsize . Setting csize = dsize = O(1) concludes the utility proof. For the privacy proof, we note that Algorithm 7 does not consume more privacy budgets than the private spectral oracle (Assumption 1) as all trimming, capping, and the computations in Theorem 55 are deterministic post-processing steps applied exclusively to the (ε, δ)-edge-DP synthetic b given by the spectral primitive in Assumption 1. graph H We then integrate this demand-aware cut finder into a recursive decomposition framework. Because the performance metric scales with ρ(S) rather than |S|, we slightly generalize the classical recursion in Nanongkai and Saranurak [NS17] by replacing cardinalities with demand masses. As in [NS17], an auxiliary graph I will be used only in the analysis and need not be maintained by the executable algorithm. Lemma 57 (Properties of Algorithm 8). Given a global privacy budget (ε, δ) and a global failure probability β ∈ (0, 1), let Λρ (ε′ , δ′ , β′ ) be a uniform upper bound on the additive error of the private oracle in Lemma 54, when invoked with local parameters (ε′ , δ′ , β′ ). Let Dmax , Nmax , ε step , δstep , β step be the public quantities defined in Algorithm 8. For every target expansion parameter satisfying
ψ ≥ 10Λρ ε step , δstep , β step , (33) the following hold. 54

1. Algorithm 8 always terminates, outputs a disjoint partition of V ( H ), and satisfies (ε, δ)-edge-DP. 2. Deterministically, every root-to-leaf path contains at most Dmax private cut-finder invocations. 3. With probability at least 1 − β, every returned component Vi induces a (ψ, ρ)-expander, and the total weight of all inter-component edges is at most ψ ρ(V ( H ))1+o(1) . In particular, when cexp , csize = ρ(V ( H ))o(1) and ρ(V ( H )) = poly(n), we have Dmax = ρ(V ( H ))o(1) = no(1)

and

Nmax = n1+o(1) .

Thus, under the polynomial regularity assumed for Λρ , condition (33) has the asymptotic form    ε δ β e , , ψ ≥ Ω Λρ . n o (1) n o (1) n 1+ o (1) Proof. This proof is a demand-weighted analogue of the global expansion-decomposition analysis of Nanongkai and Saranurak [NS17, Section 5.2]. The hard depth cap in Algorithm 8 ensures termination and privacy on every transcript. We first analyze utility on the event that every invocation of CutFinder satisfies the guarantees of Lemma 56. For a graph J and a sparsity parameter φ, define   ∅ ̸ = X ⊊ V ( J ),   OPTρ ( J, φ) := max ρ( X ) : ρ( X ) ≤ ρ(V ( J ) \ X ), , (34)   w J ( X, V ( J ) \ X ) ≤ φρ( X ) where the maximum is defined to be zero when no such cut exists. As in [NS17], associate an auxiliary graph I with each recursive call. This graph is used only for analysis: • the root call is represented by ( H, H, 1); • a smaller-side child is represented by ( H ′ [S], H ′ [S], 1); • a larger-side child is represented by ( H ′ [V ( H ′ ) \ S], I, l ); and • a level-increment child is represented by ( H ′ , H ′ , l + 1). We claim that every analytical call ( H ′ , I, l ) made on the success event satisfies OPTρ ( I, 2ψl ) < sl .

(35)

For l = 1, every smaller side of a cut in I has demand at most ρ(V ( I ))/2 ≤ R/2 < s1 . This proves the invariant at the root and after every smaller-side reset. The invariant is unchanged along a larger-side recursive call because both I and l remain unchanged. It remains to consider a level increment. Such an increment occurs only when ρ(S) <

s l +1 . csize

2ψl +1 =

ψl . cexp

By the choice of the level parameters,

55

(36)

The bicriteria maximality guarantee of Lemma 56 therefore implies   ′ ψl ′ ≤ csize ρ(S) < sl +1 . OPTρ ( H , 2ψl +1 ) = OPTρ H , cexp This proves (35) inductively. Because s L ≤ 1 and all nonempty demand masses are positive integers, the invariant at level L implies OPTρ ( H ′ , 2ψL ) = 0 whenever the analytical anchor is I = H ′ . If CutFinder( H ′ , ψL ) returned a nonempty cut, its sparsity guarantee would make that cut ψL -sparse, and hence also 2ψL -sparse, a contradiction. Thus, on the success event, no call advances beyond level L. We next bound the depth of the recursion before the hard cap. Following [NS17], call the edge to the smaller-side child a left edge, the edge to the larger-side child a right edge, and a levelincrement edge a down edge. Along any root-to-leaf path, there are at most ⌈log2 R⌉ left edges, because every left edge replaces the current graph by a subgraph of at most half its demand mass. Between consecutive left edges there are at most L down edges. It remains to bound consecutive right edges. Fix a maximal sequence of right edges at one level l, beginning immediately after the root, a left edge, or a down edge. At the beginning of this sequence, the analytical anchor equals the current graph; denote it by H1 . Write Hi+1 = Hi [V ( Hi ) \ Si ],

Xj =

j [

Si ,

r = ρ(V ( H1 )).

i =1

Each cut in this sequence satisfies ρ ( Si ) ≥

s l +1 , csize

ρ ( Si ) ≤

ρ(V ( Hi )) , 2

w Hi (Si , V ( Hi ) \ Si ) ≤ ψl ρ(Si ).

(37)

The sets Si are disjoint, and every edge crossing ( X j , V ( H1 ) \ X j ) is contained in one of the cuts removed so far. Consequently, j

w H1 ( X j , V ( H1 ) \ X j ) ≤ ∑ w Hi (Si , V ( Hi ) \ Si ) ≤ ψl ρ( X j ).

(38)

i =1

Set a :=

s l +1 , csize

g := csize Rσ ,

so that ga = sl . Suppose first that r ≤ 3sl . Then fewer than 3csize Rσ right edges are possible, since otherwise the disjoint removed sets would have total demand at least 3csize Rσ a = 3sl ≥ r, while the current right-side component has positive demand. Now suppose that r > 3sl . If there were at least ⌈ g⌉ right edges, let j be the first index for which x := ρ( X j ) ≥ sl ,

x − : = ρ ( X j −1 ) < s l .

Since S j is the smaller side in Hj , we have x = x − + ρ(S j ) ≤ x − +

r − x− r + x− r + sl 2r = < < . 2 2 2 3 56

If x ≤ r/2, then (38) shows that X j is a 2ψl -sparse smaller side with demand at least sl . If x > r/2, let Y = V ( H1 ) \ X j . Then ρ (Y ) = r − x >

r > sl 3

and

x ≤ 2ρ(Y ).

Using (38), w H1 (Y, V ( H1 ) \ Y ) ≤ ψl x ≤ 2ψl ρ(Y ). Thus, in either case, H1 contains a 2ψl -sparse smaller side of demand at least sl , contradicting the invariant (35). Therefore every such sequence contains fewer than Γ = ⌈3csize Rσ ⌉ right edges. There are at most 1 + ⌈log2 R⌉ blocks separated by left edges, and each block contains at most L level segments. Hence every root-to-leaf path contains at most
(1 + ⌈log2 R⌉) 1 + L(1 + Γ) = Dmax recursive nodes at which a private oracle can be invoked. Therefore, on the success event, the natural recursion terminates before the hard depth cap is triggered. We now establish expansion. On the success event, a non-singleton component H ′ = G [Vi ] is returned only when CutFinder( H ′ , ψl ) outputs ∅. By the contrapositive of the bicriteria maximality guarantee in Lemma 56, no cut S′ ⊊ Vi satisfies w H ′ (S′ , Vi \ S′ ) ≤

ψl min{ρ(S′ ), ρ(Vi \ S′ )}. cexp

By the definition of ψl , ψl L−l ≥ ψ. = ψ cbexp cexp

(39)

It follows that G [Vi ] is a (ψ, ρ)-expander. Singleton components satisfy this property trivially. To bound the total weight of inter-component edges, consider every recursive split returning a nonempty cut S at level l. By Lemma 56, w H ′ (S, V ( H ′ ) \ S) ≤ ψl ρ(S) ≤ ψ1 ρ(S). Charge this weight to the demand units in the smaller side S. Any fixed unit of demand can be charged at most O(log R) times, because after each charge it lies in a recursive component whose total demand is at most half that of its preceding component. Therefore,

∑

w H ′ (S, V ( H ′ ) \ S) ≤ O(ψ1 R log R)

inter-component cuts

  L = O ψR log R cbexp

= ψ R 1+ o (1) . The last equality follows from L = O(1 + 1/σ ) and  q  L cbexp = exp O log R log cbexp + log cbexp = R o (1) . 57

It remains to prove privacy and bound the failure probability. The hard cap ensures unconditionally that at most Dmax private oracle calls occur along any root-to-leaf path. Conditioned on any fixed transcript preceding a recursion depth, the active recursive subproblems are induced on pairwise disjoint vertex sets. Hence a single input-edge change affects at most one active subproblem at that depth, and the calls at that depth satisfy (ε step , δstep )-DP by parallel composition. Sequential composition (Lemma 7) across at most Dmax depths gives
Dmax ε step , Dmax δstep = (ε, δ). The hard-cap and level-cap return operations are post-processing and consume no additional privacy budget. Thus the algorithm is (ε, δ)-edge-DP on every transcript, independently of the oracle’s utility behavior. At any fixed recursion depth, the active nonempty components have disjoint vertex sets, so there are at most |V ( H )| oracle calls. The deterministic total number of calls is therefore at most Nmax = |V ( H )| Dmax . Each adaptive invocation has conditional utility-failure probability at most β step . Independence is not required: a conditional union bound gives Pr[some oracle invocation fails] ≤ Nmax β step = β. Finally, for every level l, ψl ≥ ψL = ψcexp . Condition (33) therefore implies
ψl ≥ 10cexp Λρ ε step , δstep , β step , so Lemma 56 applies simultaneously to all calls on the success event. Combining the preceding expansion, depth, and charging arguments proves all claimed utility guarantees with probability at least 1 − β.

7.4

Private Cut Approximation via Recursive Expander Decomposition

Here, we synthesize the preceding mechanisms into a unified multi-round recursive sparsification algorithm. By repeatedly factoring out demand-aware expanders, the residual graph is driven to a highly sparse state parameterized completely by the spectral error Π (in Lemma 54) and the total number of iterative rounds T. The final guarantee of our framework is formalized as follows: Theorem 58. Assuming access to a private spectral primitive with error interface Π(n, d, ε, δ) (Assumption 1), for any n-node unweighted simple graph G = (V, E), privacy parameters (ε, δ), multiplicative error parameter γ ∈ (0, 1), and any positive integer T ≤ poly(n), there exists an (ε, δ)-edge-DP polynomial-time e such that, with high probability, for all algorithm that outputs a non-negative weighted synthetic graph G cuts C ⊆ V:  2 1/3 ! n n M T e wG (C ) − wGe (C ) ≤ γwG (C ) + O + , (40) ε ε2 γ where the edge count MT is obtained by iterating the dynamical system     ! 1+ o (1) n M ε δ t e Mt + 1 = O Π n, max 1, , , T , γ n T T for t = 0, 1, . . . , T − 1, with initial condition M0 = n2 . 58

Before we prove Theorem 58, to better formalize the recursive framework, we recall all mechanisms or modular subroutines developed in the preceding sections. Specifically, 1. We denote the subroutine for generating the demand vector ρ from Lemma 52 as BuildDemand, and the demand-sensitive expander decomposition (i.e., Algorithm 8) from Lemma 57 as DemandExpDecomp, which includes CutFinder (Algorithm 7) as a subroutine. 2. Crucially, we formalize the private synthesis process established in Lemma 54 as the subroutine SyntheticOracle, which encompasses the local port graph construction and executing the generic private spectral primitive (Assumption 1). e (n + (n2 M )1/3 ) additive error cut release oracle in Theorem 37 (Sec3. We also denote the O tion 6) as CutRelease( G, M, ε, δ). With these primitives defined, we present the main recursive sparsification in Algorithm 9. Proof. (Of Theorem 58.) We analyze the utility, dynamical recurrence, privacy, and probability bounds consecutively to establish Theorem 58. For any cut C ⊆ V, every original unweighted edge e ∈ E is either absorbed inside some component U ∈ Pt at a specific round t, or it survives all T rounds to become a residual edge in R T . Therefore, we can decompose the cut value of C (in the original graph) as follows: T −1

wG (C ) = ∑

∑ wR [U] (C ∩ U, U \ C) + wR (C). T

t

(41)

t=0 U ∈Pt

e the estimated cut size evaluates to: On the other hand, by the definition of the out G, T −1

wGe (C ) = ∑

∑ w Hb (C ∩ U, U \ C) + wRb (C),

t=0 U ∈Pt

t,U

T

(42)

b T is the output of the terminal release mechanism. where R For any internal component U ∈ Pt , according to Lemma 57, the subgraph Rt [U ] is an (ψt , ρt )expander (eq. (6)). Invoking the demand-sensitive oracle error (Lemma 54) and substituting the expansion bound w Rt [U ] ≥ ψt min{ρt (C ∩ U ), ρt (U \ C )}, we bound the local absolute deviation. To leave room for the terminal relative error, we configure the internal spectral release to operate at target accuracy γinternal = γ/2: w Rt [U ] − w Hbt,U ≤ Λt min{ρt (C ∩ U ), ρt (U \ C )}

≤

Λt γ w (C ∩ U, U \ C ) ≤ wRt [U ] (C ∩ U, U \ C ). ψt Rt [U ] 2

(43)

Summing Eq. (43) across all components U and rounds t, the aggregated error over all internal releases is then bounded by: T −1

∑ ∑ wR [U] − w Hb t

t=0 U ∈Pt

t,U

γ T −1 ∑ wRt [U] (C ∩ U, U \ C) 2 t∑ =0 U ∈Pt γ ≤ w G ( C ). 2

≤

59

(44)

To determine the final error of the terminal residual graph R T , we map the trajectory of the e (n) (Lemma 52) and substituting ψt , the residual edge sequence Mt . Utilizing the fact ρt (V ) ≤ O recurrence across T rounds is governed by the spectral error interface Π evaluated at the deep recursion budgets ε step = ε/(8Tno(1) ) and δstep = δ/(8Tno(1) ). Crucially, the expander decomposition incurs an no(1) penalty on both the residual edges and the privacy parameters (Lemma 57). Invoking Assumption 1 again, the no(1) shrinkage in privacy parameters inflates the error Π by at most an no(1) multiplicative overhead. We explicitly extract and incorporate this penalty:       M ε δ t 1+ o (1) 1 + o ( 1 ) − 1 e Π n, max 1, Mt+1 = ψt ρt (V ) ≤O , , n γ T . n T T Starting from the initial dense graph configuration M0 = n2 , this recursive process produces the terminal residual edge count MT after T iterations. We then process R T via the relative terminal release mechanism CutOracle (Theorem 37). Allocating privacy budgets ε terminal = ε/2 and δterminal = δ/2, and setting the terminal multiplicative error parameter to γoracle = γ/2, the oracle guarantees:  1/3 ! 2M n γ n T e w RT (C ) − w Rb T (C ) ≤ w RT (C ) + O + . (45) 2 ε/2 (ε/2)2 (γ/2)
e (n/ε + n2 MT /(ε2 γ) 1/3 ). Finally, the additive bias simplifies to α T = O Combining the internal absorption (44) with the terminal deviation (45), and exploiting the fact that w RT (C ) ≤ wG (C ) since R T is a subgraph of G, we bound the global additive error for any cut C: γ  γ wG (C ) − wGe (C ) ≤ wG (C ) + w RT (C ) + α T 2 2  2 1/3 ! n M n T e + , ≤ γwG (C ) + O ε ε2 γ which concludes the utility proof in Theorem 58. The overall differential privacy holds under adaptive and parallel composition. The total privacy budget ε is partitioned into four allocations: ε/2 dedicated to the terminal CutOracle algorithm, and the remaining ε/2 distributed evenly across the T rounds, allocating 4ε round = 4ε/(8T ) per round. Within any round t, by Lemma 53, the gadget construction strictly limits ℓ1 -sensitivity to O(1), consuming ε round under the Laplace mechanism. The recursion steps in Algorithm 8 isolates original edges to sub-problems of depth bounded by no(1) . By applying basic composition over this no(1) depth, we allocate a local privacy budget of ε step = ε round /no(1) to each decomposition step, thereby collectively consuming ε round globally across the depth under basic composition. The subsequent internal spectral releases operate on the mutually disjoint vertex subsets U ∈ Pt ; thus, via parallel composition, they collectively consume only ε round globally across the round. The allocation for budget δ over each round is identical. By basic composition over T rounds and the final step with CutOracle, the algorithm preserves (ε, δ)-DP. Finally, we bound the global failure probability. Failure events encompass degree noise violations, hash collisions exceeding bounds, spectral primitive aborts, and terminal oracle failures. In any given round t, the recursive expander decomposition tree produces at most n1+o(1) internal components. Consequently, there are at most n1+o(1) ≤ n2 local invocations of the hash mappings, spectral oracles, and cut-finders per round. By distributing the global failure probability β and allocating β round = β/(8Tn2 ) to each individual sub-routine invocation across all T rounds (and 60

allocating β/2 to the final terminal release), the sum of all failure probabilities over the entire pipeline is bounded by T · n2 · β round + β/2 ≤ β/8 + β/2 < β, completing the proof. With the generic reduction established in Theorem 58, we can now plug in the bootstrapped fourth-power spectral primitive (Theorem 32) developed in Section 5.2 to break the O(n1.25 ) additive error barrier. Lemma 59 (A square-root contraction recurrence). Let x0 , b, c ≥ 0, and suppose that x t +1 ≤ for every t ≥ 0. Then

√ 1 xt + b xt + c 4

x t ≤ 2− t x 0 + 2 ( b 2 + c )

for every t ≥ 0.

√ Proof. For every x ≥ 0, it is easy to verify that b x ≤ 41 x + b2 . Consequently, xt+1 ≤ 12 xt + b2 + c. Iterating this inequality yields t −1

x t ≤ 2− t x 0 + ( b 2 + c ) ∑ 2− j ≤ 2− t x 0 + 2 ( b 2 + c ), j =0

as claimed. The following corollary utilize Lemma 59 to solve the recursive dynamical system driving by our spectral primitive (Theorem 32) to its optimal fixed point. e (n13/12+o(1) ) Additive Error). For any n-node unCorollary 60 (Private Cut Approximation with O weighted simple graph G = (V, E), privacy parameters ε ∈ (0, 1), δ ∈ (0, 1/2) and multiplicative error parameter γ ∈ (0, 1/4), there exists an (ε, δ)-edge-DP polynomial-time algorithm that outputs a non-negative e such that, with high probability, simultaneously for all cuts C ⊆ V, weighted synthetic graph G ! 13/12+o (1) n eδ wG (C ) − wGe (C ) ≤ γwG (C ) + O . εγ7/6 Proof. Define γ̄ := min{γ, 1/8},

δ̄ := min{δ, 1/4}.

It suffices to construct an (ε, δ̄)-edge-DP mechanism with multiplicative error γ̄. Indeed, δ̄ ≤ δ, γ̄ ≤ γ, and γ̄−7/6 = O(γ−7/6 ). Assume n ≥ 2, since the claim is immediate for n = 1, and fix the number of recursive sparsification rounds in advance as T := ⌈log2 n⌉ . We apply Theorem 58 with parameters (ε, δ̄, γ̄, T ) and instantiate its spectral primitive using Theorem 32. For every t, define   Mt . dt := max 1, n In particular, d0 = n. Under privacy parameters (ε/T, δ̄/T ), Theorem 32 gives 

ε δ̄ Π n, dt , , T T

 e =O δ̄

! √ 1/8 T 3/8 1/4 q1/4 T 3/4 q dt T n1/8 d1/2 n T t + + . √ + εq ε ε3/8 ε3/4

61

The recurrence in Theorem 58 contains one additional multiplicative factor T. Therefore, after dividing the residual edge bound by n, we obtain # !" 11/8 n1/8 d1/2 q1/8 o (1) 3/2 d 7/4 n1/4 q1/4 2 T n T T T t t e . (46) d t +1 ≤ 1 + O + + + √ δ̄ εq ε γ̄ ε3/8 ε3/4 The additive 1 comes from the dt+1 = max{1, Mt+1 /n}. Because T = O(log n), all powers of T, all polylogarithmic losses, and all no(1) losses in (46) can be bounded by a public factor   e n o (1) , L=O L ≥ 1. δ̄ We enlarge L, if necessary, by an additional polylogarithmic factor so that the choice of q below also satisfies the lower-bound requirement on q in Theorem 32. Thus (46) implies " # 1/8 1/4 q1/4 n1/8 d1/2 q dt L n 1 t d t +1 ≤ 1 + B √ + , B := . (47) + + 3/8 3/4 εq ε γ̄ ε ε We now choose the tunable parameter as:  q := e In particular, q = O δ̄

 o (1)  n εγ̄2

 16B2 . ε

(48)

. hus, q is not asserted to be just polylogarithmic in 1/ε and 1/γ̄. Its

polynomial dependence on these parameters is displayed explicitly. By eq. (48), we have √Bεq ≤ 14 . Define Bn1/8 q1/8 b := ε3/8 and B Bn1/4 q1/4 + . c := 1 + 3/4 ε ε Then (47) becomes p 1 dt+1 ≤ dt + b dt + c. 4 Applying Lemma 59 gives d t ≤ 2− t d 0 + 2 ( b 2 + c ). (49) It remains to bound b2 + c. Since B ≥ 1 and ε ≤ 1, the choice (48) gives q ≤ 17B2 /ε. Consequently, b2 =

B2 n1/4 q1/4 =O ε3/4



n1/4 B5/2 ε

 ,

and similarly, Bn1/4 q1/4 =O ε3/4



n1/4 B3/2 ε

Moreover, B 1+ ≤ O ε







≤O

n1/4 B5/2 ε

62

n1/4 B5/2 ε

 .

 .

Therefore, 

2

b +c =O

n1/4 B5/2 ε

 .

(50)

Because T = ⌈log2 n⌉, we have 2−T d0 ≤ 1. Combining (49) and (50) yields  dT = O

n1/4 B5/2 ε





=O

n1/4 L5/2 εγ̄5/2

 e =O δ̄

n1/4+o(1) εγ̄5/2

! .

e (no(1) ). Since MT ≤ nd T , it follows that Here we used L5/2 = O δ̄ ! 5/4+o (1) n e MT = O . δ̄ εγ̄5/2

(51)

Finally, Theorem 58, instantiated with multiplicative parameter γ̄, gives additive error  2 1/3 ! n n M T e O + . δ̄ ε ε2 γ̄ Substituting (51), 

n2 M ε2 γ̄

T

1/3

 e  =O δ̄

n2 n5/4+o(1) ε3 γ̄5/2+1

!1/3  e =O δ̄

n13/12+o(1) εγ̄7/6

! .

Because n13/12 ≥ n, γ̄ ≤ 1, and ε ≤ 1, this term also absorbs the n/ε term. Thus the algorithm satisfies ! 13/12+o (1) n e wG (C ) − wGe (C ) ≤ γ̄wG (C ) + O δ̄ εγ̄7/6 simultaneously for all cuts C. e =O e δ . This gives Finally, γ̄ ≤ γ, γ̄−7/6 = O(γ−7/6 ), and O δ̄ eδ wG (C ) − wGe (C ) ≤ γwG (C ) + O

n13/12+o(1) εγ7/6

! ,

as required. The algorithm is polynomial-time because T = O(log n), the chosen value of q is polynomial in the displayed accuracy and privacy parameters up to an no(1) factor, and both Theorem 58 and Theorem 32 provide polynomial-time implementations.

8

Hardness of Graph Spectral Estimation with Approximate DP

Here we prove that, under edge-level differential privacy, any algorithm for√estimating the Laplacian of an√unweighted graph on n vertices must incur a spectral error of Ω( n). This matches the e ( n) upper bound, showing that the improvement to O e ((nd)1/4 ) achieved by our private trivial O spectral primitive √ (Theorem 29) is not an artifact of loose analysis but rather an intrinsic barrier: e ( n) additive error is, in fact, asymptotically optimal in the worst case. the trivial O

63

Theorem 61 (Lower bound for spectral release). Fix a constant ε > 0. There exists a constant c = 1 c(ε) > 0 such that the following holds for all sufficiently large n: let δ ≤ 8(1+ , for any (ε, δ)-edge-DP eε )

algorithm that releases matrix11 Y on input graph G, there exists some connected graph G with m = Θ(n) and maximum degree d = Θ(n), the algorithm must have √ Pr[∥Y − LG ∥2 ≥ c n] > 0.49.

8.1

The Hard Family and Reconstruction

To prove this theorem, we first introduce the construction of the family of hard instances. Let the vertex set be V = {0, 1, 2, . . . , n − 1}. Each hard instance consists of a fixed, public path 0 − 1 − 2 − · · · − ( n − 1) and a private k-star centered 0. Formally, let U = {2, 3, . . . , n − 1}. For every set of vertices S ⊂ U of size k, we define  GS = B ∪ {0, i } : i ∈ S , where B denotes the edge set of the public path. Note that every graph GS is simple and connected. It has exactly m = (n − 1) + k edges: n − 1 path edges and k private star edges. We denote the set of all possible GS as the family Fn,k . The next lemma demonstrates how spectral approximation exposes private edges. Specifically, for any two graphs GS and GT from this family, the symmetric difference between their edge sets can be bounded by their spectral distance. Since both graphs share the identical public path, this edge difference stems solely from their private stars. Lemma 62 (Spectral separation). For any two k-subsets S, T ⊆ U, q ∥ LGS − LGT ∥2 ≥ |S△ T |. Proof. If S = T, the claimed inequality is trivial. Thus we assume S ̸= T. Let ai = 1S (i ) − 1 T (i ), for every i ∈ U. By S ̸= T we have a ̸= 0. Since |S| = | T | = k,

∑ ai = 0.

i ∈U

Also ai ∈ {−1, 0, 1}, therefore

∥ a∥22 = ∑ a2i = |S△ T |. i ∈U

The path B is common to both graphs, thus we have: LGS − LGT = ∑ ai L{0,i} . i ∈U

Define a vector z ∈ Rn by 1 z0 = √ , 2

zi = − √

ai 2 ∥ a ∥2

( i ∈ U ),

z1 = 0.

11 We note that the theorem does not restrict that the output is actually a graph. Therefore the lower bound applies to

arbitrary symmetric matrix releases.

64

Note z is a unit vector since

∥z∥22 =

1 1 + a2i = 1. 2 2 ∥ a∥22 i∑ ∈U

For an edge {0, i }, z⊤ L{0,i} z = (z0 − zi )2 . Hence z⊤ ( LGS − LGT )z = ∑ ai (z0 − zi )2 i ∈U

 2 ai 1 = ∑ ai 1 + 2 i ∈U ∥ a ∥2

=

1 1 1 a2i + a3 . ai + ∑ ∑ 2 ∑ i 2 i ∈U ∥ a ∥ 2 i ∈U 2 ∥ a ∥ 2 i ∈U

Because ai ∈ {−1, 0, 1}, we have a3i = ai . Since ∑i ai = 0, both the first and third terms vanish. Therefore q ⊤ z ( LGS − LGT )z = ∥ a∥2 = |S△ T |. Since z is a unit vector,

∥ LGS − LGT ∥2 ≥ z⊤ ( LGS − LGT )z =

q

| S △ T |.

The next lemma shows that the private star of the input graph can be partially recovered, provided we are given a matrix that spectrally approximates the graph with a small error. Suppose an algorithm outputs a matrix Y. Define a nearest-neighbor decoder Sb(Y ) ∈ arg

min

T ⊆U, | T |=k

∥Y − L GT ∥ 2 .

Ties are broken arbitrarily. This decoder is not required to be computationally efficient. Lower bounds may use arbitrary post-processing of the algorithm output. Lemma 63. If S ⊆ U, |S| = k, and

∥Y − LGS ∥2 ≤ α, then

|S△Sb(Y )| ≤ 4α2 .

Proof. By the definition of Sb(Y ), Y − LGSb(Y)

2

≤ ∥Y − LGS ∥2 ≤ α.

Therefore, by the triangle inequality, LGS − LGSb(Y)

2

≤ ∥ LGS − Y ∥2 + Y − LGSb(Y)

Lemma 62 gives q

|S△Sb(Y )| ≤ LGS − LGSb(Y)

Squaring yields the claim. 65

2

≤ 2α.

2

≤ 2α.

The next corollary converts a high-probability spectral guarantee into an average reconstruction guarantee. Corollary 64. Let S be uniformly random among all k-subsets of U, let Y = A( GS ), and let Sb = Sb(Y ). Suppose that, for every S,   Pr ∥Y − LGS ∥2 ≤ α ≥ 1 − β. Then

  E |S△Sb| ≤ 4α2 + 2βk.

Moreover, since |S| = |Sb| = k,     E |S \ Sb| = E |Sb \ S| ≤ 2α2 + βk. Proof. On the success event ∥Y − LGS ∥2 ≤ α, Lemma 63 gives |S△Sb| ≤ 4α2 . On the failure event, we use the trivial bound |S△Sb| ≤ 2k, because both sets have size k. Since the failure probability is at most β for every fixed S, it is also at most β when S is uniform. Hence   E |S△Sb| ≤ 4α2 + 2βk. Finally, since |S| = |Sb| = k, the number of false negatives equals the number of false positives: 1 |S \ Sb| = |Sb \ S| = |S△Sb|. 2 This yields the second claim.

8.2

Reconstruction violates Approximate-DP

The previous section says that small spectral error reconstructs the hidden star support. We now show that such reconstruction violates (ε, δ)-DP. We first record the two-edge version of differential privacy. Lemma 65. Let A be (ε, δ)-edge-DP. If two graphs G, H differ in at most two edge edits, then for every event E , Pr[A( G ) ∈ E ] ≤ e2ε Pr[A( H ) ∈ E ] + (1 + eε )δ. Proof. Choose an intermediate graph G ′ such that G is edge-neighboring to G ′ and G ′ is edgeneighboring to H. Applying DP twice gives Pr[A( G ) ∈ E ] ≤ eε Pr[A( G ′ ) ∈ E ] + δ

≤ eε (eε Pr[A( H ) ∈ E ] + δ) + δ = e2ε Pr[A( H ) ∈ E ] + (1 + eε )δ.

For a fixed vertex i ∈ U, define two distributions over private sets:

Di1 = uniform over all k-subsets S ⊆ U with i ∈ S, Di0 = uniform over all k-subsets S ⊆ U with i ∈ / S. The distributions Di1 and Di0 differ only by the membership of the single private edge {0, i }. More precisely, they can be coupled so that the corresponding graphs differ in two edge edits: one deletes a star edge {0, j} and adds the other star edge {0, i }. 66

Lemma 66. Let A be (ε, δ)-edge-DP. Fix i ∈ U and let Ei be any event depending on the output. Then PrS∼D1 [A( GS ) ∈ Ei ] ≤ e2ε PrS∼D0 [A( GS ) ∈ Ei ] + (1 + eε )δ. i

i

Proof. We give an explicit coupling. Sample T ∼ Di0 uniformly, then sample j ∈ T uniformly, and set S = T \ { j} ∪ {i }. Then S is uniform over Di1 . Indeed, for any fixed S with i ∈ S, it can arise by choosing T = S \ {i } ∪ { j} for some j ∈ U \ S, and there are N − k such choices. Since ( N k−1) = Nk−k ( Nk−−11), each such S is produced with probability NN−−1 k = N1−1 . This concludes that S is uniform over Di1 . ( k )k

( k −1 )

For every coupled pair (S, T ), the graphs GS and GT differ by exactly two private star edges: remove {0, j} and add {0, i }. Lemma 65 therefore gives Pr[A( GS ) ∈ Ei ] ≤ e2ε Pr[A( GT ) ∈ Ei ] + (1 + eε )δ. Averaging over the coupling proves the lemma. We now choose the event Ei to be the event that the decoder claims the private edge {0, i } is present, i.e., Ei = {Y : i ∈ Sb(Y )}. We define p1i = Pr[i ∈ Sb(Y ) | i ∈ S],

p0i = Pr[i ∈ Sb(Y ) | i ∈ / S ],

where S is uniformly random among all k-subsets of U and Y = A( GS ). Lemma 66 gives, for each i ∈ U, p1i ≤ e2ε p0i + (1 + eε )δ. (52) On the other hand, reconstruction accuracy implies that p1i is large on average and p0i is small on average. Lemma 67. Let S be uniformly random among all k-subsets of U, let Y = A( GS ), and let Sb = Sb(Y ). Suppose that, for every S,   Pr ∥Y − LGS ∥2 ≤ α ≥ 1 − β. Then

and

1 2α2 , p1i ≥ 1 − β − ∑ N i ∈U k 1 βk + 2α2 p0i ≤ . ∑ N i ∈U N−k

Proof. The expected number of false negatives is E[|S \ Sb|] = ∑ Pr[i ∈ S and i ∈ / Sb] i ∈U

= ∑ Pr[i ∈ S]Pr[i ∈ / Sb | i ∈ S] i ∈U

= By Corollary 64,

k (1 − p1i ). N i∑ ∈U

E[|S \ Sb|] ≤ 2α2 + βk.

67

Therefore

k (1 − p1i ) ≤ 2α2 + βk, N i∑ ∈U

which rearranges to

1 2α2 p1i ≥ 1 − β − . ∑ N i ∈U k

Similarly, the expected number of false positives is E[|Sb \ S|] = ∑ Pr[i ∈ / S and i ∈ Sb] i ∈U

= ∑ Pr[i ∈ / S]Pr[i ∈ Sb | i ∈ / S] i ∈U

= Again using Corollary 64,

N−k p0i ≤ 2α2 + βk. N i∑ ∈U

which rearranges to

8.3

N−k p0i . N i∑ ∈U

βk + 2α2 1 0 ≤ . p i N i∑ N−k ∈U

Proof of Theorem 61

With the tools developed in the √ previous sections, we are now ready to prove the following lemma, which further derives the Ω( n) lower bound for DP spectral release. Lemma 68. Fix ε > 0 and 0 < β < 1/2. Let N = n − 2, let 1 ≤ k < N/2, and consider the connected graph family Fn,k defined in Section 8.1. Suppose A is an (ε, δ)-edge-DP algorithm that outputs a symmetric matrix Y, and suppose that, for every G ∈ Fn,k ,   Pr ∥Y − LG ∥2 ≤ α ≥ 1 − β. Then 1−β−

2α2 βk + 2α2 ≤ e2ε + (1 + eε )δ. k N−k

(53)

In particular, for every constant ε > 0 and every constant failure probability β < 1/2, by choosing k = ⌊ρn⌋ for a sufficiently small constant ρ = ρ(ε, β) > 0, every (ε, δ)-edge-DP algorithm with negligible δ = o (1) must incur √ α = Ω( n) on some connected graph with m = Θ(n). Proof. For each i ∈ U, inequality (52) gives p1i ≤ e2ε p0i + (1 + eε )δ.

68

Averaging over i ∈ U yields 1 1 p1i ≤ e2ε ∑ p0i + (1 + eε )δ. ∑ N i ∈U N i ∈U Lemma 67 lower bounds the left-hand side and upper bounds the right-hand side, giving βk + 2α2 2α2 ≤ e2ε + (1 + eε )δ. k N−k

1−β−

This proves (53). Consequently, if we assume: e2ε

βk 1−β ≤ N−k 4

where β ≤ 1/2, then 1−β− Therefore, α2 ≥

δ≤

and

1 1−β ≤ , 8(1 + e ε ) 4(1 + e ε )

(54)

2α2 1 − β 2e2ε α2 1 − β ≤ + + . k 4 N−k 4

1−β = Ωε,β,k/N (n). 4 (1/k + e2ε /( N − k ))

(55)

Take k = ⌊ρN ⌋, where ρ > 0 is a sufficiently small constant depending only on ε and β so that
the first inequality in (54) holds for all large n. Substituting k = ⌊ρN ⌋, the term 1/k + e2ε /( N − k ) becomes Θ(1/N ) = Θ(1/n). The bound (55) then gives α2 = Ω(n) Since m = n − 1 + k = Θ(n), this completes the proof. Proof of Theorem 61. It is enough to show that for any constants ε > 0 and β < 1/2, there exists 1 c = c(ε, β) > 0 such that, for all sufficiently large n, no (ε, δ)-edge-DP algorithm with δ = 8(1+ eε ) can output Y with √ Pr[∥Y − LG ∥ ≤ c n] ≥ 1 − β. on every connected n-vertex graph G. Choose k = ⌊ρ(n − 2)⌋ for a sufficiently small constant ρ = ρ(ε, β) > 0, and apply Lemma 68. √ The hard graphs have m = n − 1 + k = Θ(n) edges and are connected. The lemma gives α ≥ c′ n for some constant c′ = c′ (ε, β, ρ) > 0. Taking c < c′ gives the contradiction.

Acknowledgments. We are very grateful to Mina Dalirrooyfard and Jalaj Upadhyay for their insightful discussions on related topics prior to the start of this project.

69

References [ACD+ 25]

Anders Aamand, Justin Y Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Breaking the n{1.5} additive error barrier for private and efficient graph sparsification via private expander decomposition. In Forty-second International Conference on Machine Learning, 2025.

[AU19]

Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. In Advances in Neural Information Processing Systems, pages 13378–13389, 2019.

[BBDS12]

Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The JohnsonLindenstrauss transform itself preserves differential privacy. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 410–419. IEEE, 2012.

[BCSZ18]

Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. Revealing network structure, confidentially: Improved rates for node-private graphon estimation. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 533–543. IEEE Computer Society, 2018.

[BEK21]

Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In International Conference on Machine Learning, pages 1136–1146. PMLR, 2021.

[BG17]

Nikhil Bansal and Anupam Gupta. Potential-function proofs for first-order methods. arXiv preprint arXiv:1712.04581, 2017.

[Bub15]

Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.

[CAEL+ 22] Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz Medina, David Saulpic, Chris Schwiegelshohn, and Sergei Vassilvitskii. Scalable differentially private clustering via hierarchically separated trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 221–230, 2022. [CDFZ26]

Rishi Chandra, Michael Dinitz, Chenglin Fan, and Zongrui Zou. Differentially private algorithms for graph cuts: A shifting mechanism approach and more. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5688– 5728. SIAM, 2026.

[CFL+ 22]

Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. Near-optimal correlation clustering with privacy. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.

[Che52]

Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493–507, 1952.

70

[DGU+ 25] Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang, and Samson Zhou. On the price of differential privacy for hierarchical clustering. In 13th International Conference on Learning Representations, ICLR 2025, pages 99052–99083. International Conference on Learning Representations, ICLR, 2025. [DMN23]

Mina Dalirrooyfard, Slobodan Mitrovic, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. Advances in Neural Information Processing Systems, 36:24947–24965, 2023.

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC, pages 265–284, 2006. [DR14]

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.

[DRV10]

Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proc. of the 51st Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 51–60, 2010.

[DSZ+ 21]

Xiaofeng Ding, Shujun Sheng, Huajian Zhou, Xiaodong Zhang, Zhifeng Bao, Pan Zhou, and Hai Jin. Differentially private triangle counting in large graphs. IEEE Transactions on Knowledge and Data Engineering, 34(11):5278–5292, 2021.

[Dur19]

Rick Durrett. Probability: Theory and Examples. Cambridge University Press, 5 edition, 2019.

[EKKL20]

Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–578. SIAM, 2020.

[GLM+ 10] 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. Society for Industrial and Applied Mathematics, 2010. [GRU12]

Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of cryptography conference, pages 339–356. Springer, 2012.

[HH+ 26]

Yin He, Zihan Hu, et al. Harmonizing semantic and collaborative in llms: Reasoning-based embedding generator for sequential recommendation. arXiv preprint arXiv:2606.16703, 2026.

[HJ12]

Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.

[IEM+ 23]

Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, and Vahab Mirrokni. Differentially private hierarchical clustering with provable approximation guarantees. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 14353–14375. PMLR, 2023.

71

[IMC22]

Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Differentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1505–1519, 2022.

[KNRS13]

Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. In Amit Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 457–476. Springer, 2013.

[Lov93]

László Lovász. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.

[LS21]

Jason Li and Thatchaphol Saranurak. Deterministic weighted expander decomposition in almost-linear time. arXiv preprint arXiv:2106.01567, 2021.

[LSW15]

Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049–1065. IEEE, 2015.

[LSY03]

Greg Linden, Brent Smith, and Jeremy York. Amazon. com recommendations: Itemto-item collaborative filtering. IEEE Internet computing, 7(1):76–80, 2003.

[LUZ24]

Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1019–1049. SIAM, 2024.

[NS17]

Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o (n1/2-ε)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122–1129, 2017.

[PSM14]

Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.

[PX25]

Pan Peng and Hangyu Xu. Differentially private synthetic graphs preserving trianglemotif cuts. arXiv preprint arXiv:2507.14835, 2025.

[RSWZ26]

Sofya Raskhodnikova, Adam Smith, Connor Wagaman, and Anatoly Zavyalov. Local node differential privacy. arXiv preprint arXiv:2602.15802, 2026.

[SS11]

Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011.

[Tro12]

Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389–434, 2012.

[US19]

Jonathan R. Ullman and Adam Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3765– 3775, 2019. 72

[UUA21]

Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In International Conference on Artificial Intelligence and Statistics, pages 1171–1179. PMLR, 2021.

[Ver18]

Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.

[WHX+ 25] Minhao Wang, Yunhang He, Cong Xu, Zhangchi Zhu, Shuang Hao, Ning Liu, and Wei Zhang. Beyond semantic understanding: Preserving collaborative frequency components in llm-based recommendation. arXiv preprint arXiv:2508.10312, 2025. [ZEFD26]

Zongrui Zou, Alessandro Epasto, Chenglin Fan, and Rudrajit Das. Differentially private minimum spanning tree in euclidean graphs. In The 29th International Conference on Artificial Intelligence and Statistics, 2026.

[ZFD+ 25]

Zongrui Zou, Chenglin Fan, Michael Dinitz, Jingcheng Liu, and Jalaj Upadhyay. A generalized binary tree mechanism for private approximation of all-pair shortest distances. Advances in Neural Information Processing Systems, 38:36439–36468, 2025.

[ZLU25]

Zongrui Zou, Jingcheng Liu, and Jalaj Upadhyay. Almost linear time differentially private release of synthetic graphs. Proceedings of Machine Learning Research, 258:289– 297, 2025.

73

Algorithm 8: Demand-Aware Private Expander Decomposition (DemandExpDecomp) V(H)

Input: Graph H = G [U ] with public demand vector ρ ∈ Z≥1 , target sparsity ψ, privacy budgets (ε, δ), and failure probability β. Output: A disjoint partition P = {V1 , . . . , Vk } of V ( H ). 1 if H is a singleton then 2 return {V ( H )}; // Part 1: Global Initialization & Privacy Budgeting 3 R ← ρ (V ( H )) ; // Total global demand bexp ← 2cexp ; 4 c // Constant slack used in the depth proof  p 5 σ ← min 1, log cbexp / log R ; // Step decay rate n o (ℓ− 1 ) σ 6 L ← min ℓ ≥ 1 : (R /2 + 1) / R ≤1 ; // Maximum level 7 8

for i = 1 to L + 1 do si ← (R/2 + 1)/R(i−1)σ ;

// Pre-compute exact mass thresholds

9 Γ ← ⌈3csize Rσ ⌉ ;

// Maximum consecutive larger-side steps
Dmax ← (1 + ⌈log2 R⌉) 1 + L(1 + Γ) ; // Hard recursion-depth cap 11 Nmax ← |V ( H )| Dmax ; // Hard upper bound on oracle calls 12 ε step ← ε/Dmax , δstep ← δ/Dmax , β step ← β/Nmax ; 10

// Part 2:

The Recursive Core

13 Function RecDecomp( H ′ , l, d ): 14 if H ′ is a singleton then 15 16 17

18 19 20 21 22 23 24 25

return {V ( H ′ )};

if d ≥ Dmax or l > L then return {V ( H ′ )} ; // Hard cap; this branch is not reached on the success event ψ L − l +1 ψl ← cbexp ; 2 S ← CutFinder( H ′ , ψl , ρ, ε step , δstep , β step ); if S = ∅ then return {V ( H ′ )}; if ρ(S) ≥ sl +1 /csize then return RecDecomp( H ′ [S], 1, d + 1) ∪ RecDecomp( H ′ [V ( H ′ ) \ S], l, d + 1); else return RecDecomp( H ′ , l + 1, d + 1);

26 return RecDecomp( H, 1, 0);

74

Algorithm 9: Recursive Demand-Private Cut Approximation Input: Unweighted graph G = (V, E), privacy budgets (ε, δ), failure probability β, multiplicative error γ, recursion rounds T. c 1 Set R0 ← G, M0 ← n2 and denote by c exp = log n (Lemma 56); 2 Set ε round ← ε/ (8T ), δround ← δ/ (8T ), β round ← β/ (8Tn2 ); 3 for t = 0 to T − 1 do // Phase 1: Public Demand Generation (Lemma 52) 4 ρt ← BuildDemand( Rt , Mt , ε round , β round ) // Phase 2: Error and Threshold Calibration e (Π(n, Mt /n, ε round , δround )); 5 Λt ← O 6 γt ← γ/(2T ) ; 7 ψt ← Λt cexp no(1) /γt // Phase 3: Recursive Expander Decomposition (Lemma 57) 8 Pt ← DemandExpDecomp( Rt , ρt , ψt , ε round , δround , β round ) // Phase 4: Local Oracle Releases (Parallel Composition) 9 for each internal component U ∈ Pt do b t,U ← SyntheticOracle( Rt [U ], ρt , ε round , δround , β round ) 10 H 11 12

// Phase 5: Graph Deflation Rt+1 ← {e ∈ E( Rt ) : e crosses different components in Pt } Mt+1 ← ψt ρt (V )1+o(1)

// Phase 6: Terminal Sparse Graph Release 13 Hsparse ← CutRelease( R T , MT , ε/2, δ/2, β/2) ; e = Hsparse + ∑ T −1 ∑U ∈P H b t,U 14 return G t =0 t

75