Differentially Private Minimum Spanning Tree in Euclidean Graphs

Zongrui Zou, Alessandro Epasto, Chenglin Fan, Rudrajit Das
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:379-387, 2026.

Abstract

Many graph learning applications involve analyzing geometric graphs (e.g., nearest neighbor graphs over embeddings) built over sensitive data, thus requiring formal privacy protections. In this paper, we study benchmark problems in privately analyzing geometric graphs obtained from high dimensional embeddings. We provide several new results for the differentially private approximation of minimum spanning trees and hierarchical clustering in Euclidean graphs. Our algorithms achieve a near optimal privacy-utility trade-off (up to constants), providing a $(1+\eta)$-multiplicative approximation with $\tilde{O}(\rho/\eta^2)$ additive error per edge of the tree under $\rho$-dist privacy (a generalization of DP in geometric data where neighboring datasets different in a single point moved by at most $\rho$ distance). Furthermore, we establish a separation between Euclidean and general graphs by proving a lower bound of $\Omega(\rho\sqrt{n})$ additive error per edge of the tree for general graphs under a similar privacy notion, demonstrating that better utility is indeed achievable (allowing also multiplicative approximation) for geometric data. Our algorithm can also be directly applied to widely used clustering algorithm based on MST, incurring only a small loss in the approximation guarantee compared to its non-private counterpart.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-zou26a, title = { Differentially Private Minimum Spanning Tree in Euclidean Graphs }, author = {Zou, Zongrui and Epasto, Alessandro and Fan, Chenglin and Das, Rudrajit}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {379--387}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/zou26a/zou26a.pdf}, url = {https://proceedings.mlr.press/v300/zou26a.html}, abstract = { Many graph learning applications involve analyzing geometric graphs (e.g., nearest neighbor graphs over embeddings) built over sensitive data, thus requiring formal privacy protections. In this paper, we study benchmark problems in privately analyzing geometric graphs obtained from high dimensional embeddings. We provide several new results for the differentially private approximation of minimum spanning trees and hierarchical clustering in Euclidean graphs. Our algorithms achieve a near optimal privacy-utility trade-off (up to constants), providing a $(1+\eta)$-multiplicative approximation with $\tilde{O}(\rho/\eta^2)$ additive error per edge of the tree under $\rho$-dist privacy (a generalization of DP in geometric data where neighboring datasets different in a single point moved by at most $\rho$ distance). Furthermore, we establish a separation between Euclidean and general graphs by proving a lower bound of $\Omega(\rho\sqrt{n})$ additive error per edge of the tree for general graphs under a similar privacy notion, demonstrating that better utility is indeed achievable (allowing also multiplicative approximation) for geometric data. Our algorithm can also be directly applied to widely used clustering algorithm based on MST, incurring only a small loss in the approximation guarantee compared to its non-private counterpart. } }
Endnote
%0 Conference Paper %T Differentially Private Minimum Spanning Tree in Euclidean Graphs %A Zongrui Zou %A Alessandro Epasto %A Chenglin Fan %A Rudrajit Das %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-zou26a %I PMLR %P 379--387 %U https://proceedings.mlr.press/v300/zou26a.html %V 300 %X Many graph learning applications involve analyzing geometric graphs (e.g., nearest neighbor graphs over embeddings) built over sensitive data, thus requiring formal privacy protections. In this paper, we study benchmark problems in privately analyzing geometric graphs obtained from high dimensional embeddings. We provide several new results for the differentially private approximation of minimum spanning trees and hierarchical clustering in Euclidean graphs. Our algorithms achieve a near optimal privacy-utility trade-off (up to constants), providing a $(1+\eta)$-multiplicative approximation with $\tilde{O}(\rho/\eta^2)$ additive error per edge of the tree under $\rho$-dist privacy (a generalization of DP in geometric data where neighboring datasets different in a single point moved by at most $\rho$ distance). Furthermore, we establish a separation between Euclidean and general graphs by proving a lower bound of $\Omega(\rho\sqrt{n})$ additive error per edge of the tree for general graphs under a similar privacy notion, demonstrating that better utility is indeed achievable (allowing also multiplicative approximation) for geometric data. Our algorithm can also be directly applied to widely used clustering algorithm based on MST, incurring only a small loss in the approximation guarantee compared to its non-private counterpart.
APA
Zou, Z., Epasto, A., Fan, C. & Das, R.. (2026). Differentially Private Minimum Spanning Tree in Euclidean Graphs . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:379-387 Available from https://proceedings.mlr.press/v300/zou26a.html.

Related Material