摘要

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

论文地址：

http://cjc.ict.ac.cn/online/onlinepaper/002-%E5%88%98%E5%AE%87%E6%B6%B5-H-2022425163952.pdf

引言

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

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

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

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

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

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

内容中包含的图片若涉及版权问题，请及时与我们联系删除