R2T: Instance-Optimal Truncation for Differentially Private Query Evaluation with Foreign Keys

1.1 The truncation mechanism.

The issue above was first identified by Kotsogiannis et al.,²¹ who also formalized the DP policy for relational databases with foreign key (FK) constraints. The essence of their model (a rigorous definition is given in Section 2) is that individuals and their private data are stored in separate relations linked by FKs. This is perhaps the most crucial feature of the relational model, yet it causes a major difficulty in designing DP mechanisms as illustrated above. Their solution is the truncation mechanism, which simply deletes all customers with more than $\tau$ orders before applying the Laplace mechanism, for some threshold $\tau$. After truncation, the query has sensitivity $\tau$, so adding a noise of scale $\tau$ is sufficient.

Truncation is a special case of Lipshitz extensions and has been studied extensively for graph pattern-counting queries²⁰ and machine learning (ML).¹ A well-known issue for the truncation mechanism is the bias-variance trade-off: In one extreme $\tau =G{S}_Q$; it degenerates into the naive Laplace mechanism with a large noise (that is, large variance). In the other extreme $\tau =0$, the truncation introduces a bias as large as the query answer. The issue of how to choose a near-optimal $\tau$ has been extensively studied in the statistics and ML communities.^2,17 In fact, the particular query in Example 1.1 is equivalent to the 1-dimensional mean (sum) estimation problem, which is important for many ML tasks. A key challenge there is that the selection of $\tau$ must also be done in a DP manner.

1.2 The issue with self-joins.

While self-join-free queries are equivalent to mean (sum) estimation (see Section 3 for a more formal statement), self-joins introduce another challenge unique to relational queries. In particular, all techniques from the statistics and machine-learning literature for choosing a $\tau$ critically rely on the fact that the individuals are independent, that is, adding/removing one individual does not affect the data associated with another, which is not true when the query involves self-joins. In fact, when there are self-joins, even the truncation mechanism itself fails, as illustrated in the example below.

The reason why the truncation mechanism fails is that the underlined claim above does not hold in the presence of self-joins. More fundamentally, this is due to the correlation among the individuals introduced by self-joins. In the example above, we see that the addition of one node may cause the degrees of many others to increase. For the problem of graph pattern counting under node-DP, which can be formulated as a multi-way self-join counting query on the special schema $R=\{\mathrm{Node}\left(\underset{\_}{\mathrm{ID}}\right)$, $\mathrm{Edge}(\mathrm{src},\mathrm{dst})\}$, Kasiviswanathan et al.²⁰ propose an LP-based truncation mechanism (to differentiate, we will call the truncation mechanism above naive truncation) to fix the issue, but they do not study how to choose $\tau$. As a result, while their mechanism satisfies DP, there is no optimality guarantee in terms of utility. In fact, if $\tau$ is chosen inappropriately, their error can be even larger than $G{S}_Q$, namely, worse than the naive Laplace mechanism.

1.3 Our contributions.

In this paper, we start by studying how to choose a near-optimal $\tau$ in a DP manner in the presence of self-joins. As with all prior $\tau$-selection mechanisms over mean (sum) estimation^2,17 and self-join-free queries,²⁴ we assume that the global sensitivity of the given query $Q$ is bounded by $G{S}_Q$. Since one tends to set a large $G{S}_Q$ as argued in Example 1.1, we must try to minimize the dependency on $G{S}_Q$.

The first contribution of this paper (Section 4) is a simple and general DP mechanism, called Race-to-the-Top (R2T), which can be used to adaptively choose $\tau$ in combination with any valid DP truncation mechanism that satisfies certain properties. In fact, it does not choose $\tau$ per se; instead, it directly returns a privatized query answer with error at most $O(log\left(G{S}_Q\right)loglog\left(G{S}_Q\right)·D{S}_Q\left(I\right))$ for any instance $I$ with constant probability. While we defer the formal definition of $D{S}_Q\left(I\right)$ to Section 3, what we can show is that it is an per-instance lower bound, that is, any valid DP mechanism has to incur error $\Omega \left(D{S}_Q\left(I\right)\right)$ on $I$ (in a certain sense). Thus, the error of R2T is instance-optimal up to logarithmic factors in $G{S}_Q$. Furthermore, a logarithmic dependency on $G{S}_Q$ is also unavoidable,¹⁹ even for the mean estimation problem, that is, the simple self-join-free query in Example 1.1. In practice, these log factors are usually between 10 to 100, and our experiments show that R2T has better utility than previous methods in most cases.

However, as we see in Example 1.2, naive truncation is not a valid DP mechanism in the presence of self-joins. As our second contribution (Section 5), we extend the LP-based mechanism of Kasiviswanathan et al,²⁰ which only works for graph pattern-counting queries, to general queries on an arbitrary relational schema that uses the four basic relational operators: Selection (with arbitrary predicates), Projection, Join (including self-join), and sum Aggregation. When plugged into R2T, this yields the first DP mechanism for answering arbitrary SPJA queries in a database with FK constraints. For SJA queries, the utility is instance-optimal, while the optimality guarantee for SPJA queries is slightly weaker, but we argue that this is unavoidable.

