A Min-Max Optimization Framework For Online Graph Classification

ABSTRACT

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 time-consuming 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 it on several real-world graph databases. Encouraging experimental results further demonstrate the effectiveness of our method.

References

1. J. Abernethy, A. Agarwal, and P. L. Bartlett. A stochastic view of optimal regret through minimax duality. In Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
2. M. S. Bartlett. An inverse matrix adjustment arising in discriminant analysis. The Annals of Mathematical Statistics, pages 107--111, 1951.
3. M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. The Journal of Machine Learning Research, 7:2399--2434, 2006.
4. G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Learning noisy linear classifiers via adaptive and selective sampling. Machine learning, 83(1):71--102, 2011.
5. N. Cesa-Bianchi, A. Conconi, and C. Gentile. A second-orde perceptron algorithm. SIAM Journal on Computing, 34(3):640--668, 2005.
6. N. Cesa-Bianchi, C. Gentile, and F. Orabona. Robust bounds for classification via selective sampling. In ICML-09, pages 121--128, 2009.
7. N. Cesa-Bianchi, C. Gentile, and L. Zaniboni. Worst-case analysis of selective sampling for linear classification. The Journal of Machine Learning Research 7:1205--1230, 2006.
8. O. Chapelle, B. Schölkopf, A. Zien, et al. Semi-supervised learning, volume 2. MIT press Cambridge, 2006.
9. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressive algorithms. JMLR, 7:551--585, 2006.
10. K. Crammer, M. Dredze, and F. Pereira. Confidence-weighted linear classification for text categorization. JMLR, 13(1):1891--1926, 2012.
11. C. Desrosiers and G. Karypis. Within-network classification using local structure similarity. In Machine Learning and Knowledge Discovery in Databases, pages 260--275. 2009.
12. C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211--218, 1936.
13. J. Forster. On relative loss bounds in generalized linear regression. In Fundamentals of Computation Theory, pages 269--280, 1999.
14. Y. Freund, H. S. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine learning, 28(2--3):133--168, 1997.
15. C. Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265--299, 2003.
16. G. Giacinto, F. Roli, and L. Didaci. Fusion of multiple classifiers for intrusion detection in computer networks. Pattern recognition letters, 24(12):1795--1803, 2003.
17. A. B. Goldberg, X. Zhu, A. Furger, and J.-M. Xu. Oasis: Online active semi-supervised learning. In AAAI, 2011.
18. Q. Gu, C. Aggarwal, J. Liu, and J. Han. Selective sampling on graphs for classification. In Proceedings of the 19th ACM SIGKDD, pages 131--139, 2013.
19. M. Herbster, G. Lever, and M. Pontil. Online prediction on large diameter graphs. In NIPS-09, pages 649--656, 2009.
20. M. Herbster and M. Pontil. Prediction on a graph with a perceptron. In NIPS-06, pages 577--584, 2006.
21. M. Herbster, M. Pontil, and L. Wainer. Online learning over graphs. In ICML-05, pages 305--312, 2005.
22. S. C. Hoi, J. Wang, and P. Zhao. Libol: A library for online learning algorithms. The Journal of Machine Learning Research, 15(1):495--499, 2014.
23. M. Ji, J. Han, and M. Danilevsky. Ranking-based classification of heterogeneous information networks. In Proceedings of the 17th ACM SIGKDD, pages 1298--1306, 2011.
24. D. Kushnir. Active-transductive learning with label-adapte kernels. In Proceedings of the 20th ACM SIGKDD, pages 462--471, 2014.
25. F. Orabona and N. Cesa-Bianchi. Better algorithms for selective sampling. In ICML-11, pages 433--440, 2011.
26. F. Orabona and K. Crammer. New adaptive algorithms for online classification. In NIPS-10, pages 1840--1848, 2010.
27. M. Pennacchiotti and A.-M. Popescu. A machine learning approach to twitter user classification. ICWSM, 11:281--288, 2011.
28. A. A. Ross, K. Nandakumar, and A. K. Jain. Handbook of multibiometrics, volume 6. Springer Science & Business Media, 2006.
29. N. Slonim, E. Yom-Tov, and K. Crammer. Active online classification via information maximization. In IJCAI, volume 22, page 1498, 2011.
30. A. J. Smola and R. Kondor. Kernels and regularization on graphs. In Learning theory and kernel machines, pages 144--158. Springer, 2003.
31. E. Takimoto and M. K. Warmuth. The last-step minimax algorithm. In Algorithmic Learning Theory, pages 279--290, 2000.
32. V. Vovk. Competitive on-line linear regression. NIPS-98, pages 364--370, 1998.
33. J. Wang, P. Zhao, and S. C. Hoi. Exact soft confidence-weighted learning. In ICML-12, pages 121--128, 2012.
34. Z. Yang, J. Tang, and Y. Zhang. Active learning for streaming networked data. In CIKM-14, pages 1129--1138, 2014.
35. P. Zhao and S. C. Hoi. Cost-sensitive online active learning with application to malicious url detection. In Proceedings of the 19th ACM SIGKDD, pages 919--927. ACM, 2013.
36. P. Zhao, S. C. Hoi, and R. Jin. Double updating online learning. The Journal of Machine Learning Research, 12:1587--1615, 2011.
37. P. Zhao, S. C. H. Hoi, R. Jin, and T. Yang. Online AUC maximization. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011, pages 233--240, 2011.
38. P. Zhao, S. C. H. Hoi, J. Wang, and B. Li. Online transfer learning. Artificial Intelligence, 216:76--102, 2014

Index Terms

• Computing methodologies

  • Machine learning

• Information systems

  • Information systems applications

    • Data mining