PaperlayerView exact revision on arXiv

Source-linked AI summary

Calibrating Data to Sensitivity in Private Data Analysis

Davide Proserpio, Sharon Goldberg, Frank McSherry

arXiv:1203.3453v5cs.CRcs.SI

TL;DR

Differentially private analysis can lose accuracy when worst-case sensitivity dictates noise for challenging records or graph structures. The paper introduces wPINQ, which uses weighted datasets, stable operators, and MCMC inference to rescale contributions and synthesize datasets from noisy measurements. The resulting platform supports graph analyses and can improve or extend measurements, although its scope includes limitations for vertex privacy and some triangle-by-degree inference settings.

  • Problem

    Existing differential privacy platforms have limited applicability to graph analysis because worst-case sensitivity can require substantial noise when a single edge changes a query greatly.

  • Method

    wPINQ generalizes PINQ with weighted datasets, data-dependent stable transformations, a non-uniformly scaling Join operator, and MCMC-based synthesis from noisy measurements.

  • Results

    wPINQ expresses graph analyses and uses MCMC to improve consistency across measurements, combine constraints, and estimate quantities not directly queried.

  • Takeaways & Limitations

    Scaling troublesome records rather than all records uniformly can bypass many worst-case sensitivity bounds, while probabilistic inference extends the utility of noisy wPINQ measurements.

  • Takeaways & Limitations

    The approach does not directly provide vertex differential privacy, and triangle-by-degree inference can be overwhelmed by noise for large degrees absent in the secret graph.

Abstract

from arXiv · show

We present an approach to differentially private computation in which one does not scale up the magnitude of noise for challenging queries, but rather scales down the contributions of challenging records. While scaling down all records uniformly is equivalent to scaling up the noise magnitude, we show that scaling records non-uniformly can result in substantially higher accuracy by bypassing the worst-case requirements of differential privacy for the noise magnitudes. This paper details the data analysis platform wPINQ, which generalizes the Privacy Integrated Query (PINQ) to weighted datasets. Using a few simple operators (including a non-uniformly scaling Join operator) wPINQ can reproduce (and improve) several recent results on graph analysis and introduce new generalizations (e.g., counting triangles with given degrees). We also show how to integrate probabilistic inference techniques to synthesize datasets respecting more complicated (and less easily interpreted) measurements.

1. INTRODUCTION

wPINQ addresses the poor applicability of worst-case differential privacy to graph analysis by scaling down troublesome records in weighted datasets rather than uniformly increasing noise. It combines a declarative language with stable transformations and MCMC-based inference to support graph measurements and synthetic-data construction.

  • Worst-case sensitivity can force substantial noise when one graph edge drastically changes a query, limiting existing differential privacy platforms for graph analysis.
  • wPINQ generalizes PINQ to weighted datasets, using data-dependent rescaling to support graph analyses that existing platforms cannot express.
  • Weighting each triangle by 1/max{d_a, d_b, d_c} can yield constant noise on constant-degree graphs, unlike uniform weighting by 1/|V|.
  • wPINQ supplies stable transformations, including a non-uniformly scaling Join, for graph analyses such as degree-conditioned triangle and cycle counts.
  • MCMC post-processing can remove noisy inconsistencies, combine constraints from multiple measurements, and estimate unqueried quantities from posterior samples.

2. WEIGHTED DATASETS AND wPINQ

wPINQ represents datasets with real-valued record weights and composes stable transformations with differentially private aggregation. Its operators rescale contributions to preserve stability while tracking privacy costs under composition and repeated dataset use.

  • Weighted datasets extend multisets by assigning each record a real-valued weight rather than an integer multiplicity.
  • wPINQ generalizes differential privacy to weighted datasets and preserves sequential composition, with smaller ϵ indicating stronger privacy.
  • NoisyCount adds Laplace(1/ϵ) noise to each weighted record instead of scaling noise according to query sensitivity.
  • wPINQ includes per-record and relational operators such as Select, Where, SelectMany, GroupBy, Shave, Join, Union, and Intersect.
  • Stable transformations can be composed with private aggregations without compromising their privacy guarantee, but transformations alone do not provide privacy.
  • Reusing a dataset k times in a query with an ϵ-private aggregation yields a kϵ privacy cost for that dataset.

