技术摘要：通过谱放大器实现图谱与割的隐私近似

1. 问题陈述

本文研究了在**边级差分隐私（edge-level differential privacy, DP）**下，发布一个能够近似输入无权图 $G$ 中所有割（cut）大小的合成图的问题。目标是输出一个加权合成图 $\tilde{G}$，使得对于每一个割 $S \subseteq V$，其割大小 $w_{\tilde{G}}(S)$ 满足混合误差保证：
$$|w_G(S) - w_{\tilde{G}}(S)| \le \gamma w_G(S) + \alpha$$
其中 $\gamma$ 是一个小的乘性松弛项，$\alpha$ 是加性误差。

本文强调了该设定下的一个基本矛盾：

• 纯加性误差 ($\gamma=0$)： 对于稠密图，最优最坏情况误差为 $\tilde{\Theta}(n^{3/2})$。
• 混合误差 ($\gamma > 0$)： 虽然存在具有近线性误差 $\tilde{O}(n)$ 的信息论机制，但它们需要指数级时间。在本文之前，已知的最佳多项式时间算法（Aamand 等人，ICML 2025）实现的加性误差为 $\tilde{O}(n^{5/4+o(1)})$。

核心挑战在于如何缩小指数级时间信息论界限与多项式时间算法之间的差距，特别是通过改进多项式时间算法中的加性误差项。

2. 方法论与技术方法

作者提出了一种多项式时间 $(\varepsilon, \delta)$-DP 算法，实现了 $\tilde{O}(n^{13/12+o(1)})$ 的加性误差。该解决方案构建在一个结合了三个不同层级的模块化框架之上：

A. 通过谱放大器实现的隐私谱原语

核心技术创新是一类基于**基于幂次的谱放大器（power-based spectral amplifiers）**的新型隐私谱原语。算法不是直接发布邻接矩阵 $A$（这会引入 $\tilde{O}(\sqrt{n})$ 的噪声），而是发布矩阵的噪声幂次 $A^q$。

• 平方放大器 ($q=2$)： 通过发布 $A^2$（用于计算公共邻居），信号（特征值）被二次放大 ($\lambda \to \lambda^2$)，而 $A^2$ 在有界度图中的敏感度仅为 $O(\sqrt{d})$。这使得识别大特征值时，噪声仅为 $\tilde{O}((nd)^{1/4})$，优于针对稀疏图的标准 $\tilde{O}(\sqrt{n})$ 基准。
• 引导式四次幂放大器 ($q=4$)： 为了进一步降低误差，作者引入了一个称为**迭代三次评分覆盖（Iterated Cubic-Score Cover）**的预处理步骤。该步骤通过隐私方式识别并移除导致高“两步游走能量”（局部拥塞）的边。剩余的残差图对于 $A^4$ 查询具有较低的敏感度。对该残差图应用 $A^4$ 放大器，可得到其谱误差界限取决于最大度 $d$，并包含一个可调的收缩项 $d/\sqrt{q}$。

B. 基于需求感知扩展图分解的递归稀疏化

算法采用递归扩展图分解框架。

• 稳定端口小部件（Stable Port Gadget）： 为了处理即使在图很稀疏的情况下最大度 $d$ 可能很大的情况（例如星形图），算法将图转换为一个“端口代理”图。该小部件将高度数顶点平铺为多个“端口”，确保代理图的最大度随平均度 ($M/n$) 而缩放，而非随最大度缩放。
• 递归分解： 利用度敏感的谱原语，算法将图递归地分解为扩展图。在每个扩展图内部，谱误差足够小，可以被视为乘性误差吸收。残差图（扩展图之间的边）会变得越来越稀疏。
• 递推关系： 原语的谱误差驱动残差边数 $M_t$ 的递推。新的谱原语允许残差在经过 $T = O(\log n)$ 轮后，缩减至 $M_T = \tilde{O}(n^{5/4+o(1)})$ 条边。

C. 边敏感终端割预言机（Edge-Sensitive Terminal Cut Oracle）

一旦残差图足够稀疏（$M$ 条边），算法停止递归并应用终端割预言机。

• 机制： 该预言机使用带有正则化半正定规划（SDP）松弛的隐私镜像下降算法。
• 关键洞察： 通过允许乘性松弛 $\gamma$，算法可以吸收梯度更新的方差。这使得可以使用更大的学习率，从而实现更快的势函数衰减。
• 结果： 终端预言机发布的稀疏残差的割函数，其加性误差为 $\tilde{O}(n + (n^2 M)^{1/3})$。将 $M = \tilde{O}(n^{5/4})$ 代入，得到最终的 $\tilde{O}(n^{13/12})$ 界限。

3. 主要贡献与结果

主定理（隐私割近似）

本文提出了一个多项式时间算法，对于任何 $n$ 个顶点的无权图，该算法能以高概率输出一个合成图 $\tilde{G}$，使得对于所有割 $S$：
$$|w_G(S) - w_{\tilde{G}}(S)| \le \gamma w_G(S) + \tilde{O}_{\varepsilon, \delta, \gamma}\left( \frac{n^{13/12+o(1)}}{\varepsilon \gamma^{7/6}} \right)$$
这改进了 Aamand 等人 (2025) 提出的 $\tilde{O}(n^{5/4+o(1)})$ 的先前最佳多项式时间最坏情况界限。

隐私谱原语

作者开发了首个针对有界度图的隐私谱估计器，在高度数情形下超越了标准的 $\min\{2d, \tilde{O}(\sqrt{n}/\varepsilon)\}$ 基准。

• 平方放大器： 实现误差 $\tilde{O}((nd)^{1/4}/\sqrt{\varepsilon})$。
• 四次幂原语： 实现误差 $\tilde{O}(d/\sqrt{q} + n^{1/8}d^{1/2}q^{1/8} + n^{1/4}q^{1/4})$，其中 $q$ 是可调参数。这对于残差图的递归收缩至关重要。

下界

本文证明了拉普拉斯释放的信息论下界。即使对于平均度为 $O(1)$ 的图，任何 $(\varepsilon, \delta)$-DP 算法也必须承受 $\Omega(\sqrt{n})$ 的最坏情况谱误差。这表明 $\tilde{O}(\sqrt{n})$ 壁垒是内在的，不能仅靠平均度敏感性来突破；本文的改进在于利用了递归算法中残差度的不断降低。

4. 重要性与主张

本文声称解决了隐私图分析中的一个长期瓶颈，即改进了图割的多项式时间近似。

• 打破壁垒： 该工作将状态最优的加性误差从 $\tilde{O}(n^{1.25})$ 提升到了 $\tilde{O}(n^{1.083})$ ($13/12$)，缩小了与信息论目标 $\tilde{O}(n)$ 之间的差距。
• 模块化框架： 作者强调其方法是模块化的。度敏感谱释放、稳定端口小部件以及边敏感终端预言机的结合，为未来的改进提供了一个模板。
• 内在极限： 通过证明即使在稀疏图中谱释放也存在 $\Omega(\sqrt{n})$ 的下界，本文阐明了其算法之所以成功，在于递归减少了图的有效度，而非对所有图都实现了通用的谱估计改进。

本文并不声称解决了所有情形下的问题（例如，纯加性误差仍为 $\tilde{O}(n^{3/2})$），也没有提出实验验证，而是专注于理论算法设计和复杂度界限。