Faster Private Minimum Spanning Trees

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.