提出首个兼顾高精度与低空间的私有图算法，实现隐私增强与数据压缩双赢。
Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
- 通过精细化子采样实现隐私放大与稀疏化同步
- 添加边触发早期采样，消除前人算法中的额外对数因子
- 适合关注隐私保护与空间效率的图分析研究者
我们研究了边差分隐私（DP）图算法在亚线性空间持续发布模型下的应用，聚焦于插入只读场景下的最密子图问题（DSG）。本文首次提出一种持续发布型的最密子图算法，其加性误差达到最优静态私有算法水平，空间复杂度接近最优非私有流式算法，仅相差常数因子。核心思想是精炼使用子采样，同时实现隐私放大和图稀疏化，这一关联此前未在图差分隐私中形式化。通过一个简单的黑箱归约至静态设置，我们获得了纯差分隐私和近似差分隐私算法，均具有 $O(\log n)$ 的加性误差和 $O(n\log n)$ 的空间复杂度，显著优于此前最优成果。过程中引入图密度增强机制，在图差分隐私框架下添加边以提前触发子采样，消除了先前工作 [ELMZ25] 引入的额外对数误差与空间开销。我们认为这一简单思路本身可能具有独立价值。
原文摘要 · Abstract (English)
We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms, with a focus on the densest subgraph problem (DSG) in the insertion-only setting. Our main result is the first continual release DSG algorithm that matches the additive error of the best static DP algorithms and the space complexity of the best non-private streaming algorithms, up to constants. The key idea is a refined use of subsampling that simultaneously achieves privacy amplification and sparsification, a connection not previously formalized in graph DP. Via a simple black-box reduction to the static setting, we obtain both pure and approximate-DP algorithms with $O(\log n)$ additive error and $O(n\log n)$ space, improving both accuracy and space complexity over the previous state of the art. Along the way, we introduce graph densification in the graph DP setting, adding edges to trigger earlier subsampling, which removes the extra logarithmic factors in error and space incurred by prior work [ELMZ25]. We believe this simple idea may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。