PaperlayerView exact revision on arXiv

Source-linked AI summary

Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]

Shixi Chen, Shuigeng Zhou

arXiv:1304.4795v1cs.DB

TL;DR

Differentially private aggregation over relational queries with unrestricted joins remained unsupported, and useful node-private graph statistics were an open problem. The paper models participant-linked data and gives a mechanism for private linear statistics over positive relational algebra; its subgraph-counting evaluation reports greater accuracy than existing algorithms at the same or stronger privacy guarantee.

  • Problem

    Existing record-based differential privacy methods do not address relational queries with unrestricted joins, where one participant can have complex or unbounded impact on the query answer.

    Source: §1 · p. 1, §1.2 · p. 2

  • Method

    The paper models sensitive participant-linked databases and answers linear queries over K-relations with a differentially private mechanism using empirical sensitivity.

    Source: §1 · p. 1, §1.2 · p. 2

  • Results

    For subgraph counting, the mechanism returns more accurate answers than existing algorithms while achieving the same or stronger privacy guarantee.

    Source: §8 · p. 11

  • Takeaways & Limitations

    Subgraph counting is a special case of the mechanism, which supports node or edge differential privacy for any subgraphs.

    Source: §1.2 · p. 2, §8 · p. 11

    The general implementation has expensive computation cost for H and G.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

