# Graph-based Clustering under Differential Privacy

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2018.

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

- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Faster Private Minimum Spanning Trees](https://mlsanity.com/paper/2408.06997/) (2024)
- [Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation](https://mlsanity.com/paper/2412.10130/) (2024)
- [Privacy utility trade offs for parameter estimation in degree heterogeneous higher order networks](https://mlsanity.com/paper/2602.03948/) (2026)

## Abstract (arXiv)

In this paper, we present the first differentially private clustering method for arbitrary-shaped node clusters in a graph. This algorithm takes as input only an approximate Minimum Spanning Tree (MST) T released under weight differential privacy constraints from the graph. Then, the underlying nonconvex clustering partition is successfully recovered from cutting optimal cuts on T. As opposed to existing methods, our algorithm is theoretically well-motivated. Experiments support our theoretical findings.