An Empirical Study on Budget-Aware Online Kernel Algorithms for Streams
  of Graphs
  Kernel methods are considered 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 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.
