References

1. K. Borgwardt, Graph Kernels, PhD thesis, Faculty for Mathematics, Informatics and Statistics, Ludwig-Maximilians-University Munich, Germany, 2007.

2. D. Bonchev, D. Rouvray, Chemical Graph Theory. Introduction and Fundamentals, Taylor & Francis, London, 1991.

3. J. Gasteiger, T. Engel, Chemoinformatics, Wiley-VCH, Weinheim, 2003.

4. R. Sharan, T. Ideker, Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24(4), 427–433 (2006).

5. S. Wasserman, K. Faust, Social network analysis, in Structural Analysis in the Social Sciences, Vol. 8, Cambridge University Press, 1995.

6. R. Kumar, J. Novak, A. Tomkins, Structure and evolution of online social networks, in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2006), Philadelphia, USA, August 20–23, pp. 611–617, 2006.

7. Z. Harchaoui, F. Bach, Image classification with segmentation graph kernels, in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007), Minneapolis, Minnesota, USA, June 18–23, IEEE Computer Society, 2007.

8. M. Collins, N. Duffy, Convolution kernels for natural language, in (T. Dietterich, S. Becker, Z. Ghahramani, eds.), Advances in Neural Information Processing Systems 14 (NIPS 2001), Vancouver, British Columbia, Canada, December 8–3, MIT Press, pp. 625–632, 2002.

9. F. Emmert-Streib, M. Dehmer, Networks for systems biology: conceptual connection of data and function, IET Syst. Biol. 5(3), 185–207 (2011).

10. R.C. Read, D.G. Corneil, The graph isomorphism disease. J. Graph Theor. 1(4), 339–363 (1977).

11. J.R. Ullman, An algorithm for subgraph isomorphism. J. Assoc. Comput. Mach. 23(1), 31–42 (1976).

12. B. Zelinka, On a certain distance between isomorphism classes of graphs. asopis pro Pstování Matematiky 100(4), 371–373 (1975).

13. M.-L. Fernández, Gabriel Valiente, A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recogn. Lett. 22(6–7) (2001).

14. M. Neuhaus, H. Bunke, Edit distance-based kernel functions for structural pattern classification. Pattern Recogn. 39(10), 1852–1863 (2006).

15. L.G. Shapiro, Organization of relational models, in Proceedings of the 6th International Conference on Pattern Recognition (ICPR 1982), Munich, Germany, October 19–22, pp. 360–365, 1982.

16. D. Gernert, Measuring the similarity of complex structures by means of graph grammars, Bull. Eur. Assoc. Theor. Comput. Sci. 7, 3–9 (1979).

17. T. Hofmann, B. Schölkopf, A. Smola, A review of kernel methods in machine learning, Technical Report 156, Max-Planck-Institute for Biological Cybernetics, 2006.

18. K.-R. Müller, S. Mika, G. Rätsch, K. Tsuda, B. Schölkopf, An introduction to kernel-based learning algorithms. IEEE Trans. Neural Netw. 12(2), 181–201 (2001).

19. B. Schölkopf, A. Smola, Learning with Kernels, MIT Press, Cambridge, 2002.

20. J. Shawe-Taylor, Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, 1st edn., 2004.

21. R. Kondor, J. Lafferty, Diffusion kernels on graphs and other discrete structures, in (C. Sammut, A. Hoffmann, eds.), Proceedings of the 19th International Conference on Machine Learning (ICML 2002), Sydney, Australia, July 8–12, Morgan Kaufmann, pp. 315–322, 2002.

22. R. Kondor, J.-P. Vert, Diffusion kernels, in (B. Schölkopf, K. Tsuda, J.-P. Vert, eds.), Kernel Methods in Computational Biology, MIT Press, Cambridge, pp. 171–191, 2004.

23. A. Smola, R. Kondor, Kernels and regularization on graphs, in (B. Schölkopf, M. Warmuth, eds.), Learning Theory and Kernel Machines: Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT / Kernel 2003), Washington DC, USA, August 24–27, Vol. 2777, Lecture Notes in Computer Science, Springer, pp. 144–158, 2003.

24. J. Kandola, J. Shawe-Taylor, N. Cristianini, Learning semantic similarity, in (S. Becker, S. Thrun, K. Obermayer, eds.), Advances in Neural Information Processing Systems 15 (NIPS 2002), Cambridge, Massachusetts, USA, December 10–12, MIT Press, pp. 657–664, 2003.

25. T. Jaakkola, M. Diekhans, D. Haussler, A discriminative framework for detecting remote protein homologies. J. Comput. Bio. 7(1–2), 95–114 (2000).

