Online Spectral Learning on a Graph with Bandit Feedback

Quanquan Gu, Jiawei Han

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

Abstract

Online learning on a graph is appealing due to its efficiency. However, existing online learning algorithms on a graph are limited to binary classification. Moreover, they require accessing the full label information, where the label oracle needs to return the true class label after the learner makes classification of each node. In many application scenarios, we only have access to partial label information, where the label oracle will return a single bit indicating whether the prediction is correct or not, instead of the true class label. This is also known as bandit feedback. In this paper, to overcome the above limitations of existing online learning algorithms on a graph, we study online learning on a graph for multi-class node classification, in both the full information setting and the partial information setting. First, we present an online multi-class classification algorithm in the full information setting. It is based on function learning on a graph using the spectral information of the graph Laplacian. We show that it attains O (cd log T) regret bound, where T is the number of rounds in online learning, c is the number of classes, and d is the number of eigenvectors of the graph Laplacian used for learning. Second, we present an online multi-class classification algorithm with bandit feedback. We use upper-confidence bound technique to trade off the exploration and exploitation of label information. We show that it attains O (cd √T log T) regret bound, which is only a √T factor worse than the proposed algorithm in the full information setting. Experiments on several benchmark graph datasets show that the proposed online multi-class classification algorithm beats the state-of-art baseline, and the proposed bandit algorithm is also much better than the bandit version of the baseline.

Original languageEnglish (US)
Title of host publicationProceedings - 14th IEEE International Conference on Data Mining, ICDM 2014
EditorsRavi Kumar, Hannu Toivonen, Jian Pei, Joshua Zhexue Huang, Xindong Wu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages833-838
Number of pages6
EditionJanuary
ISBN (Electronic)9781479943029
DOIs
StatePublished - Jan 1 2014
Event14th IEEE International Conference on Data Mining, ICDM 2014 - Shenzhen, China
Duration: Dec 14 2014Dec 17 2014

Publication series

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

Other

Other14th IEEE International Conference on Data Mining, ICDM 2014
CountryChina
CityShenzhen
Period12/14/1412/17/14

Keywords

  • Bandit Feedback
  • Graph Cut Size
  • Online Learning on a Graph
  • Partial Information Setting
  • Regret Bound
  • Spectral Learning

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Online Spectral Learning on a Graph with Bandit Feedback'. Together they form a unique fingerprint.

Cite this