1HIkDA: A Novel Privacy Preserving Framework for Graph Data Publication

As graph-based data storage becomes increasingly prevalent, the demand for robust privacy protection during data publication has intensified. A fundamental tension, however, exists between the level of privacy protection and the utility of anonymized graph: achieving stronger privacy often necessitates substantial alterations to the original graph (e.g., adding or removing nodes or edges), which can compromise critical graph attributes and reduce practical value. Addressing this challenge, we propose a two-phase privacy protection framework, 1HIkDA, designed to ensure both1-hop indistinguishable and k-degree anonymity, thus offering enhanced resilience against unknown structural attacks. To optimize the usability of anonymized graphs, our framework integrates two distinct algorithms: the Greedy-based 1-hop Indistinguishable (G1HI) algorithm and the Wasserstein and Regularization-based k-degree Anonymity (WRkDA) algorithm. The G1HI algorithm achieves neighbor-hood indistinguishability with minimal modifications and low costs, while the WRkDA algorithm minimizes the Wasserstein dis-tance between degree distributions pre-and post-anonymization to meet k-degree anonymity requirements. Extensive experiments conducted on nine synthetic and real-world networks have demonstrated the effectiveness and efficiency of the proposed scheme.