Trading Off Scalability, Privacy, and Performance in Data Synthesis

To successfully apply artificial intelligent approaches (e.g. machine learning & deep learning algorithms) in the real world application, data has became the most important part to support these algorithms. However, many types of data have privacy concerns and limited in terms of publicity [1, 2]. This causes the issue on training the machine learning models on these regions since these models require support from huge training data.

To mitigate this issue, synthetic data has been widely studied to substitute the real data. Synthetic data is the fake data points which generated by the generative model with the information from the real data points [3, 4, 5]. To evaluate the real world application of synthetic data, privacy preservation is one of the critical measurements which checks if identities from the original dataset can be detected or recognized in the synthetic data [6, 7, 8]. Similarity is another measurement since the synthetic data need to capture the information from the original data [9, 10]. Moreover, another important measurement is to check if the synthetic data can be used to substitute the real data on training the models [11, 12].

In this study, we evaluate a new data synthesis method called recursive random projections. Initially developed for optimization, recursive random projection uses the FASTMAP [13, 14] technique to recursively bi-cluster the data into numerous small leaf clusters. An optimizer then samples just $N=2$ points per leaf. But after reading the data synthesis literature [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] we began to wonder if recursive random projection could also be a data synthesis algorithm just by sampling much more than $N=2$.

To check this, we perform the study described in this paper. As described in §IV, random projection is augmented with mutation and crossover operators to generate synthetic data points per leaf cluster. This is then compared to state-of-the-art synthetic data generation algorithms such as (a) the DataSynthesizer [15], (b) the Synthetic Data Vault [16], and (c) the Howso engine [17].

To structure this inquiry, we ask these questions:

• •

  RQ1: When considering the privacy, which synthetic data generation algorithm can generate the synthetic data with the highest privacy preservation score?

• •

  RQ2: Which synthetic data generation algorithm can generate data that has higher similarity to the original data?

• •

  RQ3: When the machine learning model is trained on the synthetic data, can the model achieve compatible performance with those trained on the original data?

• •

  RQ4: Which algorithm has the best scalability?

• •

  RQ5: What suggestions can we provide from analyzing the conclusions in RQ1 to RQ4?

The contributions of this paper are

• •

  We proposed a random projection based synthetic data generation framework.

• •

  We made an empirical experiment to compare our proposed method, Howso engine, and two state-of-the-art synthetic data generation algorithms in different aspects such as (a) privacy preservation, (b) statistical measurements, (c) marginal probability, and (d) performance on training the machine learning models.

• •

  We found random projection based framework and Howso engine outperform state-of-the-art methods in some of the aspects.

• •

  The random projection based framework, in terms of scalability, can run significantly faster than Howso engine, and have similar runtime comparing to state-of-the-art methods, while outperform on more metrics than state-of-the-art methods.

The rest of this paper is constructed as follow: Section II illustrates the background of synthetic data generation, privacy & accuracy, and literature review on the synthetic data generation. Section III presents the Howso engine. Section IV illustrates our proposed random projection based synthetic data generation framework. Section V shows two state-of-the-art synthetic data generation algorithms DataSynthesizer and Synthetic Data Vault. Section VI presents the summary of benchmarks, evaluation metrics, and statistical analysis used in our experiment. Section VII shows our experimental results and our analysis to the results. We also discuss the threat to validity of our experiment in Section VIII, and make a conclusion to this study in Section IX.

Howso Engine is developed by Howso²²2https://www.howso.com/. It is an AI engine which supports the synthetic data generation. Specifically, Howso Engine utilizes the k-nearest neighbors to synthesize data with both global and local distributions [34]. The algorithm contains three parameters to control the search, and the best combination of the parameters is found by the grid search. Since there is only two parameters that need to be explored, the grid search is very fast.

• •

  The Minkowski coefficient $p\in[0.1,2.0]$ which controls the calculation of distance.

  $$d(x,y,\Delta)=(\sum_{i=1}^{n}\Delta(x_{i},y_{i})^{p})^{1/p}$$

  (1)

