PGB (Private Graph Benchmark)

PGB（私有图基准）是一个全面的基准，旨在公平地比较不同的私有图生成算法。该数据集包含43,200个单一实验，涉及6种选定的算法、8个图数据集、6个隐私预算和15个查询。数据集的创建过程遵循了四个基本设计原则：机制、图数据集、隐私要求和效用指标。PGB的应用领域主要是在保护个人隐私的同时，从多样化的图数据中提取洞察，解决图分析中的隐私泄露问题。

PGB (Private Graph Benchmark) is a comprehensive benchmark developed to fairly compare distinct private graph generation algorithms. This dataset contains 43,200 individual experiments, covering 6 selected algorithms, 8 graph datasets, 6 privacy budgets, and 15 queries. Four fundamental design principles were followed during the dataset's creation: mechanism, graph datasets, privacy requirements, and utility metrics. The main application areas of PGB focus on extracting insights from diverse graph data while protecting personal privacy, and resolving privacy leakage issues in graph analysis.

原始信息汇总

PrivGraph 数据集概述

环境要求

• numpy >= 1.20.1
• pandas >= 1.2.4
• networkx >= 2.5
• scikit-learn >= 0.24.1
• python-louvain >= 0.15
• python >= 3.8

内容结构

• data (文件夹): 包含所有数据集。
• comm (文件夹): 用于社区发现。
• result (文件夹): 存储结果，包含四个合成图示例。
• main.py (文件): 用于获取 PrivGraph 端到端实验结果。
• main_vary_N.py (文件): 用于获取不同节点数量的结果。
• main_vary_eps.py (文件): 用于获取不同隐私预算分配的结果。
• main_vary_t.py (文件): 用于获取不同分辨率参数的结果。
• IM_spread.py (文件): 用于获取影响力最大化的结果。
• utils.py (文件): 包含其他文件所需的一些函数。

运行示例

• 端到端实验: python main.py
• 节点数量影响: python main_vary_N.py
• 隐私预算分配影响: python main_vary_eps.py
• 分辨率参数影响: python main_vary_t.py
• 影响力最大化: python IM_spread.py

引用

@inproceedings{YZDCCS23, author = {Quan Yuan and Zhikun Zhang and Linkang Du and Min Chen and Peng Cheng and Mingyang Sun}, title = {{PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information}}, booktitle = {{USENIX Security}}, publisher = {}, year = {2023}, }

搜集汇总

数据集介绍

构建方式

PGB (Private Graph Benchmark) 数据集的构建基于四个关键元素：机制、图数据集、隐私要求和效用度量。首先，通过文献综述识别出这四个元素，并讨论了确保基准全面性的原则。随后，提出了一个基准实例，该实例遵循所有设计原则，用于评估现有的和新提出的图生成算法。通过广泛的理论和实证分析，获得了对先前算法优缺点的宝贵见解。

特点

PGB 数据集的特点在于其全面性和公平性。它涵盖了多种图生成算法、多样化的图数据集、不同的隐私预算和多样的效用度量，确保了不同算法之间的公平比较。此外，PGB 还提供了详细的实验结果和分析，帮助研究人员选择适合不同场景的机制。

使用方法

PGB 数据集的使用方法包括选择合适的图生成算法、图数据集、隐私预算和效用度量进行实验。研究人员可以根据实验结果评估算法的性能，并根据不同的应用场景选择最优的算法。PGB 还提供了详细的实验指南和代码实现，方便研究人员进行复现实验和进一步研究。

背景与挑战

背景概述

在图数据分析领域，保护个体隐私的同时提取有价值的见解是一项重要任务。PGB（Private Graph Benchmark）数据集由Shang Liu等研究人员于2024年创建，旨在为差分隐私合成图生成算法提供一个综合基准。该数据集的核心研究问题是如何在保护个体隐私的前提下，生成与原始图语义相似的合成图。PGB的提出填补了现有算法比较中的空白，通过统一的隐私定义、图数据集、隐私要求和效用度量，确保了不同算法之间的公平比较。这一研究对社交网络、交通网络和流行病学网络等多个领域具有深远影响，推动了差分隐私技术在图分析中的应用。

当前挑战

PGB数据集面临的挑战主要集中在两个方面。首先，差分隐私合成图生成算法在不同隐私定义、多样化的图数据集和不同的隐私要求下进行有效比较存在困难。其次，构建过程中，算法使用的隐私定义不同（如边差分隐私和节点差分隐私），缺乏开源支持，数据依赖性错误以及隐私参数ε的不同选择，都增加了算法比较的复杂性。此外，现有算法仅覆盖部分图查询，且在评估同一查询时使用不同的效用度量，进一步加剧了比较的难度。PGB通过引入统一的设计原则和基准实例化，旨在解决这些挑战，提供一个公平、全面的比较平台。

常用场景

经典使用场景

PGB（Private Graph Benchmark）数据集在差分隐私图生成算法的评估中发挥了关键作用。其经典使用场景包括对不同差分隐私图生成算法进行公平比较，通过提供统一的基准来评估这些算法在隐私保护和图数据生成质量之间的权衡。PGB涵盖了多种图数据集、隐私预算和效用度量，确保了评估的全面性和公正性。

实际应用

在实际应用中，PGB数据集被广泛用于开发和测试新的差分隐私图生成算法。例如，社交网络分析、交通网络优化和流行病学网络研究等领域可以利用PGB来生成符合隐私保护要求的合成图数据。这些合成数据可以在不泄露个人敏感信息的前提下，支持多种图分析任务，如社区检测、子图计数和中心性分析。

衍生相关工作

PGB数据集的提出催生了大量相关研究工作。例如，基于PGB的评估结果，研究人员提出了改进的差分隐私图生成算法，如TmF和DGG，这些算法在特定数据集和隐私预算下表现优异。此外，PGB还激发了对差分隐私图生成算法理论基础的深入研究，推动了隐私保护技术的理论发展。PGB的成功应用也促进了其他领域（如表格数据分析）的差分隐私基准的开发。