graphkernels-package {graphkernels}

Graph Kernels

Description

A fast C++ implementation for computing various graph kernels including (1) simple kernels between vertex and/or edge label histograms, (2) graphlet kernels, (3) random walk kernels (popular baselines), and (4) the Weisfeiler-Lehman graph kernel (state-of-the-art).

Details

This library provides the following graph kernels:

• the linear kernel between vertex label histograms

• the linear kernel between edge label histograms

• the linear kernel between vertex-edge label histograms

• the linear kernel combination vertex label histograms and vertex-edge label histograms

• the Gaussian RBF kernel between vertex label histograms

• the Gaussian RBF kernel between edge label histograms

• the Gaussian RBF kernel between vertex-edge label histograms

• the graphlet kernel

• the k-step random walk kernel

• the geometric random walk kernel

• the exponential random walk kernel

• the shortest-path kernel

• the Weisfeiler-Lehman subtree kernel

Given a list of igraph graphs, each function calculates the corresponding kernel (Gram) matrix.

Author(s)

Mahito Sugiyama

Maintainer: Mahito Sugiyama <[e-mail]>

References

Borgwardt, K. M., Kriegel, H.-P.: Shortest-Path Kernels on Graphs, Proceedings of the 5th IEEE International Conference on Data Mining (ICDM'05), 74-81 (2005) https://ieeexplore.ieee.org/document/1565664/.

Debnath, A. K., Lopez de Compadre, R. L., Debnath, G., Shusterman, A. J., Hansch, C.: Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity, Journal of Medicinal Chemistry, 34(2), 786-797 (1991) https://pubs.acs.org/doi/abs/10.1021/jm00106a046.

Gartner, T., Flach, P., Wrobel, S.: On graph kernels: Hardness results and efficient alternatives, Learning Theory and Kernel Machines (LNCS 2777), 129-143 (2003) https://link.springer.com/chapter/10.1007/978-3-540-45167-9_11.

Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., Borgwardt, K. M.: Weisfeiler-Lehman Graph Kernels, Journal of Machine Learning Research, 12, 2359-2561 (2011) https://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf.

Shervashidze, N., Vishwanathan, S. V. N., Petri, T., Mehlhorn, K., Borgwardt, K. M.: Efficient Graphlet Kernels for Large Graph Comparison, Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS), 5, 488-495 (2009) https://proceedings.mlr.press/v5/shervashidze09a.html.

Sugiyama, M., Borgwardt, K. M.: Halting in Random Walk Kernels, Advances in Neural Information Processing Systems (NIPS 2015), 28, 1630-1638 (2015) https://papers.nips.cc/paper/5688-halting-in-random-walk-kernels.pdf.

Examples

data(mutag)
KEH <- CalculateEdgeHistKernel(mutag)
  ## compute linear kernel between edge histograms
KWL <- CalculateWLKernel(mutag, 5)
  ## compute Weisfeiler-Lehman subtree kernel