图数据上的隐私攻击与防御技术

摘要

如今，图数据已经被广泛地应用于现实生活与科学研究当中，有巨大的使用和研究价值. 但与此同时，针 对图数据的收集与发布中也存在巨大的隐私风险 . 如何在保护图隐私的同时，发布与收集可用图数据，是目前个 人、企业、政府等面临的重大挑战. 本文首先从隐私信息所包含的内容、不同的隐私泄露场景，以及敌手模型三个方 面深入地剖析了图数据在使用中存在的隐私风险，然后重点从攻击和防御两个角度展开介绍. 针对攻击而言，本文分析了当前可行的图数据隐私攻击与攻击量化算法及其算法原理. 针对防御而言，本文总结了简单匿名、图修改、 聚类，以及差分隐私四种图数据隐私防御技术；分析了集中与分布两种数据存储场景下，不同类型图数据使用的各 类隐私防御算法，以及数据隐私性与可用性度量方法. 最后本文综合已有的研究成果，指出了图数据上隐私保护研 究当前存在的问题、面临的挑战,及未来的研究方向.

引言

图数据目前已被广泛应用于生活中的各个领 域 . 相较于列表等其他数据类型，图数据具有更强 的表达能力：除通过结点表征实体属性信息外，还可 以通过边清晰地表达结点实体间的链接关系，因此 被普遍应用于现实生活与科学研究中［1］ . 典型的图 数据包括社交网络、通讯网络、移动轨迹、传染病与 医疗数据、合作网络、引用网络、交易信息网络、自治 系统数据及其他拓扑图等，被政府、科研机构及企业 应用于犯罪分子行为模式挖掘、疾病传播研究、推荐 系统等政府数据挖掘、学术研究与商业应用当中.

然而图数据中蕴含大量的敏感信息，一旦泄露， 造成的后果极为严重 . 除如社交网络中的个人资 料、医疗数据中的诊疗记录、交易信息网络中的交易 内容等图结点上的敏感文本属性外，图数据中还包 含社会关系、医患关系、交易方式等边上的敏感链接 关系. 因此图数据的隐私泄露事件往往涉及人数众 多、影响广泛 . 2018 年，社交网络 Facebook 超过 5000万用户个人信息遭到泄露，除个人资料等用户 结点属性信息外，还包括好友资料、点赞与转发情况 等用户结点间的关联关系 . 数据公司通过分析用户 间的关联关系，准确推测出了用户的受教育情况、政 治倾向、性取向，甚至是用户儿童时期受过的创伤， 从而精准投放引导性信息，以达到左右用户行为的 目的 . 此外，数据分析者还利用用户的好友列表，进 一步扩大影响范围 . 最终，该隐私泄露事件累计波 及到了 8700 万用户 . Facebook 也因此信誉受损、市 值下跌，并面临累计超过16亿美元的罚款.

可见，图数据在收集与发布等使用过程中面临 着巨大的隐私风险 . 攻击者可以结合各种背景知识 对图数据发起隐私攻击 . 在图的集中式存储场景 下，攻击者可借助公开的人口统计数据、个体语义属性信息、个体所在图的局部结构信息、公开数据集、 网络爬虫爬取的图数据等辅助信息，对匿名图发起 结点实体身份再识别攻击，并进一步推断实体的语 义属性、链接关系等隐私信息 . 在图的分布式存储 场景下，不可信的数据收集者可以在数据收集过程 中直接窃取用户的隐私数据 . 即便只发布或收集与 原始图相关的统计信息或随机图模型参数等，图数 据的隐私安全依然会遭到威胁 . 一则，发布的统计 数据本身可能是敏感信息 . 二则，攻击者可以通过 发布的数据以较高的准确度还原原始图，或者综合 利用各类统计数据对原始图进行隐私推断.

