LDPGen: Crafting Privacy-Preserving Social Graphs from Decentralized Data

TL;DR

Analyzing social networks often requires a "God's eye view," yet real-world data like phone contacts or private communications are decentralized. LDPGen bridges this gap by using Local Differential Privacy (LDP) to collect structural information without ever seeing a user's raw neighbor list. By grouping users into "structural clusters" and synthesizing a graph from these clusters, it preserves community features that previous methods simply erased with noise.

The Decentralization Paradox

In a centralized network (like most of Facebook's internal analysis), a single party sees the whole graph. But in decentralized contexts—think of P2P networks like Synereo or even the aggregate of everyone's private phone contacts—no one owns the map.

If we want to study these networks without violating privacy, we face the Noise vs. Resolution trade-off:

1. High Resolution (RNL): Ask everyone for their neighbor list and flip bits to hide identities. Result: The graph becomes a massive "hairball" of noise because even a 1% bit-flip probability can create millions of fake edges in a sparse network.
2. Low Resolution (DGG): Just ask everyone for their total number of friends (degree). Result: You get the scale right, but lose the "who connects to whom" structure, making community detection impossible.

Methodology: The Power of Structural Clustering

LDPGen's core insight is that connectivity is a feature. If two users have similar connection patterns to different parts of the population, they likely belong to the same community.

Phase I: The Rough Sketch

The curator starts with a random partition of users. Each user reports a Noisy Degree Vector—not who they know, but how many people they know in each random partition. Using a derived optimization formula, the curator determines the ideal number of groups ($k_1$) to balance privacy noise and structural loss.

Phase II: Structural Refinement

Using the first round of reports, the curator uses k-means clustering to group users who have similar connectivity patterns. This moves "structurally similar" users into the same buckets. The users then report their degree vectors again, this time relative to these much more meaningful clusters.

Phase III: Graph Synthesis

Finally, the curator uses the BTER (Block Two-Level Erdos-Renyi) model. It creates dense "intra-cluster" edges for communities and sparse "inter-cluster" edges to maintain the "small-world" property of the original graph.

Experimental Results: High Utility Under Pressure

The researchers tested LDPGen against four real-world datasets. The results were striking in three key areas:

1. Graph Statistics: For metrics like Assortativity and Modularity, LDPGen maintained 80%+ accuracy where baselines fell below 20%.
2. Community Discovery: In the ARI/AMI tests (which measure how well detected communities match the ground truth), LDPGen's performance scaled beautifully with the privacy budget $ϵ$, while straw-man methods remained flat at near-zero utility.
3. Social Recommendation: In tasks like predicting which movie a user might like based on their friends' ratings, LDPGen provided highly relevant results (NDCG > 0.6) compared to the failure of degree-only methods.

Figure: Performance on Facebook dataset showing LDPGen's superior modularity preservation.

Critical Insight & Conclusion

Why does LDPGen work? It exploits the Parallel Composition property of Differential Privacy. By asking for counts over disjoint groups rather than individual bits, it keeps the sensitivity low while the information gain remains high.

Takeaway: The future of social analytics isn't about collecting more data, but collecting smarter aggregations. LDPGen proves that we don't need to see the edges to understand the shape of the web.

Limitations

• Edge Privacy vs. Node Privacy: LDPGen focuses on Edge-LDP (hiding the presence of a specific connection). Protecting the entire presence of a node is significantly harder and remains an open challenge for this level of utility.
• Static Nature: The model assumes a snapshot of a graph; applying this to dynamic, evolving social networks would require further budget-splitting over time.