Furthermore, the simplicity of our mechanism allows it to be built on top of any RDMBS and an LP solver. To demonstrate its practicality, we built a system prototype (Section 7) using PostgreSQL and CPLEX. Experimental results (Section 8) show it can provide order-of-magnitude improvements in terms of utility over the state-of-the-art DP-SQL engines. We obtain similar improvements even over node-DP mechanisms specifically designed for graph pattern-counting problems, which are just special SJA queries.

2.1 Database queries.

Let $R$ be a database schema. We start with a multi-way join:

where $R_1,\dots ,R_n$ are relation names in $R$ and each $x_i$ is a set of $arity\left(R_i\right)$ variables. When considering self-joins, there can be repeats, i.e., $R_i=R_j$; in this case, we must have $x_i\ne x_j$, or one of the two atoms will be redundant. Let $var\left(J\right):=x_1\cup \cdots \cup x_n$.

Let $I$ be a database instance over $R$. For any $R\in R$, denote the corresponding relation instance in $I$ as $I\left(R\right)$. This is a physical relation instance of $R$. We use $I(R,x)$ to denote $I\left(R\right)$ after renaming its attributes to $x$, which is also called a logical relation instance of $R$. When there are self-joins, one physical relation instance may have multiple logical relation instances; they have the same rows but with different column (variable) names.

A JA or an SJA query $Q$ aggregates over the join results $J\left(I\right)$. More abstractly, let $\psi :\mathrm{dom}\left(var\right(J\left)\right)\to N$ be a function that assigns non-negative integer weights to the join results, where $\mathrm{dom}\left(var\right(J\left)\right)$ denotes the domain of $var\left(J\right)$. The result of evaluating $Q$ on $I$ is

Note that the function $\psi$ only depends on the query. For a counting query, $\psi (·)\equiv 1$; for an aggregation query, for example, $\mathrm{SUM}(A*B)$, $\psi \left(q\right)$ is the value of $A*B$ for $q$. And an SJA query with an arbitrary predicate over $var\left(J\right)$ can be easily incorporated into this formulation: If some $q\in J\left(I\right)$ does not satisfy the predicate, we simply set $\psi \left(q\right)=0$.

2.2 DP in relational databases with FK constraints.

We adopt the DP policy in Kotsogiannis. et al,²¹ which defines neighboring instances by taking FK constraints into consideration. We model all the FK relationships as a directed acyclic graph (DAG) over $R$ by adding a directed edge from $R$ to $R^{\prime }$ if $R$ has an FK referencing the PK of $R^{\prime }$. There is a.^a designated primary private relation $R_P$, and any relation that has a direct or indirect FK referencing $R_P$ is called a secondary private relation. The referencing relationship over the tuples is defined recursively as follows: (1) any tuple $t_P\in I\left(R_P\right)$ said to reference itself; (2) for $t_P\in I\left(R_P\right)$, $t\in I\left(R\right),t^{\prime }\in I\left(R^{\prime }\right)$, if $t^{\prime }$ references $t_P$, $R$ has an FK referencing the PK of $R^{\prime }$, and the FK of $t$ equals the PK of $t^{\prime }$, then we say that $t$ references $t_P$. Then two instances $I$ and $I^{\prime }$ are considered neighbors if $I^{\prime }$ can be obtained from $I$ by deleting a set of tuples, all of which reference the same tuple $t_P\in I\left(R_P\right)$, or vice versa. In particular, $t_P$ may also be deleted, in which case all tuples referencing $t_P$ must be deleted in order to preserve the FK constraints. Finally, for a join result $q\in J\left(I\right)$, we say that $q$ references $t_P\in I\left(R_P\right)$ if $|t_P\bowtie q|=1$.

We use the notation $I\sim I^{\prime }$ to denote two neighboring instances and $I{\sim }_{t_P}{I}^{\prime }$ denotes that all tuples in the difference between $I$ and $I^{\prime }$ reference the tuple $t_P\in R_P$.

Some queries, as given, may be incomplete, that is, it has a variable that is an FK but its referenced PK does not appear in the query $Q$. The query in Example 2.1 is such an example. Following Kotsogiannis. et al,²¹ we always make the query complete by iteratively adding those relations whose PKs are referenced to $Q$. The PKs will be given variable names matching the FKs. For example, for the query in Example 2.1, we add $\mathrm{Node}\left(A\right)$, $\mathrm{Node}\left(B\right)$, $\mathrm{Node}\left(C\right)$, and $\mathrm{Node}\left(D\right)$.

The DP policy above incorporates both edge-DP and node-DP, two commonly used DP policies for private graph analysis, as special cases. In Example 2.1, by designating $\mathrm{Edge}$ as the private relation ($\mathrm{Node}$ is thus public, and we may even assume it contains all possible vertex IDs), we obtain edge-DP; for node-DP, we add FK constraints from $\mathrm{src}$ and $\mathrm{dst}$ to $\mathrm{ID}$, and designate $\mathrm{Node}$ as the primary private relation, while $\mathrm{Edge}$ becomes a secondary private relation.

