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

本文研究度量差分隐私（metric differential privacy, mDP）机制的可扩展构造问题。mDP 适合定义在结构化的秘密域上（例如路网、地理网格、坐标空间），因为它的隐私保证随秘密值之间的度量距离变化，比标准差分隐私更贴合位置类数据。但现实中的目标域往往规模庞大且粒度极细，直接在该域上构造同时兼顾隐私与效用的机制，计算开销通常高到不可接受。作者因此系统研究『扩展式』mDP 设计：先在规模有限的种子记录集合上指定一个机制，再把它扩展到更大的目标域，而不是一次性针对全域求解。作者指出，据其所知，这是首个把『扩展』作为 mDP 通用设计范式（而非某个具体方法的附带构造技巧）加以形式化的工作。为此，论文提出一个基于图的扩展框架：把种子记录与目标域元素组织成图结构，并给出保证正确性的三项条件——局部 mDP 约束（种子层面各自满足 ε-mDP）、重叠一致性（不同种子扩展在重叠区域给出的结果必须一致，从而全局机制良定义）、以及后继层 mDP 保持（扩展过程中隐私参数不被稀释）。论文证明，在上述条件成立时，由种子机制诱导出的全局机制是良定义的，并在目标域上满足 ε-mDP。作者进一步用面向多分辨率网格的树形扩展算法实例化该框架，其中多维扩展通过一维插值加逐维组合来实现，从而把高维构造成本降到可接受范围。在道路网数据集上的实验显示，该方法在保持精确 mDP 保证的同时取得了较强的效用—可扩展性折衷。论文定位为方法论与理论贡献，适合隐私保护数据发布、位置隐私、地理不可区分性机制设计方向的研究者与工程实现者阅读。

本文研究差分隐私（DP）约束下的基础图优化问题，并给出基于“重构攻击”思路的新型下界证明。作者考虑图 G=(V,E,w⃗)，其中顶点集 V 与边集 E 是公开的，只有边权函数 w:E→ℝ 需要满足 ℓ1 邻接关系下的差分隐私。研究对象包括两个经典问题：发布最小生成树（MST）与发布最小权完美匹配。作者证明，在 n 个顶点、m>2n 条边的最坏情形图上，任何 DP 算法的误差下界为 Ω(n·log(m/n)/ε)。该下界与已知的纯 DP 算法上界相匹配，因此是紧的；并且即使在近似 (ε,δ)-DP 下，只要 δ ≤ (n/m)^{Ω(1)}，下界依然成立。这一结果改进了 Sealfon（PODS'16）给出的 Ω(n/ε) 下界，量级上增加了 log(m/n) 这个因子。 论文的一个重要对照结论是：在 ℓ1 邻接关系下，允许近似 DP 并不能降低 MST 的误差，这与 Pagh 等人（PODS'25）在 ℓ∞ 邻接关系下证明的“近似 DP 可大幅改善误差”形成鲜明反差，说明邻接关系（敏感度定义）的选择对可实现的效用具有决定性影响。作者并未局限于最坏情形图，而是进一步给出了具有扩展性质（expander）的一大类稀疏图上的下界；特别地，对任意最小割至少为 Ω(log n) 的图，证明了 MST 的 Ω(n/ε) 下界。 最后，作者把方法拓展到隐私层次聚类问题：在 Dasgupta 代价函数（STOC'16）框架下，给出首个由“平衡割的最小权重”参数化的近似 DP 下界，将 Deng 等人（ICLR'25）的结果推广到一般图，并推广到近似 DP 设置。核心方法属于重构式下界证明技术，通过论证若算法精度过高则攻击者可重构出受保护的权重信息，从而反推出误差不可避免。总体贡献是给出了图优化在 DP 下更强、更贴合图结构的误差刻画，明确了隐私—效用权衡的理论极限。

本文提出了一个高度可扩展的安全计算图算法框架，用于保护图拓扑及节点/边关联数据的隐私。在该框架中，图的所有节点和边都以秘密共享形式分布在多个服务器上，服务器间通过安全计算协议协同计算，而不泄露任何图结构或节点属性信息。虽然该方案具有一定的普适性，但文中重点展示了三服务器诚实多数设置下的实现，同时支持半诚实安全和完全安全（可抵御恶意攻击）两种级别。主要技术贡献在于采用安全洗牌（secure shuffle）替代传统方法中效率较低的安全排序（secure sort）协议，显著减少了通信和计算开销。针对恶意行为，通过引入高效的洗牌验证机制，并利用完全安全的电路计算协议，实现了全安全性。为了验证该技术的适用性，作者实现了两个经典图算法：广度优先搜索（BFS）和最大独立集（MIS），其中 BFS 可应用于私有接触图上的接触者追踪。实验在包含数百万元素的图上进行，两种算法在两种安全级别下均能在数秒内完成，展示了超大规模图数据安全分析的实用性。这项研究为隐私保护图分析提供了可扩展的解决方案，适用于社交网络、传染病防控等敏感数据场景。