The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

Jeremiah Blocki; Avrim Blum; Anupam Datta; Or Sheffet

Source-linked AI summary

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet

arXiv:1204.2136v2Apr 10, 2012cs.DS

TL;DR

The paper asks how to preserve differential privacy without sacrificing utility through excessive added noise. It uses the Johnson–Lindenstrauss transform with a reversible input alteration, proving privacy for Gaussian projections and applying them to graph cuts and directional variance. The resulting guarantees include cut-query noise scaling with |S| and directional-variance utility independent of matrix dimensions, subject to important scope limitations.

Problem
Differential-privacy mechanisms must provide tight utility and privacy tradeoffs rather than answers so noisy that they obliterate useful data.
Method
The paper reversibly alters the input so the Johnson–Lindenstrauss transform’s Gaussian projections can preserve differential privacy while approximately preserving relevant lengths.
Results
The method publishes a differentially private perturbed graph Laplacian for single-edge changes and a sanitized covariance matrix whose directional-variance utility guarantees are independent of d and n.
Takeaways & Limitations
For graph cuts, the method adds O(|S|) noise w.h.p. instead of noise proportional to the number of vertices, while directional-variance guarantees avoid dependence on matrix dimensions.
Takeaways & Limitations
The sanitized covariance output is a test matrix rather than a low-rank approximation or a matrix guaranteed suitable for approximate PCA.

Abstract

from arXiv · show

