String Kernels for Matching Seriated Graphs

Graph seriation allows the nodes of a graph to be placed in a string order, and then matched using string alignment algorithms. Prior work has used Bayesian methods to derive the string edit costs required in matching. The aim in this paper is to demonstrate how the matching of seriated graphs can be kernelised. To do this we make use of string kernels and show how the parameters of the kernels can be linked to edge density. We illustrate that the graph edit distances computed using the string kernel can be used for graph clustering