• •

  Iteration parameter $l=6$ which is used to find the parameter for distance calculation.

• •

  The number of neighbors $k\in[5,22]$ during the execution of $k$-nearest neighbors algorithm.

In the distance calculation, $\Delta$ is the specific function to measure the distance between two variables. Howso Engine implements the Lukaszyk-Karmowski metric (LK metric) for the Laplace distribution [17]. Specifically,

The Laplace distribution is preferred here since it makes entropy-minimizing assumptions about the underlying data, and more performant than Gaussian distribution. In the above calculation, $b$ is the surprisal that needs to be found through multiple iterations for each dataset. Specifically, the initial $b$ is set to $1/k$ where $k$ is the number of neighbors used in $k$-nearest neighbor algorithm. The first iteration finds the local neighbors by traditional Minkowski distance since no information in the initial round. In the end of the initial round, we can update the surprisal $b$:

• •

  For the numerical feature $k$, Howso Engine uses mean absolute deviation (MAE):

  $$b=\frac{1}{n}\sum_{i=1}^{n}|x_{i}-\mu_{k}|$$

  (3)

• •

  For the symbolic feature, Howso Engine uses mode and accuracy instead of mean and MAE.

Once the value of $b$ is stabilized (which we found $b$ tends to stable in 6 iterations), Howso Engine iteratively picks one random feature to synthesize. Specifically,

• •

  The values in the first picked feature will be synthesized on the basis of the global histogram (for nominal features) or the global Laplace distribution (for continuous features).

• •

  For all subsequent features, values are generated based on the distribution in the $k$ nearest neighbors to the partially synthesized cases.

The above process is done $m$ times per feature where $m$ is the number of synthetic instances that request to be generated.

Recursive random projection, as its name shows, projects the high-dimensional data into different low-dimensional clusters by using the random pivot selection procedure recursively [35] . In the synthetic data generation, the relationships between different features are hard to capture. Previous literature uses causal graph [15] or covariance metrics [16] to explore the connections between different features. In this study, we adopt the random projection to split the data into different clusters, which each cluster capture the data points that have similar feature patterns. In this section, we will introduce our design of random projection framework from the following two aspect:

• •

  First, the cluster algorithm which split the data into different clusters.

• •

  Second, the mutation & crossover operators which mutate the data points in the same cluster to generate synthetic data points that have strong connection to the original data points.

The cluster algorithm aims to split the data points into different clusters, which each cluster will contain data points with similar patterns. To achieve that, we utilize the FASTMAP random projection algorithm [13]. With a set of data points, FASTMAP uses the cosine rule to project the data points into the hyperplane formed by two farest points. More specifically, with two farest points $a$ and $b$, any third point $c$ from the set of data points can be mapped into the line connecting $a$ and $b$ by

Algorithm 1 shows the recursive clustering procedure, which in each function call, the algorithm first check if the number of current candidates in $\mathcal{C}$ less than the threshold $t$ (line 1). If the number does not reach the threshold, then stop the recursive. Otherwise, the split function will bi-cluster the current candidates, and perform the cluster algorithm again to the two sub-clusters (line 2-5). Algorithm 2 illustrates in detail how the split function works. More specifically, it firstly picks a random pivot, and finds two farest points based on the random pivot (line 1-4). After that, as we stated above, it uses the cosine rule to map all other data points to the line formed by two farest point (line 5-10). Finally, it returns two subsets based on the distance calculated by cosine rule (line 11-13).

Traditional clustering algorithms require $O(N^{2})$ calculations to fully split the data. However, random projection can achieve that in $O(2N)$, which is much faster than traditional clustering algorithms. This is the intuition we use random projection to reduce the scalability on generating synthetic data.

After the random projection returns the clusters, we then utilize the mutation and crossover operators used in the differential evolution algorithm to generate the synthetic data [36]. In the differential evolution algorithm, a better solution can be found in the current region of data points by mutating the data points as follow

