Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy¶

会议: NeurIPS 2026
arXiv: 2601.01710
OpenReview: https://openreview.net/forum?id=ocQWtpw7Ib
代码: https://github.com/Crightub/private-below-threshold-triangle-counting
领域: AI安全
关键词: 本地差分隐私, 加权图, 三角形计数, 平滑敏感度, 最小费用最大流

一句话总结¶

本文提出首个在本地权重差分隐私（LWDP）下统计加权图低于阈值三角形数量的两阶段算法框架，通过最小费用最大流/贪心分配最小化节点间计数协方差，并提出 $O(d^2 \log^2 d)$ 时间的高效平滑敏感度计算算法，将计数相对误差降低达两个数量级。

研究背景与动机¶

在城市道路交通规划、移动通信网络以及生物代谢网络分析等诸多实际图数据应用中，网络物理拓扑往往是公开信息（例如城市路网骨架、通信基站分布），而真正的敏感私有信息则编码在边权重上（如道路实时车流量、两基站间的用户通话频次）。低于指定阈值的三角形计数及其衍生指标（如加权聚类系数）是挖掘网络拥堵区域、识别关键密集子图以及检测负环的基础算法构件。然而，若要协作统计此类全局统计量，中心化差分隐私严重依赖完全受信任的中央服务器，存在单点泄露风险；而现有的本地差分隐私（LDP）图算法大多集中在无权图的边本地差分隐私（LEDP）设置，或者将图拓扑和边权重均作为敏感信息盲目隐藏，不仅引入了巨大的不必要扰动误差，也破坏了实际场景中公开拓扑天然具备的先验优势。

在本地权重差分隐私（LWDP）模型下，每个节点仅持有自身关联边的真实权重向量，中央服务器公开图拓扑结构但无法直接获取边权重。由于每个三角形由三个节点和三条边构成，若允许多个节点重叠统计共用边，不同节点基于同一带噪边权重做出的估计必然引入强烈的跨节点协方差，这种协方差结构在误差分析中对应于两三角形共享一条非关联边的 $C'_4$ 子图模式，成为总方差平方误差的主导项。此外，为了校准局部统计量发布时的加噪尺度，传统全局敏感度受制于最大节点度数 $d_{\max}$，往往导致过度加噪，而数据相关的平滑敏感度计算此前缺乏高效的多项式时间算法，计算瓶颈高达 $O(d^2)$ 每次尝试，在实际高密度或大度数网络中极难落地。

面对上述核心矛盾，本文打破了无权图 LDP 盲态假设，充分利用公开图拓扑结构将统计协方差问题转化为图上的离线负载均衡与最小费用流分配，并基于排序数组设计了快速前缀距离更新结构。核心 idea：在本地权重差分隐私下设计“带噪权重发布-本地精细估计”两阶段框架，利用公开图拓扑通过最小费用流或贪心任务分配将共享带噪边的协方差极小化，并结合平滑敏感度快速搜索与无偏直方图估计器，实现兼具高精度与可扩展性的私有子图统计。

方法详解¶

整体框架¶

本文算法采用两阶段交互式通信范式（Two-Step Algorithm）。在第一阶段，每个节点 $v$ 对其局部关联边权重向量添加离散拉普拉斯（Geometric）噪声并发布，服务端汇总并依据边索引打破对称性构建统一的全局带噪图 $G'$；同时，服务端基于公开的无权拓扑 $(V, E)$ 求解三角形到节点的责任分配函数 $\rho: \Delta \to V$。在第二阶段，服务端将分配方案及相关非关联边的带噪权重下发至对应责任节点；各节点基于私有真实权重与远端带噪权重计算低于阈值的三角形局部计数值，并通过平滑敏感度机制注入噪声后回传，最终服务端线性累加各节点报告输出全局无偏/有偏估计量 $\tilde{k}$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["私有加权图<br/>公开拓扑 (V,E) + 节点私有权重"] --> B["第一阶段：离散拉普拉斯带噪发布<br/>满足 ε1-LWDP 导出全局带噪图 G'"]
    B --> C["最小费用流 / 贪心任务分配<br/>优化分配 ρ: Δ → V 最小化 C'4 协方差"]
    C --> D["第二阶段：本地三角形低于阈值估计<br/>可选有偏指示器 BT' 或无偏估计器 UT'"]
    D --> E["高效平滑敏感度快速计算<br/>基于排序前缀距离在 O(d² log² d) 时间求解"]
    E --> F["敏感度加噪与服务端全局聚合<br/>注入拉普拉斯/柯西扰动，输出估计值 k~"]

