Constrained Active Learning for Anchor Link Prediction Across Multiple Heterogeneous Social Networks

Junxing Zhu, Jiawei Zhang, Quanyuan Wu, Yan Jia, Bin Zhou, Xiaokai Wei, Philip S. Yu

TL;DR

This paper introduces "Constrained Active Learning" for predicting anchor links between user accounts across different social networks. By leveraging the inherent one-to-one constraint of anchor links, their method efficiently queries for labels, significantly improving prediction accuracy compared to traditional methods, especially when labeled data is scarce.

What Problem Does This Paper Address?

In today's digital landscape, individuals are active on multiple social media platforms. Identifying which accounts belong to the same person across these "heterogeneous social networks" is crucial for applications like cross-network recommendations and data integration. This is known as "anchor link prediction." While supervised learning models can be effective, they typically require a large number of pre-labeled anchor links. However, manually labeling these links is extremely time-consuming and expensive, leading to a scenario where most anchor links are unlabeled. This paper tackles this challenge by proposing an active learning approach that intelligently selects which unlabeled links to query for labels, thereby maximizing the utility of limited labeling resources.

Methods

The core innovation lies in adapting active learning to the specific constraints of anchor link prediction. Traditional active learning often assumes data points are independent, but anchor links have a crucial one-to-one constraint: a user can only have one account in another network. This means if one anchor link is identified as positive (an existing connection), all other potential links involving those same two users must be negative (non-existent).

The authors introduce Constrained Active Learning (CAL) methods. When a positive anchor link is identified, CAL automatically labels related links as negative, effectively gaining more information from a single query. They propose two main types of CAL:

  • Normal Constrained Active Learning (NCAL): This category includes methods like Basic-entropy-based CAL (BC) and Mean-entropy-based CAL (MC). These methods use entropy measures to quantify the informativeness of unlabeled links. MC is particularly interesting as it considers not only the entropy of a link itself but also the average entropy of its related links, aiming to better handle imbalanced data.
  • Biased Constrained Active Learning (BCAL): These methods prioritize querying potential positive links, aiming to acquire more informative positive samples. This includes Biased Basic-entropy-based CAL (BBC) and Biased Mean-entropy-based CAL (BMC).

The underlying anchor link prediction model used is Multi-Network Anchoring (MNA), which leverages heterogeneous features (social, spatial, temporal, and text) from multiple networks.

Datasets

The experiments were conducted on two real-world social network datasets:

  • Foursquare: A location-based social network.
  • Twitter: A microblogging social network.

The paper mentions collecting ground-truth anchor links by identifying users who explicitly linked their Twitter IDs in their Foursquare profiles. A total of 600 anchor links were obtained. The datasets were pre-processed and partitioned into training, query, validation, and test sets using a 6-fold cross-validation approach.

Key Insights and Ideas

  • The power of constraints: The one-to-one constraint of anchor links is not just a technicality; it's a powerful mechanism that allows active learning to gain significantly more information from each query than in traditional settings.
  • Beyond individual entropy: The MC method's insight that the "mean entropy" of related links is crucial for robust active learning, especially in imbalanced datasets, is a key contribution. It suggests that understanding the context of a link within its neighborhood is as important as the link's inherent uncertainty.
  • Balancing exploration and exploitation: The Biased CAL methods attempt to strike a balance between exploring uncertain links and exploiting potentially positive ones, showing that different strategies can be beneficial depending on the data characteristics.
  • Generalizability: The paper demonstrates that their constrained active learning framework can be integrated with various existing anchor link prediction techniques, highlighting its broad applicability.

Key Results

The proposed Mean-entropy-based Constrained Active Learning (MC) method consistently outperformed other baseline methods, including traditional active learning approaches and the base MNA model, across various metrics (F1-measure, Precision, Recall).

  • In experiments with different numbers of queries, MC achieved superior performance, often ranking first.
  • In experiments with varying imbalance ratios (Negative-Positive Rates), MC also demonstrated strong performance, generally outperforming other methods.
  • The Biased Basic-entropy-based CAL (BBC) method also showed competitive results, particularly when a reasonable validation set was not available, making it a good alternative in such scenarios.
  • The authors' constrained active learning methods (MC and BBC) significantly improved the performance of other state-of-the-art anchor link prediction techniques when integrated with them.

Limitations and Future Work

  • Validation Set Dependency: The MC method's performance is sensitive to the size and representativeness of the validation set used for calculating probabilities. If the validation set is insufficient, its performance can degrade.
  • Parameter Tuning: The paper mentions that parameter tuning, such as for the threshold adjusting pace ($\Delta\delta$) in Algorithm 2, can impact performance.
  • Future Work: The authors suggest future research directions, including:
  • Investigating how to select an optimal-sized validation set for MC.
  • Determining the optimal value for the parameter $\Delta\delta$.
  • Exploring how to adapt the framework to other types of social network link prediction problems.

Summary updated

Abstract

Nowadays, people are usually involved in multiple heterogeneous social networks simultaneously. Discovering the anchor links between the accounts owned by the same users across different social networks is crucial for many important inter-network applications, e.g., cross-network link transfer and cross-network recommendation. Many different supervised models have been proposed to predict anchor links so far, but they are effective only when the labeled anchor links are abundant. However, in real scenarios, such a requirement can hardly be met and most anchor links are unlabeled, since manually labeling the inter-network anchor links is quite costly and tedious. To overcome such a problem and utilize the numerous unlabeled anchor links in model building, in this paper, we introduce the active learning based anchor link prediction problem. Different from the traditional active learning problems, due to the one-to-one constraint on anchor links, if an unlabeled anchor link a = ( u , v ) is identified as positive (i.e., existing), all the other unlabeled anchor links incident to account u or account v will be negative (i.e., non-existing) automatically. Viewed in such a perspective, asking for the labels of potential positive anchor links in the unlabeled set will be rewarding in the active anchor link prediction problem. Various novel anchor link information gain measures are defined in this paper, based on which several constraint active anchor link prediction methods are introduced. Extensive experiments have been done on real-world social network datasets to compare the performance of these methods with state-of-art anchor link prediction methods. The experimental results show that the proposed Mean-entropy-based Constrained Active Learning (MC) method can outperform other methods with significant advantages.
BibTeX
@inproceedings{zhu2017constrained,
  author = {Junxing Zhu and Jiawei Zhang and Quanyuan Wu and Yan Jia and Bin Zhou and Xiaokai Wei and Philip S. Yu},
  title = {{Constrained Active Learning for Anchor Link Prediction Across Multiple Heterogeneous Social Networks}},
  booktitle = {Sensors},
  year = {2017},
  url = {https://openreview.net/forum?id=5FYdCd-G-Ri},
}
Figure