IEEE引用格式：J. Xia et al., “SMAP: A Joint Dimensionality Reduction Scheme for Secure Multi-Party Visualization,” 2020, [Online]. Available: http://arxiv.org/abs/2007.15591.

文章简介

在多方数据被融合到一个站点来建立点集关系时，传统的可视分析方法(如降维)可能会暴露数据隐私，可视分析中的数据隐私是一个重要的需求，比如几个医院想要执行其病人数据的联合分析，同时保持他们的数据隐私

应用可视化技术帮助人们理解多方高维数据的时候，通常会采用降维技术，比如主成分分析(PCA)，多维尺度(MDS)，t-SNE，将所有的数据点投影到一个公共空间，然而降维技术首先就会破坏数据的隐私性，比如传统的降维方法是为单站点计算设计的，需要从所有站点收集原始数据来创建联合嵌入，如果在多方数据之前简单地匿名化数据又会减少数据的效用，导致不准确的布局，而且匿名的数据也有被保护的必要。其次当其他人采用可视化设计来检查隐私敏感数据时，数据隐私也会受到威胁

基于此，文章提出了一种安全的多方可视化联合降维方法，允许在可视化生成和可视化消费两个阶段保护隐私数据，首先开发了一个安全的t-SNE嵌入多方计算方案，对t-SNE的重设计中核心的挑战就是原始数据和数据点中间的距离矩阵都可能威胁到数据的隐私，这些都不应该暴露给参与者，其次建立了一个在线可视化系统SMAP，支持隐私感知的嵌入结果探索

总的来说，文章的贡献分为两个部分：

  1. 一种安全的联合t-SNE多方降维方案
  2. 一个在线可视化系统，以支持隐私保护的探索和在线任务组织

相关工作

安全感知的分布式机器学习和数据挖掘

在机器学习和数据挖掘领域，解决原始数据分布在多个参与者中的安全问题的一个常见方法是差异隐私理论，采用随机机制更改原始的输入数据并且保持数据的实用性，常用的随机扰动有高斯噪声和拉普拉斯噪声，显然噪声越多越能保护隐私但同时解释结果的偏差也越大，在以往的研究中，并没有能做到降维的同时保持距离矩阵不暴露

可视化中的隐私保护

与数据挖掘对应方法类似，可视化领域的隐私保护针对两种主要风险类型：身份披露(个人身份被链接到特定数据)和属性披露(敏感的属性)，一个常见的解决策略是在敏感信息的显示中应用视觉不确定性(比如模糊效果或者聚合集群)

本文的方法旨在将数据嵌入低维空间，在低维空间中身份和属性的暴露可以自然地被消除，而集群或异常可以被保留，若点级别关系是高度敏感的，则可以使用聚合可视化来隐藏点级别信息

降维

降维指将高维数据投影到低维空间，同时保留特定的属性，比如主成分分析(PCA)保留了数据点之间的方差，线性判别分析(LDA)试图保持簇之间的可分离性，t距离随机邻点嵌入(t-SNE)和多维标度(MDS)则保护基于距离矩阵的数据点之间的相似性

降维意味着数据的压缩，因此在很多应用中被用于保护数据的隐私，这些研究和本文的区别是，他们是利用降维来解决隐私问题，降维在单地点进行，但是本文的目标是在多方降维的过程中防止其他参与者的数据暴露

场景，需求与方法概述

示例场景

多方数据分析

在该场景中，参与者希望在全局数据的上下文中分析本地数据，同时对彼此保持数据的私密性，比如多个社区医院的分析人员希望探索社区之间的差异，识别异常患者，然而因为隐私保护原因他们不能融合他们的数据。通过安全的联合嵌入，可以将局部数据点投影到共享空间中，在共享空间中可以可视化分析所有数据点之间的相似性

数据采购

在数据驱动的应用程序中，用户往往需要购买丰富的数据，通过数据市场训练自己的机器学习模型，出于成本考虑，必须仔细选择合适的数据集，比如覆盖失败样本或者支持少数的数据集，然而这些信息在购买数据集之前是未知的，安全多方可视化为用户提供了一种工具，可以在不影响数据隐私的情况下，将本地数据与销售数据进行比较。这种信息透明性有助于用户做出购买决策

需求分析

R1：在多方可视化中保留隐私

考虑到所有参与者对数据都很好奇，应该保证在整个过程中所有参与者都不能获得或推断出原始数据

R2：在可视化过程中保护隐私

在散点图中，每个参与者应该只允许探索全局数据点的低维表示，而不是高维表示

R3：支持隐私感知可视化结果的交互式探索