综上所述，对图数据隐私保护技术的研究迫在 眉睫 . 然而图数据蕴含信息丰富，实体间关联关系 复杂，给其上的隐私保护带来了严峻的挑战 . 首先， 图数据上信息的多样性增大了隐私定义的难度 . 图 数据中结点所代表的实体身份、语义属性、结点所在 的子图结构、结点本身在图中的存在性，以及图中边 上的语义属性、边的存在性，都可能是需要保护的敏 感信息. 如何选择并综合各类敏感信息进行合理的 隐私定义，是图数据隐私保护上的一个难点 . 其次， 图数据中结点之间复杂的关联关系增大了隐私保护 技术设计与应用的难度 . 同一个结点可能与大量其 它结点存在各种不同的链接关系，并且结点上的语 义信息与结点所在子图的结构特征也存在一定的关 联，对图中任何一个结点、一条边或一条语义信息稍 做更改，都可能牵一发而动全身，大大降低图数据整 体的可用性 . 因此，如何在充分保护用户隐私的前 提下，同时保障图数据的高可用性是研究者关注的 焦点.

针对关系型数据的传统隐私保护技术无法满足 图数据发布与收集的隐私需求. 传统的k-匿名技术、 l-多样性技术、t-接近技术等虽然可以直接应用于图 数据发布时，结点上语义信息的保护，但是无法同时 保护结点间特殊的链接关系，以及结点所在的特殊子 图结构等隐私信息.而传统的差分隐私技术直接应用 于图数据的发布与收集时，相关函数敏感度较高，会 导致添加的噪声过大，数据可用性急剧下降.此外，若 直接用传统的差分隐私技术对结点上的语义信息、结 点存在性、边上的语义信息与边存在性等进行全面的 隐私保护，不仅会引起添加噪声过大问题，而且会破 坏图数据上信息之间的一致性，降低数据可用性. 因 此，为满足图数据上隐私保护的需求，需要在传统隐 私保护技术的基础上结合图数据的特点、针对图数据 上隐私保护的难点来进行创新.

本文第2节从图数据隐私信息、泄露场景、与敌 手模型三个方面综合分析了图数据在收集与发布中 面临的隐私风险 . 第 3 节分析了目前在图数据模型 上各类攻击算法及其量化方法，对攻击者的能力进 行直观地说明. 第4节介绍了图数据中简单匿名、图 修改、聚类，及差分隐私四种主流隐私保护技术，并 梳理了针对不同应用场景与数据类型的隐私防御算 法 . 同时介绍了图数据隐私性与可用性度量及二者 关系 . 第 5 节总结了当前图数据隐私保护中仍然存 在的问题，并展望了未来可能的研究方向与挑战 . 第6节总结全文.

2 隐私风险

隐私风险指的是在图发布与收集的过程中可能 面临来自多种攻击者、对不同的攻击对象发起的各 类攻击，从而导致图中的敏感信息泄露 . 本节将从 隐私信息、隐私泄露场景、敌手模型三个方面，评估 在图收集发布的过程中所面临的隐私风险。

2.1 隐私信息

隐私信息是图中可能泄露的各类敏感信息 . 文 献［3］从结构上将图上的隐私信息主要分为结点上 的隐私信息与边上的隐私信息两大类 . 而本文则根 据文献［2］，从内容的角度将图上的隐私信息分为 身份信息、语义属性与链接关系三大类，并丰富了定 义内涵.

身份信息指图数据中结点与结点所代表实体身 份的一一对应关系，如：社交网络中结点所代表用户 的用户姓名、用户 ID 等身份标识符 . 除结点与实体 的对应关系外，在传染病传播图等数据中，结点本身 在图中的存在性也是一个敏感信息.

语义属性指结点中除身份信息外其他可能泄露 隐私的属性信息，通常包括敏感属性信息，如邮件通 讯网络中与用户结点关联的邮件内容；或一组可以 唯一确定结点身份的非敏感属性集合，即准标识符， 如职业社交网络中用户结点的职业、性别、年龄、所 在地邮编等. 链接关系指结点所代表实体之间的关联关系， 在图中用边表示 .

链接关系上的隐私信息包括边上 的权重，如商业网络中两个实体间的交易额；边上的 属性，如社交网络中两个实体间的朋友、亲友、医患 关系等；边的存在性，如在通讯图中结点所代表的实 体间是否存在短信或电话往来等.

2.2 隐私泄露场景

