我们研究了在持续发布和完全动态更新的挑战性环境下，分析图的差分隐私算法。此环境中，边缘会随时间插入和删除，算法需要在每个时间步更新解决方案。之前的研究已提出了许多仅能处理插入或删除的部分动态算法，并对完全动态环境的难度进行了研究。至今，唯一在完全动态环境下的算法是Fichtenberger、Henzinger和Ost（ESA 21）提出的边计数算法，以及Fichtenberger、Henzinger和Upadhyay（ICML 23）提出的所有图割值发布算法。
我们提供了多个其他基本图统计量（包括三角形计数、连通分量数量、最大匹配的大小和度直方图）的首个差分隐私和完全动态图算法，分析了它们的误差，并为该环境下的所有算法提供了强下界。我们研究了完全动态图算法的两种边差分隐私变体：事件级和项级。我们给出了多种基本图问题的事件级和项级完全动态算法的误差上下界。在项级隐私的情况下，之前并没有已知的完全动态算法。对于多个问题，我们的算法达到了下界。
博主点评： 本文提出的全动态图算法在保持差分隐私的同时，解决了多个基本图问题，填补了现有研究的空白，尤其是在项级隐私方面的突破，具有重要的理论和实际意义。