Differentially Private Minimum Spanning Tree in Euclidean Graphs

We study differentially private approximation of minimum spanning trees (MST) and hierarchical clustering for Euclidean graph embeddings. Our algorithms achieve an optimal trade-off, providing a $(1+\eta)$-multiplicative approximation with $\tilde{O}(n/\eta^2)$ additive error under $\rho$-dist privacy. Furthermore, we establish a separation between Euclidean and general graphs by proving a lower bound of $\Omega(n^{1.5})$ additive error for general graphs under a similar privacy notion, demonstrating that better utility is indeed achievable for geometric data. Our algorithm can also be directly applied to clustering tasks based on specific MST algorithms, incurring only a minimal loss in the approximation guarantee compared to its non-private counterpart.