where $x_{\text{old}_{i}}$ is the point from the original set of candidates, and $x_{1}$, $x_{2}$, and $x_{3}$ are three other random points from the set of candidates. $F$ is the difference scaling factor from 0 to 1, and $CR$ is the crossover probability that also from 0 to 1. Large $F$ indicates more scaling on the difference of two data points during the mutation, and large $CR$ indicates more probability the new candidate has a new value in each index. $R$ is a random index such that the value in that index must be mutated. This can prevent the duplicated new candidate when $CR$ is very small. We hypothesis that the synthetic data generated by this mutation and crossover operator can capture the feature information from the original data in each cluster since each cluster includes the data points that are close to each other.

In this section, we will briefly explain two state-of-the-art synthetic data generation algorithms we compared to.

In this section we will illustrate following things: (a) the benchmarks, (b) the evaluation metrics, and (c) the statistical analysis procedure.

In this section, we present our experimental results, and answer RQs based on the results.

RQ1: When considering the privacy, which synthetic data generation algorithm can generate the synthetic data with the highest privacy preservation? To evaluate the synthetic data in terms of privacy, we implement the Privacy Preservation metric to evaluate the privacy score. As we described in Section VI-B, privacy preservation evaluates the distance from the synthetic data point to the density of the region of the $k$-nearest neighbors of the closest original data point. We calculate such distance ratio for all synthetic data points, and take the geometric mean as the final privacy preservation score for the synthetic dataset. As mentioned in Section VI-B1, higher score refers to better privacy. However, the score of 1 already indicates that the synthetic data lies out of the density region of its closest original data point. Hence, in this research question, we consider an approach with good privacy preservation if its score is greater or equal than 1. Table III presents the experimental results. At first glance, DataSynthesizer has higher raw values than any other algorithms. However, those methods with score equal or greater than 1 will not induce the privacy issue in the real world application. Hence, if a method is not in the highest rank through statistical testing but its raw value is equal or greater than 1, we still consider it as a good method and marked them with grey color in Table III.

As we can see, synthetic data generated by DataSynthesizer has the highest privacy score. After that, Howso engine has promising performance on 6 case studies. SDV and recursive random projection do not perform well in terms of privacy preservation. Hence, our answer to RQ1 is

DataSynthesizer and Howso engine are two promising algorithms that can generate synthetic data with good privacy preservation score. If we only consider privacy, the result would recommend DataSynthesizer. However, as we will discuss in the RQ5, the evaluation of synthetic data cannot only concentrate on the privacy, and therefore, we recommend Howso engine more than DataSynthesizer.

RQ2: Which synthetic data generation algorithm can generate data that has higher similarity to the original data? Similarity is another important measurement on checking if synthetic data can provide same information as original data does. We implement statistical similarity score and marginal distribution similarity score to evaluate the synthetic data. Specifically,

• •

  Statistical similarity score evaluate the synthetic data by comparing its statistical measurements to the original data for each feature.

• •

  Marginal distribution similarity score evaluates the synthetic data from the estimated marginal probability distribution of each feature.

Table IV shows the statistical similarity score, which is calculated by evaluating the SMAPE of 14 different statistical measurements in synthetic data and original data (described in §VI-B2). From this table, we can find Howso engine and recursive random projection algorithm have better performance in more case studies than any other algorithms. This indicates that the synthetic data generated by Howso engine and recursive random projection algorithm can better capture the statistical patterns in the original data. More specifically, the large SMAPE scores on DataSynthesizer reduce its advantage on the privacy preservation since the synthetic data generated by it does not follow the statistical patterns in the original data.

Table V presents the marginal probability distribution similarity score, which is calculated by Jensen-Shannon divergence. Specifically, the marginal distribution is estimated through the KNN density estimation in numeric features and normalized value counts in categorical features. Different to the statistical similarity, this metric concentrates more on the estimated local probability distribution of each feature and check if the probability distribution of the same feature from synthetic data and orignial data is similar or not through Jenson-Shannon divergence. As we can see, most of the algorithms get good scores except DataSynthesizer, which is also shown to have worse score in statistical similarity score.