参与者只能通过局部数据和相似度来推断高维信息

R4：支持在多个参与者之间组织在线联合嵌入任务

除了联合嵌入算法外，还需要一个连接不同站点参与者的在线系统，在真实环境中设置框架

方法概述

基于上述需求，本文提出了一种联合t-SNE方案，开发了一个安全多方可视化的在线可视化系统

首先，提出了一种安全的多方联合t-SNE协议，旨在保护数据隐私，只有加密的和有噪音的数据被传送给两个外部合作者，其次，设计了一个在线可视化系统，该系统支持隐私保护可视化，此外，在线系统连接来自不同站点的参与者，组织在线联合嵌入任务

安全多方投影

t-SNE算法

在高维空间中，两个数据点$x_i$和$x_j$之间的相似性用对称概率$p_{ij}$表示，即$x_i$是$x_j$的邻居的概率，$p_{ij}$表示为

$p_{ij}=\frac{(p_{j|i}+p_{i|j})}{2N}$

其中N是点的数量，条件概率$p_{j|i}$的计算方法为

$p_{j|i}=\frac{\exp(-||x_i-x_j||^2/2\sigma_i^2)}{\sum_{k\neq l}\exp(-||x_i-x_k||^2/2\sigma_i^2)}$

在低维空间中，t-SNE采用了一个单自由度的t分布来描述分布，表示$y_i$点和$y_j$点相似性的联合概率$q_{ij}$被定义为

$q_{ij}=\frac{(1+||y_i-y_j||^2)^{-1}}{\sum_{k \neq l}(1+||y_k-y_l||^2)^{-1}}$

$y_i$和$y_j$是$x_i$和$x_j$的嵌入

t-SNE算法通过最小化高维空间和低维空间概率分布之间的KL散度来优化嵌入。KL散度表示为

$C=KL(P||Q)=\sum_i\sum_jp_{ij}log\frac{p_{ij}}{q_{ij}}$

联合t-SNE的安全多方协议

通过对t-SNE算法的回顾，可以知道其中关键的一步是计算高维空间中的条件概率$p_{j|i}$，而其计算依赖于高维空间中成对距离的计算，这是将传统降维方法转化为安全的多参与者版本的一个障碍，因为成对距离矩阵不能暴露给任何的参与者，因此$p_{j|i}$的计算必须重新设计

为了解决这个问题，文章中提出了一个安全的多方协议t-SNE，除了数据的拥有这，还引入了两个协作者S和T来提供计算服务，体系结构如图所示

T只加密没有私钥的数据，而S只加密有噪声的数据。S和T相互协作计算t-SNE布局，并将结果分发给参与者。在假设这两个协作者不会相互串通的情况下，数据隐私得到保护

协议的过程如下图所示

协议中采用的符号说明见下表

Step1：密钥的生成与传播

S生成用于数据加密的公钥PK和用于数据解密的私钥SK，S广播PK到T和所有的P，在协议中，使用加性同态加密进行数据加密，在加性同态加密(AHE)下，保留了加法和标量乘法，有SK(PK(a) ◦ PK(b)) = a + b，SK(PK(a) ⋄ PK(b)) = a − b，以及SK(a ⋆ PK(b)) = a ∗ b，PK()和SK()指用公钥和私钥加密，◦，⋄和⋆表示加密数据的加法减法和标量乘法

Step2：加密数据收集

每个参与者P将本地数据X加密的数据PK(X)发送到T

Step3：加密数据加入噪声

给定来自所有参与方的数据X，T给加密数据的每个条目添加一个随机的噪声

$PK(\bar{x_{ij}})=PK(x_{ij})◦PK(\sigma_{ij})$

$\sigma_{ij}$是一个随机的噪声，然后T将噪声加密数据发送给S

Step4：噪声距离计算

首先协作者S用$SK(PK(\bar{x_{ij}}))=x_{ij}+\sigma_{ij}$来解密数据，然后噪声欧几里得距离可以通过如下公式计算

$z_{ij}=\sum_{k=1}^m((x_{ik}+\sigma_{ik})-(x_{jk}+\sigma_{jk}))^2$

m是数据点的维度

接着S将噪声距离矩阵加密为PK(Z)并发送给T，Z是加密噪声距离矩阵

Step5: 加密的距离计算

在这个步骤中，协作者T计算加密的精确距离矩阵D

对$\sigma_{ik}-\sigma_{jk}$替换为$\delta_{ijk}$，可以将上式转化为

将$x_i$和$x_j$之间的距离记为$d_{ij}$，可以进一步将式子转化为

