Provenance Graph Kernel
  Provenance is a record that describes how entities, activities, and agents
have influenced a piece of data; it is commonly represented as graphs with
relevant labels on both their nodes and edges. With the growing adoption of
provenance in a wide range of application domains, users are increasingly
confronted with an abundance of graph data, which may prove challenging to
process. Graph kernels, on the other hand, have been successfully used to
efficiently analyse graphs. In this paper, we introduce a novel graph kernel
called provenance kernel, which is inspired by and tailored for provenance
data. It decomposes a provenance graph into tree-patterns rooted at a given
node and considers the labels of edges and nodes up to a certain distance from
the root. We employ provenance kernels to classify provenance graphs from three
application domains. Our evaluation shows that they perform well in terms of
classification accuracy and yield competitive results when compared against
existing graph kernel methods and the provenance network analytics method while
more efficient in computing time. Moreover, the provenance types used by
provenance kernels also help improve the explainability of predictive models
built on them.
