Preserving Privacy in Weighted Social Networks: Moving Beyond Strict Isomorphism

TL;DR

Social networks are increasingly weighted (representing affinity, frequency, or trust), and these weights are a goldmine for attackers. This paper presents HIGA (Heuristic Indistinguishable Group Anonymization), a scheme that replaces the rigid requirement of graph isomorphism with a more flexible Probabilistic Indistinguishability. By combining random-walk structural analysis with weight generalization, it protects users while keeping the data useful for complex graph mining.

The Problem: The "Weighted 1*-Neighborhood" Attack

Most researchers previously assumed that removing names or masking degrees was enough. However, the authors identify a potent threat: the Weighted 1-Neighborhood Attack*.

In this scenario, an attacker knows:

1. A target's one-hop neighbors.
2. The connections between those neighbors (the 1-neighborhood graph).
3. The absolute degrees of those neighbors and the weights on the edges.

Even if a graph is k-neighbor anonymous (meaning $k$ people have the same neighbor structure), the specific weights (e.g., "Bob talks to Alice 50 times a day") can act as a unique fingerprint, allowing for nearly 100% accurate re-identification.

Methodology: The HIGA Framework

The core innovation lies in the HIGA scheme, which treats privacy as a grouping problem rather than a total obfuscation problem.

1. Structural Similarity via Random Walks

Instead of checking if two subgraphs are perfectly identical (isomorphic), which is computationally expensive and data-destructive, the authors use Random Walks (RW). By performing a random walk on neighbor structures, they generate a "topological signature." If the Hellinger distance between two signatures is below a threshold, the structures are deemed "similar enough."

2. Weight Generalization

To handle edge weights, HIGA doesn't just delete them. It generalizes them into ranges (e.g., a weight of 4 and 2 become the range [2, 4]). This ensures that an attacker cannot distinguish between nodes based on precise affinity values.

3. Probabilistic Indistinguishability

The final touch is a randomization step. By slightly perturbing the graph with a probability $p$ after anonymization, the authors ensure that even if an attacker finds a match, they can never be certain if that match was original or a result of the noise, keeping re-identification confidence below $1/k$.

Experimental Performance

The authors tested HIGA on major datasets: Facebook, CA-CondMat, Enron, and Douban.

• Utility Preservation: Unlike methods that scrub weights entirely, HIGA maintains the "small-world" characteristics and power-law distributions of the original networks.
• Efficiency: While large datasets like Douban (154k nodes) take significant time, the paper proposes a parallel graph partition strategy to scale the process.

Fig: As the group size $k$ increases, the number of modified edges rises, but remains lower than traditional isomorphism-based methods.

Critical Insight & Conclusion

The true value of this work is the shift from deterministic privacy (it must look exactly like $k$ others) to probabilistic privacy (it probably looks like others, and there's enough noise to mask the truth).

Takeaway: If you are publishing graph data, stop trying to make every neighborhood identical. Use structural signatures and weight ranges. It provides the same protection against real-world attackers while keeping the "social" signal in your social network data alive.

Limitations: The computational cost for massive graphs (millions of edges) remains high, and the current model handles static graphs; dynamic, evolving social networks would require a more temporal-aware approach.