Existing studies on differential privacy 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 sensitive database, and desires differentially private aggregation on the result of the query. However, no known work is capable to release this kind of aggregation when the query contains unrestricted join operations. This severely limits the applications of existing differential privacy techniques because many data analysis tasks require unrestricted joins. One example is subgraph counting on a graph. Existing methods for differentially private subgraph counting address only edge differential privacy and are subject to very simple subgraphs. Before this work, whether any nontrivial graph statistics can be released with reasonable accuracy under node differential privacy is still an open problem. In this paper, we propose a novel differentially private mechanism to release an approximation to a linear statistic of the result of some positive relational algebra calculation over a sensitive database. Unrestricted joins are supported in our mechanism. The error bound of the approximate answer is roughly proportional to the \emph{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 the first solution to achieve node differential privacy, for any kind of subgraphs.

1. INTRODUCTION

Differential privacy mechanisms built for record-based data struggle when participants are linked to relational data and one participant can have unbounded impact. The paper introduces models and mechanisms for private linear statistics over positive relational algebra, including subgraph counting under node or edge privacy.

1.1 Motivation

  • Earlier subgraph-counting methods covered limited motifs or edge privacy, while releasing nontrivial graph statistics with reasonable node privacy remained an open question.Source: §1.1 · pp. 1–2
  • The approach targets linear statistics of positive relational-algebra outputs, with either node or edge privacy and constraints on arbitrary subgraph nodes or edges.The paper identifies subgraph counting as a special case of this setting.Source: §1.1 · p. 2

1.2 Contributions

  • The general sensitive-database model permits one participant to affect database content in any way while basing privacy protection on individual participants.This model addresses complex relationships between participants and database content.Source: §1.2 · p. 2
  • Empirical sensitivity measures the maximum query-answer change when a participant withdraws data from the current database, and is always bounded and often small.The paper presents it as a measure of the least noise magnitude needed to answer a query.Source: §1.2 · p. 2
  • A general but inefficient mechanism answers any monotonic query on a sensitive database with ϵ-differential privacy and error roughly proportional to global empirical sensitivity.Source: §1.2 · p. 2
  • The efficient K-relation mechanism answers linear queries with ϵ-differential privacy and polynomial computation, and supports subgraph counting for any subgraph under node or edge privacy.Its error bound is roughly proportional to universal empirical sensitivity for linear queries and local empirical sensitivity for subgraph counting.Source: §1.2 · p. 2

2. PRELIMINARIES

The preliminaries define differential privacy and utility through neighboring databases and noise accuracy, then review sensitivity measures and K-relations as the representation for participant-dependent query results.

2.1 Privacy and Utility

  • Differential privacy requires nearly indistinguishable outputs on neighboring databases; Figure 1 compares mechanisms on SQL and subgraph tasks, excluding output-generation cost.The figure notes that either node- or edge-based privacy can be used for subgraph counting, depending on the choice of user.Source: §2.1 · p. 2, Figure 1 · p. 3

2.2 Global Sensitivity

  • Laplace noise is calibrated to global sensitivity, the maximum query-answer change across neighboring databases, which can cause unnecessarily large noise.For a query sequence, the Laplace mechanism adds independent noise scaled by global sensitivity and the privacy parameter.Source: §2.2 · p. 3, §2.3 · p. 3

2.3 Local Sensitivity and Smooth Sensitivity

  • Local sensitivity measures change around one database, but releasing with that noise scale can leak information; smooth sensitivity instead uses an upper bound whose logarithm has low global sensitivity.Global sensitivity is the maximum local sensitivity over databases.Source: §2.3 · p. 3

2.4 K-Relation and c-Table

  • K-relations annotate tuples with provenance, and c-tables use positive Boolean expressions to encode tuple presence as participants opt out; positive relational algebra supports joins but not difference.Equivalent expressions cannot always be rewritten freely in this work, because the efficient mechanism depends on expression form.Source: §2.4 · p. 4

3. PROBLEM FORMULATION

The problem formulation models how participants contribute to databases and defines withdrawal-based neighbors. It then restricts attention to monotonic linear queries, represented with sensitive relations and K-relations, and relates empirical sensitivity to answer error.

3.1 Sensitive Databases and Monotonic Queries

  • A sensitive database pairs participants with a function specifying database content for each contributing subset, so withdrawing one participant defines neighboring databases.The model assumes a shared empty-participant database and a class closed under ancestors.Source: §3.1 · p. 4
  • The framework considers real-valued monotonic queries, for which empirical sensitivity measures the maximum answer change when a participant opts out.Global empirical sensitivity is bounded by global sensitivity, while local empirical sensitivity is bounded by global and global empirical sensitivity.Source: §3.1 · pp. 4–5

3.2 Linear Queries on Sensitive Relations

  • A linear query first maps a database to a finite tuple set and then applies a linear statistic; monotonicity requires tuples not to disappear as participants are added and nonnegative weights.A statistic that may be negative can be decomposed into two nonnegative components and computed separately.Source: §3.2 · p. 5
  • A sensitive K-relation annotates each tuple with a positive Boolean condition of presence, with participant variables recording whose data contributes.This representation expresses how a query's output relation changes when participants opt out.Source: §3.2 · p. 5
  • Two sensitive K-relations are neighboring when replacing the added participant's variable with False yields equivalent tuple annotations.The equivalence relation matters: the efficient mechanism depends on expression form, so equivalent truth tables need not permit arbitrary rewrites.Source: §3.2 · p. 5
  • K-relations illustrate outputs for both subgraph counting and a more complicated common-friend query.Figure 2 presents examples of K-relations generated by graph queries.Source: §3.2 · pp. 5–6, Figure 2 · p. 6
  • For unit tuple weights, universal empirical sensitivity counts tuples whose annotations contain a participant; the mechanism's error bound is roughly proportional to it.The paper introduces impact and universal empirical sensitivity as variants relevant to the mechanism's error bound.Source: §3.2 · p. 5

4. THE RECURSIVE MECHANISM FRAMEWORK

The recursive mechanism answers monotonic queries by building recursive and bounding sequences, then calibrating noise to the bound. Its general implementation achieves differential privacy with error tied to the bound, but computing the sequences is expensive.

4.1 The Basic Framework

  • H is a recursive sequence, while G is a recursive sequence satisfying additional bounding conditions that relate later H values to earlier ones.The framework uses these sequences to support its three-step mechanism.Source: §4.1 · p. 6
  • It constructs H and a g-bounding sequence G, privately estimates the bound, then adds Laplace noise to an answer estimate with sensitivity at most the noisy bound.The framework approximates the query answer using H and calibrates the final Laplace noise using the privately estimated bound.Source: §4.1 · p. 6
  • The mechanism satisfies (ε1+ε2)-differential privacy, with error roughly proportional to G_|P|.The theorem gives a corresponding accuracy guarantee in terms of G_|P| and its parameters.Source: §4.1 · p. 7

4.2 A General but Inefficient Implementation

  • The general implementation constructs H and G for any monotonic query, and the theorem establishes that they meet the required sequence conditions.Its error is roughly proportional to the query’s global empirical sensitivity, but computing H and G is expensive.Source: §4.2 · p. 7

5. EFFICIENT RECURSIVE MECHANISM

The efficient recursive mechanism uses relaxation to handle linear queries on sensitive K-relations. Its error depends on empirical sensitivity and φ-sensitivity, while its computation reduces to linear programming with a stated runtime bound.

5.1 Recursive Mechanism with Relaxation

  • Relaxation maps Boolean expressions to [0,1]-valued functions, yielding a recursive sequence H whose final entry equals q(supp(R)); a 2-bounding sequence G is then constructed for H.The mapping φ is the basis for the efficient mechanism on linear queries over sensitive K-relations.Source: §5 · p. 7, §5.1 · p. 7

5.2 The Mapping φ

  • The recursive mapping uses max{0, φx(f)+φy(f)−1} for conjunction and max{φx(f),φy(f)} for disjunction, and has the stated correctness and shape properties.The properties include correctness, naturalness, monotonicity, convexity, and truncated linearity.Source: §5.2 · p. 7
  • For disjunctive normal form expressions, φ-sensitivity is at most 1; safe annotation also preserves neighboring sensitive K-relations when participants opt out.For positive relational algebra queries, the stated φ-sensitivity bound is at most one plus the number of query operations under the specified tuple-participant condition.Source: §5.2 · p. 8
  • The error bound is roughly proportional to S times universal empirical sensitivity; for subgraph counting, it is roughly proportional to local empirical sensitivity.S is the maximum φ-sensitivity, and is linear in positive relational algebra query length in general; it is 1 for disjunctive normal form expressions.Source: §5.2 · p. 8

5.3 Computation Cost

  • The computation encodes each H_i and G_i calculation as a linear program with O(L) variables, enabling polynomial-time execution.Monotonicity of G and convexity of H support a more efficient computation, with the runtime given by Theorem 6.Source: §5.3 · p. 8
  • The efficient mechanism runs in O(ln(ln(G_|P|)/β)T(L)) time, where T(L) is the time to solve a linear program with O(L) variables.L is the total length of the annotated expressions in the support of R.Source: §5.3 · p. 8

6. EXPERIMENTAL EVALUATION

The evaluation measures median relative error for subgraph-counting mechanisms and tests the recursive mechanism on synthetic and real graphs as well as generated K-relations. Results favor the mechanism in several settings, while accuracy and runtime vary with graph structure and query sensitivity.

6. EXPERIMENTAL EVALUATION

  • Accuracy is measured as median relative error across repeated runs on randomly generated graphs or K-relations.The study compares subgraph-counting mechanisms and separately evaluates more general K-relations.Source: §6 · p. 8

6.1 Subgraph Counting

  • With edge privacy, the recursive mechanism gives the most accurate answers; under node privacy, errors are high for 2-stars and 2-triangles but decrease as graphs grow.RHMS errors can be too high to show, while local-sensitivity errors can be unusable for triangle queries on sparse graphs.Source: §6.1 · pp. 9–10
  • At fixed average degree, runtime grows polynomially with the true count: 2-star counting slows as graphs grow, while triangle and 2-triangle counting can speed up.The latter counts often decrease as sparse random graphs enlarge.Source: Figure 5 · p. 9, §6.1 · p. 10
  • For real datasets, the recursive mechanism is often superior to the other mechanisms in the reported experiments.Figures 6 and 7 report graph sizes and triangle-counting accuracy comparisons.Source: §6.1 · p. 10, Figure 6 · p. 10, Figure 7 · p. 10

6.2 Processing K-Relations

  • The K-relation experiments use random 3-DNF and 3-CNF expressions, with participant count matched to relation support size and the true answer set to that support size.Figures 8 and 9 vary expression length and relation size, respectively.Source: §6.2 · p. 10, Figure 8 · p. 10, Figure 9 · p. 10
  • On generated K-relations, error is nearly linear in universal empirical sensitivity divided by ε, and that sensitivity is insensitive to increases in participants and tuples.Consequently, relative error can decrease as more data become available; runtime is polynomial in relation support size and expression length.Source: §6.2 · p. 10

7. RELATED WORK

Prior work developed global- and local-sensitivity methods for private query answers, alongside graph-counting mechanisms with restricted privacy or utility guarantees.

Global sensitivity

  • The Laplace mechanism calibrates noise to global sensitivity, but can give unusable answers for queries with large global sensitivity.It underlies later methods, including work on relational algebra queries.Source: §7 · p. 11

Local sensitivity

  • Smooth sensitivity calibrates instance-dependent noise to an upper bound on local sensitivity, but no general method computes it for an arbitrary query.Algorithms were given for triangle count and other statistics in selected domains.Source: §7 · p. 11

Graph statistics

  • Private k-star and k-triangle counting used local sensitivity, while general subgraph counting relaxed privacy to improve utility.These approaches provide edge privacy rather than node privacy.Source: §7 · p. 11

Other graph privacy

  • Other graph-privacy studies largely fall outside differential privacy and often lack quantitative privacy and utility guarantees; surveys k-anonymity approaches.Source: §7 · p. 11

8. CONCLUSION

The paper proposes a differentially private mechanism for approximating linear statistics of positive-relational-algebra query outputs, including subgraph counts. Its evaluation reports greater accuracy than existing subgraph-counting algorithms at the same or stronger privacy guarantee.

8. CONCLUSION

  • The mechanism approximates linear statistics of tables produced by positive relational algebra queries and supports either node or edge differential privacy.Subgraph counting is a special case.Source: §8 · p. 11

A. PROOFS

The proof appendix establishes privacy and accuracy guarantees for the recursive mechanism and verifies sequence and mapping properties used in its construction.

Recursive sequence proof

  • For neighboring databases, the proof sketch shows that the selected indices for the recursive sequence differ by at most one.It establishes i ≤ j ≤ i + 1.Source: A. PROOFS · p. 11

Recursive mechanism guarantee

  • When ε1 = Θ(ε), ε2 = Θ(ε), β = ε1/k, and θ and μ are constants, the mechanism is (O(k ln(G_|P|)G_|P|/ε), 2e^-kμ)-accurate as ε→0, k→∞, and G_|P|→∞.Source: A. PROOFS · p. 12
  • The privacy-and-accuracy proof sketch combines private estimates of sensitivity and query value with bounds on their errors and on the approximation to H_|P|.Source: A. PROOFS · p. 12

K-relation construction proofs

  • The construction proofs establish that H is recursive and ends at q(supp(R)), while G is a 2-bounding sequence of H.The mapping φ is shown to have the required correctness, naturalness, monotonicity, convexity, and truncated-linearity properties.Source: A. PROOFS · pp. 12–13
Loading 1304.4795v1…