Extreme Graph Kernels for Online Learning on a Memory Budget

Nicolò Navarin, Giovanni Da San Martino, Alessandro Sperduti

Abstract

Learning with limited resources (processing power and memory) on a stream of data is a challenging problem. When dealing with structured data, in particular with graphs, state-of- the-art graph kernels coupled with budget-aware online learning algorithms provide an efficient and effective solution. They map the input graph in a feature space that can be represented explicitly in sparse format. In this paper, we propose a method to enhance existing graph kernels in a streaming scenario with strict memory constraints. Specifically, we combine state-of-the-art online kernel methods with the power and flexibility of the feature representation of Extreme Learning Machines (ELM). Although being in principle a simple idea, our proposal, applied to several real-world datasets, outperformed state-of-the-art algorithms on streams of graphs with respect to predictive performance.
BibTeX
@inproceedings{navarin2018extreme,
  author = {Nicolò Navarin and Giovanni Da San Martino and Alessandro Sperduti},
  title = {{Extreme Graph Kernels for Online Learning on a Memory Budget}},
  booktitle = {IJCNN},
  year = {2018},
  doi = {10.1109/ijcnn.2018.8489432},
}

Loading related content...

Figure