Source-linked AI summary
Iterative Constructions and Private Data Release
Anupam Gupta, Aaron Roth, Jonathan Ullman
TL;DR
The paper asks how to release exponentially many graph cut queries while preserving differential privacy. It introduces an IDC-based framework for interactive and non-interactive release, analyzes existing mechanisms, and gives new constructions. The results include improved dense-graph interactive bounds, synthetic graph release with error O(|V|^1.5), and a rank-1 approximation reduction for future improvement.
Problem
The paper studies approximately releasing graph cut functions while protecting the privacy of individual edges, where efficient methods for all cut queries were previously unavailable.
Method
It builds private query-release mechanisms from iterative database constructions, including a new Frieze/Kannan-based IDC and a randomized-response synthetic-data method using cut-norm approximation.
Results
The framework yields tighter interactive analyses, non-trivial error o(|E|) for all cuts on sufficiently dense graphs, and synthetic graph release with error O(|V|^1.5).
Takeaways & Limitations
IDC algorithms provide a common route to private release in both interactive and non-interactive settings, while rank-1 approximation remains a path toward improved synthetic graph guarantees.
Takeaways & Limitations
The reported average per-query bound applies only for k ≤ |X|/2, while the other listed algorithms bound worst-case per-query error; the synthetic-data setting assumes |E| = Ω(|V|).
Abstract
from arXiv · showhide
In this paper we study the problem of approximately releasing the cut function of a graph while preserving differential privacy, and give new algorithms (and new analyses of existing algorithms) in both the interactive and non-interactive settings. Our algorithms in the interactive setting are achieved by revisiting the problem of releasing differentially private, approximate answers to a large number of queries on a database. We show that several algorithms for this problem fall into the same basic framework, and are based on the existence of objects which we call iterative database construction algorithms. We give a new generic framework in which new (efficient) IDC algorithms give rise to new (efficient) interactive private query release mechanisms. Our modular analysis simplifies and tightens the analysis of previous algorithms, leading to improved bounds. We then give a new IDC algorithm (and therefore a new private, interactive query release mechanism) based on the Frieze/Kannan low-rank matrix decomposition. This new release mechanism gives an improvement on prior work in a range of parameters where the size of the database is comparable to the size of the data universe (such as releasing all cut queries on dense graphs). We also give a non-interactive algorithm for efficiently releasing private synthetic data for graph cuts with error O(|V|^{1.5}). Our algorithm is based on randomized response and a non-private implementation of the SDP-based, constant-factor approximation algorithm for cut-norm due to Alon and Naor. Finally, we give a reduction based on the IDC framework showing that an efficient, private algorithm for computing sufficiently accurate rank-1 matrix approximations would lead to an improved efficient algorithm for releasing private synthetic data for graph cuts. We leave finding such an algorithm as our main open problem.
1 Introduction
The paper develops private mechanisms for releasing graph cut queries in interactive and non-interactive settings. Its IDC framework unifies and improves prior analyses, while new constructions address dense graphs and synthetic graph release.
- Problem: The paper targets differentially private access to exponentially many graph cut queries while protecting the existence of individual edges.Interactive release answers adaptive cut queries; non-interactive release produces a private data structure or synthetic graph.
- Problem: Existing efficient query-release methods were unsuitable for releasing all graph cut queries, motivating solutions in both interactive and non-interactive settings.The paper treats cut queries as an instance of exponentially large families of linear queries.
- Interactive release: The IDC framework converts efficient iterative database construction algorithms into private query-release mechanisms and gives modular, tighter analyses of prior mechanisms.It encompasses the median, online multiplicative weights, and offline multiplicative weights mechanisms.
- Synthetic data: The non-interactive algorithm efficiently generates private synthetic graphs preserving cut queries approximately, with a stated error of O(|V|^1.5).It uses randomized response and an Alon–Naor constant-factor cut-norm approximation as a separation oracle.
- Open problem: An efficient private algorithm for sufficiently accurate rank-1 matrix approximation would imply improved efficient private synthetic-data release for graph cuts.The reduction contrasts NP-hard cut-norm witnessing with non-private singular-value decomposition for rank-1 approximation.
- Interactive release: For sufficiently dense graphs, the revised analyses show all cut queries can be answered with error o(|E|), whereas previous bounds need not be at most |E|.The trivial mechanism that always answers 0 has error at most |E|, so the new guarantee is non-trivial in this regime.
- Interactive release: A new Frieze/Kannan-based IDC improves private interactive release when database size is comparable to data-universe size, including dense-graph cut queries.The construction is for arbitrary linear queries and is tailored to the cut-query setting.
2 Preliminaries
The preliminaries formalize databases, differential privacy, query accuracy, synthetic release, and interactive release. They specialize these notions to graph edges, cuts, cut norm, and rank-1 queries.
- Privacy and databases: A database is a histogram over universe X, and two databases are adjacent when they differ in one element.In histogram form, adjacency is expressed as ∥D−D′∥1 ≤ 1.
- Privacy and databases: Differential privacy requires nearly indistinguishable output distributions on adjacent databases.The paper uses the standard (ε, δ)-differential privacy definition.
- Privacy and databases: For low-sensitivity vector queries, adding independent Laplace noise with scale 1/ε preserves (ε, 0)-differential privacy.The cited theorem assumes ℓ1 sensitivity at most 1.
- Query release: An (α, β)-accurate mechanism approximates every query in Q within α with probability at least 1−β.Accuracy is evaluated through a mechanism-dependent function Eval(Q, r).
- Query release: Synthetic release outputs a dataset representation that answers queries by evaluating them on the released synthetic database.Efficiency is measured polynomially in the dataset size n, with concise representations required when n is much smaller than |X|.
- Query release: Interactive release answers an arbitrary adaptively chosen stream of queries online, using polynomial time per query.The mechanism must answer each query before receiving the next one.
- Graphs and cuts: For graphs, the database is the edge set and the universe is the set of possible edges on a common vertex set.A graph cut is specified by two vertex subsets S and T.
- Graphs and cuts: The cut norm maximizes the absolute matrix sum over pairs of subsets, and graph cut queries are linear queries on the adjacency matrix.Cut queries can be represented as outer products of characteristic vectors.
3 Iterative Database Constructions
Iterative database constructions maintain hypotheses that increasingly approximate a database and update them using queries that expose significant discrepancies. Their efficiency is measured by the number of updates before all queries are approximated.
- Core abstraction: An IDC maintains a sequence of data structures D(1), D(2), … that increasingly approximate the input database with respect to a query class.The next structure is generated from one distinguishing query whose current answer differs significantly from the true answer.
- Formal definition: A database-update sequence begins with an initial structure and records distinguishing queries, approximate answers, and successive updates.Each update applies U(D(t), Q(t), Â(t)) to produce D(t+1).
- Update process: The approximate answer need only determine the sign of the discrepancy, so its error must be smaller than α.This is the role of the accuracy condition on Â(t).
- Efficiency: The main efficiency measure is the maximum number of updates required before the maintained structure approximates the database well over Q.This update bound determines how useful the construction is within the private release framework.
- Formal definition: An IDC is specified by an update rule U and a bound B(α) on the length C of every valid database-update sequence.The update rule receives the current structure, a distinguishing query, and an approximate query answer.
- Convergence: If an update sequence is maximal, the final data structure approximates the database within α for every query in Q.Otherwise another distinguishing query would extend the sequence, contradicting maximality.
4 Query Release from Iterative Database Construction
This section presents a generic mechanism that turns iterative database constructions into private query-release algorithms. It establishes privacy and accuracy through a modular analysis of update rounds and applies the framework to existing mechanisms.
- Framework and mechanism: Iterative database constructions support an interactive algorithm for releasing linear queries.The mechanism uses an IDC oracle, noisy query answers, and hypothesis updates when the current data structure differs substantially from the true database.
- Privacy analysis: The mechanism is (ε, δ)-differentially private.The privacy proof classifies rounds by whether noise prevents, permits, or makes an update unavoidable, then bounds cumulative privacy loss.
- Privacy analysis: With probability at least 1 − δ/2, the number of potentially privacy-leaking rounds is at most 16B log(4/δ).The bound follows by controlling the expected number of relevant rounds and applying a Chernoff bound.
- Accuracy analysis: The generic framework yields (α, β)-accurate release when the IDC has a bounded update sequence and the threshold satisfies T(α) ∈ [4α/3, 2α].Accuracy follows because significant discrepancies trigger IDC updates, while the construction limits how many such updates can occur.
- Relation to prior mechanisms: The framework generalizes the median and multiplicative-weights mechanisms while providing a simpler, modular analysis.The abstraction treats these mechanisms as instances of the same IDC-based approach.
5 An Iterative Database Construction Based on Frieze/Kannan
This section constructs an IDC from the Frieze/Kannan cut decomposition and instantiates the generic release mechanism with it. A potential argument bounds updates, yielding an interactive improvement for dense-graph cut queries.
- IDC construction: The Frieze/Kannan-based IDC iteratively modifies a database using the sign of a query discrepancy.The update adds or subtracts a scaled vector according to whether the hypothesis under- or overestimates the noisy query answer.
- Update bound: The IDC makes at most B(α) = ||D||_2^2|X|/α^2 updates.An L2 potential decreases by α^2/|X| at each update, while remaining nonnegative.
- Interactive release: Instantiating Algorithm 1 with this IDC gives an (ε, δ)-differentially private and (α, β)-accurate interactive release mechanism.The guarantee follows from the generic IDC-to-query-release framework.
- Graph-cut consequence: For graph cuts, the bound is an improvement over the multiplicative-weights IDC for dense graphs when |E| ≥ Ω(|V|^2/log |V|).The improvement applies when the database size is comparable to the data-universe size.
6 Results for Synthetic Data
This section develops an efficient non-interactive method that releases a synthetic graph preserving all cut queries. It adds Laplace noise, then uses optimization and cut-norm approximation to obtain a valid graph with bounded error.
- Synthetic-data objective: A synthetic graph can be released directly, avoiding the stateful API required by interactive mechanisms.The output graph can be examined by data analysts at their leisure.
- Randomized response: Independent Lap(1/ε) noise added to histogram entries preserves (ε, 0)-differential privacy but may produce negative edge weights.The noisy histogram is private, yet it is not itself a valid synthetic graph.
- Accuracy analysis: For graph cuts, the randomized-response analysis gives high-probability error O(ε^-1√(|V||S||T|)) for a cut (S, T).The tighter bound depends on the number of noisy entries participating in that cut.
- Synthetic graph release: There is an efficient (ε, 0)-differentially private algorithm producing a synthetic graph with all-cut error O(|V|^1.5/ε).An LP converts the noisy data structure into a nonnegative weighted graph, using approximate cut-norm separation.
- Spectral solution: Using spectral approximation for normalized cut norm solves the LP within ρ = O(log |V|), while the released graph also supports rank-1 queries with an O(log |V|) loss.The rank-1-query extension follows from the same spectral relationship used for separation.
7 Towards Improving on Randomized Response for Synthetic Data
This section develops an iterative-construction route to private synthetic data release, pairing iterative database construction algorithms with private distinguishers. It establishes privacy and accuracy guarantees and identifies rank-1 approximation as a route to improved graph-cut release.
- Iterative Construction Mechanism: The IC mechanism pairs an (F(ε), γ)-private distinguisher with a B(α)-iterative database construction algorithm for query class Q.The mechanism initializes a hypothesis and repeatedly uses the distinguisher and noisy query answers to update it.
- Privacy and Accuracy Guarantees: At most 2B(α) data accesses through ε0-differentially private procedures yield an (ε, δ)-differentially private mechanism.The privacy proof uses composition and chooses ε0 to obtain the stated overall guarantee.
- Privacy and Accuracy Guarantees: An (F(ε), γ)-private distinguisher and a B(α)-IDC give an (α, β)-accurate mechanism when γ ≤ β/(2B(α)).The analysis conditions on the distinguisher and noisy-answer events, whose combined failure probability is at most β.
- Efficient Synthetic Data Release: Efficient IDCs and distinguishers automatically produce efficient private synthetic-data release algorithms for the corresponding query class.For graph cuts, both the multiplicative-weights and Frieze/Kannan IDCs are computationally efficient.
- Rank-1 Approximation Route: An efficient private rank-1 distinguisher would yield improved efficient synthetic-data release for graph cuts and all rank-1 queries.For the Frieze/Kannan graph-cut IDC, accurate rank-1 approximation for symmetric matrices would suffice.
A Other Iterative Database Construction Algorithms
The appendix notes that the median and multiplicative-weights mechanisms can both be viewed as iterative database constructions for general linear-query classes.
- The median and multiplicative-weights mechanisms fit the IDC framework for general classes of linear queries Q.
A.1 The Median Mechanism
The median mechanism uses a collection of databases and repeatedly removes candidates inconsistent with noisy query answers. Its candidate set remains query-accurate for a bounded number of updates.
- Median Datastructure: A median datastructure evaluates a query by taking the median of that query across its constituent databases.
- Median Mechanism: The median mechanism removes databases on the wrong side of the median relative to each noisy answer.
- Accuracy and Iteration Bound: B(α) = n^2 log |X| log k/α^2 bounds the median mechanism's iterative database construction steps for every class of k linear queries.The bound follows because each update halves the candidate set, while an α-accurate database remains available.
A.2 The Multiplicative Weights Mechanism
The multiplicative-weights mechanism treats databases as normalized distributions and updates them using query discrepancies. A potential-function argument bounds the number of updates needed for query accuracy.
- Setup: The multiplicative-weights mechanism operates on normalized databases, where α/n accuracy implies α accuracy for un-normalized linear-query answers.
- Potential Analysis: B(α) = 4n^2 log |X|/α^2 bounds the multiplicative-weights mechanism's iterative database construction steps for every class of linear queries Q.The analysis uses a nonnegative potential initially bounded by log |X|.
- Potential Analysis: Whenever query discrepancy reaches α/n, the update decreases the potential, so the mechanism eventually outputs a database with maximum query error below α/n.