SoK: Privacy-Preserving Data Synthesis

Back to home page

Data Utility and Fidelity Measures

We present the fidelity and utility measures for the synthetic data, where fidelity measures include various intrinsic properties of synthetic data, and utility measures refer to the performance of synthetic data when used for downstream applications.

Let F denote fidelity, and A denote application.

We organize this section based on different data types. For structured data, we study tabular data (S1), trajectory data (S2), and graph data (S3). For unstructured data, we consider image data (U1).

For each data type, we first outline the data analysis performed on it or the target of the analysis. We then provide the measures (i.e., evaluation metrics) for each data analysis task.

Tabular

S1-F1. $k$-way marginals

Measure: similarity, concretely:

• $L_1$ distance (average error): Zhang et al., 2014, Gaboardi et al., 2014, Bindschaedler et al., 2016, Asghar et al., 2019, McKenna et al., 2021, Zhang et al., 2021, Cai et al., 2021, Liew et al., 2022

• $L_2$ distance: Chen et al., 2015

• $L_\infty$ distance (max error): Asghar et al., 2019, Vietri et al., 2020, Aydore et al., 2021

• Kullback-Leibler (KL) divergence: Hardt et al., 2012

• Kolmogorov-Smirnov distance (Massey Jr, 1951)]: Gambs et al., 2021

S1-F2. Queries, including:

1. Random linear queries: Xu et al., 2017

2. Range queries: Hardt et al., 2012, Li et al., 2014, Zhang et al., 2021, Liew et al., 2022

3. Parity queries: Gaboardi et al., 2014

4. Aggregation queries: Fan et al., 2020

Measure: similarity by $L_1$ distance

S1-F3. Matrix

Measure: similarity, concretely

• Frobenius distance: Li et al., 2011, Jiang et al., 2013

• Mean Correlation Delta: Gambs et al., 2021

S1-F4. Similarity w.r.t. pairwise distances: Xu et al., 2017

S1-F5. Distinguishing game Bindschaedler et al., 2016

S1-F6. Classification

Measure: similarity, concretely

• Matthews Correlation Coefficient (MCC) (Matthews, 1975)]: Gambs et al., 2021

S1-A1. Classification

Below are different classifiers:

1. SVM: Zhang et al., 2014, Chen et al., 2015, Xu et al., 2017, Chanyaswad et al., 2019, Zhang et al., 2021, Cai et al., 2021, Beaulieu-Jones et al., 2019, Astolfi et al., 2021, Jordon et al., 2019, Harder et al., 2020

2. Boosting: Bindschaedler et al., 2016, Gambs et al., 2021, Fan et al., 2020, Jordon et al., 2019, Long et al., 2021, Harder et al., 2020

3. Random forest: Bindschaedler et al., 2016, Fan et al., 2020, Beaulieu-Jones et al., 2019, Hyland et al., 2017, Jordon et al., 2019, Harder et al., 2020

4. Decision tree: Bindschaedler et al., 2016, Fan et al., 2020, Jordon et al., 2019, Harder et al., 2020

5. Bagging: Jordon et al., 2019, Long et al., 2021, Harder et al., 2020

6. Multilayer Perceptron: Jordon et al., 2019, Long et al., 2021, Harder et al., 2020

Measure: accuracy/misclassification rate/Area Under the Receiver Operating Characteristics (AUROC)

S1-A2. Regression

Below are different regression methods:

• Kernel Ridge Regression: Chanyaswad et al., 2019

• Linear regression: Gambs et al., 2021, Fan et al., 2020, Beaulieu-Jones et al., 2019, Astolfi et al., 2021, Jordon et al., 2019, Long et al., 2021, Harder et al., 2020

Measure: root mean square error (RMSE) (Bishop, 2006), AUROC

S1-A3. Clustering

Measure:

• Silhouette Coefficient (Rousseeuw, 1987): Chanyaswad et al., 2019

• Normalized Mutual Information: Fan et al., 2020

Trajectory

S2-F1. Count queries

Measure: similarity, concretely:

• relative error: Chen et al., 2012a, Chen et al., 2012b, Zhang et al., 2016, Roy et al., 2016, Gursoy et al., 2018a, Gursoy et al., 2018b, Gursoy et al., 2020

S2-F2. Frequent patterns

Measure: similarity, concretely:

• True/false positive: Chen et al., 2012a, Roy et al., 2016
• Precision: Chen et al., 2012b, Zhang et al., 2016
• Average relative error: Chen et al., 2012b, Gursoy et al., 2018a, Gursoy et al., 2018b, Gursoy et al., 2020
• $F_1$ score: He et al., 2015, Gursoy et al., 2018b
• Kendall-tau coefficient: Gursoy et al., 2018a, Gursoy et al., 2018b

S2-F3. Longest common subsequence (LCSS) (Vlachos et al., 2002): Wang and Sinnott, 2017

S2-F4. Spatial location

Measure: similarity, concretely