26. K. Tsuda, M. Kawanabe, G. Rätsch, S. Sonnenburg, K.-R. Müller, A new discriminative kernel from probabilistic models. Neural Comput. 14(10), 2397–2414 (2002).

27. K. Tsuda, T. Kin, K. Asai, Marginalized kernels for biological sequences. Bioinformatics 18(7), S268–S275 (2002).

28. H. Kashima, K. Tsuda, A. Inokuchi, Kernels for graphs, in (B. Schölkopf, K. Tsuda, J.-P. Vert, eds.), Kernel Methods in Computational Biology, MIT Press, Cambridge, pp. 155–170, 2004.

29. H. Kashima, K. Tsuda, A. Inokuchi, Marginalized kernels between labeled graphs, in (T. Fawcett, N. Mishra, eds.), Proceedings of the 20th International Conference on Machine Learning (ICML 2003), Washington DC, USA, August 21–24, Menlo Park, CA, AAAI Press, pp. 321–328, 2003.

30. P. Mahé, N. Ueda, T. Akutsu, J.-L. Perret, J.-P. Vert, Extensions of marginalized graph kernels, in (C. Brodley, ed.), Proceedings of the 21st International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canada, July 4–8, Omnipress, Madison, WI, USA, pp. 552–559, 2004.

31. T. Horváth, T. Gärtner, S. Wrobel, Cyclic pattern kernels for predictive graph mining, in (R. Kohavi, J. Gehrke, W. DuMouchel, J. Ghosh, eds.), Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2004), Seattle, Washington, USA, August 22–25, ACM Press, pp. 158–167, 2004.

32. T. Horváth, Cyclic pattern kernels revisited, in (J. Carbonell, J. Siekmann, eds.), Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2005), Hanoi, Vietnam, May 18–20, Vol. 3518, Lecture Notes in Computer Science, Springer, pp. 791–801, 2005.

33. K. Borgwardt, H.-P. Kriegel, Shortest-path kernels on graphs, in Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), Houston, Texas, USA, November 27–30, IEEE Computer Society, pp. 74–81, 2005.

34. H. Fröhlich, J. Wegner, F. Sieker, A. Zell, Optimal assignment kernels for attributed molecular graphs, in (L. de Raedt, S. Wrobel, eds.), Proceedings of the 22nd International Conference on Machine Learning (ICML 2005), Bonn, Germany, August 7–11, Madison, WI, USA, pp. 225–232, Omnipress, 2005.

35. H. Fröhlich, J. Wegner, A. Zell, Assignment kernels for chemical compounds, in Proceedings of the 2005 International Joint Conference on Neural Networks (IJCNN 2005), Montréal, Canada, July 31–August 4, IEEE Computer Society, pp. 913–918, 2005.

36. H. Fröhlich, J. Wegner, F. Sieker, A. Zell, Kernel functions for attributed molecular graphs: a new similarity-based approach to ADME prediction in classification and regression, QSAR Comb. Sci. 25(4), 317–326 (2006).

37. M. Rupp, E. Proschak, G. Schneider, Kernel approach to molecular similarity based on iterative graph similarity. J. Chem. Inform. Model. 47(6), 2280–2286 (2007).

38. J.-P. Vert, The optimal assignment kernel is not positive definite, Technical Report HAL-00218278, Centre for Computational Biology, Mines ParisTech, Paris, France, 2008.

39. N. Fechner, A. Jahn, G. Hinselmann, A. Zell, Atomic local neighborhood flexibility incorporation into a structured similarity measure for QSAR, J. Chem. Inform. Model. 49(3), 549–560 (2009).

40. A. Jahn, G. Hinselmann, N. Fechner, A. Zell, Optimal assignment methods for ligand-based virtual screening, J. Cheminform. 1(14) (2009).

41. M. Rupp, Kernel Methods for Virtual Screening, PhD thesis, Johann Wolfgang Goethe-University, Frankfurt am Main, Germany, 2009.

42. L. Ralaivola, S. Swamidass, H. Saigo, P. Baldi, Graph kernels for chemical informatics. Neural Netw. 18(8), 1093–1110 (2005).

43. J. Swamidass, J. Chen, J. Bruand, P. Phung, L. Ralaivola, P. Baldi, Kernels for small molecules and the prediction of mutagenicity, toxicity and anti-cancer activity. Bioinformatics 21(Suppl. 1), i359–i368 (2005).

44. S. Menchetti, F. Costa, P. Frasconi, Weighted decomposition kernels, in (L. de Raedt, S. Wrobel, eds.), Proceedings of the 22nd International Conference on Machine Learning (ICML 2005), Bonn, Germany, August 7–11, Omnipress, Madison, WI, USA, pp. 585–592, 2005.

