Propagation Kernels - Efficient Graph Kernels from Propagated Information – Københavns Universitet

Propagation Kernels - Efficient Graph Kernels from Propagated Information

Talk by Marion Neumann

Propagation kernels are a flexible graph kernel framework for efficiently measuring the similarity of structured data. The main idea behind their design is to monitor how information spreads through a set of given graphs. They leverage early-stage distributions from propagation schemes such as random walks to capture structural information encoded in node labels, attributes, and edge information.

Doing so has two benefits. First, off-the-shelf propagation schemes can be used to naturally realize kernels for all kinds of graphs such as labeled, partially labeled, unlabeled, (un-)directed, and attributed graphs. Second, they can be considerably faster than state-of-the-art approaches without sacrificing performance. In this talk, we will introduce propagation kernels and showcase their efficient computation for grid graphs. We will present results of various experiments on graph classification including protein classification, image-based texture classification, and 3D object category prediction.