Abstract: Predicting pairs of anchor users plays an important role in the cross-network analysis. Due to the expensive costs of labeling anchor users for training prediction models, we consider in this paper the problem of minimizing the number of user pairs across multiple networks for labeling as to improve the accuracy of the prediction. To this end, we present a deep active learning model for anchor user prediction (DALAUP for short). However, active learning for anchor user sampling meets the challenges of non-i.i.d. user pair data caused by network structures and the correlation among anchor or non-anchor user pairs. To solve the challenges, DALAUP uses a couple of neural networks with shared-parameter to obtain the vector representations of user pairs, and ensembles three query strategies to select the most informative user pairs for labeling and model training. Experiments on real-world social network data demonstrate that DALAUP outperforms the state-of-the-art approaches.
Introduction
Social network users often maintain accounts across multiple platforms, such as Twitter and Foursquare. Identifying these overlapping individuals—termed anchor users—is a fundamental task for cross-network applications like enhanced recommendation systems and information diffusion tracking.
Because users rarely use identical identifiers across platforms, researchers rely on network structure to predict matches. However, training accurate supervised models requires a massive amount of labeled anchor user pairs, which are expensive and time-consuming to obtain. Active Learning (AL) is a natural solution to reduce labeling costs by iteratively querying an oracle for the most "informative" data points. However, standard AL assumes data is independent and identically distributed (i.i.d.). Social network user pairs violate this due to the interlock property: if User A on Twitter is confirmed to be User B on Foursquare, User A cannot be User C on Foursquare. Standard AL strategies fail to account for this 1-to-1 mapping correlation, leading to suboptimal sampling.
Methodology: The DALAUP Framework
The proposed DALAUP (Deep Active Learning for Anchor User Prediction) framework tightly couples a network embedding model with a novel active learning sampling mechanism to address these challenges.
1. Anchor User Prediction (Embedding Model)
The model extracts structural context using random walks with restart, which is then fed into a shared-parameter Convolutional and Deconvolutional Neural Network. The network learns low-dimensional vector representations by minimizing single-network reconstruction error while maximizing the cosine similarity between known cross-network anchor pairs.
2. Active Learning Query Strategies
To select unlabeled user pairs for querying, DALAUP utilizes three distinct strategies:
- Cross Network Structure Aware Information Entropy: A modified entropy measure that accounts for the "interlock" property, rewarding the discovery of positive matches which provide more structural information than negative ones.
- Cosine Similarity: Queries pairs that are already close in the embedding space to test the model's current boundaries.
- Expected Error Reduction (EER): Selects pairs that maximize the overall label certainty of the remaining unlabeled pool.
3. Multi-Armed Bandit Selection
Rather than relying on a single strategy, DALAUP treats strategy selection as an adversarial multi-armed bandit problem. Using an $\epsilon$-greedy algorithm, the model dynamically chooses the best query strategy at each iteration based on historical validation performance, balancing exploration and exploitation.
Experimental Evaluation
The model was evaluated on two real-world datasets: Foursquare (5,313 users) and Twitter (5,120 users), with 3,141 known anchor users as ground truth.
Key Results
- Active Learning Efficiency: DALAUP drastically outperforms random sampling. As shown in the performance curves, the active selection mechanism yields significant gains in Precision@30 and MAP@30 compared to random baselines. Adding 1,500 intelligently selected pairs provides a much higher performance boost than adding the same number of random pairs.
- Ensemble Superiority: The multi-armed bandit approach (DALAUP) successfully outperforms any of its individual query strategies (e.g., DALAUP-eer or DALAUP-cs) used in isolation, demonstrating the value of adaptive strategy selection.
- Supervised Baseline Performance: Even without active learning, the base embedding model (AUP) is highly effective, outperforming state-of-the-art baselines like IONE and PALE across various training ratios.
Conclusion
DALAUP demonstrates that the "interlock" property of anchor users is a critical insight for efficient sampling. By recognizing that anchor pairs are mutually exclusive, the model can prioritize queries that provide the most structural information. The integration of shared-parameter neural networks with a dynamic multi-armed bandit query ensemble allows DALAUP to achieve superior prediction accuracy with a significantly reduced labeling budget.
Summary updated