Differential Privacy for Collabo

协同过滤推荐算法中的差分隐私

IWSPA '16: Proceedings of the 2016 ACM on International Workshop on Security And Privacy Analytics

下载地址：https://dl.acm.org/doi/abs/10.1145/2875475.2875483

关键词：

推荐 协同过滤 推理共计 差分隐私

背景及现状：

一些现有的方法将差分隐私与协同过滤结合是通过向评分矩阵添加噪声。攻击者可以使用推理攻击等手段可以从用户购买记录中得到用户的其他信息。

提出问题：

如何保护用户隐私

解决方法：

该文在推荐过程中采用了差分隐私，而非对数据集，设计了两种算法：基于项目的差异隐私推荐(DP-IR)和基于用户的差异隐私推荐(DP-UR)

研究重点&亮点：

1. 针对推理攻击进行研究解决

2. 研究了什么样的相似性度量适用于差分隐私机制

3. 对购买记录进行了差分隐私保护

主要内容：

1. 将差分隐私基础定义公式根据协同过滤矩阵进行改写

相邻矩阵

M与M'是相邻矩阵，只有一条用户记录不同

l1范数敏感度

L1范数敏感度，用于评估差分隐私算法输出与最佳输出相比的误差。

Advanced Composition

Advanced Composition——[1]的Theorem 3.20、[2]、[3]

论文里的公式打错了...ε应当在根号外。

2. DP-IR

根据评分矩阵计算每个项目的相关项目列表，然后针对目标用户，根据其购买历史来计算最相关的项目列表。通过低敏感度相似性度量(carefully designed similarity measurement with low sensitivity)将指数机制应用于相关项目的选择。

Step 1：给定一个用户及其购买记录，抽样得到一个新的user-item矩阵T，设计一个差分隐私算法DP − A1(T, c, δ0,Iu) → L|Iu|根据T计算相关列表，满足(c, δ0)-差分隐私。

Step 2：根据算出的列表向用户推荐k个商品

思路

算法1

Sij为项目相似度。算法1为基础的基于项目的推荐算法，不具有保护隐私的功能。例如图书馆发布了每本书的相关列表，假设攻击者知道关于目标用户U的一些信息，如部分购买记录。再假设U在某个时间段使用系统并购买了物品M，则物品M就会被加入到购买记录中，而M和所有购买记录中物品的协方差都会增加，所以在相关购物记录中M的排名/秩(?rank)都会增加。攻击者就可以从相关购物记录中来推断U的购物活动，甚至能推断出购买的是M。

算法2

该ε'公式可从[1]第52页的Corollary 3.21得到。算法2中的敏感度为1，用点相似度(Dot Similarity)作为评分函数，因为数据太大，为了降低Sij的计算复杂度，要进行抽样处理。根据指数机制得到的概率值进行抽样，获得每个被抽样物品的一系列相关列表。

算法3

算法3将敏感度改变为1/p，p的值为ε/2，满足(ε, εδ0/2)-差分隐私。

算法4

挑选top-k物品作为推荐。

证明符合(ε, δ)-差分隐私

比较了欧几里得距离和余弦相似度，发现在基于物品的协同过滤中还是用点相似度在召回率方面表现更好点。

3. DP-UR

对于特定用户，先在评分矩阵中根据用户的购买历史计算用户之间的相似度，然后选择最相关的用户列表。然后根据相关用户评分的加权得分总和计算每个项目的得分。将具有高分数的项目选择为对用户的推荐列表。

推理攻击：假设攻击者已经有一些关于目标用户U的购买历史背景，这一次的攻击目的是为了获取U购买的其他物品信息。攻击者显示创建k个sybil用户，并用U的北京信息来填充每个sybil用户的购买历史。接着攻击者试图假装其中一个sybil用户并检查推荐列表来推断U的其他购买记录，而这个列表的排名靠前的物品都可能被U买走。

算法5

用皮尔逊系数计算用户相似度S'(u,v)。

4. 实验

显示平均误差随着训练集大小的增加而减小

参考资料：

[1] The Algorithmic Foundationsof Differential Privacy

[2] https://zhuanlan.zhihu.com/p/212819144?utm_source=wechat_session、

[3]https://zhuanlan.zhihu.com/p/264779199