Graph Compression Cuts Privacy Noise in Social Network Clustering by Up to 20 Percent

Social networks hold some of the most intimate maps of modern life: who talks to whom, who shares a friend circle, who belongs to which community. Analyzing those maps can improve recommendation systems, detect fraud, and reveal hidden patterns of group behavior, but doing so on decentralized platforms means asking millions of users to hand over their friend lists to a server that nobody can fully trust. A new study published in the journal Cybersecurity proposes a way to have it both ways, showing that a classic data-compression trick borrowed from text processing can dramatically improve the accuracy of privacy-preserving graph clustering.

The research, led by Dongyue Zhang of Hebei University of Science and Technology with colleagues from Southeast University, Wuxi University, and the National University of Defense Technology, introduces a scheme called GCC-LDP. It tackles a stubborn tension at the heart of local differential privacy, or LDP, the gold-standard privacy model in which each user perturbs their own data on their device before it ever reaches a collector. Under LDP, no honest-but-curious server ever sees a raw friend list, which matters in an era when the Cambridge Analytica scandal exposed the personal information of roughly 87 million Facebook users through the platform’s own API.

The problem with applying LDP to graphs is dimensional. Each user in a decentralized social network only holds a star graph, a one-hop view of themselves and their direct neighbors. To encode that view for a network of n users, existing methods such as LF-GDPR represent it as an adjacency bit vector of length n, one bit per possible connection. To satisfy edge-level LDP, every one of those bits must be randomly flipped with some probability, a perturbation technique known as randomized response. The noise injected scales with the length of the vector, which scales with the number of users. In large networks, the perturbed data becomes so saturated with fake edges that the synthetic graph the collector reconstructs bears little resemblance to reality, and any clustering performed on it degrades accordingly.

Earlier approaches took the opposite tack. LDPGen, a landmark 2017 method, encodes each user’s star graph as a short degree vector, counting how many of the user’s edges reach each of a set of randomly assigned groups. Because these vectors are short, the perturbation cost is low, but the encoding captures only coarse degree information and discards connectivity entirely. Nodes with similar degrees but distant positions in the original graph can end up clustered together, and the method effectively clusters a graph without edges. A later refinement, Wdt-SCAN, partitions nodes into core and ordinary nodes using the Pareto principle to shield the noisiest parts of the data, but it still works from structurally impoverished encodings. Both families of methods also share a second flaw: they need many rounds of interaction and iterative aggregation, often with K-means or Louvain-style optimization, which accumulates statistical error at every step and slows the whole pipeline down.

GCC-LDP attacks both weaknesses at once. Its first component, the adjacency set vector encoding model, or AEM, shrinks the graph before anyone perturbs it. The collector first strips out peripheral nodes, the low-degree users whose sparse star graphs are disproportionately corrupted by randomized response. The arithmetic is stark: in a thousand-node graph, a peripheral node with only two real edges and a bit-flip probability of just 0.01 is expected to generate ten false edges, five times its true connections. On a sparse network like Facebook, whose graph density is around 0.01 percent, even a generous privacy budget of 1 inflates the expected synthetic density to 0.27 percent, a twenty-seven-fold rise. Removing such nodes, the authors prove, does not reduce graph density and therefore does not harm the structural skeleton that clustering depends on.

The second compression step is where the scheme gets clever. Drawing on Re-Pair, a recursive grammar-compression algorithm originally designed for compressing strings by repeatedly replacing the most frequent pair of symbols, AEM merges pairs of non-peripheral nodes that are strongly connected, meaning they share many common neighbors relative to the union of their neighborhoods. The rationale rests on homophily, the well-documented tendency of people with many mutual friends to belong to the same social circle and hence the same community. Merging such pairs into macro-nodes reduces the node count exponentially across compression rounds while preserving connectivity at a coarser granularity, and because strongly connected nodes are likely to end up in the same cluster anyway, the merging barely distorts the final partition. Each user then encodes their star graph against the compressed node set using a ternary adjacency set vector, whose entries distinguish no connection, partial connection to one member of a macro-node, and full connection to both members. That third state turns out to be statistically valuable: a least-squares correction exploits it to cut connection-strength estimation error by four fifteenths.

