TY - GEN
T1 - Towards active learning on graphs
T2 - 12th IEEE International Conference on Data Mining, ICDM 2012
AU - Gu, Quanquan
AU - Han, Jiawei
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - Active learning
KW - Generalization error bound
KW - Graph
KW - Sequential optimization
UR - http://www.scopus.com/inward/record.url?scp=84874056110&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84874056110&partnerID=8YFLogxK
U2 - 10.1109/ICDM.2012.72
DO - 10.1109/ICDM.2012.72
M3 - Conference contribution
AN - SCOPUS:84874056110
SN - 9780769549057
T3 - Proceedings - IEEE International Conference on Data Mining, ICDM
SP - 882
EP - 887
BT - Proceedings - 12th IEEE International Conference on Data Mining, ICDM 2012
Y2 - 10 December 2012 through 13 December 2012
ER -