GASNA: Optimizing Privacy and Utility in Social Network Anonymization

TL;DR

GASNA (Greedy Algorithm for Social Network Anonymization) is a high-performance framework that protects social network data against identity and attribute disclosure. By combining k-anonymity (structural protection) with l-diversity (sensitive attribute protection) and utilizing greedy edge-addition strategies, it achieves SOTA results in preserving graph utility with a fraction of the computational overhead of previous methods.

Background: The Structural Privacy Trap

In the era of big data, releasing social network datasets for research is a double-edged sword. While relational data can be anonymized by masking names, social networks contain structural quasi-identifiers. An adversary knowing that "John has 11 friends" can easily locate him in a graph if only one node has a degree of 11.

Existing works attempted to solve this, but they often relied on expensive graph isomorphism tests or added so many "noise" edges that the resulting graph became useless for analysis.

Methodology: The GASNA Three-Phase Pipeline

1. Efficient Similarity Measuring

Instead of full isomorphism checks, GASNA calculates a Similarity Cost. The similarity between two nodes is defined as the number of edges required to make their d-neighborhoods isomorphic. This greedy metric allows for rapid clustering of "structurally similar" individuals.

2. Strategic Clustering & l-Diversity

The algorithm groups nodes into clusters of size at least k. Crucially, it enforces l-diversity during this step: a node is only added to a cluster if it doesn't cause the sensitive attribute (e.g., "Disease" or "Birthplace") to become too homogenous.

3. Optimized Anonymization (AFN vs. AEN)

The paper introduces two sophisticated edge addition techniques:

• AFN (Adding Fake Nodes): Creates "ghost" nodes to satisfy degree requirements of existing nodes.
• AEN (Adding Existing Nodes): Connects two existing nodes that both need additional degrees. AEN is the superior method, as it satisfies two requirements with a single edge, reducing graph distortion.

Figure: The cost-based similarity logic for d=1 and d=2 neighborhoods.

Performance Benchmarks

GASNA was tested against the R-MAT synthetic model and real-world co-authorship networks.

• Efficiency: The algorithm processed 15,000 nodes in 5.34 seconds, making it viable for large-scale social graphs.
• Data Utility: In a 15,000-node test, GASNA (AEN) added only 569 edges, whereas previous SOTA methods (Zhou & Pei) required up to 1700 edges. By adding 66% fewer edges, GASNA preserves the original graph's properties (like clustering coefficients and path lengths) much more effectively.

Figure: Comparison of AEN vs AFN performance on real-world scientific datasets.

Critical Insight: Partial Anonymity

One of the most innovative contributions is the concept of Partial Anonymity for complex neighborhoods (d > 1). Instead of forcing total symmetry across all neighbors—which causes an "edge explosion"—GASNA ensures that each node's neighborhood structure is a subset of a "lead" node's structure. This provides a pragmatic balance between rigorous privacy and the preservation of graph topology.

Conclusion

GASNA proves that privacy doesn't have to come at the cost of extreme data distortion or prohibitive compute time. By shifting from exhaustive graph matching to a greedy, cost-based edge addition strategy, it provides a scalable blueprint for publishing privacy-safe social network data.

Future Directions: The authors suggest exploring multi-sensitive attribute protection and quantifying the exact "Information Loss" in spectral graph properties.