Privacy-Preserving Sketching: Balancing OSN Data Utility and Anonymity

TL;DR

Sharing Online Social Network (OSN) data is a double-edged sword: it’s vital for research and advertising but catastrophic for privacy. This paper introduces the bottom-(l, k) sketch, an evolution of All-Distance Sketching (ADS) that removes 80% of redundant edges while preserving critical structural properties like shortest paths. By adding dummy paths and deleting real ones, the authors create a "probabilistic shield" that thwarts advanced de-anonymization attacks.

Context: The Privacy-Utility Tug-of-War

From the Facebook-Cambridge Analytica scandal to modern data mining, the risk of "de-anonymization" is real. Attackers use "seed nodes" (high-degree users) or subgraph patterns to map anonymized graphs back to real identities.

Current SOTA methods like ε-differential privacy often introduce too much noise, turning a social network into a "random graph" where the original structural insights—like how fast a rumor spreads—are lost. The authors identify a "sweet spot": Sketching.

The Problem with Basic Sketching

While ADS accurately estimates distances by keeping nodes with the lowest hash values (ranks), it has two fatal flaws for privacy:

1. Zero False Positives: Since ADS only removes edges, every edge in a published sketch must exist in the original graph.
2. Second-Round ADS Attacks: An intelligent attacker can run a sketch on the published sketch to filter out "unimportant" dummy edges, exposing the true "backbone" of the network.

Methodology: The Bottom-(l, k) Innovation

To fix this, the authors propose bottom-(l, k) sketch.

1. The Core Intuition

Instead of just keeping the $k$ lowest-ranked nodes, the algorithm ensures that for any node $u$ in the sketch of $v$, there are at least $l$ distinct paths between them. This redundancy effectively hides the "true" path among several plausible alternatives.

2. The Algorithm Workflow

The process involves three sophisticated steps:

• Sketch Generation: Building a residual matrix to track required paths.
• Obfuscation: Adding intermediate nodes to create "dummy" paths that look structurally important.
• Edge Changing: Randomly swapping edges based on an Edge-to-Path Matrix (Mp) to meet a "Privacy Budget" without breaking the (l, k) property.

Fig 1: The transformation from an original graph (a) to a sketched representation (b) and finally a disturbed, published graph (d).

Performance: High Privacy, Low Loss

The paper evaluates the method against the dK-2 differential privacy model using real-world datasets (Facebook, Enron).

Key Findings:

• Shortest Path Preservation: While dK-2 often doubles the average shortest path length (making the graph "stretched"), the bottom-(l, k) sketch maintains a length very close to the original (see Fig 2).
• Centrality Gains: Metrics like Betweenness and Closeness Centrality—which indicate who the "influencers" are—remain highly accurate in the sketched graph, whereas they collapse under traditional differential privacy.
• Data Reduction: The method achieves privacy by actually reducing data volume (removing ~80% of edges), making it more efficient for third-party researchers to handle.

Fig 2: Shortest path distribution comparison. The (l, k) sketch (blue/red lines) closely tracks the original (black line), significantly outperforming the dK-2 reference (dashed lines).

Critical Insight: Average ε-Privacy

A major contribution of this work is the mathematical bridge between Sketching and Differential Privacy. The authors prove an "Average Privacy Parameter" (εa), showing that sketching has a similar information-leakage bound to traditional noise-injection methods, but with vastly superior utility.

Conclusion & Limitations

The bottom-(l, k) sketch is a robust framework for OSN data publication. It shifts the focus from "adding noise" to "structural summarization."

Limitations: The method currently focuses on unweighted graphs and static topologies. Future work would need to address dynamic OSNs where users and edges change over time, requiring a "rolling" sketch that maintains privacy across snapshots.

Takeaway for Practitioners: If you need to share graph data without losing the "topology" that makes social networks meaningful, stop looking at global noise and start looking at local structural sketches.