Proof. The algorithm interacts with the private dataset \(D\) through two sequential queries, and we bound the total privacy leakage via basic composition (Lemma 2).

In Step 1, the algorithm releases the symmetric matrix \(\widetilde{Y} = M^q + W\). Since \(\widetilde{Y}\) is symmetric, its output space is uniquely determined by its \(n(n+1)/2\) upper-triangular entries (including the diagonal). The \(\ell_2\) sensitivity of these elements is indeed bounded by the Frobenius sensitivity of the full matrix \(M^q\): \[\sqrt{\sum_{1 \le i \le j \le n} \left(M^q_{i,j} - (M')^q_{i,j}\right)^2} \le \left\Vert M^q - (M')^q\right\Vert_F \le \Delta_q.\] Thus, by the Gaussian mechanism (Lemma 6), adding independent Gaussian noise \(\mathcal{N}(0, \sigma_1^2)\) calibrated to \(\sigma_1 = \Delta_q \sqrt{2\log(1.25/\delta_1)} / \varepsilon_1\) to the upper-triangular entries (and mirroring them to the lower triangle) guarantees \((\varepsilon_1, \delta_1)\)-differential privacy.

In Step 2, the algorithm extracts the projection matrix \(P\) and its orthogonal basis \(U\) as a function solely of the privatized matrix \(\widetilde{Y}\). By the post-processing property of differential privacy (Lemma 1), 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^\top M U\) confined within the fixed public subspace spanned by \(U\). To bound the \(\ell_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^\top (M - M') U\). Using the cyclic property of the trace and the identity \(U U^\top = P\), the Frobenius norm of the difference is bounded by: \[\begin{align} \left\Vert U^\top M U - U^\top M' U\right\Vert_F^2 &= \left\Vert U^\top(M-M')U\right\Vert_F^2 \\ &= \text{tr}\Big( U^\top(M-M')^\top U U^\top (M-M') U \Big) \\ &= \text{tr}\Big( (M-M') P (M-M') P \Big). \end{align}\] Since \(P\) is an orthogonal projection matrix, its eigenvalues are exactly \(0\) or \(1\), establishing \(P \preceq I\). Consequently, the trace is bounded by \(\text{tr}((M-M')^2) = \left\Vert M-M'\right\Vert_F^2 \le \Delta_M^2\). Thus, the Frobenius sensitivity of \(U^\top M U\) remains bounded by \(\Delta_M\).

Analogous to Step 1, since \(C = U^\top M U\) is also symmetric, we only need to release its upper-triangular entries. Their \(\ell_2\) sensitivity is bounded by \(\left\Vert C - C'\right\Vert_F \le \Delta_M\). Adding independent Gaussian noise \(\mathcal{N}(0, \sigma_2^2)\) to these entries (and mirroring them to construct the symmetric matrix \(E\)) with scale \(\sigma_2 = \Delta_M \sqrt{2\log(1.25/\delta_2)} / \varepsilon_2\) guarantees \((\varepsilon_2, \delta_2)\)-DP for this final query.

Finally, by the adaptive composition theorem (Lemma 2), the overall algorithm satisfies \((\varepsilon_1 + \varepsilon_2, \delta_1 + \delta_2)\)-DP, which concludes the proof. ◻

Proof. Recall that the reconstructed matrix is given by \(\widehat{M} = U \widetilde{C} U^T\). By substituting the definition of the noisy matrix \(\widetilde{C} = U^T M U + E\), we have: \[\widehat{M} = U (U^T M U + E) U^T = U U^T M U U^T + U E U^T.\] Notice that \(U \in \mathbb{R}^{n \times r}\) consists of orthonormal column vectors spanning the range of \(P\), meaning \(U U^T = P\) and \(U^T U = I_r\). Substituting this yields \(\widehat{M} = P M P + U E U^T\). We decompose the total estimation error using the triangle inequality: \[\left\Vert M - \widehat{M}\right\Vert_2 \le \underbrace{\left\Vert M - P M P\right\Vert_2}_{\text{Truncation Bias}} + \underbrace{\left\Vert U E U^T\right\Vert_2}_{\text{Subspace Noise}}.\] Because \(U\) has orthonormal columns, for any vector \(x\), \(\left\Vert U E U^T x\right\Vert_2 \le \left\Vert E\right\Vert_2 \left\Vert x\right\Vert_2\). Hence, the subspace noise is at most \(\left\Vert E\right\Vert_2\).

First, we bound the truncation bias. Condition on the high-probability event \(\mathcal{E}_1\) that \(\left\Vert W\right\Vert_2 \le \eta\), which occurs with probability at least \(1-\beta_1\) (Lemma 10). For any unit vector \(x \perp \text{range}(P)\), its Rayleigh quotient on \(\widetilde{Y}\) satisfies \(x^T \widetilde{Y} x \le 2\eta\). Since \(\widetilde{Y} = M^q + W\) and \(\left\Vert W\right\Vert_2 \le \eta\), the Rayleigh quotient on the true amplified matrix is bounded by: \[x^T M^q x = x^T \widetilde{Y} x - x^T W x \le 2\eta + \eta = 3\eta, \text{ where } x \perp \text{range}(P).\] To bound the spectral norm of \(M\) in the orthogonal complement \(P^\perp\), we evaluate \(\left\Vert Mx\right\Vert_2^2 = x^T M^2 x\). Let \(M = \sum_{i=1}^n \lambda_i v_i v_i^T\) be the eigendecomposition of \(M\). We have \(x^T M^2 x = \sum_{i=1}^n \lambda_i^2 (v_i^T x)^2\). Because \(q \ge 2\), the mapping \(f(z) = z^{2/q}\) is a concave function for \(z \ge 0\). Writing \(\lambda_i^2 = (|\lambda_i|^q)^{2/q}\), and noting that \(\sum_{i=1}^n (v_i^T x)^2 = \left\Vert x\right\Vert_2^2 = 1\), we apply Jensen’s inequality: \[\begin{align} \left\Vert Mx\right\Vert_2^2 = \sum_{i=1}^n \left(|\lambda_i|^q\right)^{2/q} (v_i^T x)^2 &\le \left( \sum_{i=1}^n |\lambda_i|^q (v_i^T x)^2 \right)^{2/q} \\ &= \left( x^T M^q x \right)^{2/q} \le (3\eta)^{2/q}. \end{align}\] Taking the square root yields \(\left\Vert Mx\right\Vert_2 \le (3\eta)^{1/q}\) for any unit vector \(x \perp \text{range}(P)\). To bound the matrix operator norm \(\left\Vert M(I-P)\right\Vert_2\), we note that: \[\label{eq:project95space} \left\Vert M(I-P)\right\Vert_2 = \sup_{y \in \mathbb{R}^n, \, \left\Vert y\right\Vert_2 = 1} \left\Vert M(I-P)y\right\Vert_2.\tag{8}\] For any arbitrary unit vector \(y \in \mathbb{R}^n\), let \(z = (I-P)y\). Since \(I-P\) is a projector orthogonal to \(P\), then \(z \perp \text{range}(P)\) and that \(\left\Vert z\right\Vert_2 \le \left\Vert y\right\Vert_2 = 1\). If \(z = \mathbf{0}\), the bound holds trivially. Otherwise, we can normalize it into a valid unit vector \(\widehat{z} = z / \left\Vert z\right\Vert_2 \perp \text{range}(P)\), then: \[\left\Vert M(I-P)y\right\Vert_2 = \left\Vert Mz\right\Vert_2 = \left\Vert z\right\Vert_2 \left\Vert M\widehat{z}\right\Vert_2 \le 1 \cdot (3\eta)^{1/q} = (3\eta)^{1/q}.\] Taking this back to 8 yields \(\left\Vert M(I-P)\right\Vert_2 \le (3\eta)^{1/q}\). We then decompose the residual matrix: \[\left\Vert M - PMP\right\Vert_2 \le \left\Vert M(I-P)\right\Vert_2 + \left\Vert PM(I-P)\right\Vert_2 \le 2\left\Vert M(I-P)\right\Vert_2 \le 2(3\eta)^{1/q}.\] Next, we bound the variance inside the subspace. Still conditioning on \(\mathcal{E}_1\), let \(\{u_1, \dots, u_r\}\) be the orthonormal basis forming \(P\). For each basis vector, \(u_i^T M^q u_i = u_i^T \widetilde{Y} u_i - u_i^T W u_i > 2\eta - \eta = \eta\). Summing this over all \(r\) dimensions yields \(r\eta < \sum_{i=1}^r u_i^T M^q u_i\). By Ky Fan’s Maximum Principle (Theorem 6), because \(M^q \succeq 0\), this sum is bounded by the total trace \(B_q\): \[r\eta < \sum_{i=1}^{r} u_i^T M^q u_i \le \text{tr}(M^q) \le B_q \implies r \le \frac{B_q}{\eta}.\] Conditioning on a second event \(\mathcal{E}_2\) that the spectral norm of the Gaussian noise \(E \in \mathbb{R}^{r \times r}\) follows the concentration bound (Lemma 10): \[\left\Vert E\right\Vert_2 \le O_{\delta}\left(\sigma_2 \sqrt{r} + \sigma_2 \sqrt{\log(1/\beta_2)}\right) = \widetilde{O}_{\delta}\left( \frac{\Delta_M}{\varepsilon_2} \sqrt{\frac{B_q}{\eta}} \right),\] where we let \(\beta_2=1/n^c\). By a union bound, events \(\mathcal{E}_1\) and \(\mathcal{E}_2\) hold simultaneously with probability at least \(1 - \beta\). Summing the truncation bias and the subspace noise, the overall error is: \[\left\Vert M - \widehat{M}\right\Vert_2 \le \widetilde{O}_{\delta}\left( \eta^{1/q} + \frac{\Delta_M}{\varepsilon} \sqrt{\frac{B_q}{\eta}} \right).\] Substituting \(\eta = \widetilde{O}_{\delta}(\sigma_1 \sqrt{n}) = \widetilde{O}_{\delta}\left( \frac{\Delta_q \sqrt{n}}{\varepsilon} \right)\) yields the desired bound 7 , concluding the proof. ◻

Proof. Let \(A' = A + H\), where the update corresponding to a single edge between vertices \(u\) and \(v\) is \(H = s(e_u e_v^\top + e_v e_u^\top)\) for \(s \in \{-1, +1\}\). Clearly, \(\left\Vert H\right\Vert_F = \sqrt{2} = O(1)\), establishing \(\Delta_M = \sqrt{2}\). For the squared sensitivity, we have: \[A'^2 - A^2 = (A+H)^2 - A^2 = AH + HA + H^2.\] Because \(A\) is the adjacency matrix of a graph with maximum degree \(d\), its local column \(\ell_2\)-norm is bounded by the degree: \(\left\Vert A e_u\right\Vert_2 = \sqrt{\sum_{i=1}^n A_{iu}^2} \le \sqrt{d}\). Consequently, \[\left\Vert AH\right\Vert_F = \left\Vert A(s e_u e_v^\top + s e_v e_u^\top)\right\Vert_F \le \left\Vert A e_u\right\Vert_2 \left\Vert e_v\right\Vert_2 + \left\Vert A e_v\right\Vert_2 \left\Vert e_u\right\Vert_2 \le 2\sqrt{d}.\] By symmetry, \(\left\Vert HA\right\Vert_F \le 2\sqrt{d}\). Furthermore, \(H^2 = e_u e_u^\top + e_v e_v^\top\), meaning \(\left\Vert H^2\right\Vert_F = \sqrt{2}\). Applying the triangle inequality, we bound the squared sensitivity as follows: \[\Delta_2 \le \left\Vert AH\right\Vert_F + \left\Vert HA\right\Vert_F + \left\Vert H^2\right\Vert_F \le 4\sqrt{d} + \sqrt{2} = O(\sqrt{d}).\] Finally, since the trace of \(A^2\) is exactly the sum of vertex degrees: \[B_2 = \operatorname{tr}(A^2) = \left\Vert A\right\Vert_F^2 = \sum_{u=1}^n \operatorname{deg}(u) \le nd.\] ◻

Proof. We first see the privacy guarantee. We partition the budget: In line 1, running the Square Amplifier requires \((\varepsilon/2, \delta)\)-DP by 8. 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 \(\ell_1\)-sensitivity of the degree vector is \(2\). Applying the Laplace mechanism (Lemma 5) with scale \(2 / (\varepsilon/2) = 4/\varepsilon\) guarantees \((\varepsilon/2, 0)\)-DP. Therefore, the joint release of \(\widehat{A}\) and \(\widehat{D}\) satisfies \((\varepsilon, \delta)\)-DP by the basic composition theorem (Lemma 2). The SDP projection in Step 9 operates exclusively on the privatized matrix \(\widetilde{L}\) without accessing the underlying graph topology, consuming zero additional privacy budget due to post-processing (Lemma 1). Thus, the algorithm is overall \((\varepsilon, \delta)\)-DP.

For the utility bound, we first compute the spectral distance of the intermediate matrix \(\widetilde{L}\). By the triangle inequality: \[\label{eq:triangle95laplacian} \left\Vert\widetilde{L} - L_G\right\Vert_2 = \left\Vert(\widehat{D} - \widehat{A}) - (D - A)\right\Vert_2 \le \left\Vert\widehat{D} - D\right\Vert_2 + \left\Vert A - \widehat{A}\right\Vert_2.\tag{12}\] Applying Theorem 9 (specifically the \(q=2\) form in 9 ) and substituting the parameters from Lemma 12 (\(\Delta_A = \sqrt{2}\), \(\Delta_2 = \Theta(\sqrt{d})\), \(B_2 = nd\)) evaluated under budget \(\varepsilon/2\), the approximation error on adjacency matrix is: \[\begin{align} \left\Vert\widehat{A} - A\right\Vert_2 &\le \widetilde{O}_{\delta}\left( \sqrt{ \frac{\sqrt{d}\sqrt n}{\varepsilon} } + \frac{1}{\varepsilon} \sqrt{ \frac{nd\varepsilon}{\sqrt{d}\sqrt n} } \right) = \widetilde{O}_{\delta}\left( \frac{(nd)^{1/4}}{\sqrt{\varepsilon}} \right). \end{align}\] For the degree matrix, the error is only contained on the diagonal: \(\left\Vert\widehat{D} - D\right\Vert_2 = \max_{i \in [n]} |Z_i|\). By the tail bounds of the Laplace distribution (Lemma 4) and a union bound over \(n\) variables, with high probability: \[\left\Vert\widehat{D} - D\right\Vert_2 \le {O}\left(\frac{\log n}{\varepsilon}\right).\] Substituting both bounds into 12 : \[\left\Vert\widetilde{L} - L_G\right\Vert_2 \le \left\Vert\widehat{A} - A\right\Vert_2+\left\Vert\widehat{D} - D\right\Vert_2 = \widetilde{O}_{\delta}\left( \frac{(nd)^{1/4}}{\sqrt{\varepsilon}} + \frac{1}{\varepsilon} \right).\] Finally, we analyze the SDP projection. The constraint \(-\gamma I_n \preceq \widetilde{L} - X \preceq \gamma I_n\) is identical to \(\left\Vert\widetilde{L} - X\right\Vert_2 \le \gamma\). The SDP computes the operator-norm projection onto \(\mathbb{L}_n\): \[\widehat{L} = \arg\min_{X \in \mathbb{L}_n} \left\Vert\widetilde{L} - X\right\Vert_2.\] Because the true unweighted graph Laplacian inherently satisfies \(L_G \in \mathbb{L}_n\), the optimality of \(\widehat{L}\) dictates that \(\left\Vert\widehat{L} - \widetilde{L}\right\Vert_2 \le \left\Vert L_G - \widetilde{L}\right\Vert_2\). Applying the triangle inequality yields the final spectral error: \[\begin{align} \left\Vert L_G - \widehat{L}\right\Vert_2 &\le \left\Vert L_G - \widetilde{L}\right\Vert_2 + \left\Vert\widetilde{L} - \widehat{L}\right\Vert_2 \le 2 \left\Vert L_G - \widetilde{L}\right\Vert_2 \le \widetilde{O}_{\delta}\left( \frac{(nd)^{1/4}}{\sqrt{\varepsilon}} +\frac{1}{\varepsilon}\right). \end{align}\] The constant factor is absorbed by the \(\widetilde{O}_{\delta}\) notation, completing the proof. ◻

Proof. Let \(A'=A+H\), where \(H=\pm(e_ue_v^\top+e_ve_u^\top)\). We expand the difference: \[(A+H)^3-A^3 =A^2H+AHA+HA^2+AH^2+HAH+H^2A+H^3.\] The first and third terms satisfy \[\left\lVert A^2H\right\rVert_F, \left\lVert HA^2\right\rVert_F \le 2\max_v\left\Vert A^2e_v\right\Vert_2 \le 2\sqrt K.\] Moreover, since \(\max_{u \in [n]} \left\Vert A e_u\right\Vert_2 = \max_{u \in [n]} \sqrt{\sum_{v=1}^n A_{uv}^2} \le \sqrt{d}\), we have: \[\left\lVert AHA\right\rVert_F \le 2\left\Vert Ae_u\right\Vert_2\left\Vert Ae_v\right\Vert_2 \le 2d.\] By our premise \(K \ge d^2\), the remaining terms involve at least two factors of \(H\) and have Frobenius norm \(O(\sqrt d+1)\), which is dominated by \(O(\sqrt K)\). Therefore, \(\left\lVert (A')^3-A^3\right\rVert_F \le C\sqrt K\). ◻

Proof. Let \(A'=A+H\), where \(H=\pm(e_ue_v^\top+e_ve_u^\top)\). We expand \((A+H)^4-A^4\) 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 \(A^i H A^{3-i}\) for \(i\in\{0,1,2,3\}\). Using the facts that \(\left\Vert A^2e_v\right\Vert_2\leq\sqrt{\kappa_2}\le \sqrt K\), \(\left\Vert Ae_v\right\Vert_2\le \sqrt{d}\), and \(\left\Vert A\right\Vert_2\leq d\), we bound them as follows: \[\left\lVert A^2HA\right\rVert_F \le \left\Vert A^2e_u\right\Vert_2\left\Vert Ae_v\right\Vert_2+\left\Vert A^2e_v\right\Vert_2\left\Vert Ae_u\right\Vert_2 \le 2\sqrt{Kd},\] \[\left\lVert A^3H\right\rVert_F \leq \left\Vert A^3e_u\right\Vert_2\left\Vert e_v\right\Vert_2+\left\Vert A^3e_v\right\Vert_2\left\Vert e_u\right\Vert_2 \leq (\left\Vert A^2e_u\right\Vert_2+\left\Vert A^2e_v\right\Vert_2)\left\Vert A\right\Vert_2\leq 2d\sqrt{K}.\] By symmetry, \(\left\lVert HA^3\right\rVert_F\) and \(\left\lVert AHA^2\right\rVert_F\) are similarly bounded by \(2d\sqrt{K}\). Furthermore, the Frobenius norm of all multi-\(H\) terms is at most \(O(d^2) \le O(d\sqrt K)\) because \(K \ge d^2\). Summing these bounded terms completes the proof. ◻

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 \(\varepsilon_{test}\) and \(\varepsilon_{rel}\). First, we analyze the sensitivity of the true local energy \(\kappa_2(G) = \max_v \sum_u \operatorname{codeg}(u,v)^2\). Adding or removing a single edge \(e=\{x,y\}\) in a \(d\)-bounded graph changes the common neighborhood \(\operatorname{codeg}(u,v)\) by at most 1, and this perturbation only occurs for pairs where \(\{u,v\} \cap \{x,y\} \neq \varnothing\). Thus, for any fixed vertex \(v\), the sum \(\sum_u \operatorname{codeg}(u,v)^2\) changes by at most \(\sum_{u \in N(v)} (2\operatorname{codeg}(u,v) + 1) \le 2d^2 + d \le 3d^2\). Consequently, \(\kappa_2(G)\) has an exact global sensitivity bounded by \(\Delta_\kappa \le 3d^2\). By the standard Laplace mechanism (Lemma 5), releasing \(\kappa_{2,i} + \xi_i\) satisfies \((\varepsilon_{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 2), we analyze the \(i\)-th round conditioned on an arbitrary fixed transcript of previous outputs in rounds \(0 ,\cdots, i-1\). Because the set of removed edge pairs \(P_{<i} = \bigcup_{j=0}^{i-1} P_j\) 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 \(R_i = G \setminus P_{<i}\) and \(R'_i = G' \setminus 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 \(\kappa_{2,i}(R_i)\) and \(\kappa_{2,i}(R'_i)\):

• Case 1 (Both Unsafe): If both \(\kappa_{2,i} > K_i\) and \(\kappa'_{2,i} > K_i\), the probability that the algorithm passes the test for either graph is bounded by \(\mathbf{Pr}[\xi_i \le -M_i] \le \frac{1}{2}\exp(-\varepsilon_{test} M_i / \Delta_\kappa) = \delta'/2\). Thus, the algorithm outputs \(\bot\) with probability at least \(1 - \delta'/2\). For any set of outcomes \(\mathcal{O}\), we have \[\begin{align} \mathbf{Pr}[\mathcal{M}(R_i) \in \mathcal{O}] &= \mathbf{Pr}[\mathcal{M}(R_i) \in \mathcal{O} \setminus \{\bot\}] + \mathbf{Pr}[\mathcal{M}(R_i) = \bot \land \bot \in \mathcal{O}]\\ &\le \delta'/2 + \delta' + \mathbf{Pr}[\mathcal{M}(R_i') = \bot \land \bot \in \mathcal{O}] \\ &\le e^{\varepsilon'} \mathbf{Pr}[\mathcal{M}(R_i') \in \mathcal{O}] + 1.5\delta'. \end{align}\] satisfying \((\varepsilon', 1.5\delta')\)-DP.

• Case 2 (Both Safe): If both \(\kappa_{2,i} \le K_i\) and \(\kappa'_{2,i} \le K_i\), the true global sensitivity of the cubic query \(A_i^3\) is deterministically bounded by \(O(\sqrt{K_i})\) due to Lemma 13. If the test fails, the algorithm outputs \(\bot\). If it passes, the Gaussian mechanism is calibrated to the true sensitivity, guaranteeing \((\varepsilon_{rel}, \delta'/2)\)-DP for the released matrix. Because the safety test itself provides \((\varepsilon_{test}, 0)\)-DP, standard basic composition dictates that the entire procedure (including the probability of outputting \(\bot\)) satisfies \((\varepsilon_{test} + \varepsilon_{rel}, \delta'/2) \subset (\varepsilon', \delta')\)-DP.

• Case 3 (Boundary): Without loss of generality, assume \(\kappa_{2,i} \le K_i\) (safe) but \(\kappa'_{2,i} > K_i\) (unsafe). since they are neighbors, we have \(\kappa'_{2,i} \le \kappa_{2,i} + \Delta_\kappa \le K_i + \Delta_\kappa\). The probability that the unsafe graph \(R_i'\) passes the test is bounded by: \[\mathbf{Pr}[\text{pass} \mid R_i'] = \mathbf{Pr}[\xi'_i \le K_i - \kappa'_{2,i} - M_i] \le \frac{1}{2}\exp\left(-\varepsilon_{test} \frac{M_i - \Delta_\kappa}{\Delta_\kappa}\right) = \frac{\delta'}{2} e^{\varepsilon_{test}} \le \delta',\] assuming \(\varepsilon_{test} \le \ln 2\). Crucially, the probability that the safe graph \(R_i\) passes the test is identically bounded: \[\mathbf{Pr}[\text{pass} \mid R_i] = \mathbf{Pr}[\xi_i \le K_i - \kappa_{2,i} - M_i] < \mathbf{Pr}[\xi_i \le \Delta_\kappa - M_i] \le \delta'.\] For any set of outcomes \(\mathcal{O}\), let \(\mathcal{O}_{\text{mat}} = \mathcal{O} \setminus \{\bot\}\), for the direction from \(R_i\) to \(R_i'\): \[\begin{align} \mathbf{Pr}[\mathcal{M}(R_i) \in \mathcal{O}] &= \mathbf{Pr}[\mathcal{M}(R_i) = \bot] \cdot \mathbb{1}_{\bot \in \mathcal{O}} + \mathbf{Pr}[\mathcal{M}(R_i) \in \mathcal{O}_{\text{mat}}] \\ &\le e^{\varepsilon_{test}} \mathbf{Pr}[\mathcal{M}(R_i') = \bot] \cdot \mathbb{1}_{\bot \in \mathcal{O}} + \mathbf{Pr}[\text{pass} \mid R_i] \\ &\le e^{\varepsilon_{test}} \mathbf{Pr}[\mathcal{M}(R_i') \in \mathcal{O}] + \delta' \le e^{\varepsilon'} \mathbf{Pr}[\mathcal{M}(R_i') \in \mathcal{O}] + \delta', \end{align}\] where the relation \(\mathbf{Pr}[\mathcal{M}(R_i) = \bot] \le e^{\varepsilon_{test}} \mathbf{Pr}[\mathcal{M}(R_i') = \bot]\) follows from the \((\varepsilon_{test}, 0)\)-DP property of Laplace mechanism (Lemma 5). \(\mathbf{Pr}[\mathcal{M}(R_i') \in \mathcal{O}] \le e^{\varepsilon'} \mathbf{Pr}[\mathcal{M}(R_i) \in \mathcal{O}] + \delta'\) holds by identical reasoning. This proves \((\varepsilon', \delta')\)-DP on the boundary.

Therefore, the single round satisfies \((\varepsilon', 1.5\delta')\)-DP for all possible inputs, without conditioning on high-probability utility events. Finally, basic composition (Lemma 2) over \(S\) rounds guarantees the overall \((\varepsilon, \delta)\)-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 (\(\|Z_i\|_{\max} \le \zeta_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/n^c\) for \(\delta= n^{-c'}\).

Consider a single cover round on the residual graph \(R_i\) with adjacency matrix \(A_i\). If \(uv \in P_i\), then \((A_i^3)_{uv} \ge \tau_i - \zeta_i \ge \tau_i/2\). For any vertex \(u\), the row sum \(\sum_v (A_i^3)_{uv}\) represents the total number of length-three walks originating from \(u\), which is inherently at most \(d^3\). Therefore, the maximum degree of the covered edges in this round is bounded by: \[\label{eq:degree-Pi} \Delta(P_i) \le \max_{u}\frac{\sum_v(A_i^3)_{uv}}{\min_{v:uv\in P_i}(A_i^3)_{uv}} \le \frac{d^3}{\tau_i/2} = \frac{2d^3}{\tau_i}.\tag{14}\]

Conversely, if an edge \(uv\) remains in the residual graph \(R_{i+1}\), it must be that \(uv \notin P_i\), implying \((A_i^3)_{uv} < 2\tau_i\). Because \(R_{i+1} \subseteq R_i\), the number of walks monotonically decreases, so \((A_{i+1}^3)_{uv} \le (A_i^3)_{uv} < 2\tau_i\). Thus, combing 4 , for any vertex \(u\), the true local energy is bounded by: \[\label{eq:energy-rec} \kappa_2(R_{i+1}) = \max_u \sum_{v \in N_{i+1}(u)} (A_{i+1}^3)_{uv} \le 2d\tau_i.\tag{15}\] Notice that the algorithm explicitly defines the public threshold \(K_{i+1} = C_1 d \tau_i\) with a constant \(C_1 \ge 4\). This guarantees a safety gap \(K_{i+1} - \kappa_2(R_{i+1}) \ge \frac{1}{2} K_{i+1}\). Since the algorithm ensures \(K_{i+1} \ge \widetilde{O}(d^2 q / \varepsilon_{rel})\), and we assume \(q \ge \operatorname{polylog}(d)/\varepsilon\), this gap is asymptotically larger than the required Laplace margin \(M_{i+1} = \widetilde{O}(d^2/\varepsilon_{test})\), implying that the propose-test-release passes with high probability in the next round.

Now, we evaluate the recurrence. If the initial energy \(K_0 = 2d^3 \le \widetilde{O}(d^2 q/\varepsilon_{rel})\), the algorithm trivially satisfies the breaking condition at round \(i=0\) and immediately outputs \(P=\varnothing\), naturally satisfying all required bounds. Thus, we focus on the non-trivial regime where \(K_0 > \widetilde{O}(d^2 q/\varepsilon_{rel})\), which implies \[d \ge \widetilde{\Omega}(q/\varepsilon_{rel}) \ge \Omega(1/\varepsilon_{rel}^2),\] meaning the base term \(2d\varepsilon_{rel}^2 \ge 1\). By the algorithmic definition, \(\tau_i = \widetilde{O}_{\delta}\left(\max(\sqrt{K_i}/\varepsilon_{rel}, dq/\varepsilon_{rel})\right)\). Notice that the \(\max\) operation implies a phase transition at \(K_i \approx d^2q^2\). In the noise-dominated regime where \(K_i \ge d^2q^2\), substituting the threshold into \(K_{i+1}\gets C_1d\tau_i\) gives the recurrence relation \(K_{i+1} = \widetilde{O}_{\delta}\left(d\sqrt{K_i}/\varepsilon_{rel}\right)\). Ignoring polylogarithmic factors, solving this exact recurrence for the base case \(K_0 = 2d^3\) yields \[K_i = \frac{d^2}{\varepsilon_{rel}^2}(2d\varepsilon_{rel}^2)^{2^{-i}}.\] For any \(d \ge 1\) and \(\varepsilon_{rel} > 0\), as \(i \to \infty\), the exponential term \((2d\varepsilon_{rel}^2)^{2^{-i}}\) rapidly approaches \(1\). Thus, \(K_i\) converges to the fixed point \(d^2/\varepsilon_{rel}^2\). Crucially, because we assume \(q \ge \operatorname{polylog}(d)/\varepsilon\), the phase-transition target \(d^2q^2\) is larger than this fixed point \(d^2/\varepsilon_{rel}^2\). To ensure the sequence reaches the target \(K_T \le d^2q^2\), it suffices to make sure that the residual factor satisfies: \[(2d\varepsilon_{rel}^2)^{2^{-T}} \leq (2d)^{2^{-T}} \leq 2 \leq \varepsilon_{rel}^2 q^2,\] which yields \(T = O(\log\log d)\) since our premise \(q \ge \operatorname{polylog}(d)/\varepsilon\) naively guarantees \(q \ge \sqrt{2}/\varepsilon_{rel}\). Assume that in the \(T\)-th round, \(K_T\) becomes smaller than \(\widetilde{O}_{\delta}(d^2q^2)\) for the first time, i.e., \(K_T\le d^2q^2\) and \(K_{T-1}>d^2q^2\). At this point, the Gaussian noise bound drops below the floor \(\widetilde{O}_{\delta}(dq/\varepsilon_{rel})\), thus the threshold transitions to \(\tau_T=\widetilde{\Theta}_{\delta}(dq/\varepsilon_{rel})\). Then in the \(T+1\) round, \[\kappa_2(R_{T+1}) \le d\tau_{T} =\widetilde{O}_{\delta}(d^2q/\varepsilon_{rel}).\] Therefore the algorithm successfully satisfies the breaking condition and stops after the \(T+1\) round. Since \(\tau_i\ge dq/\varepsilon_{rel}\) for all \(i\leq T+1\), substituting this into 14 gives: \[\Delta(P_{i}) \le \frac{2d^3}{\tau_{i}} = \widetilde{O}_{\delta}\left(\frac{\varepsilon_{rel} d^2}{q}\right).\] Summing over \(T+1=O(\log\log d)\) rounds only alters the polylogarithmic factor. Recalling that \(\varepsilon_{rel} = \Theta(\varepsilon/ \log\log d)\), we conclude: \[\Delta(P) \le \widetilde{O}_{\delta}\left(\frac{\varepsilon d^2}{q}\right).\] This completes the proof. ◻

Proof. Let \(g_e = \xi_e / \sigma\), so that \(g_e \sim \mathcal{N}(0,1)\) are independent standard Gaussian random variables. The target random matrix can be identically rewritten as \(Z = \sum_{e \in P} g_e (\sigma L_e)\). We first compute the matrix variance proxy \(v\): \[v = \left\lVert \sum_{e\in P} (\sigma L_e)^2\right\rVert_2 = \sigma^2 \left\lVert \sum_{e\in P} L_e^2\right\rVert_2.\] For any single edge \(e=\{u,v\}\), its unweighted Laplacian matrix \(L_e\) satisfies the identity \(L_e^2 = 2L_e\). Substituting this identity simplifies the variance proxy to: \[v = 2\sigma^2 \left\lVert \sum_{e\in P} L_e\right\rVert_2 = 2\sigma^2 \left\lVert L_P\right\rVert_2,\] where \(L_P = \sum_{e\in P} L_e\) 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 \(\left\lVert L_P\right\rVert_2 \le 2d\). Therefore, the variance proxy is bounded by: \[v \le 2\sigma^2 (2d) = 4\sigma^2 d.\] Applying Lemma 8, we conclude that with probability at least \(1-1/n^c\): \[\left\lVert \sum_{e\in P}\xi_eL_e\right\rVert_2 \le \sqrt{2(4\sigma^2 d) \log(2n\cdot n^c)} = \widetilde{O}_{\delta}(\sigma\sqrt d),\] which completes the proof. ◻

Proof. By the principle of adaptive composition (Lemma 2), we analyze this subroutine conditioned on an arbitrary fixed transcript of the public support \(P\) generated by Algorithm 4. For a fixed \(P\), the query \(G\mapsto (\mathbb{1}[e\in E(G)])_{e\in P}\) has \(\ell_2\)-sensitivity at most one under edge-level privacy. The privacy claim then follows from the Gaussian mechanism (Lemma 6).

Next, we establish the spectral utility bound. The true Laplacian of the graph \(G\) restricted to the edge support \(P\) is denoted as \(L_{G[P]} = \sum_{e \in P} \mathbb{1}[e \in E] L_e\). By Algorithm 5, the spectral error matrix is: \[\widehat L_P - L_{G[P]} = \sum_{e \in P} (\mathbb{1}[e \in E] + \xi_e) L_e - \sum_{e \in P} \mathbb{1}[e \in E] L_e = \sum_{e \in P} \xi_e L_e.\] Since the elements \(\xi_e \sim \mathcal{N}(0, \sigma^2)\) are independent Gaussian random variables and the underlying edge support \(P\) has a maximum vertex degree of at most \(\Delta(P)\), we apply Proposition 13 and with probability at least \(1-1/n^c\), the operator norm of the error matrix satisfies: \[\left\lVert \widehat L_P - L_{G[P]}\right\rVert_2 = \left\lVert \sum_{e \in P} \xi_e L_e\right\rVert_2 \le \widetilde{O}_{\delta}\left(\sigma \sqrt{\Delta(P)}\right)\le \widetilde{O}_{\delta}\left(\frac{\sqrt{\Delta(P)}}{\varepsilon}\right).\] Combining the upper bound of \(\Delta(P)\) in Lemma 15 completes the proof. ◻

Proof. By Lemma 14, the amplified sensitivity is bounded by \(\Delta_4 = O(d\sqrt K)\). The trace bound satisfies \(B_4=\operatorname{tr}(A_R^4) = \sum_{v\in V}\left\Vert A_R^2e_v\right\Vert_2^2 \le nK\). Applying the general bound for power amplifiers (7 ) evaluated at \(q=4\) directly yields: \[\left\Vert A_R-\widehat A_R\right\Vert_2 \le \widetilde{O}_{\delta}\left( \left(\frac{d\sqrt{K}\sqrt n}{\varepsilon}\right)^{1/4} + \frac{1}{\varepsilon} \sqrt{ \frac{nK\varepsilon}{d\sqrt{K}\sqrt n} } \right) = \widetilde{O}_{\delta}\left( \frac{n^{1/8}K^{1/8}d^{1/4}}{\varepsilon^{1/4}} +\frac{n^{1/4}K^{1/4}}{\sqrt{d\varepsilon}} \right).\] Finally, as in the analysis of Theorem 11, estimating the residual degree vector using the Laplace mechanism with \(\ell_1\)-sensitivity \(O(1)\) independently contributes \(\widetilde{O}_{\delta}(1/\varepsilon)\) to the diagonal. Summing these errors yields the stated bound. ◻

Proof of Theorem 12. 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 \(\delta\) is when a residual graph \(R\) with true local energy \(\kappa_2(R) > K_{\text{final}}\) accidentally passes the test. By setting the safety margin to \(M_{\text{final}} = 3d^2 \frac{\log(6/\delta)}{\varepsilon_{test}}\) and applying the Laplace tail bound (Lemma 4), the probability of such an unsafe graph passing the test is bounded by \(\delta/6\).

Therefore, with all but \(\delta/6\) probability, any graph that proceeds to line 14 satisfies the 4th-power sensitivity bound \(O(d\sqrt{K_{\text{final}}})\), guaranteeing that the subsequent spectral amplifier (Algorithm 2) provides \((\varepsilon_{amp}, \delta/6)\)-DP. Combining the budgets used in the cover (Algorithm 4), the support release (Algorithm 5), the PTR test, and the final amplifier via basic composition (Lemma 2) yields the overall \((\varepsilon, \delta)\)-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 \(\bot\)) and all noise tail bounds hold.

By Lemma 15, the IteratedCubicScoreCover successfully outputs \((P, R)\) satisfying \(\kappa_2(R) \le \widetilde{O}(d^2q/\varepsilon_{cov})\) with probability at least \(1-\beta/3\), which ensures that \(\kappa_2(R) \le K_{\text{final}}/2\) for the publicly promised target energy \(K_{\text{final}} = \widetilde{O}(d^2q/\varepsilon)\) by choosing large enough constants for \(K_{\text{final}}\). Because \(q \ge \operatorname{polylog}(n)\), the gap \(K_{\text{final}} - \kappa_2(R) \ge K_{\text{final}}/2\) asymptotically dominates the safety margin \(M_{\text{final}} = \widetilde{O}(d^2/\varepsilon_{test})\). Therefore, to trigger a false abort, the Laplace noise \(\xi_{\text{final}}\) must exceed \(K_{\text{final}}/2 - M_{\text{final}} \gg \Delta_\kappa \frac{\ln(3/\beta)}{\varepsilon_{test}}\). By the standard tail bound of the Laplace distribution (Lemma 4), this happens with probability at most \(\beta/3\).

Conditioned on this successful execution, the true graph Laplacian partitions exactly as \(L_G = L_{G[P]} + L_R\). Applying the triangle inequality to our raw estimate \(\widetilde{L} = \widetilde{L}_P + \widetilde{L}_R\), we sum the spectral error bounds from the support release (Lemma 16) and the fourth-power residual release (Lemma 17). By a union bound over all subroutines, this raw estimation error bounds \(\left\Vert L_G-\widetilde{L}\right\Vert_2\) with overall probability at least \(1-\beta\).

Finally, because the true unweighted graph Laplacian inherently satisfies \(L_G \in \mathbb{L}_n\), the optimality of the SDP projection guarantees that \(\left\Vert\widehat L_G-\widetilde{L}\right\Vert_2 \le \left\Vert L_G-\widetilde{L}\right\Vert_2\). Applying the triangle inequality one last time yields \[\left\Vert L_G-\widehat L_G\right\Vert_2 \le \left\Vert L_G-\widetilde{L}\right\Vert_2 + \left\Vert\widetilde{L}-\widehat L_G\right\Vert_2 \le 2\left\Vert L_G-\widetilde{L}\right\Vert_2,\] which gives the claimed error interface and completes the proof. ◻

Proof. The diagonal of \(X_S^\rho\) is one. Its eigenvalues are \(2\rho\) on \((\beta^S)^\perp\) subspace and \(n(1-2\rho)+2\rho\) in the \(\beta^S\) direction, so \(X_S^\rho\succeq\rho I\). Hence \(X_S^\rho\in\mathcal{X}\). For any \(e=\{u,v\}\), write \(b_e = e_u - e_v\), we have \[\frac{1-(X_S^\rho)_{uv}}{2}=\frac{1}{4}b_e^\top X_S^\rho b_e =\frac{1-2\rho}{4}(\beta^S_u-\beta^S_v)^2+\frac{2\rho}{4}\left\Vert b_e\right\Vert_2^2 =(1-2\rho)c_S(e)+\rho.\] Combining this with \(\sum_{e \in \binom{n}{2}} a_\sigma(e) + a_\sigma^{\text{slack}} = -\gamma M\) gives \[\widehat{F}_\sigma(w, w^*,X_S^\rho,\rho)=\sum_{e=\{u,v\} \in \binom{n}{2}} a_\sigma(w,w^*)_e\cdot\frac{1 - (X_S^\rho)_{uv}}{2}+a_\sigma^{\text{slack}}\cdot \rho =(1-2\rho)\left\langle a_\sigma,c_S\right\rangle-\rho\gamma M.\] Using \(\operatorname{cut}_w(S) = \langle w, c_S \rangle\) completes the proof. ◻

Proof. Hadamard’s inequality (Lemma 9) gives \(\det X\leq1\) because \(\operatorname{diag}(X)=\mathbf{1}_n\). Plus that \(t\leq 1\) gives \(\mathcal{\mathcal{R}}(X,\rho)\leq 0\). Since the eigenvalues of \(X_S^\rho\) are \(2\rho\) on \((\beta^S)^\perp\) subspace and \(n(1-2\rho)+2\rho\) in the \(\beta^S\) direction, we have \[\log\det X_S^\rho =(n-1)\log(2\rho) +\log\bigl(n(1-2\rho)+2\rho\bigr).\] Therefore, by \(\rho\leq1/8\), \[R(X_S^\rho,\rho)=(n-1)\log(2\rho) +\log\bigl(n(1-2\rho)+2\rho\bigr)+\log\rho\geq-C_0 n\log(1/\rho)\] for a universal constant \(C_0\). ◻

Proof. We prove the contrapositive. Assume there exists a cut \(S\) such that \[|\operatorname{cut}_w(S) - \operatorname{cut}_{w^*}(S)| > \gamma \operatorname{cut}_{w^*}(S) + \alpha.\] Using \(\operatorname{cut}_w(S) = \langle w, c_S \rangle\), this implies that there exists a sign \(\sigma \in \{+, -\}\) such that \(\langle a_\sigma, c_S \rangle > \alpha\). By Lemma 18 and \(\rho=\min(\frac{1}{8},\frac{\alpha}{16\gamma M})\), we have \[\widehat{F}_\sigma(w, w^*,X,t) =(1-2\rho) \langle a_\sigma, c_S \rangle - \rho \gamma M\geq\frac{3\alpha}{4}-\frac{\alpha}{16}\geq\frac{11}{16}\alpha.\] Furthermore, by Lemma 19 and the assumption \(C_0 \lambda n \log(1/\rho) \leq \frac{\alpha}{32}\), we have: \[\lambda\mathcal{R}(X_S^\rho, \rho) \geq-\lambda C_0 n\log(1/\rho) \geq-\frac{\alpha}{32}.\]

Because \(F_\sigma(w, w^*)\) maximizes over all \(X\in\mathcal{X}\) and \(\rho\leq t\leq1\), evaluating it at \((X_S^\rho, \rho)\) provides a lower bound of \(F_\sigma(w, w^*)\). Therefore, \[\begin{align} F_\sigma(w, w^*)&\geq \widehat{F}_\sigma(w, w^*,X_S^\rho,\rho) +\lambda\mathcal{R}(X_S^\rho, \rho) \\ &\geq \frac{11\alpha}{16}-\frac{\alpha}{32} > \frac{5}{8}\alpha. \end{align}\] This contradicts with the assumption. ◻

Proof. Let \(P_{\sigma}=(a_\sigma(w_t,w^*),a_\sigma^{\text{slack}})\) be the signed residual vectors for \(w^*\), and \(P_{\sigma}'=(a_\sigma(w_t,w^{*\prime}),a_\sigma^{\text{slack}})\) be the signed residual vector for \(w^{*\prime}\). For \(\sigma = +\), by the definition, the change in the edge residual vector is: \[\|a_+(w_t, w^*) - a_+(w_t, w^{*\prime})\|_1 = (1+\gamma)\|w^* - w^{*\prime}\|_1 \leq 1+\gamma.\]

Since \(s(w)=M-\left\Vert w\right\Vert_1\), the change in the slack residual is: \[|a_+^{\text{slack}}(w_t, w^*) - a_+^{\text{slack}}(w_t, w^{*\prime})| = (1+\gamma)|s(w^*) - s(w^{*\prime})| =(1+\gamma)|\left\Vert w^*\right\Vert_1-\left\Vert w^{*\prime}\right\Vert_1|\leq 1+\gamma.\] Thus, the total \(\ell_1\)-norm change of \((a_+, a_+^{\text{slack}})\) is bounded by \(c = 2(1+\gamma) \leq 4\) (since \(\gamma \in (0,1)\)). Similarly, for \(\sigma = -\), the total \(\ell_1\)-norm change of \((a_-, a_-^{\text{slack}})\) is bounded by \(2(1-\gamma) \leq 2 \leq 4\). We can conclude that \(\left\Vert P_{\sigma}-P_{\sigma}'\right\Vert_1\leq4\).

Let \((X^*, t^*)\) and \((X^{*\prime}, t^{*\prime})\) be the unique optimizers of the regularized objectives parameterized by \(w^*\) and \(w^{*\prime}\), respectively. By the optimality of \((X^*, t^*)\), the objective value for \(w^{*\prime}\) evaluated at the \((X^{*\prime}, t^{*\prime})\) must be smaller, i.e., \[\begin{align} F_\sigma(w_t, w^*) &= \langle P_{\sigma}, Q(X^*, t^*)\rangle + \lambda \mathcal{R}(X^*, t^*) \\ &\geq \langle P_{\sigma}, Q(X^{*\prime}, t^{*\prime})\rangle + \lambda \mathcal{R}(X^{*\prime}, t^{*\prime}). \end{align}\] Conversely, the objective for \(w^{*\prime}\) is exactly evaluated at its own optimizer: \[F_\sigma(w_t, w^{*\prime}) =\langle P_{\sigma}', Q(X^{*\prime}, t^{*\prime})\rangle+ \lambda \mathcal{R}(X^{*\prime},t^{*\prime}).\] Combining the above yields: \[\begin{align} F_\sigma(w_t, w^{*\prime}) - F_\sigma(w_t, w^*) &\leq \langle P_{\sigma}'-P_{\sigma}, Q(X^{*\prime}, t^{*\prime})\rangle\\ &\leq \|P_{\sigma}-P_{\sigma}'\|_1 \|Q(X^{*\prime},t^{*\prime})\|_\infty \\ &\leq 4 \times 1 = 4. \end{align}\] The last inequality comes from the fact \(\|Q(X,t)\|_\infty\leq1\) for any \(X\in\mathcal{X}\) and \(t\in[\rho,1]\). A symmetric argument establishes that \(F_\sigma(w_t, w^*) - F_\sigma(w_t, w^{*\prime}) \leq 4\), concluding the proof. ◻

Proof. To match the dimensions of the optimization variables \(X \in \mathcal{X} \subset \mathbb{R}^{n \times n}\) and \(t \in \mathbb{R}\) encoded in the covariance matrix \(\Sigma = \begin{pmatrix} X & 0 \\ 0 & t \end{pmatrix} \in \mathbb{R}^{(n+1) \times (n+1)}\), we formulate the linear objective coefficients as matrices in the exact same space. Let \(C_{uv} = \begin{pmatrix} \frac{1}{2}(e_u e_v^\top + e_v e_u^\top) & 0 \\ 0 & 0 \end{pmatrix} \in \mathbb{R}^{(n+1) \times (n+1)}\) and \(C^{\text{slack}} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \in \mathbb{R}^{(n+1) \times (n+1)}\). We define the gradient matrix \(G_{\sigma}\) with respect to \(\Sigma\): \[G_{\sigma} = -\frac{1}{2}\sum_{e=\{u,v\}} a_{\sigma}(w_t,w^*)_{uv} C_{uv} + a_{\sigma}^{\text{slack}}(w_t,w^*) C^{\text{slack}},\] and define \(G_{\sigma}'\) analogously for \(w^{*\prime}\). Because the feasible space of \(\Sigma\) is a convex set and the objective is concave, the constrained optimal solutions satisfy the first-order variational inequality. Specifically, since both \(\Sigma\) and \(\Sigma'\) are feasible, cross-evaluating the gradients \(\nabla F_\sigma = G_\sigma + \lambda \Sigma^{-1}\) and \(\nabla F_\sigma' = G_\sigma' + \lambda \Sigma'^{-1}\) at their respective optima yields: \[\langle G_{\sigma} + \lambda \Sigma^{-1}, \Sigma' - \Sigma \rangle \leq 0,\quad \langle G_{\sigma}' + \lambda \Sigma'^{-1}, \Sigma - \Sigma' \rangle \leq 0\] Summing these two inequalities gives: \[\lambda \langle \Sigma^{-1} - \Sigma'^{-1}, \Sigma' - \Sigma \rangle \leq \langle G_{\sigma}' - G_{\sigma}, \Sigma' - \Sigma \rangle.\] Define \(E = \Sigma^{-1/2}(\Sigma' - \Sigma)\Sigma^{-1/2}\). We denote the eigenvalues of \(I+E\) as \(\mu_i\). Since \(I+E=\Sigma^{-1/2}\Sigma'\Sigma^{-1/2}\), it holds that \(\mu_i>0\) and \(\Sigma' = \Sigma^{1/2}(I+E)\Sigma^{1/2}\). Furthermore, \(\mu_i \leq 1 + |\mu_i - 1| \leq 1 + \|E\|_F\) and \(\left\Vert E\right\Vert_F^2=\sum_i(\mu_i-1)^2\). Thus the left-hand side can be lower bounded as follows: \[\begin{align} \lambda \langle \Sigma^{-1} - \Sigma'^{-1}, \Sigma' - \Sigma \rangle &=\lambda \operatorname{tr}\left( (\Sigma^{-1} - \Sigma'^{-1})(\Sigma' - \Sigma) \right)\\ &=\lambda \operatorname{tr}\left( (\Sigma^{-1} - \Sigma^{-1/2}(I+E)^{-1}\Sigma^{-1/2})(\Sigma^{1/2}(I+E)\Sigma^{1/2} - \Sigma) \right)\\ &= \lambda \operatorname{tr}(E (I-(I+E)^{-1})) = \lambda \sum_i \frac{(\mu_i-1)^2}{\mu_i}\\ &\geq \lambda \frac{\sum_i(\mu_i-1)^2}{1+\left\Vert E\right\Vert_F} = \lambda \frac{\left\Vert E\right\Vert_F^2}{1+\left\Vert E\right\Vert_F}. \end{align}\]

For the right-hand side, utilizing our earlier definition of \(C_{uv}\), we note that \(\Sigma^{1/2} C_{uv} \Sigma^{1/2} = \frac{1}{2} \begin{pmatrix} x_u x_v^\top + x_v x_u^\top & 0 \\ 0 & 0 \end{pmatrix}\) where \(x_u = X^{1/2} e_u\). Its squared Frobenius norm expands to \[\frac{1}{2}( (x_u^\top x_v)^2 + \left\Vert x_u\right\Vert_2^2 \left\Vert x_v\right\Vert_2^2 ) = \frac{1}{2}(X_{uv}^2 + X_{uu}X_{vv}) = \frac{1}{2}(X_{uv}^2 + 1).\] Since \(|X_{uv}|\leq 1\), we establish \(\left\Vert\Sigma^{1/2} C_{uv} \Sigma^{1/2}\right\Vert_F \leq 1\). Thus by the Cauchy-Schwarz inequality, \[\langle C_{uv},\Sigma' - \Sigma\rangle=\operatorname{tr}(C_{uv}\Sigma^{1/2} E \Sigma^{1/2})=\operatorname{tr}(\Sigma^{1/2}C_{uv}\Sigma^{1/2}E)\leq\left\Vert\Sigma^{1/2}C_{uv}\Sigma^{1/2}\right\Vert_F\left\Vert E\right\Vert_F\leq\left\Vert E\right\Vert_F.\] Similarly, since \(\left\Vert\Sigma^{1/2} C^{\text{slack}} \Sigma^{1/2}\right\Vert_F = t \le 1\), we have \(\langle C^{\text{slack}},\Sigma' - \Sigma\rangle\leq\left\Vert E\right\Vert_F\). Then we have, \[\begin{align} \langle G_{\sigma}' - G_{\sigma}, \Sigma' - \Sigma \rangle =&-\frac{1}{2}\sum_{uv} (a_{\sigma}(w_t,w^{*\prime})_{uv} - a_{\sigma}(w_t,w^*)_{uv})\langle C_{uv},\Sigma' - \Sigma\rangle\\ &+(a_{\sigma}^{\text{slack}}(w_t,w^{*\prime})-a_{\sigma}^{\text{slack}}(w_t,w^*))\langle C^{\text{slack}},\Sigma' - \Sigma\rangle\\ &\leq\left\Vert P_{\sigma}-P_{\sigma}'\right\Vert_1\left\Vert E\right\Vert_F. \end{align}\] Combining both sides yields \[\lambda \frac{\left\Vert E\right\Vert_F^2}{1+\left\Vert E\right\Vert_F} \leq \left\Vert P_{\sigma}-P_{\sigma}'\right\Vert_1\left\Vert E\right\Vert_F.\] From the proof of Lemma 21, we have \(\left\Vert P_{\sigma}-P_{\sigma}'\right\Vert_1\leq 4\). Thus if \(\lambda \geq 12\), this simplifies to \[\|E\|_F=\|\Sigma^{-1/2}(\Sigma' - \Sigma)\Sigma^{-1/2}\|_F \leq\frac{\left\Vert P_{\sigma}-P_{\sigma}'\right\Vert_1}{\lambda-\left\Vert P_{\sigma}-P_{\sigma}'\right\Vert_1}=O(\frac{1}{\lambda})\leq\frac{1}{2}.\] ◻

Proof. Algorithm 7 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 (\(\widetilde{F}_{t,+}\) and \(\widetilde{F}_{t,-}\)) and generating one covariance sample sequence (\(z, z_0\)) based on \(X_{t,\sigma_t},t_{t,\sigma_t}\). Consequently, the entire algorithm consists of \(3T\) adaptive mechanisms.

By Lemma 21 and the Gaussian Mechanism (Lemma 6), setting \(\nu=\Theta(\frac{\log(1/\delta_0)}{\varepsilon_0})\) ensures that each of the two objective evaluations is \((\varepsilon_0, \delta_0)\)-differentially private. For the covariance sample, combining Lemma 22 and Lemma 23 bounds the density ratio by \(e^{\varepsilon_0}\) with probability \((1-\delta_0)\). Symmetrically applying it in the reverse neighboring direction (as formalized in [3]) establishes that drawing the gradient samples satisfies \((\varepsilon_0, \delta_0)\)-differential privacy.

Therefore, setting the per-mechanism budgets to \(\varepsilon_0 = \Theta(\frac{\varepsilon}{\sqrt{3T \log(1/\delta)}})\) and \(\delta_0 = \Theta(\frac{\delta}{3T})\), by applying the Advanced Composition Theorem (Lemma 3) over the \(3T\) total mechanisms, Algorithm 7 is \((\varepsilon, \delta)\)-differentially private. ◻

Proof. Since \(X_{uu} = X_{vv} = 1\) and \(z \sim \mathcal{N}(0, X_{t,\sigma_t})\), the linear combination \((z_u - z_v)\) is a zero-mean Gaussian variable with variance: \[\mathbb{E}[(z_u - z_v)^2] =\left(\mathbb{E}[z_u^2] - 2\mathbb{E}[z_u z_v] + \mathbb{E}[z_v^2]\right) = (X_{t,\sigma_t})_{uu} - 2(X_{t,\sigma_t})_{uv} + (X_{t,\sigma_t})_{vv}= 2 - 2X_{uv}.\] Since for Gaussian random variable \(Y\sim \mathcal{N}(0,\sigma)\) there is \(\mathbb{E}[Y^2] = \sigma^2\) and \(\mathbb{E}[Y^4] = 3\sigma^4\), we have: \[\mathbb{E}[\widehat g_t (\{u,v\})]=\mathbb{E}\left[\frac{1}{4}(z_u - z_v)^2\right] = \frac{1 - (X_{t,\sigma_t})_{uv}}{2}, \quad \mathbb{E}[g_t^{\text{slack}}]=\mathbb{E}[z_0^2] = t_{t,\sigma_t},\] \[\mathbb{E}\left[\widehat{g}_t(\{u,v\})^2\right] = \frac{3}{16}\left(2 - 2(X_{t,\sigma_t})_{uv}\right)^2 \le \frac{3 - 3(X_{t,\sigma_t})_{uv}}{2}, \quad \mathbb{E}[(\widehat{g}_t^{\text{slack}})^2] = 3t_{t,\sigma_t}^2 \le 3t_{t,\sigma_t}.\] because \(X_{t,\sigma_t}\in\mathcal{X}\) ensures \(|(X_{t,\sigma_t})_{uv}| \le 1\) and \(t_{t,\sigma_t}\leq1\). Since \(g_t(e) = \min(B, \widehat g_t(e))\) and \(g_t^{\text{slack}} = \min(B, \widehat g_t^{\text{slack}})\), for every \(e=\{u,v\}\in\binom{V}{2}\): \[\mathbb{E} [\widehat g_t (e)-g_t (e)] = \mathbb{E}\left[ (\widehat g_t(e) - B) \cdot \mathbb{1}[\widehat g_t(e) > B] \right] = \int_B^\infty \mathbf{Pr}[\widehat g_t(e) > x] dx.\]

Since we can write \(\widehat g_t(\{u,v\}) = \frac{1-(X_{t,\sigma_t})_{uv}}{2} \cdot \xi^2\), where \(\xi \sim \mathcal{N}(0, 1)\) and \(\xi^2\) follows a chi-squared distribution with one degree of freedom (\(\chi_1^2\)). Applying the standard tail bound \(\mathbf{Pr}[\xi^2 > y] \leq e^{-y/2}\) for \(y \geq 1\) (Lemma 7), and noting that \(\frac{1-(X_{t,\sigma_t})_{uv}}{2} \leq 1\), the tail probability for all \(x \geq B \geq 1\) can be bounded by: \[\mathbf{Pr}[\widehat g_t(e) > x] = \mathbf{Pr}[\xi^2 > \frac{2x}{1-(X_{t,\sigma_t})_{uv}}]\leq\mathbf{Pr}[\xi^2 > x] \leq e^{-x/2}.\] Integrating this tail bound yields: \[\mathbb{E} [\widehat g_t (e)-g_t (e)] \leq \int_B^\infty e^{-x/2} dx = 2e^{-B/2}.\] Following the identical process for the slack variable where \(\widehat g_t^{\text{slack}} = t \cdot \xi^2\) with \(t \leq 1\), we obtain \(\mathbb{E}[\widehat g_t^{\text{slack}}-g_t^{\text{slack}}] \le 2e^{-B/2}\), which concludes the proof. ◻

Proof. In the following proof, we always condition on \(w_t\). Recall that we condition on the good event that all the Gaussian noises \(\{Z_{t,\sigma}\}_{t,\sigma}\) are bounded by \(O(\nu\sqrt{\log T})=\widetilde{O}_{\delta}(\sqrt{T}/\varepsilon)\leq\frac{\alpha}{32}\), by the assumption \(\alpha\geq\Omega_{\delta}(\frac{\sqrt{T}}{\varepsilon})\). Suppose Algorithm 7 does not terminate at iteration \(t\), then the chosen direction \(\sigma_t\) ensures a significant violation: \[\label{eq:utility95violation} \widehat{F}_{\sigma_t}(w, w^*,X_{t,\sigma_t},t_{t,\sigma_t}) \geq \frac{19\alpha}{32}-\frac{\alpha}{32}=\frac{9}{16}\alpha.\tag{18}\] For simplicity, we set: \[\begin{align} U &:= \sum_{u,v} w_t(\{u,v\})\frac{1 - (X_{t,\sigma_t})_{uv}}{2} + s(w_t)t_{t,\sigma_t},\\ U^* &:= \sum_{u,v} w^*(\{u,v\})\frac{1 - (X_{t,\sigma_t})_{uv}}{2} + s(w^*)t_{t,\sigma_t},\\ V&:=\sum_{u,v} (w_t(\{u,v\})-w^*(\{u,v\}))g_t + (s(w_t)-s(w^*))g_t^{\text{slack}},\\ \widehat{V}&:=\sum_{u,v} (w_t(\{u,v\})-w^*(\{u,v\}))\widehat{g}_t + (s(w_t)-s(w^*))\widehat{g}_t^{\text{slack}}. \end{align}\] Let \(W_t=\sum_{e} w_t(e) e^{-\theta_t\eta g_t(e)} + s(w_t) e^{-\theta_t\eta g_t^{\text{slack}}}\). The mirror descent update rule in [eq:mirror32descent32update] yields that: \[\begin{align} \Phi(t+1) - \Phi(t) &=\sum_{e} w^*_e \log \frac{(w_{t})_e}{(w_{t+1})_e} + s(w^*) \log \frac{s(w_t)}{s(w_{t+1})}\\ &=\sum_{e} w^*_e \log \frac{(w_{t})_e}{(w_{t})_ee^{-\theta_t\eta g_t(e)}M/W_t} + s(w^*) \log \frac{s(w_t)}{s(w_{t})e^{-\theta_t\eta g_t^{\text{slack}}}M/W_t}\\ &=\theta_t\eta \langle w^*, g_t \rangle + \theta_t\eta s(w^*) g_t^{\text{slack}}+M\log\frac{W_t}{M}. \end{align}\] Since \(e^{x} \leq 1 + x + x^2\) holds for every \(x\leq1/4\) and \(\eta |g_t(e)|\leq\eta B\leq\frac{1}{4}\) by the assumption⁷, together with \(\log(1+y) \leq y\), we have, \[\begin{align} \log\frac{W_t}{M} &=\log \left( \sum_{e} \frac{w_t(e)}{M} e^{-\theta_t\eta g_t(e)} + \frac{s(w_t)}{M} e^{-\theta_t\eta g_t^{\text{slack}}} \right)\\ &\leq\log \left( \sum_{e} \frac{w_t(e)}{M} (1-\theta_t\eta g_t(e)+\eta^2 g_t^2(e)) + \frac{s(w_t)}{M} (1-\theta_t\eta g_t^{\text{slack}}+\eta^2 (g_t^{\text{slack}})^2)\right)\\ &\leq\sum_{e} \frac{w_t(e)}{M} (-\theta_t\eta g_t(e)+\eta^2 g_t^2(e)) + \frac{s(w_t)}{M} (-\theta_t\eta g_t^{\text{slack}}+\eta^2 (g_t^{\text{slack}})^2). \end{align}\] Therefore, \[\begin{align} \Phi(t+1) - \Phi(t) &\leq -\theta_t\eta \left( \langle w_t - w^*, g_t \rangle + (s(w_t) - s(w^*))g_t^{\text{slack}} \right) + \eta^2 \left( \sum_{e} w_t(e) g_t(e)^2 + s(w_t) (g_t^{\text{slack}})^2 \right)\\ &=-\theta_t\eta V+ \eta^2 \left( \sum_{e} w_t(e) g_t(e)^2 + s(w_t) (g_t^{\text{slack}})^2 \right). \end{align}\] By Lemma 24, \(\mathbb{E}[\widehat g_t^2 (\{u,v\})]\le\frac{3 - 3(X_{t,\sigma_t})_{uv}}{2}\) and \(\mathbb{E}[(\widehat g_t^{\text{slack}})^2]\le3t_{t,\sigma_t}\), together with \(g_t\leq\widehat g_t\) and \(g_t^{\text{slack}}\leq\widehat g_t^{\text{slack}}\) we have, \[\mathbb{E}[g_t^2 (\{u,v\})]\leq \mathbb{E}[\widehat g_t^2 (\{u,v\})]\le\frac{3 - 3(X_{t,\sigma_t})_{uv}}{2}, \qquad \mathbb{E}[( g_t^{\text{slack}})^2]\leq\mathbb{E}[(\widehat g_t^{\text{slack}})^2]\le3t_{t,\sigma_t}.\] Therefore, \[\mathbb{E}\left[\eta^2 \left( \sum_{e} w_t(e) g_t(e)^2 + s(w_t) (g_t^{\text{slack}})^2 \right)\right]\leq 3\eta^2 U.\] By Lemma 24, \(\mathbb{E} [\widehat g_t (\{u,v\})-g_t (\{u,v\})] \le 2e^{-B/2}\) and \(\mathbb{E}[\widehat g_t^{\text{slack}}-g_t^{\text{slack}}] \le 2e^{-B/2}.\) Thus, \[\begin{align} \mathbb{E}[|\widehat{V}-V|] &\leq 2e^{-B/2} \left| \sum_e (w_t(e) + w^*(e)) + (s(w_t) + s(w^*)) \right| \\ &= 4M e^{-B/2}. \end{align}\] For the case when \(\sigma_t=+\), 18 implies \(U-(1+\gamma)U^*\geq\frac{9}{16}\alpha\). Note that \(\mathbb{E}[\widehat V]=U-U^*\) again because of Lemma 24. Then we have, \[\mathbb{E}[\widehat V]=U - U^* \geq \frac{\gamma}{1+\gamma}U + \frac{9}{16(1+\gamma)}\alpha.\] Similarly, for the case when \(\sigma_t=-\), 18 implies \((1-\gamma)U^*-U\geq\frac{9}{16}\alpha\). We have, \[\mathbb{E}[-\widehat V]=U^* - U \geq \frac{\gamma}{1-\gamma}U + \frac{9}{16(1-\gamma)}\alpha.\] Combining the above, we obtain, \[\begin{align} \mathbb{E}[\Phi(t+1) - \Phi(t)]&\leq-\eta\mathbb{E}[\theta_t\widehat V]+\eta\mathbb{E}[|\widehat V-V|]+ 3\eta^2 U\\ &\leq-\eta U \left( \frac{\gamma}{1+\theta_t\gamma} - 3\eta \right) - \frac{9\eta\alpha}{16(1+\theta_t\gamma)} + 4\eta M e^{-B/2}. \end{align}\] By the assumption that \(\eta \leq \frac{\gamma}{6(1+\gamma)}<\frac{\gamma}{6(1-\gamma)}\), the first term is negative for all \(U \geq 0\)⁸. By setting the clipping threshold to be \(B = \Theta(\log\frac{M}{\alpha})\), the third term can be smaller than \(\frac{\eta\alpha}{100}\). By setting \(\eta=\Theta(\frac{\gamma}{B})\), the requirement \(\eta \leq \frac{\gamma}{6(1+\gamma)}\) and \(\eta B\leq\frac{1}{4}\) can hold. Therefore, utilizing the fact that \(\gamma \in (0, 1/4)\) and \(\eta=\Theta(\frac{\gamma}{B})\), we conclude: \[\mathbb{E}[\Phi(t+1) - \Phi(t) \mid w_t] \leq 0- \frac{9\eta\alpha}{20} + \frac{\eta\alpha}{100} \leq -c \frac{\gamma \alpha}{B}.\] ◻

Proof of Lemma 26. Let \(t \ge 1\) denote the iteration index. We define the stochastic process \(X_t := \Phi(t) + \Delta \cdot t\) for any \(t\leq\tau\).⁹ By the assumption, for any \(t\leq\tau\), we have, \[\begin{align} \mathbb{E}[X_{t+1} \mid w_t] &= \mathbb{E}[\Phi(t+1) \mid w_t] + \Delta \cdot (t+1) =\mathbb{E}[\Phi(t+1)-\Phi(t) \mid w_t] +\Phi(t) + \Delta \cdot (t+1)\\ &\le - \Delta + \Phi(t) + \Delta \cdot (t+1) = \Phi(t) + \Delta \cdot t = X_t. \end{align}\] This implies that \((X_t)_{t \ge 1}\) is a supermartingale with respect to the filtration generated by \((w_t)_{t \ge 1}\).

Let \(\tau\) denote the first iteration where the halting condition \(\max(\widetilde{F}_{t,+}, \widetilde{F}_{t,-}) \leq 19\alpha/32\) is met (with \(\tau = \infty\) if it is never met). Since Algorithm 7 explicitly enforces a maximum iteration limit of \(T\), the actual number of executed steps is deterministically bounded by \(\tau_T = \min(\tau, T) \le T\). Because this bounded stopping time is valid for the optional stopping theorem (Proposition 18), we have: \[\mathbb{E}[X_{\tau_T}] \le \mathbb{E}[X_1] = \Phi(1) + \Delta.\] Since the Bregman divergence is non-negative, \(\Phi(\tau_T) \ge 0\), which yields: \[\Delta \cdot \mathbb{E}[\tau_T] \le \mathbb{E}[\Phi(\tau_T) + \Delta \cdot \tau_T] = \mathbb{E}[X_{\tau_T}] \le \Phi(1) + \Delta.\] By the identical calculation bounding the initial potential, we have \(\Phi(1) \le 2M \log n\). Therefore, the expected number of steps before halting or hitting the horizon is bounded by: \[\mathbb{E}[\tau_T] \le \frac{2M \log n}{\Delta} + 1 = O\left(\frac{M \log n}{\Delta}\right).\] To ensure the algorithm halts successfully before hitting the hard limit \(T\), we set \(T = \lceil 6 \cdot \mathbb{E}[\tau_T] \rceil = \Theta(\frac{M \log n}{\Delta})\). Applying Markov’s inequality unconditionally on the bounded variable \(\tau_T\): \[\mathbf{Pr}[\tau > T] \le \mathbf{Pr}[\tau_T \ge T] \le \frac{\mathbb{E}[\tau_T]}{T} \le \frac{1}{6}.\] Thus, with probability at least \(5/6\), the algorithm successfully terminates with a valid output within \(T\) iterations. ◻

Proof. Combining Lemma 25 and Lemma 26, if \(\alpha=\Omega_{\delta}(\frac{\sqrt{T}}{\varepsilon})\), setting the total iteration limits to \(T = \Theta(\frac{M\log n}{\gamma\alpha/B})=\Theta(\frac{BM\log n}{\gamma\alpha})\) ensures that the algorithm outputs \(w_t\) such that \(\max(\widetilde{F}_{t,+}, \widetilde{F}_{t,-}) \leq 19\alpha/32\) with probability at least \(5/6\). Since \(\{Z_{t,\sigma}\}_{t,\sigma}\) are bounded by \(O(\nu\sqrt{\log T})=\widetilde{O}_{\delta}(\sqrt{T}/\varepsilon)\leq\frac{\alpha}{32}\) with probability at least \(5/6\), we have, \(\max_{\sigma}F_{t,\sigma}(w_t,w^*)\leq\frac{19\alpha}{32}+\frac{\alpha}{32}=\frac{5\alpha}{8}\). By Lemma 20, if \(\rho = \min(\frac{1}{8},\frac{\alpha}{16\gamma M})\) and \(C_0 \lambda n \log(1/\rho) \leq \frac{\alpha}{32}\), we can conclude that, \[|\operatorname{cut}_w(S) - \operatorname{cut}_{w^*}(S)| \leq \gamma \operatorname{cut}_{w^*}(S) + \alpha\] holds for all \(S \subseteq V\).

Since we set \(\lambda=\Theta(\frac{\sqrt{T}\log^{3/2}(T/\delta)}{\varepsilon})\) and \(B=\Theta(\log\frac{M}{\alpha})\), combining them with \(C_0 \lambda n \log(1/\rho) \leq \frac{\alpha}{32}\) (already ensures \(\alpha=\Omega_{\delta}(\frac{\sqrt{T}}{\varepsilon})\)) and \(T =\Theta(\frac{BM\log n}{\gamma\alpha})\) yields \[\alpha=\widetilde{O}_{\delta}\left(\frac{\sqrt{T}n}{\varepsilon}\right)=\widetilde{O}_{\delta}\left(\frac{\sqrt{M}n}{\sqrt{\gamma\alpha}\varepsilon}\right).\] Also noting that \(T\geq1\), thus the total additive error \[\alpha = \widetilde{O}_{\delta}\left( \frac{n}{\varepsilon} + \left(\frac{n^2 M}{\varepsilon^2 \gamma}\right)^{1/3} \right).\] It can be verified that all assumptions in [lem:opt implies cut approx,thm:main_privacy,lem:potential progress] are satisfied under our choice of parameters. ◻

Proof of Theorem 14. We construct the final algorithm \(\mathsf{CutOracle}\) by executing the core subroutine (Algorithm 7) repeatedly. Let \(K = \lceil C \log(1/\beta) \rceil\) for a sufficiently large absolute constant \(C\). The oracle runs Algorithm 7 up to \(K\) times independently. If an execution returns a valid edge-weight vector \(w_t\) (instead of "\(\perp\)"), \(\mathsf{CutOracle}\) halts immediately and outputs \(w_t\). If all \(K\) executions return "\(\perp\)", it outputs an empty graph.

6.4.0.1 Privacy Guarantee.

In the worst case, the algorithm executes the subroutine \(K\) times. We allocate a local privacy budget \((\varepsilon_0, \delta_0)\) to each individual run. By the advanced composition Theorem (Lemma 3), it suffices to set: \[\varepsilon_0 = \Theta\left(\frac{\varepsilon}{\sqrt{K \log(1/\delta)}}\right), \quad \delta_0 = \frac{\delta}{2K}.\] As the halting condition only depends on the privately released \(\widetilde{F}_{t,\sigma}\), the adaptive stopping time is private due to post-processing(Lemma 1). Finally, combing Theorem 17 concludes the proof.

6.4.0.2 Utility Guarantee.

We bound the failure probability by analyzing two failure events. First, let \(\mathcal{E}_{\text{noise}}^c\) be the event that any drawn Gaussian noise \(|Z_{t, \sigma}|\) across all \(K\) runs and \(T\) iterations exceeds \(\alpha/32\). Since \(Z_{t, \sigma} \sim \mathcal{N}(0, \nu^2)\), applying standard Gaussian tail bounds (Lemma 10) and a union bound over the \(2KT\) random variables guarantees that setting \(\alpha = \Omega(\nu \sqrt{\log(KT/\beta)})\) is enough to guarantee \(\mathbf{Pr}[\mathcal{E}_{\text{noise}}^c] \le \beta/2\). Second, let \(\mathcal{E}_{\text{all 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 19), which bounds the failure probability of a single run by \(1/3\). Thus, the probability is \(\mathbf{Pr}[\mathcal{E}_{\text{all abort}}] \le (1/3)^K \le \beta/2\) (by our choice of constant \(C\)).

By the union bound, the probability that the algorithm either suffers from large noise or abort is bounded by \(\mathbf{Pr}[\mathcal{E}_{\text{noise}}^c \cup \mathcal{E}_{\text{all abort}}] \le \beta/2 + \beta/2 = \beta\). Therefore, with probability at least \(1-\beta\), neither failure event occurs. Because \(\mathcal{E}_{\text{all abort}}\) does not occur, the algorithm successfully halts and outputs a graph; because \(\mathcal{E}_{\text{noise}}^c\) does not occur, the analysis in Theorem 19 guarantees this output graph satisfies the target error bound: \[\alpha = \widetilde{O}_{\delta}\left( \frac{n}{\varepsilon_0} + \left(\frac{n^2 M}{\varepsilon_0^2 \gamma}\right)^{1/3} \right).\] Substituting \(\varepsilon_0 = \Theta\left(\frac{\varepsilon}{\sqrt{\log(1/\beta) \log(1/\delta)}}\right)\), the error scales as: \[\alpha = \widetilde{O}_{\delta}\left( \frac{n \sqrt{\log(1/\beta)}}{\varepsilon} + \left(\frac{n^2 M \log(1/\beta) }{\varepsilon^2 \gamma}\right)^{1/3} \right),\] where the \(\widetilde{O}_{\delta}(\cdot)\) hides polylogarithmic factors in \(n, 1/\delta\).

6.4.0.3 Implementation.

Follow a similar proof to [3], 7 can be implemented in time \(\tilde{O}_{\varepsilon,\delta,\gamma}(n^{20/3}\log^{O(1)}(n))\) with the same level of guarantee for additive error and privacy. Here we only give a proof sketch.

By 7 and Lemma 19, we have \(T=\Theta(\frac{BM\log n}{\gamma\alpha})=\tilde{O}_{\varepsilon,\delta,\gamma}(M^{2/3}n^{-2/3})\). In each iteration, note that the update step runs in \(O(n^2)\) time. Denote \(X^*,t^*\) be the maximizer of the SDP \(\max_{X\in\mathcal{X},\rho\le t\le 1}\hat{F}_{\sigma}(w,w^*,X,t)\) and \(\Sigma^* = \left(\begin{array}{cc} X^{*} & 0 \\ 0 & t^{*} \end{array}\right)\). We use the algorithm of [43] to find an approximate solution \(X,t\) (let \(\Sigma = \left(\begin{array}{cc} X & 0 \\ 0 & t \end{array}\right)\)) of the SDP in 7 in time \(\tilde{O}(n^6\log^{O(1)}(n/\mu))\), s.t., \(\left\Vert(\Sigma^*)^{-\frac{1}{2}}(\Sigma^*-\Sigma)(\Sigma^*)^{-\frac{1}{2}}\right\Vert_F\leq\mu\). Therefore, across all \(K\) rounds and \(T\) iterations, our algorithm can be implemented in time \(\tilde{O}_{\varepsilon,\delta,\gamma}(M^{2/3}n^{16/3}\log^{O(1)}(n))=\tilde{O}_{\varepsilon,\delta,\gamma}(n^{20/3}\log^{O(1)}(n))\). According to [3], the additive error only differs by a constant factor when we choose \(\mu=1/n^{O(1)}\). And the privacy loss in each iteration is still \(O(\frac{1}{\lambda})\) by Lemma 22, hence the privacy guarantee is the same as before. This concludes the proof of Theorem 14. ◻

Proof. The true degree vector \(deg_R(\cdot)\) has an \(\ell_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 5) by adding independent noise variables \(Z_v \sim \texttt{Lap}(2/\varepsilon_{deg})\) and computing the noisy degrees \(\widetilde{d}_v = deg_R(v) + Z_v\). This is \((\varepsilon_{deg}, 0)\)-DP.

To ensure that the capacity condition holds even under worst-case negative noise, we define a high-probability noise bound \(a = \frac{2}{\varepsilon_{deg}} \ln\left(\frac{n}{\beta_{deg}}\right)\). We further apply a deterministic upper cap: since the true degree satisfies \(deg_R(v) < n\), we hard-cap the shifted noisy degree at \(n+2a\): \[\label{eq:demand95allocation} b_v = \rho(v) = 1 + \left\lceil\frac{\min\{n+2a, \max\{0, \widetilde{d}_v + a\}\}}{D}\right\rceil.\tag{19}\] Deterministically, this hard cap limits the total demand to \[\rho \leq n\left(2 + \frac{n + \frac{4}{\varepsilon_{deg}}\ln(n/\beta_{deg})}{D}\right).\]

By the tail bounds of the Laplace distribution (Lemma 4) and a union bound over all \(n\) vertices, the good event that \(|Z_v| \le a\) for all \(v \in V\) holds with probability at least \(1 - \beta_{deg}\). Conditioning on this good event, \(Z_v \ge -a\) guarantees that \(\widetilde{d}_v + a = deg_R(v) + Z_v + a \ge deg_R(v)\). Because the true degree \(deg_R(v) < n \le n+2a\), the deterministic cap never pulls the value below the true degree. Consequently, the allocated number of ports unconditionally guarantees \(b_v \ge deg_R(v)/D\) on this good event, satisfying the Capacity property.

To bound the total demand mass \(\rho(V)\) accurately on this good event, we sum the unclipped values over all vertices: \[\rho(V) = \sum_{v \in V} b_v \le n + \sum_{v \in V} \frac{deg_R(v) + 2a + 1}{D} \le n + \frac{2M}{D} + \frac{n(2a+1)}{D}.\] Since \(D = \max\{1, M/n\}\), we have \(2M/D \le 2n\). Therefore, substituting the constants yields \(\rho(V) \le 3n + n(2a+1)/D = \widetilde{O}_{\varepsilon_{deg}}(n)\), concluding the proof. ◻

Proof. For each vertex \(v \in V\), we instantiate its \(\rho(v)\) ports. To distribute the original incident edges among these ports, we draw fresh, fully independent public hash functions \(h_v: V \setminus \{v\} \to [\rho(v)]\). For any original edge \(e = \{u, v\} \in E_R\), its projection is deterministically mapped to the port pair \(\{(u, h_u(v)), (v, h_v(u))\}\). To enforce a worst-case upper bound on the maximum degree of \({}^\sharp R\), we apply a deterministic truncation mechanism. For each port \((v, j)\), we define its candidate incident set as \(C_{v,j}(R) = \{ \{u, v\} \in E_R : h_v(u) = j \}\). Instead of accepting all candidates, we sort \(C_{v,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 = 2\mathrm{e}D + 3 \ln(2 \rho(V) / \beta_{util})\) elements, yielding the truncated set \(\mathrm{Top}_B(C_{v,j}(R))\). A candidate edge is added to \({}^\sharp R\) if and only if it survives the truncation at both endpoints. This hard cutoff guarantees that the maximum degree \(\Delta({}^\sharp R) \le B\). Since Lemma 27 bounds \(\rho(V) \le \widetilde{O}(n)\), the threshold simplifies to \(B = {O}(D) + O\left(\ln({n}/{\beta_{util}})\right)\), which proves the 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: \(C_{x, h_x(y)}\) and \(C_{y, h_y(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 \(\mathrm{Top}_B\) 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({}^\sharp R)\) and \(E({}^\sharp 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 \(\rho(v) \ge deg_R(v)/D\) (Lemma 27), the expected load for any port \((v, j)\) is \(\mu_{v,j} = \mathbb{E}{|C_{v,j}(R)|} = deg_R(v)/\rho(v) \le D\). By applying the standard Chernoff bound (Lemma 11), the probability that the load exceeds the threshold \(B\) is upper bounded by \[\mathbf{Pr}[|C_{v,j}(R)| \ge B] \le \frac{\beta_{util}}{\rho(V)}.\] Taking a union bound over all \(\rho(V)\) ports across the entire graph, the probability that any port overflows its capacity \(B\) is bounded by \(\beta_{util}\). When no overflow occurs, every edge in \(E_R\) passes the truncation at both endpoints, establishing an exact bijection between the edges of \(R\) and \({}^\sharp R\). Therefore, mapping the vertices of \(S\) to their corresponding ports \({}^\sharp S\) preserves the cut edges across the boundary, yielding \(w_R(S, V \setminus S) = w_{{}^\sharp R}({}^\sharp S, V({}^\sharp R) \setminus {}^\sharp S)\) holds with probability at least \(1- \beta_{util}\), which concludes the proof. ◻

Proof. The oracle \(\mathsf{SyntheticOracle}(H, \rho,\varepsilon,\delta)\) simply first builds the proxy graph \({}^\sharp H\) with \(\rho\) and then run the generic spectral oracle (Assumption 1) on \({}^\sharp H\) to generate a synthetic graph.

Instead of inducing from a globally truncated port graph \({}^{\sharp}R\) (which could leak information and introduce more sensitivity from edges outside \(U\)), we construct the local port proxy graph \({}^\sharp H\) with \(\mathsf{BuildGadget}(H, \rho)\) (Lemma 28) directly on the induced subgraph \(H = R[U]\). We define the lifted vertex set exclusively for \(U\) as \({}^\sharp U = \bigcup_{v \in U} \{(v, j) : j \in [\rho(v)]\}\). The total number of micro-nodes in \({}^\sharp H\) evaluates to the local demand mass, bounded by the global capacity: \[|V({}^\sharp H)| = |{}^\sharp U| = \sum_{v \in U} \rho(v) = \rho(U) \le \rho(V) \le \widetilde{O}(n).\]

We then invoke the private spectral primitive (Assumption 1) on \({}^\sharp H\). Because the addition or removal of an original edge in \(R\) modifies at most \(c=4\) edges in \({}^\sharp H\)¹⁰, treating the graph \({}^\sharp 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 parameters \(\varepsilon' = \varepsilon/ c\) and \(\delta' = \delta / \sum_{j=0}^{c-1} e^{j\varepsilon'}\) ensures \((\varepsilon, \delta)\)-edge-DP. The mechanism outputs a synthetic graph Laplacian \(\widehat{L}_{{}^\sharp H}\). We define the error matrix \(E = L_{{}^\sharp H} - \widehat{L}_{{}^\sharp H}\). Given that \(\Pi(\cdot, \cdot, \cdot, \cdot, \cdot)\) is monotonically non-decreasing in dimensions and monotonically non-increasing in privacy parameters, with probability at least \(1-\beta\), the spectral norm of \(E\) satisfies: \[\label{eq:spectral95norm95E} \left\Vert E\right\Vert_2 \le \widetilde{O} \left( \Pi(|V({}^\sharp H)|, \Delta({}^\sharp H), \varepsilon', \delta', \beta) \right).\tag{20}\] Here, \(\Delta({}^\sharp H)\) is bounded by \(O(\max\{1, M/n\}) + O(\log(n/\beta'))\) due to Lemma 28. According to Assumption 1, the polylogarithmic inflation in vertices and degrees, alongside the constant splitting of privacy budgets, can be absorbed into the \(\widetilde{O}\) notation. This cleanly yields: \[\label{eq:spectral95norm95E95simplified} \left\Vert E\right\Vert_2 \le \widetilde{O} \left( \Pi(n, \max\{1, M/n\}, \varepsilon, \delta, \beta) \right) := \Lambda_\rho(M, \varepsilon, \delta, \beta).\tag{21}\] To form the final synthetic graph \(\widehat{H}\) on the original vertex space \(U\), we collapse the micro-nodes back to their source vertices. Note that, the Laplacian \(\widehat{L}_H\) of the synthetic graph \(\widehat{H}\) is defined by summing the corresponding block submatrices of \(\widehat{L}_{{}^\sharp H}\): \[\widehat{L}_H(u,v) = \sum_{i=1}^{\rho(u)} \sum_{j=1}^{\rho(v)} \widehat{L}_{{}^\sharp H}((u,i), (v,j)).\] For any cut \(S \subseteq U\), we lift it to the port space by defining its indicator vector \(1_{{}^\sharp S} \in \{0,1\}^{|{}^\sharp U|}\), where \((1_{{}^\sharp S})_{(v, i)} = 1\) if and only if \(v \in 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-\beta_{util} = 1-1/n^c\). Consequently, the cut weight in \(H\) can be formulated identically as the quadratic form of the port Laplacian: \[w_H(S, U \setminus S) = w_{{}^\sharp H}({}^\sharp S, {}^\sharp U \setminus {}^\sharp S) = 1_{{}^\sharp S}^\top L_{{}^\sharp H} 1_{{}^\sharp S}.\] Simultaneously, the matrix block-sum definition guarantees that the cut value in the synthetic graph \(\widehat{H}\) translates to the same quadratic form under the synthetic Laplacian: \[w_{\widehat{H}}(S, U \setminus S) = 1_{{}^\sharp S}^\top \widehat{L}_{{}^\sharp H} 1_{{}^\sharp S}.\] The absolute additive error is therefore equivalent to the quadratic form evaluated over the error matrix \(E\): \[\label{eq:additive95error95S} |w_H(S, U \setminus S) - w_{\widehat{H}}(S, U \setminus S)| = \left\vert 1_{{}^\sharp S}^\top (L_{{}^\sharp H} - \widehat{L}_{{}^\sharp H}) 1_{{}^\sharp S} \right\vert = \left\vert 1_{{}^\sharp S}^\top E 1_{{}^\sharp S} \right\vert.\tag{22}\] Applying the standard operator norm inequality, we bound the quadratic form utilizing 20 and the \(\ell_2\)-norm of the indicator vector: \[\label{eq:error95bound95S} \left\vert 1_{{}^\sharp S}^\top E 1_{{}^\sharp S} \right\vert \le \left\Vert E\right\Vert_2 \left\Vert 1_{{}^\sharp S}\right\Vert_2^2 \le \Lambda(M, \varepsilon, \delta) \sum_{v \in S} \sum_{i=1}^{\rho(v)} 1^2 = \Lambda(M, \varepsilon, \delta) \sum_{v \in S} \rho(v) = \Lambda(M, \varepsilon, \delta) \rho(S).\tag{23}\] To establish the complementary bound for the complement cut \(U \setminus S\), we note that by the definition of graph Laplacian matrix: \(L_{{}^\sharp H} \mathbf{1} = \mathbf{0}\) and \(\widehat{L}_{{}^\sharp H} \mathbf{1} = \mathbf{0}\) hold unconditionally, implying \[E \mathbf{1} = (L_{{}^\sharp H} - \widehat{L}_{{}^\sharp H} )\mathbf{1} = L_{{}^\sharp H} \mathbf{1} - \widehat{L}_{{}^\sharp H} \mathbf{1}= \mathbf{0}.\] We express the all-ones vector as \(\mathbf{1} = 1_{{}^\sharp S} + 1_{{}^\sharp U \setminus {}^\sharp S}\) and expand the quadratic form of the complement indicator vector: \[1_{{}^\sharp U \setminus {}^\sharp S}^\top E 1_{{}^\sharp U \setminus {}^\sharp S} = (\mathbf{1} - 1_{{}^\sharp S})^\top E (\mathbf{1} - 1_{{}^\sharp S}) = \mathbf{1}^\top E \mathbf{1} - \mathbf{1}^\top E 1_{{}^\sharp S} - 1_{{}^\sharp S}^\top E \mathbf{1} + 1_{{}^\sharp S}^\top E 1_{{}^\sharp S}.\] Note that \(E \mathbf{1} = \mathbf{0}\) and \(\mathbf{1}^\top E = \mathbf{0}^\top\), which yields that: \[1_{{}^\sharp U \setminus {}^\sharp S}^\top E 1_{{}^\sharp U \setminus {}^\sharp S} = 1_{{}^\sharp S}^\top E 1_{{}^\sharp S}.\] Substituting this symmetric equality into the operator norm inequality mirroring 23 : \[\label{eq:error95bound95US} \left\vert 1_{{}^\sharp S}^\top E 1_{{}^\sharp S} \right\vert = \left\vert 1_{{}^\sharp U \setminus {}^\sharp S}^\top E 1_{{}^\sharp U \setminus {}^\sharp S} \right\vert \le \left\Vert E\right\Vert_2 \left\Vert 1_{{}^\sharp U \setminus {}^\sharp S}\right\Vert_2^2 \le \Lambda(M, \varepsilon, \delta) \sum_{v \in U \setminus S} \rho(v) = \Lambda(M, \varepsilon, \delta) \rho(U \setminus S).\tag{24}\] Combining Eq. 23 and Eq. 24 simultaneously restricts the absolute error to the minimum of the two respective demand masses, concluding the proof. ◻

Proof. We first construct a trimmed and capped proxy graph \(\widehat{H}'\) from \(\widehat{H}\) to bound the dynamic range of the edge weights. We define a minimum weight threshold \(\theta = \frac{\psi}{10n}\) and a maximum capacity bound \(W_{\max} = \psi \rho(U)\). To form \(\widehat{H}'\), we simply delete any edge \(e \in \widehat{H}\) with weight \(w_e < \theta\), and truncate any edge with \(w_e > W_{\max}\) to exactly \(W_{\max}\). The ratio of the maximum to non-zero minimum edge weight in \(\widehat{H}'\) is therefore bounded by \(W_{\max} / \theta = 10 n \rho(U) \le \mathrm{poly}(n)\). We then execute the deterministic demand-vector routine (Theorem 20, or Theorem 2.14 in [44]) on \(\widehat{H}'\) with a target sparsity threshold of \(0.8\psi\). If the algorithm in Theorem 20 fails to find a cut meeting this threshold, we output \(\varnothing\); otherwise, we output the returned cut \(S\).

First, we assume the algorithm outputs \(S \neq \varnothing\) and prove the sparsity guarantee. By the guarantee of such cut in Theorem 20, \(w_{\widehat{H}'}(S, U \setminus S) \le 0.8\psi \rho(S)\). We prove by contradiction that the cut \(S\) does not sever any capped edges. If it did, the weight of the cut in \(\widehat{H}'\) would be at least \(W_{\max} = \psi \rho(U)\). Since \(S\) is the smaller demand side, \(\rho(S) \le \rho(U)/2\), which implies \(\psi \rho(U) \ge 2\psi \rho(S) > 0.8\psi \rho(S)\), which leads to a contradiction. Thus, the cut \(S\) evaluates identically in \(\widehat{H}'\) and \(\widehat{H}\) except for the deleted small edges. The total weight of all deleted edges crossing the cut is naively bounded by \(\theta \cdot |S| \cdot |U \setminus S| \le \theta n \rho(S) = 0.1\psi \rho(S)\). Consequently, the uncut synthetic weight is bounded by \(w_{\widehat{H}}(S, U \setminus S) \le w_{\widehat{H}'}(S, U \setminus S) + 0.1\psi \rho(S) \le 0.9\psi \rho(S)\). Applying the additive error guarantee from Lemma 29, the true weight in \(H\) evaluates to: \[\begin{align} w_H(S, U \setminus S) &\le w_{\widehat{H}}(S, U \setminus S) + \Lambda_\rho \rho(S) \nonumber \\ &\le 0.9\psi \rho(S) + \left(\frac{\psi}{10 c_{exp}}\right) \rho(S) \le \psi \rho(S). \end{align}\]

Next, we establish the bicriteria maximality. Assume there exists an optimal sparse cut \(S'\) satisfying \(w_H(S', U \setminus S') \le \frac{\psi}{c_{exp}} \rho(S')\). The oracle’s additive error guarantees that the weight of \(S'\) in the synthetic graph \(\widehat{H}\) is bounded by: \[w_{\widehat{H}}(S', U \setminus S') \le w_H(S', U \setminus S') + \Lambda_\rho \rho(S') \le \left( \frac{\psi}{c_{exp}} + \Lambda_\rho \right) \rho(S').\] By setting \(c_{exp} = 4 d_{exp}\) (recall that \(d_{exp} = \mathrm{polylog}(n)\) is the internal expansion loss of in Theorem 20) and invoking the premise \(\psi \ge 10 c_{exp} \Lambda_\rho\), we see that: \[\frac{\psi}{c_{exp}} + \Lambda_\rho \le \frac{\psi}{4 d_{exp}} + \frac{\psi}{40 d_{exp}} = 0.275 \frac{\psi}{d_{exp}}.\] Because the trimming and capping operations can only decrease the weight of an existing cut, the weight of \(S'\) in \(\widehat{H}'\) satisfies that \(w_{\widehat{H}'}(S', U \setminus S') \le 0.275 \frac{\psi}{d_{exp}} \rho(S') \le 0.8 \frac{\psi}{d_{exp}} \rho(S')\). Under this condition, the bicriteria guarantee in Theorem 20 dictates that the returned cut \(S \neq \varnothing\) satisfies \(\rho(S) \ge \frac{\rho(S')}{d_{size}}\). Setting \(c_{size} = d_{size} = O(1)\) concludes the utility proof.

For the privacy proof, we note that Algorithm 8 does not consume more privacy budgets than the private spectral oracle (Assumption 1) as all trimming, capping, and the computations in Theorem 20 are deterministic post-processing steps applied exclusively to the \((\varepsilon,\delta)\)-edge-DP synthetic graph \(\widehat{H}\) given by the spectral primitive in Assumption 1. ◻

Proof. This proof is a demand-weighted analogue of the global expansion-decomposition analysis of Nanongkai and Saranurak [28]. The hard depth cap in Algorithm 9 ensures termination and privacy on every transcript. We first analyze utility on the event that every invocation of \(\mathsf{CutFinder}\) satisfies the guarantees of Lemma 30. For a graph \(J\) and a sparsity parameter \(\varphi\), define \[\operatorname{OPT}_\rho(J,\varphi) := \max\left\{ \rho(X): \begin{array}{l} \varnothing\neq X\subsetneq V(J),\\ \rho(X)\le \rho(V(J)\setminus X),\\ w_J(X,V(J)\setminus X)\le \varphi\rho(X) \end{array} \right\}, \label{eq:demand-opt}\tag{26}\] where the maximum is defined to be zero when no such cut exists.

As in [28], 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')\setminus 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 \[\operatorname{OPT}_\rho(I,2\psi_l)<\overline{s}_l. \label{eq:demand-opt-invariant}\tag{27}\] For \(l=1\), every smaller side of a cut in \(I\) has demand at most \(\rho(V(I))/2\le \+R/2<\overline{s}_1\). 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 \[\rho(S)<\frac{\overline{s}_{l+1}}{c_{size}}.\] By the choice of the level parameters, \[2\psi_{l+1} = \frac{\psi_l}{c_{exp}}. \label{eq:level-parameter-relation}\tag{28}\] The bicriteria maximality guarantee of Lemma 30 therefore implies \[\operatorname{OPT}_\rho(H',2\psi_{l+1}) = \operatorname{OPT}_\rho \left(H',\frac{\psi_l}{c_{exp}}\right) \le c_{size}\rho(S) <\overline{s}_{l+1}.\] This proves 27 inductively.

Because \(\overline{s}_L\le 1\) and all nonempty demand masses are positive integers, the invariant at level \(L\) implies \[\operatorname{OPT}_\rho(H',2\psi_L)=0\] whenever the analytical anchor is \(I=H'\). If \(\mathsf{CutFinder}(H',\psi_L)\) returned a nonempty cut, its sparsity guarantee would make that cut \(\psi_L\)-sparse, and hence also \(2\psi_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 [28], call the edge to the smaller-side child a left edge, the edge to the larger-side child a right edge, and a level-increment edge a down edge. Along any root-to-leaf path, there are at most \(\lceil\log_2\+R\rceil\) 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 \(H_1\). Write \[H_{i+1}=H_i[V(H_i)\setminus S_i], \qquad X_j=\bigcup_{i=1}^j S_i, \qquad r=\rho(V(H_1)).\] Each cut in this sequence satisfies \[\rho(S_i)\ge \frac{\overline{s}_{l+1}}{c_{size}}, \qquad \rho(S_i)\le\frac{\rho(V(H_i))}{2}, \qquad w_{H_i}(S_i,V(H_i)\setminus S_i) \le\psi_l\rho(S_i). \label{eq:right-edge-properties}\tag{29}\] The sets \(S_i\) are disjoint, and every edge crossing \((X_j,V(H_1)\setminus X_j)\) is contained in one of the cuts removed so far. Consequently, \[w_{H_1}(X_j,V(H_1)\setminus X_j) \le \sum_{i=1}^j w_{H_i}(S_i,V(H_i)\setminus S_i) \le \psi_l\rho(X_j). \label{eq:union-cut-bound}\tag{30}\]

Set \[a:=\frac{\overline{s}_{l+1}}{c_{size}}, \qquad g:=c_{size}\+R^\sigma,\] so that \(ga=\overline{s}_l\). Suppose first that \(r\le 3\overline{s}_l\). Then fewer than \(3c_{size}\+R^\sigma\) right edges are possible, since otherwise the disjoint removed sets would have total demand at least \(3c_{size}\+R^\sigma a=3\overline{s}_l\ge r\), while the current right-side component has positive demand.

Now suppose that \(r>3\overline{s}_l\). If there were at least \(\lceil g\rceil\) right edges, let \(j\) be the first index for which \[x:=\rho(X_j)\ge\overline{s}_l, \qquad x^-:=\rho(X_{j-1})<\overline{s}_l.\] Since \(S_j\) is the smaller side in \(H_j\), we have \[x = x^-+\rho(S_j) \le x^-+\frac{r-x^-}{2} = \frac{r+x^-}{2} < \frac{r+\overline{s}_l}{2} < \frac{2r}{3}.\] If \(x\le r/2\), then 30 shows that \(X_j\) is a \(2\psi_l\)-sparse smaller side with demand at least \(\overline{s}_l\). If \(x>r/2\), let \(Y=V(H_1)\setminus X_j\). Then \[\rho(Y)=r-x>\frac{r}{3}>\overline{s}_l \qquad\text{and}\qquad x\le 2\rho(Y).\] Using 30 , \[w_{H_1}(Y,V(H_1)\setminus Y) \le \psi_l x \le 2\psi_l\rho(Y).\] Thus, in either case, \(H_1\) contains a \(2\psi_l\)-sparse smaller side of demand at least \(\overline{s}_l\), contradicting the invariant 27 . Therefore every such sequence contains fewer than \[\Gamma=\left\lceil3c_{size}\+R^\sigma\right\rceil\] right edges.

There are at most \(1+\lceil\log_2\+R\rceil\) blocks separated by left edges, and each block contains at most \(L\) level segments. Hence every root-to-leaf path contains at most \[(1+\lceil\log_2\+R\rceil) \bigl(1+L(1+\Gamma)\bigr) = D_{\max}\] 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[V_i]\) is returned only when \(\mathsf{CutFinder}(H',\psi_l)\) outputs \(\varnothing\). By the contrapositive of the bicriteria maximality guarantee in Lemma 30, no cut \(S'\subsetneq V_i\) satisfies \[w_{H'}(S',V_i\setminus S') \le \frac{\psi_l}{c_{exp}} \min\{\rho(S'),\rho(V_i\setminus S')\}.\] By the definition of \(\psi_l\), \[\frac{\psi_l}{c_{exp}} = \psi\,\widehat c_{exp}^{\,L-l} \ge \psi. \label{eq:leaf-expansion-threshold}\tag{31}\] It follows that \(G[V_i]\) is a \((\psi,\rho)\)-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 30, \[w_{H'}(S,V(H')\setminus S)\le\psi_l\rho(S)\le\psi_1\rho(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, \[\begin{align} \sum_{\text{inter-component cuts}} w_{H'}(S,V(H')\setminus S) &\le O(\psi_1\+R\log\+R)\\ &= O\left( \psi\+R\log\+R\, \widehat c_{exp}^{\,L} \right)\\ &= \psi\+R^{1+o(1)}. \end{align}\] The last equality follows from \(L=O(1+1/\sigma)\) and \[\widehat c_{exp}^{\,L} = \exp\left( O\left( \sqrt{\log\+R\log\widehat c_{exp}} +\log\widehat c_{exp} \right) \right) = \+R^{o(1)}.\]

It remains to prove privacy and bound the failure probability. The hard cap ensures unconditionally that at most \(D_{\max}\) 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 \((\varepsilon_{step},\delta_{step})\)-DP by parallel composition. Sequential composition (Lemma 2) across at most \(D_{\max}\) depths gives \[\left( D_{\max}\varepsilon_{step}, D_{\max}\delta_{step} \right) = (\varepsilon,\delta).\] The hard-cap and level-cap return operations are post-processing and consume no additional privacy budget. Thus the algorithm is \((\varepsilon,\delta)\)-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 \[N_{\max}=|V(H)|D_{\max}.\] Each adaptive invocation has conditional utility-failure probability at most \(\beta_{step}\). Independence is not required: a conditional union bound gives \[\mathbf{Pr}[\text{some oracle invocation fails}] \le N_{\max}\beta_{step} = \beta.\] Finally, for every level \(l\), \[\psi_l\ge\psi_L=\psi c_{exp}.\] Condition 25 therefore implies \[\psi_l \ge 10c_{exp} \Lambda_\rho \left(\varepsilon_{step},\delta_{step},\beta_{step}\right),\] so Lemma 30 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-\beta\). ◻

Proof. (Of Theorem 21.) We analyze the utility, dynamical recurrence, privacy, and probability bounds consecutively to establish Theorem 21. For any cut \(C \subseteq V\), every original unweighted edge \(e \in E\) is either absorbed inside some component \(U \in \+P_t\) 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: \[\label{eq:cut95decomposition95true} w_G(C) = \sum_{t=0}^{T-1} \sum_{U \in \+P_t} w_{R_t[U]}(C \cap U, U \setminus C) + w_{R_T}(C).\tag{32}\] On the other hand, by the definition of the out \(\widetilde{G}\), the estimated cut size evaluates to: \[\label{eq:cut95decomposition95syn} w_{\widetilde{G}}(C) = \sum_{t=0}^{T-1} \sum_{U \in \+P_t} w_{\widehat{H}_{t,U}}(C \cap U, U \setminus C) + w_{\widehat{R}_T}(C),\tag{33}\] where \(\widehat{R}_T\) is the output of the terminal release mechanism.

For any internal component \(U \in \+P_t\), according to Lemma 31, the subgraph \(R_t[U]\) is an \((\psi_t, \rho_t)\)-expander (6 ). Invoking the demand-sensitive oracle error (Lemma 29) and substituting the expansion bound \(w_{R_t[U]} \ge \psi_t \min\{\rho_t(C \cap U), \rho_t(U \setminus 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 \(\gamma_{internal} = \gamma/2\): \[\begin{align} \label{eq:local95absorption} \left\vert w_{R_t[U]} - w_{\widehat{H}_{t,U}} \right\vert &\le \Lambda_t \min\{\rho_t(C \cap U), \rho_t(U \setminus C)\} \nonumber \\ &\le \frac{\Lambda_t}{\psi_t} w_{R_t[U]}(C \cap U, U \setminus C) \le \frac{\gamma}{2} w_{R_t[U]}(C \cap U, U \setminus C). \end{align}\tag{34}\] Summing Eq. 34 across all components \(U\) and rounds \(t\), the aggregated error over all internal releases is then bounded by: \[\begin{align} \label{eq:internal95multiplicative95bound} \sum_{t=0}^{T-1} \sum_{U \in \+P_t} \left\vert w_{R_t[U]} - w_{\widehat{H}_{t,U}} \right\vert &\le \frac{\gamma}{2} \sum_{t=0}^{T-1} \sum_{U \in \+P_t} w_{R_t[U]}(C \cap U, U \setminus C) \nonumber \\ &\le \frac{\gamma}{2} w_G(C). \end{align}\tag{35}\]

To determine the final error of the terminal residual graph \(R_T\), we map the trajectory of the residual edge sequence \(M_t\). Utilizing the fact \(\rho_t(V) \le \widetilde{O}(n)\) (Lemma 27) and substituting \(\psi_t\), the recurrence across \(T\) rounds is governed by the spectral error interface \(\Pi\) evaluated at the deep recursion budgets \(\varepsilon_{step} = \varepsilon/(8T n^{o(1)})\) and \(\delta_{step} = \delta/(8T n^{o(1)})\). Crucially, the expander decomposition incurs an \(n^{o(1)}\) penalty on both the residual edges and the privacy parameters (Lemma 31). Invoking Assumption 1 again, the \(n^{o(1)}\) shrinkage in privacy parameters inflates the error \(\Pi\) by at most an \(n^{o(1)}\) multiplicative overhead. We explicitly extract and incorporate this penalty: \[M_{t+1} = \psi_t \rho_t(V)^{1+o(1)} \le \widetilde{O} \left( \Pi\left(n, \max\left\{1, \frac{M_t}{n}\right\}, \frac{\varepsilon}{T}, \frac{\delta}{T}\right) n^{1+o(1)} \gamma^{-1} T \right).\]

Starting from the initial dense graph configuration \(M_0 = n^2\), this recursive process produces the terminal residual edge count \(M_T\) after \(T\) iterations. We then process \(R_T\) via the relative terminal release mechanism \(\mathsf{CutOracle}\) (Theorem 14). Allocating privacy budgets \(\varepsilon_{terminal} = \varepsilon/2\) and \(\delta_{terminal} = \delta/2\), and setting the terminal multiplicative error parameter to \(\gamma_{oracle} = \gamma/2\), the oracle guarantees: \[\label{eq:terminal95error} \left\vert w_{R_T}(C) - w_{\widehat{R}_T}(C) \right\vert \le \frac{\gamma}{2} w_{R_T}(C) + \widetilde{O} \left( \frac{n}{\varepsilon/2} + \left( \frac{n^2 M_T}{(\varepsilon/2)^2 (\gamma/2)} \right)^{1/3} \right).\tag{36}\] Finally, the additive bias simplifies to \(\alpha_T = \widetilde{O} ({ {n}/{\varepsilon} + \left( {n^2 M_T}/{(\varepsilon^2 \gamma)} \right)^{1/3} })\).

Combining the internal absorption 35 with the terminal deviation 36 , and exploiting the fact that \(w_{R_T}(C) \le w_G(C)\) since \(R_T\) is a subgraph of \(G\), we bound the global additive error for any cut \(C\): \[\begin{align} \left\vert w_G(C) - w_{\widetilde{G}}(C) \right\vert &\le \frac{\gamma}{2} w_G(C) + \left( \frac{\gamma}{2} w_{R_T}(C) + \alpha_T \right) \\ &\le \gamma w_G(C) + \widetilde{O} \left( \frac{n}{\varepsilon} + \left(\frac{n^2 M_T}{\varepsilon^2 \gamma}\right)^{1/3} \right), \end{align}\] which concludes the utility proof in Theorem 21.

The overall differential privacy holds under adaptive and parallel composition. The total privacy budget \(\varepsilon\) is partitioned into four allocations: \(\varepsilon/2\) dedicated to the terminal \(\mathsf{CutOracle}\) algorithm, and the remaining \(\varepsilon/2\) distributed evenly across the \(T\) rounds, allocating \(4\varepsilon_{round} = 4\varepsilon/(8T)\) per round. Within any round \(t\), by Lemma 28, the gadget construction strictly limits \(\ell_1\)-sensitivity to \(O(1)\), consuming \(\varepsilon_{round}\) under the Laplace mechanism. The recursion steps in Algorithm 9 isolates original edges to sub-problems of depth bounded by \(n^{o(1)}\). By applying basic composition over this \(n^{o(1)}\) depth, we allocate a local privacy budget of \(\varepsilon_{step} = \varepsilon_{round}/n^{o(1)}\) to each decomposition step, thereby collectively consuming \(\varepsilon_{round}\) globally across the depth under basic composition. The subsequent internal spectral releases operate on the mutually disjoint vertex subsets \(U \in \+P_t\); thus, via parallel composition, they collectively consume only \(\varepsilon_{round}\) globally across the round. The allocation for budget \(\delta\) over each round is identical. By basic composition over \(T\) rounds and the final step with \(\mathsf{CutOracle}\), the algorithm preserves \((\varepsilon,\delta)\)-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 \(n^{1+o(1)}\) internal components. Consequently, there are at most \(n^{1+o(1)} \le n^2\) local invocations of the hash mappings, spectral oracles, and cut-finders per round. By distributing the global failure probability \(\beta\) and allocating \(\beta_{round} = \beta / (8T n^2)\) to each individual sub-routine invocation across all \(T\) rounds (and allocating \(\beta/2\) to the final terminal release), the sum of all failure probabilities over the entire pipeline is bounded by \(T \cdot n^2 \cdot \beta_{round} + \beta/2 \le \beta/8 + \beta/2 < \beta\), completing the proof. ◻

Proof. For every \(x\ge 0\), it is easy to verify that \(b\sqrt{x} \le \frac{1}{4} x+b^2.\) Consequently, \(x_{t+1} \le \frac{1}{2}x_t+b^2+c.\) Iterating this inequality yields \[x_t \le 2^{-t}x_0 +(b^2+c)\sum_{j=0}^{t-1}2^{-j} \le 2^{-t}x_0+2(b^2+c),\] as claimed. ◻

Proof. Define \[\bar\gamma:=\min\{\gamma,1/8\}, \qquad \bar\delta:=\min\{\delta,1/4\}.\] It suffices to construct an \((\varepsilon,\bar\delta)\)-edge-DP mechanism with multiplicative error \(\bar\gamma\). Indeed, \(\bar\delta\le\delta\), \(\bar\gamma\le\gamma\), and \(\bar\gamma^{-7/6} = O(\gamma^{-7/6}).\) Assume \(n\ge 2\), since the claim is immediate for \(n=1\), and fix the number of recursive sparsification rounds in advance as \(T:=\left\lceil\log_2 n\right\rceil.\) We apply Theorem 21 with parameters \((\varepsilon,\bar\delta,\bar\gamma,T)\) and instantiate its spectral primitive using Theorem 12. For every \(t\), define \[d_t:=\max\left\{1,\frac{M_t}{n}\right\}.\] In particular, \(d_0=n\). Under privacy parameters \((\varepsilon/T,\bar\delta/T)\), Theorem 12 gives \[\begin{align} \Pi\left( n,d_t,\frac{\varepsilon}{T},\frac{\bar\delta}{T} \right) = \widetilde{O}_{\bar\delta}\left( \frac{d_t\sqrt T}{\sqrt{\varepsilon q}} + \frac{n^{1/8}d_t^{1/2}q^{1/8}T^{3/8}}{\varepsilon^{3/8}} + \frac{n^{1/4}q^{1/4}T^{3/4}}{\varepsilon^{3/4}} + \frac{T}{\varepsilon} \right). \end{align}\] The recurrence in Theorem 21 contains one additional multiplicative factor \(T\). Therefore, after dividing the residual edge bound by \(n\), we obtain \[d_{t+1} \le 1+ \widetilde{O}_{\bar\delta}\left( \frac{n^{o(1)}}{\bar\gamma} \right) \Bigg[ \frac{T^{3/2}d_t}{\sqrt{\varepsilon q}} + \frac{ T^{11/8}n^{1/8}d_t^{1/2}q^{1/8} }{\varepsilon^{3/8}} + \frac{ T^{7/4}n^{1/4}q^{1/4} }{\varepsilon^{3/4}} + \frac{T^2}{\varepsilon} \Bigg]. \label{eq:degree-recurrence-with-T}\tag{37}\] The additive \(1\) comes from the \(d_{t+1}=\max\{1,M_{t+1}/n\}\). Because \(T=O(\log n)\), all powers of \(T\), all polylogarithmic losses, and all \(n^{o(1)}\) losses in 37 can be bounded by a public factor \[\mathcal{L} = \widetilde{O}_{\bar\delta}\left(n^{o(1)}\right), \qquad \mathcal{L}\ge 1.\] We enlarge \(\mathcal{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 12. Thus 37 implies \[\label{eq:simplified-degree-recurrence} d_{t+1} \le 1+ B\left[ \frac{d_t}{\sqrt{\varepsilon q}} + \frac{n^{1/8}d_t^{1/2}q^{1/8}}{\varepsilon^{3/8}} + \frac{n^{1/4}q^{1/4}}{\varepsilon^{3/4}} + \frac{1}{\varepsilon} \right], \qquad B:=\frac{\mathcal{L}}{\bar\gamma}.\tag{38}\] We now choose the tunable parameter as: \[\label{eq:q-choice-cut-corollary} q := \left\lceil \frac{16B^2}{\varepsilon} \right\rceil.\tag{39}\] In particular, \(q = \widetilde{O}_{\bar\delta}\left( \frac{n^{o(1)}}{\varepsilon\bar\gamma^2} \right).\) hus, \(q\) is not asserted to be just polylogarithmic in \(1/\varepsilon\) and \(1/\bar\gamma\). Its polynomial dependence on these parameters is displayed explicitly. By 39 , we have \(\frac{B}{\sqrt{\varepsilon q}} \le \frac{1}{4}.\) Define \[b := \frac{ Bn^{1/8}q^{1/8} }{\varepsilon^{3/8}}\] and \[c := 1+ \frac{ Bn^{1/4}q^{1/4} }{\varepsilon^{3/4}} + \frac{B}{\varepsilon}.\] Then 38 becomes \[d_{t+1} \le \frac{1}{4}d_t+b\sqrt{d_t}+c.\] Applying Lemma 32 gives \[\label{eq:degree-after-t-rounds} d_t \le 2^{-t}d_0+2(b^2+c).\tag{40}\] It remains to bound \(b^2+c\). Since \(B\ge1\) and \(\varepsilon\le1\), the choice 39 gives \(q \le {17B^2}/{\varepsilon}.\) Consequently, \[\begin{align} b^2 = \frac{ B^2n^{1/4}q^{1/4} }{\varepsilon^{3/4}} = O\left( \frac{ n^{1/4}B^{5/2} }{\varepsilon} \right), \end{align}\] and similarly, \[\begin{align} \frac{ Bn^{1/4}q^{1/4} }{\varepsilon^{3/4}} = O\left( \frac{ n^{1/4}B^{3/2} }{\varepsilon} \right) \le O\left( \frac{ n^{1/4}B^{5/2} }{\varepsilon} \right). \end{align}\] Moreover, \[1+\frac{B}{\varepsilon} \le O\left( \frac{ n^{1/4}B^{5/2} }{\varepsilon} \right).\] Therefore, \[\label{eq:b-c-bound} b^2+c = O\left( \frac{ n^{1/4}B^{5/2} }{\varepsilon} \right).\tag{41}\] Because \(T=\lceil\log_2 n\rceil\), we have \(2^{-T}d_0\le1\). Combining 40 and 41 yields \[\begin{align} d_T = O\left( \frac{ n^{1/4}B^{5/2} }{\varepsilon} \right) \nonumber = O\left( \frac{ n^{1/4}\mathcal{L}^{5/2} }{ \varepsilon\bar\gamma^{5/2} } \right) \nonumber = \widetilde{O}_{\bar\delta}\left( \frac{ n^{1/4+o(1)} }{ \varepsilon\bar\gamma^{5/2} } \right). \label{eq:terminal-degree-bound} \end{align}\tag{42}\] Here we used \(\mathcal{L}^{5/2} =\widetilde{O}_{\bar\delta}(n^{o(1)})\). Since \(M_T\le nd_T\), it follows that \[\label{eq:terminal-edge-bound} M_T = \widetilde{O}_{\bar\delta}\left( \frac{ n^{5/4+o(1)} }{ \varepsilon\bar\gamma^{5/2} } \right).\tag{43}\] Finally, Theorem 21, instantiated with multiplicative parameter \(\bar\gamma\), gives additive error \[\widetilde{O}_{\bar\delta}\left( \frac{n}{\varepsilon} + \left( \frac{ n^2M_T }{ \varepsilon^2\bar\gamma } \right)^{1/3} \right).\] Substituting 43 , \[\begin{align} \left( \frac{ n^2M_T }{ \varepsilon^2\bar\gamma } \right)^{1/3} = \widetilde{O}_{\bar\delta}\left( \left( \frac{ n^{2} n^{5/4+o(1)} }{ \varepsilon^3 \bar\gamma^{5/2+1} } \right)^{1/3} \right) = \widetilde{O}_{\bar\delta}\left( \frac{ n^{13/12+o(1)} }{ \varepsilon\bar\gamma^{7/6} } \right). \end{align}\] Because \(n^{13/12}\ge n\), \(\bar\gamma\le1\), and \(\varepsilon\le1\), this term also absorbs the \(n/\varepsilon\) term. Thus the algorithm satisfies \[\left\vert w_G(C)-w_{\widetilde{G}}(C)\right\vert \le \bar\gamma w_G(C) + \widetilde{O}_{\bar\delta}\left( \frac{ n^{13/12+o(1)} }{ \varepsilon\bar\gamma^{7/6} } \right)\] simultaneously for all cuts \(C\).

Finally, \(\bar\gamma\le\gamma\), \(\bar\gamma^{-7/6}=O(\gamma^{-7/6})\), and \(\widetilde{O}_{\bar\delta}=\widetilde{O}_\delta\). This gives \[\left\vert w_G(C)-w_{\widetilde{G}}(C)\right\vert \le \gamma w_G(C) + \widetilde{O}_{\delta}\left( \frac{ n^{13/12+o(1)} }{ \varepsilon\gamma^{7/6} } \right),\] 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 \(n^{o(1)}\) factor, and both Theorem 21 and Theorem 12 provide polynomial-time implementations. ◻

Proof. If \(S=T\), the claimed inequality is trivial. Thus we assume \(S\neq T\). Let \(a_i=\mathbf{1}_S(i)-\mathbf{1}_T(i)\), for every \(i\in U\). By \(S\neq T\) we have \(a\neq 0\). Since \(|S|=|T|=k\), \[\sum_{i\in U}a_i=0.\]

Also \(a_i\in\{-1,0,1\}\), therefore \[\left\Vert a\right\Vert_2^2=\sum_{i\in U}a_i^2=|S\triangle T|.\]

The path \(B\) is common to both graphs, thus we have: \[L_{G_S}-L_{G_T} = \sum_{i\in U}a_iL_{\{0,i\}}.\]

Define a vector \(z\in\mathbb{R}^n\) by \[z_0=\frac{1}{\sqrt 2}, \qquad z_i=-\frac{a_i}{\sqrt 2\left\Vert a\right\Vert_2}\quad (i\in U), \qquad z_1=0.\]

Note \(z\) is a unit vector since \[\left\Vert z\right\Vert_2^2 = \frac{1}{2}+\frac{1}{2\left\Vert a\right\Vert_2^2}\sum_{i\in U}a_i^2 =1.\]

For an edge \(\{0,i\}\), \(z^\top L_{\{0,i\}}z=(z_0-z_i)^2\). Hence \[\begin{align} z^\top(L_{G_S}-L_{G_T})z &= \sum_{i\in U}a_i(z_0-z_i)^2 \\ &= \frac{1}{2}\sum_{i\in U}a_i \left(1+\frac{a_i}{\left\Vert a\right\Vert_2}\right)^2 \\ &= \frac{1}{2}\sum_{i\in U}a_i +\frac{1}{\left\Vert a\right\Vert_2}\sum_{i\in U}a_i^2 +\frac{1}{2\left\Vert a\right\Vert_2^2}\sum_{i\in U}a_i^3 . \end{align}\]

Because \(a_i\in\{-1,0,1\}\), we have \(a_i^3=a_i\). Since \(\sum_i a_i=0\), both the first and third terms vanish. Therefore \[z^\top(L_{G_S}-L_{G_T})z = \left\Vert a\right\Vert_2 = \sqrt{|S\triangle T|}.\]

Since \(z\) is a unit vector, \[\left\lVert L_{G_S}-L_{G_T}\right\rVert_2 \geq \left|z^\top(L_{G_S}-L_{G_T})z\right| = \sqrt{|S\triangle T|}.\] ◻

Proof. By the definition of \(\widehat S(Y)\), \[\left\lVert Y-L_{G_{\widehat S(Y)}}\right\rVert_2 \leq \left\lVert Y-L_{G_S}\right\rVert_2 \leq \alpha.\] Therefore, by the triangle inequality, \[\left\lVert L_{G_S}-L_{G_{\widehat S(Y)}}\right\rVert_2 \leq \left\lVert L_{G_S}-Y\right\rVert_2 + \left\lVert Y-L_{G_{\widehat S(Y)}}\right\rVert_2 \leq 2\alpha.\] Lemma 33 gives \[\sqrt{|S\triangle\widehat S(Y)|} \leq \left\lVert L_{G_S}-L_{G_{\widehat S(Y)}}\right\rVert_2 \leq 2\alpha.\] Squaring yields the claim. ◻

Proof. On the success event \(\left\lVert Y-L_{G_S}\right\rVert_2\leq \alpha\), Lemma 34 gives \(|S\triangle\widehat S|\leq 4\alpha^2.\) On the failure event, we use the trivial bound \(|S\triangle\widehat S|\leq 2k\), because both sets have size \(k\). Since the failure probability is at most \(\beta\) for every fixed \(S\), it is also at most \(\beta\) when \(S\) is uniform. Hence \[\mathbb{E}\bigl[|S\triangle\widehat S|\bigr] \leq 4\alpha^2+2\beta k.\] Finally, since \(|S|=|\widehat S|=k\), the number of false negatives equals the number of false positives: \[|S\setminus \widehat S|=|\widehat S\setminus S|=\frac{1}{2} |S\triangle\widehat S|.\] This yields the second claim. ◻

Proof. Choose an intermediate graph \(G'\) such that \(G\) is edge-neighboring to \(G'\) and \(G'\) is edge-neighboring to \(H\). Applying DP twice gives \[\begin{align} \mathbf{Pr}[\mathcal{A}(G)\in \mathcal{E}] &\leq e^{\varepsilon}\mathbf{Pr}[\mathcal{A}(G')\in \mathcal{E}]+\delta \\ &\leq e^{\varepsilon}\left(e^{\varepsilon}\mathbf{Pr}[\mathcal{A}(H)\in \mathcal{E}]+\delta\right)+\delta \\ &= e^{2\varepsilon}\mathbf{Pr}[\mathcal{A}(H)\in \mathcal{E}] +(1+e^{\varepsilon})\delta. \end{align}\] ◻

Proof. We give an explicit coupling. Sample \(T\sim\mathcal{D}_i^0\) uniformly, then sample \(j\in T\) uniformly, and set \(S=T\setminus\{j\}\cup\{i\}.\) Then \(S\) is uniform over \(\mathcal{D}_i^1\).

Indeed, for any fixed \(S\) with \(i\in S\), it can arise by choosing \(T=S\setminus\{i\}\cup\{j\}\) for some \(j\in U\setminus S\), and there are \(N-k\) such choices. Since \({N-1\choose k} = \frac{N-k}{k}{N-1\choose k-1}\), each such \(S\) is produced with probability \(\frac{N-k}{{N-1\choose k}\, k} = \frac{1}{{N-1\choose k-1}}\). This concludes that \(S\) is uniform over \(\mathcal{D}_i^1\).

For every coupled pair \((S,T)\), the graphs \(G_S\) and \(G_T\) differ by exactly two private star edges: remove \(\{0,j\}\) and add \(\{0,i\}\). Lemma 35 therefore gives \[\mathbf{Pr}[\mathcal{A}(G_S)\in \mathcal{E}_i] \leq e^{2\varepsilon}\mathbf{Pr}[\mathcal{A}(G_T)\in \mathcal{E}_i] +(1+e^{\varepsilon})\delta.\] Averaging over the coupling proves the lemma. ◻

Proof. The expected number of false negatives is \[\begin{align} \mathbb{E}[|S\setminus\widehat S|] &= \sum_{i\in U}\mathbf{Pr}[i\in S\text{ and }i\notin\widehat S] \\ &= \sum_{i\in U}\mathbf{Pr}[i\in S]\mathbf{Pr}[i\notin\widehat S\mid i\in S] \\ &= \frac{k}{N}\sum_{i\in U}(1-p_i^1). \end{align}\] By Corollary 3, \[\mathbb{E}[|S\setminus\widehat S|] \leq 2\alpha^2+\beta k.\] Therefore \[\frac{k}{N}\sum_{i\in U}(1-p_i^1) \leq 2\alpha^2+\beta k,\] which rearranges to \[\frac{1}{N}\sum_{i\in U}p_i^1 \geq 1-\beta-\frac{2\alpha^2}{k}.\] Similarly, the expected number of false positives is \[\begin{align} \mathbb{E}[|\widehat S\setminus S|] &= \sum_{i\in U}\mathbf{Pr}[i\notin S\text{ and }i\in\widehat S] \\ &= \sum_{i\in U}\mathbf{Pr}[i\notin S]\mathbf{Pr}[i\in\widehat S\mid i\notin S] \\ &= \frac{N-k}{N}\sum_{i\in U}p_i^0. \end{align}\] Again using Corollary 3, \[\frac{N-k}{N}\sum_{i\in U}p_i^0 \leq 2\alpha^2+\beta k.\] which rearranges to \[\frac{1}{N}\sum_{i\in U}p_i^0 \leq \frac{\beta k+2\alpha^2}{N-k}.\] ◻

Proof. For each \(i\in U\), inequality 44 gives \[p_i^1\leq e^{2\varepsilon}p_i^0+(1+e^{\varepsilon})\delta.\] Averaging over \(i\in U\) yields \[\frac{1}{N}\sum_{i\in U}p_i^1 \leq e^{2\varepsilon}\frac{1}{N}\sum_{i\in U}p_i^0 +(1+e^{\varepsilon})\delta.\] Lemma 37 lower bounds the left-hand side and upper bounds the right-hand side, giving \[1-\beta-\frac{2\alpha^2}{k} \leq e^{2\varepsilon}\frac{\beta k+2\alpha^2}{N-k} +(1+e^{\varepsilon})\delta.\] This proves 45 . Consequently, if we assume: \[\label{eq:parameter-choice} e^{2\varepsilon}\frac{\beta k}{N-k}\leq \frac{1-\beta}{4} \qquad\text{and}\qquad \delta \leq \frac{1}{8(1+e^\varepsilon)}\leq \frac{1-\beta}{4(1+e^\varepsilon)},\tag{46}\] where \(\beta \leq 1/2\), then \[1-\beta-\frac{2\alpha^2}{k} \leq \frac{1-\beta}{4} + \frac{2e^{2\varepsilon}\alpha^2}{N-k} + \frac{1-\beta}{4}.\] Therefore, \[\label{eq:alpha-lower} \alpha^2 \geq \frac{1-\beta}{4\left(1/k+e^{2\varepsilon}/(N-k)\right)} =\Omega_{\varepsilon,\beta,k/N}(n).\tag{47}\]

Take \(k=\lfloor\rho N\rfloor\), where \(\rho>0\) is a sufficiently small constant depending only on \(\varepsilon\) and \(\beta\) so that the first inequality in 46 holds for all large \(n\). Substituting \(k = \lfloor\rho N\rfloor\), the term \(\left(1/k + e^{2\varepsilon}/(N-k)\right)\) becomes \(\Theta(1/N) = \Theta(1/n)\). The bound 47 then gives \(\alpha^2 = \Omega(n)\) Since \(m=n-1+k=\Theta(n)\), this completes the proof. ◻

Proof of Theorem 22. It is enough to show that for any constants \(\varepsilon>0\) and \(\beta<1/2\), there exists \(c=c(\varepsilon,\beta)>0\) such that, for all sufficiently large \(n\), no \((\varepsilon,\delta)\)-edge-DP algorithm with \(\delta = \frac{1}{8(1+e^\varepsilon)}\) can output \(Y\) with \[\mathbf{Pr}[\|Y - L_G\| \leq c\sqrt{n}] \geq 1-\beta.\] on every connected \(n\)-vertex graph \(G\). Choose \(k=\lfloor\rho(n-2)\rfloor\) for a sufficiently small constant \(\rho=\rho(\varepsilon,\beta)>0\), and apply Lemma 38. The hard graphs have \(m=n-1+k=\Theta(n)\) edges and are connected. The lemma gives \(\alpha\geq c'\sqrt n\) for some constant \(c'=c'(\varepsilon,\beta,\rho)>0\). Taking \(c<c'\) gives the contradiction. ◻