关键设计¶

1. 协方差极小化的三角形任务分配：利用公开拓扑消除主导误差 在两阶段算法中，当两个三角形 $T = \{v, x, y\}$ 与 $T' = \{u, x, y\}$ 共享同一条非关联边 $\{x, y\}$ 时，负责两三角形的节点 $v$ 和 $u$ 均使用了同一份带噪权重 $w'_{xy}$，产生强烈的误差协方差，其出现频次记为 $\#C'_4$。定义边 $e=\{u, v\}$ 的负载 $l(e)$ 为所有满足 $\rho(T) \notin \{u, v\}$ 且 $e \in T$ 的三角形数量，总协方差代价满足 $c(\rho) = \#C'_4 = \sum_{e \in E} \binom{l(e)}{2} = \frac{1}{2}\sum_{e} l(e)^2 - \frac{|\Delta|}{2}$。为最小化这一方差主导项，本文将问题归约为限制性离线负载均衡，构建从源点到三角形节点、再到边节点、最后到汇点的流网络，通过连续最短路（Successive Shortest Path）算法在 $O(|\Delta|^2 + |\Delta|(|\Delta|+m)\log(|\Delta|+m))$ 时间内求得精确最优解。针对稠密图，本文进一步设计了在线贪心近似算法：按任意顺序遍历三角形，依次分配给当前负载 $l(e)$ 最小的对应对边，证明其在平方 $\ell_2$ 范数上达到 $3+2\sqrt{2}$ 的严格近似比。在平面图上，最优分配可直接证明达到 $\#C'_{4, \mathrm{OPT}} = 0$（即完全消除协方差），使有偏估计器误差与平面图理论下界 $\Omega(n^2/\varepsilon^2)$ 渐近匹配。

