作者：Zibo Wang，Yifei Zhu，Dan Wang，Zhu Han
单位：上海交通大学
来源：IEEE INFOCOM 2022
时间：2022
背景
传统频繁模式挖掘（FPM）依赖集中式数据收集，但隐私保护法规如GDPR、CCPA限制了原始数据的共享，现有的隐私保护方法如RAPPOR、SFP存在局限性，仅支持单一模式类型、复杂数据结构下效用损失严重。作为联邦学习的相似范式的联邦分析FA在FPM任务多为任务专用，缺乏面对通用场景的计算框架。
核心创新点
论文提出FedFPM框架，是第一个用于各种FPM问题的统一FA框架，包括频繁项、项集和序列挖掘，通过模块化设计实现通用性。
- FedFPM实现了高数据效用，采用交互式查询-响应机制，客户端不上传原始数据，而是响应服务器的查询，满足LDP，并通过高效的候选生成和验证设计为每个单独的客户端带来了较小的通信和计算成本。
- 使用 Apriori原理 和 Hoeffding不等式 控制候选生成和置信区间判断，实现理论可证明的隐私保护与误差控制。
FedFPM框架在不同的FPM场景中的性能优于前沿的专业基准，同时在计算开销方面约为基准的86%~98%
FedFPM框架
FedFPM主要用于解决三种FPM任务，分别是频繁项挖掘（FIM）、频繁项集挖掘（FIsM）、频繁有序序列挖掘（FSM）。
框架采用了一个服务器端和客户端的交互式查询-响应机制，流程包括五个部分：候选生成、候选分发、客户端响应、候选更新、候选筛选
候选生成（Candidate Generation）
框架中对于频繁模式分为三个池，接受池，拒绝池，候选池
候选生成阶段根据已经接受的频繁模式，生成新的候选模式，其中对于不同的任务生成候选的策略不同，根据Apriori原则（频繁模式的所有子模式也一定是频繁的）
FIM：直接枚举所有项
FIsM：两个项集可以合并生成新的候选项集
FSM：两个子序列拼接生成更长候选序列
候选分发（Candidate Distribution）
服务器从候选池中选择部分候选模式，随机发送给客户端，客户端仅仅需要响应一个候选模式，对于客户端，开销小
客户端响应（Client Response）
客户端接受到服务器发送的候选模式，在本地数据中进行判断，并返回扰动后的响应，其中扰动使用随机扰动来实现本地差分隐私，论文定义二元随机应答，公式如下：
b为原本模式的结果η为噪声因子，客户端将扰动后的结构返回服务器端
候选更新（Profile Update）
每个候选模式具有两个属性，cy和cn，服务器收集客户端响应，记录每个候选的 “是” 计数（cy）和 “否” 计数（cn）。
候选筛选（Candidate Filtering）
在一轮的响应完成后，服务器基于响应结果判断是否将候选加入“接受池”或“拒绝池”。决策部分使用Hoeffding 不等式。
引入了参数ξ作为允许错误率，频繁模式的频率阈值表示为f，噪声因子表示为η
但候选者的置信度满足17号定理公式，可以认定为具有置信度的频繁模式，该候选模式可以放入接受池，满足18号定理公式，则认为候选模式不频繁，置入拒绝池，同时当候选模式打到最大响应阈值采用强制决策，根据19号定理进行候选判断。
实验及分析
数据集：
使用真实数据集，Kosarak、MovieLens和MSNBC，分别用于评估FedFPM框架在FIM、FIsM和FSM场景中的性能。
基准选择：
RAPPOR：保护工业隐私的FIM方法，同时采用onehot编码处理FIsM场景
SFP：保护隐私的FSM方案
评估指标：
F1：衡量挖掘准确性
Client usage：参与任务客户端数量，反映系统资源消耗
Client runtime：客户端平均计算时间，衡量计算负担
实验结果分析：
在下图a-f中，FedFPM在FIM和FSM场景中表现优于RAPPOR和SFP方案，在FIsM场景中与RAPPOR持平，但是随问题规模增加，适用性优于RAPPOR。
客户计算负担方面，下图a-c，论文框架明显优于对比基准
总结与启发
总结：
论文提出了一个统一的联邦分析框架FedFPM，用于在保护用户隐私的前提下进行频繁模式挖掘。FedFPM通过采用LDP和交互式查询响应机制，使得每个客户端只需本地判断一个候选模式是否存在，并将扰动后的响应上传至服务器，从而在不暴露原始数据的前提下实现协同挖掘。服务端利用Apriori原理生成候选模式，通过 Hoeffding 不等式进行频率可信度筛选，动态更新候选池，实现高效低开销的频繁模式识别。
启发
- 论文框架方向基于联邦分析，对于频繁模式进行挖掘，在隐私计算方面，采用本地扰动+基于Hoeffding不等式的概率置信评估策略实现本地差分隐私，属于隐私计算的一类，可以参考课题的相关协作计算研究，属于扰动加密
- 论文框架依赖大量客户端，从而得到统计可信的频繁模式，但是节点换为数据孤岛的时候，结果的可信度会明显降低，同时论文方法依赖多迭代，对于基于区块链的场景开发，会增加交互成本。