Edge distance graph kernel and its application to small molecule classification

Graph classification is an important problem in graph mining with various applications in different fields. Kernel methods have been successfully applied to this problem, recently producing promising results. A graph kernel that mostly specifies classification performance has to be defined in order to apply kernel methods to a graph classification problem. Although there are various previously proposed graph kernels, the problem is still worth investigating, as the available kernels are far from perfect. In this paper, we propose a new graph kernel based on a recently proposed concept called edge distance-k graphs. These new graphs are derived from the original graph and have the potential to be used as novel graph descriptors. We propose a method to convert these graphs into a multiset of strings that is further used to compute a kernel for graphs. The proposed graph kernel is then evaluated on various data sets in comparison to a recently proposed group of graph kernels. The results are promising, both in terms of performance and computational requirements

PDF

___

[1] Swamidass SJ, Chen JH, Bruand J, Phung P, Ralaivola L, Baldi P. Kernels for small molecules and the prediction of mutagenicity, toxicity and anti-cancer activity. Bioinformatics 2005; 21: 359-368.
[2] Vujoˇsevi´c-Janiˇci´c M, Nikoli´c M, Toˇsi´c D, Kuncak V. Software verification and graph similarity for automated evaluation of students assignments. Inform Software Tech 2013; 55: 1004-1016.
[3] Henderson K, Gallagher B, Li L, Akoglu L, Eliassi-Rad T, Tong H, Faloutsos C. Its who you know: graph mining using recursive structural features. In: SIGKDD 2011 International Conference on Knowledge Discovery and Data Mining; 2124 August 2011; San Diego, CA, USA. New York, NY, USA: ACM. pp. 663-671.
[4] Sch¨olkopf B, Smola AJ. Learning With Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Cambridge, MA, USA: MIT Press, 2002.
[5] Vishwanatan SVN, Schraudolph NN, Kondor R, Borgwardt KM. Graph kernels. J Mach Learn Res 2010; 11: 1201- 1242.
[6] Yang X, Tschaplinski TJ, Hurst GB, Jawdy S, Abraham PE, Lankford PK, Adams RM, Shah MB, Hettich RL, Lindquist E et al. Discovery and annotation of small proteins using genomics, proteomics, and computational approaches. Genome Res 2011; 21: 634-641.
[7] Czech W. Invariants of distance k-graphs for graph embedding. Pattern Recogn Lett 2012; 33: 1968-1979.
[8] G¨artner T, Flach P, Wrobel S. On graph kernels: hardness results and efficient alternatives. In: Sch¨olkopf B, Warmuth MK, editors. Learning Theory and Kernel Machines. Berlin, Germany: Springer-Verlag, 2003. pp. 129- 143.
[9] Kashima H, Tsuda K, Inokuchi A. Marginalized kernels between labeled graphs. In: AAAI 2003 International Conference on Machine Learning; 2124 August 2003; Washington, DC, USA. Palo Alto, CA, USA: AAAI. pp. 321-328.
[10] Borgwardt KM, Kriegel HP. Shortest-path kernels on graphs. In: IEEE 2005 International Conference on Data Mining; 2730 November 2005; Washington, DC, USA. New York, NY, USA: IEEE. pp. 74-81.
[11] Mahe P, Vert JP. Graph kernels based on tree patterns for molecules. Mach Learn 2009; 75: 3-35.
[12] Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM. Weisfeiler-Lehman graph kernels. J Mach Learn Res 2011; 12: 2539-2561.
[13] Deshpande M, Kuramochi M, Wale N, Karypis G. Frequent substructure-based approaches for classifying chemical compounds. IEEE T Knowl Data En 2005; 17: 1036-1050.
[14] Schietgat L, Costa F, Ramon J, Raedt LD. Effective feature construction by maximum common subgraph sampling. Mach Learn 2011; 83: 137-161.
[15] Shervashidze N, Vishwanathan SVN, Petri T, Mehlhorn K, Borgwardt KM. Efficient graphlet kernels for large graph comparison. In: International Conference on Artificial Intelligence and Statistics; 1618 April 2009; Clearwater Beach, FL, USA. Harrisburg, PA, USA: ASAIP. pp. 488-495.
[16] Neumann M, Patricia N, Garnett R, Kersting K. Efficient graph kernels by randomization. In: ACM 2012 European Conference on Machine Learning and Knowledge Discovery in Databases; 2428 September 2012; Bristol, UK. New York, NY, USA: ACM. pp. 378-393.
[17] Costa F, Grave KD. Fast neighborhood subgraph pairwise distance kernel. In: ACM 2010 International Conference on Machine Learning; 2124 June 2010; Haifa, Israel. New York, NY, USA: ACM. pp. 255-262.
[18] Li B, Zhu X, Chi L, Zhang C. Nested subtree hash kernels for large-scale graph classification over streams. In: IEEE 2012 International Conference on Data Mining; 1013 December 2012; Brussels, Belgium. New York, NY, USA: IEEE. pp. 399-408.
[19] Kriege N, Mutzel P. Subgraph matching kernels for attributed graphs. In: IEEE 2012 International Conference on Machine Learning; 1517 July 2012; Xian, China. New York, NY, USA: IEEE. pp. 1-8.
[20] Fr¨ohlich H, Wegner JK, Sieker F, Zell A. Optimal assignment kernels for attributed molecular graphs. In: ACM 2005 International Conference on Machine Learning; 711 August 2005; Bonn, Germany. New York, NY, USA: ACM. pp. 225-232.
[21] Brouwer A, Cohen A, Neumaier A. Distance Regular Graphs. Berlin, Germany: Springer-Verlag, 1989.
[22] Bagrow JP, Bollt EM, Skufca JD, Ben-Avraham D. Portraits of complex networks. Europhys Lett 2008; 81: 68004.
[23] Hoffman T, Sch¨olkopf B, Smola AJ. Kernel methods in machine learning. Ann Stat 2008; 36: 1171-1220.
[24] Gubichev A, Bedathur S, Seufert S, Weikum G. Fast and accurate estimation of shortest paths in large graphs. In: ACM 2010 International Conference on Information and Knowledge Management; 2630 October 2010; Toronto, ON, Canada. New York, NY, USA: ACM. pp. 499-508.
[25] Helma C, King R, Kramer R, Srinivasan A. A survey of the predictive toxicology challenge 20002001. Bioinformatics 2001; 19: 107-108.
[26] Debnath AK, de Compadre RLL, Debnath G, Shusterman AJ, Hansch C. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compouns correlation with molecular orbital energies and hydrophobicity. J Med Chem 1991; 34: 786-797.
[27] Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V et al. Scikit-learn: machine learning in Python. J Mach Learn Res 2011; 12: 2825-2830.
[28] Tan M. Information theoretic feature selection for Weisfeiler-Lehman graph kernels. In: ACM 2013 International Conference on Bioinformatics and Computational Biology; 2225 September 2013; Washington, DC, USA. New York, NY, USA: ACM.
[29] Fei H, Huan J. Structure feature selection for graph classification. In: ACM 2008 International Conference on Information and Knowledge Management; 2630 October 2008; Napa Valley, CA, USA. New York, NY, USA:ACM. pp. 991-1000.