技术摘要：差分隐私谱图聚类

问题陈述

本文解决了在遵守边差分隐私（edge DP）的前提下，对网络数据进行谱图聚类所面临的挑战。在此设定下，目标是将图 $G=(V, E)$ 的顶点划分为 $k$ 个互不相交的社区，使得任意单条边的包含或移除对输出的影响有限。作者重点关注隐私（由隐私预算 $\epsilon$ 量化）、准确性（由误分类错误率衡量）与效率（计算和空间复杂度）之间的基本权衡。

该工作特别针对社区数量 $k$ 可能未知，且底层图模型（如随机块模型）在密度和异质性方面存在变化的场景。论文将其提出的方法与两种为边 DP 调整的基准方法进行了对比：直接对邻接矩阵添加高斯噪声的Analyze Gauss机制，以及带有噪声的迭代特征向量估计的Noisy Power Method。

方法论

本文提出了一个统一的分析框架和三种不同的私有谱聚类机制：

1. 统一误差分析框架

作者开发了一个理论框架，用于界定任何允许加性噪声分解的私有谱机制的误分类错误率上限。该框架结合了：

• Davis–Kahan 扰动理论：基于谱隙（$\Delta_k$）和扰动幅度，界定真实特征子空间与扰动特征子空间之间的偏差。
• Procrustes 对齐：将特征子空间距离与嵌入之间的 Frobenius 误差联系起来。
• 分类 - 边界界：将嵌入误差与最终的 k-means 聚类误差联系起来，明确考虑了聚类中心分离度（$\Delta^\star$）和聚类内半径（$r^\star$）。

2. 矩阵洗牌机制（提出）

这是本文的核心贡献。该机制分两个阶段运行：

• 图扰动：使用**随机响应（RR）**对邻接矩阵 $A$ 进行扰动。每条边以概率 $\mu = 1/(e^{\epsilon_0} + 1)$ 被翻转。
• 矩阵洗牌：将扰动后的矩阵乘以随机置换矩阵 $P$（即 $P \tilde{A} P^\top$）。
• 隐私放大：作者证明，虽然 RR 单独提供的 $\epsilon$ 保证在图大小 $n$ 增长时仅为常数，但随机置换放大了隐私。有效的 $\epsilon$ 随着 $n \to \infty$ 趋于零，具体缩放比例为 $O(n^{-1/2})$。
• 间隙检测：提出了一种私有谱间隙检测算法，直接从私有化输出中估计 $k$。该过程涉及对洗牌后的矩阵进行中心化以消除全局密度效应，并将其投影到全 1 向量正交的空间中，随后识别最大的特征值间隙。

3. 基准机制

论文调整并分析了两种现有方法以进行比较：

• Analyze Gauss：直接向邻接矩阵元素添加对称高斯噪声。
• Noisy Power Method：在幂迭代步骤的每一步添加校准的高斯噪声，以迭代计算特征向量。

主要贡献

1. 矩阵洗牌机制：作者引入了一种结合随机边翻转与均匀随机置换的新机制。他们证明该机制实现了 $(\epsilon, \delta)$-边 DP，且随着节点数量增加，有效隐私泄露趋于消失，这是对标准 RR 的重大改进。
2. 统一误差分析：建立了一个全面的理论框架，得出了所有三种机制的明确误分类率。该框架明确刻画了误差如何随隐私预算、特征值间隙、社区数量和图大小进行缩放。
3. 理论缩放改进：分析表明，矩阵洗牌机制实现了 $\tilde{O}(1/n)$ 的误差率缩放。相比之下，在边 DP 设定下，Analyze Gauss 和 Noisy Power Method 基准方法相对于 $n$ 的缩放比例为 $\tilde{O}(1)$。
4. 私有谱间隙检测：提出了一种从私有化数据中估计社区数量的过程，继承了洗牌机制的隐私放大优势。
5. 实验验证：在合成随机块模型（SBMs）和真实世界数据集（Facebook 社交圈和 Cora 引用网络）上验证了理论发现。

结果

理论发现

• 错误率：矩阵洗牌机制实现了渐近错误率 $\tilde{O}\left(\frac{1}{n(e^\epsilon - 1)^2} \cdot \frac{k}{\Delta_k^2}\right)$。这明显优于基准方法，后者分别缩放为 $\tilde{O}\left(\frac{k^2}{\epsilon^2 \Delta_k} \cdot \frac{k}{\Delta_k^2}\right)$（Noisy Power）和 $\tilde{O}\left(\frac{1}{\epsilon^2} \cdot \frac{k}{\Delta_k^2}\right)$（Analyze Gauss）。
• 复杂度权衡：
  • 空间：由于扰动后的邻接矩阵的稠密性质，洗牌机制和 Analyze Gauss 都需要 $O(n^2)$ 的存储空间。Noisy Power Method 在空间上更高效（稀疏图为 $O(n)$）。
  • 时间：洗牌机制涉及稠密化，导致计算成本高于对稀疏友好的 Noisy Power Method，尽管它在误差缩放方面提供了更优越的准确性。

实验发现

• 合成数据（SBM）：在具有不同社区数量（$k=3$ 和 $k=10$）的 SBM 上，矩阵洗牌机制始终表现出最强的隐私 - 效用权衡，即使在 $\epsilon$ 降低时也能保持低错误率。Noisy Power Method 和 Analyze Gauss 在具有挑战性的设置（例如更高的 $k$）中性能下降更为显著。
• 真实世界数据：在 Facebook 社交圈和 Cora 引用网络上的实验证实了理论预测。矩阵洗牌机制在不同的聚类数量和图结构下均优于基准方法。
• 间隙检测：只要总体特征值间隙与噪声充分分离，所提出的算法就能以高概率在合成实验中成功恢复真实的社区数量。

意义与主张

本文声称提供了对谱聚类中隐私、准确性和效率之间基本权衡的首次系统研究，且未对底层图模型施加限制性假设。

• 隐私放大：该工作强调，洗牌可以根本性地改变图聚类中的隐私 - 准确性格局，允许随着网络规模增长而实现消失的错误率，这是直接应用于邻接矩阵的标准边 DP 机制所不具备的特性。
• 统一框架：通过推导基于分类边界和特征值间隙的明确误差界，本文为比较差分隐私谱方法提供了严格的工具。
• 实际效用：结果表明，对于存储允许的稠密或中等规模图，矩阵洗牌是现有私有 PCA 和幂迭代方法进行社区检测的更优替代方案。

作者承认了局限性，指出其保证特定于边 DP（而非更强的节点 DP），洗牌机制会使矩阵稠密化（限制了其在非常大的稀疏图中的可扩展性），且误差界依赖于特征值间隙等特定于图的量。未来的工作建议将这些结果扩展到属性图和节点 DP 设定。