HPGA：一种用于个性化图数据匿名化的高效分层算法

《Computers & Security》：HPGA: An efficient hierarchical algorithm for personalized graph data anonymization

　　

**摘要** 图数据因其丰富的结构和语义信息，已成为一种关键资源。匿名化对于防止图数据共享或发布过程中的节点重识别至关重要。不同的用户有不同的隐私需求，这促进了个性化匿名化研究。在实践中，多个数据分析师可能对同一图数据要求不同级别的隐私保护，这需要根据不同的隐私要求重新生成匿名化图。现有的个性化匿名化方法在支持多样化、特定场景的需求时，计算开销巨大。为了解决这种低效问题，我们制定了一个个性化 $k^2$-匿名性模型，以保护节点度和属性信息。然后，我们设计了一种分层个性化图匿名化（HPGA）算法，以在不同隐私要求下高效生成多场景匿名化图。HPGA 构建了一个可重用的分层结构，并整合了一种高效的隐私需求匹配机制用于匿名化。它应用边修改和属性泛化策略来生成匿名化图。在真实世界数据集上的实验结果表明，与现有方法相比，HPGA 显著减少了 99% 的计算时间。此外，HPGA 保持了良好的数据效用。

**引言** 如今，随着大数据的爆炸式增长，许多领域的数据（Hay et al., 2008, Wang et al., 2023, Dong et al., 2023）——如社交网络、推荐系统和物联网（IoT）——通常以图结构表示（Bhagat et al., 2009）。在图数据中，节点表示实体，边表示它们之间的关系（Tabassum et al., 2018）。然而，随着图数据的共享或发布，存储在图数据中的敏感信息面临着各种恶意攻击的风险（Yuan et al., 2010）。因此，隐私保护技术对于防止敏感信息泄露至关重要。匿名化被认为是最流行的隐私保护方法之一，用于缓解此类隐私风险（El Emam and Dankar, 2008, Ji et al., 2016）。

过去几十年，研究人员探索了各种图匿名化机制（Zhou and Pei, 2008, Jiao et al., 2014, Ren et al., 2022）。大多数提出的方法专注于通过基于聚类的方法（Hay et al., 2008）或图编辑方法（Zhou and Pei, 2008, Zou et al., 2009）来扰动原始图结构，使得匿名化图满足既定的隐私模型（Zhang et al., 2017, Yuan et al., 2010），例如 $k$-度（Liu and Terzi, 2008）。$k$-度模型要求每个节点至少与 $k-1$ 个其他节点无法区分。还提出了额外的隐私模型来保护更复杂的隐私，包括节点标签（Yuan et al., 2013）、边关系（Cormode et al., 2008）和邻域结构（Cheng et al., 2010）等。

不同的节点可能有不同的隐私偏好。向所有节点提供统一的隐私保护级别可能是不公平的（Yuan et al., 2010）。为了解决这种异质性，研究人员提出了个性化图匿名化，允许用户指定他们的隐私需求。大多数个性化匿名化研究将隐私偏好分为几个级别。Lan 等人（2011）将实体分为敏感和非敏感，并提出了一种 $k$-邻域方法来匿名化图。Jiao 等人（2014）将隐私需求定义为 H（高）、M（中）和 L（低），并开发了一种个性化 $k$-度-$l$-多样性模型。然而，很少有个性化匿名化工作关注每个节点都有自己的隐私需求值的场景。Mehrabiun 和 Omoomi（2023）提出了一种算法 MDPLS 来保护节点度，允许个人指定他们自己的匿名化隐私级别。但这种方法忽略了节点属性保护。Hoang 等人（2023）的近期工作通过引入一种个性化基于聚类的知识图匿名化算法（PCKGA）解决了这一限制。他们的方法不仅允许用户设置隐私级别，还成功保护了知识图的节点属性和度的隐私。PCKGA 使用一种距离度量，即属性和度信息损失距离（ADM），作为聚类标准以最小化信息损失。这需要预先计算节点对之间的 ADM 距离矩阵，并在匿名化期间执行需求感知聚类。尽管他们的方法在保护节点属性和度的同时保持了较高的数据效用，但这些增强带来了显著的计算成本，复杂度为 $O(cn^2 \log n)$，其中 $n$ 表示节点数量，$c$ 表示聚类数量。

在现实场景中，多个数据分析师对同一数据感兴趣，他们在访问数据时具有不同的信任级别（Pujol et al., 2020, Zhang and He, 2023）。同一图中的节点由于敏感性不同，往往表现出不同的隐私需求。在这种情况下，反复使用 Hoang 等人的方法进行匿名化会产生显著的计算开销，特别是对于大规模图。因此，在不同场景中，在支持保护节点度和属性信息的个性化隐私需求的同时保持数据效用仍然具有挑战性。据我们所知，目前尚无现有工作解决在不同隐私要求下高效产生多个匿名化发布版本的挑战。

为了克服重复图匿名化的低效，我们提出了一种策略：不是为每个新的隐私需求反复处理原始图，而是预先构建一个封装了多个隐私级别的可重用结构。我们不再将匿名化视为一次性操作，而是探索构建一种统一表示的可能性，以支持多个隐私粒度级别。基于这一概念，我们制定了一个个性化 $k^2$-匿名性模型作为隐私保证，以保护节点度和属性。然后，我们设计了一种分层个性化图匿名化（HPGA）算法，该算法能够高效生成满足不同个性化隐私需求的多个匿名化图。HPGA 分为三个步骤运行：分层结构生成、隐私需求匹配和匿名化图生成。

