Iterative Constructions and Private Data Release

Introduction

Consider a graph representing the online communications between a set of individuals: each vertex represents a user, and an edge between two users indicates that they have corresponded by email. It might be extremely useful to allow data analysts access to this graph in order to mine it for statistical information. However, the graph is also composed of sensitive information, and we cannot allow our released information to reveal much about the existence of specific edges. Thus we would like a way to analyze the structure of this graph while protecting the privacy of individual edges. Specifically we would like to be able to provide a promise of differential privacy [DMNS06] (defined in Section 2), which, roughly, requires that our algorithms be randomized, and induce nearly the same distribution over outcomes when given two data sets (e.g. graphs) which differ in only a single point (e.g. an edge).

One natural objective is to provide private access to the cut function of this graph. That is, to provide a privacy preserving way for a data analyst to specify any two (of the exponentially many) subsets of individuals, and to discover (up to some error) the number of email correspondences that have passed between these two groups. There are two ways we might try to achieve this goal: We could give an interactive solution where we give the analyst private oracle access to the cut function. Here the user can write down any sequence of cut queries and the oracle will respond with private, approximate answers. We may also try for a stronger, non-interactive solution, in which we release a private synthetic dataset; a new, private graph that approximately preserves the cut function of the original graph.

The case of answering cut queries on a graph is just one instance of the more general problem of query release for exponentially sized families of linear queries on a data set. Although this problem has been extensively studied in the differential privacy literature, we observe that no previously known efficient solution is suitable for the case of releasing all cut queries on graphs. In this paper we provide solutions to this problem in both the interactive and non-interactive settings.

We give a generic framework that converts objects that we call iterative database construction (IDC) algorithms into private query release mechanisms in both the interactive and non-interactive settings. This framework generalizes the median mechanism [RR10], the online multiplicative weights mechanism [HR10], and the offline multiplicative weights mechanism [GHRU11, HLM11]. Our framework gives a simple, modular analysis of all of these mechanisms, which lead to tighter bounds in the interactive setting than those given in [RR10] and [HR10]. These improved bounds are crucial to our objective of giving non-trivial approximations to all possible cut queries. We also instantiate this framework with a new IDC algorithm for arbitrary linear queries that is based on the Frieze/Kannan low-rank matrix decomposition [FK99a] and is tailored to releasing cut queries. This algorithm leads to a new online query release mechanism for linear queries that gives a better approximation in settings (such as we would encounter trying to answer all cut queries on a dense graph) where the database size is comparable to the size of the data universe. We summarize our bounds in Table 1.

We also give a new algorithm (building on techniques for constructing private synthetic data in [BCD+07, DNR+09]) in the non-interactive setting that efficiently generates private synthetic graphs that approximately preserve the cut function. Finally, we use our IDC framework to show that an efficient, private algorithm for the problem of privately computing good rank-1 approximations to symmetric matrices would automatically yield efficient private algorithms for releasing synthetic graphs with improved approximation guarantees.

Our main conceptual contribution is to define the abstraction of iterative database construction algorithms (Section 3) and to show that an efficient IDC for any class of queries $\mathcal{Q}$ automatically yields an efficient private data release mechanism for $\mathcal{Q}$ in both the interactive and non-interactive settings. Informally, IDCs construct a data structure that can be used to answer all the queries in $\mathcal{Q}$ by iteratively improving a hypothesis data structure. Moreover, they update the hypothesis when given a query witnessing a significant difference between the hypothesis data structure and the underlying database.

In hindsight, this framework generalizes the median mechanism [RR10] and the subsequent refinement for linear queries, the online multiplicative weights mechanism [HR10]. It also generalizes the offline multiplicative weights mechanism [GHRU11, HLM11]. All of these mechanisms can be seen to use IDCs of the sort we define in this work. (In Appendix A we show how these algorithms fall into the IDC framework.)

Our generalization and abstraction also allows for a simple, modular analysis of mechanisms based on IDCs. Using this analysis, we are able to show improved bounds on the accuracy of both the median mechanism and multiplicative weights mechanism. These improved bounds are critical to our application to releasing all cut queries. For these parameters, the previous bounds would not guarantee error that is $\leq|E|$, meaning that the error may be larger than the largest cut in the graph. Of course, we can privately guarantee error $\leq|E|$ simply by releasing the answer for every cut query. Our new analysis shows that these mechanism are capable of answering all cut queries with error $o(|E|)$ for sufficiently dense graphs.

We also define a new IDC based on the Frieze/Kannan low-rank matrix decomposition [FK99a], which yields a private interactive mechanism for releasing linear queries. Our new mechanism outperforms previously known techniques when the size of the database is comparable to the size of the data universe, as is the case on a dense graph.

We then consider the problem of efficiently releasing private synthetic data for the class of cut queries. We show that a technique based on randomized response efficiently yields a private data structure (but not a synthetic databse) capable of answering any cut query on a graph with $|V|$ vertices up to maximum error $O(|V|^{1.5})$. We then show how to use this data structure to efficiently construct a synthetic database with only a constant factor blowup in our error. Our algorithm is based on a technique for constructing synthetic data in [BCD+07, DNR+09]. Their observation is that, for linear queries, the set of accurate synthetic databases is described by a (large) set of linear constraints. In the case of cut queries, we are able to use a constant-factor approximation to the cut-norm due to Alon and Naor [AN06] as the separation oracle to find a feasible solution (and thus a synthetic database) efficiently. Finally, we show how the existence of an efficient private algorithm for finding good low-rank approximations to matrices would imply the existence of an improved algorithm for privately releasing synthetic data for cut queries, using our IDC framework.