加密的平方距离$PK(d_{ij}^2)$可以被计算为

Step 6：在加密距离中加入噪声项

在此步骤中，协作者T在加密距离矩阵PK(D)中加入了噪声并将其发送给S

Step 7：对称概率计算

这一步中，S计算高维空间中的对称概率

Step 8：t-SNE嵌入

T将矩阵恢复顺序后用KL散度优化式计算t-SNE

协议分析

安全性

在整个过程中有两个隐私敏感数据项：原始数据和距离矩阵，有了全距离矩阵，人们可以很容易地恢复原始数据，因此需要保证没有任何参与者可以得到两个数据项中的任何一个

首先对于参与者P，其只有自己的局部数据和分布的嵌入结果，从t-SNE嵌入恢复精确的成对距离是非常不切实际的

协作者S有公钥PK，私钥SK，以及噪声加密数据和重排列的距离矩阵，因为噪声仅T执有，所以S既不能恢复原始数据，也不能恢复距离矩阵

T只有加密的数据和加密的距离矩阵，没有私钥无法恢复成对隐私敏感的数据项

所以总的来说协议可以保证数据的安全性

准确性

嵌入结果与标准的t-SNE算法完全一致

SMAP系统

架构与实现

S和T属于两个不同的没有共谋的信誉实体，由服务器组织，S和T彼此连接，并发送加密或噪声数据给对方。参与者按照安全多方协议连接到两个协作者。S向它们广播公钥。它们将加密的数据发送给T，并从T接收可视化结果。在每个参与者中都安装了一个客户端交互界面，用于任务管理和可视化结果的探索。

SMAP是一个基于web的系统，前端用JavaScript和D3.js实现，后端用python实现，采用基于python的库来进行部分同态加密，并开发了一个多线程实现

参与者用户界面

如图所示，在任务列表面板(a)中，参与者可以浏览在线任务，加入一个准备任务，并提出一个新的任务，在列表中选择一个任务之后，任务描述面板(b)显示任务信息，，例如数据的内容和参与者，对于参与的任务，参与者可以直接切换到”我参与的任务”选项卡，其中显示了所有协作者和参与者的详细信息，包括他们的角色，IP地址，状态和贡献的数据点，此面板还支持任务操作，包括数据加密和上传

全局投影试图(c)显示了来自所有参与者的数据的嵌入结果，在单个投影试图(d)中，根据全局嵌入，只显示所选参与者的数据，为了满足隐私保护的需求，本文提供了两种可视化策略，当参与者想知道点集关系的时候，结果会议散点图的形式呈现，其中颜色编码了数据所有权或者数据类，在散点图模式下，参与者可以自由活动，由于参与者只能访问原始的本地数据，只能通过选择附近的本地数据来推断他人数据的高维表示。当参与者涉及到点级隐私性的时候，聚合的可视化被提供来显示联合嵌入结果

案例研究

三个案例

  1. 模拟了一个数据市场场景，其中数据消费者(M)购买数据来改进他自己的小数据集，邀请了一个机器学习专家来作为消费者M，每个零售商提供3000个数据点，消费者只有1000个数据点(专家操作过程和建议详见论文)
  2. 分散学习场景，解决non-IID issue，五个包含800个数据点的不同子集分别被分配给五个具有机器学习研究背景的硕士研究生
  3. 将SMAP部署到三个社区医院，以进行安全的多方可视化分析，为了防止两个协作者之间的共谋，作者团队作为协作者T来保存加密的数据。合作伙伴由一家外部公司服务，该公司受到所有医院的信任

讨论

  1. 本文的协议可以直接支持PCA，因为它只需要计算协方差矩阵而不是距离矩阵，其敏感信息更少，而应用于UMAP和isomap可能会面临一些挑战，因为这两种方法必须计算k个最近邻之间的距离，这是距离矩阵的子集，无法在Step7进行分数约简来保护距离矩阵，需要更多研究来评估这个子集的风险

  2. 在不同的场景中组织安全的协同视觉分析将是一项有趣的未来工作

  3. 安全多方可视化方案耗时较长，关键部分是数据加密、解密和对加密数据的算术运算

  4. 点数增加，散点图中不可避免地会出现重叠，影响了基于散点图的嵌入结果分析，入识别离群值等，文章中的处理方法是以随机顺序呈现数据点，未来可以采取更多的解决方案，比如可以透明底呈现数据点，也可以采用离群值检测算法来检测并突出检测到的离群值

未来工作

  1. 加速安全的多方预测
  2. 通过联合嵌入实现的安全协作分析
  3. 其它数据类型的安全多方可视化