• Earth Mover’s Distance (EMD) (Rubner et al., 2000): Mir et al., 2013, Roy et al., 2016
• Euclidean distance: Wang and Sinnott, 2017
• Dynamic Time Warping (DTW): Wang and Sinnott, 2017
• Edit Distance on Real sequence (EDR) (Chen et al., 2005): Wang and Sinnott, 2017

S2-F5. Length distribution

Measure: similarity, concretely

• Jenson-Shannon divergence (Fuglede and Topsoe, 2004): Gursoy et al., 2018a, Gursoy et al., 2018b, Gursoy et al., 2020
• $L_1$ distance: Zhang et al., 2016

S2-F6. Diameter distribution

Measure: similarity, concretely:

• Jenson-Shannon divergence: He et al., 2015, Gursoy et al., 2018a, Gursoy et al., 2018b
• Histogram: Mir et al., 2013

S2-F7. Trip distribution

Measure: similarity, concretely:

• Jenson-Shannon divergence: He et al., 2015, Gursoy et al., 2018a, Gursoy et al., 2018b, Gursoy et al., 2020

Graph

S3-F1. (Joint) degree distribution: Sala et al., 2011, Mir and Wright, 2012, Xiao et al., 2014, Jorgensen et al., 2016, Chen et al., 2020, Zhang et al., 2021, Yang et al., 2020

S3-F2. Assortativity: Sala et al., 2011, Wang and Wu, 2013

S3-F3. Shortest/average/weighted path distance: Sala et al., 2011, Wang and Wu, 2013, Xiao et al., 2014

S3-F4. Global/local clustering coefficients: Mir and Wright, 2012, Wang and Wu, 2013, Jorgensen et al., 2016, Chen et al., 2020

S3-F5. Attribute-edge correlations (Hellinger distance): Jorgensen et al., 2016, Chen et al., 2020

S3-F6. Community stucture

Measure:

• Modularity: Wang and Wu, 2013
• Precision and recall: Chen et al., 2020

S3-F7. Parameter estimation: Lu and Miklau, 2014

S3-F8. Statistics

1. Nodes: Wang and Wu, 2013

2. Edges: Wang and Wu, 2013, Jorgensen et al., 2016, Chen et al., 2020, Zheng et al., 2021

3. Reachable pairs of nodes within $h$ hopes: Mir and Wright, 2012
4. Average degree: Wang and Wu, 2013
5. Max degree: Zheng et al., 2021
6. Triangle: Wang and Wu, 2013, Jorgensen et al., 2016, Chen et al., 2020, Zheng et al., 2021
7. Other alternating statistics: Lu and Miklau, 2014, Zheng et al., 2021

Measure: count

S3-F9. Spectrum (node) analysis

Measure:

• Similarity w.r.t. eigenvector centrality: Xiao et al., 2014
• Largest eigenvalue of the adjacent matrix: Wang and Wu, 2013
• Leading eigenvector of the adjacent matrix: Mir and Wright, 2012
• Spectrum of the adjacent matrix: Mir and Wright, 2012

S3-A1. Reliable Email (Garriss et al., 2006): Sala et al., 2011

S3-A2. Influence maximization (Chen et al., 2009): Sala et al., 2011

S3-A3. Link prediction: Zheng et al., 2021, Yang et al., 2020

The readers can refer to Costa et al., 2007 for a comprehensive survey of the common utility metrics in graph.

Image data

U1-F1. Inception Score (IS) (Salimans et al., 2016): Liu et al. 2019, Wang et al., 2020, Zhang et al., 2018, Xu et al., 2019, Yang et al., 2020, Schwabedal et al., 2020, Chen et al., 2020, Long et al., 2021, Zhang et al., 2019, Chen et al., 2022, Xin et al., 2022

U1-F2. Frechet Inception Distance (FID) (Heusel el al., 2017): Schwabedal et al., 2020, Chen et al., 2020, Long et al., 2021, Liew et al., 2022, Chen et al., 2022, Xin et al., 2022

U1-F3. Kernel Inception Distance (KID) (Bińkowski et al., 2018): Liew et al., 2022

U1-F4. Jensen-Shannon Scores (Fuglede et al., 2004): Zhang et al., 2018, Xu et al., 2019, Yang et al., 2020

U1-A1. Classification

Measure: accuracy/error: Liu et al. 2019, Xie et al. 2018, Frigerio et al. 2019, Zhang et al., 2018, Xu et al., 2019, Yang et al., 2020, Chen et al., 2020, Torkzadehmahani et al., 2019, Triastcyn et al., 2020, Long et al., 2021, Wang et al., 2021, Ma et al., 2020, Imtiaz et al., 2021, Harder et al., 2020, Chen et al., 2022, Zhang et al., 2021, Triastcyn et al., 2020

U1-A2. Segmentation

Measure: Hausdorff distance: Schwabedal et al., 2020

U1-A3. Data Debugging

Measure: visualization: Chen et al., 2020, Triastcyn et al., 2020, Augenstein et al., 2020