For all other algorithms except DataSynthesizer, we prefer Synthetic Data Vault with Gaussian Copula, recursive random projection, and Howso engine since they both perform well in two similarity metrics. Hence, our answer for RQ3 is

Considering two different similarity measurements, Synthetic Data Vault with Gaussian Copula, recursive random projection, and Howso engine achieve good performance in both two metrics. Thus, we recommend these three algorithms when evaluating the similarity.

RQ3: When the machine learning model is trained on the synthetic data, can the model achieve compatible performance with those trained on the original data? The model performance score is a very important indicator to evaluate the synthetic data. We split both the original data and the synthetic data to 80% training set and 20% test set. Then we use the model trained on the synthetic training data to predict the test set split from the original data. As stated in Section VI-B, for the classification task we collect accuracy, precision, recall, and Matthews correlation coefficient, and for the regression task we collect RMSE, R², and Spearman correlation coefficient. Table VI shows the scores of these metrics. As we can see, in all metrics, Howso engine and recursive random projection framework get significant higher performance than other two state-of-the-art algorithms. Therefore, we conclude that the synthetic data generated by these two algorithms can be applied to the real world machine learning models without loss on the information. Based on above, our answer to RQ3 is:

Howso engine and recursive random projection algorithm can generate synthetic data that does not loss any original information when training on the machine learning models.

RQ4: Which algorithm has the best scalability? To answer this question, we record the runtime of each generation algorithm. Figure 1 shows the runtime for each generation algorithm. To visualize the scalability, we first record the actual runtime for each algorithm in each case study. The scatters shows the point $(x,y)$ where $x$ is the size of the dataset, and $y$ is the runtime. After that, we plot the best fitting polynomial curve, which presents the trending of the runtime when the size of the dataset is increasing. As we can see, when the size of the dataset is small, all algorithms have similar runtime. However, when the size of the dataset becomes larger (e.g. 40k+ rows), the runtime of Howso engine and GAN based algorithm increases exponentially (i.e. the blue line and the pink line). To the contrary, our proposed recursive random projection algorithm, along with DataSynthesizer and Synthetic Data Vault with Gaussian Copula, have better efficiency, which the best fitting curve of runtime is close to linear with low slope even though the size of the dataset goes exponentially large. Hence, our answer to RQ4 is:

Our proposed recursive random projection framework, along with DataSynthesizer and Synthetic Data Vault with Gaussian Copula have the best scalability even when the size of the dataset is very large.

RQ5: What recommendation can we provide from analyzing the conclusions from RQ1 to RQ4? Evaluating synthetic data needs to consider multi-dimensional criteria. To empirically evaluate all performance from RQ1 to RQ4, we transfer each criteria to a 0-1 range and use the radar chart to visualize the performance. Specifically

• •

  For privacy preservation, all scores greater than 1 are treated as 1, and all other values will not be modified. The overall score of an algorithm will be the geometric mean of its scores in 10 case studies (If an algorithm has score 0, then we use 0.001 when calculating the geometric mean).

• •

  For statistical similarity and marginal distribution similarity, the scores are 1 minus the values in Table IV since smaller is better in these two metrics. The overall score is also the geometric mean through 10 case studies.

• •

  For model comparison, the negative correlation coefficient will be treated as 0.001 since negative value means no correlation. We first calculate the geometric mean of each algorithm for each individual metric, and then calculate the geometric mean again for 7 metrics.

• •

  For scalability, we transfer the actual runtime by minmax scalar in each case study. Then the overall score will also be the geometric mean through 10 case studies for each individual algorithm.

We select 4 algorithms to be presented in our chart. The first one is the correlation mode of DataSynthesizer. We do not choose independent mode since it is worse than correlation mode in privacy preservation, and similar to correlation mode in other metrics. The same procedure is applied to Synthetic Data Vault and the Gaussian Copula mode is selected. Hence in the chart, we have above two algorithms plus recursive random projection and Howso engine.