This paper proves that an "old dog", namely -- the classical Johnson-Lindenstrauss transform, "performs new tricks" -- it gives a novel way of preserving differential privacy. We show that if we take two databases, $D$ and $D'$, such that (i) $D'-D$ is a rank-1 matrix of bounded norm and (ii) all singular values of $D$ and $D'$ are sufficiently large, then multiplying either $D$ or $D'$ with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and \emph{public} alteration of the input is enough to assert that all singular values of $D$ are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a $(S,\bar S)$-cut in a graph. We show that the JL transform allows us to \emph{publish a sanitized graph} that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only $O(|S|/ε)$ random noise to any given query (w.h.p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts ($|S| = o(n)$). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to \emph{publish a sanitized covariance matrix} that preserves differential privacy w.r.t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w.h.p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions.

1 Introduction

This paper shows that the classical Johnson–Lindenstrauss transform can preserve differential privacy when applied to suitably altered inputs, reversing the usual strategy of adding noise to sensitive outputs. It applies this approach to graph cut queries and directional variance, obtaining utility guarantees that can improve on existing methods in relevant settings.

Motivation: Differential privacy requires balancing privacy with useful answers, motivating tighter utility–privacy tradeoffs.Standard mechanisms add Laplace or Gaussian noise to query answers; this paper instead alters inputs reversibly and proves privacy for the resulting algorithm.
Core technique: The JL transform preserves differential privacy by multiplying databases with iid Gaussian vectors, under suitable singular-value conditions and a deterministic input translation.In the toy example, the output variance changes from ||D||2 to ||D||2 + 1 after one database entry changes; concentration bounds then yield privacy when the variance is sufficiently large.
Applications: For directional variance, the JL transform publishes a sanitized covariance matrix with utility guarantees independent of matrix dimensions under bounded row changes.The neighboring-input model permits one row to change by a vector of norm at most 1.
Applications: For graph cut queries, the method publishes a perturbed Laplacian with (ε, δ)-differential privacy under single-edge changes.The cut query is represented using the edge matrix and an indicator vector, linking the query answer to a product length.
Applications: O(|S|) random noise is added w.h.p. to a cut query, whereas existing algorithms add noise proportional to the number of vertices.The paper reports that its method is advantageous for small cuts, while a pathological projection can produce substantially larger estimation error.

2 Basic Definitions, Preliminaries and Notations

The paper defines privacy, neighboring inputs, query tasks, and the linear-algebraic and Gaussian preliminaries needed for its JL-based mechanisms.

Privacy and utility: Neighboring matrices differ only in one row, whose change has norm at most 1.
Query definitions: Cut queries measure the total weight of edges crossing a vertex subset S and its complement.
Query definitions: Directional variance queries evaluate x^T A^T A x for a unit-length direction x, after centering A’s rows.
Linear algebra: The SVD represents a matrix through unitary factors and ordered positive singular values.
Gaussian and JL preliminaries: Gaussian linear combinations and matrix transformations remain Gaussian, with transformed means and covariance matrices determined algebraically.
Gaussian and JL preliminaries: The JL transform uses an iid Gaussian matrix and approximately preserves the L2 norm of every fixed vector.

3 Publishing a Perturbed Laplacian

The paper publishes a perturbed graph Laplacian using the JL transform, establishing edge differential privacy and approximation guarantees for cut queries. The mechanism’s all-query error scales with cut size rather than only graph size, while its guarantees concern predetermined queries.

3.1 The Johnson-Lindenstrauss Algorithm: Algorithm 1 publishes a Laplacian whose construction uses iid Gaussian projections of the graph’s edge matrix.The proof analyzes each projected row and then applies composition across the independent rows.
3.1 The Johnson-Lindenstrauss Algorithm: Algorithm 1 preserves (ε, δ)-differential privacy for edge changes in the input graph.
3.2 Cut-query utility: For a cut S of size s, Algorithm 2 provides a (η, τ, ν)-approximation with error controlled by the JL norm-preservation guarantee.The proof states the resulting upper bound as τ ≤ 2ηw · s.
3.2 Cut-query utility: The mechanism guarantees accurate answers for any set of k predetermined cuts when the per-algorithm failure parameter satisfies ν < 1/(2k).
3.1 The Johnson-Lindenstrauss Algorithm: The privacy proof relies on adding a public complete-graph component, which makes the relevant Laplacian singular values sufficiently large.The construction ensures a lower spectral bound through the relation between the complete-graph Laplacian and the input Laplacian.
3.2 Cut-query utility: For all 2^n cut queries, the noise is ˜O(s√(log(k))/ε), while the JL matrix may increase dimension because r > n.

4 Publishing a Covariance Matrix

The paper publishes a differentially private covariance test-matrix by applying Gaussian Johnson–Lindenstrauss projections after shifting singular values, supporting directional variance queries under bounded row changes.

Problem: The algorithm addresses covariance estimation for an n×d matrix when one row may change by a norm-1 vector.It targets directional variance queries and can also output the sample mean.
Limitation: The published matrix is a test-matrix, not a low-rank approximation or a reliable basis for PCA.The paper does not guarantee comparable singular values or eigenvectors between the published matrix and A^TA.
Privacy: (ε, δ)-differential privacy follows by comparing Gaussian projections of neighboring matrices whose difference is rank one.The proof uses the rank-1 gap matrix and composition across the sampled projections.
Algorithm: The mechanism samples an r×n iid Gaussian matrix and projects the input after deterministic spectral shifting.The JL output is formed from Gaussian projections; the shift ensures sufficiently large singular values for the privacy analysis.
Utility: The method answers directional variance queries with additive noise independent of the input matrix size, unlike the compared mechanisms.The comparison assumes polynomially many queries and contrasts the method with Laplace, Multiplicative Weights, and randomized response.
Utility: O(log(k)/ε^2) is the stated utility bound when the failure parameter is set to ν = O(1/k).This follows by substituting ν = O(1/k) into the directional-variance theorem.

5 Discussion and Open Problems

The discussion identifies limits of the JL-based graph mechanism and outlines open questions about projection count, error correction, error detection, and broader applications.

Open questions: The JL transform’s differential-privacy property may have theoretical and practical applications beyond those developed in the paper.The authors present several open questions motivated by this possibility.
Error dependency on r: r = Ω(n) projections are required by the analysis to approximate all cut-queries, and the authors show this dependence is not merely an analytical artifact.A projection direction can become highly correlated with the published Laplacian.
Error dependency on r: For a perfect-matching graph, one projection can estimate an O(n) cut as Ω(n^2), while averaging still yields ω(n) error when r = o(n).The problematic direction is induced by the projection itself, with X and Y both proportional to n with high probability.
Error amplification or error detection: The authors ask whether error-correction schemes can reduce cut-query error without substantially increasing r.They view the published Laplacian as a code containing mostly correct approximate cut answers, but could not prove that a self-correcting scheme works.
Error amplification or error detection: The paper also raises whether one can detect when the published Laplacian gives a good cut estimate, potentially using a trivial guess for the cut value.The passage frames error detection as a separate open direction.
Edges between S and T: The method gives utility for cut-queries but no guarantees for E(S,T), because multiplicative errors on large surrounding cuts can overwhelm a small inter-set edge count.The limitation concerns edges connecting two disjoint vertex subsets.
Edges between S and T: The dot-product route has an error bound depending on ∥EG1S∥ and ∥EG1T∥, which may be large.This dependence limits direct estimation of interactions between disjoint subsets.
Other versions and related work: The authors expect qualitatively similar results for dense non-Gaussian JL variants but are uncertain about sparse transforms.Their work also lacks the low-rank approximation guarantees provided by a related differentially private algorithm, though integration may improve that algorithm’s first stage.

A Facts from Linear Algebra

This appendix collects standard linear-algebra facts used in the paper, including variational characterizations and inequalities for singular values, eigenvalues, kernels, and pseudoinverses.

Notation: The appendix defines descending-order eigenvalue and singular-value notation for matrices used throughout the proofs.The notation is evi(M) for the i-th eigenvalue and svi(M) for the i-th singular value.
Singular-value facts: The Courant-Fischer min-max principle characterizes each singular value through an extremal optimization over subspaces and unit vectors.This characterization underlies the proof of Fact 3.5.
Singular-value facts: Weyl’s inequality implies ordered singular values increase when a positive-semidefinite difference E = B − A satisfies x^TEx ≥ 0 for every x.The appendix applies this claim directly to LG and LG′.
Pseudoinverse facts: For positive-semidefinite matrices with the same kernel, the quadratic-form order x^TAx ≤ x^TBx reverses under pseudoinversion: x^TA†x ≥ x^TB†x.The proof decomposes vectors into the common kernel and its orthogonal complement, then uses SVDs and a constructed matrix C.
Eigenvalue facts: Lindskii’s theorem and Wielandt’s min-max principle provide the eigenvalue interlacing tools used to prove Fact 4.4.The appendix states the relevant min-max and perturbation results before invoking the observation about a symmetric matrix’s eigenvalues.