在分层结构生成期间，HPGA 改进了 Hoang 等人（2023）的距离度量，基于度和属性差异量化节点对相似度。此距离度量指导聚类过程构建一个分层结构，其中每一层对应于一个满足预定大小阈值的图聚类结果。分层结构封装了节点的多个聚类粒度，且每一层相互独立。在隐私需求匹配阶段，给定一个个性化隐私需求，HPGA 高效地将该个性化隐私需求映射到分层结构中，并导出适当的聚类结果。与 Hoang 等人的 PCKGA 方法相比，HPGA 避免了为每个新的隐私配置从零开始重复聚类，从而减少了冗余计算。最后，匿名化图生成阶段应用边的添加/删除和属性泛化来生成匿名化图。

我们在三个真实世界数据集上评估 HPGA 的性能，并将其与两种最先进的个性化匿名化算法进行比较：MDPLS (Mehrabiun and Omoomi, 2023) 和 PCKGA (Hoang et al., 2023)。效率实验表明，HPGA 比 PCKGA 处理速度快 99%，在与 MDPLS 进行隐私需求匹配时的执行时间相似。包括分层结构生成在内，HPGA 在 Hamster (Kunegis, 2013)、ArnetMiner (Tang et al., 2008) 和 Cora (?ubelj and Bajec, 2013) 数据集上分别比 PCKGA 提高了 30%、25% 和 50% 的效率。在效用实验中，HPGA 通过边添加/删除和属性泛化产生的平均信息损失略高于 PCKGA；然而，两种算法都保持了较高的数据效用。特别是，在所有数据集上，HPGA 和 PCKGA 比 MDPLS 表现出的信息损失低 5%–95%。我们进一步进行下游节点分类实验以评估图分析效用。结果显示，HPGA 在匿名化后保持了可比的分类性能：原始图达到 53.46% 准确率和 64.45% F1 分数，而 HPGA 在不同隐私设置下达到 52.37%–52.99% 准确率和 63.75%–68.92% F1 分数。

本文的主要贡献总结如下：
1. 我们引入了多场景个性化属性图匿名化问题，其中从同一原始图生成多个匿名化发布版本，满足不同节点级隐私需求。然后，我们为无向属性图制定了一个个性化 $k^2$-匿名性模型，以保护节点度和属性。
2. 我们开发了分层个性化图匿名化（HPGA）算法。HPGA 构建了一个为最小信息损失优化的可重用分层结构，并整合了一种高效的隐私需求匹配机制用于按需匿名化。最终的匿名化图通过边修改和属性泛化生成。
3. 我们在真实世界数据集上进行实验，证明 HPGA 在效率上优于现有方法，同时保持了较高的数据效用。

**章节片段**

**相关工作** 近年来，用于隐私保护数据发布的匿名化引起了显著的研究关注。开创性工作首先引入了 $k$-匿名性（Samarati, 2001）来保护关系数据，随后启发了对图数据的许多扩展（Ji et al., 2016）。由于其固有的结构复杂性，与关系数据相比，图匿名化提出了独特的挑战。除了属性保护外，图匿名化还必须保持拓扑特征，

**预备知识** 在本节中，我们呈现研究中使用的图、对手知识和个性化隐私模型的定义。我们还正式定义了我们工作旨在解决的问题。这些基本概念为设计所提出的匿名化算法提供了理论基础。

**我们的方法** 在本节中，我们提出分层个性化图匿名化（HPGA）算法，以解决多场景个性化图匿名化问题。我们详细介绍了 HPGA 的每个组成部分。此外，我们从安全性、时间复杂度和可扩展性方面对该算法进行了分析。

**实验评估** 在本节中，我们呈现实验细节。我们首先介绍数据集、参数设置、对比算法和度量指标。然后，我们展示并分析实验结果。

**讨论** 虽然我们的算法在多场景个性化匿名化方面显示出显著优势，但我们认识到几个需要深入分析的考虑因素。在本节中，我们讨论这些方面。

**扩展到更强的隐私模型。** 我们的算法的隐私保证基于个性化 $k^2$-匿名性模型，该模型提供了针对身份泄露的健壮保护。然而，我们识别出一个潜在漏洞：在某些条件下，对手可能

**结论** 在本文中，我们提出了一种新型个性化匿名化算法 HPGA，以解决在不同隐私要求下高效生成多个匿名化图的挑战。我们的方法建立了一个可重用的分层结构，并引入了一种隐私需求匹配算法，在支持多样化个性化隐私级别的同时显著减少了计算开销。为了同时保护结构和属性信息，我们提出了

**CRediT 作者贡献声明** 袁玉林：写作 – 审阅与编辑，写作 – 初稿，验证，资源，方法论，调查，形式化分析，概念化。袁曙光：写作 – 审阅与编辑。余静：资金获取。陈驰：写作 – 审阅与编辑。

**利益冲突声明** 作者声明他们没有已知的竞争性财务利益或个人关系，这些利益或关系可能影响本文报告的工作。

**致谢** 得到中国科学院战略性先导科技专项资助，项目编号：XDB0690303。

袁玉林|袁曙光|余静|陈驰
中国科学院信息工程研究所，北京市海淀区淑清路 19 号，邮编 100084