Anonymising social graphs in the presence of active attackers

Sjouke Mauw, Yunior Ramírez-Cruz, Rolando Trujillo-RasuaTrans. Data Priv 2018 · OpenReview

Abstract

Social network data releases are increasingly threatened by active attackers who plant fake profiles, known as Sybils, to de-anonymize users through structural fingerprints. This paper introduces a robust framework for achieving $(k, \ell)$-anonymity in social graphs. By strategically adding a small number of edges, the proposed methods obfuscate distance-based identities, effectively reducing an attacker's success rate to zero while preserving the graph's overall structure and utility.

Introduction

While passive attacks on social network privacy—where adversaries use public metadata to identify users in released datasets—are well-studied, active attacks pose a more severe threat. In an active attack, an adversary inserts "Sybil nodes" (fake accounts) into the network before data publication. These nodes are linked to targets in specific patterns, creating unique structural "fingerprints." Upon the release of "anonymized" data, the attacker identifies these Sybils and their fingerprints to re-identify victims with high certainty.

Most real-world social graphs currently exhibit $(1, 1)$-anonymity, the weakest possible state, where a single Sybil node can uniquely identify a user. This research addresses the challenge of transforming these vulnerable graphs into $(k, \ell)$-anonymous structures, ensuring that even an attacker with $\ell$ Sybil nodes cannot identify a victim with a probability exceeding $1/k$.

Methodology

The authors propose a family of perturbation methods based on strategic edge additions. The core objective is to identify "1-resolvable" vertices—nodes uniquely identifiable by their distance to a specific set of other nodes—and obfuscate them.

A vulnerable local graph structure where node $v_1$ may be uniquely identifiable by its distance to neighbors.

The framework utilizes a metric representation to model a node's identity based on its distance to a set of reference nodes. By adding "anonymising edges," the uniqueness of these distance profiles is broken.

The same graph after anonymising edges are added to create cycles, thereby obfuscating the distance-based fingerprint of $v_1$.

Three specific strategies for edge selection were evaluated:

  • Odd-Order Cycles (OOCV): Forces the creation of odd-order cycles.
  • Smallest-Order Cycles (SOCV): Adds edges between nodes that are as close as possible.
  • Largest-Order Cycles (LOCV): Adds edges between nodes that are as distant as possible.

The authors provide formal proofs of convergence and tight upper bounds on the number of edges required to reach target anonymity levels.

Experimental Evaluation

The approach was tested on both synthetic and real-world datasets:

  1. Facebook Ego-networks: 4,039 nodes representing friendship circles.
  2. Panzarasa Graph: 1,893 nodes from a student messaging community.
  3. URV Email Graph: 1,133 nodes from an academic email network.
  4. Synthetic Collection: 250,000 randomly generated graphs to test performance across varying network densities.

Results and Discussion

The experimental results demonstrate that active attacks can be neutralized with minimal impact on graph utility.

Attack Neutralization

In all real-world datasets, the success probability of standard walk-based active attacks dropped to 0.0 after applying the anonymization variants. This confirms the effectiveness of $(k, \ell)$-anonymity in practice.

Minimal Perturbation

Despite high theoretical upper bounds, real-world graphs required very few changes. For the Facebook graph, only 73-74 edges (a 0.08% increase) were necessary. The URV graph, while requiring more changes, still only saw a 5.6% increase in edge count.

Utility Preservation

The method's focus on edge addition preserves global properties like community structure and "small-world" characteristics. Evaluations using community detection algorithms (BigClam and CoDA) showed remarkably low utility loss, averaging between 0.02 and 0.08.

Conclusion

This work demonstrates that strategic edge addition is a highly effective and efficient means of protecting social graphs against active Sybil attacks. Future research may explore hybrid approaches involving edge deletion for extremely dense graphs and methods to prevent the initial retrieval of Sybil nodes from published datasets.

Summary updated

BibTeX
@article{mauw2018anonymising,
  author = {Sjouke Mauw and Yunior Ramírez-Cruz and Rolando Trujillo-Rasua},
  title = {{Anonymising social graphs in the presence of active attackers}},
  journal = {Trans. Data Priv.},
  year = {2018},
  url = {https://openreview.net/forum?id=CtQDlzK8vH},
}
Figure