2.4 Select, Where, and SelectMany

Select, Where, SelectMany, and GroupBy provide stable weighted transformations for filtering, mapping, expansion, and grouping records. Their scaling rules depend on actual output structure rather than a single worst-case bound.

  • Select maps records and accumulates weights for records sharing an output, while Where retains records satisfying a predicate.
  • SelectMany stabilizes one-to-many expansion by scaling output weights according to the number of records each input produces.
  • SelectMany permits different inputs to produce different numbers of outputs, supporting applications such as frequent itemset mining.
  • GroupBy partitions records by key and applies a reducer, providing MapReduce-like processing for collections such as edges grouped by source vertex.
  • For weighted GroupBy, records are ordered by decreasing weight and emitted prefix sets receive weights based on adjacent weight differences.

2.6 Union, Intersect, Concat, and Except

wPINQ gives familiar set and database operators weighted semantics, while its Join rescales matching pairs to remain stable. This makes Join useful for constructing graph paths without allowing high-degree matches to dominate sensitivity.

  • Union and Intersect use element-wise maximum and minimum weights, while Concat and Except use element-wise addition and subtraction.
  • These four operators are stable binary transformations.
  • Standard SQL equi-join is unstable because one record can match as many records as exist in the other input.
  • wPINQ Join scales matched pairs by the sum of the weighted input norms for their join key, with products of input weights determining pair contributions.
  • Self-joining graph edges constructs length-two paths, assigning paths through high-degree nodes smaller weights while preserving non-trivial weight for low-degree paths.

2.8 Shave

Shave decomposes weighted records into indexed records with smaller weights, enabling non-uniform scaling while preserving total weight. Select can reverse this decomposition, and the operators support stable graph transformations.

  • Shave: Shave breaks a record of weight A(x) into indexed records whose smaller weights sum to A(x).The transformation applies a record-to-sequence function f(x) and emits one record for each sequence term.
  • Shave: Applying Shave with unit weights creates multiple indexed records for each input record.The example uses f(x) = ⟨1.0, 1.0, 1.0, ...⟩ for every record.
  • Select: Select is Shave’s functional inverse and recovers the original dataset without reducing total weight.Select retains the first tuple element using f(⟨x, i⟩) = x.
  • Graph transformation: SelectMany, Shave, and Where transform unit-weight edges into node records with weight 0.5.Each edge becomes two node records, and identical node records accumulate weight according to node degree.
  • Graph transformation: The transformation cannot produce unit-weight nodes because one edge changes two output node records.Weight 0.5 is therefore the largest reasonably stable output weight for this edge-to-node transformation.

3. GRAPH ANALYSES WITH wPINQ

wPINQ expresses differentially private graph analyses, including degree, joint-degree, triangle, and square statistics. Its operators combine weighted transformations with postprocessing and noise calibration to support richer graph queries under privacy guarantees.

  • Overview: wPINQ expresses degree and joint-degree analyses while correcting issues in prior privacy analyses.The platform also provides privacy bounds for challenging custom graph statistics.
  • 3.1 Degree distributions: wPINQ reproduces degree analysis without publicly revealing the number of nodes.It uses a non-increasing degree sequence and can combine degree-sequence measurements with their CCDF for more accurate postprocessing.
  • 3.1 Degree distributions: The degree CCDF query converts edge records into degree-indexed records whose weights count nodes above each degree threshold.Select, Shave, and weight accumulation produce the CCDF before NoisyCount adds noise.
  • 3.1 Degree distributions: The lowest-cost grid path jointly fits noisy degree and CCDF measurements while respecting their monotonic structure.Horizontal and vertical edge costs correspond to deviations from the noisy degree sequence and CCDF, respectively.
  • 3.1 Degree distributions: The path-based postprocessing is more expensive than PAVA but experimentally takes several milliseconds.The implementation constructs edges as needed and visits nodes in the low-cost trough near the true measurements.
  • 3.2 Joint degree distribution: Prior joint-degree work used noise proportional to 4 max(da, db)/ϵ but had a privacy flaw when absent pairs were released without noise.Noising all pairs would correct the flaw but harm the reported accuracy.
  • 3.2 Joint degree distribution: wPINQ’s comparable joint-degree mechanism requires noise amplitude 8 + 8da + 8db, making it worse than the bespoke analysis by a factor of two to four.The comparison accounts for duplicated measurements, undirected-graph guarantees, and four uses of the input dataset.
  • 3.3 Triangles by degree: Triangle-by-degree counting joins degree-labeled paths so that only triangles contribute weight to each degree triple.Dividing each reported number by the stated normalization yields noisy triangle counts for degree triples.

