该论文研究的是「差分隐私图性质测试」这一此前几乎空白的交叉方向。图性质测试（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）的任意性质都是可私有测试的。作者强调，这些私有测试器的查询复杂度与其非私有对应版本相当，也就是说引入隐私保护几乎不带来额外的查询开销。论文适合差分隐私/密码学、亚线性算法与图算法方向的研究者，以及需要在图数据上做隐私保护统计分析的工程人员阅读。