type
status
date
slug
summary
tags
category
icon
password
SPG: Structure-Private Graph Database via SqueezePIR阅读记录-VLDB2023
基本信息
SPG: Structure-Private Graph Database via SqueezePIR
作者：Ling Liang
期刊 & 会议： International Conference on Very Large Data Bases（VLDB）
时间：2023
JCR/CCF：CCF-A
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
研究对象
密码技术 & 应用场景
- 图数据库 & 隐私信息检索 & 图神经网络
研究动机
潜在问题
- 大数据时代的到来驱使着社交网络、金融贸易等领域的快速发展，图数据数量大规模增长使得本地存储成为问题。因此，需要将图数据外包至云服务器存储。然而，外包存储会存在隐私泄露问题。恶意服务器可以窃取外包图数据中所包含的隐私信息。
- 为解决外包数据隐私泄露问题，客户端可以对图数据加密并上传至云服务器存储，随后通过多设备并行检索云服务器拥有的图数据库并解密获得最终的检索结果。然而，这种方法虽然可以保证数据内容的机密性，但是图数据结构仍然会被泄露。
研究目标&贡献
主要贡献
- 提出了一个框架SPG，通过使用隐私信息检索（PIR）技术实现对图数据库的结构信息的保护
- 提出了一个方法SqueezePIR，实现对PIR检索过程的加速，以降低开销，达到提高效率的目标
- 基于SEAL库实现了所提的SPG以及SqueezePIR，并通过多个图神经网络模型来评估，实验结果表明与FastPIR相比，平均加速11.85倍，精度损失不到2%。
研究基础
图数据存储格式 & 图神经网络
图表示：一个简单的无向图如图1中的(a)所示
- 节点表示：图的节点表示实体或对象的基本单位。每个节点都有一个特征向量，描述节点的属性信息。这些特征可以是节点的数值属性，类别标签，或者节点在图中的位置等。如图1中的(c)所示，无向图中每个节点都有着自己的特征向量。
- 边表示：图的边表示节点之间的关系或连接。边可以是有向的或无向的，权重可以表示连接的强度。除了权重信息外，边也可以携带其他的属性信息，例如时间戳、相似度等。如图1中的(b)所示，无向图的边列表
压缩稀疏行格式（Compressed Sparse Row，CSR）
- 压缩稀疏行格式是一种以节省内存的方式存储稀疏矩阵的方法。它使用三个数组：值数组、行偏移数组和列索引数组来表示一个有图生成的稀疏矩阵。
- 值数组：按行开始，依次存储每一行的非零元素，其长度为稀疏矩阵中非0（非特定元素）数据的个数。对于无向图，通常不需要值数组，因为边的存在本身已经能够表示图的结构。如果图中的边有权重，则值数组保存了每个边的权重值。
- 行偏移数组：行偏移数组保存了每个节点对应的邻接节点在列索引数组中的起始位置。
- 列索引数组：列索引数组保存了每个节点的所有邻接节点的索引。
- 以图1中的无向图为例，解释CSR存储方法，图(a)对应的稀疏矩阵如下
- 列索引数组：
- 第一行：[3,4]；第二行：[2]；第三行：[3,4]；第四行：[0,2]；第五行：[0,2]
- 列索引数组：[3,4|,2|3,4|,0,2|,0,2]，对应着图(b)中的第二列
- 行偏移数组：
- [0,2,3,5,7]，对应着图(b)中的第三列
图神经网络
图神经网络的目标是在图结构数据中学习和推理节点之间的关系和属性，以解决各种任务，如节点分类、图分类、链接预测等。其核心思想主要包括聚合以及更新两个方法
- 聚合
- 消息传递（Message Passing）：每个节点会将自身的特征信息与其邻居节点的特征信息相结合，生成一个消息，这个消息通常是对邻居节点特征的某种汇总或转换。这个过程可以基于节点的邻接关系和特征来进行，不同的方法可能有不同的消息传递策略。
- 特征聚合（Feature Aggregation）：接收到消息的节点会对这些消息进行聚合，以更新自身的表示。这个过程可以是简单的加权平均、拼接，或者更复杂的操作，如注意力机制，它可以帮助节点更好地利用来自不同邻居节点的信息。
其中， 是节点 接收到的消息， 是节点 的邻居节点集合， 是邻居节点 的特征表示。
- 更新
- 特征更新（Feature Updating）：节点完成了聚合过程后，使用得到的聚合信息来更新自身的表示。这个更新通常是通过应用一个神经网络层或者其他变换函数来实现的。这个神经网络层会接收节点的当前特征表示和聚合后的信息，然后生成一个新的特征表示，以更新节点的状态。
- 迭代更新（Iterative Updating）：在许多图神经网络中，这个聚合和更新的过程是迭代进行的，即节点会多次执行消息传递、聚合和更新操作，直到达到一定的迭代次数或者收敛条件。这样的迭代更新可以使得节点表示更好地捕捉图中的结构信息和节点之间的关系。
其中， 表示将节点 的当前特征表示 和节点 接收到的消息 进行拼接， 和 是神经网络层的参数， 是激活函数。
FastPIR-SimplePIR
该方法是通过同态加密的乘法操作、旋转操作实现快速隐私信息检索，发表在USENIX 2023 《One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval》，方法核心思想如下图所示，具体内容见文章
低秩矩阵近似（Low-rank ）
- 特征值与特征向量（对角化分解）
- 给定一个任意维方阵，其对角化分解就是，其中的每一列都是一个特征向量，是一个仅对角线元素非零（从大到小排列的特征值）的矩阵。
- 求解特征值与特征向量的方法如下
- 特征值和特征向量的意义
- 特征向量：矢量，代表着一个矩阵在线性空间变换的多个方向
- 特征值：一个标量，代表着矩阵在每个线性空间变换方向的速度
- 如果将矩阵在线性空间变换理解为位移，那么特征向量就是在该线性空间的多维位移方向，而特征值就是在这些多维位移方向的位移速度。特征向量就是不变子空间，无论矩阵所做的线性变换是什么样子的，特征向量不会变化，只会是在原本方向上面进行伸缩变换，伸缩变换的具体长度就是特征值。
- 对称对角化分解
- 一种特殊情况，即当矩阵是一个对称方阵时，存在一个对称的对角化分解，即，其中的每一列都是相互正交的特征向量，且为单位向量，是一个仅对角线元素非零（从大到小排列的特征值）的矩阵。
- 奇异值分解
- 给定一个矩阵，那么是一个维对称方阵，是一个维对称方阵。因此可以对其进行对称对角化分解得到，则矩阵的奇异分解为，其中是左奇异向量,是右奇异向量,同样是一个对角线元素非零的矩阵且对角线元素即为奇异值（奇异值大小为特征值的平方根且非负）.
研究内容
SPG流程图
- 完全可信的客户端（client）例如一些企业、公司，其想通过收集图结构数据完成一些图神经网络模型训练任务，以达到某些目标。然而，由于图结构数据通常多且复杂，其本地存储能力不够存储所有的图结构数据，因此需要将图数据外包至云服务器存储。随后为从云服务器获取这些数据，其需要一些设备（devices）通过隐私信息检索方法在不泄露图结构数据隐私的情况下获取数据，用于图神经网络模型训练。
系统模型&安全模型
- 客户端：完全可信，其主要功能有：1）从设备（devices）中收集更新的节点特征；2）对节点特征进行低秩近似压缩；3）发送加密的变列表以及节点特征至云服务器存储。
- 服务器：半诚实，即诚实执行协议内容，但是会试图获取图数据库中的边列表以及节点特征。其主要功能有：1）存储来自client的边列表和节点特征密文；2）与devices进行PIR协议交互
- 设备：完全可信，其主要功能有：1）发送新的节点特征给client；2）与服务器交互执行PIR协议获取图结构数据信息；3）使用获取的图数据信息使用GNN模型完成推断任务。
SimplePIR的检索结果
从下面这个检索结果来说，相比较于使用SimplePIR检索边列表数据，当前最快的隐私信息检索PIR方法在图结构数据的节点特征检索方面存在着严重的效率低下问题，为此主要针对这一问题开展后续研究。
SqueezePIR协议
- 协议总体预览
SqueezePIR协议解析
- 图结构数据库压缩：完全可信的客户端完成这一操作。例如，在SqueezePIR协议总体图中，给一个的图结构数据库，首先客户端将数据库划分为两个 的子数据库（这样的好处是后续有新的节点特征要存入当前数据库，只需要把这些新数据也按照进行组合存储即可，并且不会对之前的数据有任何影响）。其次，客户端将每个的子数据库进行SVD分解为两个矩阵的乘积，随后按照预定义的低秩近似值来对SVD后的两个子数据库压缩。（在图中就是选择秩为2，即只选择矩阵的前两列和的前两行）。最后，客户端加密选择的和
- 问询生成：每个设备（device）生成自己的问询向量密文，如下算法所示。是一个L长的one-hot向量，其仅在检索位置为1，其他为0（就对应着总体图里面那个问询向量长度-4）
- 问询结果生成：首先服务器需要将问询向量密文以及图数据库低秩近似后的左奇异矩阵密文按位相乘，随后是两个矩阵密文相乘，最后将每个密文问询向量的计算结果进行叠加，获得最终的问询结果密文返回给device，device再解密获得明文检索结果，即明文的近似节点特征（低秩近似导致的，当然只要低秩值选的合适，对图神经网络模型准确率而言影响并不大）
In-Place Query Mapping方法
问询结果生成方法存在的弊端
- 的生成需要非方阵的密文矩阵乘法，这对于同态加密而言开销非常大，因为不仅需要数据重构（rotation）以及会需要额外的中间数据密文
- 矩阵中并不是每一维都是需要的，只有在检索的那行才拥有图结构数据，其他位置所对应的明文都是零，这也是SimplePIR致力于解决的问题
In-Place Query Mapping方法（所有操作都是服务器执行的）
- 问询扩展：假设问询位置为，分组长度为，将进行递归扩展，包含问询位置的问询向量由原本的one-hot向量密文变为全1向量密文，对于其他的问询向量仍然是全0保持不变。
- 问询映射：分别计算MA-U和MA-V，对于MA-U，计算原始问询向量与低秩近似左奇异矩阵的同态乘法与同态加法，即。对于MA-V，计算扩展问询向量与低秩近似右奇异矩阵的同态乘法与同态加法，即
- MA-U扩展：通过同态旋转（rotation）操作扩展MA-U，获得EXP-U，如总体图所示。
- 问询结果生成：计算即可获得问询结果的密文。
递归向量扩展（Recursive Vector Expanding）
通过递归地对一个密文向量进行密文旋转（rotation）和同态加法（addition）操作以获得一个扩展后的密文
研究结果
复杂性对比分析
- 由于使用了SVD的低秩近似方法，所以可以将原本数据库存储大小降低至。对于SimplePIR未对数据库做任何处理，因此对于一个维的数据库，需要花费的内存。对于SqueezePIR，假设低秩值为，对于划分为个的数据块，对于每个数据块进行SVD的低秩近似后结果为两个矩阵和 ，所以每个数据块需要内存，所以一共需要内存。
- 同态乘法操作主要集中在总体图的步骤和
- 同态旋转操作主要集中在总体图的步骤和
实验设置
- 使用BFV与SimplePIR实现边列表隐私信息检索，明文大小设置为16比特，密文大小设置为109比特
- 使用CKKS与SqueezePIR实现节点特征隐私信息检索，明文多项式次数设置为8192，密文多项式次数设置为4096，扩张因子设置为
- 编程语言：C++ & SEAL库
- 不同数据库节点、特征以及边的设置情况
实验结果（虽然这些图不重要，但是为了完整还是写上了，实验部分重要的地方在于源码）
- 不同密文多项式次数与不同低秩近似值，SVD和SqueezePIR的效率对比
- 不同PIR协议的检索时间对比
- 固定数据库大小为，在不同低秩近似值下对比SqueezePIR协议的检索时间
- 固定低秩近似值为256，在不同数据库大小下对比SqueezePIR协议的检索时间
- 不同低秩近似值以及不同数据库大小下对比SqueezePIR协议的检索时间
- 在现实图数据库上面对于一个节点邻接边集合以及特征集合的使用SqueezePIR和SimplePIR检索时间对比
- 不同现实数据库上，对于一个节点特征使用SimplePIR和SqueezePIR检索时间对比
- 在不同低秩近似值下压缩后的不同图结构数据库上面图神经网络模型的准确率（低秩近似后数据必然与真实数据有着误差，可能会给模型带来影响，所以需要做这样的一个准确率的评估，否则如果准确率很低，那么再怎么节省存储开销和计算开销来检索数据都没有任何意义）
总结与展望
缺陷
- 在SqueezePIR协议中，为防止服务器获取设备（devices）检索的具体数据信息，服务器需要对所有的问询向量都进行同态rotation操作，并且对所有的低秩左奇异矩阵都要进行递归rotation。（这个似乎无法避免）
- 服务器是半可信的，并且仅仅具备试图尝试获取设备检索的具体是那条数据有关信息，未考虑更强能力的服务器。
- 对于问询向量密文的递归rotation扩展是否可以不让服务器去完成，而是设备自己去完成？即设备发送两个问询向量（这个问询向量扩展是可以避免的）
- 这个问询向量扩展似乎没有必要吧，就用原本的问询向量先与左奇异向量相乘，再递归rotation，得到Exp-U，最后再将Exp-U与MA-V同态乘不就行了？感觉就用SimplePIR那个递归rotation方法就可以完成所谓的In-Place Query Mapping方法。
- SPG中设备devices需要是完全可信，如果考虑他们具备一些恶意攻击的能力，会出现什么结果
- 首先在SPG中，使用相同的公私钥对，所以每个设备都可以获取其他人的检索的具体信息是什么（这并不是问题，因为你也可以自己去跟服务器交互并获得其他设备检索到的xi）？？？（不确定）
参考文献
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~ 🍊