2 Related Work

Differential privacy was introduced in a series of papers [BDMN05, CDM+05, DMNS06] in the last decade, and has become a standard solution concept for statistical database privacy. The first mechanism for simultaneously releasing the answers to exponentially large classes of statistical queries was given in [BLR08]. They showed that the existence of small nets for a class of queries $\mathcal{Q}$ automatically yields a (computationally inefficient) non-interactive, private algorithm for releasing answers to all the queries in $\mathcal{Q}$ with low error. Subsequent improvements were given by Dwork et al. [DNR+09, DRV10].

Roth and Roughgarden [RR10] showed that large classes of queries could also be released with low error in the interactive setting, in which queries may arrive online, and the mechanism must provide answers before knowing which queries will arrive in the future. Subsequently, Hardt and Rothblum [HR10] gave improved bounds for the online query release problem based on the multiplicative weights algorithm. In hindsight, both of these algorithms follow the same basic framework, which is to use an IDC.

Gupta et al. [GHRU11] gave a non-interactive data release mechanism based on the multiplicative weights algorithm and an arbitrary agnostic learner for a class of queries. An instantiation of this algorithm (the offline multiplicative weights algorithm) using the generic agnostic learner of Kasiviswanathan et al. [KLN+08] (who use the exponential mechanism of [MT07]) was implemented and experimentally evaluated on the task of releasing small conjunctions to low error on real data by Hardt, Ligett, and McSherry [HLM11]. This algorithm gives bounds comparable to those given in this paper, but it does not work in the interactive setting, and is not computationally efficient for settings in which the number of queries is exponentially larger than the database size (as is the case with graph cuts). We note in Section 7 that this generic algorithm can also be instantiated with any iterative database construction algorithm.

The Frieze-Kannan low-rank approximation (or the weak regularity lemma) shows that every matrix can be approximated by a sum of few cut matrices [FK99a, FK99b]: this fact has many important algorithmic applications. We also use the fact that the proof extends to more general settings, as was noted by [TTV09].

Preliminaries

We will generally think of $\epsilon$ as being a small constant, and $\delta$ as being negligibly small – i.e. smaller than any inverse polynomial function of $n$.

We note that when we will discuss interactive mechanisms, we must view the output of a mechanism as a transcript of an interaction between an adaptive adversary who supplies questions about the database based on previous outcomes of the mechanism, and the mechanism itself. For clarity, in this paper we will elide specifics about the model of adaptive private composition. For a detailed treatment of this issue, see [DRV10].

A useful distribution is the Laplace distribution.

A fundamental result in data privacy is that perturbing low sensitivity queries with Laplace noise preserves $(\epsilon,0)$-differential privacy.

It will be useful to understand how privacy parameters for individual steps of an algorithm compose into privacy guarantees for the entire algorithm. The following useful theorem is due to Dwork, Rothblum, and Vadhan:

A common type of queries are linear queries. A linear query $Q$ has a representation as a vector $^{|\mathcal{X}|}$, and can be evaluated on a database by taking the dot product between the query and the histogram representation of the database: $Q(\mathcal{D})=Q\cdot\mathcal{D}$.

We say an algorithm efficiently releases $k$ queries from a class $\mathcal{Q}$ in the interactive setting if on an arbitrary, adaptively chosen stream of queries $Q_{1},\ldots,Q_{k}$, it outputs answers $a_{1},\ldots,a_{k}$. The algorithm must output each $a_{i}$ after receiving query $Q_{i}$ but before receiving $Q_{i+1}$, and is only allowed poly$(n)$ run time per query. We are typically interested in the case when $k$ can be exponentially large in $n$. Note that as far as computational efficiency is concerned, releasing synthetic data for a class of queries $k$ is at least as difficult as releasing queries from $k$ in the interactive setting, since we can use the synthetic data to answer queries interactively.

Graphs and Cuts. When we consider datasets that represent graphs $G=(V,E)$, we think of the database as being the edge set $\mathcal{D}_{G}=E$, and the data-universe being the collection of all possible edges in the complete graph: $|\mathcal{X}|={|V|\choose 2}$. That is, we consider the vertex set to be common among all graphs, which differ only in their edge sets. One example we care about is approximating the cut function of a private graph $G$.

Note that as linear queries, we can write cut queries as the outer product of two vectors: $Q_{S,T}=\chi_{S}\cdot\chi_{T}^{T}$, where $\chi_{S},\chi_{T}\in\{0,1\}^{|V|}$ are the characteristic vectors of the sets $S$ and $T$ respectively. Let us define a more general class of rank-1 queries on graphs to be a subset of all linear queries:

A rank-1 query is a linear query and can be evaluated

Of course the set of rank-1 queries includes the set of cut queries, and any mechanism that is accurate with respect to rank-1 queries is also accurate with respect to cut queries.

Iterative Database Constructions

In this section we define the abstraction of iterative database constructionsthat includes our new Frieze/Kannan construction and several existing algorithm [RR10, HR10] as a special case. Roughly, each of these mechanisms works by maintaining a sequence of data structures $\mathcal{D}^{(1)},\mathcal{D}^{(2)},\dots$ that give increasingly good approximations to the input database $\mathcal{D}$ (in a sense that depends on the IDC). Moreover, these mechanisms produce the next data structure in the sequence by considering only one query $Q$ that distinguishes the real database in the sense that $Q(\mathcal{D}^{(t)})$ differs significantly from $Q(\mathcal{D})$.

$\mathcal{D}^{(1)}=\mathcal{D}(\emptyset,\cdot,\cdot)$,

