Towards active learning on graphs: An error bound minimization approach

Quanquan Gu, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Active learning on graphs has received increasing interest in the past years. In this paper, we propose a nonadaptive active learning approach on graphs, based on generalization error bound minimization. In particular, we present a data-dependent error bound for a graph-based learning method, namely learning with local and global consistency (LLGC). We show that the empirical transductive Rademacher complexity of the function class for LLGC provides a natural criterion for active learning. The resulting active learning approach is to select a subset of nodes on a graph such that the empirical transductive Rademacher complexity of LLGC is minimized. We propose a simple yet effective sequential optimization algorithm to solve it. Experiments on benchmark datasets show that the proposed method outperforms the stateof-the-art active learning methods on graphs.

Original languageEnglish (US)
Title of host publicationProceedings - 12th IEEE International Conference on Data Mining, ICDM 2012
Pages882-887
Number of pages6
DOIs
StatePublished - Dec 1 2012
Event12th IEEE International Conference on Data Mining, ICDM 2012 - Brussels, Belgium
Duration: Dec 10 2012Dec 13 2012

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other12th IEEE International Conference on Data Mining, ICDM 2012
CountryBelgium
CityBrussels
Period12/10/1212/13/12

Keywords

  • Active learning
  • Generalization error bound
  • Graph
  • Sequential optimization

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Towards active learning on graphs: An error bound minimization approach'. Together they form a unique fingerprint.

Cite this