45. A. Ceroni, F. Costa, P. Frasconi, Classification of small molecules by two-and three-dimensional decomposition kernels. Bioinformatics 23(16), 2038–2045 (2007).

46. A. Wonica, A. Kalousis, M. Hilario, Matching based kernels for labeled graphs, in (T. Gärtner, G. Garriga Thorsten Meinl, eds.), Proceedings of the International Workshop on Mining and Learning with Graphs (MLG 2006), Berlin, Germany, September 18, pp. 97–108, 2006.

47. A. Smalter, J. Huan, G. Lushington, GPM: a graph pattern matching kernel with diffusion for chemical compound classification, in Proceedings of the 8th IEEE International Conference on Bioinformatics and Bioengineering (BIBE 2008), Athens, Greece, October 8–10, IEEE Computer Society, 2008.

48. A. Smalter, J. Huan, G. Lushington, Chemical compound classification with automatically mined structure patterns, in (A. Brazma, S. Miyano, T. Akutsu, eds.), Proceedings of the 6th Asia-Pacific Bioinformatics Conference (APBC 2008), Kyoto, Japan, January 14–17, Imperial College Press, pp. 39–48, 2008.

49. K. Borgwardt, H.-P. Kriegel, V. Vishwanathan, N. Schraudolph, Graph kernels for disease outcome prediction from protein–protein interaction networks, in (R. Altman, K. Dunker, L. Hunter, T. Murray, T. Klein, eds.), Proceedings of the 12th Pacific Symposium on Biocomputing (PSB 2007), Maui, Hawaii, USA, January 3–7, pp. 4–15, 2007.

50. F.R. Bach, Graph kernels between point clouds, in (A. McCallum, S. Roweis, eds.), Proceedings of the 25th International Conference on Machine Learning (ICML 2008), Helsinki, Finland, July 5–9, Omnipress, pp. 25–32, 2008.

51. R. Kondor, K.M. Borgwardt, The skew spectrum of graphs, in (A. McCallum, S. Roweis, eds.), Proceedings of the 25th International Conference on Machine Learning (ICML 2008), Helsinki, Finland, July 5–9, Omnipress, pp. 496–503, 2008.

52. N. Shervashidze, V. Vishwanathan, T. Petri, K. Mehlhorn, K. Borgwardt, Efficient graphlet kernels for large graph comparison, in (D. van Dyk, M. Welling, eds.), Proceedings of the 12th International Workshop on Artificial Intelligence and Statistics (AISTATS 2009), Clearwater Beach, Florida, USA, April 16–18, pp. 488–495, 2009.

53. R. Kondor, N. Shervashidze, K.M. Borgwardt, The graphlet spectrum, in (L. Bottou, M. Littman, eds.), Proceedings of the 26th International Conference on Machine Learning (ICML 2009), Montreal, Quebec, Canada, June 14–18, Omnipress, pp. 529–536, 2009.

54. A. Demco, Graph Kernel Extensions and Experiments with Application to Molecule Classification, Lead Hopping and Multiple Targets. PhD thesis, School of Electronics and Computer Science, University of Southampton, England, 2009.

55. P. Mahé, J.-P. Vert, Graph kernels based on tree patterns for molecules. Mach. Learn. 75(1), 3–35 (2009).

56. N. Shervashidze, K. Borgwardt, Fast subtree kernels on graphs, in (Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, A. Culotta, eds.), Advances in Neural Information Processing Systems 22 (NIPS 2009), Vancouver, Canada, December 7–12, MIT Press, pp. 1660–1668, 2009.

57. S. Hido, H. Kashima, A linear-time graph kernel, in Proceedings of the 9th IEEE International Conference on Data Mining (ICDM 2009), Miami, Florida, USA, December 6–9, IEEE Computer Society, 2009.

58. T. Gärtner, P. Flach, S. Wrobel, On graph kernels: hardness results and efficient alternatives, in Learning Theory and Kernel Machines (B. Schölkopf, M. Warmuth, eds.), Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT / Kernel 2003), Washington DC, USA, August 24–27, Vol. 2777, Lecture Notes in Computer Science, Springer, pp. 129–143, 2003.

59. D. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms 2(4), 393–405 (1981).

60. D. Johnson, The NP-completeness column. ACM Trans. Algorithms 1(1), 160–176 (2005).

61. D. Johnson, The NP-completeness column: an ongoing guide. J. Algorithms 5(1), 147–160 (1984).

