Kernels for acyclic digraphs

This paper proposes two efficient kernels for comparing acyclic, directed graphs. The first kernel counts the number of common paths and allows for weighing according to path-length and/or according to the vertices contained in each particular path. The second kernel counts the number of paths in common minors of the graphs involved and allows for length- and vertex-weighting too. Both kernels have algorithmic complexity that is cubic in the size of the vertex-set. The performance of the algorithms is concisely demonstrated using synthetic and real data.

► Graph kernel of complexity O(∣V∣3) that evaluates all common paths in DAG’s with common vertex set V.
► Graph kernel of complexity O(∣V∣3) that evaluates all paths of all common graph-minors in DAG’s with common vertex set V.
► Kernels allow for weighing the paths according to the vertices included.
► Performance is demonstrated on synthetic data.