On Differentially Private Graph Sparsification and Applications

Raman Arora, Jalaj UpadhyayNeurIPS 2019 · OpenReview

Introduction

Graph data, such as social networks and communication logs, is incredibly rich but often highly sensitive. To process massive graphs efficiently, researchers frequently rely on spectral sparsification—a technique that reduces a graph with millions of edges to a much smaller one that behaves almost identically in terms of its Laplacian matrix.

However, traditional sparsification is fundamentally incompatible with Differential Privacy (DP). A sparsifier inherently selects a few "important" edges to preserve the graph's structural essence. If an edge is critical to the graph's structure, its presence in the output reveals its existence in the input, directly violating privacy guarantees.

Previous approaches to differentially private graph processing were either task-specific (tailored for a single problem like counting triangles) or structure-destroying (outputting a private matrix that isn't actually a valid graph, breaking compatibility with standard graph-processing tools). This paper introduces the first efficient algorithm for differentially private spectral sparsification of graphs. By producing a sparse, private representation that preserves the original graph's spectrum, the authors enable a suite of downstream applications—like MAX-CUT, SPARSEST-CUT, and Laplacian eigenmaps—with significantly better accuracy and efficiency than previous methods.

The PRIVATE-SPARSIFY Algorithm

The authors tackle the challenge of creating a "meta-algorithm" that outputs a private, sparse graph that remains useful for many different spectral tasks. They propose PRIVATE-SPARSIFY, a multi-stage approach combining random sketching with optimization:

  1. Private Sketching: The algorithm uses Gaussian random matrices to "sketch" the left and right singular vectors of the graph's edge-adjacency matrix. This allows for the private estimation of effective resistances (a measure of how "important" an edge is to overall connectivity).
  2. Plausible Deniability: To satisfy DP, the input graph is "overlaid" with a weighted complete graph. This introduces noise that provides deniability; any edge in the output could have come from the original data or the added noise.
  3. SDP Sanitization: The authors solve a Semi-Definite Program (SDP) to find a "sanitized" graph that closely approximates the original spectrum while remaining within the strict bounds required for privacy.
  4. Final Sparsification: Once a private (but potentially dense) representation is secured, a standard, non-private sparsification algorithm is applied to prune it down to $O(n/\epsilon^2)$ edges.

Key Insights

  • The "Relaxation" of Sparsification: The authors mathematically prove that "pure" spectral sparsification is impossible under DP. Their breakthrough is defining a well-posed relaxation: approximating the spectrum of the input graph plus a small multiple of a complete graph ($L_n$). This "additive error" is the necessary price paid for privacy.
  • Importance Sampling meets DP: While importance sampling (sampling edges based on effective resistance) is a staple of graph theory, this paper is one of the first to demonstrate how to compute those sampling probabilities privately without losing too much structural information.
  • Preserving "Graph-ness": Unlike previous work that outputs generic symmetric matrices, this method ensures the output is a valid Laplacian of a graph with positive weights. Consequently, the output can be plugged directly into any existing graph algorithm.

Key Results and Improved Bounds

The algorithm successfully produces a sparse graph with only $O(n/\epsilon^2)$ edges (where $n$ is the number of nodes) while satisfying $(\alpha, \beta)$-differential privacy at the edge level.

Because the output preserves the graph's spectrum, it yields immediate improvements for several classic graph problems.

Comparison of additive errors between the proposed method and previous best approaches for various graph problems.

As shown in the table above, the algorithm achieves an additive error for the MAX-CUT problem that scales sublinearly with $n$. Specifically, it improves upon the previous state-of-the-art by reducing the error from $O(n^{3/2}/\alpha)$ to $O(|S_m|\sqrt{n}/\alpha)$. Similar improvements are demonstrated for SPARSEST-CUT and general cut queries. Furthermore, the paper provides the first efficient DP algorithm for learning Laplacian eigenmaps, a popular technique in manifold learning and dimensionality reduction.

Limitations and Future Work

While theoretically rigorous, the approach has a few limitations:

  • Computational Complexity: The algorithm requires solving a Semi-Definite Program (SDP). While SDPs are solvable in polynomial time, they can be computationally expensive for extremely large graphs compared to simpler randomized projections.
  • Additive Error on Sparse Graphs: The privacy guarantee necessitates an additive error term related to the complete graph. While often small, this error might be significant for very sparse graphs where the injected "noise" could overwhelm the structural signal.
  • Weighted Graphs: The primary focus and most elegant results apply to unweighted or integer-weighted graphs. Further optimization for graphs with high-precision continuous weights remains an open direction for future research.

Summary updated

Abstract

In this paper, we study private sparsification of graphs. In particular, we give an algorithm that given an input graph, returns a sparse graph which approximates the spectrum of the input graph while ensuring differential privacy. This allows one to solve many graph problems privately yet efficiently and accurately. This is exemplified with application of the proposed meta-algorithm to graph algorithms for privately answering cut-queries, as well as practical algorithms for computing {\scshape MAX-CUT} and {\scshape SPARSEST-CUT} with better accuracy than previously known. We also give the first efficient private algorithm to learn Laplacian eigenmap on a graph.
BibTeX
@inproceedings{arora2019differentially,
  author = {Raman Arora and Jalaj Upadhyay},
  title = {{On Differentially Private Graph Sparsification and Applications}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=cvWphIv-xFd},
}
Figure