Breaking the Seed Dependency: Structural F-Score for Seedless Social Network De-anonymization

TL;DR

Social network de-anonymization usually assumes that every person in "Network A" has an account in "Network B." In reality, users overlap only partially. This paper introduces the Structural F-score, a topology-based metric that allows for highly accurate de-anonymization without needing any "seed nodes" (pre-identified users). By maximizing link precision and recall, the proposed algorithm can prune incorrect matches and achieve SOTA performance on networks with tens of thousands of users.

The Reality of Partial Overlap

Most academic de-anonymization attacks treat the problem as a Full Matching problem (a Quadratic Assignment Problem). However, if you compare a sanitized Wikipedia linkage graph with an anonymized Twitter graph, many users will exist in only one of the two.

Prior work failure points:

1. The Mismatch Trap: If you force a full matching on two networks that only share 50% of their users, the algorithm is forced to create 50% wrong matches, which pollutes the structural integrity of the alignment.
2. The Seed Dilemma: High-performance algorithms like Percolation Graph Matching (PGM) require "seeds"—a handful of known user pairs. Finding these seeds often requires manual effort or side-channel information.

The authors ask: Can we distinguish between a correct match and a forced "wrong" match using only the links between nodes?

Methodology: The Structural F-score

To solve this, the authors borrow a concept from machine learning—the F-score—and redefine it using Link Accordance.

1. Link Precision & Recall

Instead of checking if nodes are correct (which we don't know), we check if the links between matched nodes exist in both networks.

• Link Precision (${\hat{f}}_p$): The ratio of links that exist in both networks among the matched pairs to the total links in their union.
• Link Recall (${\hat{f}}_r$): The ratio of links in accordance divided by the links that would exist in a broader full matching.

The Structural F-score is the harmonic mean of these two:

2. The Two-Step Heuristic

The authors prove a powerful theorem: The perfect matching is contained within the optimal full matching. This leads to the Direct De-anonymization (DDA) algorithm:

1. Find the Best Full Match: Match everyone, even if it's wrong, using a standard algorithm (like Collective De-anonymization).
2. Prune the "Hinders": Iteratively remove matched pairs. If removing a pair increases the overall Structural F-score, that pair was likely a "forced" wrong match.

Visualizing the difference between a partial match (a) and its forced full matching counterpart (b).

Scaling to Large Networks: PDA Algorithm

For networks with $>2,000$ nodes, computing full distances is too expensive ($O(n^3)$). The authors propose Percolation De-anonymization (PDA):

• Seed Discovery: Automatically identify high-degree nodes. Because high-degree nodes have more structural information, they are easier to match correctly via the F-score.
• Percolation: Once these "high-confidence" seeds are found, the algorithm "spreads" the matching to their neighbors, similar to how a virus spreads through a network.

Experimental Mastery

The authors tested their approach on Erdos-Renyi (ER), Scale-Free (SF), and real-world datasets like Wikipedia, Slashdot, and Douban.

Key Findings:

• Accuracy Boost: In Wikipedia networks, the DDA algorithm significantly improved nodal precision compared to full-matching baselines.
• Seedless Power: On 10,000-node Scale-Free networks, the PDA algorithm achieved a nodal F-score almost identical to the seeded PGM algorithm, essentially proving that structural self-evidence can replace manual seeds.

Performance Comparison: PDA (ours) vs PGM (seeded). In Scale-Free networks (right), our seedless approach converges to the seeded baseline.

Critical Analysis & Insight

The brilliance of this paper lies in the mathematical intuition that the structural F-score is strictly monotonic with respect to the number of correct matches. While the authors admit some correlations between mismatched links are ignored for simplicity, the bounds remain tight enough for practical use.

Limitations:

• The computational complexity of the initial full match in DDA is still $O(n^3)$, making the "Seed Discovery" phase the bottleneck for extremely massive graphs.
• Very sparse graphs (low mean degree) might not provide enough "link accordance" to distinguish real matches from noise.

Conclusion

This research effectively bridges the gap between theoretical graph alignment and messy, real-world social data. By proving that you can "prune" your way to a perfect match using the Structural F-score, the authors have removed one of the biggest hurdles in privacy research: the reliance on pre-identified victims (seeds).