Differentially Private Graph Data Publishing via Feature-Based Community Detection
摘要
Graph data publishing is essential for numerous applications but raises privacy concerns due to sensitive relationships embedded within the data. Differential privacy is introduced into the Graph data publishing to eliminate privacy concerns. However, existing differentially private graph data publishing method suffer from excessive noise or structural distortions due to random community partitioning. Specifically, data utility does not increase as the privacy budget increases when random partitioning community. To this end, we propose a novel feature-based community detection approach for differentially private graph publishing. Our method leverages structural features extracted from local node neighborhoods to form privacy-aware communities so that data utility continuously increases as privacy budget increases. In other words, our method can overcome the utility growth bottlenecks of existing approaches. Experiments on real-world datasets demonstrate that our method significantly outperforms state-of-the-art methods across multiple structural metrics while maintaining formal privacy guarantees.