CGGen: Shielding Correlated Social Networks with Advanced Local Differential Privacy

TL;DR

The exponential growth of social network data has made privacy-preserving data sharing a critical challenge. Modern techniques like Local Differential Privacy (LDP) often fail by assuming social nodes are independent. CGGen breaks this mold by modeling Intra-group and Inter-group correlations, allowing for the generation of highly accurate synthetic graphs that protect sensitive ties without destroying the "community" intelligence within the data.

The "Independence" Fallacy in Graph Privacy

In traditional Differential Privacy (DP), we assume that adding or removing one record affects the result only slightly. However, social graphs are correlated. If Alice and Bob are close friends, their neighbor lists are not independent. Previous SOTA methods like LDPGen often ignored these correlations when merging local user lists into a global graph.

Why is this a problem?

1. Privacy Leakage: If a malicious actor knows the correlation, they can reverse-engineer the "noise" added to the data.
2. Utility Loss: Treating every edge as equally sensitive results in "over-blurring," where the synthetic graph loses its original topological properties (like clustering coefficients).

Methodology: Quantifying "Social Similarity"

CGGen introduces a two-tier correlation mechanism to refine privacy protection:

1. Intra-group Correlation

Using Hamming distance, the paper measures how many common neighbors two users share. If the distance is small, they likely belong to the same community. This correlation coefficient (${\phi }_{u_i}$) determines the specific Laplace noise sensitivity for that user.

2. Inter-group Correlation

Groups aren't islands. CGGen measures how communities interact (Inter-group correlation ${\mathbb{W}}_{\alpha }$). This ensures that the global synthetic graph preserves the "bridge" edges that connect different social clusters.

Figure 1: Illustration of how users (1, 2, 3, 4) form a highly correlated community based on shared edges.

The CGGen Pipeline

The framework follows a three-step dance:

1. Local Perturbation: Users perturb their degree vectors using LDP based on identified correlations.
2. Optimal Clustering: The algorithm automatically determines the best number of clusters ($k_1$) to minimize the L1 distance between raw and noisy data.
3. Graph Synthesis: Using the BTER (Block Two-Level Erdős-Rényi) model, a global synthetic graph is generated that mimics the original's degree distribution.

Experimental Validation: Outperforming the SOTA

The researchers tested CGGen against LDPGen and DGG on two massive datasets: Facebook (Social) and Enron (Email).

Performance Highlights:

• Accuracy (AMI/ARI): CGGen showed a consistent lead in preserving the community structure. As the privacy budget ($ϵ$) increases, CGGen’s ability to recover original clusters scales much faster than LDPGen.
• Structural Fidelity: In metrics like Assortativity Coefficient (which measures if high-degree nodes connect to other high-degree nodes), CGGen achieved an error as low as 0.05.

Figure 2: Performance comparison on Facebook (left) and Enron (right) datasets showing CGGen's superiority in Adjusted Mutual Information (AMI).

Critical Insight & Conclusion

The core contribution of CGGen is proving that privacy and utility are not a zero-sum game. By understanding how data is correlated, we can be smarter about where we place the noise.

Takeaway for the Industry: If you are building decentralized data analytics platforms (e.g., for federated social apps), generic LDP is not enough. You must implement Topology-Aware Privacy. CGGen provides the mathematical foundation to do exactly that, ensuring that synthetic data remains a "digital twin" of the original social structure while keeping individual identities safe.

Limitations: While CGGen excels at undirected graphs, real-world social data is often dynamic and directed. Future iterations would need to address how these correlations evolve over time as new edges are formed.