Personalized Sensitive Label-Preserving: Bridging the Gap Between Privacy and Social Network Utility

TL;DR

Publishing social network data requires a delicate balance: protecting user privacy without rendering the data useless for researchers. This paper tackles the "excessive anonymity" problem in traditional k-degree models. By shifting the focus from "minimizing edge changes" to "preserving topological features" (like Average Path Length and Clustering Coefficient), the authors propose a node segmentation algorithm that maintains high data utility while effectively resisting structural re-identification attacks.

Problem & Motivation: The Distortion of Data

Traditional anonymization often treats graph structure as a secondary concern. When nodes are modified to meet k-degree anonymity (ensuring every node shares its degree with at least $k-1$ others), the resulting "noise" frequently destroys the graph's fundamental characteristics.

The authors identify two fatal flaws in prior work:

1. Indiscriminate Anonymization: Sensitive attributes are often anonymized to the same degree regardless of their actual sensitivity.
2. Structural Fragility: Using the "number of changes" as a utility metric ignores the fact that different edges have different impacts on the graph's global properties.

The research intuition here is clear: Not all nodes are created equal. Sensitive nodes and "bridging" nodes (key nodes that connect different communities) must be handled with surgical precision.

Methodology: A Utility-Centric Dual-Layer Model

The core of the methodology lies in redefining how we measure "loss" during anonymization. Instead of just counting added edges, the authors look at the Topological Similarity.

1. Dual-Layer Analysis

The model splits the problem into two spheres:

• Upper Virtual Network: Used to map users to attribute nodes. A sensitivity function $sensitivity(x)$ determines which attributes are "sensitive" based on a threshold $\rho$.
• Lower Distributed Network: Focuses on "Key Nodes" (KV) using Betweenness Centrality. These are the nodes whose modification would most severely damage the graph's connectivity.

2. The Multi-Objective Utility Function

The authors define a new utility loss function $D_{change}$: $D_{change}=a\cdot (TC)+b\cdot (IL)$ Where:

• TC (Topology Change): Measures the deviation in Average Path Length (APL) and Clustering Coefficient (CC).
• IL (Information Loss): Measures the overlap between sensitive nodes and key bridging nodes.

3. Node Segmentation Algorithm

Unlike standard edge-addition algorithms, the node segmentation approach focuses on grouping nodes based on their attribute similarity (calculated via Cosine Similarity of their attribute vectors) and their degree needs, mitigating the "excessive anonymity" effect.

Experiments & Results: Superior Structural Preservation

The authors tested their approach using a 13MB subgraph from the Last.fm dataset. The primary goal was to see how much the graph's "soul" (its topology) was altered as privacy requirements ($k$) grew stricter.

Key Findings:

• Average Path Length (APL): While traditional k-degree methods caused APL to fluctuate wildly, the proposed node segmentation algorithm kept APL remarkably stable, nearly mirroring the original graph's properties.
• Clustering Coefficient (CC): The proposed method maintained the "community" structure of the network much better than simple edge-addition methods, which tend to "flatten" or "over-connect" clusters.

Fig 2. The impact on Average Path Length (APL) - Lower distortion compared to traditional methods.

Fig 3. The impact on Clustering Coefficient (CC) - High structural fidelity.

Critical Insight & Conclusion

The significance of this work lies in its move toward Personalized Privacy. By recognizing that sensitive attribute preservation and topological utility can be mathematically unified, it provides a roadmap for more responsible data sharing.

Limitations: The sensitivity thresholds ($a,b,\rho$) currently rely on "experience" or manual setting. For this to be truly robust in production, automatable, data-driven methods for determining these parameters are required.

Future Outlook: As social graphs become increasingly multi-modal (containing text, images, and temporal links), the concept of "utility" must expand. This paper provides a solid foundation by proving that graph-theoretic metrics (APL, CC) are better anchors for anonymization than simple edit distances.