# Faster Private Minimum Spanning Trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 13 Aug 2024.

## Builds on (most cited first, 9 of 9)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [Shortest Paths and Distances with Differential Privacy](https://mlsanity.com/paper/1511.04631/) (2015)
- [Minimum spanning tree release under differential privacy constraints](https://mlsanity.com/paper/1801.06423/) (2018)
- [Graph-based Clustering under Differential Privacy](https://mlsanity.com/paper/1803.03831/) (2018)
- [Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree](https://mlsanity.com/paper/2308.00503/) (2023)
- [Near-Universally-Optimal Differentially Private Minimum Spanning Trees](https://mlsanity.com/paper/2404.15035/) (2024)

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

- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)

## Abstract (arXiv)

Motivated by applications in clustering and synthetic data generation, we consider the problem of releasing a minimum spanning tree (MST) under edge-weight differential privacy constraints where a graph topology G=(V,E) with n vertices and m edges is public, the weight matrix vecW∈ ℝn × n is private, and we wish to release an approximate MST under ρ-zero-concentrated differential privacy. Weight matrices are considered neighboring if they differ by at most Delta_∞ in each entry, i.e., we consider an ℓ_∞ neighboring relationship. Existing private MST algorithms either add noise to each entry in vecW and estimate the MST by post-processing or add noise to weights in-place during the execution of a specific MST algorithm. Using the post-processing approach with an efficient MST algorithm takes O(n2) time on dense graphs but results in an additive error on the weight of the MST of magnitude O(n2log n). In-place algorithms give asymptotically better utility, but the running time of existing in-place algorithms is O(n3) for dense graphs. Our main result is a new differentially private MST algorithm that matches the utility of existing in-place methods while running in time O(m + n3/2log n) for fixed privacy parameter ρ. The technical core of our algorithm is an efficient sublinear time simulation of Report-Noisy-Max that works by discretizing all edge weights to a multiple of Delta_∞ and forming groups of edges with identical weights. Specifically, we present a data structure that allows us to sample a noisy minimum weight edge among at most O(n2) cut edges in O(√n log n) time. Experimental evaluations support our claims that our algorithm significantly improves previous algorithms either in utility or running time.