# Node-Differentially Private Estimation of the Number of Connected Components

arXiv: https://arxiv.org/abs/2304.05890 · HTML: https://mlsanity.com/paper/2304.05890/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2023.

## Built on by (most cited first, 4 of 4)

- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [It's My Data Too: Private ML for Datasets with Multi-User Training Examples](https://mlsanity.com/paper/2503.03622/) (2025)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Differentially Private Modeling of Disease Transmission within Human Contact Networks](https://mlsanity.com/paper/2604.07493/) (2026)

## Abstract (arXiv)

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 varepsilon, our algorithm runs in polynomial time and, with probability 1-o(1), has additive error widetildeO(fracDelta^*lnln nvarepsilon), where Delta^* 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 Delta-stars has a spanning forest of degree at most Delta. 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 ℓ_∞ error of our Lipschitz extensions is nearly optimal.