Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
534098 | Pattern Recognition Letters | 2012 | 6 Pages |
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.