for every $t=1,2,\dots,C$, $\left|Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{(t)})\right|\geq\alpha$,

for every $t=1,2,\dots,C$, $\left|Q^{(t)}(\mathcal{D})-\widehat{A}^{(t)}\right|<\alpha$,

and for every $t=1,2,\dots,C-1$, $\mathcal{D}^{(t+1)}=\mathbf{U}(\mathcal{D}^{(t)},Q^{(t)},\widehat{A}^{(t)})$.

We note that for all of the iterative database constructions we consider, the approximate answer $\widehat{A}^{(t)}$ is used only to determine the sign of $Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{(t)})$, which is the motivation for requiring that $\widehat{A}^{(t)}$ have error smaller than $\alpha$. The main measure of efficiency we’re interested in from an iterative database construction is the maximum number of updates we need to perform before the database $\mathcal{D}^{(t)}$ approximates $\mathcal{D}$ well with respect to the queries in $\mathcal{Q}$. To this end we define an iterative database construction as follows:

Note that the definition of an $B(\alpha)$-iterative database construction implies that if $\mathbf{U}$ is a $B(\alpha)$-iterative database construction, then given any maximal $(\mathbf{U},\mathcal{D},\mathcal{Q},\alpha,C)$-database update sequence, the final database $\mathcal{D}^{(C)}$ must satisfy $\max_{Q\in\mathcal{Q}}\left|Q(\mathcal{D})-Q(\mathcal{D}^{(C)})\right|\leq\alpha$ or else there would exist another query satisfying property 2 of Definition 3.1, and thus there would exist a $(\mathbf{U},\mathcal{D},\mathcal{Q},\alpha,C+1)$-database update sequence, contradicting maximality.

Query Release from Iterative Database Construction

In this section we describe an interactive algorithm for releasing linear queries using an arbitrary iterative database construction.

Algorithm 1 is $(\epsilon,\delta)$-differentially private.

Our privacy analysis follows the approach of [HR10]. Intuitively, we will consider each round of the mechanism individually, conditioned on the previous rounds and classify each round by the amount of “information leaked” from the database. We will use this classification, as well as Azuma’s Inequality to bound the total amount of information leaked.

Observe that $\mathbf{v}$ and the list of queries $Q^{(1)},\dots Q^{(k)}$We treat all the parameters of the mechanism, $\alpha,\beta,\epsilon,\delta,k$ as well as the query sequence $Q^{(1)},\dots,Q^{(k)}$ as public information. are sufficient to reconstruct the internal state of the mechanism, and thus its output, in each round. Therefore it will be sufficient to demonstrate that a mechanism that releases $\mathbf{v}$ is $(\epsilon,\delta)$-differentially private.

In each round $t=1,2,\dots,k$, we define three ranges for the value of the noise $Z^{(t)}$ that will describe whether or not we were “never”, “sometimes”, or “always” going to do an update in round $t$. Specifically, let $R^{(t)}=Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{(t-1)})$. Note that $R^{(t)}=A^{(t)}-\Lambda^{(t)}$ and that $R^{(t)}+Z^{(t)}=\widehat{A}^{(t)}-\Lambda^{(t)}$. Now let

Intuitively, the event $E_{1}^{(t)}$ corresponds to values of the noise where $\widehat{A}^{(t)}-\Lambda^{(t)}$ is sufficiently small that switching databases could not cause an update. In these rounds, $\mathbf{v}^{(t)}=\bot$ with probability $1$ under both $V_{1}$ and $V_{2}$, so there is no privacy loss. The event $E_{3}^{(t)}$ corresponds to values of the noise where $\widehat{A}^{(t)}-\Lambda^{(t)}$ is sufficiently large that switching databases could not prevent an update. These rounds do leak information about the database, but the update will increment $C$, and thus there can only be $B(\alpha)$ such rounds. The event $E_{2}^{(t)}$ are the problematic rounds. In these rounds we may not update and increment $C$, thus in principle there may be an arbitrary number of these rounds. However, $\widehat{A}^{(t)}-\Lambda^{(t)}$ may be close enough to the update threshold that switching from $\mathcal{D}_{1}$ to $\mathcal{D}_{2}$ would cause an update. Thus these rounds may incur privacy loss. The remainder of the analysis relies on showing that there are not too many such rounds.

Now we make the following claims about the privacy loss in each type of round, based on the properties of the Laplace distribution and the way in which we defined the events $E_{1}^{(t)},E_{2}^{(t)},E_{3}^{(t)}$.

Note that under both conditional measures, the probability of $\mathbf{v}^{(t)}=\bot$ is $1$. ∎

The proof of this claim requires a straightforward analysis of the event $u=\bot$ under both conditional measures. To not interrupt the flow of the larger proof, we defer the details until later. The next claim states that the expected privacy loss is considerably smaller than the worst-case privacy loss.

This claim follows from Claim 4.3 and Theorem 2.4. ∎

In light of the previous claims, we want to bound the number of rounds in which $E_{1}^{(t)}$ does not occur. Let $H=\left|\left\{t\mid Z^{(t)}\not\in E_{1}^{(t)}\right\}\right|$.

With probability $1-\delta/2$, $|H|\leq 16B\log(4/\delta)$.

We now give a high-probability bound on the total privacy loss, conditioned on the event that $|H|\leq 16B\cdot\log(4/\delta)$.

Conditioning on the coins of the mechanism we have

If we condition on the event that $|H|\leq 16B\log(4/\delta)$ then we have

Claims 4.6 and 4.7 suffice to prove the Theorem. ∎

