该论文研究的是「差分隐私图性质测试」这一此前几乎空白的交叉方向。图性质测试（graph property testing）的基本问题是：给定一个规模极大的图，能否只做亚线性（sublinear）次数的查询，就判断它满足某个性质，还是与满足该性质「相距很远」。由于测试器通常只随机检查输入的很小一部分，直觉上它与差分隐私（DP）以及「子采样带来的隐私放大」天然契合，但长期以来把两者联系起来的形式化结果非常少。本文首次对稠密图模型（dense graph model）和有界度图模型（bounded-degree graph model）下的差分隐私图性质测试进行系统性研究，目标是设计出既高效又具备形式化隐私保证的测试器。 核心方法上，作者为若干在图算法中被广泛使用的采样过程建立了新的隐私放大定理，涵盖诱导子图采样（induced subgraph sampling）、随机游走（random walks）以及 k-圆盘采样（k-disc sampling）。这些定理定量刻画了「只观察随机采样得到的小部分结构」能够在多大程度上压低隐私泄露风险，从而可以把非私有测试器的采样查询流程直接转化成满足差分隐私的流程。 主要贡献有三点：其一，利用上述放大技术，在稠密图模型中构造出私有的「规范测试器」（canonical tester）；其二，在稠密图与有界度图模型中分别给出私有的二部性（bipartiteness）测试器与子图自由性（subgraph freeness）测试器；其三，借助新证明的 k-disc 采样隐私放大定理，证明超有限图（hyperfinite graphs）的任意性质都是可私有测试的。作者强调，这些私有测试器的查询复杂度与其非私有对应版本相当，也就是说引入隐私保护几乎不带来额外的查询开销。论文适合差分隐私/密码学、亚线性算法与图算法方向的研究者，以及需要在图数据上做隐私保护统计分析的工程人员阅读。

本文针对差分隐私随机梯度下降（DPSGD）中隐私核算不严谨的问题进行研究。DPSGD通过在梯度上添加噪声并裁剪梯度来保护隐私，但这会导致模型效用显著下降且收敛缓慢。先前的工作，特别是差分隐私选择性更新与释放（DPSUR）算法，通过选择性更新部分梯度实现了较好的模型效用，但其隐私核算忽略了选择性释放机制引入的采样概率变化，从而削弱了隐私保证的严谨性。为了克服这一局限，本文重新评估了选择性释放机制的隐私分析，并提出了一种新算法——基于裁剪梯度的差分隐私选择性释放（DPSR-CG）。该算法通过严格的、新推导的隐私分析，在多个数据集（MNIST、CIFAR-10、IMDB和FMNIST）上进行了大量实验，结果表明DPSR-CG在保持严格隐私保证的同时，实现了卓越的模型性能。本文的核心贡献是修正了隐私核算缺陷，并提供了更高效的隐私-效用平衡方案。适合对差分隐私、机器学习隐私保护感兴趣的研究人员和工程师阅读。