Bayesian Vulnerability: De-anonymizing Social Graphs via Probabilistic Inference

TL;DR

Social networks often "anonymize" data by perturbing edges with noise before publication. This paper proves such measures are fragile. The authors propose a Bayesian Privacy Analysis Model that leverages simple background knowledge (node degrees) to re-identify individuals in a published graph with high probability, outperforming existing structural attacks.

Background: The Illusion of Anonymity

When platforms like Facebook or WeChat share data for research, they don't just delete names; they modify the graph structure—adding or removing edges using techniques like Gaussian noise. The assumption is that structural perturbation provides a safety net. However, this paper views "anonymization" not as a shield, but as a probabilistic channel that can be reversed using Bayesian logic.

The Core Concept: From Prior to Posterior

The researchers identify a critical flaw: if an attacker knows the degree of a target node (Prior Knowledge), they can calculate the likelihood of that node existing in the noisy published graph (Posterior Probability).

1. The General Privacy Analysis Framework

The paper structures the attack into a three-stage pipeline:

• Original Graph ($G$): The raw, sensitive social ties.
• Published Graph ($G^{\prime }$): The version "protected" by Gaussian noise.
• Analysis Graph: The reconstructed result where the attacker maps anonymous nodes back to identities.

2. The Bayesian Methodology

The mathematical heart of the paper is the application of Bayes' Rule: $\bar{P}(v|G^{\prime })=\frac{P(G^{\prime }|v)P(v)}{P(G^{\prime })}$

• $P(v)$: The prior probability of a node based on its degree.
• $P(G^{\prime }|v)$: The likelihood, which models how the environment around node $v$ was perturbed by Gaussian noise.
• The Intuition: If the observed noisy structure $G^{\prime }$ is highly consistent with the expected noise transformation of node $v$, the probability of identification spikes.

Experimental Evidence

The authors tested their model against the Degree Attack, a common baseline that simply looks for nodes with matching link counts.

Key Finding 1: Success in Identifiability

In testing with the Karate Club (34 nodes) and Dolphin Social Network (62 nodes), the Bayesian method successfully identified target nodes. A crucial discovery was that as the standard deviation ($\sigma$) of the added noise increases, the identification probability changes, but the Bayesian model consistently outperforms simple degree counting.

Key Finding 2: Scalability vs. Accuracy

As the network size increases, the identification probability naturally decreases because the "anonymity set" becomes larger. However, the Bayesian method maintains a significant lead over traditional attacks, proving that probabilistic modeling is a much more potent threat than simple structural matching.

Critical Insights & Future Work

The value of this paper lies in its offensive security perspective. By providing a rigorous way to "break" graph anonymity, it provides a benchmark for what a good privacy-preserving method must resist.

• Limitation: The current model assumes independent and identically distributed (i.i.d.) noise across edges, which might not hold in more complex, correlated graph perturbation strategies.
• Industry Impact: Data providers must move beyond simple noise injection. If a Bayesian attacker can re-identify a node in a 200-node graph with elevated probability, large-scale graph data remains at risk unless more sophisticated techniques like Differential Privacy or $k$-anonymity are integrated.

Final Takeaway: In the era of big data, your "structural signature" is as unique as a fingerprint. Noise doesn't erase it; it just blurs it—and as this paper shows, Bayesian math is excellent at de-blurring.