Using Metrics Suites to Improve the Measurement of Privacy in Graphs
Using Metrics Suites to Improve the Measurement of Privacy in Graphs
复制标题
DOI：
10.1109/tdsc.2020.2980271
复制
发表时间：
2019-05
影响因子：
7.3
通讯作者：
Yuchen Zhao;Isabel Wagner
中科院分区：
文献类型：
--
作者：
Yuchen Zhao;Isabel Wagner
社交图谱广泛应用于研究（如流行病学）和商业（如推荐系统）。然而，共享这些图表会带来隐私风险，因为它们包含有关个人的敏感信息。图匿名化技术的目的是保护图中的个人用户，而图去匿名化技术的目的是重新识别用户。匿名化和去匿名化算法的有效性通常用隐私指标来评估。然而，目前尚不清楚现有的隐私指标在用于图形隐私时有多强大。在本文中，我们研究了图匿名化和去匿名化的26个隐私指标，并根据三个标准评估了它们的强度：单调性表明度量是否表明较强对手的隐私较低；对于场景内比较，均匀性表示度量值是否均匀分布；对于场景之间的比较，共享值范围指示度量是否在场景之间使用一致的值范围。我们的大量实验表明，没有一个度量标准能完美地满足所有三个标准。因此，我们使用来自多标准决策分析的方法来聚合度量套件中的多个度量，并且我们表明，与最佳的单个度量相比，这些度量套件改善了单调性。这一重要结果使得对新的图形匿名化和去匿名化算法的评估更加单调，从而更加准确。
Social graphs are widely used in research (e.g., epidemiology) and business (e.g., recommender systems). However, sharing these graphs poses privacy risks because they contain sensitive information about individuals. Graph anonymization techniques aim to protect individual users in a graph, while graph de-anonymization aims to re-identify users. The effectiveness of anonymization and de-anonymization algorithms is usually evaluated with privacy metrics. However, it is unclear how strong existing privacy metrics are when they are used in graph privacy. In this article, we study 26 privacy metrics for graph anonymization and de-anonymization and evaluate their strength in terms of three criteria: monotonicity indicates whether the metric indicates lower privacy for stronger adversaries; for within-scenario comparisons, evenness indicates whether metric values are spread evenly; and for between-scenario comparisons, shared value range indicates whether metrics use a consistent value range across scenarios. Our extensive experiments indicate that no single metric fulfills all three criteria perfectly. We therefore use methods from multi-criteria decision analysis to aggregate multiple metrics in a metrics suite, and we show that these metrics suites improve monotonicity compared to the best individual metric. This important result enables more monotonic, and thus more accurate, evaluations of new graph anonymization and de-anonymization algorithms.