Linking the Anonymous: How Spatio-Temporal Traces De-mask Multi-Service Identities

TL;DR

In our hyper-connected world, you likely have different "egos" across QQ, Weibo, Taobao, and Twitter. Researchers from Tsinghua and UIUC have developed a system that can link these disparate IDs back to you by simply looking at your physical movement patterns. By treating identity linkage as a set-wise partition problem rather than traditional pair-wise matching, their system achieves a massive 0.20 AUC improvement over previous SOTA methods.

The "Multiple Ego" Problem in Large-Scale Data

Identity Linkage (IL) is the holy grail for service providers—it allows them to fuse fragmented data into a 360-degree user profile. However, two major hurdles have historically made this "dirty" work:

1. Service Multiplicity: Most algorithms are designed to match Service A to Service B. What happens when you have A, B, C, and D? The order in which you match them (A→B then B→C) drastically changes the result.
2. ID Multiplicity: Users often have multiple accounts on the same platform (e.g., two Twitter handles). Pair-wise matchers fail to see these as a single entity set.

Methodology: The Contact Graph and Bayesian Optimality

The authors move away from service-specific attributes (like usernames) and focus on a more universal signal: Physical Mobility. The intuition is simple: if two IDs are frequently "co-located" at the same cell tower or WiFi AP, they likely belong to the same human.

1. The Contact Graph

Instead of a bipartite graph, the authors construct one massive Contact Graph. Nodes are IDs, and edges represent a co-location event in the physical world. This allows the system to identify "candidate sets" of IDs that form dense subgraphs.

Figure 1: The workflow of the multi-service ID linking system, from trajectory processing to Bayesian ranking.

2. Bayesian Inference & Partitioning

The core of the paper is the Set-wise Identity Matching Problem (SIMP). Using Bayesian inference, the authors calculate the posterior probability of a specific "partition"—a grouping of IDs—given the observed mobility records. They provide a mathematical proof that ranking candidate sets based on this probability is the optimal strategy to minimize matching errors.

They offer two behavior models:

• Multinomial Model: Treats locations as independent visits.
• Markov Model: Captures the sequence of movements (transition patterns), which is far more descriptive but prone to noise in sparse data.

Experiments: Performance at Scale

The researchers tested their system on a colossal ISP dataset involving 815,000 IDs across four services (IM, OSN, EC, and OR).

Key Result 1: Outperforming the SOTA

The system consistently beat baselines like WYCI and POIS. In complex "one-to-many" relations (where a user has multiple IDs in one service), the AUC gain reached 0.20.

Figure 2: Precision-Recall curves showing the clear lead of MN-G (Multinomial-Global) and MK-C (Markov-Collapsed) over existing baselines.

Key Result 2: Robustness to "Matching Order"

One of the most striking findings is that traditional pair-wise methods are sensitive to the sequence of analysis. If you match Service A to B first, you might get a different result than if you started with C. The proposed SIMP algorithm is largely immune to this, showing a variance of only 0.06 in AUC compared to the 0.20 drop seen in baselines.

Critical Insights & Future Outlook

The paper proves that "where you are is who you are." Even with coarse-grained location data (district-level), the uniqueness of human mobility is enough to stitch together fragmented digital identities.

The Catch: The Markov model, while theoretically superior because it captures transitions, is highly sensitive to data sparsity. In the Twitter-Foursquare dataset (which is much sparser than the ISP data), the simpler Multinomial model with "Collapsed Parameters" actually performed better. This suggests that in the real world, the "cleanliness" of your model often beats the "complexity" of your math.

Takeaway for Practitioners: If you are building a recommendation engine or a fraud detection system across multiple apps, stop thinking about pair-wise ID matching. Focus on the underlying physical behavior and use set-wise partitioning to handle the reality of multi-account users.