Extensions of marginalized graph kernels

ABSTRACT

Positive definite kernels between labeled graphs have recently been proposed. They enable the application of kernel methods, such as support vector machines, to the analysis and classification of graphs, for example, chemical compounds. These graph kernels are obtained by marginalizing a kernel between paths with respect to a random walk model on the graph vertices along the edges. We propose two extensions of these graph kernels, with the double goal to reduce their computation time and increase their relevance as measure of similarity between graphs. First, we propose to modify the label of each vertex by automatically adding information about its environment with the use of the Morgan algorithm. Second, we suggest a modification of the random walk model to prevent the walk from coming back to a vertex that was just visited. These extensions are then tested on benchmark experiments of chemical compounds classification, with promising results.

REFERENCES

• 1: Debnath, A. K., de Compadre, R. L. L., Debnath, G., Schusterman, A., & Hansch, C. (1991). Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 786--797.
• 2: Gärtner, T., Flach, P., & Wrobel, S. (2003). On graph kernels: Hardness results and efficient alternatives. Proc. of the Sixteenth Annual Conference on Computational Learning Theory and the Seventh Annual Workshop on Kernel Machines. Heidelberg: Springer-Verlag.
• 3: Gribskov, M., & Robinson, N. L. (1996). Use of receiver operating characteristic (ROC) analysis to evaluate sequence matching. Computers and Chemistry, 20, 25--33.
• 4: Kashima, H., Tsuda, K., & Inokuchi, A. (2003). Marginalized kernels between labeled graphs. Proceedings of the Twentieth International Conference on Machine Learning (pp. 321--328). AAAI Press.
• 5: King, R. D., Muggleton, S. H., Srinivasan, A., & Sternberg, M. J. E. (1996). Structure-activity relationships derived by machine learning: The use of atoms and their bond connectivities to predict mutagenicity by inductive logic programming. Proc. Natl. Acad. Sci. USA, 93, 438--442.
• 6: Morgan, H. (1965). The generation of unique machine description for chemical structures - a technique developped at chemical abstracts service. Journal of Chemical Documentation, 107--113.
• 7: Schölkopf, B., & Smola, A. J. (2002). Learning with kernels. Cambridge, MA, MIT Press.
• 8: Smola, A., & Kondor, I. (2003). Kernels and regularization on graphs. Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Colt/Kernel 2003 (pp. 144--158). Springer.
• 9: Toivonen, H., Srinivasan, A., King, R. D., Kramer, S., & Helma, C. (2003). Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 19, 1183--1193.
• 10: Tsuda, K., Kin, T., & Asai, K. (2002). Marginalized kernels for biological sequences. Bioinformatics, 18, S268--S275.