where inequality (2) follows because the sensitivity of $Q^{(t)}$ is bounded above by $1$. Now we will consider the case of $u=\bot$.

2 Utility Analysis

Roughly, the argument is as follows: Assume we did not add any noise to the queries. Then we would answer each query with the true answer $A^{(t)}$ or with $\Lambda^{(t)}$ if $\Lambda^{(t)}$ is sufficiently close to $A^{(t)}$. Thus the only reason the mechanism would fail to be accurate is if it performs too many updates and has to terminate due to the condition $C=B$. But since we only invoke $\mathbf{U}$ when we find a query such that $|Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{(t)})|$ is large, we are actually generating a database update sequence, which cannot be too long if $\mathbf{U}$ is an efficient iterative database construction. To formalize this intuition we have to consider the effect of the noise on this process and show that with high probability the noise remains in a small enough range that this intuition is indeed correct.

Fix any $\alpha,T(\alpha)$, such that $T(\alpha)\in[4\alpha/3,2\alpha]$. For brevity, we use $T$ to denote $T(\alpha)$. First, we observe that, with probability $1-\beta$,

For the rest of the proof we will condition on this event and show that for every $t=1,2,\dots,k$,

Assuming the algorithm has not yet terminated, in step 3 we answer each query with either $\Lambda^{(t)}$ s.t.

(in which case the error is at most $5T/4$); or else we answer directly with $\widehat{A}^{(t)}$, in which case

Now it suffices to show that Algorithm 1 does not prematurely terminate (due to the condition $C=B$) before answering every query, and in particular that the sequence of invocations of $\mathbf{U}$ form an $(\mathbf{U},\mathcal{D},\mathcal{Q},\alpha,C)$-database update sequence. Indeed, if this were the case, then we’d be assured (by Definition 3.2) that after $B$ invocations of $\mathbf{U}$, the resulting database $\mathcal{D}^{*}$ would be $(\alpha,\mathcal{Q})$-accurate. So in every subsequent round we’d have

and we’d never make the $B+1^{st}$ update. So to complete the proof, we show that we satisfy the properties in Definition 3.1. Firstly, in every round in which we invoke $\mathbf{U}$,

so that the update sequence satisfies property 2 of Definition 3.1. Secondly, we have already seen that in every round

so that the update sequence satisfies property 3 of Definition 3.1. Properties 1 and 4 of Definition 3.1 follow by the construction of Algorithm 1. This completes the proof. ∎

In order to get the best accuracy parameters, one can just solve for the equation $\alpha=3T(\alpha)/4$; substituting for $T(\cdot)$, this is the same as solving the following equation for $\alpha$:

The Multiplicative Weights mechanism is $(\epsilon,\delta)$-differentially private and $(\alpha,\beta)$ accurate for:

The Median Mechanism is $(\epsilon,\delta)$-differentially private and $(\alpha,\beta)$ accurate for:

The multiplicative weights and median mechanism subroutines are given in Appendix A. By Theorem A.4, the multiplicative weights subroutine is a $B(\alpha)$-IDC for $B(\alpha)=4n^{2}\log|\mathcal{X}|/\alpha^{2}$. By Theorem A.2, the median mechanism subroutine is a $B(\alpha)$-IDC for $B(\alpha)=n^{2}\log k\log|\mathcal{X}|/\alpha^{2}$. The bounds then follow simply by solving for $\alpha$ in the expression $\alpha=\frac{3000\sqrt{B(\alpha)}\log(4/\delta)\log(k/\beta)}{\epsilon}$. ∎

An Iterative Database Construction Based on Frieze/Kannan

In this section we describe and analyze an iterative database construction based on the Frieze/Kannan “cut decomposition” [FK99a]. Although the style of analysis we use was originally applied specifically to cuts in [FK99a], we use a generalization of their argument to arbitrary linear queries. To our knowledge, such a generalization was first observed in [TTV09].

Note that the sum in Algorithm 2 denotes vector addition.

be $(\mathbf{U}^{FK}_{\alpha},\mathcal{D},\mathcal{Q},\alpha,B)$-database update sequence (Definition 3.1). We want to show that $C\leq\|\mathcal{D}\|_{2}^{2}|\mathcal{X}|/\alpha^{2}$. Specifically, that after $\|\mathcal{D}\|_{2}^{2}|\mathcal{X}|/\alpha^{2}$ invocations of $\mathbf{U}^{FK}_{\alpha}$, the database $\mathcal{D}^{(\|\mathcal{D}\|_{2}^{2}|\mathcal{X}|/\alpha^{2})}$ is $(\alpha,\mathcal{Q})$-accurate for $\mathcal{D}$, and thus there cannot be a sequence of longer than $\|\mathcal{D}\|_{2}^{2}|\mathcal{X}|/\alpha^{2}$ queries that satisfy property 2 of Definition 3.1.

In order to formalize this intuition, we use a potential argument as in [FK99a] to show that for every $t=1,2,\dots,B$, $\mathcal{D}^{(t+1)}$ is significantly closer to $\mathcal{D}$ than $\mathcal{D}^{(t)}$. Specifically, our potential function is the $L_{2}^{2}$ norm of the database $\mathcal{D}-\mathcal{D}^{(t)}$, defined as

Observe that $\|\mathcal{D}-\mathcal{D}^{(1)}\|_{2}^{2}=\|\mathcal{D}\|_{2}^{2}$, and $\|\mathcal{D}\|_{2}^{2}\geq 0$. Thus it suffices to show that in every step, the potential decreases by $\alpha^{2}/|\mathcal{X}|$. We analyze the case where $|Q^{(t)}(\mathcal{D}^{(t)})|<\widehat{A}^{(t)}$, the analysis is the opposite case will be similar. Let $R^{(t)}=\mathcal{D}^{(t)}-\mathcal{D}$. Observe that in this case we have

