Type: Package
Title: Graph Kernels
Version: 1.6.1
Date: 2021-12-20
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).
License: GPL-2 | GPL-3 [expanded from: GPL (≥ 2)]
Imports: Rcpp (≥ 0.12.9)
Depends: igraph (≥ 1.1.2)
LinkingTo: Rcpp, RcppEigen
NeedsCompilation: yes
Packaged: 2021-12-20 08:26:04 UTC; mahito
Author: Mahito Sugiyama [aut, cre], The development of the graphkernels open access software package was financially supported by the Horizon 2020/CDS-QUAMRI/634541 project. This support is gratefully acknowledged. [fnd]
Maintainer: Mahito Sugiyama <mahito@nii.ac.jp>
Repository: CRAN
Date/Publication: 2021-12-20 09:00:02 UTC

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:

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

Author(s)

Mahito Sugiyama

Maintainer: Mahito Sugiyama <mahito@nii.ac.jp>

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

Connected graphlet kernel

Description

This function calculates a kernel matrix of the graphlet kernel with connected graphlets K_{CGL} between unlabeled graphs.

Usage

CalculateConnectedGraphletKernel(G, par)

Arguments

G

a list of igraph graphs

par

the number k of graphlet nodes (k = 3, 4, or 5 is supported)

Value

a kernel matrix of the connected graphlet kernel K_{CGL}

Author(s)

Mahito Sugiyama

References

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.

Examples

data(mutag)
K <- CalculateConnectedGraphletKernel(mutag, 4)

Gaussian RBF kernel between edge label histograms

Description

This function calculates a kernel matrix of the Gaussian RBF kernel K_{EH,G} between edge label histograms.

Usage

CalculateEdgeHistGaussKernel(G, par)

Arguments

G

a list of igraph graphs

par

\sigma in the Gaussian RBF kernel

Value

a kernel matrix of the Gaussian RBF kernel K_{EH,G} between edge label histograms

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateEdgeHistGaussKernel(mutag, .1)

Linear kernel between edge label histograms

Description

This function calculates a kernel matrix of the linear kernel K_{EH} between edge label histograms.

Usage

CalculateEdgeHistKernel(G)

Arguments

G

a list of igraph graphs

Value

a kernel matrix of the linear kernel K_{EH} between edge label histograms

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateEdgeHistKernel(mutag)

Exponential random walk kernel

Description

This function calculates a kernel matrix of the exponential random walk kernel K_{ER}.

Usage

CalculateExponentialRandomWalkKernel(G, par)

Arguments

G

a list of igraph graphs

par

a coefficient \beta, with which the weight \lambda_k for each step k is given as \lambda_k = \beta^k / k!

Value

a kernel matrix of the exponential random walk kernel K_{ER}

Author(s)

Mahito Sugiyama

References

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.

Examples

data(mutag)
K <- CalculateExponentialRandomWalkKernel(mutag[1:5], .1)

Geometric random walk kernel

Description

This function calculates a kernel matrix of the geometric random walk kernel K_{GR}.

Usage

CalculateGeometricRandomWalkKernel(G, par)

Arguments

G

a list of igraph graphs

par

a coefficient \lambda, with which the weight \lambda_k for each step k is given as \lambda_k = \lambda^k

Value

a kernel matrix of the geometric random walk kernel K_{GR}

Author(s)

Mahito Sugiyama

References

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.

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)
K <- CalculateGeometricRandomWalkKernel(mutag, .1)

Graphlet kernel

Description

This function calculates a kernel matrix of the graphlet kernel K_{GL} between unlabeled graphs.

Usage

CalculateGraphletKernel(G, par)

Arguments

G

a list of igraph graphs

par

the number k of graphlet nodes (k = 3 or 4 is supported)

Value

a kernel matrix of the graphlet kernel K_{GL}

Author(s)

Mahito Sugiyama

References

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.

Examples

data(mutag)
K <- CalculateGraphletKernel(mutag, 4)

An C++ implementation of graphlet kernels

Description

This function calculates a graphlet kernel matrix.

Usage

CalculateGraphletKernelCpp(graph_adj_all, graph_adjlist_all, k, connected)

Arguments

graph_adj_all

a list of adjacency matrices

graph_adjlist_all

a list of adjacency lists

k

the number k of graphlet nodes

connected

whether or not graphlets are conneceted

Value

a kernel matrix of the respective graphlet kernel

Author(s)

Mahito Sugiyama

References

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.

Examples

data(mutag)
al.list <- as.list(rep(NA, length(mutag)))
for (i in 1:length(mutag)) { al.list[[i]] <- as_adj_list(mutag[[i]]) }
K <- CalculateGraphletKernelCpp(list(), al.list, 4, 0)

k-step random walk kernel

Description

This function calculates a kernel matrix of the k-step random walk kernel K_{\times}^{k}.

Usage

CalculateKStepRandomWalkKernel(G, par)

Arguments

G

a list of igraph graphs

par

a vector of coefficients \lambda_0, \lambda_1, \dots, \lambda_k

Value

a kernel matrix of the k-step random walk kernel K_{\times}^{k}