隐私泄露场景是图数据发布与收集中可能泄露 隐私的环节，主要包括图的集中式存储与图的分布 式存储两种场景. 图1为隐私泄露场景示意图. 下面 分别介绍两种场景下图数据面临的隐私问题.

2. 3 敌手模型

敌手模型通过敌手能力、敌手知识，以及敌手目 标三个方面，全面刻画攻击者的特征 . 充分了解敌 手模型，做到知己知彼，可以为图数据隐私防御方法 的研究提供指导依据.

3 隐私攻击

3. 1 攻击算法

在图的分布式存储场景下，当隐私泄露方式为 直接泄露时，攻击者无需复杂的攻击算法；而当攻击 者试图对用户进行暴力入侵时，通常采用中间人攻 击等信息安全领域的攻击方法，不在本文的讨论范 畴内 . 因此本节将主要介绍图的集中式存储场景下 的隐私攻击算法. 目前，图的集中式存储场景下的攻击算法可分为 两大类，基于种子结点（seed-based）的攻击算法以 及非种子结点（seed-free）攻击算法. 本文进一步将 基于种子结点的攻击算法分为基于种子结点的主动 攻击算法与被动攻击算法两个子类 . 此外，不同于 ［1，14］等文献按照时间顺序介绍相关算法细节，本 文首次提炼各类图隐私攻击面临的关键问题，明晰攻 击算法整体的发展脉络.下文围绕算法目标、针对的关 键问题，以及相应的解决方案，描述经典攻击算法.

3. 2 攻击量化

除从实践上证明算法的可行性外，还有一系列 的研究致力于从理论上给出匿名图可以被攻破的条 件，以及不同背景知识对去匿名化的影响 . 不同于 ［1，14］等文献，本文除量化算法所基于的随机图模 型外，还着重分析了各个经典量化算法针对的不同 的去匿名化条件，并在表3中从理论模型假设、攻击 类型，以及量化攻击时考虑的不同条件类型，全面总 结了当前攻击量化研究成果.

4 隐私防御

为抵御上述针对图数据的隐私攻击，研究者结 合不同地隐私防御技术，提出了多种隐私防御的算 法，本节将从图上的隐私防御技术、隐私防御算法， 以及图的隐私性与可用性三方面展开介绍.

4. 1 隐私防御技术

目前，针对图数据发布与收集的隐私防御技术 主要可以分为简单匿名技术、图修改技术、聚类技术 以及差分隐私技术四类 . 下面将依次介绍上述隐私 防御技术及其实现机制.

4. 2 隐私防御算法

在针对图数据的发布与收集过程中，最直接的方 式是发布或收集原始图的邻居向量或邻接矩阵，因此 部分研究基于原始图的拓扑结构、邻接矩阵或邻居向 量设计隐私保护方案. 然而原始图的拓扑结构复杂， 邻接矩阵维度较高，在算法设计与实现过程中存在算 法时间复杂度高、噪声添加大等困难. 因此除原始图 外，还有研究针对图上的统计特征、随机图模型参数， 以及合成图的收集与发布进行隐私保护. 相比于以隐私技术为依据的传统分类方式［1，14，］ 本文从实际应用的角度出发，分别介绍在集中式与分 布式数据存储场景下，针对以上四种图上数据类型的 隐私防御算法. 同时，本文首次提炼出各类隐私防御 算法面临的关键问题，并围绕算法的防御目标、采用 的防御技术，以及算法针对的关键问题及其解决方 案，对相关算法进行描述，明晰各类算法发展脉络.

5 挑战与展望

随着人们对个人隐私的逐步重视，各类新政 策的出台，个人隐私保护需求与高质量服务需求 之间的矛盾被持续激化，使得对图数据的隐私风 险评估与隐私性度量、可用性度量、隐私保护技 术、隐私保护算法等的深入研究空前迫切 . 目前， 已经有很多研究致力于解决图上的隐私保护问 题，相关研究已经广泛涉及到了不同场景下的多 种数据类型、隐私保护技术，取得了一定的进展 . 但由于图数据具有蕴含信息丰富、数据之间关联性强、现实中图相对稀疏等特点，现有的研究还不 能满足人们对图数据上隐私保护的需求，当前还 有很多亟待解决的问题，限制了相关研究在现实 应用中的推广与普及。