62. D. Haussler, Convolution kernels on discrete structures, Technical Report UCSC-CRL-99-10, Department of Computer Science, University of California at Santa Cruz, California, USA, 1999.

63. C. Watkins, Dynamic alignment kernels, Technical Report CSD-TR-98-11, Royal Holloway, London, England, 1999.

64. V. Vishwanathan, N. Schraudolph, R. Kondor, K. Borgwardt, Graph kernels. J. Mach. Learn. Res. 11(4), 1201–1242 (2010).

65. T. Gärtner, Exponential and geometric kernels for graphs, in Neural Information Processing Systems (NIPS) Workshop on Unreal Data: Principles of Modeling Nonvectorial Data, 2002.

66. T. Gärtner, A survey of kernels for structured data. ACM SIG Knowledge Discov. Data Mining Explorations Newsletter 5(1), 49–58 (2003).

67. P. Mahé, N. Ueda, T. Akutsu, J.-L. Perret, J.-P. Vert, Graph kernels for molecular structure–activity relationship analysis with support vector machines. J. Chem. Inform. Model. 45(4), 939–951 (2005).

68. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edn., MIT Press, Cambridge, 2009.

69. J.Y. Yen, Finding the k shortest loopless paths in a network. Manag. Sci. 17(11), 712–716 (1971).

70. E.L. Lawler, A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manag. Sci. 18(7), 401–405 (1972).

71. B. Weisfeiler, A.A. Lehman, A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauch.-Techn. Inform. 2(9), 12–16 (1968).

72. M. Zaki, Efficiently mining frequent trees in a forest: algorithms and applications. IEEE Trans. Knowledge Data Eng. 17(8), 1021–1035 (2005).

73. J. Flum, M. Grohe, The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892–922 (2004).

74. H. Bodlaender, A tourist guide through treewidth. Acta Cybernetica 11(1–2), 1–21 (1993).

75. M. Plotkin, Mathematical basis of of ring-finding algorithms in CIDS. J. Chem. Doc. 11(1), 60–63 (1971).

76. P. Gleiss, P. Stadler, Relevant cycles in biopolymers and random graphs, in Proceedings of the 4th Slovene International Conference in Graph Theory, Lake Bled, Slovenia, June 28–July 2, 1999.

77. B.D. McKay, Small graphs are reconstructible. Austral. J. Combin. 15, 123–126 (1997).

78. B. Bollobás, Almost every graph has reconstruction number three. J. Graph Theor. 14(1), 1–4 (1990).

79. R. Kakarala, A group-theoretic approach to the triple correlation, in Proceedings of the IEEE Signal Processing Workshop on Higher-Order Statistics (SPW-HOS 1993), South Lake Tahoe, California, USA, June 7–9, IEEE, pp. 28–32, 1993.

80. N. Weskamp, E. Hüllermeier, D. Kuhn, G. Klebe, Graph alignments: a new concept to detect conserved regions in protein active sites, in (R. Giegerich, J. Stoye, eds.), Proceedings of the German Conference on Bioinformatics (GCB 2004), Bielefeld, Germany, October 4–6, Gesellschaft für Informatik, pp. 131–140, 2004.

81. J. Berg, M. Lässig, Local graph alignment and motif search in biological networks. Proc. Natl. Acad. Sci. U.S.A. 101(41), 14689–14694 (2004).

82. M. Dehmer, F. Emmert-Streib, J. Kilian, A similarity measure for graphs with low computational complexity. Appl. Math. Comput. 182(1), 447–459 (2006).

83. H. Kuhn, The Hungarian method for the assignment problem, Bull. Am. Math. Soc. 61, 557–558 (1955).

84. J. Munkres, Algorithms for the assignment and transportation problems. J. Soc. Indus. Appl. Math. 5(1), 32–38 (1957).

85. F. Bourgeois, J.-C. Lassalle, An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Commun. ACM 14(12), 802–804 (1971).

86. C. Berg, J. Christensen, P. Ressel, Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions, Springer, 1984.

87. V. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Doklady 10(8), 707–710 (1966).

88. D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, Cambridge, 1997.

89. M. Neuhaus, H. Bunke, An error-tolerant approximate matching algorithm for attributed planar graphs and its application to fingerprint classification, in (A. Fred, T. Caelli, R. Duin, A. Campilho, D. de Ridder, eds.), Proceedings of the 10th Joint IAPR International Workshops on Structural, Syntactic, and Statistical Pattern Recognition (SSPR 2004, SPR 2004), Lisbon, Portugal, August 18–20, Vol. 3138, Lecture Notes in Computer Science, Springer, pp. 180–189, 2004.