Privacy is preserved throughout by construction. Each entry of the adjacency set vector is independently perturbed by randomized response, reporting the true value with probability e to the epsilon over e to the epsilon plus two, and each alternative with equal probability otherwise, which satisfies epsilon-LDP for every vector. Because the compression rounds compose sequentially, the total privacy cost is the sum of the per-round budgets, and the authors allocate two thirds of the budget to the encoding phase, where noise sensitivity is highest, and one third to the final label reporting. Everything the collector does afterward, including merging and clustering, counts as post-processing, which LDP theory guarantees leaks no additional privacy.

The second component of GCC-LDP replaces iterative clustering with a fixed two-round aggregation framework. In the first round, the collector scores each compressed node by a centrality index combining node density, the estimated number of its connections, and node importance, a weighted sum of its neighbors’ degrees. Rather than guessing how many clusters exist, the method sorts these scores and applies a second-order difference, a discrete analogue of the second derivative, to find the knee point where centrality scores fall off sharply. Nodes above the knee become cluster centers automatically. The centers are then expanded into full clusters using a node-similarity metric grounded in group cohesion, counting both direct and indirect connections to each cluster. In the second round, users refine their own cluster labels using their actual neighbor lists, perturb the label through an exponential mechanism calibrated to the sensitivity of the similarity score, and the collector aggregates the results. Two rounds, no iteration, no compounding error.

The theoretical payoff is quantified. Where adjacency-bit-vector methods accumulate total noise on the order of h times n squared over epsilon squared across h collection rounds, GCC-LDP’s progressive compression shrinks the encoding each round, bounding total noise by a constant multiple of n squared over epsilon squared independent of the number of rounds. Communication cost drops to the same order as a single full upload, and running time falls because the aggregation never iterates. Experiments on five real-world datasets, the Zachary Karate Club network, a Facebook page network, an email correspondence network, a Twitch gamer network, and the large-scale DBLP co-authorship network, back the theory up. Against the strongest privacy-preserving baselines, LDPGen, Wdt-SCAN, LF-GDPR, and GC-NLDP, GCC-LDP improved clustering performance by 10 to 20 percent as measured by Adjusted Rand Index, Adjusted Mutual Information, and Relative Error, with the largest gains in the strict-privacy regime where noise dominates. On the Karate network, the method correctly reproduced the club’s famous real-world split, identifying the true leaders as cluster centers and misclassifying only a single boundary node.

The implications reach beyond social networks. Any platform that wants to mine community structure from user-held connection data, messaging apps, telecom providers analyzing contact graphs, collaboration networks, could adopt the compress-then-perturb pattern to get more signal out of the same privacy budget. The authors point to clear next steps: extending the framework to attributed, weighted, and uncertain graphs, exploring community-aware handling of small or sparse clusters, and investigating stronger privacy paradigms such as shuffled and node-level LDP, which currently demand noise levels that cripple utility. For now, the study makes a compelling case that the road to private graph analysis runs through compression: the smaller the message, the less noise needed to hide it, and the sharper the picture that emerges on the other side.

Subject of Research: Privacy-preserving clustering of decentralized social graphs under local differential privacy using structure-preserving graph compression

Article Title: Locally differentially private graph clustering via structure-preserving graph compression

Article References: Zhang, D., Ni, W., Fu, N., & Yao, H. (2026). Locally differentially private graph clustering via structure-preserving graph compression. Cybersecurity, 9(1), Article 223. https://doi.org/10.1186/s42400-026-00652-w

Image Credits: AI Generated

DOI: 10.1186/s42400-026-00652-w

Keywords: local differential privacy, graph clustering, graph compression, Re-Pair, social networks, randomized response, decentralized graphs, privacy-preserving data analysis, community detection, cybersecurity, GCC-LDP, adjacency set vector