Differentially Private Random Spanning Tree Generation
Its authors withdrew this paper, so there is no full text to read or summarize.
Lists
Only you see this
Abstract
Random spanning trees (RSTs) are a fundamental object in graph theory with wide-ranging applications in network design, reliability analysis, and randomized algorithms. However, when the underlying graph encodes sensitive information, such as private user relationships or confidential communication links, directly releasing sampled spanning trees may leak critical structural details. To address this issue, we study the problem of generating random spanning trees under differential privacy constraints. We introduce DP-RST, the first algorithmic framework for differentially private random spanning tree generation. Our method perturbs edge weights by decomposing them into binary representations and applying randomized response at the bit level, then recombining the noisy weights and sampling a spanning tree from the perturbed graph. This carefully designed pipeline injects noise while preserving the essential utility of RSTs, thereby ensuring $(\epsilon, \delta)$-DP. We further demonstrate that DP-RST achieves privacy protection with comparable computational efficiency to existing non-private RST algorithms, making it suitable for large-scale graphs. This work bridges the gap between random spanning tree generation and differential privacy, opening new directions for privacy-preserving graph algorithms.
BibTeX
@misc{cao2026differentially,
author = {Yang Cao and Zhao Song and Jiahao Zhang and Jiale Zhao},
title = {{Differentially Private Random Spanning Tree Generation}},
year = {2026},
url = {https://openreview.net/forum?id=j3ZMptxwLP},
howpublished = {OpenReview},
note = {Submitted to ICLR 2026},
}Loading related content...