BASS: Solving the Identity Alignment Puzzle Across Heterogeneous Social Networks

TL;DR

The digital self is fragmented across platforms—Facebook for friends, LinkedIn for work, and Twitter for news. BASS (Bootstrapping Approach for Aligning Social Networks) is an unsupervised framework that glues these fragments back together. By using an iterative "bootstrapping" process that learns from usernames, social ties, and multi-modal behavior, it identifies identical users across networks with over 80% F1-score—without requiring the heavy manual labeling of previous SOTA methods.

The "Identity Linkage" Problem: Beyond Just Names

Why is it so hard to know if User_A on Weibo is the same as User_B on Douban?

1. Sparsity: People don't always use the same handle (alias-conflation).
2. Heterogeneity: One site might capture movies you watch, while another captures your political rants.
3. Privacy: Profile details like emails and locations are increasingly hidden.
4. Scale: With billions of users, comparing every pair ($O(N^2)$) is computationally impossible.

Previous works were either rule-based (too simple) or supervised (too expensive). BASS shifts the paradigm by treating the alignment itself as a "hidden" state that evolves through learning.

Methodology: The Virtuous Cycle of Bootstrapped Learning

The core innovation of BASS is its Expectation-Maximization (EM) workflow. Instead of needing a human to label thousands of user pairs, it starts with an "imperfect" set of anchors (usually users with identical names) and expands from there.

1. The Multi-Modal Consistency Model

BASS doesn't just look at who you follow; it looks at why you do what you do.

• Username: Uses edit distance and naming patterns.
• Social Ties: Leverages social tie consistency (if my friends are aligned, I am likely aligned).
• UGC (Preference): This is the secret sauce. BASS uses a Multi-modal LDA to map heterogeneous actions (like Weibo "tweets" and Douban "movie ratings") into a shared "Universal Topic Space." This allows the model to see that a user who posts about "dogs" on one site likely enjoys "family comedies" on another.

Figure: The BASS Bootstrapping Workflow showing the iterative refinement between Consistency and Classification units.

2. Scalable Alignment: The Stable-Marriage Solution

Standard bipartite matching (KM algorithm) is $O(N^3)$, which breaks at the scale of real OSNs. BASS introduces:

• Boundary Subsampling: Instead of training on all $N^2$ pairs, it focuses on "hard negatives"—account pairs that look similar but aren't the same.
• Stable Marriage Algorithm: By treating alignment as a preference matching problem and exploiting the symmetry of scores, BASS reduces the complexity to a manageable $O(N{D}^2)$, where $D$ is the average degree of the network.

Experiments: Performance at Scale

The authors tested BASS on two massive real-world datasets: Facebook-Twitter (328k pairs) and Weibo-Douban (141k pairs).

SOTA Comparisons

BASS outperformed traditional methods like MNA and MAH by a wide margin. For example, on the Weibo-Douban set, including UGC (User Generated Content) modeling boosted the F1-score from 0.748 to 0.778.

Figure: The "Snowball Effect" — as iterations increase, both precision and recall improve, demonstrating the power of bootstrapping.

Key Breakthroughs:

• Unsupervised Power: BASS-U (the unsupervised version) performed better than existing supervised models even when those models were given 50% of the ground truth for training.
• Robustness to "Lone Wolves": Unlike previous models that crashed if users appeared only on one network, BASS maintained high precision when the ratio of common users dropped.

Critical Insight & Takeaways

BASS proves that the graph structure + behavioral semantics provides a much stronger signal than mere profiles. The ability to discover preferences (via Multi-modal LDA) allows the system to bridge totally different platforms (e.g., a movie site and a microblog).

Future Outlook: While BASS is robust, the next frontier is aligning "Silent Users" who consume content but don't post, and expanding this to Multi-network alignment (aligning across 5+ platforms simultaneously). For users, this highlights a privacy reality: your public activities are often enough to link your "anonymous" accounts across the web.