A Property Testing Framework for the Theoretical Expressivity of Graph Kernels

A Property Testing Framework for the Theoretical Expressivity of Graph Kernels

Nils M. Kriege, Christopher Morris, Anja Rey, Christian Sohler

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 2348-2354. https://doi.org/10.24963/ijcai.2018/325

Graph kernels are applied heavily for the classification of structured data. However, their expressivity is assessed almost exclusively from experimental studies and there is no theoretical justification why one kernel is in general preferable over another. We introduce a theoretical framework for investigating the expressive power of graph kernels, which is inspired by concepts from the area of property testing. We introduce the notion of distinguishability of a graph property by a graph kernel. For several established graph kernels we show that they cannot distinguish essential graph properties. In order to overcome this, we consider a kernel based on k-disc frequencies. We show that this efficiently computable kernel can distinguish fundamental graph properties. Finally, we obtain learning guarantees for nearest neighbor classifiers in our framework.
Keywords:
Machine Learning: Classification
Machine Learning: Kernel Methods
Machine Learning: Learning Theory