Abstract: In this paper, we focus on answering queries, in a differentially private manner, on graph streams. We adopt the sliding window model of privacy, where we wish to perform analysis on the last $W$ updates and ensure that privacy is preserved for the entire stream. We show that in this model, the price of ensuring differential privacy is minimal. Furthermore, since differential privacy is preserved under post-processing, our results can be used as a subroutine in many tasks, including Lipschitz learning on graphs, cut functions, and spectral clustering.
Introduction
Graph analysis is essential for applications ranging from community detection in social networks to contact tracing in epidemiology. However, real-world graphs are rarely static; they arrive as streams of updates. Furthermore, recent data is often more relevant than old data, leading researchers to use a sliding window model (e.g., "only analyze the last three months of data").
This paper, presented at AISTATS 2021, introduces the first efficient differentially private (DP) algorithm for analyzing graph streams within this sliding window framework. By leveraging a novel "Smooth Laplacian" property, the authors demonstrate how to maintain a private approximation of a graph's spectrum using space that is logarithmic in the window size, enabling tasks like spectral clustering and cut approximation on dynamic, privacy-sensitive data.
The Challenge of Private Graph Streams
Maintaining privacy and efficiency in graph streams presents two primary hurdles:
- Privacy: Standard graph analysis can leak sensitive information about individual edges. While Differential Privacy (DP) is the gold standard for protection, most DP graph algorithms assume a static dataset.
- Efficiency: Storing every update in a large window is memory-intensive. In non-private settings, "smooth histograms" allow for sub-linear space complexity, but extending this to the complex world of matrices (graph Laplacians) and privacy is mathematically non-trivial.
Methodology: The SLIDING-PRIV-GRAPH Algorithm
The core of the research is the SLIDING-PRIV-GRAPH algorithm, which integrates several sophisticated techniques:
- Gaussian Mechanism: To ensure privacy, the algorithm "overlays" the input graph with a weighted complete graph where edge weights are sampled from a Gaussian distribution. This provides "plausible deniability" for the presence or absence of any single edge.
- Smooth Laplacian Property: This is the paper's primary theoretical innovation. In scalar streaming, one can prune old data if it doesn't significantly change a sum. For graphs, the authors define a way to prune "checkpoints" (representative graphs from specific time intervals) if their Laplacian matrices are spectrally similar.
- Matrix Ordering: Unlike scalars, matrices do not have a simple linear order. The authors develop a strategy to maintain a small set of checkpoints that "sandwich" any possible sliding window, ensuring the approximation remains accurate.
- Spectral Sparsification: The authors provide a DP version of spectral sparsification, reducing a dense graph to a much sparser one while preserving its structural properties like cuts and eigenvalues.
Key Results and Comparative Analysis
As a theoretical research paper, the work focuses on algorithmic design and provable guarantees. The algorithm achieves significant improvements in space efficiency and utility:
- Space Efficiency: The algorithm uses $O(\min\{W, \frac{n^3 \log W}{\rho}\})$ space, where $W$ is the window size and $n$ is the number of vertices. This is a massive improvement over storing the full window when $W$ is large.
- Spectral Guarantee: The output graph $\tilde{G}$ is a $(1 \pm \rho)$-spectral approximation of the true windowed graph $G_W$, plus an additive error term that scales with $\sqrt{\log n \log W} / \epsilon$.
- Improved Cut Queries: The paper provides a comparison of their work to previous state-of-the-art DP graph algorithms. In many regimes, especially for specific $(S, T)$ queries, this work provides tighter error bounds than earlier static models.
Discussion and Future Work
While this work sets a new benchmark for private graph streaming, several avenues for future research remain:
- Cubic Dependence on $n$: The current space complexity depends on $n^3$. Non-private algorithms can achieve $n^2$, and it remains an open question whether the DP version can be similarly optimized.
- Lower Bounds: While the authors provide upper bounds on error and space, they haven't yet established the theoretical lower bounds for what is possible in private sliding window graph analysis.
- Empirical Validation: Future work could involve implementing these algorithms on massive real-world streams (like social media or financial transaction logs) to evaluate the practical performance of the theoretical constants.
Summary updated