2. 无偏与有偏估计器构造：在偏差与方差之间的理论权衡 对于节点 $v$ 负责的三角形 $T=\{v, u, x\} \in \Delta_v$，判定其总权重是否低于阈值 $\lambda$ 面临远端边 $\{u, x\}$ 带噪的偏差问题。有偏估计器直接采用硬阈值指示函数 $B'_T = \mathbf{1}\{w_{vu} + w_{vx} + w'_{ux} < \lambda\}$，其平方误差为 $O(\frac{d_{\max} m}{\varepsilon_2^2} + \frac{|\Delta|^2}{\varepsilon_1^2} + \frac{\#C'_4}{\varepsilon_1})$，其偏差项随三角形总数 $|\Delta|$ 呈平方级增加，但在小隐私预算 $\varepsilon$ 下较为稳健。为在三角形密集的网络中彻底消除该偏差，本文引入针对离散拉普拉斯扰动的无偏逆核函数 $h(m)$： $$ h(m) = \begin{cases} 0, & m > \lambda \ -\frac{p}{(1-p)^2}, & m = \lambda \ 1 + \frac{p}{(1-p)^2}, & m = \lambda - 1 \ 1, & m < \lambda - 1 \end{cases} \quad \text{其中 } p = e^{-\varepsilon_1} $$ 构造无偏估计器 $U'_T = h(w_{vu} + w_{vx} + w'_{ux})$。此时平方误差界转化为 $O(\frac{d_{\max} m}{\varepsilon_1^4 \varepsilon_2^2} + \frac{|\Delta|}{\varepsilon_1^3} + \frac{\#C'_4}{\varepsilon_1^3})$。误差对三角形总数 $|\Delta|$ 从平方依赖降为线性依赖，使得在包含海量三角形的大规模真实图上，无偏估计器的相对误差大幅下降。

3. 基于双目标排序数据结构的高效平滑敏感度计算 为避免全局敏感度 $GS(f'_v) = O(d_v)$ 导致的过量噪声注入，第二阶段采用 $\beta$-平滑敏感度 $S^*_{f'_v, \beta}(w) = \max_{z \in \mathbb{Z}^d} (LS_f(w+z) e^{-\beta \|z\|_1})$。针对有偏与无偏估计器，局部敏感度的最大化等价于选择权重大步长平移向量 $z$，使得尽可能多的局部边权重偏置聚集到特定跃迁目标点 $t$。朴素搜索需要枚举所有目标和移动元素数量，单节点耗时达 $O(d^3)$。本文证明最优目标点 $t$ 必然落在部分权重候选集合 $\mathcal{T} = \{w_j + w'_{u(i)u(j)} + \delta : \delta \in \{-1, 0, 1\}\} \cup \{\lambda - 1 - w_e\}$ 内；进而设计单/双目标排序前缀和数据结构，维护左右分区的排序数组，通过二分搜索判定不等式 $\frac{k}{k+1} < e^{-\beta d(k+1)}$，从而在 $O(\log^2 d)$ 时间完成单目标下最优迁移数检索，并将目标沿有序数组推进的均摊更新代价控制在 $O(\log d)$。最终将度数为 $d$ 节点的平滑敏感度计算复杂度从 $O(d^3)$ 锐减至 $O(d^2 \log^2 d)$，使得在千万级边图上的实际单机运行时间缩短至 5 分钟以内。

损失函数 / 训练策略¶

作为纯组合图算法与差分隐私机制，本算法不涉及反向传播训练与可学习参数。隐私预算总体分配为 $\varepsilon = \varepsilon_1 + \varepsilon_2$，标准实验设置平分预算 $\varepsilon_1 = \varepsilon_2 = \varepsilon / 2$。第二阶段平滑敏感度机制采用参数 $\Gamma = 4$ 的重尾柯西类扰动分布（保证方差 $\mathrm{Var}[Z] = 1$），噪声乘子为 $\frac{2(\Gamma-1)^{(\Gamma-1)/\Gamma}}{\varepsilon_2} = \frac{2 \cdot 3^{3/4}}{\varepsilon_2} \approx \frac{4.559}{\varepsilon_2}$，确保满足严格的 $\varepsilon_2$-本地权重差分隐私，全流程根据组合定理严格满足 $(\varepsilon_1 + \varepsilon_2)$-LWDP。

实验关键数据¶

主实验¶

实验在意大利米兰电信网络真实加权图（ML-Tele-278，包含 278 个基站节点、38,503 条边、3,542,276 个三角形，阈值 $\lambda = 4$）上系统评估，对比各算法在不同总隐私预算 $\varepsilon$ 下的平均相对误差 $|r - p| / r$（重复 10 次取均值）：

数据集 / 设置	评估指标	本文 (Smooth-Unbiased)	Global-Unbiased	Baseline (全加噪重建)	相比 Baseline 提升
ML-Tele-278 ($\varepsilon=0.5$)	相对误差 (Rel. Error)	0.082	0.450	2.850	误差降低 97.1% (约 35×)
ML-Tele-278 ($\varepsilon=1.0$)	相对误差 (Rel. Error)	0.038	0.185	1.120	误差降低 96.6% (约 29×)
ML-Tele-278 ($\varepsilon=2.0$)	相对误差 (Rel. Error)	0.015	0.081	0.380	误差降低 96.1% (约 25×)
ML-Tele-278 ($\varepsilon=4.0$)	相对误差 (Rel. Error)	0.007	0.025	0.012	误差降低 41.7% (约 1.7×)

消融实验¶

在 ML-Tele-278 数据集（固定 $\varepsilon=2.0, \lambda=4$）上对估计器类型（Biased vs. Unbiased）及敏感度机制（Global vs. Smooth）进行完整正交消融：

配置 (Config)	相对误差 (Rel. Error)	运行时间 (Runtime)	说明
Smooth-Unbiased (完整方案)	0.015	285s	无偏估计器结合平滑敏感度，相对误差最佳
Smooth-Biased (替换为有偏)	0.092	272s	误差增大约 6.1×，受三角形总数平方级偏差拖累
Global-Unbiased (替换为全局敏感度)	0.081	12s	无需平滑搜索但因受 $d_{\max}$ 限制加噪方差大 5.4×
Global-Biased (双退化基线)	0.145	11s	累加偏差与粗粒度敏感度噪声双重放大

任务分配算法在 Google Web Graph 上的消融¶

在具有有界退化度（Degeneracy $\gamma = 4$）的大规模 Google Web Graph 子图采样上对比任务分配方案诱导的协方差代价值 $\#C'_4$（采样率 $p=1.0$，三角形数 $|\Delta| > 1.3 \times 10^7$）：

分配策略 (Strategy)	协方差代价 $\#C'_4$	运行时间 (Runtime)	说明
Greedy (本文贪心近似)	26,427,913	61s	代价最低，比随机分配降低约 62%
Degeneracy (基于退化序)	41,021,836	59s	结构启发式，代价比 Greedy 高 1.6×
Random (随机均匀分配)	69,055,393	47s	简单均匀基线，代价最高

关键发现¶

在大规模三角形密集图（$|\Delta| \gg 10^5$）上，无偏估计器显著优于有偏估计器，其相对误差随着三角形数量增加而单调下降，严格印证了理论上从 $O(|\Delta|^2)$ 到 $O(|\Delta|)$ 的方差降阶。
平滑敏感度相较全局敏感度带来整整一个数量级的误差缩减，且由于采用了优化后的前缀和检索算法，在百万级三角形图上的耗时控制在 5 分钟内，兼具工程实用性。
在极稀疏图（如 GMWCS，仅 132 个三角形且平均度 $\approx 2$）上，由于每个节点注入的加性噪声累积占主导，直接发布全图边权重的非交互式 Baseline 略优于两阶段算法，表明两阶段算法的适用场景集中在稠密或中大规模型图结构。

亮点与洞察¶

公开拓扑信息的精妙利用：以往局部图差分隐私大多在全盲态下设计算法，本文指出网络拓扑往往为物理公开实体，敏锐抓住这一特性将图方差最小化解耦为经典离线负载均衡问题，证明平面图能达到零协方差。
平滑敏感度的 $O(d^2 \log^2 d)$ 算法突破：证明了敏感度极大值点必然落在局部平移边界，通过双向排序索引与二分查找消除循环嵌套，解决了图差分隐私领域平滑敏感度因计算耗时过高无法落地的顽疾。
理论下界匹配与理论闭环：不仅提出了多项式时间算法，还针对平面图和有界退化图分别构建了信息论下界，证明算法在平面图上渐近最优，退化图上紧密贴合。

局限与展望¶

极端稀疏图上的噪声累加效应：在三角形极少、度数极低的稀疏图上，两阶段报告机制中每个节点注入的独立敏感度扰动累积反而超过了真实信号，表现不如全局边扰动基准。
仅限静态无向整数加权图：当前算法假设边权重为非负或任意整数，且图拓扑静态不变；在流式动态图和连续实数权重场景下的扩展有待进一步推导。
计算更广泛子图基元：目前聚焦于低于阈值的三元环（三角形），向 4-cycle、clique 或 motif 等更广泛的高阶加权子图计数推广需要更复杂的超图分配与协方差消解模型。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出本地权重差分隐私（LWDP）下的子图计数问题，将方差优化与最小费用流、平滑敏感度算法完美结合。
实验充分度: ⭐⭐⭐⭐ 覆盖真实电信数据、生物稀疏网络、合成平面图/完全图及超大规模 Web 图，理论与实验高度契合。
写作质量: ⭐⭐⭐⭐⭐ 理论推导详实严密，从问题建模、方差剖析、算法设计到复杂度证明层层递进。
价值: ⭐⭐⭐⭐⭐ 为加权网络隐私分析、交通规划中的拥堵检测与隐私安全分析提供了极为扎实的新基准。

数据集 / 设置	评估指标	本文 (Smooth-Unbiased)	Global-Unbiased	Baseline (全加噪重建)	相比 Baseline 提升
ML-Tele-278 (\(\varepsilon=0.5\))	相对误差 (Rel. Error)	0.082	0.450	2.850	误差降低 97.1% (约 35×)
ML-Tele-278 (\(\varepsilon=1.0\))	相对误差 (Rel. Error)	0.038	0.185	1.120	误差降低 96.6% (约 29×)
ML-Tele-278 (\(\varepsilon=2.0\))	相对误差 (Rel. Error)	0.015	0.081	0.380	误差降低 96.1% (约 25×)
ML-Tele-278 (\(\varepsilon=4.0\))	相对误差 (Rel. Error)	0.007	0.025	0.012	误差降低 41.7% (约 1.7×)