论文来自于：
Sajadmanesh S, Gatica-Perez D. Locally private graph neural networks[C]//Proceedings of the 2021 ACM SIGSAC conference on computer and communications security. 2021: 2130-2145.
摘要
图神经网络（GNN）在学习节点表示以完成多种图推理任务时表现出色。然而，当节点代表个人或涉及敏感信息的人类相关变量时，基于图数据的学习可能引发隐私问题。尽管已有大量针对非关系数据的隐私保护深度学习技术，但针对图上深度学习算法的隐私问题研究较少。
本文研究节点数据隐私问题：图节点拥有潜在敏感数据（特征向量与标签）保持私有，但可被中心服务器用于训练GNN。提出一种基于局部差分隐私（LDP）的隐私保护GNN训练算法，具备形式化的隐私保证。
核心贡献
- 多比特机制（Multi-bit Mechanism）：LDP编码器 + 无偏整流器，实现高效通信下特征扰动与收集。
- KProp层：基于多跳聚合的简单图卷积层，增强去噪能力，提升首层卷积估计精度。
- Drop鲁棒训练框架：利用KProp对噪声标签进行去噪，提升泛化性能。
- 理论分析：隐私保证、误差界。
- 实验验证：在真实数据集上实现良好的准确率-隐私权衡。
问题定义与背景
图结构
- 图 $ G = (V, E, X, Y) $
- $ V = V_L \cup V_U $：有标签节点 + 无标签节点
- $ X \in \mathbb{R}^{|V| \times d} $：特征矩阵（私有）
- $ Y \in {0,1}^{|V| \times c} $：标签矩阵（私有）
- 服务器拥有：$ V, E $
- 节点私有：$ X, Y $
目标
在不泄露原始 $ X, Y $ 的前提下，训练GNN。
图神经网络（GNN）基础
每层嵌入更新：
$$ h^l_{N(v)} = \text{Aggregate}^l \left( \{ h^{l-1}_u \mid \forall u \in \mathcal{N}(v) \} \right) $$$$ h^l_v = \text{Update}^l \left( h^l_{N(v)} \right) $$- 初始：$ h^0_v = x_v $
- 最后一层输出 $ c $ 维向量 + softmax 预测标签
局部差分隐私（LDP）
定义 2.1：机制 $ M $ 满足 $ \epsilon $-LDP，若对任意输入 $ x, x’ $ 和输出 $ y $：
$$ \Pr[M(x)=y] \leq e^\epsilon \Pr[M(x')=y] $$- $ \epsilon $：隐私预算（越小越强）
- 实现方式：本地扰动 → 聚合去噪
整体框架
流程
- 节点本地扰动 每个节点用 Multi-bit Encoder 对特征进行局部扰动，生成编码向量；有标签节点用 广义随机响应 扰动标签。一次性上传至服务器。
- 服务器去偏估计 服务器用 Multi-bit Rectifier 对所有扰动向量进行无偏校正，估计近似首层卷积输入。
- 插入 KProp 去噪 在 GNN 前插入 KProp 多跳聚合层，通过 K 步线性传播平均化噪声，增强低度节点表示。
- GNN 训练（Drop 鲁棒框架）
- 前向传播得到预测概率
- 用 KProp 聚合预测概率，生成“净化标签”
- 结合扰动标签 + 净化标签计算损失
- 反向传播更新模型
- 迭代至收敛 每轮重复扰动→上传→去偏→训练，直至模型收敛。
- 推理 训练好的 GNN 直接用于新节点分类（无需再扰动）。
核心特点：一次通信 + 聚合去噪 + 标签净化，实现 隐私保护下的高精度 GNN 训练。
核心组件
Multi-bit Encoder（节点端）
- 输入：节点 $ v $ 的原始特征 $ x_v \in \mathbb{R}^d $
- 输出：扰动编码向量
- 目标：高维特征下高效通信 + LDP保证
- 方法：扩展1-bit机制至多维，逐维度采样并翻转
每个节点仅需一次通信发送扰动特征
Multi-bit Rectifier（服务器端）
- 输入：所有节点的扰动编码
- 输出：无偏估计的聚合特征
- 作用：校正统计偏差，近似首层图卷积
- 关键：利用线性聚合作为天然去噪机制
聚合平均化注入的差分隐私噪声
KProp（多跳聚合层）
$$ h_v^{(k)} = (1 - \alpha) h_v^{(k-1)} + \alpha \cdot \text{Aggregate}(h_u^{(k-1)}, u \in \mathcal{N}(v)) $$- 输入：扰动后特征
- 操作：迭代K次线性聚合，扩展有效邻域至K跳
- 作用：
- 增强去噪（噪声 ~ 1/√聚合规模）
- 提升低度节点估计精度
- 可插入任意GNN前作为预处理层
特别适用于幂律分布图（多数节点度数低）
标签扰动（Randomized Response）
正确标签保留概率：$ p = \frac{e^\epsilon}{e^\epsilon + c - 1} $
其他类别随机翻转为：$ q = \frac{1}{e^\epsilon + c - 1} $
Drop：鲁棒训练框架
挑战
- 噪声标签 → 过拟合 → 泛化差
- 无干净验证集 → 难以调参
解决方案
- 利用KProp对标签预测概率进行多跳聚合
- 估计每个节点的邻域标签频率
- 选择频率最高者作为“净化标签”
- 用于损失计算或早停判断
不依赖任何干净数据（特征/标签）
符号表（文中主要符号）
| 符号 | 含义 |
|---|---|
| $ G = (V, E, X, Y) $ | 图结构 |
| $ V_L, V_U $ | 有/无标签节点集 |
| $ x_v \in \mathbb{R}^d $ | 节点 $ v $ 的特征向量 |
| $ y_v \in {0,1}^c $ | 节点 $ v $ 的one-hot标签 |
| $ \mathcal{N}(v) $ | 节点 $ v $ 的邻居集（可含自身） |
| $ h^l_v $ | 第 $ l $ 层节点 $ v $ 的嵌入 |
| $ \epsilon $ | 隐私预算 |
| $ K $ | KProp 步数 |
| $ M(\cdot) $ | LDP扰动机制 |
| $ \text{MB-Encoder} $ | 多比特编码器 |
| $ \text{MB-Rectifier} $ | 多比特整流器 |