Publication
ICDM 2009
Conference paper

A linear-time graph kernel

View publication

Abstract

The design of a good kernel is fundamental for knowledge discovery from graph-structured data. Existing graph kernels exploit only limited information about the graph structures but are still computationally expensive. We propose a novel graph kernel based on the structural characteristics of graphs. The key is to represent node labels as binary arrays and characterize each node using logical operations on the label set of the connected nodes. Our kernel has a linear time complexity with respect to the number of nodes times the average number of neighboring nodes in the given graphs. The experimental result shows that the proposed kernel performs comparable and much faster than a state-of-the-art graph kernel for benchmark data sets and shows high scalability for new applications with large graphs. © 2009 IEEE.

Date

Publication

ICDM 2009

Authors

Share