KONG: Kernels for ordered-neighborhood graphs
This work addresses graph comparison for evolving graphs, providing incremental improvements in feature informativeness and efficiency for specific applications.
The authors tackled the problem of comparing graphs with ordered neighborhoods by developing novel graph kernels that combine convolutional subgraph and string kernels, resulting in scalable algorithms with precise bounds on accuracy and complexity, and experiments showing that neighborhood ordering yields more informative features.
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.