This folder contains Matlab scripts for computing several graph kernels for graphs with unlabeled or
categorically labeled nodes and scripts for evaluating the SVM classification performance using
precomputed kernels using cross-validation.
The folder "unlabeled" contains
- a README
- the family of graphlet kernels (subfolders allgraphlets, connectedgraphlets, samplinggraphlets) from [6]
- the random walk kernel (RWkernel.m) from [7]
- the shortest path kernel (SPkernel.m) from [1]
for unlabeled graphs.
The folder "labeled" contains
- a README
- 3 kernels from the Weisfeiler-Lehman kernel family: the WL subtree (WL.m), the WL shortest path (WLspdelta.m),
and the WL edge (WLedge.m) kernels from [5]
- the labeled 3-node graphlet kernel (l3graphletkernel.m) - extension of an algorithm in [6]
- the labeled random walk kernel (lRWkernel.m) from [7]
- the labeled random walk kernel based on walks up to size p (untilpRWkernel.m) - extension of [2],[3]
- the labeled shortest path kernel (spkernel.m) from [1]
- the Ramon and Gaertner subtree kernel (RGkernel.m) from [4]
for graphs with categorically labeled nodes. Note that all WL kernels in this folder also support unlabeled
graphs.
"help X.m" executed in Matlab will display instructions on the usage of X.m for any script X.m
MUTAG is an example graph data set in the required format for all scripts above.
The folder "svm" contains scripts for evaluating the classification performance of SVM with precomputed kernels
using cross-validation. It also contains a separate README. You need to install libSVM and its Matlab interface
to be able to use scripts in this folder.
References
[1] K. M. Borgwardt and H.-P. Kriegel.
Shortest-path kernels on graphs. In Proceedings of the International Conference on Data Mining,
pages 74-81, 2005.
[2] T. Gaertner, P. A. Flach, and S. Wrobel.
On graph kernels: Hardness results and efficient alternatives. In Proceedings of the 16th Annual
Conference on Computational Learning Theory and 7th Kernel Workshop, pages 129-143.
ISBN 3-540-40720-0.
[3] H. Kashima, K. Tsuda, and A. Inokuchi.
Marginalized kernels between labeled graphs. In Proceedings of the 20th International Conference
on Machine Learning, Washington, DC, United States, 2003.
[4] J. Ramon and T. Gaertner.
Expressivity versus efficiency of graph kernels. In First International Workshop on Mining Graphs,
Trees and Sequences (held with ECML/PKDD'03), 2003.
[5] N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhorn, and K. M. Borgwardt.
Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12:2539-2561, 2011.
[6] N. Shervashidze, S. V. N. Vishwanathan, T. Petri, K. Mehlhorn, and K. M. Borgwardt.
Efficient graphlet kernels for large graph comparison. In Proceedings of the International
Conference on Artificial Intelligence and Statistics, 2009.
[7] S. V. N. Vishwanathan, N. N. Schraudolph, I. R. Kondor, and K. M. Borgwardt.
Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.