University of Illinois at Urbana Champaign
Active learning on graphs has received increasing interest in the past years. In this paper, the authors propose a non-adaptive active learning approach on graphs, based on generalization error bound minimization. In particular, they present a data-dependent error bound for a graph-based learning method, namely Learning with Local and Global Consistency (LLGC). They 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.