Ordered Decompositional DAG kernels enhancements

By Giovanni Da San Martino, Nicoló Navarin, Alessandro Sperduti. 2015

22 citations recorded by the source corpus.

In this paper, we show how the Ordered Decomposition DAGs (ODD) kernel framework, a framework that allows the definition of graph kernels from tree kernels, allows to easily define new state-of-the-art graph kernels. Here we consider a fast graph kernel based on the Subtree kernel (ST), and we propose various enhancements to increase its expressiveness. The proposed DAG kernel has the same worst-case complexity as the one based on ST, but an improved expressivity due to an augmented set of features. Moreover, we propose a novel weighting scheme for the features, which can be applied to other kernels of the ODD framework. These improvements allow the proposed kernels to improve on the classification performances of the ST-based kernel for several real-world datasets, reaching state-of-the-art performances.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

On Filter Size in Graph Convolutional Networks (2018, background): “We do not include other state-of-the-art graph kernels such as NSPDK [33] and ODD [26] because their performance is not much different from the considered ones, and it is above the scope of this paper to extensively compare the graph kernels in literature.”
Tree-Based Kernel for Graphs With Continuous Attributes (2015, methodology): “This section briefly recalls the procedure for extrac ting them from a graph [4] [13].”