4. SYNTHESIZING INPUT DATASETS

wPINQ uses probabilistic inference to turn noisy measurements into posterior distributions over plausible datasets, then samples representative synthetic datasets with Metropolis-Hastings. Its incremental evaluator makes repeated MCMC updates practical, but complex graph queries remain constrained by computation time and memory capacity.

  • 4.1 Probabilistic Inference: Probabilistic inference combines noisy measurements with a known likelihood relationship to produce a posterior distribution over possible datasets.Bayes’ rule updates a prior using the probability that each dataset would produce the observed measurements.
  • 4.1 Probabilistic Inference: wPINQ automatically converts queries into an MCMC sampling algorithm that explores synthetic datasets by repeatedly applying and evaluating small changes.The engine uses noisy measurements but no longer accesses the secret input during this process.
  • 4.1 Probabilistic Inference: The posterior favors datasets matching observed measurements and can indirectly improve agreement with other statistics constrained by those measurements.For graphs, accurate degree-distribution measurements can complement noisier triangle-related measurements.
  • 4.2 Metropolis-Hastings: Metropolis-Hastings uses a random walk and scoring function to generate a limiting distribution proportional to supplied dataset scores.The user supplies an initial state, random walk, and scoring function; wPINQ can seed graph sampling with a dataset matching measured degree distributions.
  • 4.3 Incremental Query Evaluator: Incremental query evaluation updates computations in response to small candidate-dataset changes instead of recomputing each query from scratch.wPINQ records transformations in a directed dataflow graph and maintains intermediate state for these updates.
  • 4.3 Incremental Query Evaluator: Complex graph analyses remain limited by computation time and memory because one changed edge can propagate through many intermediate results.For the TbD query, intermediate structures can grow with input size and query complexity; tested workloads required as many as 64 gigabytes of memory.

5. EXPERIMENTS

The experiments combine wPINQ measurements with MCMC graph synthesis to infer triangle-related properties, showing that bucketing improves TbD’s signal while TbI gives stronger aggregate inference but remains computationally demanding.

  • Graph-synthesis workflow: The workflow first creates a seed graph matching private degree measurements, then uses edge-swapping MCMC to fit additional wPINQ measurements.The seed preserves its degree distribution during subsequent MCMC proposals.
  • Evaluating TbD: TbD measurements by degree can overwhelm MCMC with noise for high-degree triples that are absent from the secret graph.For large degrees, the perturbed counts are almost entirely noise, so MCMC makes little progress.
  • Evaluating TbD: Bucketing degree triples increases cumulative signal without increasing bucket noise, enabling MCMC to distinguish graphs with similar-degree triangle counts.The implementation groups each batch of k degrees by replacing each degree with floor(degree/k).
  • Evaluating TbD: For CA-GrQc, bucketing allowed MCMC to distinguish the original graph from a degree-matched random graph, although it still failed to recover the input graph properties.The experiment used k = 20 and 5 × 10^6 MCMC steps.
  • Scalability: On Barabási–Albert graphs, increasing the dynamical exponent from β = 0.5 to β = 0.7 increased memory needs and reduced MCMC throughput from about 80 to 25 steps/second.The easiest graph used about 25Gb of RAM, while the most difficult used over 45Gb.

6. RELATED WORK

