Title: A Unifying View of Explicit and Implicit Feature Maps for Structured Data: Systematic Studies of Graph Kernels,
Abstract: Non-linear kernel methods can be approximated by fast linear ones using
suitable explicit feature maps allowing their application to large scale
problems. To this end, explicit feature maps of kernels for vectorial data have
been extensively studied. As many real-world data is structured, various
kernels for complex data like graphs have been proposed. Indeed, many of them
directly compute feature maps. However, the kernel trick is employed when the
number of features is very large or the individual vertices of graphs are
annotated by real-valued attributes.
Can we still compute explicit feature maps efficiently under these
circumstances? Triggered by this question, we investigate how general
convolution kernels are composed from base kernels and construct corresponding
feature maps. We apply our results to widely used graph kernels and analyze for
which kernels and graph properties computation by explicit feature maps is
feasible and actually more efficient. In particular, we derive feature maps for
random walk and subgraph matching kernels and apply them to real-world graphs
with discrete labels. Thereby, our theoretical results are confirmed
experimentally by observing a phase transition when comparing running time with
respect to label diversity, walk lengths and subgraph size, respectively.
Moreover, we derive approximative, explicit feature maps for state-of-the-art
kernels supporting real-valued attributes including the GraphHopper and Graph
Invariant kernels. In extensive experiments we show that our approaches often
achieve a classification accuracy close to the exact methods based on the
kernel trick, but require only a fraction of their running time.