90. J. Mohr, B. Jain, K. Obermayer, Molecule kernels: a descriptor-and alignment-free quantitative structure–activity relationship approach. J. Chem. Inform. Model. 48(9), 1868–1881 (2008).

91. D. Douguet, Ligand-based approaches in virtual screening. Curr. Comput.-Aided Drug Design 4(3), 180–190 (2008).

92. C. Selassie, History of quantitative structure–activity relationships, in (D. Abrahams, ed.), Burger's Medicinal Chemistry and Drug Discovery, Wiley, Vol. 1, Chapter 1, pp. 1–48, 6th edn., 2003.

93. M. Rupp, T. Schroeter, R. Steri, H. Zettl, E. Proschak, K. Hansen, O. Rau, O. Schwarz, L. Müller-Kuhrt, M. Schubert-Zsilavecz, K.-R. Müller, G. Schneider, From machine learning to natural product derivatives selectively activating transcription factor PPARγ. ChemMedChem 5(2), 191–194 (2010).

94. T. Gärtner, Q.Viet Le, A. Smola, A short tour of kernel methods for graphs, Technical Report, 2006.

95. T. Gärtner, T. Horváth, Q.Viet Le, A. Smola, S. Wrobel, Kernel methods for graphs, in Mining Graph Data (D. Cook, L. Holder, eds.), Wiley, pp. 253–282, 2007.

96. P. Mahé, J.-P. Vert, Virtual screening with support vector machines and structure kernels, Technical Report HAL-00166188, Ecole des Mines de Paris, Center for Computational Biology, 2007.

97. T. Gärtner, Kernels for Structured Data, Number 72 in Machine Perception and Artificial Intelligence, World Scientific Publishing, 2009.

98. J. Ramon, T. Gärtner, Expressivity versus efficiency of graph kernels, in (L. de Raedt, T. Washio, eds.), Proceedings of the 1st International Workshop on Mining Graphs, Trees and Sequences (MGTS 2003), Cavtat-Dubrovnik, Croatia, September 22–23, pp. 65–74, 2003.

99. V. Vishwanathan, K. Borgwardt, N. Schraudolph, Fast computation of graph kernels, in (B. Schölkopf, J. Platt, T. Hofmann, eds.), Advances in Neural Information Processing Systems 19 (NIPS 2006), Vancouver, Canada, December 4–7, MIT Press, pp. 1449–1456, 2006.

100. K. Borgwardt, C.S. Ong, S. Schönauer, V. Vishwanathan, A. Smola, H.-P. Kriegel, Protein function prediction via graph kernels, in (H.V. Jagadish, D. States, B. Rost, eds.), Proceedings of the 13th International Conference on Intelligent Systems for Molecular Biology (ISMB 2005), Detroit, USA, June 25–29, Vol. 21 (Suppl. 1) Bioinformatics, Oxford, pp. i47–i56, 2005.

101. A. Airola, S. Pyysalo, J. Björne, T. Pahikkala, F. Ginter, T. Salakoski, A graph kernel for protein–protein interaction extraction, in (D. Demner-Fushman, S. Ananiadou, B. Cohen, J. Pestian, J. Tsujii, B. Webber, eds.), Proceedings of the ACL-08 / HLT Workshop on Current Trends in Biomedical Natural Language Processing (BioNLP 2008), Columbus, Ohio, USA, June 19, Association for Computational Linguistics, pp. 1–9, 2008.

102. T. Fober, M. Mernberger, V. Melnikov, R. Moritz, E. Hüllermeier, Extension and empirical comparison of graph-kernels for the analysis of protein active sites, in (M. Hartmann, F. Janssen, eds.), Joint Workshop on Lernen, Wissen, Adaptivität (LWA 2009), Darmstadt, Germany, September 21–23, Technical University of Darmstadt, pp. 30–36, 2009.

103. F. Towfic, M. Heather West Greenlee, V. Honavar, Aligning biomolecular networks using modular graph kernels, in S.L. Salzberg, T. Warnow, eds.), Proceedings of the 9th International Workshop on Algorithms in Bioinformatics (WABI 2009), Philadelphia, Pennsylvania, USA, September 12–13, Vol. 5724, Lecture Notes in Bioinformatics, pp. 345–361, 2009.

104. V. Vapnik, The Nature of Statistical Learning Theory, 1st edn., Springer, New York, 1995.

105. E. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42–65 (1982).

106. H. Wiener, Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69(1), 17–20 (1947).

107. S. Sonnenburg, G. Rätsch, C. Schäfer, B. Schölkopf, Large scale multiple kernel learning. J. Mach. Learn. Res. 7(7), 1531–1565 (2006).