SaNGreeA: Safeguarding Privacy in the Age of Social Graphs

TL;DR

SaNGreeA is a greedy clustering algorithm that provides k-anonymity for social networks by simultaneously generalizing node attributes and network structures. Unlike previous methods that randomly "noise" the graph, SaNGreeA uses a dedicated Structural Information Loss (SIL) metric to ensure the anonymized graph remains useful for researchers while protecting individual identities.

The Multi-Dimensional Privacy Problem

In a standard database, privacy is often about hiding "who participates in what record." In a Social Network, the problem becomes three-dimensional:

1. Identifiers: Standard PII like Names or SSNs.
2. Quasi-identifiers: Attributes like ZipCode or Age which, when combined, identify a person.
3. Structural Identity: Your "neighborhood" (who you are connected to) can be as unique as a fingerprint.

The authors argue that simply anonymizing attributes is insufficient. If an attacker knows your friend group's structure, they can re-identify you even if your name and zip code are masked.

Methodology: The SaNGreeA Approach

The core innovation of SaNGreeA (Social Network Greedy Anonymization) lies in its clustering and collapsing mechanism.

1. The Clustering Logic

The algorithm groups nodes into clusters of size $\ge k$. It picks a seed node (usually a high-degree node) and greedily adds the "closest" available nodes. "Closeness" is defined by a weighted sum:

• $\alpha imes$ NIL (Attribute Loss): How much "detail" we lose by grouping these people (e.g., turning "Age 25" and "Age 27" into "[25-27]").
• $\beta imes$ Dist (Structural Distance): How similar their connection patterns are.

2. Edge Generalization

Instead of adding or deleting edges randomly, SaNGreeA performs Edge Generalization.

• Intra-cluster: Edges within a cluster are summarized as a density value $(|cl|,|E_{cl}|)$.
• Inter-cluster: Edges between two clusters are collapsed into a single "super-edge" labeled with the total count of original edges.

Figure 1: Example of generalization hierarchies for categorical and numerical attributes.

Measuring "Information Loss"

The paper introduces a formal Structural Information Loss (SIL) metric. It views the anonymized graph as a probabilistic model. If a cluster has a certain number of edges, what is the probability that a researcher would "guess" an edge correctly? SIL quantifies the "error" introduced by this generalization.

Experimental Validation

The authors tested SaNGreeA against Zheleva's algorithm using the UCI Adult dataset mapped onto synthetic graphs (Random and R-MAT).

Figure 2: Performance on R-MAT Graphs (Power-law distribution). SaNGreeA (blue and green lines) consistently shows lower Structural Loss compared to the baseline.

Key Findings:

• Structural Fidelity: SaNGreeA is significantly better at preserving the "shape" of the network because its greedy selection considers neighborhoods.
• User Control: By adjusting $\alpha$ and $\beta$, data owners can prioritize either attribute accuracy or structural accuracy depending on the intended use case.

Critical Insight & Conclusion

SaNGreeA succeeds because it recognizes that topology is data. However, the greedy nature of the algorithm means it finds a local, not global, optimum. For massive networks (millions of nodes), the $O(n^2)$ complexity might pose a challenge, suggesting a need for more scalable heuristic variants.

Ultimately, this work moves us away from "naive" anonymization toward a structured framework for Data Utility vs. Privacy trade-offs in relational datasets.