Can I read A Min-Max Optimization Framework For Online Graph Classification on EtoBox?

A Min-Max Optimization Framework For Online Graph Classification by Peng Yang; Peilin Zhao is a scholarly article available to read on EtoBox.

What is A Min-Max Optimization Framework For Online Graph Classification about?

Traditional online learning for graph node classification adapts graph regularization into ridge regression, which may not be suitable when data is adversarially generated. To solve this issue, we propose a more general min-max optimization framework for online graph node classification. The derived online algorithm can achieve a min-max regret compared with the optimal linear model found offline. However, this algorithm assumes that the label is provided for every node, while label is scare and labeling is usually either too timeconsuming or expensive in real-world applications. To save labeling effort, we propose a novel confidence-based query approach to prioritize the informative labels. Our theoretical result shows that an online algorithm learning on these selected labels can achieve comparable mistake bound with the fully-supervised online counterpart. To take full advantage of these labels, we propose an aggressive algorithm, which can update the model even if no error occurs. Theoretical analysis shows that the mistake bound of the proposed method, thanks to the aggressive update trials, is better than conservative competitor in expectation. We finally empirically evaluate

Author

Peng Yang; Peilin Zhao

Publisher

ACM

Published

2015

Language

EN