An empirical study on budget-aware online kernel algorithms for streams of graphs

NEUROCOMPUTING

卷:216

Article

Da San Martino, Giovanni¹  Navarin, Nicolo²  Sperduti, Alessandro² 

[1] HBKU, Qatar Comp Res Inst, POB 5825, Doha, Qatar

[2] Univ Padua, Dept Math, Via Trieste 63, Padua, Italy

关键词: Online learning;    Graph kernels;    Graph streams;    Online passive aggressive;   

DOI  :  10.1016/j.neucom.2016.07.029

来源: Elsevier

【 摘 要 】

Kernel methods are considered as an effective technique for on-line learning. Many approaches have been developed for compactly representing the dual solution of a kernel method when the problem imposes memory constraints. However, in the literature no work is specifically tailored to streams of graphs. Motivated by the fact that the size of the feature space representation of many state-of-the-art graph kernels is relatively small and thus it is explicitly computable, we study whether executing kernel algorithms in the feature space can be more effective than the classical dual approach. We study three different algorithms and various strategies for managing the budget. Efficiency and efficacy of the proposed approaches are experimentally assessed on relatively large graph streams exhibiting concept drift. It turns out that, when strict memory budget constraints have to be enforced, working in feature space, given the current state-of-the-art on graph kernels, is more than a viable alternative to dual approaches, both in terms of speed and classification performance. (C) 2016 Elsevier B.V. All rights reserved.

【 授权许可】

Free