Locally differentially private graph clustering via structure-preserving graph compression

Abstract

Abstract Locally differentially private clustering is an effective approach to uncover latent structures in decentralized social graphs while preserving individual privacy. Existing solutions encode graph data using adjacency bit vectors, whose high dimensionality introduces substantial differential noise and consequently degrades clustering utility. Besides, they typically require multiple rounds of interaction and iterative aggregation to construct clusters, leading to inevitable error accumulation and reduced clustering efficiency. To address these issues, we propose GCC-LDP, a graph compression-based clustering scheme that achieves efficient and accurate clustering under local differential privacy constraints. Specifically, we introduce an adjacency set vector encoding model, which leverages the Re-Pair compression method to adaptively reduce encoding length, significantly mitigating noise injection. Furthermore, a two-round decentralized social graph aggregation framework is designed to alleviate error accumulation. It employs a second-order difference method to detect distinguishing characteristics among nodes, facilitating rapid identification of cluster centers. Subsequently, a center expansion procedure forms clusters by exploiting intra-group node cohesion, avoiding costly iterative aggregation. Theoretical analysis and experiments on real-world datasets demonstrate that GCC-LDP substantially improves clustering performance by $$10\%$$ 10 % to $$20\%$$ 20 % , significantly outperforming state-of-the-art privacy-preserving clustering methods.