cs.CRNov 6, 2026

GSynPEF: A Privacy Evaluation Framework for Synthetic Graphs

Authors: Yu Duan, Luca Baldesi, Carter T. Butts, Athina Markopoulou

Organizations: University of California, Irvine United States · Apple Inc. United States

Abstract

It is often desirable to generate and release synthetic graphs, which resemble real-world data, in a privacy-preserving way. While substantial progress has been made in designing private graph synthesizers (PGS), opportunities remain for more explicit connections between synthesizer models and privacy evaluation, and better accounting for output variation. This paper proposes GSynPEF, a practical framework for empirical evaluation of privacy and utility in settings for which a real-world graph is given as input and output synthetic graph(s) are observed. Our framework links a broad class of graph synthesizers (both statistical and deep-learning based) with privacy metrics, expanding evaluation dimensions to practical utility and risk, through empirical analysis of multiple actual outputs. The framework accommodates both an Exact Solution scenario, where synthesizer behavior is directly observable, and a Monte Carlo Approximation scenario where only synthetic outputs from a black box synthesizer are available. Extensive experiments on four real-world datasets and seven widely used graph synthesizers demonstrate framework's versatility, enabling privacy evaluation for different attack goals (e.g., to infer an edge or node) and capabilities (e.g., observing one or multiple synthetic graphs). We analyze evaluation results by examining the relationship between graph statistics and synthesizer design choices, providing insights for data curators in PGS selection and researchers for improved PGS design.

Figures & tables

Explore similar work

CardsList
  1. Differentially Private Synthetic Data via APIs 3: Using Simulators Instead of Foundation Model

    Feb 8, 2025Zinan Lin, Tadas Baltrusaitis, Wenyu Wang +1Differentially Private Synthetic Data GenerationSynthetic Data Generation

  2. Benchmarking Time Series Generation Methods for Privacy-Preserving Forecasting

    Aug 11, 2026Luis Amorim, Vitor Cerqueira, Moises Santos +2Synthetic Data GenerationTime Series Forecasting

  3. Empirical Auditing of Edge-Private Graph Generators

    Sep 21, 2026Anum Fatima, Stratis Limnios, James Adams +4Privacy AuditingEdge Inference