Class-based graph anonymization for social network data

Graham Cormode, Divesh Srivastava, Smriti Bhagat, Balachander KrishnamurthyPVLDB 2009 · DOI · OpenReview

TL;DR

This paper introduces novel techniques for anonymizing rich social network data, moving beyond simple graph structures to handle complex interactions and user attributes. Their "label list" and "partitioning" approaches aim to protect user privacy while enabling accurate querying of anonymized data, demonstrating a practical trade-off between privacy and utility.

What Problem Does This Paper Address?

Online Social Networks (OSNs) like Facebook and MySpace generate vast amounts of data about user interactions and personal details. Sharing this data for research is crucial, but it's also highly sensitive. Traditional anonymization methods, often designed for simple tabular data or basic graphs, struggle to preserve the richness of OSN data. Simply removing non-graph information or altering edges can lead to significant loss of analytical utility. This paper tackles the challenge of anonymizing "rich interaction graphs" – those that capture multiple types of interactions (e.g., messages, friendships, group memberships) and associated user attributes – in a way that balances privacy guarantees with the ability to perform meaningful analysis.

Methods

The authors propose two main anonymization approaches:

  • Label List Approach: This method replaces each node's true identifier with a "label list" containing multiple possible identifiers. The core idea is to create ambiguity about an entity's true identity while still allowing for queries. They introduce a "Class Safety property" to ensure that nodes within a class don't have too many overlapping interactions, preventing direct inference. Two specific types of label lists are detailed:
  • Uniform List: Lists are generated based on a "pattern" and a class size parameter (k, m). This approach aims for structured anonymization to foil inference attacks.
  • Prefix Pattern: A special case of uniform lists where the pattern is a simple sequence.
  • Full Pattern: Another special case where the list contains all possible labels in the class.
  • Partitioning Approach: This method groups nodes into larger "classes" and only reveals the number of interactions between these classes, rather than individual node-interaction mappings. This offers stronger privacy guarantees, especially against attackers with more background knowledge, but at the cost of reduced utility. This approach also relies on the "Class Safety property."

Datasets

The authors evaluate their methods using two real-world datasets:

  • Xanga Social Network: A large dataset with approximately 780,000 nodes and 3 million edges, representing users, blogs, subscriptions, and friendship relations. User profile information like age, gender, and location is available.
  • Speed Dating Study: A smaller dataset with 530 participants and 4150 "dates." It includes demographic information (age, race, field of study) and hobby interest levels, with interactions representing "dates" and whether they resulted in a "match."

Key Insights and Ideas

  • Richness of OSN Data: The paper emphasizes that OSN data is far richer than simple graphs, involving multi-participant interactions and diverse user attributes, necessitating more sophisticated anonymization.
  • Privacy-Utility Trade-off is Inherent: There's a fundamental tension between protecting privacy (by obscuring information) and maintaining utility (by allowing accurate queries). The proposed methods explore different points on this spectrum.
  • Class Safety is Crucial: The "Class Safety property" is a novel and critical component, preventing direct inference of interactions by ensuring that nodes within a class don't have too many shared connections. This is key to both anonymization methods.
  • Prioritizing Attributes for Utility: The order in which attributes are considered when forming classes significantly impacts query accuracy. Sorting nodes based on attributes relevant to anticipated queries can dramatically improve utility.
  • Label Lists vs. Partitioning: Label lists offer better utility for many queries but are less robust to attackers with extensive background knowledge. Partitioning provides stronger privacy but sacrifices utility, especially for queries involving node degrees.

Key Results

  • Improved Utility over Sanitization: Both label list and partitioning approaches significantly outperform simple data sanitization (where all links are randomized) in terms of query accuracy. For example, errors on sanitized data were at least 3 times higher than on anonymized data.
  • Label List Accuracy: For the Xanga dataset, median relative errors for label list anonymization (full and prefix) were in the single digits for a workload of 100 queries.
  • Partitioning Performance: The partitioning approach showed comparable utility to label lists for queries based solely on node attributes but had much lower accuracy for queries involving node degrees.
  • Impact of Parameters: For label lists, smaller class sizes (lower 'm') generally led to higher utility. For full lists, increasing 'k' (which also implies increasing 'm' in the full pattern case) led to higher errors, reflecting the privacy-utility trade-off.
  • Prioritization Benefits: Sorting nodes based on attributes relevant to queries (e.g., Age, Gender, Location, Degree) led to substantial improvements in query accuracy, sometimes reducing errors to near zero.

Limitations and Future Work

  • Defining Privacy Goals: The authors acknowledge that precisely quantifying privacy goals and translating them into precise anonymization parameters remains a challenge.
  • Unknown Future Queries: The trade-off between privacy and utility is difficult to optimize without knowing the exact nature of future queries.
  • Temporal Data: The current work focuses on static snapshots of social networks. Extending the methods to handle dynamic, temporal data (how networks evolve over time) is a significant area for future work.
  • Interaction Classes: While entities are grouped into classes, interactions themselves are not. Masking interaction types could offer further privacy but might also reduce utility.
  • Directed Graphs: The current work primarily assumes undirected graphs, though extensions to directed graphs are mentioned as feasible.
  • Information Theoretic Approaches: The authors suggest that information theoretic methods could be beneficial for modeling the privacy-utility trade-off.

Summary updated

BibTeX
@article{cormode2009class,
  author = {Graham Cormode and Divesh Srivastava and Smriti Bhagat and Balachander Krishnamurthy},
  title = {{Class-based graph anonymization for social network data}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687714},
}
Figure