nips nips2009 nips2009-95 nips2009-95-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nino Shervashidze, Karsten M. Borgwardt
Abstract: In this article, we propose fast subtree kernels on graphs. On graphs with n nodes and m edges and maximum degree d, these kernels comparing subtrees of height h can be computed in O(mh), whereas the classic subtree kernel by Ramon & G¨ rtner scales as O(n2 4d h). Key to this efficiency is the observation that the a Weisfeiler-Lehman test of isomorphism from graph theory elegantly computes a subtree kernel as a byproduct. Our fast subtree kernels can deal with labeled graphs, scale up easily to large graphs and outperform state-of-the-art graph kernels on several classification benchmark datasets in terms of accuracy and runtime. 1
[1] F. R. Bach. Graph kernels between point clouds. In ICML, pages 25–32, 2008.
[2] K. M. Borgwardt and H.-P. Kriegel. Shortest-path kernels on graphs. In Proc. Intl. Conf. Data Mining, pages 74–81, 2005.
[3] A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. J Med Chem, 34:786–797, 1991.
[4] P. D. Dobson and A. J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. J Mol Biol, 330(4):771–783, Jul 2003.
[5] T. G¨ rtner, P.A. Flach, and S. Wrobel. On graph kernels: Hardness results and efficient altera natives. In B. Sch¨ lkopf and M. Warmuth, editors, Sixteenth Annual Conference on Computao tional Learning Theory and Seventh Kernel Workshop, COLT. Springer, 2003.
[6] T. Horvath, T. G¨ rtner, and S. Wrobel. Cyclic pattern kernels for predictive graph mining. In a Proceedings of the International Conference on Knowledge Discovery and Data Mining, 2004.
[7] H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th International Conference on Machine Learning (ICML), Washington, DC, United States, 2003.
[8] P. Mah´ , N. Ueda, T. Akutsu, J.-L. Perret, and J.-P. Vert. Extensions of marginalized graph e kernels. In Proceedings of the Twenty-First International Conference on Machine Learning, 2004.
[9] P. Mah´ and J.-P. Vert. Graph kernels based on tree patterns for molecules. q-bio/0609024, e September 2006.
[10] J. Ramon and T. G¨ rtner. Expressivity versus efficiency of graph kernels. Technical report, First a International Workshop on Mining Graphs, Trees and Sequences (held with ECML/PKDD’03), 2003.
[11] N. Shervashidze, S.V.N. Vishwanathan, T. Petri, K. Mehlhorn, and K. M. Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, 2009.
[12] S. V. N. Vishwanathan, Karsten Borgwardt, and Nicol N. Schraudolph. Fast computation of graph kernels. In B. Sch¨ lkopf, J. Platt, and T. Hofmann, editors, Advances in Neural o Information Processing Systems 19, Cambridge MA, 2007. MIT Press.
[13] N. Wale and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Proc. of ICDM, pages 678–689, Hong Kong, 2006.
[14] B. Weisfeiler and A. A. Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, Ser. 2, 9, 1968. 9