Now we can analyze the drop in potential.

This bounds the number of steps by $\|\mathcal{D}\|_{2}^{2}|\mathcal{X}|/\alpha^{2}$, and completes the proof. ∎

Algorithm 1, instantiated with $\mathbf{U}^{FK}_{\gamma}$ for $\gamma=O\left(\epsilon^{-1/2}n_{2}^{1/4}|\mathcal{X}|^{1/4}\sqrt{\log(k/\beta)}\right)$ is $(\epsilon,\delta)$-differentially private and an $(\alpha,\beta)$-accurate interactive release mechanism for query set $\mathcal{Q}$ with $\alpha=O\left(\frac{n_{2}^{1/4}|\mathcal{X}|^{1/4}\sqrt{\log(k/\beta)\log(1/\delta)}}{\sqrt{\epsilon}}\right)$ where $n_{2}=\|\mathcal{D}\|_{2}^{2}$. Note that for databases that are subsets of the data universe (rather than multisets), $n_{2}=n$.

Results for Synthetic Data

In this section, we consider the more demanding task of efficiently releasing synthetic data for the class of cut queries on graphs. The task at hand here is to actually generate another graph that approximates the private graph with respect to cuts. Such a graph can then simply be released to data analysts, who can examine it at their leisure. This is preferable to the interactive setting, in which an actual graph is never produced, and a central stateful API must be maintained to handle queries as they come in from data analysts. Our algorithm is simple, and is based on releasing a noisy histogram. Note that for a graph, $|\mathcal{X}|={|V|\choose 2}$, and $\mathcal{D}=E$, so as long as $|E|=\Omega(|V|)$, the universe is at most a polynomial in the database size. (Moreover, it is easy to show that there does not exist any $(\epsilon,0)$-private mechanism that has error $o(|V|)$, so the only interesting cases are when $|E|=\Omega(|V|)$.)

The utility guarantee of this procedure over the collections $\mathcal{Q}$ of linear queries is also not difficult; i.e., each query $Q\in\mathcal{Q}$ is a vector in $^{|\mathcal{X}|}$, and on any database $\mathcal{D}$ evaluates to $Q(\mathcal{D})=\langle Q,\mathcal{D}\rangle$.

Suppose that $\mathcal{Q}\subseteq^{|\mathcal{X}|}$ is some collection of linear queries. For the case $|\mathcal{Q}|\leq(\beta/2)\,2^{|\mathcal{X}|/6}$, it holds that with probability at least $1-\beta$,

for every query $Q\in\mathcal{Q}$. For general $\mathcal{Q}$, the error bound is $O(\varepsilon^{-1}\sqrt{|\mathcal{X}|\log(|\mathcal{X}|/\beta)\log(|\mathcal{Q}|/\beta)})$.

as long as $\alpha\leq|\mathcal{X}|/\varepsilon$. If we set $\alpha=\varepsilon^{-1}\sqrt{12|\mathcal{X}|\log(2|\mathcal{Q}|/\beta)}$ the probability bound on the right hand side at most $\beta$, and the condition $\alpha\leq|\mathcal{X}|/\varepsilon$ translates to $|\mathcal{Q}|\leq(\beta/2)\,2^{|\mathcal{X}|/6}$.

The proof for the general case, where we do not assume a bound on the size $|\mathcal{Q}|$, loses an extra factor of $O(\sqrt{\log(|\mathcal{X}|/\beta)})$. Indeed, with probability at least $1-\beta/2$, each of the absolute values $|Y_{i}|$’s are at most $L=O(1/\varepsilon)\log(|\mathcal{X}|/\beta)$. Now, conditioning on this event happening, the sum $\sum_{i=1}^{|\mathcal{X}|}q_{i}Y_{i}$ behaves like a sum of $|\mathcal{X}|$-many independent $[-L,L]$-bounded random variables with mean : in this case, $\Pr[|\sum_{i}q_{i}Y_{i}|>\alpha]\leq 2e^{-\Omega(\alpha^{2}/(L^{2}|\mathcal{X}|))}=e^{-\Omega(\alpha^{2}\varepsilon^{2}/(|\mathcal{X}|\log(|\mathcal{X}|/\beta)))}$ by a standard Chernoff bound. Now setting $\alpha=O(\varepsilon^{-1}\sqrt{|\mathcal{X}|\log(|\mathcal{X}|/\beta)\log(|\mathcal{Q}|/\beta)})$ causes this probability to be at most $\beta/2$; by a union bound, the probability of large deviations is at most $\beta$. ∎

In summary, note that the bounds on the error are $\approx\varepsilon^{-1}\sqrt{|\mathcal{X}|\log|\mathcal{Q}|}$, with some correction terms depending on whether the size of the query set is at most $2^{O(|\mathcal{X}|)}$ or larger.

with probability at least $1-\beta$. In fact, one can give a slightly tighter analysis where the accuracy depends on the size of the sets $S,T$—by observing that the number of random variables participating in a cut query $(S,T)$ is exactly $|S||T|$, one can show that the accuracy for all cuts is whp $O(\varepsilon^{-1}\sqrt{|V||S||T|})$.

There is a computationally efficient $(\varepsilon,0)$-differentially private randomized algorithm that takes a unweighted graph $G$ and outputs a synthetic graph $G^{\prime}$ such that, with high probability, $\|G-G^{\prime}\|_{C}\leq O(|V|^{3/2}/\varepsilon)$—all cuts in $G$ and $G^{\prime}$ are within $O(|V|^{3/2}/\varepsilon)$ additive error.

