ICML'21 | 隐私保护下的图神经网络推荐系统

2021 年 11 月 4 日 图与推荐

基于图神经网络的推荐系统已经在很多工业场景验证了其有效性。最近，关于用户隐私的关注越来越多，如何在保证隐私的前提下实现GNN based Recommendation？ICML 2021 FedGNN: Federated Graph Neural Network for Privacy-Preserving Recommendation这篇文章就很好的回答了上述问题。

前言

现有的基于 GNN 的推荐方法依赖于用户-物品图的集中存储和集中的模型学习，然而用户数据是隐私敏感的，数据的集中存储存在隐私泄露的风险。本文提出了一个基于GNN 隐私保护的联邦学习框架，在保护隐私的前提下从离散的的用户数据中训练 GNN 模型，并利用高阶的用户物品交互信息完成高效的推荐。

如果大家对大图数据上高效可扩展的 GNN 和基于图的隐私计算感兴趣，欢迎关注下面的 Github，之后会不断更新相关的论文和代码的学习笔记。

https://github.com/XunKaiLi/Awesome-GNN-Research

Motivation

现有的基于 GNN 的推荐方法通常需要集中存储整个用户-物品图来学习 GNN 模型以及用户和物品的 embedding，这意味着用户-物品交互数据需要集中存储，如图1（a）所示。然而，用户-物品交互数据是高度隐私敏感的，其集中存储会导致用户的隐私问题和数据泄露的风险。此外，在 GDPR1 等严格的数据保护法规的压力下，在线平台可能无法集中存储用户物品交互数据，以便在未来学习GNN模型进行推荐。

解决用户-物品交互数据隐私问题的一个直观方法是在用户设备上本地存储原始数据，并在此基础上学习本地 GNN 模型，如图1（b）所示。但是存在以下限制：

对于大多数用户来说，他们设备上的交互数据量太小，无法在本地训练准确的 GNN 模型。因此需要一个统一的框架，协调大量的用户客户端，从分散的用户数据中集体学习一个准确的全局 GNN 模型。
在本地用户数据上训练的本地GNN模型可能会上传私人信息，在从本地模型合成全局 GNN模型时，保护用户隐私存在困难。
本地用户数据只包含一阶用户-物品的交互，由于隐私限制，用户的行为历史信息不能直接交换。因此，在不泄露隐私的情况下利用高阶用户-物品交互信息存在困难。

FedGNN

FedGNN 在在每个用户客户端基于本地用户-物品交互数据推断出的用户-物品图来训练 GNN 模型。每个客户端将 GNN 的本地梯度上传到服务器端进行汇总，经过客户端处理后，这些梯度会被进一步发送给用户客户端以更新本地 GNN 模型。
为保护梯度中的隐私信息，FedGNN 对本地梯度应用本地差分隐私（local differential privacy）技术以保护隐私。
为了保护用户产生交互的历史行为信息，FedGNN 使用随机抽样的项目作为假的交互历史信息以实现匿名。
为了纳入高阶的用户-物品行为信息，FedGNN 提出了一种用户-物品图扩展方法找到有共同交互的相邻用户，并交换他们的嵌入，以保护隐私的方式扩展本地用户-物品图。

Problem Formulation

定义用户集合和物品集合：，分别代表用户物品的数量。评分矩阵为，用户物品的交互二部图的生成基于观察到的评分，用户的 K 个交互物品集合表示为，一名用户和其交互物品集合可以构成一阶用户物品交互子图，用户的 K 个物品评分集合可以表示为。为了保护用户隐私，模型目标是基于用户本地存储的一阶用户物品交互子图在保证隐私的条件下预测没有观察到的评分矩阵部分。

FedGNN Framework

FedGNN 主要由一个中央服务器和大量的用户客户端组成。用户客户端保留一个本地子图，该子图由用户与物品的交互历史和该用户的邻居组成。每个客户端从其本地子图中学习用户/物品嵌入和 GNN模型，并将梯度上传至中央服务器。中央服务器负责在模型学习过程中协调这些用户客户端，从一些用户客户端收到的梯度汇总，并将汇总的梯度传递给客户端。

每个用户客户端上的局部子图是由用户与物品的交互数据和与该用户共同交互过物品的邻近用户构成。这个用户的节点与其所交互的物品的节点以及邻居用户的节点相连。

首先在嵌入层使用基于每个用户客户端的交互子图生成用户和邻居物品及用户集合的嵌入，用表示，由于在模型没有调参的情况下，用户嵌入可能不够准确，所以在模型迭代的前T 次中排除相邻用户嵌入，当模型调参后再纳入学习。用户的嵌入和物品嵌入可以在模型训练中进行局部调整，而相邻用户的嵌入是固定的（即使可训练，对模型效果帮助不大）。
使用 GNN 处理 embedding，为本地一阶子图上的节点之间的相互作用建模。输出相应的结果：。
使用评分预测模块基于用户和物品嵌入预测用户交互评分。
预测的评分与用户设备上本地存储的真实评分进行比较，以计算损失函数。符号化的表示形式为：，进一步使用损失来得出模型和嵌入的梯度，分别用和表示。之后将梯度上传到服务器进行汇总。
服务器协调所有的用户设备并计算全局梯度以更新用户客户端的模型和嵌入参数。在每个 epoch 中，服务器唤醒一定数量的用户客户端来计算本地梯度并发送给服务器。在服务器收到这些用户的梯度后，服务器上的聚合器 [1] 将把这些本地梯度聚合成一个统一的梯度
服务器将汇总的梯度发送给每个客户端，以进行本地参数更新。将第 i 的用户设备中的参数集称为。，是学习率。

