Hypergraph Anonymization: Protecting Identity in GeoSocial Networks

TL;DR

As GeoSocial Networks (GSNs) like Foursquare or Facebook Check-ins grow, the risk of identity disclosure increases. This paper proposes a Hypergraph-based GSN (HGSN) model and two new anonymity constraints—$(k,\delta )-m$ and $(k,\delta )-m,l$—to protect users from adversaries who possess partial knowledge of their locations and social circles. By treating location sets as hyperedges, the method balances data utility with robust privacy protection.

Problem & Motivation: The "Check-in" Trap

In a standard social network, edge structures might be enough to identify you. In a GSN, your location history is a fingerprint.

• The Issue with Prior Work: Most existing models assume an attacker knows everywhere you have been. This "strong adversary" assumption leads to "over-anonymization," where the data becomes practically useless for researchers or businesses.
• The Hybrid Attack: Attackers rarely know everything, but they might know your top 2-3 favorite coffee shops (Location Attack, $Pl$) or where your best friends hang out (Structure-Location Hybrid Attack, $Ph$). This paper addresses these realistic, "bounded knowledge" scenarios.

Methodology: The Hypergraph Approach

The core innovation is representing the GSN as a Hypergraph. In this model:

1. Vertices: Represent users.
2. Hyperedges: Represent sets of top locations. A hyperedge connects a set of users who share a specific set of location signatures.

Fig 1: A visual representation of how social links (solid lines) and location sets (colored hyperedge boundaries) overlap in a GSN.

The Two-Step Solution

The authors propose a decoupled algorithm to optimize utility:

• Step 1: $(k,\delta )-m$ Anonymity: Focuses on location generalization. It merges hyperedges (location sets) until every set is shared by at least $k$ users.
• Step 2: $(k,\delta )-m,l$ Anonymity: Focuses on social structure. By selectively deleting "sensitive" social edges, the algorithm ensures that even if an attacker knows your friends' locations, you cannot be uniquely identified through those connections.

Experiments & Results

The researchers tested their approach on the Brightkite (BK) and Gowalla (GW) datasets.

Identity Disclosure Risk

The study confirmed a frightening reality: with knowledge of just two top locations, an attacker can uniquely identify nearly 100% of active users in these datasets.

Fig 2: Percentage of users identified (victims) increases sharply as the attacker's knowledge (m locations) grows.

Utility vs. Privacy

The results showed that:

• Location Bias: Generalizing locations to satisfy $k=10$ or $k=20$ resulted in manageable information loss, specifically when the "original location combination" constraint was enforced.
• Social Link Utility: Interestingly, increasing $k$ (anonymity level) in the location step actually reduced the number of social edges that needed to be deleted in the second step. This suggests that stronger location privacy can "subsidize" structural privacy.

Critical Analysis & Conclusion

Takeaway

The shift toward a Hypergraph model is a significant academic contribution. It allows for a more granular mathematical treatment of "partial knowledge" attacks, which are more common in the real world than total knowledge attacks.

Limitations & Future Work

While the deletion-based approach for social links is effective, it only considers edge deletion. In real-world applications, edge addition (adding fake "noise" friends) might offer better utility for certain graph properties. Additionally, the current model treats locations as coordinate points. Future research should incorporate Semantic Privacy, recognizing that visiting a "Hospital" carries different privacy implications than visiting a "Park."

Ultimately, this work provides a scalable foundation for publishing GSN data that remains useful for location-based service analysis while respecting user anonymity.