First we construct the noisy datastructure $\widehat{D}$ by perturbing each entry of $\mathcal{D}$ with independent noise drawn from Lap$(1/\epsilon)$. All further operations will be conducted on $\widehat{D}$, and so the entire algorithm will be $(\epsilon,0)$-differentially private. let $z_{i,j}$ denote the $i,j$’th entry of $\widehat{D}$: i.e. $z_{i,j}=\mathcal{D}[i,j]+\textrm{Lap}(1/\epsilon)$. Let us condition on the event that for every cut $(S,T)$, the additive error bound is $O(|V|^{3/2}/\varepsilon)$. Now define the following LP:

There exists a feasible solution to this LP with $\lambda=O(|V|^{3/2}/\varepsilon)$, since we can just use the original graph to get the solution $x_{ij}=\mathbf{1}_{(ij\in E(G))}$. Now if we solve the LP, and output the optimal feasible solution to the LP, it would be a weighted graph $G^{\prime}$ such that $\|G-G^{\prime}\|_{C}\leq O(|V|^{3/2}/\varepsilon)$.

Since the LP has exponentially many constraints, it remains to show how to solve the LP. Define the matrix $A$ with $A_{ij}=x_{ij}-z_{ij}$, and define $A(S,T):=\sum_{i\in S,j\in T}A_{ij}$, then the separation oracle must find sets $S,T$ such that $|A(S,T)|$ is larger than $\lambda$. Equivalently, it suffices to approximately compute the cut norm of the matrix $A$. There is a constant-factor approximation algorithm of Alon and Naor for the cut norm problem [AN06]; using this we can solve the LP above to within constant factors of optimum. ∎

The procedure outlined above results in outputting a weighted graph (with non-negative edge weights) $\mathcal{D}^{\prime}\in^{|V|\times|V|}$. Note that if the original graph was unweighted: $\mathcal{D}\in\{0,1\}^{|V|\times|V|}$ and it is desired to output another unweighted graph, we can simply randomly round $\mathcal{D}^{\prime}$ to an integral solution in the obvious way. This does not incur any asymptotic loss in the stated accuracy bound.

2 A Spectral Solution, and Rank-111 Queries

The Alon-Naor algorithm involves solving SDPs which are computationally intensive, but we can avoid that by using the tighter accuracy bound of $O(\varepsilon^{-1}\sqrt{|V||S||T|})$ we proved. Consider the modified LP:

Again, this LP has a feasible solution (whp) with $\lambda=O(|V|^{1/2}/\varepsilon)$. And solving the LP to within a factor of $\rho$, and outputting a near-optimal feasible solution to the LP would give a synthetic weighted graph $G^{\prime}$ such that $\|G-G^{\prime}\|_{C}\leq O(\rho\cdot\sqrt{|V||S||T|}/\varepsilon)=O(\rho\cdot|V|^{3/2}/\varepsilon)$. To this end, define the normalized cut norm as

Now the separation problem is to find $S,T$ approximately maximizing the normalized cut norm. For this we use a theorem of Nikiforov [Nik09] which says that if $\sigma_{1}(A)$ is the top singular value of $A$ (and $\|A\|_{2}$ is $A$’s spectral norm) then

There is also a polynomial-time algorithm that given the top singular value/vector for $A$, returns a normalized cut $(S^{\prime},T^{\prime})$ of value $|A(S^{\prime},T^{\prime})|/\sqrt{|S^{\prime}||T^{\prime}|}\geq\sigma_{1}(A)/O(\log|V|)\geq\|A\|_{NC}/O(\log|V|)$. Using this as a separation oracle we can solve the LP to within $\rho=O(\log|V|)$ of the optimum, and hence get an additive error of $O(\varepsilon^{-1}\log|V|\sqrt{|V||S||T|})=O(\varepsilon^{-1}|V|^{3/2}\log|V|)$.

We note that the theorem of Nikiforov quoted above [Nik09] also implies that the synthetic graph released by our algorithm is useful for the (infinite) set of rank-1 queries $\mathcal{Q}_{r1}$ as well as the set of cut queries, with only an $O(\log|V|)$ factor loss in the additive approximation for each query.

3 A Tail Bound for Laplace Distributions

The following tail bound for Laplace random variables uses standard techniques, we give it here for completeness.

where we used the Taylor series expansion (and hence need that $|q_{i}bt|<1$). The last expression only worsens as the $q_{i}$’s increase, so the worst case is when all $q_{i}=1$, when we get a bound of

Let us set $t:=\frac{\alpha}{2kb^{2}}$. Recall that we needed the condition that $t\in[0,1/b]$, so let us assume that $\alpha\leq kb$. This implies that $tb=\alpha/2kb\leq 1/2$. Hence, plugging in this setting for $t$, and noting that $(1-(tb)^{2})\geq 3/4$, we get

This completes the proof for the case $\alpha\leq kb$. Now suppose $\alpha>kb$; in that case let us set $t=1/2b$—substituting this into (6) gives us a tail bound of $\exp(-\alpha/2b+k/3)$. And since $\alpha>kb$, this is bounded by $\exp(-\alpha/6b)$. This proves the theorem. ∎

Towards Improving on Randomized Response for Synthetic Data