5. 1 图数据隐私发布与收集中的难点问题

5. 1. 1 隐私性与可用性权衡问题

数据隐私性与可用性的权衡问题是隐私保护领 域的一个共性问题 . 如何找到可用性的牺牲与隐私 性保证之间的平衡点是设计隐私保护算法的关键 . 然而，图中隐私信息类型丰富，不同结点之间具有很 强的关联性，给图数据隐私性与可用性的量化与隐 私方案设计带来了更大的挑战 . 首先，对于数据隐 私性而言，虽然针对不同采用不同隐私技术的匿名 图有不同的量化方式，但是缺乏统一的量化标准；对 于数据可用性而言，虽然可以用特定的图性质来度 量，但同样尚且没有简洁统一的量化标准 . 并且，不 论是图数据的隐私性度量还是可用性度量，目前都 很难兼顾图上结点的身份信息、链接关系及属性信 息等多种隐私信息 . 而一旦可以综合量化数据隐私 性与可用性，就可以通过理论分析找到其平衡点，从 而设计更有效的隐私防御方案 . 其次，在具体设计 隐私方案时，不同的隐私信息类型需要采用不同的 隐私保护技术，因此很难兼顾所有的隐私信息；图中 的同一个结点通过边与很多其他结点相连，若对中 心结点进行修改则会极大程度破坏图结构可用性， 而不做修改则很难保障中心结点的结构隐私 . 基于 此，无论是对图数据隐私性与可用性的量化，还是对 于具体的隐私保护方案设计，图数据的隐私性与可 用性权衡都将继续是未来图数据隐私保护的一个严 峻的挑战.

**5. 1. 2 个性化隐私保护 **

图数据在现实生活中图数据有广泛的应用，如 基于社交网络、购买记录等的推荐系统，基于地理 位置的路径规划，以及基于交易记录的欺诈检测等 等 . 在不同类型的网络中对隐私保护强度有不同的 需求 . 而在同一个网络中，同一个实体结点对不同 的隐私信息也有不同的需求 . 以基于社交网络的朋 友推荐为例，社交网络中的不同用户哪些属性为隐 私属性，或者哪些链接关系为隐私链接关系都有不 同的定义 . 还有一些用户不认为自己所在社交网络 中存在隐私信息，反而希望服务提供商利用自己在 社交网络中的信息，为自己提供更精准的好友推 荐、社群推荐或者商品推荐等服务 . 在以往的研究 中，还没有发现能够解决图数据上个性化隐私保护 的可行方案 . 因此，如何针对不同网络中不同实体 的隐私需求，在保护实体隐私的同时，为实体提供 更好的服务是未来图数据隐私保护一个研究趋势.

**5. 1. 3 图数据的动态发布与多次收集 **

在对图的研究中，图的演化是一个重要的研究 方向 . 研究图的演化可以对人的社交行为、疾病的 传播规律等具有更深刻的认识与理解 . 而研究图的 演化，往往需要对同一图数据进行多次收集或者动 态发布 . 一般的隐私防御方案无法保证在多次收集 或者动态发布中数据的隐私安全 . 多次收集及动态 发布时，在保证结点、边及属性隐私安全的同时，还 需要保证同一时间序列下数据的一致性，如：同一时 间序列下相同结点的身份代码要一致；此外发布数 据中边的存在性、图中的语义信息等要符合原始图 的演化规律等 . 隐私防御算法在保证数据的一致性 同时，提高了数据的可用性，但同时也丰富了攻击者 对同一时间序列下的图数据发起攻击时的敌手知 识，进一步增加了防御的难度 . 目前，已经有少量的研究关注该问题，但是鲜有有效的解决方案，因此该 问题是仍然是未来图数据隐私保护上的一个重要探 索方向.

**5. 1. 4 面向主动攻击的隐私防御算法 **

