A Min-Max Optimization Framework For Online Graph Classification

摘要: Traditional online learning for graph node classification adapts 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 classification. The derived algorithm can achieve regret compared with the optimal linear model found offline. However, assumes that label provided every node, while scare and labeling usually either too time-consuming or expensive in real-world applications. save effort, novel confidence-based query approach to prioritize informative labels. Our theoretical result shows an on these selected labels comparable mistake bound fully-supervised counterpart. take full advantage of labels, aggressive algorithm, update even if no error occurs. Theoretical analysis proposed method, thanks trials, better than conservative competitor expectation. We finally empirically evaluate it several databases. Encouraging experimental results further demonstrate effectiveness our method.