In this section, we consider one possible avenue towards giving an efficient algorithm for privately generating synthetic data for graph cuts that improves over randomized response. We first show how generically, any efficient Iterative Database Construction algorithm can be used to give an efficient offline algorithm for privately releasing synthetic data when paired with an efficient distinguisher. The analysis here follows the analysis of [GHRU11], who analyzed the corresponding algorithm when instantiated with the multiplicative weights algorithm, rather than a generic Iterative Database Construction algorithm.

We will pair an Iterative Database Construction algorithm for a class of queries ${\cal C}$ with a corresponding distinguisher.

Note that in [GHRU11], we referred to a distinguisher as an agnostic learner. Indeed, a distinguisher is solving the agnostic learning problem for its corresponding set of queries. We here refer to it as a distinguisher to emphasize its applicability beyond the typical realm of learning (e.g. we here hope to apply a distinguisher to a graph cuts problem).

What follows is a formal analysis, but the intuition for the mechanism is simple: we simply run the iterative database construction algorithm to construct a hypothesis that approximately matches $\mathcal{D}$ with respect to the queries ${\cal C}$. If our distinguisher succeeds in finding a query that has high discrepancy between the hypothesis database and the true database whenever one exists, then our IDC algorithm will output a database that is $\beta$-accurate with respect to ${\cal C}$. This requires at most $T$ iterations, and so we access the data only $2T$ times using $(\epsilon_{0},0)$-differentially private methods (running the given distinguisher, and then checking its answer with the Laplace mechanism). Privacy will therefore follow from the composition theorem.

Given parameters $\epsilon,\delta<1$, The IC mechanism is $(\epsilon,\delta)$ differentially private.

The mechanism accesses the data at most $2B(\alpha)$ times using algorithms that are $\epsilon_{0}$-differentially private. By Theorem LABEL:thm:eps-delta-composition, the mechanism is therefore $(\epsilon^{\prime},\delta)$-differentially private for $\epsilon^{\prime}=\sqrt{4B(\alpha)\ln(1/\delta)}\epsilon_{0}+2B(\alpha)\epsilon_{0}(e^{\epsilon_{0}}-1)$. Plugging in our choice of $\epsilon_{0}$ proves the claim. ∎

Given an $(F(\epsilon),\gamma)$-private distinguisher and a $B(\alpha)$-IDC, the Iterative Construction mechanism is $\alpha,\beta$ accurate for:

so long as $\gamma\leq\beta/(2B(\alpha))$.

The analysis is straightforward. First we observe that because the algorithm runs for at most $B(\alpha)$ steps, except with probability at most $\beta/2$, for all $t$:

Note that by assumption, $\gamma\leq\beta/(2B(\alpha))$, so we also have that except with probability $\beta/2$,

For the rest of the argument, we will condition on both of these events occurring, which is the case except with probability $\beta$. There are two cases. Either a database $\mathcal{D}^{\prime}=D^{B(\alpha)}$ is output, or database $\mathcal{D}^{\prime}=D^{t-1}$ for $t\leq B(\alpha)$ is output. First, suppose $\mathcal{D}^{\prime}=D^{B(\alpha)}$. Since for all $t$ $|\widehat{A}^{(t)}-Q^{(t)}(D^{t-1})|\geq 3\alpha/4$ and by our conditioning, $|\widehat{A}^{(t)}-Q^{(t)}(\mathcal{D})|\leq\frac{\alpha}{4}$, the sequence $(D^{t},Q^{(t)},\widehat{A}^{(t)})$, formed a maximal $(\mathbf{U}_{\alpha/2},\mathcal{D},\mathcal{Q},\alpha/2,B(\alpha))$-Database Update Sequence. Therefore, we have that $\max_{Q\in\mathcal{Q}}|Q(\mathcal{D})-Q(\mathcal{D}^{\prime})|\leq\alpha/2$ as desired. Next, suppose $\mathcal{D}^{\prime}=D^{t-1}$ for $t\leq B(\alpha)$. Then it must have been the case that for some $t$, $|\widehat{A}^{(t)}-Q^{(t)}(D^{t-1})|<3\alpha/4$. By our conditioning, in this case it must be that $Q^{(t)}(\mathcal{D})-Q^{(t)}(D^{t-1})<\alpha/2$, and that therefore by the properties of an $(F(\epsilon_{0}),\gamma)$-distinguisher:

Note that the running time of the algorithm is dominated by the running time of the IDC algorithm and of the distinguishing algorithm: efficient IDC algorithms paired with efficient distinguishing algorithms for a class of queries $\mathcal{Q}$ automatically correspond to efficient algorithms for privately releasing synthetic data useful for $\mathcal{Q}$. For the class of graph cut queries, both the multiplicative weights IDC and the Frieze/Kannan IDC are computationally efficient. Therefore, one approach to finding a computationally efficient algorithm for releasing synthetic data useful for cut queries is to find an efficient private distinguishing algorithm for cut queries.

One curious aspect of this approach is that it might in fact be computationally easier to release a larger class of queries than cut queries, even though this is a strictly more difficult task from an information theoretic perspective. For example, solving the distinguishing problem for cut queries on graphs $\mathcal{D}$ and $\mathcal{D}^{\prime}$ is equivalent to finding a pair of sets $(S,T)$ which witness the cut-norm on the graph $\mathcal{D}-\mathcal{D}^{\prime}$. On the other hand, solving the distinguishing problem for rank-1 queries (which include cut queries, and are a larger class) is equivalent to finding the best rank-1 approximation to the adjacency matrix $\mathcal{D}-\mathcal{D}^{\prime}$. The former problem is NP-hard, whereas the latter problem can be quickly solved non-privately using the singular value decomposition.

