Extensions of Marginalized Graph Kernels

Abstract

Positive definite kernels between labeled graphs have recently been proposed. They enable the application of kernel methods, such as support vectormachines, to the analysis and classification of graphs, for example, chemicalcompounds. These graph kernels are obtained by marginalizing a kernel betweenpaths with respect to a random walk model on the graph vertices along theedges. We propose two extensions of these graph kernels, with the double goal toreduce their computation time and increase their relevance as measure ofsimilarity between graphs. First, we propose to modify the label of eachvertex by automatically adding information about its environment with the useof the Morgan algorithm. Second, we suggest a modification of the random walkmodel to prevent the walk from coming back to a vertex that was just visited. These extensions are then tested on benchmark experiments of chemicalcompounds classification, with promising results.