@INPROCEEDINGS{Shi:11TIST,
AUTHOR = "Lixin Shi and Yuhang Zhao and Jie Tang",
TITLE = "Batch Mode Active Learning for Networked Data",
YEAR = {2011},
BOOKTITLE = "ACM Transactions on Intelligent Systems and Technology (TIST)",
}

Introduction

We study a novel problem of batch mode active learning for networked data. In this problem, data instances are connected with links and their labels are correlated with each, and the goal of our batch mode active learning is to exploit the link-based dependencies and node-specific content information to actively select a batch of instances to query the user for learning an accurate model to label the unknown instances in the network. We present three criteria (i.e., minimum redundancy, maximum uncertainty and maximum impact) to quantify the informativeness of a set of instances, and formalize the batch mode active learning problem as selecting a set of instances by maximizing an objective function which combines both link and content information. Solving the objective function is NP-hard, we present an efficient algorithm to optimize the objective function with a bounded approximation rate. To scale to real large networks, we develop a parallel implementation of the algorithm. Experimental results on both synthetic data sets and real-world data sets demonstrate the effectiveness and efficiency of our approach.

Machine learning algorithms often suffer from insufficiently labeled training data. The goal of active learning is, not only, as usual, to construct an accurate classifier, but also to minimize the number of labeled instances by actively selecting a few number of instances to query the user. Also, recently there has seen a new direction of machine learning field, that is how to learn an accurate model to classify the networked data. In this work, we aim to answer the question: how to actively select a set of instances from the networked data and query the users in a batch mode?

We refer to this problem as the Batch Mode active learning (BMAL) problem for networked data. Suppose we are given a data set with only one labeled sample (with positive label), and the samples are connected in a two dimensional space. We try to select two samples to query the user in a batch mode. If we only consider the content information, then we would tend to select the two center nodes (top-right figure); while if we only consider the link information, we would select two samples with the most links (middle-left figure). By combining the link and content information, our BMAL method suggests two different samples (middle-right figure). The bottom two figures show how a machine learning algorithm updates the classification model when the user provides labels to the queried samples (suppose one positive and one negative).

(The top-left figure plots the input networked data, where pink circles indicate instances with positive labels, gray circles indicate unknown labels, and blue circles indicate instances with negative labels. "w/o link'' stands for active learning without considering links; "w/o content'' stands for active learning without considering the content information; and ``BMAL'' stands for active learning by the proposed method, which considers both the content and link information.)

Technologies

We designed Q(S) as the objective function over S, a subset of the unlabeled set. It measures the informativeness of S, so collective active learning could be viewed as selecting:

There are three criteria to design this objective function:

    -- Maximum Uncertainty: H(S) as summation of entropies
    -- Maximum Impact: Graph-cut-based design of C(S), which could be seen as a summation of maximum impacts over samples in S
    --  Minimum Redundancy: We theoretically proved that definition of C(S) minimizes redundancy

Experiments

We have conducted extensive experiments on both synthetic and real-world data sets. The following is a series of experiments on real-world document citation-network data sets:

Here is the average classification accuracy result, comparing with several baselines:  Random, Most uncertainty(MU), Active Learning using Gaussian Fields(GF, suggested by Zhu et al. 2003), Hybrid(suggested by Macskassy 2009), k-means(K-M, suggested by Rattigan et al. 2007):

Data & Codes

Codes could be found here. It is mainly written in Matlab, mainly consists of the active selection process (see ./LCC) and auxiliary routine for learning (./SVM, ./BMAL_Sparse, ./GF), some toolkit. It also contains the opensource netkit toolkit (see http://wiki.netkit.org/index.php/Main_Page)

Data coud be found here. It includes the four data sets that we are using:

• Cora Data Set contains 2,708 scientific publications, and the documents are classified into seven categories (fields): i.e., Case Based, Genetic Algorithms, Neural Networks, Probabilistic Methods, Reinforcement Learning, Rule Learning, and Theory. After stemming and removing stop words and words that appear less than 10 times in the data set, we obtain a vocabulary of 1,433 unique words. There are 5,429 citation relationships between the documents.
• Citeseer Data Set contains 3,312 publications, categorized into 6 classes: Agents, AI, DB, IR, ML, and HCI. There are 3,703 unique words after processing, and the number of citations is 4,732.
• WebKB Data Set contains web pages from four computer science departments, and there are five categories: course, faculty, student, project, and staff. This is a subset of the original WebKB data set (see reference). The webKB data set contains 877 web pages and 1,703 unique words. There are 2,868 total links between these pages.
• UCI 20NewsGroups Data Set contains approximately 20,000 newsgroup documents, partitioned (nearly) evenly across 20 different categories. Some of the categories are closely related to each other and some are unrelated.

Full paper could be found here.