| 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:
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 kernelthe 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 <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 |
par |
the number |
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 |
par |
|
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 |
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 |
par |
a coefficient |
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 |
par |
a coefficient |
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 |
par |
the number |
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 |
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 |
par |
a vector of coefficients |
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 |
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 |
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 |
par |
|
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 |
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 |
par |
|
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 |
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 |
par |
a coefficient |
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 |
par |
the number |
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 |
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)