Author(s)

Mahito Sugiyama

References

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.

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)
K <- CalculateKStepRandomWalkKernel(mutag, rep(1, 2))

An C++ implementation of graph kernels

Description

This function calculates a kernel matrix.

Usage

CalculateKernelCpp(graph_info_list, par_r, kernel_type)

Arguments

graph_info_list

a list of igraph graphs

par_r

parameters of kernels

kernel_type

type of kernel

Value

a kernel matrix of the respective kernel

Author(s)

Mahito Sugiyama

References

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)
graph.info.list <- vector("list", length(mutag))
for (i in 1:length(mutag)) { graph.info.list[[i]] <- GetGraphInfo(mutag[[i]]) }
K <- CalculateKernelCpp(graph.info.list, 5, 11)

Shortest-path kernel

Description

This function calculates a kernel matrix of the shortest-path kernel K_{SP}.

Usage

CalculateShortestPathKernel(G)

Arguments

G

a list of igraph graphs

Value

a kernel matrix of the shortest-path kernel K_{SP}

Author(s)

Mahito Sugiyama

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/.

Examples

data(mutag)
K <- CalculateShortestPathKernel(mutag)

Gaussian RBF kernel between vertex-edge label histograms

Description

This function calculates a kernel matrix of the Gaussian RBF kernel K_{VEH,G} between vertex-edge label histograms.

Usage

CalculateVertexEdgeHistGaussKernel(G, par)

Arguments

G

a list of igraph graphs

par

\sigma in the Gaussian RBF kernel

Value

a kernel matrix of the Gaussian RBF kernel K_{VEH,G} between vertex-edge label histograms

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateVertexEdgeHistGaussKernel(mutag, .1)

Linear kernel between vertex-edge label histograms

Description

This function calculates a kernel matrix of the linear kernel K_{VEH} between vertex-edge label histograms.

Usage

CalculateVertexEdgeHistKernel(G)

Arguments

G

a list of igraph graphs

Value

a kernel matrix of the linear kernel K_{VEH} between vertex-edge label histograms

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateVertexEdgeHistKernel(mutag)

Gaussian RBF kernel between vertex label histograms

Description

This function calculates a kernel matrix of the Gaussian RBF kernel K_{VH,G} between vertex label histograms.

Usage

CalculateVertexHistGaussKernel(G, par)

Arguments

G

a list of igraph graphs

par

\sigma in the Gaussian RBF kernel

Value

a kernel matrix of the Gaussian RBF kernel K_{VH,G} between vertex label histograms

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateVertexHistGaussKernel(mutag, .1)

Linear kernel between vertex label histograms

Description

This function calculates a kernel matrix of the linear kernel K_{VH} between vertex label histograms.

Usage

CalculateVertexHistKernel(G)

Arguments

G

a list of igraph graphs

Value

a kernel matrix of the linear kernel K_{VH} between vertex label histograms

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateVertexHistKernel(mutag)

Linear kernel combination of vertex label histograms and vertex-edge label histograms

Description

This function calculates a kernel matrix of the linear kernel combination K_{H} of vertex label histograms K_{VH} and vertex-edge label histograms K_{VEH}.

Usage

CalculateVertexVertexEdgeHistKernel(G, par)

Arguments

G

a list of igraph graphs

par

a coefficient \lambda, with which the resulting kernel is given as K_{VH} + \lambda K_{VEH}

Value

a kernel matrix that is equivalent to K_{VH} + \lambda K_{VEH}

Author(s)

Mahito Sugiyama

References

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)
K <- CalculateVertexVertexEdgeHistKernel(mutag, .1)

Weisfeiler-Lehman subtree kernel

Description

This function calculates a kernel matrix of the Weisfeiler-Lehman subtree kernel K_{WL}.

Usage

CalculateWLKernel(G, par)

Arguments

G

a list of igraph graphs

par

the number h of iterations

Value

a kernel matrix of the Weisfeiler-Lehman subtree kernel K_{WL}

Author(s)

Mahito Sugiyama

References

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.

Examples

data(mutag)
K <- CalculateWLKernel(mutag, 5)

Necessary information of graphs for kernel computation

Description

This function extracts necessary information of graphs for kernel computation.

Usage

GetGraphInfo(g)

Arguments

g

an igraph graph

Value

a list of graph information with the following elements:

edge

a matrix of edges with their labels

vlabel

a vector of vertex labels

vsize

the number of vertices

esize

the number of edges

maxdegree

the maximum degree

Author(s)

Mahito Sugiyama

Examples

data(mutag)
ginfo <- GetGraphInfo(mutag[[1]])

Symbol registration

Description

This is a supplement for symbol registration.

Author(s)

Mahito Sugiyama

Symbol registration

Description

This is a supplement for symbol registration.

Author(s)

Mahito Sugiyama

The mutag dataset

Description

This is the mutag dataset, a well known benchmark dataset for graph processing algorithms.

Usage

data(mutag)

Author(s)

Mahito Sugiyama

References

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.

Examples

data(mutag)
K <- CalculateWLKernel(mutag, 5)