An efficient $(F(\epsilon),\gamma)$-distinguisher for the class of rank-1 queries for $F(\epsilon)=T/\epsilon$ would yield an $(\alpha,\beta)$-accurate mechanism for releasing synthetic data for graph cuts (and all rank-1 queries) for any $\beta\geq\Omega(\exp(-\epsilon T))$ and: $\alpha_{MW}=2\sqrt{2}\epsilon^{-1/2}\sqrt{Tm}\left(\log|V|\log(1/\delta)\right)^{1/4}$ using the multiplicative weights IDC, or: $\alpha_{FK}\geq 2\epsilon^{-1/2}(m\log(1/\delta))^{1/4}\sqrt{|V|T}$ using the Frieze/Kannan IDC

The Multiplicative Weights mechanism is a $B(\alpha)$-IDC for the class of rank-1 queries on graphs with $m=|E|$ edges and $|V|$ vertices for $B(\alpha)=2m^{2}\log|V|/\alpha^{2}$. We can set:

The Frieze/Kannan algorithm is a $B(\alpha)$-IDC with $B(\alpha)=m|V|^{2}/\alpha^{2}$. We can set:

This paper benefited from interactions with many people. We particularly thank Moritz Hardt and Kunal Talwar for extensive, enlightening discussions. In particular, the observation that randomized response leads to a data structure for graph cuts with error $O(|V|^{1.5})$ is due to Kunal Talwar. We thank Salil Vadhan for helpful discussions about the Frieze/Kannan low-rank matrix decomposition, and Frank McSherry and Adam Smith for helpful discussions about algorithms for computing low-rank matrix approximations. We thank Cynthia Dwork for always fruitful conversations.

References

Appendix A Other Iterative Database Construction Algorithms

In this section, we demonstrate how the median mechanism and the multiplicative weights mechanism fit into the IDC framework. These mechanisms apply to general classes of linear queries $\mathcal{Q}$.

In this section, we show how to use the median database subroutine as an Iterative Database Construction.

The Median Mechanism algorithm is a $B(\alpha)=n^{2}\log|\mathcal{X}|\log k/\alpha^{2}$ iterative database construction algorithm for every class of $k$ linear queries $\mathcal{Q}$.

For any set of $k$ linear queries $\mathcal{Q}$ and any database $\mathcal{D}$ of size $n$, there is a database $\mathcal{D}^{\prime}$ of size $|\mathcal{D}^{\prime}|=n^{2}\log k/\alpha^{2}$ so that $\mathcal{D}^{\prime}$ is $\alpha$-accurate for $\mathcal{D}$ with respect to $\mathcal{Q}$.

From this claim, we have that $|\mathbf{D}^{t}|\geq 1$ for all $t$, and so can always be used to evaluate queries. On the other hand, each update step eliminates half of the databases in the median datastructure: $|\mathbf{D}^{t}|=|\mathbf{D}^{t-1}|/2$. This is because the update step eliminates every database either above or below the median with respect to the last query. Initially $|\mathbf{D}^{0}|=|\mathcal{X}|^{n^{2}\log k/\alpha^{2}}$, and so there can be at most $B(\alpha)\leq\log n^{2}|\mathcal{X}|\log k/\alpha^{2}$ update steps before we would have $|\mathbf{D}^{B}|<1$, a contradiction. ∎

A.2 The Multiplicative Weights Mechanism

In this section we show how to use the multiplicative weights subroutine as an Iterative Database Construction. The analysis of the multiplicative weights algorithm is not new, and follows [HR10]. It will be convenient to think of our databases in this section as probability distributions, i.e. normalized so that $||\mathcal{D}||_{1}=1$. Note that if we are $\alpha/n$ accurate for the normalized database, we are $\alpha$-accurate for the un-normalized database with respect to any set of linear queries.

The Multiplicative Weights algorithm is a $B(\alpha)=4n^{2}\log|\mathcal{X}|/\alpha^{2}$ iterative database construction algorithm for every class of linear queries $\mathcal{Q}$.

For all $t$: $\Psi_{t}\geq 0$, and $\Psi_{0}\leq\log|\mathcal{X}|$.

We will argue that in every step for which $|Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{t})|\geq\alpha/n$ the potential drops by at least $\alpha^{2}/4n$. Because the potential begins at $\log|\mathcal{X}|$, and must always be non-negative, we know that there can be at most $B(\alpha)\leq 4n^{2}\log|X|/\alpha^{2}$ steps before the algorithm outputs a database $\mathcal{D}^{t}$ such that $\max_{Q\in\mathcal{Q}}|Q(\mathcal{D})-Q(\mathcal{D}^{t})|<\alpha/n$, which is exactly the condition that we want.

The rest of the proof now follows easily. By the conditions of an iterative database construction algorithm, $|\widehat{A}^{(t)}-Q^{(t)}(\mathcal{D})|\leq\alpha/(2n)$. Hence, for each $t$ such that $|Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{t})|\geq\alpha/n$, we also have that $Q^{(t)}(\mathcal{D})>Q^{(t)}(\mathcal{D}_{t})$ if and only if $\widehat{A}^{(t)}>Q^{(t)}(\mathcal{D}_{t})$. In particular, $r_{t}=Q^{(t)}$ if $Q^{(t)}(\mathcal{D}^{t})-Q^{(t)}(\mathcal{D})\geq\alpha/n$, and $r_{t}=1-Q^{(t)}$ if $Q^{(t)}(\mathcal{D})-Q^{(t)}(\mathcal{D}^{t})\geq\alpha/n$. Therefore, by Lemma A.6 and the fact that $\eta=\alpha/2n$: