Differentially Private Data Publishing and Analysis: A Survey <s> Graph Data Publishing <s> We introduce a new, generic framework for private data analysis.The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains.Our framework allows one to release functions f of the data withinstance-based additive noise. That is, the noise magnitude is determined not only by the function we want to release, but also bythe database itself. One of the challenges is to ensure that the noise magnitude does not leak information about the database. To address that, we calibrate the noise magnitude to the smoothsensitivity of f on the database x --- a measure of variabilityof f in the neighborhood of the instance x. The new frameworkgreatly expands the applicability of output perturbation, a technique for protecting individuals' privacy by adding a smallamount of random noise to the released statistics. To our knowledge, this is the first formal analysis of the effect of instance-basednoise in the context of data privacy. Our framework raises many interesting algorithmic questions. Namely,to apply the framework one must compute or approximate the smoothsensitivity of f on x. We show how to do this efficiently for several different functions, including the median and the cost ofthe minimum spanning tree. We also give a generic procedure based on sampling that allows one to release f(x) accurately on manydatabases x. This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of f is known orwhen f is given as a black box. We illustrate the procedure by applying it to k-SED (k-means) clustering and learning mixtures of Gaussians. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Graph Data Publishing <s> We develop algorithms for the private analysis of network data that provide accurate analysis of realistic networks while satisfying stronger privacy guarantees than those of previous work. We present several techniques for designing node differentially private algorithms, that is, algorithms whose output distribution does not change significantly when a node and all its adjacent edges are added to a graph. We also develop methodology for analyzing the accuracy of such algorithms on realistic networks. ::: ::: The main idea behind our techniques is to 'project' (in one of several senses) the input graph onto the set of graphs with maximum degree below a certain threshold. We design projection operators, tailored to specific statistics that have low sensitivity and preserve information about the original statistic. These operators can be viewed as giving a fractional (low-degree) graph that is a solution to an optimization problem described as a maximum flow instance, linear program, or convex program. In addition, we derive a generic, efficient reduction that allows us to apply any differentially private algorithm for bounded-degree graphs to an arbitrary graph. This reduction is based on analyzing the smooth sensitivity of the 'naive' truncation that simply discards nodes of high degree. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Graph Data Publishing <s> We introduce the notion of restricted sensitivity as an alternative to global and smooth sensitivity to improve accuracy in differentially private data analysis. The definition of restricted sensitivity is similar to that of global sensitivity except that instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over a restricted class of datasets. Specifically, given a query f and a hypothesis H about the structure of a dataset D, we show generically how to transform f into a new query f_H whose global sensitivity (over all datasets including those that do not satisfy H) matches the restricted sensitivity of the query f. Moreover, if the belief of the querier is correct (i.e., D is in H) then f_H(D) = f(D). If the belief is incorrect, then f_H(D) may be inaccurate. We demonstrate the usefulness of this notion by considering the task of answering queries regarding social-networks, which we model as a combination of a graph and a labeling of its vertices. In particular, while our generic procedure is computationally inefficient, for the specific definition of H as graphs of bounded degree, we exhibit efficient ways of constructing f_H using different projection-based techniques. We then analyze two important query classes: subgraph counting queries (e.g., number of triangles) and local profile queries (e.g., number of people who know a spy and a computer-scientist who know each other). We demonstrate that the restricted sensitivity of such queries can be significantly lower than their smooth sensitivity. Thus, using restricted sensitivity we can maintain privacy whether or not D is in H, while providing more accurate results in the event that H holds true. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Graph Data Publishing <s> Existing differential privacy (DP) studies mainly consider aggregation on data sets where each entry corresponds to a particular participant to be protected. In many situations, a user may pose a relational algebra query on a database with sensitive data, and desire differentially private aggregation on the result of the query. However, no existing work is able to release such aggregation when the query contains unrestricted join operations. This severely limits the applications of existing DP techniques because many data analysis tasks require unrestricted joins. One example is subgraph counting on a graph. Furthermore, existing methods for differentially private subgraph counting support only edge DP and are subject to very simple subgraphs. Until recent, whether any nontrivial graph statistics can be released with reasonable accuracy for arbitrary kind of input graphs under node DP was still an open problem. In this paper, we propose a novel differentially private mechanism that supports unrestricted joins, to release an approximation of a linear statistic of the result of some positive relational algebra calculation over a sensitive database. The error bound of the approximate answer is roughly proportional to the empirical sensitivity of the query --- a new notion that measures the maximum possible change to the query answer when a participant withdraws its data from the sensitive database. For subgraph counting, our mechanism provides a solution to achieve node DP, for any kind of subgraphs. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Graph Data Publishing <s> We present efficient algorithms for releasing useful statistics about graph data while providing rigorous privacy guarantees. Our algorithms work on datasets that consist of relationships between individuals, such as social ties or email communication. The algorithms satisfy edge differential privacy, which essentially requires that the presence or absence of any particular relationship be hidden. Our algorithms output approximate answers to subgraph counting queries. Given a query graph H, for example, a triangle, k-star, or k-triangle, the goal is to return the number of edge-induced isomorphic copies of H in the input graph. The special case of triangles was considered by Nissim et al. [2007] and a more general investigation of arbitrary query graphs was initiated by Rastogi et al. [2009]. We extend the approach of Nissim et al. to a new class of statistics, namely k-star queries. We also give algorithms for k-triangle queries using a different approach based on the higher-order local sensitivity. For the specific graph statistics we consider (i.e., k-stars and k-triangles), we significantly improve on the work of Rastogi et al.: our algorithms satisfy a stronger notion of privacy that does not rely on the adversary having a particular prior distribution on the data, and add less noise to the answers before releasing them. We evaluate the accuracy of our algorithms both theoretically and empirically, using a variety of real and synthetic datasets. We give explicit, simple conditions under which these algorithms add a small amount of noise. We also provide the average-case analysis in the Erdős-Renyi-Gilbert G(n,p) random graph model. Finally, we give hardness results indicating that the approach Nissim et al. used for triangles cannot easily be extended to k-triangles (hence justifying our development of a new algorithmic approach). <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Graph Data Publishing <s> Protecting the privacy of individuals in graph structured data while making accurate versions of the data available is one of the most challenging problems in data privacy. Most efforts to date to perform this data release end up mired in complexity, overwhelm the signal with noise, and are not effective for use in practice. In this paper, we introduce a new method which guarantees differential privacy. It specifies a probability distribution over possible outputs that is carefully defined to maximize the utility for the given input, while still providing the required privacy level. The distribution is designed to form a 'ladder', so that each output achieves the highest 'rung' (maximum probability) compared to less preferable outputs. We show how our ladder framework can be applied to problems of counting the number of occurrences of subgraphs, a vital objective in graph analysis, and give algorithms whose cost is comparable to that of computing the count exactly. Our experimental study confirms that our method outperforms existing methods for counting triangles and stars in terms of accuracy, and provides solutions for some problems for which no effective method was previously known. The results of our algorithms can be used to estimate the parameters of suitable graph models, allowing synthetic graphs to be sampled. <s> BIB006
With the significant growth of online social networks (OSNs), graph data has raised concern among OSN participants. An OSN dataset can be modeled as an undirected graph G ¼ ðV; EÞ. We use V to denote nodes and use E V Â V to denote edges. In an OSN, nodes normally represent individuals while edges denote their relationships. Two concepts of differential privacy in graph data have been defined: node differential privacy and edge differential privacy. Edge Differential Privacy. Edge Differential Privacy ensures that a query's answer does not reveal the inclusion or removal of a particular edge in the graph. Two graphs are neighboring if they differ in one edge. The first differential privacy research into graph data was conducted by Nissim BIB001 , who showed how to evaluate the number of triangles in a social network with edge differential privacy. They use local sensitivity, which limits the sensitivity tightly with an upper bound, and show how to efficiently calibrate the noise for subgraph counts accordingly. The results of this technique were investigated by Karwa et al. BIB005 to release counts on k-triangles and k-stars. They achieved -differential privacy for k-star counting, and ð; dÞ-differential privacy for k-triangle counting. Zhang et al. BIB006 claim that if one can find an isomorphic graph with proper statistical properties that is similar to the original graph, the isomorphic graph can be used to generate accurate query answers. Given a subgraph G 0 , they adopted an exponential mechanism to search a number of isomorphic copies of G 0 to answer subgraph queries. Node differential privacy. In node differential privacy, two graphs are considered to be neighboring if one of them is generated by removing one node and all the edges related to this node from the other graph. Node differential privacy is more strict than edge differential privacy. The sensitivities resulting from the change of one node are proportional to the graph size. With the observation that many useful statistics have low sensitivities on graphs G u with a small degree u, a common approach to achieve node differential privacy is to transform the graph G to a u-degree-bounded graph G u , in which the nodes with degrees of more than u are deleted BIB002 , BIB003 . Chen et al. BIB004 proposed an iteration mechanism for node differential privacy. Given a graph G and any real-valued function f, they defined a sequence of real-valued functions 0 ¼ f 0 ðGÞ f 1 ðGÞ Á Á Á f m ðGÞ ¼ fðGÞ with a recursive monotonicity property. The recursive approach will return subgraph counting for any kind of subgraph with node differential privacy. However, constructing the sequence of functions f i ðGÞ is usually NP-hard, and efficiently implementing it remains an open problem. Discussion. Existing methods work reasonably well with edge differential privacy or even node differential privacy for basic graph statistics. However, releasing specific statistics, such as cuts, pairwise distances between nodes, or on hyper-graphs, still remain open issues.