Online Spectral Learning on a Graph with Bandit Feedback

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.