DeepMGGE: Bridging Social Silos via Multi-Granularity Graph Embeddings

TL;DR

Connecting the dots between different social media platforms (User Identity Linkage) is notoriously difficult due to data sparsity and privacy. DeepMGGE solves this by treating social structures through "multiple granularities." By zippering networks together and using a deep-learning-based heuristic to weight the importance of connections, it identifies "higher-order" friends that simple similarity checks miss.

Background: The Identity Linkage Puzzle

In the modern digital landscape, a single natural person often leaves fragments of their identity across Twitter, Foursquare, and LinkedIn. Identifying that @shun_fu on Twitter is the same person as Shun Fu on Foursquare—known as User Identity Linkage (UIL)—is the "holy grail" for cross-platform recommendations and network fusion.

The challenge? Privacy hides profile data, and usernames are rarely unique. We must rely on the structural topology of friend circles. However, if your friends aren't yet "linked" across platforms, 1st-order similarity fails.

The Core Insight: Multi-Granularity Stability

The authors argue that a user's position in a social network isn't just about who they follow (local), but their position relative to Supervisory Anchor Pairs (SAPs)—users we already know are the same across platforms.

They propose two granular layers of embedding:

1. Macro-Structure (Higher-Order): Using Random Walks to see beyond immediate neighbors.
2. Task-Specific (SAP-Oriented): Using Deep Learning to weight edges that lead toward known anchors.

Methodology: How DeepMGGE Works

1. The Zipper Operation

Instead of embedding two networks separately and trying to align their latent spaces (which is like trying to align two different star maps), DeepMGGE zippers them. It merges known SAP nodes into a single vertex, creating a bridge between Graph A and Graph B.

2. Deep Heuristic Weighting

This is the "Deep" in DeepMGGE. The model calculates a Hadamard product of node embeddings to represent an edge ($z_{ij}=z_i\circ z_j$). A Deep Neural Network (DNN) is then trained to predict if an edge is likely to be part of an identity-linked path.

Paths that lead toward anchors get higher weights. This forces the "Random Walker" to spend more time exploring regions of the graph that are rich in identity-relevant information.

Experimental Battleground

DeepMGGE was tested on real-world datasets: Twitter-Foursquare, DBLP (Co-author networks), and Facebook-Twitter.

SOTA Comparison

The model was compared against heavyweights like IONE and PALE. As shown in the table below, DeepMGGE's ability to capture non-linear structural properties gives it a distinct edge, especially when the number of known anchors is high.

The "Higher-Order" Advantage

A critical finding (Fig 6 in the paper) shows that as the ratio of "Hidden Higher-Order" users increases, the performance gap between DeepMGGE and traditional methods widens. This proves that the model's "deep sampling" strategy effectively finds users who are "friends of friends of anchors."

Critical Analysis & Takeaways

The brilliance of DeepMGGE lies in its Heuristic Edge Weighting. By moving from linear weighting to a DNN-based approach, the model handles the non-linear "noise" inherent in social connections.

Limitations:

• Computational Cost: The time complexity $O(\gamma |V|L\omega (d+d\log |V|))$ is manageable for academic datasets but may require further optimization for billion-node graphs like Facebook's global index.
• Anchor Dependency: The "zippering" method requires a reliable set of initial SAPs. In "Cold Start" scenarios where no anchors exist, the model would require an unsupervised initialization phase.

Future Outlook

DeepMGGE sets a precedent for Granular Computing in Graph Neural Networks. Future iterations could involve Temporal Granularity—how friend circles evolve over time—to further refine the accuracy of identity linkage in dynamic social environments.