CS Graph
Differential Privacy 差分隐私
一句话概括：允许从数据里学到“群体规律”，但不允许判断某一个具体的人 / 边 / 样本有没有出现在数据里。
差分隐私背后的直观想法是：如果随机修改数据库中的一个记录造成的影响足够小，求得的统计特征就不能被用来反推出单一记录的内容。
$\epsilon$-Differential Privacy
标准的数学定义：
$$
P[M(D) \in S] \leq e^{\epsilon} \cdot P[M(D’) \in S]
$$
其中，有
- $M$：表示算法
- $D$ 和 $D’$：原始数据和只差一个隐私单位的数据
- $S$：某一类可能的输出结果
- $\epsilon$：隐私预算
$\epsilon$ 越小，隐私越强；$\epsilon$ 越大，隐私越弱。在 DP 里永远有一个 trade-off：
隐私强度 ↑ -> 噪声 ↑ -> 准确率可能 ↓
隐私强度 ↓ -> 噪声 ↓ -> 准确率可能 ↑
Edge-level DP
主要保护的是：一条边是否存在
$G$ 和 $G’$ 只有一条边不同的情况下，如果算法满足 edge-level DP，那么攻击者看到输出后，不能很明确的判断这条边到底存不存在。
Node-level DP
保护的是：一个节点以及它相关的所有边是否存在
也就是说，$G$ 和 $G’$ 差了一个节点，以及这个节点连出去的所有边.
Laplace Mechanism 拉普拉斯机制
DP 最经典的方式就是：本来想输出一个准确统计量，但为了保护隐私，在结果上加随机噪声
这里加的噪声通常来自 Laplace Distribution 拉普拉斯分布
Laplace Mechanism 的形式是：
$$
M(D) = f(D) + \text{Lap} \left( \frac{\Delta f}{\epsilon} \right)
$$
其中，我们有：
- $f(D)$：真正想查的统计量
- $\Delta f$：Sensitivity 敏感度
- $\text{Lap} \left( \frac{\Delta f}{\epsilon} \right)$：拉普拉斯噪声
Laplace Distribution：
$$
X \sim \text{Lap}(\mu, b)
$$
其 PDF 概率密度函数为：
$$
f(x) = \frac{1}{2b} \exp \left( - \frac{|x-\mu|}{b} \right)
$$
在 DP 中，我们一半用均值 $\mu=0$ 的形式，即：
$$
X \sim \text{Lap}(b) \
f(x) = \frac{1}{2b} \exp \left( - \frac{|x|}{b} \right)
$$
Sensitivity 敏感度
敏感度问的是：如果只改变一个隐私单位，查询结果最多会变多少？
其在数学上的定义是
$$
\Delta f = \max_{D, D’} \lVert f(D) - f(D’) \rVert_1
$$
注意这里是 L1 范数，即曼哈顿范数
比如统计一个节点 $u$ 的 1-hop 邻居 label count：[A count, B count, C count]
如果只改变一条边 $(u,v)$，那么 $u$ 的邻居集合多一个或少一个节点 $v$。假设 $v$ 的 label 是 B，那么 count vector 可能从 [10, 2, 1] 变成 [10, 3, 1]，最多一个位置变化 $1$，那么这里的 $\Delta f=1$，可以在 $f(D)$ 上加 $\text{Lap} \left( \frac{1}{\epsilon} \right)$
Post-processing 后处理
差分隐私有一个非常重要的性质：如果一个机制 $M(D)$ 已经满足 DP，那么对它的输出做任何不再访问原始私有数据的后处理，都不会额外消耗隐私预算。
数学上可以写成：
$$
M(D) \text{ is DP} \Rightarrow g(M(D)) \text{ is also DP}
$$
其中 $g$ 可以是任意函数，例如 argmax、MLP、Controller、ensemble、calibration 等。
直观理解是：如果敏感信息已经被 DP 噪声保护过了，那么后续模块只看到这个 DP-protected output，而没有再次访问原始数据，因此不会泄露更多隐私。
Composition 隐私预算累积
如果一个算法多次访问 private data，并且每次都使用一个 DP mechanism，那么总的 privacy budget 会累积。
最简单的 sequential composition 可以理解为：
$$
\epsilon_{\text{total}} = \epsilon_1 + \epsilon_2 + \cdots + \epsilon_k
$$
这说明 DP 不是“加一次噪声就永远安全”，而是每次重新访问原始私有数据都可能消耗 privacy budget。
在图任务中，如果 GNN 训练过程中反复访问 raw graph structure，那么每次训练 / retraining 都需要考虑额外的 privacy cost。而如果我们先生成一个 DP-protected graph statistic，后续只使用这个 statistic，则后续步骤可以看作 post-processing。
Gaussian Mechanism 高斯机制
除了 Laplace Mechanism，DP 中也常用 Gaussian Mechanism，即加入高斯噪声：
$$
M(D) = f(D) + \mathcal{N}(0, \sigma^2)
$$
Gaussian Mechanism 通常对应的是 $(\epsilon, \delta)$-DP，而不是 pure $\epsilon$-DP。
其中 $\delta$ 可以理解成一个很小的失败概率。相比 pure DP，$(\epsilon,\delta)$-DP 稍微放松了一点隐私要求，但在深度学习和高维向量场景中更常用。
References 参考
ChatGPT 5.5 Thinking