NeighborMatch: Breaking Social Graph Anonymity Without Seeds

TL;DR

Social networks often share "anonymized" data for research, but is your privacy truly protected? This paper introduces NeighborMatch, a powerful deanonymization algorithm that doesn't need "seed mappings" (pre-identified users) to work. By combining a recursive structural similarity metric with available profile attributes (like age or gender), the authors demonstrate that even large-scale networks with millions of nodes—like Tencent Weibo—can be deanonymized with high precision.

The Problem: The Myth of the "Anonymous" Graph

Standard anonymization practices often involve "naive anonymization" (removing names) or structural perturbation (adding/deleting edges). However, the authors argue that these techniques fail against sophisticated Passive Attacks.

Prior state-of-the-art methods, such as those by Narayanan and Shmatikov, were "seed-dependent"—they required an attacker to already know the identities of a few key users to "spread" the deanonymization. If the seeds were wrong or unavailable, the attack collapsed. Moreover, simple structural signatures (like node degree) are easily destroyed by anonymization algorithms.

Methodology: Recursive Similarity & Bipartite Matching

The core innovation is a Node Similarity Measurement that follows an intuitive but mathematically rigorous logic: Two nodes are similar if their neighbors can be matched to each other with high similarity.

1. Structural Similarity (Simple Graphs)

For simple graphs, the similarity $S(i,j)$ is calculated iteratively. In each step, the algorithm builds a bipartite graph of the neighbors of node $i$ (from the auxiliary graph) and node $j$ (from the target graph). It then finds a Maximum Weighted Matching to determine how well the local structures "fit."

2. Generalizing to Rich Graphs

In the real world, nodes have attributes. The authors generalize their formula to: ${\mathcal{S}}^{(k+1)}(i,j)=\alpha \cdot extMatch(extNeighbors)+{\mathcal{S}}_X(i,j)$ This allows the algorithm to weight structural evidence against profile evidence ($S_X$), such as matching "Male, born in 1990" across two different datasets.

Experimental Insights: Who is Most at Risk?

The authors tested their approach on Microsoft Academic Search, LiveJournal, Enron, and Tencent Weibo (2.3 million nodes).

The Eigenvector Centrality Tie-in

One of the most striking theoretical contributions is proving that the "Self-Similarity" score of a node converges to its Eigenvector Centrality.

• The Big Discovery: "Important" nodes (those connected to other important nodes) are significantly easier to re-identify. They have unique structural "fingerprints" that are hard to hide.

Performance on Large Scale

On Tencent Weibo, the authors found that even when different types of anonymization (sparsification, perturbation) were applied, the integration of attributes and structure remained robust.

Figure: The precision and recall stay impressively high even when the overlap between the attacker's knowledge and the target graph is minimal.

Critical Analysis & Conclusion

Takeaway for Data Owners

The paper effectively kills the idea that structural randomization is a silver bullet. If an adversary has even noisy attribute data (like a crawled partial profile), they can use structural context to "anchor" their search.

Limitations

• Computational Cost: While the greedy heuristic helps, the $O(V^2)$ nature of comparing all pairs still requires pruning strategies for billion-node graphs.
• Attribute Sensitivity: If the descriptive information is completely shuffled or removed (not just perturbed), the attack relies solely on structure, which is less effective against high-strength k-anonymity algorithms.

In conclusion, NeighborMatch serves as a wake-up call for privacy research, proving that "anonymity" in a highly connected social world is much more fragile than commonly assumed.