本文研究差分隐私（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 下更强、更贴合图结构的误差刻画，明确了隐私—效用权衡的理论极限。