算法描述如下：

(1-4)：每个用户客户端构建本地子图（包含交互物品节点和相邻用户节点），并初始化参数

Privacy-Preserving Model Update

Privacy-Preserving Model Update 模块对应于算法（9-11）。在用户客户端和中心服务器通信时，如果直接上传 GNN 模型和物品嵌入梯度，可能会出现一些隐私问题：

首先，对于嵌入梯度来说，只有与用户有交互的物品才有非零的梯度来更新其嵌入，服务器端可以根据非零的物品嵌入梯度直接恢复完整的用户-物品交互历史。
除了嵌入梯度，GNN 模型和评分预测器的梯度也可能泄露用户历史和评分的私人信息，因为 GNN 模型的梯度编码了用户对物品的偏好。在现有的方法中，如FedMF，同态加密（HE）被应用于梯度以保护隐私评分信息。然而，在这种方法中，用户设备需要在本地记忆整个物品集的嵌入表，并在每次迭代中上传，以实现用户交互历史的保护，由于在模型训练中存在巨大的存储和通信成本，这是不现实的。

本文提出了两种策略来保护模型更新过程中的用户隐私。

pseudo interacted item sampling：对用户没有互动过的M物品集合进行抽样，并使用与真实交互物品嵌入梯度均值和方差相同的高斯分布随机生成其梯度。真实嵌入梯度与伪物品嵌入梯度相结合，在第 i 个用户设备上的模型和嵌入的统一梯度更新为。
local differential privacy（LDP）。根据用户客户端的局部梯度，设置阈值的 -norm，并对统一梯度应用零均值拉普拉斯噪声的局部微分隐私（LDP）模块，以实现更好的用户隐私保护：，其中是拉普拉斯噪声的强度。受保护的梯度被上传到服务器进行汇总。

Privacy-Preserving User-Item Graph Expansion

Privacy-Preserving User-Item Graph Expansion 模块对应于算法（15），该模块希望寻找用户的邻居，并以保护隐私的方式扩展本地用户-物品图。在现有的基于集中式图存储的 GNN推荐方法中，高阶用户-物品交互可以直接从全局用户-物品图中得到。然而，当用户数据是分散的，要在不违反用户隐私保护的前提下纳入高阶用户-物品交互存在困难。为了解决这个问题，本文提出了一种保护隐私的用户-物品图扩展方法，该方法可以找到用户的匿名邻居，以增强用户和物品表示的学习，其中用户隐私不会泄露。其框架如图 3 所示。

维护推荐服务的中央服务器首先生成一个公钥，然后分发给所有用户客户端进行加密。在收到公钥后，每个用户设备根据这个密钥对互动过的物品的 ID 进行同态加密（因为这些物品的 ID是隐私敏感的），加密后的物品 ID 以及这个用户的嵌入被上传到第三方服务器（不一定被信任）。该服务器通过物品 ID 匹配找到与相同物品存在交互的用户，然后向每个用户提供其匿名邻居的嵌入。在这个阶段，负责推荐的服务器永远不会收到用户的私人信息，而第三方服务器由于无法解密物品的 ID，所以也无法获得用户和物品的任何私人信息。算法描述如下：

Analysis on Privacy Protection

FedGNN中，用户隐私受到四个方面的保护：

在 FedGNN 中，负责推荐的中心服务器从不收集原始的用户-物品交互数据，只有本地计算的梯度被上传到该服务器。基于数据处理的不平等性，可以推断出这些梯度所包含的私人信息比原始的用户交互数据要少得多。
第三方服务器不能从经过同态加密的物品 ID 中推断出私人信息，因为它不能获得私钥。然而，如果推荐服务器与第三方服务器串通，交换私钥和物品表，用户交互历史将得不到保护。但是私人评分数据仍然可以通过隐私保护模型更新方法得到保护。
在FedGNN中提出了一种假的交互物品抽样方法，通过采样一些没有与用户产生交互的物品来保护真实的交换物品。由于这两种交互物品的梯度具有相同的均值和方差，如果伪交互物品的数量足够多于真实交互物品的数量，就很难将真实交互物品与伪交互物品区分开。隐私保护的平均程度与成正比。因此，只要用户设备的计算资源允许，伪交互项目的数量可以相对较大，以实现更好的隐私保护。
FedGNN 将 LDP 应用于用户设备本地计算的梯度，使其更难从这些梯度中恢复原始的用户交互历史。隐私预算的上限是，这意味可以通过使用较小的剪切阈值或较大的噪声强度实现较小隐私预算。需要合理选择这两个超参数来平衡模型性能和隐私保护。

Experiments

超参数设置可见 Dataset and Experimental Settings。

在实验中使用的指标是均方误差（RMSE），实验结果为 10 次重复的 RMSE 值。

Figure 4 验证了纳入用户-物品图高阶信息的有效性，以及 FedGNN 的通用性。比较了 FedGNN 及其变体在完全可训练的邻居用户嵌入或没有高阶用户-项目交互的情况下的表现。并比较 GNN 模型（GGNN、GCN和GAT）的不同实现方式下的结果：https://pic2.zhimg.com/80/v2-71fb6592fb36ddbe34106621c756b3f9_1440w.jpg