Signed Graph Anonymization: Strengthening Privacy Against Relational Attacks

TL;DR

Current social network anonymization often ignores the nature of relationships (friend vs. foe). This paper reveals that signed edge attributes provide a powerful "fingerprint" for de-anonymization. To counter this, the authors propose a Signed k-Anonymity scheme that modifies graph edges to make key users structurally indistinguishable from at least $k-1$ others, preserving both privacy and graph utility.

Background: Why Simple Anonymization Fails

Removing names (labels) from a social network dataset is insufficient. Attackers can use the graph structure—specifically the "neighborhood" of a target—to re-identify individuals.

While previous research focused on 1-neighborhood (who you are connected to) and 1-neighborhood* (neighbor degrees), they treated all links as identical. However, real-world networks are Signed Graphs. Knowing that "Alice is friends with Bob but blocked by Charlie" provides significantly more identifying information than just knowing "Alice has two connections."

The Problem: The Signed 1*-Neighborhood Attack

The authors identify a new threat: the Signed 1-Neighborhood Attack*.

• Prior Work Paradox: A graph protected against unsigned attacks (Fig 2d in the paper) can still be compromised if the attacker knows the signs of the edges (Fig 2e).
• The Insight: To truly protect a user, you must ensure that there are $k$ users who not only have similar connectivity but also similar distributions of positive and negative relationships.

Methodology: Achieving Indistinguishability

The core of the paper is a mathematical framework for measuring similarity between nodes in a signed environment.

1. The Similarity Metric

The authors prove (Theorems 1-3) that the most efficient way to measure distance between two nodes is by comparing their sorted positive and negative degree sequences using $p$-norm distances.

$V_{candi}=\{v|\arg \min \sum (|x^{+}-y_v^{+}{|}^p+|x^{-}-y_v^{-}{|}^p)\}$

2. The Anonymization Algorithm

The algorithm performs a "structural surgery" on the graph:

• Filter Mechanism: Rapidly identifies the $k-1$ most similar "candidate" nodes for a target.
• Edge Modification: Adds or removes positive/negative edges until the candidate nodes share the exact same signed neighbor degree sequence as the target.

Figure 1: Comparison of different neighborhood attack models, culminating in the Signed 1-neighborhood.*

Experimental Validation

The researchers tested their approach on the Facebook and Wiki datasets from SNAP.

Performance & Efficiency

As $k$ (the level of privacy) increases, the number of modified edges naturally rises. However, the algorithm is optimized to minimize these changes to keep the data "clean" for researchers.

Data Utility

A critical question in privacy research is: Is the data still useful after modification?

• Degree Distribution: The "shape" of the network's connectivity remains largely unchanged (Fig 5).
• Closeness Centrality: The relative importance and "centrality" of nodes are preserved, as verified by K-S quantitative tests.

Figure 2: Distribution of closeness centrality showing the high overlap between the original and anonymized graphs, indicating high utility.

Critical Insight & Conclusion

The significance of this work lies in its alignment with the complexity of modern social interactions. By proving that Sorted Degree Sequences are the optimal basis for similarity, the authors provide a scalable way to protect big graph data.

Future Outlook: As social networks evolve to include more complex edge attributes (e.g., weights, timestamps, and multiple relationship types), the "Signed k-Anonymity" framework provides a foundational methodology for multidimensional privacy protection.