Active learning for networked data based on non-progressive diffusion model

Zhilin Yang, Jie Tang, Bin Xu, Chunxiao XingWSDM 2014 · DOI

TL;DR

This paper introduces MaxCo, a novel active learning framework for networked data that leverages a non-progressive diffusion model to intelligently select samples for labeling. By framing active learning as a "minimum source set" problem, MaxCo achieves significant improvements in classification accuracy and F1 scores compared to existing methods across various real-world social network datasets.

What Problem Does This Paper Address?

Collecting labeled data is a bottleneck in machine learning, especially for networked data where samples (e.g., users in a social network) are interconnected and their labels are correlated. Traditional active learning methods often treat samples independently, which is suboptimal for networked data. Furthermore, querying labels one by one can be inefficient; a "batch mode" approach, where a set of samples is queried simultaneously, is often preferred. This paper tackles the challenge of batch mode active learning for networked data by proposing a method that effectively models label dependencies and optimizes the selection of informative samples for labeling.

Methods

The core of the paper lies in its novel approach to modeling networked data and active learning:

  • Probabilistic Graphical Models (Factor Graphs): The authors use factor graphs to represent the relationships and dependencies between samples in a network. Loopy Belief Propagation (LBP) is employed for learning model parameters.
  • Non-Progressive Diffusion Model: They connect the information diffusion process within the network to active learning. Specifically, they adopt a "non-progressive" diffusion model, where a sample's state (e.g., labeled/unlabeled) can change dynamically, mirroring the iterative nature of LBP. This is contrasted with "progressive" models where states are permanent.
  • MaxCo Algorithm: This is the proposed active learning algorithm. It's a two-step process:
  • Reduction to Minimum Source Set Problem: The active learning problem is reformulated as finding the smallest set of "source" nodes (samples to be labeled) that can "activate" a desired set of "target" nodes (samples to be influenced). This reduction is proven to be equivalent to the original problem.
  • MinSS Algorithm: An iterative greedy algorithm is proposed to solve the Minimum Source Set problem. It works by iteratively expanding a target set of uncertain nodes and greedily selecting source nodes to activate them, while considering node thresholds and degrees.
  • Threshold and Uncertainty Definitions: The paper defines how to quantify a node's "threshold" (how easily it's activated) and "uncertainty" (how much its label is unknown), using measures like entropy.

Datasets

The authors evaluated their MaxCo algorithm on four real-world social network datasets:

  • Coauthor: Extracted from ArnetMiner, focusing on advisor-advisee relationships.
  • Slashdot: A social network from the Slashdot website, used to infer friendships.
  • Mobile: Logs of mobile phone activity (calls, Bluetooth) to infer friendships.
  • Enron: Email communication data from Enron employees, used to infer manager-subordinate relationships.

These datasets are used to train and evaluate factor graph models and compare the performance of different active learning strategies.

Key Insights and Ideas

  • Non-progressive diffusion is key for networked active learning: The paper argues that a non-progressive diffusion model better captures the iterative nature of belief propagation in graphical models for networked data, leading to more effective label selection than progressive models.
  • Framing active learning as "Minimum Source Set" is powerful: This reformulation allows for a more structured and theoretically grounded approach to selecting samples, especially in batch mode.
  • MaxCo balances uncertainty and network structure: The algorithm's effectiveness stems from its ability to consider both the inherent uncertainty of a sample's label and its position and connectivity within the network.
  • MaxCo is robust to parameter choices: Experiments show that MaxCo is relatively insensitive to the specific choices of uncertainty measures and threshold parameters, making it more practical.

Key Results

  • Significant performance improvements: MaxCo consistently outperformed other competing methods (Random, IMS, MU, BMAL) on all four datasets in terms of both accuracy and F1 scores. Improvements ranged from 5%-10% on average.
  • Effective handling of label imbalance: Unlike some other methods that suffer from imbalanced labeled data, MaxCo demonstrated more balanced sample selection and maintained performance.
  • Theoretical guarantees: The paper provides theoretical analysis, proving the NP-hardness of the problem and establishing convergence and correctness guarantees for the MinSS algorithm, along with approximation ratios.

Limitations and Future Work

  • Parameter tuning: While MaxCo is shown to be relatively insensitive to parameters, the paper notes that tuning the parameter $\eta$ (used in threshold definition) requires careful consideration to balance different factors.
  • Computational complexity: The paper focuses on theoretical analysis and experimental validation. Further investigation into the scalability of the algorithm for extremely large networks might be beneficial.
  • Generalizability: The authors suggest that the framework is general and can be applied to arbitrary networked data, implying potential for application to other domains beyond social networks.

Summary updated

BibTeX
@inproceedings{yang2014active,
  author = {Zhilin Yang and Jie Tang and Bin Xu and Chunxiao Xing},
  title = {{Active learning for networked data based on non-progressive diffusion model}},
  booktitle = {WSDM},
  year = {2014},
  doi = {10.1145/2556195.2556223},
}
Figure