Figure 2 presents the radar chart of (a) DataSynthesizer with correlated mode, (b) SDV with Gaussain Copula, (c) Recursive Random Projection, and (d) Howso Engine. As we can see, the area covered by DataSynthesizer and SDV (blue dash line and orange dash line correspondingly) are obviously less than the area covered by Recursive Random Projection and Howso Engine. Hence, we offer two recommendations based on the analysis, and answer RQ5:

• •

  As seen in Figure 1, runtime between different methods does not differ too much. Hence, if the scalability is not an issue, then we recommend Howso Engine since it can achieve higher accuracy score and promising privacy preservation score.

• •

  However, if the dataset that needs to be synthesized is very large, and scalability becomes more important, we recommend our proposed Recursive Random Projection since it scales very fast and generate high accurate synthetic data.

Construct validity mainly related to the different parameters setting and model construction which causes the different outcome. In our study, the threat of construct validity can happen in (a) the parameter choice in different generation models and (b) the choice of settings when evaluate the synthetic data. For example, the cluster size in our proposed random projection based framework can influence the performance of generating synthetic data. We empirically evaluate the different sizes of cluster and choose 12 as the parameter in our experiment. For another example, when we evaluate the synthetic data by training the machine learning model on it, we use the 80% train test split on both original data and synthetic data. Different train test split ratio may cause different final outcome. The train test split ratio we used is the default setting which highly used in other machine learning studies. To reduce the threat, we build our experimental scripts as a python package, and allow researchers to replicate our experiment with their own parameter choice.

Conclusion validity refers to the threat that caused by applying different evaluation metrics when make the conclusion. To mitigate this threat, we apply four metrics (privacy preservation, descriptive statistics, marginal probability, and model comparison) which include most of the evaluation aspects of synthetic data in the past literature. Researchers may expect different conclusion when applying different metrics on our methods.

Internal validity focuses on the correctness of treatment caused the outcome. To reduce the effect caused by this threat, we collect ten highly used machine learning benchmarks from PMLB and run all algorithms on those ten benchmarks. Also, we control the size of synthetic data and make it equal to the size of the original data.

External validity indicates the threat of applying this experiment to other fields. To mitigate this threat, the experimental goal of our study focuses on the machine learning object, which is one of the most well-known regions in the real world application. Moreover, our replication package can be applied to different datasets, which allows researchers to explore other real world application with our scripts.

In this study, we explore the synthetic data generation algorithms and discuss the different validation metrics. We proposed recursive random projection based generator, and compare it to (a) two state-of-the-art generation algorithms DataSynthesizer and Synthetic Data Vault, and (b) the Howso Engine from our industiral partner. We evaluate those synthetic data generators from (a) privacy preservation, (b) statistical similarity and marginal probability distribution similarity, (c) model performance comparison, and (d) scalability.

In privacy measurement, we find DataSynthesizer has the highest privacy preservation score through all case studies. Howso engine ranks behind the DataSynthesizer. However, when considering the similarity measurements and model comparison score, Howso engine and recursive random projection based framework get far more higher score than DataSynthesizer. Hence, we conclude that DataSynthesizer adds too much noise to the synthetic data which the fake points lie out of the original distribution and patterns.

By conducting the empirically analysis to five evaluation criteria, from the radar chart in RQ5, we offer two recommendations:

• •

  If scalability is not an issue, then we recommend Howso Engine which has highest accuracy performance and promising privacy score.

• •

  However, when the dataset is large enough, which will cause the scalability issue, we recommend recursive random projection based framework since it scales fast and can achieve highest accuracy performance.

In the future work, we will explore more synthetic data generation algorithms, as well as more benchmarks. Moreover, current recursive random projection based framework does not particularly add differential privacy operators. In the future, we will design such operators based on the condition in each cluster, and improve its privacy preservation score.

In this work, Howso funded NCState to comparatively assess numerous data synthesis methods. We assert that the conclusions made here are the product of NCState and were not altered by our Howso collaborators.