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 W R^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 _ in each entry, i. e. , we consider an _ neighboring relationship. Existing private MST algorithms either add noise to each entry in W 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 (n²) time on dense graphs but results in an additive error on the weight of the MST of magnitude O (n² n). In-place algorithms give asymptotically better utility, but the running time of existing in-place algorithms is O (n³) 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 + n^3/2 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 _ 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 (n²) cut edges in O (n n) time. Experimental evaluations support our claims that our algorithm significantly improves previous algorithms either in utility or running time.