Node-Differentially Private Estimation of the Number of Connected Components

Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, Charalampos E. TsourakakisACM Trans. Algorithms 2023 · OpenReview

TL;DR

This paper introduces the first algorithm for estimating the number of connected components in a graph while providing node-differential privacy. This is a significant achievement because this graph statistic is notoriously difficult to protect under node-privacy due to its sensitivity to single node additions. The proposed algorithm achieves a near-optimal error bound, making it practical for real-world applications.

What Problem Does This Paper Address?

When analyzing graph data that represents sensitive relationships (like social networks), releasing aggregate statistics can inadvertently leak individual information. Differential privacy offers a strong guarantee against such leaks. However, applying it to graph data is challenging, especially with node-differential privacy, which protects an individual and all their connections. Estimating the number of connected components (a fundamental graph property) is particularly tricky under node-privacy because adding a single node with connections can drastically change this count, making it hard to provide meaningful privacy guarantees. Existing node-private algorithms often struggle with this statistic, or their privacy guarantees are too coarse.

Methods

The core of the paper's contribution lies in designing a family of Lipschitz extensions for the number of connected components (or equivalently, the size of a spanning forest). A Lipschitz extension is a function that approximates the original statistic while being "smooth" with respect to the privacy definition. The authors leverage the forest polytope of a graph to construct these extensions. They also introduce a novel approach based on degree-bounded spanning forests and induced stars to analyze the quality of these extensions. The algorithm then uses the Generalized Exponential Mechanism (GEM) to select the best extension for a given graph and release a noisy but accurate estimate.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis for general graphs.

Key Insights and Ideas

  • Node-Privacy is Hard for Connected Components: The paper highlights why estimating connected components is a major hurdle for node-differential privacy: the statistic is highly sensitive to the addition of a single node, which is precisely what node-privacy aims to hide.
  • Lipschitz Extensions as a Solution: The authors demonstrate that carefully constructed Lipschitz extensions can bridge the gap between sensitive graph statistics and privacy guarantees.
  • Forest Polytope Power: The forest polytope provides a rich structure for building these privacy-preserving extensions.
  • Degree-Bounded Spanning Forests: Connecting the existence of low-degree spanning forests to the absence of "induced stars" in a graph is a key combinatorial insight. This helps bound the error of the privacy mechanism.
  • Instance-Based Accuracy: Instead of a worst-case guarantee, the algorithm provides accuracy bounds that depend on specific properties of the input graph (like $\Delta^*$, the smallest possible maximum degree of a spanning forest), making it more practical.

Key Results

  • First Node-Private Algorithm: The paper presents the first algorithm for node-differentially private estimation of the number of connected components.
  • Near-Optimal Error Bound: The algorithm achieves an additive error of $\widetilde{O}(\frac{\Delta^*\ln\ln n}{\varepsilon})$, where $\Delta^*$ is the smallest possible maximum degree of a spanning forest of the graph. This bound is considered near-optimal and is low for real-world networks.
  • Polynomial Time Complexity: The algorithm runs in polynomial time, making it computationally feasible.
  • Optimality of Extensions: The paper proves that their Lipschitz extensions are nearly optimal in terms of both anchor set size and $\ell_\infty$ error, comparing favorably to theoretical best-case scenarios.

Limitations and Future Work

  • Faster Algorithms: The authors suggest that an open direction is designing a faster algorithm that maintains the same privacy and utility guarantees.
  • Generalization: While this paper focuses on connected components, the techniques developed might be applicable to other graph statistics that are currently challenging for node-differential privacy.
  • Empirical Evaluation: The paper is theoretical; future work could involve empirical evaluation on real-world datasets to demonstrate practical performance.

Summary updated

Abstract

We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an n-vertex graph G and a privacy parameter ε, our algorithm runs in polynomial time and, with probability 1-o(1), has additive error Õ(Δ^*łnłn nε ), where Δ^* is the smallest possible maximum degree of a spanning forest of G. Node-differentially private algorithms are known only for a small number of database analysis tasks. A major obstacle for designing such an algorithm for the number of connected components is that this graph statistic is not robust to adding one node with arbitrary connections (a change that node-differential privacy is designed to hide): every graph is a neighbor of a connected graph. We overcome this by designing a family of efficiently computable Lipschitz extensions of the number of connected components or, equivalently, the size of a spanning forest. The construction of the extensions, which is at the core of our algorithm, is based on the forest polytope of G. We prove several combinatorial facts about spanning forests, in particular, that a graph with no induced Δ-stars has a spanning forest of degree at most Δ. With this fact, we show that our Lipschitz extensions for the number of connected components equal the true value of the function for the largest possible monotone families of graphs. More generally, on all monotone sets of graphs, the l∞ error of our Lipschitz extensions is nearly optimal.
BibTeX
@article{kalemaj2023node,
  author = {Iden Kalemaj and Sofya Raskhodnikova and Adam D. Smith and Charalampos E. Tsourakakis},
  title = {{Node-Differentially Private Estimation of the Number of Connected Components}},
  journal = {ACM Trans. Algorithms},
  year = {2023},
  url = {https://openreview.net/forum?id=LZeshuTwzx},
}
Figure