User:Creolesleepr/Graph Kernels

This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see Wikipedia:So you made a userspace draft.

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL
Easy tools: Citation bot (help) | Advanced: Fix bare URLs
This page was last edited by Cydebot (talk | contribs) 5 years ago. (Update timer)

Finished writing a draft article? Are you ready to request an experienced editor review it for possible inclusion in Wikipedia? Submit your draft for review!

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

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

Weisfeiler-Lehman Graph Kernels

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

^ 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
^ 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.
^ P. Mahe and J.-P. Vert. Graph kernels based on tree patterns for molecules. Machine Learning, 75(1):3–35, 2009.
^ Weisfeiler-Lehman Graph Kernels, Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, Karsten M. Borgwardt; JMLR, 12(Sep):2539−2561, 2011.

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

[1]

[2]

[3]

[4]