Ordered Decompositional DAG Kernels Enhancements
This work provides incremental improvements to graph kernels for researchers in machine learning and graph analysis, potentially benefiting applications in bioinformatics, social networks, and cheminformatics.
The authors tackled the problem of graph classification by enhancing the Ordered Decomposition DAGs (ODD) kernel framework, specifically improving a fast Subtree kernel-based approach with augmented features and a novel weighting scheme. The result was state-of-the-art classification performance on several real-world datasets, with the same worst-case complexity as the original kernel.
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.