Jump to content

User:Creolesleepr/Graph Kernels

From Wikipedia, the free encyclopedia

Graph Kernels are used in machine learning algorithms that can employ the kernel trick. Often, we wish to perform classification tasks on graph structured data, such as social networks, program flows, and gene regulation networks. Classifiers such as the support vector machine are general-purpose: they can be used on any data structures as long as there is a kernel function to measure distance between points encoded in the data structure. Thus, graph kernels are functions that take two graphs as input and output a "distance" between the two graphs, making it possible to tell when graphs have similar structures.

Types of Graph Kernels

[edit]
  1. Graph Kernels based on walks [1]
  2. Graph Kernels based on limited-size subgraphs [2]
  3. Graph kernels based on subtree patterns [3]


Weisfeiler-Lehman Graph Kernels

[edit]

Based on the Weisfeiler-Lehman isomorphism test of graphs, Weisfeiler-Lehman graph kernels can accept graphs with discrete node labels as input[4]. These kernels have linear runtime in the number of edges in the graph and the length of the Weisfeiler-Lehman sequence. The 1-dimensional Weisfeiler-Lehman algorithm, used by this graph kernel, iteratively refines the node labels of two input graphs, G and G'. Eventually, the label set of G and G' will differ, or the algorithm will terminate, having assigned each node in G and G' a unique label. This labeling gives a straightforward isomorphism between G and G', or a pointer to where the two graphs differ, or the algorithm is sometimes unable to determine that the two graphs are non-isomorphic, though it will successfully discern if almost all graphs are isomorphic or not.

The labels that the Weisfeiler-Lehman algorithm generates correspond to subtrees rooted at each labeled node. Essentially, we define the kernel on G and G' by counting how many times the Weisfeiler-Lehman successfully completes an iteration when run on these two graphs. In practice, this can be computed efficiently, because the Weisfeiler-Lehman isomorphism test runs in linear time in the size of the graph, and by cleverly arranging the subtrees defined by the algorithm, the paper can compute the kernel on N graphs simultaneously in linear time.

References

[edit]
  1. ^ T.Gartner, P.A.Flach and S. Worbel. On Graph kernels: Hardness results and efficient alternatives. In Proceedings of the Annual Conference on Computational Learning Theory, pages 225-232, Bonn, Germany, 2005
  2. ^ N. Shervashidze and K. M. Borgwardt. Fast subtree kernels on graphs. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Proceedings of the Conference on Advances in Neural Information Processing Systems, pages 1660–1668, 2009.
  3. ^ P. Mahe and J.-P. Vert. Graph kernels based on tree patterns for molecules. Machine Learning, 75(1):3–35, 2009.
  4. ^ Weisfeiler-Lehman Graph Kernels, Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, Karsten M. Borgwardt; JMLR, 12(Sep):2539−2561, 2011.