title: Every Query Counts: Analyzing the Privacy Loss of Exploratory Data Analyses
authors: Saskia Nuñez von Voigt Mira Pauli Johanna Reichert Florian Tschorsch
text: 
  
  Privacy Loss of Exploratory Data Analyses
  
  S. Nuñez von Voigt et al.
  
  Distributed Security Infrastructure Group, Technische Universität
  Berlin,
   Straße des 17. Juni 135, 10623 Berlin, Germany
  
  {saskia.nunezvonvoigt,florian.tschorsch}@tu-berlin.de
  
  anacision GmbH,
   Albert-Nestler-Straße 19, 76131 Karlsruhe, Germany
  
  {mira.pauli,johanna.reichert}@anacision.de
  Every Query Counts: Analyzing the Privacy Loss of Exploratory Data 
  Analyses
      Saskia Nuñez von Voigt1 Mira Pauli2 Johanna Reichert2 Florian Tschorsch1
      
  
  ============================================================================
  
  
  An exploratory data analysis is an essential step for every data analyst to 
  gain insights, evaluate data quality and (if required) select a machine 
  learning model for further processing.
  While privacy-preserving machine learning is on the rise,
  more often than not this initial analysis is not counted towards the privacy 
  budget.
  In this paper, we quantify the privacy loss for basic statistical functions
  and highlight the importance of taking it into account
  when calculating the privacy-loss budget of a machine learning approach.
  
  
  
  
  
  § INTRODUCTION
  
  
  
  One of the most prevalent barriers of machine learning
  involve data management in general
  and information security and privacy in particular.
  This is especially relevant for sensitive data sets that,
  for example, include medical and financial data items.
  In order to overcome the barriers,
  the area of PPML
  gained attention <cit.>.
  It is concerned with providing an
  infrastructure for secure and privacy-preserving data access
  as well as privacy-preserving model generation.
  
  While PPML reduces the risk of data leaks,
  particularly the risk of model inversion attacks,
  one aspect is often overlooked:
  In order to decide which type of model should be trained
  and how it should be parametrized,
  a data analyst performs a preceding EDA.
  The EDA consists of querying the data for a number of statistics and 
  metrics.
  The goal is to gain insights on the  data quality, as well as the relationships 
  between the  variables
  to initiate data preprocessing
  before a model is created.
  To do so, the data analyst has typically full data access
  and is not restricted in her queries.
  
  In this paper, we evaluate the privacy loss of performing an EDA.
  To this end, we assume that an analyst obtains differentially-private 
  answers <cit.>
  to preserve information privacy.
  We quantify the privacy loss for basic analysis steps,
  which can be used to make decisions on how to clean the data,
  select features, and to select a model.
  Based on our evaluation,
  we discuss the implications of the resulting privacy loss and conclude that
  an interactive EDA is not feasible in a privacy-preserving setting.
  
  
  
  At the same time, we compare the accuracy of an interactive approach
  with the generation of differentially-private synthetic data.
  Our results underline that the privacy loss can be mitigated by determining
  which functions are needed such that they can be answered as correlated queries.
  The generation of synthetic data is a generalization of this approach.
  Accordingly, we recommend to develop standardized sets of EDA functions
  to reduce the privacy loss and/or increase accuracy.
  In all cases, however, the privacy loss inevitably increases
  with the amount of information requested and
  should be considered for EDA in general.
  
  
  This paper is organized as follows. In <Ref> and 
  <Ref>,
  we describe our system model
  and introduce a basic set of EDA functions, respectively.
  In <Ref>, we evaluate the privacy loss and discuss the
  feasibility of a differentially-private interactive EDA,
  before concluding this paper in <Ref>.
  
  
  
  
  § BACKGROUND
  
  
  
  
  
   §.§ System and Adversary Model
  
  
  
  An EDA is typically performed before a machine learning model is created
  in order to obtain a basic understanding of variable distributions, data 
  quality,
  and the relationship between variables.
  By querying this information, a data analyst can determine the
  necessary steps for data cleaning and a suitable model.
  
  In this paper, we consider the data analyst as an adversary,
  who should not be able to reveal information about individuals.
  That is, we assume an interactive query-response setting,
  which is visualized in <Ref>.
  The analyst (internal or external)
  is allowed to query a data set and request aggregated data to perform the
  EDA and afterwards train a model.
  In order to mitigate re-identification attacks,
  noise is added to the results, which satisfy the definition of differential 
  privacy
  (see below).
  A privacy budget tracks the privacy loss generated by the queries. It decreases
  with each query until it is spent and no further
  queries are answered.
  The system model captures the privacy-utility trade-off
  inherent to the notion of information privacy.
  We believe that the requirement of an EDA is often overlooked
  when it comes to creating privacy-preserving models.
  
  
  
  
  
  
  
  
   §.§ Differential Privacy
  
  
  Differential privacy quantifies the privacy loss <cit.>
  regardless of an adversary's knowledge.
  It determines the risk of being identified in a database by
  comparing results of querying the database with and without
  the individual concerned.
  The intuition is that the absence/existence of a data subject
  should have a small impact on the results,
  which in turn implies that an adversary cannot identify individuals from the 
  result.
  More formally, a mechanism 𝒦 provides ϵ-differential 
  privacy
  if for all data sets D_1 and D_2, differing on at most one data subject,
  and all
  S⊆Range(𝒦) satisfy
  
      P[𝒦(D_1) ∈ S] ≤e^ϵ· P[𝒦(D_2) 
      ∈ S]
      .
  
  Differential privacy ensures that the result of an analysis changes
  by at most a multiplicative factor e^ϵ when a record is
  included in the data set or not.  For ϵ=0, the result of an analysis is exactly the same
  whether a record is included or not and thus provides perfect
  privacy. With ϵ=0, however, we cannot obtain meaningful
  results. In contrast, higher ϵ provide lower privacy guarantee.
  It is therefore necessary to find a balance between
  ϵ and the accuracy of the results.
  
  Any mechanism guaranteeing differential privacy is robust under
  composition <cit.>. If we apply the mechanisms 𝒦_i, each providing
  ϵ_i-differential privacy, several times to the same data, the sequence
  of queries gives ϵ-differential privacy with
  ϵ=∑_iϵ_i. In other words, the maximum privacy loss is
  bounded by the privacy budget
  ϵ, which in turn is reduced by ϵ_i for each query. 
  As soon as the budget is spent, no further queries are answered.
  The parallel application of mechanisms 𝒦_i for D_i, an
  arbitrary disjoint subset of the input domain D, each providing
  ϵ_i-differential privacy, gives ϵ -differential privacy with
  ϵ=max(ϵ_i).
  
  In an EDA, a data analyst queries interactively,
  , we assume random queries that are unknown in advance.
  Therefore, we apply the differential privacy
  mechanism for each query and calculate the required privacy budget
  ϵ according the composition theorems.
  
  
  To satisfy differential privacy for numeric queries, commonly random noise drawn
  from a Laplace distribution is added to the numerical output f(X) <cit.>. 
  The magnitude of noise is calibrated according to the
  sensitivity of a function. The sensitivity Δ f is the maximum difference
  that an output can change by removing or adding a record.
  For example, a simple counting query, , how many rows have a specific 
  variable value, has
  Δ f =1.
  Differential privacy is then provided by f(X)+Lap(Δ 
  f/ϵ).
  
  
  
  § EXPLORATORY DATA ANALYSIS
  
  
  An EDA is an essential step in any data science application.
  Generally, an EDA includes different methods and can be an
  exhaustive analysis within itself.
  Moreover, the process is not standardized
  and depends on the objective of the analysis.
  
  In the following, we select some basic statistical functions
  that serve as the least common denominator,
  which we derived from literature as well as our own practice in the field.
  The selected statistical functions for this basic EDA
  are listed in <Ref>.
  Even if we limit our EDA to certain functions, we still assume that the
  queries performed by the analyst are not
  known in advance and are sent interactively depending on the results.
  Since some analyses depend on the data type, we differentiate functions
  between categorical and numerical variables.
  
  
  
  
  
    
  Distribution.
  The distribution of the data is important to understand the data.
  For numerical variables, the range and quantiles provide
  information about the validity of the data and a sense of the range of the
  data.
  For categorical variables, a data analyst
  retrieves the unique variable values, especially the number of observations of 
  each variable value.
  Variables with a discrete uniform distribution, for example, are not suitable 
  to identify
  meaningful patterns. Variables that show this behavior need to be cleaned or
  removed for the training process.
  
  
  
  
    
  Missing Values.
  The number of missing values indicates whether steps for data cleaning are
  necessary.
  There are different options such as case deletions or imputation with a vast
  body of literature discussing these options and their implications for later
  analysis steps <cit.>.
  
  
  
    
  Outliers.
  Machine learning models can be influenced by outliers, thus an analyst should 
  be aware
  of their presence in the data set.
  There are many sophisticated tools to detect outliers,
  that mostly come with a high degree of
  privacy loss.
  Therefore, we resort to a simple box plot approach, where the cutoff point for
  outliers is defined as the upper and lower quantiles (Q_1 and
  Q_3) and a tolerance  of 1.5 · (Q_3 - Q_1) <cit.>.
  We then count all values that lie above or below that cutoff point.
  In this univariate outlier detection context, categorical variables are not 
  covered, as rare values have already become visible from the distribution.
  
  
  
    
  Correlation.
  The results of the correlation between
  variables mainly contribute to feature selection, where certain
  variables may be excluded from the model or combined with each other.
  Correlated variables are problematic for the interpretation of
  a model <cit.>.
  Furthermore, the relationship between independent variables may imply that
  dimensionality reduction methods can be applied to the data set to improve
  model performance.
  Based on this motivation, we include
  Spearman's correlation matrix for numerical data
  and a Cramer's V for categorical variables
  in our basic set of EDA functions.
  
  
  
  
  
  
  
  
  § PRIVACY LOSS AND ACCURACY IMPACT ASSESSMENT
  
  
  
  
  In <Ref>, we quantify the privacy loss
  of the functions of our basic EDA.
  The privacy budget required to compute the respective functions is cumulated by
  the privacy loss of each query.
  It depends on the privacy loss per query ϵ_i,
  the number of categorical variables c, and
  the number of numerical variables n.
  
  For the numerical distribution a data analyst queries the min,
  max, Q_1, Q_2, and Q_3.
  In other words, to obtain the information an analyst needs to query the data
  five times.
  Since each record is contained in each variable, an analyst spends
  5 ·ϵ_i· n of its privacy budget for this statistical function.
  The categorical distribution can be investigated by the counts per variable
  value
  that are queried only once per variable and the required
  budget increases by ϵ_i and c.
  
  The missing values as well as the outliers of categorical variables are visible
  from the value
  counts. Therefore, the privacy budget only increases by the numerical variables
  for both the missing values and the outliers.
  
  We quantify the relationship between two variables using Spearman's
  correlation for numerical and Cramer's V for categorical variables.
  Since both measures are symmetrical, the privacy budget increases by
  the number of permutations
  
  
  
   §.§ Privacy Loss
  
  We determine the privacy budget for some
  data sets from the UCI Machine Learning
  Repository[<http://archive.ics.uci.edu/ml>].
  The data sets differ in size and number of variables.
  Common values for ϵ comprise 0.01, 0.1, 1, ln(2), or 
  ln(3) <cit.>. Therefore we fixed the privacy guarantee for each
  query to ϵ_i=0.01, as this is the smallest value.
  
  
  
  
  
  
  <Ref> shows the cumulative privacy loss by
  conducting
  all statistical functions from our basic EDA.
  We observe an increasing and high privacy loss.
  For computing all functions, the  data set requires the smallest
  privacy budget. The prime cause of
  this difference is the small number of variables in total.
  Indeed, the  data set has less variables in total
  but more numerical variables.
  Since an analyst sends an additional query for numerical variables to determine
  the missing values or outliers, the privacy loss increases and is thus higher
  than for categorical variables.
  
  The correlation leads to the highest privacy loss, since the budget increases
  by the binomial coefficient n  2 and
  c  2.
  
  Note that the privacy budget increases linearly with the number of queries.
  With a
  lower privacy guarantee, , ϵ_i >0.01, the total privacy budget
  would exceed the privacy budget of ϵ = 3, which yields a 20 times higher
  chance (e^3) to be compromised.
  With a smaller ϵ_i, we can reduce the privacy loss and
  therefore the total required privacy budget. However, this leads to an accuracy
  loss.
  
  
  
  
  
  
  
  
  
   §.§ Accuracy
  
  Due to the order of queried information the answers of our
  queries cannot be re-used. In order to reduce the privacy budget,
  numerous approaches
  aggregate queries and determine correlations between
  queries <cit.>.
  This allows estimating results from other noisy answers without spending its
  privacy budget.
  The results of these mechanisms can also be treated as differentially-private
  synthetic data that support the original working method of a data analyst.
  
  In this section, we evaluate the accuracy of a differentially-private EDA
  and compare the interactive setting with
  differentially-private synthetic data
  sets. For data sets with numeric variables, we remove some values from a
  variable to have a numerical variable with 10% missing values.
  
  We generate synthetic data sets using the correlated mode of
  DataSynthesizer[Available for download at
  <https://github.com/DataResponsibly/DataSynthesizer>] that learns a Bayesian
  network with a degree of four.
  For comparison, we generate synthetic data with the same privacy budget that is
  required to investigate the correlation in an interactive setting.
  For example for the  synthetic data set we set
  ϵ= 51·0.01=0.51.
  
  
  
  We measure the accuracy of our basic EDA using the
  relative error of each query.
  <Ref> reports the relative error for each statistical function
  visualized as
  box plot containing the relative error for each query.
  Overall, the synthetic data sets have a smaller relative error compared to the
  interactive setting.
  However, the relative error of the synthetic data sets for the numerical
  correlation is higher compared to the interactive setting.
  For the data set  (<Ref>c), we observe a similar 
  effect for the
  outliers. The high error occurs in the synthetic data sets due to the high
  range of some numerical variables.
  Remarkably, we obtain a high error for outliers for the interactive setting. 
  This demonstrates that the relative error for the variables varies.
  
  
  
  
   §.§ Discussion
  
  
  The results show that even basic investigations of an EDA require a high
  privacy budget in an interactive setting.
  Therefore, an interactive analysis with both acceptable accuracy and an 
  acceptable privacy guarantee is not possible.
  
  
  
  Non-interactive mechanisms, such as differentially-private synthetic data sets,
  can be used to increase accuracy and/or reduce the privacy budget.
  Notably, the synthetic data set can be used directly to train a model without
  dividing the privacy budget among EDA and model generation.
  However, the expressiveness of non-interactive mechanisms is limited to the
  correlations used for generating the output. Therefore, these mechanisms are not
  applicable for an interactive setting with random or unknown queries <cit.>.
  
  In an EDA, information is queried interactively, where one query
  depends on the results of previous queries.
  Grouping or limiting the queries to certain statistics,
  a differentially-private EDA might become feasible, though.
  We therefore appeal to data analysts to agree on widely applicable
  statistics that show the information necessary for model generation.
  With our basic EDA, we made a first attempt
  to create such a collection of statistics.
  A standardized set of statistical functions used in an EDA
  could be optimized to balance the privacy-utility trade-off.
  
  
  
  
  § CONCLUSION
  
  
  In this paper we demonstrate the increase of the privacy loss and thus the
  required budget for an
  interactive differentially-private analysis. We argue that the EDA should
  be considered in privacy-preserving models, as it is an essential step in 
  machine
  learning.
  In order to address the privacy-utility trade-off, we propose to agree on
  standardized sets of EDA functions and use the remaining privacy budget for
  model creation.
  
  
  
    §.§.§ Acknowledgement
  
  This work was supported by the Federal Ministry of Education and Research of 
  Germany (project number 16KIS0909).
  
  splncs04
  10
  
  
  
  
  acuna2004treatment
  Acuna, E., Rodriguez, C.: The treatment of missing values and its effect on
    classifier accuracy. In: Classification, clustering, and data mining
    applications, pp. 639–647. Springer
  
  Al-RubaieC19
  Al-Rubaie, M., Chang, J.M.: Privacy-preserving machine learning: Threats and
    solutions. IEEE Secur. Priv.  17(2),  49–58
  
  DankarE13
  Dankar, F.K., Emam, K.E.: Practicing differential privacy in health care: A
    review. Trans. Data Priv.  6(1),  35–67
  
  Dwork06
  Dwork, C.: Differential privacy. In: ICALP'06: 33rd International Colloquium on
    Automata,Languages and Programming. pp. 1–12
  
  Dwork08
  Dwork, C.: Differential privacy: A survey of results. In: TAMC'08: 5th
    International Conference on Theory and Applications of Models of Computation.
    Lecture Notes in Computer Science, vol. 4978, pp. 1–19. Springer
  
  laurikkala2000informal
  Laurikkala, J., Juhola, M., Kentala, E., Lavrac, N., Miksch, S., Kavsek, B.:
    Informal identification of outliers in medical data. In: Fifth international
    workshop on intelligent data analysis in medicine and pharmacology. vol. 1,
    pp. 20–24
  
  Leoni12
  Leoni, D.: Non-interactive differential privacy: a survey. In: WOD'12:
    International Workshop on Open Data. pp. 40–52. ACM
  
  LiHRMM10
  Li, C., Hay, M., Rastogi, V., Miklau, G., McGregor, A.: Optimizing linear
    counting queries under differential privacy. In: PODS'10: 29th ACM
    Symposium on Principles of Database Systems. pp. 123–134
  
  LiM12
  Li, C., Miklau, G.: An adaptive mechanism for accurate query answering under
    differential privacy. Proc. VLDB Endow.  5(6),  514–525
  
  McSherryT07
  McSherry, F., Talwar, K.: Mechanism design via differential privacy. In:
    FOCS'07: Proceedings of the 48th Annual IEEE Symposium on Foundations of
    Computer Science. pp. 94–103
  
  MohasselZ17
  Mohassel, P., Zhang, Y.: Secureml: A system for scalable privacy-preserving
    machine learning. In: SP'17: IEEE Symposium on Security and Privacy. pp.
    19–38
  
  RothR10
  Roth, A., Roughgarden, T.: Interactive privacy via the median mechanism. In:
    STOC'10: 42nd ACM Symposium on Theory of Computing. pp. 765–774
  
  YaroslavtsevCPS13
  Yaroslavtsev, G., Cormode, G., Procopiuc, C.M., Srivastava, D.: Accurate and
    efficient private release of datacubes and contingency tables. In: ICDE'13:
    29th IEEE International Conference on Data Engineering,. pp. 745–756
  
  zuur2010protocol
  Zuur, A.F., Ieno, E.N., Elphick, C.S.: A protocol for data exploration to avoid
    common statistical problems. Methods in ecology and evolution  1(1),
     3–14
  
  
  
  