Skip to yearly menu bar Skip to main content


Poster

KONG: Kernels for ordered-neighborhood graphs

Moez Draief · Konstantin Kutzkov · Kevin Scaman · Milan Vojnovic

Room 517 AB #122

Keywords: [ Kernel Methods ] [ Classification ] [ Algorithms ]


Abstract:

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

Live content is unavailable. Log in and register to view live content