EEUPL: Solving the Multi-Platform Identity Puzzle with Scalable Graph Clustering

TL;DR

Linking a single user across Twitter, Instagram, and Foursquare is a complex "Who's Who" problem. Traditional methods fail when users have multiple accounts on one site or only use a few of the platforms. EEUPL (Effective and Efficient User Profile Linkage) introduces a distributed graph-clustering framework that effectively handles account duplicates and scales to millions of users using Apache Spark, outperforming existing pairwise matching approaches.

Problem: The "Platform Uncertainty" Trap

Most current research treats User Profile Linkage (UPL) as a simple 1-to-1 matching game between two platforms. However, reality is messier:

1. Platform Uncertainty: A user might be on Twitter and Instagram but not Foursquare. Simple pairwise integration creates "incorrect linkage chains" that drift away from the true identity.
2. Intra-Platform Duplication: Reports show up to 11% of Facebook accounts are duplicates. If a model assumes "one person = one account per platform," it will inevitably fail.
3. The N-Platform Explosion: The computational cost grows quadratically ($n^2$) as you add more platforms and users.

EEUPL targets these gaps by moving beyond pairwise logic to a comprehensive Similarity Graph approach.

Methodology: Graph-Based Resolution

The EEUPL workflow is divided into two major phases: effectiveness (the "what") and efficiency (the "how").

1. Similarity Graph Generation

To avoid the $O(n^2)$ comparison nightmare, the authors use MinHashLSH (Locality Sensitive Hashing) to block candidate pairs. A pre-trained Logistic Regression classifier then evaluates these pairs to assign a "match probability." These probabilities become weights in a massive undirected graph where nodes are profiles and edges signify identity overlap.

2. Average-Link Clustering

This is the "secret sauce" of the paper. Instead of rigid constraints, EEUPL uses an average-link strategy to partition the graph:

• Splitting: It removes "weak edges" where weights aren't the local maximum.
• Merging: It uses cluster representatives and an inverted index to find and merge highly similar clusters that were originally separated.

Figure: The process of evolving initial components into refined, source-consistent user clusters.

Experiments: Real-World Performance

The researchers tested EEUPL on two massive datasets: GTI (Google+, Twitter, Instagram) and NCV (North Carolina Voters, 5 million profiles).

Quantifiable Superiority

In the GTI dataset (with induced 11% duplicates), EEUPL achieved:

• F1-Score: 0.7371, significantly higher than pairwise methods like OPL and CNL.
• Ablation Study: Removing the splitting/merging steps (EEUPL_N) caused a 13-15% drop in performance, proving that the clustering refinement is critical.

Figure: Comparison of Recall, Precision, and F1-score across different methodologies.

Scaling with Spark

Efficiency is not just about speed; it's about capacity. By deploying EEUPL on Apache Spark, the system processed millions of profiles efficiently. Increasing CPU cores from 15 to 120 resulted in a marked reduction in processing time, though the authors note that 100% linear speedup is hard to achieve due to certain non-parallelizable clustering steps.

Critical Analysis & Future Outlook

EEUPL succeeds because it treats identity as a clustering problem rather than a matching problem. Its ability to handle duplicate accounts within a single platform makes it far more robust for production environments than its predecessors.

Limitations: The model currently relies heavily on profile attributes (username, name, bio). If a user uses completely different personas (e.g., a "professional" LinkedIn and a "highly anonymous" Reddit), profile linkage alone will struggle.

Future Work: The next frontier is incorporating Social Graph Structure (who follows whom) and UGC (User Generated Content) patterns to link accounts even when the names and bios have zero overlap.

Takeaway: For tech leaders in Ad-Tech or Recommendation Systems, EEUPL provides a blueprint for building "Single View of Customer" (360-degree) profiles across fragmented social ecosystems.