March 12, 2017

Kernels on Graphs

They are DirectKernels operating on DirectedGraphRepresentions.


Shortest Path Kernel

Java class: ShortestPathKernel

Source code: ShortestPathKernel.java

Maven Project: kelp-additional-kernels

JSON type: shortestPath

Description: it associates a feature to each pair of nodes of one graph. The feature name corresponds to pair of node labels while the value is the length of the shortest path between the nodes in the graph. Further details can be found in (Borgwardt and Kriegel, 2005).

Parameters:

  • representation: the String identifying the representation on which the kernel must operate

Weisfeiler–Lehman Subtree Kernel

Java class: WLSubtreeMapper to manipulate the dataset instances and obtain the explicit vectors to be used by a LinearKernel

Maven Project: kelp-additional-kernels

Description: it is actually an explicit feature extractor that outputs vectors containing the features of the WeisfeilerLehman Subtree Kernel for Graphs (Shervashidze, 2011). A LinearKernel can be used to exploit the produced vectors.


References

K. M. Borgwardt and H.P. Kriegel. ShortestPath Kernels on Graphs. in Proceedings of the Fifth IEEE International Conference on Data Mining, 2005, pp. 74–81.

N. Shervashidze, Weisfeilerlehman graph kernels, JMLR, vol. 12, pp. 2539–2561, 2011