主动攻击者具有很强的攻击能力 . 现实中，主 动攻击者可以通过在社交网络中创建僵尸账号并主 动关联目标用户对用户发起隐私攻击 . 近年来有文 献提出一种具有鲁棒性的主动攻击算法，可以以较 高的准确度一次性对大量结点进行去匿名化攻击 . 该算法的提出，不仅使研究者更深刻认识到主动攻 击者强大的攻击能力，更进一步提高了类似于社交 网络等图中用户的隐私风险 . 然而，目前尚没有攻 击算法可以有效缓解由此类攻击带来的隐私风险 . 因此如何在现有的隐私保护算法上进行提升，或者 改进已有的隐私防御技术，使其能更好的应对具有 主动攻击能力的攻击者是未来隐私保护技术发展一 个可能方向.

**5. 1. 5 隐私放大理论在图隐私保护中的应用 **

近年来，通过深入挖掘各类算法自身特征，有很 多工作提出了一系列的隐私放大理论，从而提升隐 私防御效果 . 上述工作利用算法本身的随机性、下 采样、随机打乱等方式，放大差分隐私预算，以取得 更好的隐私防御效果 . 利用差分隐私进行图的收集 与发布普遍面临噪声添加过大，导致数据可用性降 低等问题 . 若能深入研究图的各类算法自身隐含的 隐私性，或者采用基于混淆模型等的技术放大隐私， 将会极大提升数据收集与发布的质量 . 然而，在图 上应用隐私放大理论面临诸多挑战 . 图上的结点之 间存在关联边，因此不同数据之间不再具有独立性， 无论是给相关方案的设计，还是给理论上的证明都 增加了难度 . 目前，还没有相关工作将隐私放大相 关的理论与技术应用于图隐私保护相关的应用场景 下，该技术的应用可能给未来图上隐私保护技术的 发展带来新的突破.

5. 2 面向新应用场景的图数据隐私保护

**5. 2. 1 面向图数据机器学习中的隐私保护 **

图数据在机器学习领域有着非常广泛的应用， 如基于神经网络的结点分类、链接预测、社群发现， 对异常检测问题，商品及好友推荐问题等提供了巨 大的帮助 . 然而，近年来越来越多的研究发现，机器 学习中存在着巨大的隐私风险 . 攻击者可以通过机 器学习发布的模型参数、预测结果等对训练集发起 重构攻击、成员推断攻击等，导致训练集中数据隐私 泄漏 . 已有的针对图数据的隐私保护算法只能用户 对图数据训练集进行输入扰动，并且此类扰动算法 由于添加的噪声过大，可能严重影响训练模型的可 用性. 而已有的针对机器学习的隐私保护策略，则面 临着针对图训练数据隐私定义难，对关联数据扰动 难等问题 . 因此如何在保证模型可用性的同时提出 可行的隐私保护方法是未来一个可能的探索领域.

**5. 2. 2 隐私保护下的图性质多方共同计算 **

不同于分布式存储场景下的数据收集，在隐私 保护下的图性质多方共同计算中，没有数据收集者， 各方掌握部分子图，及各子图之间公共的边链接状 况，但不了解其他各个参与方所掌握的隐私图内部 结构 . 各方希望借助彼此的信息共同计算完整图中 结点间的最短路径、中心度等信息，实现计算结果共 享，同时不泄露自己所掌握图中的隐私信息 . 借助 密码学技术，如秘密共享或多方安全计算等可以解 决上述问题，但是存在通信开销大、计算开销大等弊 端 . 差分隐私等图隐私保护技术可以缓解开销问 题，但同时也可能面临计算不准确等挑战 . 目前有 少量的工作关注该问题，但仅仅集中在两方的共同 计算上 . 能否将其扩展至多方共同计算，将会是未 来可以探究的新场景.

6 总 结

目前，图数据在现实生活与研究中被广泛的应 用. 与此同时，图数据中也存在极高的隐私风险. 而 图数据上丰富的信息，数据之间关联性强，给图数据 上的隐私保护带来了巨大的挑战 . 本文分析了图的 发布与收集中的隐私风险，综述了目前针对图数据 隐私攻防的各类方案 . 综合二者，本文在最后给出 了目前图数据上隐私保护研究的仍然存在的问题以 及未来可能的研究方向 . 总之，图数据上的隐私保 护研究虽然已经取得了一定的进展，但未来依旧有 很高的研究价值与广阔的研究空间.