We describe the first algorithms that satisfy the standard notion of node-differential privacy in the continual release setting (i.e., without an assumed promise on input streams). Previous work addresses node-private continual release by assuming an unenforced promise on the maximum degree in a graph, but leaves open whether such a bound can be verified or enforced privately. Our algorithms are accurate on sparse graphs, for several fundamental graph problems: counting edges, triangles, other subgraphs, and connected components; and releasing degree histograms. Our unconditionally private algorithms generally have optimal error, up to polylogarithmic factors and lower-order terms. We provide general transformations that take a base algorithm for the continual release setting, which need only be private for streams satisfying a promised degree bound, and produce an algorithm that is unconditionally private yet mimics the base algorithm when the stream meets the degree bound (and adds only linear overhead to the time and space complexity of the base algorithm). To do so, we design new projection algorithms for graph streams, based on the batch-model techniques of Day et al. 2016 and Blocki et al. 2013, which modify the stream to limit its degree. Our main technical innovation is to show that the projections are stable -- meaning that similar input graphs have similar projections -- when the input stream satisfies a privately testable safety condition. Our transformation then follows a novel online variant of the Propose-Test-Release framework (Dwork and Lei, 2009), privately testing the safety condition before releasing output at each step.

翻译：我们提出了首个在持续发布设置下满足标准节点差分隐私定义的算法（即无需对输入流作任何先验承诺）。先前工作通过假设图中最大度存在未经验证的承诺来处理节点私密的持续发布，但未解决该界限能否被隐私地验证或强制执行的问题。我们的算法在稀疏图上对若干基础图问题具有高精度：包括计数边、三角形、其他子图及连通分量；以及发布度直方图。这些无条件隐私算法通常具有最优误差，仅相差多对数因子及低阶项。我们提供了一般性转换方法，将以持续发布设置为基础、仅需对满足承诺度界限的流保持隐私的算法，转换为无条件隐私的算法，且当输入流满足度界限时能模拟基础算法的行为（仅为基础算法的时间和空间复杂度增加线性开销）。为此，我们基于Day等人（2016）和Blocki等人（2013）的批处理模型技术，设计了新的图流投影算法，通过修改流数据以限制其度。我们的核心技术创新在于证明：当输入流满足可隐私测试的安全条件时，投影具有稳定性——即相似的输入图会产生相似的投影。我们的转换随后遵循Propose-Test-Release框架（Dwork和Lei，2009）的一种新颖在线变体，在每一步发布输出前隐私地测试安全条件。