Prior work addresses sensitivity through dataset-specific noise, trimming, relaxed privacy, and weighted sums, while wPINQ extends weighted transformations to general graph queries. This paper presents a fuller wPINQ platform and inference engine than its earlier workshop version.

  • Bypassing worst-case sensitivity: Sensitivity-bypassing methods include smooth sensitivity, dataset trimming, and privacy relaxations for records that create high sensitivity.Weighted datasets instead down-weight troublesome records while leaving benign components relatively untouched.
  • Weighted query systems: Weighted-sum techniques optimize collections of linear queries but do not directly support general transformations such as Join and GroupBy.Those transformations are described as crucial for graph analysis.
  • Privacy languages: Existing differential privacy languages do not support data-dependent record-weight rescaling; uniform scaling is effectively equivalent to increasing noise.The paper positions wPINQ as adding non-uniform, data-dependent scaling to this language landscape.
  • Privacy and graphs: Prior graph analyses cover degree distributions, joint degree distributions, triangle counting, triangle generalizations, clustering coefficients, and node-level privacy.The paper distinguishes its contribution from deriving such analyses directly from first principles.
  • Paper contribution: This paper expands an earlier workshop sketch into a full wPINQ platform with weighted transformation stability and an incremental engine for probabilistic inference.The earlier work synthesized graphs respecting degree and joint-degree distributions; this paper presents the broader platform.

7. CONCLUSIONS

The paper presents wPINQ as a declarative language and incremental evaluation engine for private computation and dataset synthesis. Its central strategy calibrates data contributions to query sensitivity rather than scaling noise.

  • Platform: wPINQ combines a declarative programming language with an incremental evaluation engine that supports MCMC synthesis of representative datasets.The platform is designed for differentially private computation.
  • Core approach: wPINQ calibrates data to query sensitivity by assigning weights that reduce the contributions of specific troublesome records.The conclusion contrasts this with calibrating noise magnitude.

A. STABILITY OF wPINQ OPERATORS

The appendix establishes stability bounds for wPINQ’s Join and GroupBy operators. These proofs bound output changes by input-weight changes and analyze GroupBy through controlled record-weight adjustments.

  • Join stability: The Join operator satisfies ||Join(A, B) − Join(A′, B′)|| ≤ ||A − A′|| + ||B − B′||.The proof decomposes changes across the two inputs and bounds each contribution.
  • Join proof: The Join proof writes the operator in vector form and bounds each summand through denominator manipulation and simplification.The argument uses cross-multiplication and shows the resulting fraction is at most one.
  • GroupBy stability: The GroupBy stability proof begins from a theorem for arbitrary datasets and key functions.It analyzes changes by decomposing weight differences into record-level steps.
  • GroupBy proof: GroupBy changes are decomposed into weight adjustments that preserve record ordering, with each record moved through intermediate positions.The accumulated adjustment is bounded by the change in the relevant grouped prefix weight.

B. wPINQ OPERATORIMPLEMENTATION

The implementation section describes incremental maintenance for linear and set-like operators, while Join and GroupBy require data structures that account for weighted inputs and changing order.

  • Basic operators: SelectMany propagates input weight changes linearly, while Union, Intersect, Concat, and Except maintain dictionaries of record weights.Updates on either input emit corresponding output differences.
  • Weighted grouping: GroupBy maintains per-key sorted lists of records and reevaluates affected prefixes when input changes alter ordering.It emits the resulting records as incremental differences.
  • Shave: Shave expands each input record into unit-weight outputs with indices so input differences can be retired efficiently.The implementation maintains a dictionary for these derived records.

C. REPRODUCTION OF SALA et al.’S RESULT: NON-UNIFORM NOISE FOR THE JDD

The section reproduces a differentially private mechanism for releasing joint degree-distribution counts with degree-dependent Laplace noise. Its proof bounds the output-probability ratio for graphs differing by one edge.

  • The mechanism releases each degree-pair edge count with zero-mean Laplace noise parameterized by 4 max{di, dj}/ϵ.
  • Privacy is proved for neighboring undirected graphs G1 and G2 that differ by one edge.
  • For a fixed output, the probability ratio between G1 and G2 reduces to the ratio of the Laplace expressions because their normalization constants match.
  • Removing edge (a, b) changes the degree-pair counts involving the endpoint degrees and their incident edges.
  • The proof accounts for the total count differences using the endpoint degrees and concludes the required bound.
Loading 1203.3453v5…