A mechanism $M$ is $\epsilon$-DP if for any neighboring instance $I,I^{\prime }$, and any output $y$, we have

Typical values of $\epsilon$ used in practice range from $0.1$ to 10, where a smaller value corresponds to stronger privacy protection.

8.1 Setup.

For graph pattern-counting queries, we used four queries: edge counting $Q_{1–}$, length-2 path counting $Q_{2–}$, triangle counting $Q_{▵}$, and rectangle counting $Q_{\square }$. We used five real-world networks datasets: $\mathrm{Deezer}$, $\mathrm{Amazon}1$, $\mathrm{Amazon}2$, $\mathrm{RoadnetPA}$ and $\mathrm{RoadnetCA}$. $\mathrm{Deezer}$ collects the friendships of users from the music-streaming service Deezer. $\mathrm{Amazon}1$ and $\mathrm{Amazon}2$ are two Amazon co-purchasing networks. $\mathrm{RoadnetPA}$ and $\mathrm{RoadnetCA}$ are road networks of Pennsylvania and California, respectively. All these datasets are obtained from SNAP.²² Table 1 shows the basic statistics of these datasets.

Most algorithms need to assume a $G{S}_Q$ in advance. Note that the value of $G{S}_Q$ should not depend on the instance, but may use some background knowledge for a particular class of instances. Thus, for the three social networks, we set a degree upper bound of $D=1024$, while for the two road networks, we set $D=16$. Then we set $G{S}_Q$ as the maximum number of graph patterns containing any node. This means that $G{S}_{Q_{1–}}=D$, $G{S}_{Q_{2–}}=G{S}_{Q_{▵}}=D^2$, and $G{S}_{Q_{\square }}=D^3$.

The LP mechanism requires a truncation threshold $\tau$, but Kasiviswanathan et al.²⁰ does not discuss how this should be set. Initially, we used a random threshold uniformly chosen from $[1,G{S}_Q]$. This turned out to be very bad as with constant probability, the picked threshold is $\Omega \left(G{S}_Q\right)$, which makes these mechanisms as bad as the naive mechanism that adds $G{S}_Q$ noise. To achieve better results, as in R2T, we consider $\{2,4,8,\dots ,G{S}_Q\}$ as the possible choices. Similarly, NT and SDE need a truncation threshold $\theta$ on the degree, and we choose one from $\{2,4,8,\dots ,D\}$ randomly.

All experiments were conducted on a Linux server with a 24-core 2.2GHz Intel Xeon CPU and 256GB of memory. Each program was allowed to use at most 10 threads and we set a time limit of 6 hours for each run. Each experiment was repeated 100 times and we report the average running time. The errors are less stable due to the random noise, so we remove the best 20 and worst 20 runs, and report the average error of the remaining 60 runs. The failure probability $\beta$ in R2T is set to $0.1$. The default DP parameter is $\epsilon =0.8$.

8.2 Experimental results.

The errors and running times of all mechanisms over the graph pattern counting queries are shown in Table 2. These results indicate a clear superiority of R2T in terms of utility, offering order-of-magnitude improvements over other methods in many cases. What is more desirable is its robustness: In all the 20 query-dataset combinations, R2T consistently achieves an error below $20\%$, while the error is below $10\%$ in all but three cases. We also notice that, given a query, R2T performs better in road networks than social networks. This is because the error of R2T is proportional to $D{S}_Q\left(I\right)$ by our theoretical analysis. Thus the relative error is proportional to $D{S}_Q\left(I\right)/\left|Q\left(I\right)\right|$. Therefore, larger and sparser graphs, such as road networks, lead to smaller relative errors.

In terms of running time, all mechanisms are reasonable, except for RM and SDE. RM can only complete within the six-hour time limit on three cases, although it achieves very small errors on these three cases. SDE is faster than RM but runs a bit slower than others. It is also interesting to see that R2T sometimes even runs faster than LP, despite the fact that R2T needs to solve $O(logG{S}_Q)$ LPs. This is due to the early stop optimization: The running time of R2T is determined by the LP that corresponds to the near-optimal $\tau$, which often happens to be one of the LPs that can be solved fastest. We also conducted experiments to see how the privacy parameter $\epsilon$ affects various mechanisms in our full version of paper. The result shows R2T has a high utility even for a small $\epsilon$.

Selection of $\tau$ In the next set of experiments, we dive deeper and see how sensitive the utility is with respect to the truncation threshold $\tau$. We tested the queries on $\mathrm{Amazon}2$ and measured the error of the LP-based mechanism²⁰ with different $\tau$. For each query, we tried various $\tau$ from 2 to $G{S}_Q$ and compare their errors with R2T. The results are shown in Table 3, where the optimal error is marked in gray. The results indicate that the error is highly sensitive to $\tau$, and more importantly, the optimal choice of $\tau$ closely depends on the query, and there is no fixed $\tau$ that works for all cases. On the other hand, the error of R2T is within a small constant factor (around 6) to the optimal choice of $\tau$, which is exactly the value of instance-optimality.